Solved

understanding single sweep multi join

Posted on 2009-05-07
17
842 Views
Last Modified: 2012-05-06
Hi

The MySQL manual says the following about the singl sweep multi join method.

"MySQL resolves all joins using a single-sweep multi-join method. This means that MySQL reads a row from the first table, and then finds a matching row in the second table, the third table, and so on. When all tables are processed, MySQL outputs the selected columns and backtracks through the table list until a table is found for which there are more matching rows. The next row is read from this table and the process continues with the next table."

I would like to check I am understanding this. Take 3 tables, Table A, B and C all of which have 2 columns ID and col1. Then take the following SQL statement

Select * from table A join tableB on tableA.col1 = TableB.Col1 join tableC on tableb.col1 = tableC.col1

The tables have this data

Table A               Table B                    Table C
id   col1               id     col1                 id     col1
1   10                 1     10                      1      10
2   10                 2     10                      2      10

Does the following happen

a)mysql finds row 1 in table a and joins it to row 1 in table b AND then joins to row 1 in column C. I will describe this row as A(1), B(1), C(1)
B) this row is output
c) mysql looks in table c for anything else that will join onto the already joined rows from table A and B
D) row 2 in table c will join
e) row is output. I will describe this row as A(1), B(1), C(2)
f) no more rows in table C will join so mysql backtracks to table b
g) row 2 in table b will join row 1 in table a
h) mysql moves to table c and joins row1 - A(1), B(2), C(1) and then row 2 - A(1), B(2), C(2)
i) no more rows in table B will join so mysql backtrack to table A and moves to row 2
j) the next rows output are A(2), B(1), C(1) - A(2), B(1), C(2) - A(2), B(2), C(1)  - A(2), B(2), C(2)

thanks in advance
andrea
0
Comment
Question by:andieje
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 10
  • 7
17 Comments
 
LVL 20

Expert Comment

by:ChristoferDutz
ID: 24327615
It seems that MySQL seems to evaluate from the outside in ... so the joins are done exaclty the other way around.

I used this query just out of interest:
Select A.id, B.id, C.id from A join B on A.col1 = B.col1 join C on B.col1 = C.col1

And the result was the following:
1, 1, 1
2, 1, 1
1, 2, 1
2, 2, 1
1, 1, 2
2, 1, 2
1, 2, 2
2, 2, 2

0
 

Author Comment

by:andieje
ID: 24329835
I don't understand then. How does the result you obtained match with this statement

MySQL resolves all joins using a single-sweep multi-join method. This means that MySQL reads a row from the first table, and then finds a matching row in the second table, the third table, and so on. When all tables are processed, MySQL outputs the selected columns and backtracks through the table list until a table is found for which there are more matching rows. The next row is read from this table and the process continues with the next table."

I must be interpreting this statement incorrectly.
0
 

Author Comment

by:andieje
ID: 24330046
I think I understand what is happening but to me that statement from the mysql manual doesnt describe what is happening intuitively.

This is what i think happens then

a) database finds first row in table a that can join to first row in table b that can then join to first row in table c. This is 1,1,1
b)Now mysql keeps the value of 1 from table C and table b and tries to find any more values from table a that can join. This gives 2,1,1
c) No more rows in table A will join to x,1,1 so mysql keeps the value from table C and moves down to the next one in table b. It tries to find rows in table a that match giving 1,2,1 and 2,2,1.
d) no mores rows in table a match. there are also no more rows in table b so mysql moves down to the next row in table c which gives x,x,2, Mysql tries to find a row in table b that matches, Row 1 matches to gives x,1,2. Mysql mow looks through all of table a to find rows that match gives 1,1,2 and and 2,1,2.
e) now no more rows in table a match so mysql moves down to the next row in table b giving x,2,2. Mysql now looks all through table a to find any matching rows to give 1,2,2 and 2,2,2

Like you said it seems to match outside in

0
Do you have a plan for Continuity?

It's inevitable. People leave organizations creating a gap in your service. That's where Percona comes in.

See how Pepper.com relies on Percona to:
-Manage their database
-Guarantee data safety and protection
-Provide database expertise that is available for any situation

 

Author Comment

by:andieje
ID: 24330175
Me again

I'm really confused now because the order or results returned in your query does not seem to tally with how joins are carried out in this article

http://hackmysql.com/case4
0
 
LVL 20

Expert Comment

by:ChristoferDutz
ID: 24330887
Well you assume the "first" table is the one comming first in the sql query string. From the result above, I'd assume that MySQL processes from the outside to the inside.
0
 

Author Comment

by:andieje
ID: 24334284
i don't really understand and its really important for me to understand as I have to do some query optimisation. Do you mind if I post another questions now I know a little bit more. I have found other people don't tend to answer questions if they already have a couple of comments even if they are unsolved.
many thank
0
 
LVL 20

Accepted Solution

by:
ChristoferDutz earned 500 total points
ID: 24336053
Hey .. I think we were on the right track. I just let MySQL explain what it was doing:
EXPLAIN Select A.id, B.id, C.id from A join B on A.col1 = B.col1 join C on B.col1 = C.col1
The result was:
1, 'SIMPLE', 'A', 'ALL', '', '', '', '', 2, ''
1, 'SIMPLE', 'B', 'ALL', '', '', '', '', 2, 'Using where; Using join buffer'
1, 'SIMPLE', 'C', 'ALL', '', '', '', '', 2, 'Using where; Using join buffer'
So it seems MySQL was doing the following:
- taking A completely and putting it into the join buffer
- taking the join buffer and selecting from B using a where statement (our ON fragment) and putting this into the join buffer.
- taking the join buffer and selecting from C using a where statement

Seems exactly the way it is described in the documentation and it fits to the results.
0
 
LVL 20

Expert Comment

by:ChristoferDutz
ID: 24336099
So just to make it clearer:

SELECT * FROM A
1
2

SELECT * FROM A LEFT JOIN B ON A.col1 = B.col1
1 1
2 1
1 2
2 2
Which is Join every entry in A with every entry in B (Think we can omit the col-thing)

SELECT A.id, B.id, C.id FROM A JOIN B ON A.col1 = B.col1 JOIN C ON B.col1 = C.col1
1 1 1
2 1 1
1 2 1
2 2 1
1 1 2
2 1 2
1 2 2
2 2 2

Which matches the result in my first post.
0
 

Author Comment

by:andieje
ID: 24339971
Hi

I'm still confused. Sorry!

I get the first bit, select all of A and put it in the join buffer. Then the next bit

"taking the join buffer and selecting from B using a where statement (our ON fragment) and putting this into the join buffer."

How does this bit actually happen. It looks to me as if mysql is doing this:

a) get the first row from table B
b) go through the rows in the join buffer one by one to see if they match
c) go to the second row in table B
d) go through the rows in the join buffer one by one to see if they match.

This would give the output you listed.

Is this what happens?
0
 
LVL 20

Expert Comment

by:ChristoferDutz
ID: 24340281
Well I'd think of it like this (just mindjogging)

- Take A and put it in a temporary table.
- Use this temporary table and join this with B and put the result in a new temporary table.
- Use this second temporary table and join this with C.

Now just call this temporary table "join buffer" ... ther you are.
This does respect the MySQL documentation and produce the output listed above.
0
 

Author Comment

by:andieje
ID: 24344976
Hi

Thanks for your last answer. However I need to understand the 'join' bit in more detail. I understand that you take table A and put it in the join buffer or a temporary table and then join this to table B. But how is the join actually carried out. Specifically i want to know how mysql finds rows in table A that match rows in table B. As i said in my last comment, does it take the first row in table B and then look through all of table A for matches and then move on to the second row. Or it could do this the opposite way round (i.e. take the rows in table A one by one). Or it could do something completely different.

Many thanks
0
 
LVL 20

Expert Comment

by:ChristoferDutz
ID: 24352992
Well if it works the way the MySQL documentation describes it, it takes a row from the join-buffer (in the first step containing only A) and checks it there are any rows in B where the "ON" part of the join matches. It then does a join with these rows and outputs them into a new joinbuffer. Then it takes the next row of the joinbuffer and does the same for this.

(Usually I you reduce the amount of values returned by the join by using "WHERE" the query optimizer should automatically propagate the filter to the join operation as well ... so not only the ON part is used for filtering, but also the part of the WHERE that dealy only with records of B)
0
 

Author Comment

by:andieje
ID: 24369391
I am sorry for being a real pain here but if it does what you say above, it wouldn't return the rows in the same order as returned by the query would it?
0
 

Author Comment

by:andieje
ID: 24369440
Sorry, I'll try again as that wasn't very clear

If it did what you say above wouldn't you get

SELECT * FROM A
1
2

SELECT * FROM A LEFT JOIN B ON A.col1 = B.col1
1 1
1 2
2 1
2  2

This is different than a comment you gave earlier in this thread. If it performs the join like this you wouldn't get the rows output in the same order as returned by mysql. This is why I am getting confused I think

0
 

Author Comment

by:andieje
ID: 24425343
Hi
If this question is abandoned I will open another question and try again if you don't mind. I have little change of attracting new attention to an old question with 14 posts.
thanks
0
 
LVL 20

Expert Comment

by:ChristoferDutz
ID: 24427003
Sorry for the long delay ... I was in Project finalisation stress and couldn't find the time to look in here. I'd suggest to reopen your question. I promise not to participate in the discussion :-)

I would be very interested though, what you need this information for anyway. You said, that you were thinking of query optimisation. What are you actually trying to optimize? Maybe this yould attract more attention, because I think there are more practical DB professionals here than theoretical DB therory guys.
0
 

Author Closing Comment

by:andieje
ID: 31579063
many thanks
0

Featured Post

 [eBook] Windows Nano Server

Download this FREE eBook and learn all you need to get started with Windows Nano Server, including deployment options, remote management
and troubleshooting tips and tricks

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

As a database administrator, you may need to audit your table(s) to determine whether the data types are optimal for your real-world data needs.  This Article is intended to be a resource for such a task. Preface The other day, I was involved …
In this series, we will discuss common questions received as a database Solutions Engineer at Percona. In this role, we speak with a wide array of MySQL and MongoDB users responsible for both extremely large and complex environments to smaller singl…
NetCrunch network monitor is a highly extensive platform for network monitoring and alert generation. In this video you'll see a live demo of NetCrunch with most notable features explained in a walk-through manner. You'll also get to know the philos…
Sometimes it takes a new vantage point, apart from our everyday security practices, to truly see our Active Directory (AD) vulnerabilities. We get used to implementing the same techniques and checking the same areas for a breach. This pattern can re…

636 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question