Say I have 3 tables, A, B , C of sizes 10, 10^4 and 10^6. What is the most efficient way to join them?

This is my reasoning. Assuming you join over primary key, if you join A with C first, you will do 10^7 operations. Also, you will be left with 10 rows in the end at most since A has 10 rows. If you then join the result with B, you will do 10^ 5 operations. Thus, total is 10^ 7 + 10^ 5 .

You do same number of operations if you join A with B and then the result with C. Does the join order really matter here?

Edit: I am new to query optimization. Can we make a decision just based on the size of the tables? If not, below is the schema.

A(sid primary key, studentname)
B(sid,cid,primary key (sid,cid), foreign key (sid) references A(sid))
C(cid, coursename, primarykey(cid))

Also, can you pls point to documents relevant to the topic? THanks

migrated from stackoverflow.com Feb 10 '15 at 6:29

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

  • It might help if you provide a sample schema (DDL), a script that does the INSERTs to populate the tables, and a sample of the SELECT you're talking about? Also, this is tagged both sqlite and mysql - which is it? – Anti-weakpasswords Jan 24 '15 at 4:25
  • Hi. Provided schema. This is sql – Programmer Jan 24 '15 at 4:31
  • 1
    Thank you. I'm still confused, however - if this is a practical question for a specific engine (like MySQL or PostgreSQL or SQL Server), then providing actual runnable CREATE statements, INSERT statements to populate data, and the SELECT you're talking about would help anyone who wants to answer a lot. If this is a pure theory question, then you should remove the mysql tag entirely. – Anti-weakpasswords Jan 24 '15 at 4:38
  • Pure theory question. – Programmer Jan 24 '15 at 5:36
  • @Anti-weakpasswords: now answer pls – Programmer Jan 24 '15 at 5:43

We'd hope to avoid a lot of the operations you estimate. And we do, by having suitable indexes available to the optimizer.

SQL (Structured Query Language) is based on the idea that we specify the results to be returned, and not specifying how those results should be returned.

A relational database management system has a component usually called "the optimizer" that evaluates SQL text, and determines which operations are to be performed to return the specified result in the most efficient manner possible.

The optimizer can consider a lot of possible options to access rows and perform joins (before MySQL version 5.6, the only join method MySQL used was nested loops) and how to satisfy GROUP BY and ORDER BY clauses, etc. With SQLite, the default order is to use the left most table as the driver of the nested loop, but SQLite will use an order other than the default if suitable indexes are available.

In terms of join "order", the order that tables are listed in the FROM clause doesn't (or shouldn't) really influence the access plan selected by MySQL or SQLite (absent any "hints" in the statement and as long as indexes are available and predicates can make use of the indexes.)

We're usually better served if we don't include hints. Those are available to us for those rare cases where other tuning efforts are insufficient and result in a sub-optimal plan. (Tuning efforts such as making sure statistics are up-to-date, making suitable indexes are available, re-writing non-sargable predicates, removing unnecessary derived tables, etc.)

While the join order can be an important component of the optimizer plan, it is only one small piece of the entire SQL tuning puzzle.

A join of a three tables ( "A, B , C of sizes 10, 10^4 and 10^6") on primary or unique keys, or even on non-unique keys won't require "10^ 7 + 10^ 5" operations if we have suitable indexes available. In that case, we are much less concerned with the join order, than we are with avoiding full table scans. The optimizer generally does a good job of figuring out an appropriate join order, unless we have written the query in a way that disallows the optimizer from considering more efficient access paths.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy