Take the 2-minute tour ×
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

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.

share|improve this question

migrated from stackoverflow.com May 6 '12 at 19:16

This question came from our site for professional and enthusiast programmers.

    
Do not concentrate on JOIN Vs Cross Product please. I understand the difference. –  Abhishek Sagar May 5 '12 at 11:32
    
Check here and here. –  vyegorov May 5 '12 at 12:00
1  
Here is a very good article explaining the various join strategies in the different DBMS: use-the-index-luke.com/sql/join –  a_horse_with_no_name May 6 '12 at 20:09

3 Answers 3

up vote 1 down vote accepted

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.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.