Algorithm for finding best match between two database rows - Computer Science Stack Exchange most recent 30 from cs.stackexchange.com 2019-09-21T21:29:58Z https://cs.stackexchange.com/feeds/question/64749 https://creativecommons.org/licenses/by-sa/4.0/rdf https://cs.stackexchange.com/q/64749 0 Algorithm for finding best match between two database rows kitsuneFox https://cs.stackexchange.com/users/19301 2016-10-17T21:45:46Z 2016-11-04T20:25:42Z <p>Let's say we have a database with a given table named food. The food table has many columns but we are interested in only 3 of them:</p> <ol> <li><code>buyorsell</code>, which specifies if the food is for selling or buying. </li> <li><code>amount</code>, which is the amount of food to be bought or sold. </li> <li><code>isVegan</code>, which is set true if the food is vegan. </li> </ol> <p>The goal is to find the best match between 2 rows. The best match should satisfy the following rules:</p> <ol> <li>Both rows have the same value for 'isVegan'</li> <li>One row should be buy/sell and the other row must be the opposite </li> <li>Both amounts must be equal</li> </ol> <p>The table will have millions of rows and the table is changing rapidly. </p> <p>What is the right algorithm in matters of speed and resource usage for this matching problem? </p> https://cs.stackexchange.com/questions/64749/-/65562#65562 1 Answer by Rick Decker for Algorithm for finding best match between two database rows Rick Decker https://cs.stackexchange.com/users/13107 2016-11-04T20:25:42Z 2016-11-04T20:25:42Z <p>Assuming we're talking about a relational database, a straightforward query would be to do a theta-join on two copies of the <em>food</em> relation, renamed $a$ and $b$, with the condition $$\theta = (a.isvegan)\land\neg(a.buyorsell=b.buyorsell)\land(a.amount=b.amount)$$ Without knowing the internal workings of the DB engine, your question about the "right" algorithm to use is impossible to answer. For instance, does the engine use, say, merge join or hash join to answer the query; is the table sorted by some attribute, do you have indexes to help you, if so how are they implemented?</p>