Question on anatomy of a query

"Erland Sommarskog" wrote in message

> tshad (tfs@dslextreme.com) writes:
>> I was looking at an article by Plamen Ratchev (which I had printed a
>> while ago but can't find it online anymore) where he states that the
>> first thing a query does if there are 2 tables involved is create a
>> Cartesian Product (cross Join) between each table. Then the ON filter is
>> applied.
>>
>> If Table A has 20,000,000 rows and Table B has 30,000,000 rows - the
>> system would read all the rows and put all the combinations together to
>> get 600,000,000,000,000 rows? Then apply the ON filter???
>
> That is what would happen if there wasn't an optimizer.
>
Why?

Why wouldn't it just read both tables and take the rows that match the ON
filter?

> Keep in mind that SQL is a *declarative* language. You tell what want. The
> DBMS figures out how to perform the operation in the most efficient
> manner.
>
> But in order to get you what you want, you need to understand the rules
> the computer works according to, and those are the rules than Plamen
> describes.
>
> The optimizer is free to recast the computation order as long as the
> result
> is guaranteed to be the same.
>

I agree that that is what happens which is why it is confusing when thinking
about how joins work. I have always been told that you do the joins left to
right and that each join becomes the left condition of the next join.

For example,

Select *
From tableA a
join tableB b on a.id = b.id
join tablec c on b.id = c.id
join tabled d on c.id = d.id
where something.

In this case, a is joined with b, b is joined with the result of a and b, d
is joined with the results of a and b and c.

If the optimizer changed the order this is done then couldn't you possibly
have a different result, especially if dealing with left joins or there is
multiple criteria in one of the joins.

Thanks,

Tom

>
> --
> Erland Sommarskog, SQL Server MVP, esquel DeleteThis @sommarskog.se
>
> Books Online for SQL Server 2005 at
> http://www.microsoft.com/technet/prodtechnol/sql/2005/downloads/books.mspx
> Books Online for SQL Server 2000 at
> http://www.microsoft.com/sql/prodinfo/previousversions/books.mspx
 >> Stay informed about: Question on anatomy of a query 

You're probably talking about the following article:
http://pratchev.blogspot.com/2007/05/anatomy-of-query.html .

In this article, Platmen make first the explicit note that this is the
logical processing of a query and that it doesn't necessarily reflect it's
physical processing.

--
Sylvain Lafontaine, ing.
MVP - Access
Blog/web site: http://coding-paparazzi.sylvainlafontaine.com
Independent consultant and remote programming for Access and SQL-Server
(French)


"tshad" wrote in message

>I was looking at an article by Plamen Ratchev (which I had printed a while
>ago but can't find it online anymore) where he states that the first thing
>a query does if there are 2 tables involved is create a Cartesian Product
>(cross Join) between each table. Then the ON filter is applied.
>
> If Table A has 20,000,000 rows and Table B has 30,000,000 rows - the
> system would read all the rows and put all the combinations together to
> get 600,000,000,000,000 rows? Then apply the ON filter???
>
> Where would it put the data it just read?
>
> Does it read all this into a temporary table in memory?
>
> Then when it applies the ON predicate, does it them move the rows that
> match to another temporary table?
>
> And if an outer join, move the other rows to the 2nd temporary table?
>
> Thanks,
>
> Tom
>
>
 >> Stay informed about: Question on anatomy of a query 

"Sylvain Lafontaine" wrote in message

> You're probably talking about the following article:
> http://pratchev.blogspot.com/2007/05/anatomy-of-query.html .
>
Actually it is only the first part of the article.

The one I had copied was much longer with examples.

One of the examples had to do placing a filter as part of the ON clause or
as part of the WHERE clause and that it makes a difference in an outer join,
which I assume would not matter in an inner join.

> In this article, Platmen make first the explicit note that this is the
> logical processing of a query and that it doesn't necessarily reflect it's
> physical processing.

But that is what is confusing. Why would you say that logically you put all
the combinations together and then take the ones that match. Logically, I
would think you would say that both tables are read and only the ones that
match are put into a temporary table.

Just curious. I like the article but that part kind of threw me.

Thanks,

Tom

>
> --
> Sylvain Lafontaine, ing.
> MVP - Access
> Blog/web site: http://coding-paparazzi.sylvainlafontaine.com
> Independent consultant and remote programming for Access and SQL-Server
> (French)
>
>
> "tshad" wrote in message
>
>>I was looking at an article by Plamen Ratchev (which I had printed a while
>>ago but can't find it online anymore) where he states that the first thing
>>a query does if there are 2 tables involved is create a Cartesian Product
>>(cross Join) between each table. Then the ON filter is applied.
>>
>> If Table A has 20,000,000 rows and Table B has 30,000,000 rows - the
>> system would read all the rows and put all the combinations together to
>> get 600,000,000,000,000 rows? Then apply the ON filter???
>>
>> Where would it put the data it just read?
>>
>> Does it read all this into a temporary table in memory?
>>
>> Then when it applies the ON predicate, does it them move the rows that
>> match to another temporary table?
>>
>> And if an outer join, move the other rows to the 2nd temporary table?
>>
>> Thanks,
>>
>> Tom
>>
>>
>
>
 >> Stay informed about: Question on anatomy of a query 

When you have more of a background, you might want to read some ANSI/
ISO Standards. They are dull, boring and complicated and in a strange
language we called "Standard-speak" when i was on the committee. One
of the technical terms is "effectively" which means that we are about
to describe a way to do something (like that CROSS JOIN thing) which
will have some effect. But any process that produces that same result
is just as good.

I work out a full SELECT statement in SQL FOR SMARTIES as per the
formal process just to show how this could be done.
 >> Stay informed about: Question on anatomy of a query 

This is important when you want to understand the old ANSI syntax for the
Outer Join: *= and =*.

Contrary to what many people think, *= is not identical with a Left Join and
=* is not identical with a Right Join. If you have a single *= or =* in
your query then yes, remplacing it with a modern Left or Right Join will
give you the same result. However, if you have more than one then replacing
them with their corresponding Left or Right Join can give a vastly different
result.

This is because all the Cross Join are done before all the *= and =* are
applied at the same time in a single operation after that. In the case of
the modern Left and Right Join, all the joins are performed consecutively
(one after the other); so when you have more than one join, in many cases,
you'll get a different result between a combination of multiples *= and/or
=* in comparaison to a combination of the modern Left and Right join.

In the case of modern outer joins, there is no need to go into this logical
application of a Cross Join but in the case of the older Ansi outer joins,
yes, it is.

--
Sylvain Lafontaine, ing.
MVP - Access
Blog/web site: http://coding-paparazzi.sylvainlafontaine.com
Independent consultant and remote programming for Access and SQL-Server
(French)


"tshad" wrote in message

>
> "Sylvain Lafontaine" wrote in message
>
>> You're probably talking about the following article:
>> http://pratchev.blogspot.com/2007/05/anatomy-of-query.html .
>>
> Actually it is only the first part of the article.
>
> The one I had copied was much longer with examples.
>
> One of the examples had to do placing a filter as part of the ON clause or
> as part of the WHERE clause and that it makes a difference in an outer
> join, which I assume would not matter in an inner join.
>
>> In this article, Platmen make first the explicit note that this is the
>> logical processing of a query and that it doesn't necessarily reflect
>> it's physical processing.
>
> But that is what is confusing. Why would you say that logically you put
> all the combinations together and then take the ones that match.
> Logically, I would think you would say that both tables are read and only
> the ones that match are put into a temporary table.
>
> Just curious. I like the article but that part kind of threw me.
>
> Thanks,
>
> Tom
>
>>
>> --
>> Sylvain Lafontaine, ing.
>> MVP - Access
>> Blog/web site: http://coding-paparazzi.sylvainlafontaine.com
>> Independent consultant and remote programming for Access and SQL-Server
>> (French)
>>
>>
>> "tshad" wrote in message
>>
>>>I was looking at an article by Plamen Ratchev (which I had printed a
>>>while ago but can't find it online anymore) where he states that the
>>>first thing a query does if there are 2 tables involved is create a
>>>Cartesian Product (cross Join) between each table. Then the ON filter is
>>>applied.
>>>
>>> If Table A has 20,000,000 rows and Table B has 30,000,000 rows - the
>>> system would read all the rows and put all the combinations together to
>>> get 600,000,000,000,000 rows? Then apply the ON filter???
>>>
>>> Where would it put the data it just read?
>>>
>>> Does it read all this into a temporary table in memory?
>>>
>>> Then when it applies the ON predicate, does it them move the rows that
>>> match to another temporary table?
>>>
>>> And if an outer join, move the other rows to the 2nd temporary table?
>>>
>>> Thanks,
>>>
>>> Tom
>>>
>>>
>>
>>
>
>
 >> Stay informed about: Question on anatomy of a query 

"--CELKO--" wrote in message

> When you have more of a background, you might want to read some ANSI/
> ISO Standards. They are dull, boring and complicated and in a strange
> language we called "Standard-speak" when i was on the committee. One
> of the technical terms is "effectively" which means that we are about
> to describe a way to do something (like that CROSS JOIN thing) which
> will have some effect. But any process that produces that same result
> is just as good.
>
> I work out a full SELECT statement in SQL FOR SMARTIES as per the
> formal process just to show how this could be done.

I'll have to check that out when I get home.

Thanks,

Tom
 >> Stay informed about: Question on anatomy of a query 

tshad (tfs@dslextreme.com) writes:
> Why?
>
> Why wouldn't it just read both tables and take the rows that match the ON
> filter?

But how it read them? How would it know which fits together? Logically the
only way to do this is to create all combinations and then filter.

Oh, in practice the optimizer does it another way, but here is the matter
of finding a neutral description.

But as Celko points out, the SQL standards are written in a very formalistic
language, and they are defintely not trivial to understand.

--
Erland Sommarskog, SQL Server MVP, esquel.TakeThisOut@sommarskog.se

Links for SQL Server Books Online:
SQL 2008: http://msdn.microsoft.com/en-us/sqlserver/cc514207.aspx
SQL 2005: http://msdn.microsoft.com/en-us/sqlserver/bb895970.aspx
SQL 2000: http://www.microsoft.com/sql/prodinfo/previousversions/books.mspx
 >> Stay informed about: Question on anatomy of a query 

"Erland Sommarskog" wrote in message

> tshad (tfs@dslextreme.com) writes:
>> Why?
>>
>> Why wouldn't it just read both tables and take the rows that match the ON
>> filter?
>
> But how it read them? How would it know which fits together? Logically the
> only way to do this is to create all combinations and then filter.
>

Makes sense.

Thanks,

Tom

> Oh, in practice the optimizer does it another way, but here is the matter
> of finding a neutral description.
>
> But as Celko points out, the SQL standards are written in a very
> formalistic
> language, and they are defintely not trivial to understand.
>
> --
> Erland Sommarskog, SQL Server MVP, esquel.DeleteThis@sommarskog.se
>
> Links for SQL Server Books Online:
> SQL 2008: http://msdn.microsoft.com/en-us/sqlserver/cc514207.aspx
> SQL 2005: http://msdn.microsoft.com/en-us/sqlserver/bb895970.aspx
> SQL 2000:
> http://www.microsoft.com/sql/prodinfo/previousversions/books.mspx
>
 >> Stay informed about: Question on anatomy of a query 

And what about the question of the JOINS:

I agree that that is what happens which is why it is confusing when thinking
about how joins work. I have always been told that you do the joins left to
right and that each join becomes the left condition of the next join.

For example,

Select *
From tableA a
join tableB b on a.id = b.id
join tablec c on b.id = c.id
join tabled d on c.id = d.id
where something.

In this case, a is joined with b, b is joined with the result of a and b, d
is joined with the results of a and b and c.

If the optimizer changed the order this is done then you could possibly
have a different result, especially if dealing with left joins or there is
multiple criteria in one of the joins.

Thanks,

To
"tshad" wrote in message

>
> "Erland Sommarskog" wrote in message
>
>> tshad (tfs@dslextreme.com) writes:
>>> Why?
>>>
>>> Why wouldn't it just read both tables and take the rows that match the
>>> ON
>>> filter?
>>
>> But how it read them? How would it know which fits together? Logically
>> the
>> only way to do this is to create all combinations and then filter.
>>
>
> Makes sense.
>
> Thanks,
>
> Tom
>
>> Oh, in practice the optimizer does it another way, but here is the matter
>> of finding a neutral description.
>>
>> But as Celko points out, the SQL standards are written in a very
>> formalistic
>> language, and they are defintely not trivial to understand.
>>
>> --
>> Erland Sommarskog, SQL Server MVP, esquel.TakeThisOut@sommarskog.se
>>
>> Links for SQL Server Books Online:
>> SQL 2008: http://msdn.microsoft.com/en-us/sqlserver/cc514207.aspx
>> SQL 2005: http://msdn.microsoft.com/en-us/sqlserver/bb895970.aspx
>> SQL 2000:
>> http://www.microsoft.com/sql/prodinfo/previousversions/books.mspx
>>
>
>
 >> Stay informed about: Question on anatomy of a query 

tshad (tfs@dslextreme.com) writes:
> For example,
>
> Select *
> From tableA a
> join tableB b on a.id = b.id
> join tablec c on b.id = c.id
> join tabled d on c.id = d.id
> where something.
>
> In this case, a is joined with b, b is joined with the result of a and
> b, d is joined with the results of a and b and c.
>
> If the optimizer changed the order this is done then you could possibly
> have a different result, especially if dealing with left joins or there is
> multiple criteria in one of the joins.

No. An inner join is just like addition and multiplication a commutative
operator. Meaning that "A JOIN B" <=> "B JOIN A".

With left and right joins this is obviously not the case.

--
Erland Sommarskog, SQL Server MVP, esquel RemoveThis @sommarskog.se

Books Online for SQL Server 2005 at
http://www.microsoft.com/technet/prodtechnol/sql/2005/downloads/books.mspx
Books Online for SQL Server 2000 at
http://www.microsoft.com/sql/prodinfo/previousversions/books.mspx
 >> Stay informed about: Question on anatomy of a query 

You are probably mixing up the two articles, for logical query
processing (http://pratchev.blogspot.com/2007/05/anatomy-of-
query.html) and for outer joins (http://pratchev.blogspot.com/2009/06/
outer-joins.html). As it has been already said, logical and physical
processing differ a lot. Logical is more like the description of the
logical flow to extract data, physical is how it is really done by the
query engine. The separation of the cross join and matching on join
predicates is done to separate the different steps logically. But when
executed in reality some predicates may be applied much earlier before
the join.

--
Plamen Ratchev
http://www.SQLStudio.com
 >> Stay informed about: Question on anatomy of a query 

"Erland Sommarskog" wrote in message

> tshad (tfs@dslextreme.com) writes:
>> For example,
>>
>> Select *
>> From tableA a
>> join tableB b on a.id = b.id
>> join tablec c on b.id = c.id
>> join tabled d on c.id = d.id
>> where something.
>>
>> In this case, a is joined with b, b is joined with the result of a and
>> b, d is joined with the results of a and b and c.
>>
>> If the optimizer changed the order this is done then you could possibly
>> have a different result, especially if dealing with left joins or there
>> is
>> multiple criteria in one of the joins.
>
> No. An inner join is just like addition and multiplication a commutative
> operator. Meaning that "A JOIN B" <=> "B JOIN A".

Right

but would:
A JOIN B
B JOIN C
C JOIN D

be the same thing as
A JOIN B
C JOIN D
B JOIN C

If so, the 3rd join IS NOT joining against the previous result set.

In otherwords, would the first example be:

(A JOIN B
B JOIN C) a1
D JOIN a1

Where D is being joined with the result of the 1st 2 joins so only joining
with the rows in C that matched with the rows in B that matched with the
rows in A.

This could give less rows that the original set than if D were JOIN'd with
the whole table of C.

And if result sets were joined with each other then the 2nd example would
have the results of A JOIN B join'd with the result set of C JOIN B.

Of course, if previous result sets are not used that this is all mute and it
doesn't matter what the order is.

Thanks,

Tom
>
> With left and right joins this is obviously not the case.
>
> --
> Erland Sommarskog, SQL Server MVP, esquel.TakeThisOut@sommarskog.se
>
> Books Online for SQL Server 2005 at
> http://www.microsoft.com/technet/prodtechnol/sql/2005/downloads/books.mspx
> Books Online for SQL Server 2000 at
> http://www.microsoft.com/sql/prodinfo/previousversions/books.mspx
 >> Stay informed about: Question on anatomy of a query 

If you have the same join predicates then the results of the multiple
inner joins (no matter how you group or rearrange them) will be always
the same. Try it with example and see.

The order of tables in JOIN matters only when you deal with outer
joins (because of the added outer rows).

--
Plamen Ratchev
http://www.SQLStudio.com
 >> Stay informed about: Question on anatomy of a query