How is a join performed by a database engine?

Question

How is a join between two tables actually performed by a database engine?

I am sure that listing one tuple against all tuples of the other table cannot be the way to perform the join; it's just a way of understanding what the output will look like. Otherwise, for two tables containing 1000 tuples each, a join would prepare an intermediate data set of 1000*1000 tuples! That's hard to believe.

Answer 1

There are a number of ways depending on what the DBMS thinks you want versus what is helped in the database.

1. Read a row from the first table, then read any matching rows from the second table. This is the preferred method when you are requesting a very few rows and there are indexes to support the read of the second table.
2. Matching index scan, select the required set from an index of the first table, then match this set to an index of the second table (usually after a sort), then fetch the required rows. Usually this method is used where a substantial number of rows are requested in a particular sequence.
3. Brute force, get all the rows from the first table and sort them into the right sequence, then get all the rows from the second table and sort them into the right sequence, then merge the results. Usually this method is used when there are no usable indexes to support the join. Its a performance pig and only used where nothing else will do.

There are many variations on these three methods which vary from RDBMS to RDBMS and the more expensive commercial databases have dozens of subtle optimizations which they will use depending on the circumstances.

Answer 2

My understanding: let's consider two tables, A and B (relationship is one-to-many). JOIN creates a temp table with the requested fields FROM A and B. For each row of B, along with the requested fields from table B, appends the needed fields of table A's row whose primary key is equal to B's foreign key.

Too bad this are just my thoughts, so they might not be what you're looking for.

Answer 3

Well, if you do not have an additional filter in place, the dataset of 1000 * 1000 rows is the thing you asked for.

However, if you have additional conditions, the strategy that is used had to depend on that conditions. There will be no general answer on your question.

PostgreSQL for example uses three different strategies for JOINs, depending on the situation. You can read about them here.

You can get the information which strategy is chosen by issuing the your query preceded by an EXPLAIN, like

EXPLAIN SELECT * FROM t1 LEFT JOIN t2 ON t1.a > t2.b

Looking into this output often gives you valuable hints on how to improve the query by reformulating your condition in a way that a more powerful join strategy is chosen.