SQL Server Logical Query Processing - how does it manage the huge datasets?

Question

I'm doing some reading on SQL Server performance:

http://www.amazon.com/Inside-Microsoft-SQL-Server-2005/dp/0735623139/ref=sr_1_6?ie=UTF8&s=books&qid=1267032068&sr=8-6

One of the surprising things I came across was how it processes the "FROM" phase in its Logical Processing. From what I understand, SQL Server will do the following:

1) For the first two tables, it will create a virtual table (VT1) consisting of a Cartesian join of the two tables

2) For every additional table, it will create a Cartesian join of VT1 and the additional table, with the result becoming VT1

I'm sure there is alot more to it under the covers, but at face value, this seems like it would involve a huge amount of processing/memory if you're dealing with big tables (and big queries).

I was just wondering whether anyone had a quick explanation of how SQL Server is able to do this in any sort of realistic time/space frame?

Answer 1

In reality the optimiser will look at the whole query, estimated rows, statistics, constraints etc

Logically, it is in the order mentioned though

Contrived example:

SELECT
   BT.col1, LT.col2
FROm
   BigTable BT
   JOIN
   LT.Table LT ON BT.FKCol = LT.PKCol
WHERE
   LT.PKCol = 2
ORDER BY
   BT.col1

The cartesian of BT and LT could be 100s of millions.

But the optimiser:

• knows PKCol is unique so it expects only one row
• can use statistics to estimate the number of rows from BT
• looks for indexes (eg covering index on BT for FKCol INLCUDE col1)
• will probably apply the WHERE first
• will look ahead for an ORDER BY or GROUP BY for example to see if it can save some spooling (resorting)

Answer 2

If you are really interested in how SQL Server does what it does, please read this book: http://www.amazon.com/Microsoft-SQL-Server-2008-Internals/dp/0735626243/ref=sr_1_1?ie=UTF8&s=books&qid=1267033666&sr=8-1

Answer 3

I don't know the resource you are reading, but what you describe is the behavior of:

SELECT ... FROM tableA, tableB, tableC, ....

This uses a cartesian join (also called a cross join) and is very expensive. With large enough datasets SQL Server (or any RDBMS) can't do this in any sort of realistic time/space frame.

Using an ON clause and specifying the JOIN type performs vastly better:

SELECT ... FROM tableA JOIN tableB on tableB.a_id = tableA.a_id

In real applications cross joins should be rare or at least limited to very small datasets. For many applications it's not uncommon to never have a cross join.

Answer 4

The carthesian join is just a description of the result, not an actual result. After the full carthesian join of tables A, B, C...X, the filter operators are applied (still as a definition), things like ON clauses of the join and WHERE clauses of the query. In the end this definition is in turn transformed into an execution plan, which will contain physicall operators like Nested Loops or Hash Join or Merge Join, and this operators, when iterated, will produce the results as requested in the query definition.

So the big 100x100x100x100... carthesian cube is never materialized, is just a definition.