Friday, May 18, 2007

Anatomy of a Query

To write a good and correct query it is very important to understand the logical processing of a query. It is sad that very few SQL programming manuals start with that. Here is a look at the insides of logical query processing.

First, to start with a note: the logical processing of a query does not guarantee that the query will be executed that way. Since the cost based optimization of SQL Server goes through a few steps to find the optimal execution plan, it may choose to process the query different way that the sequence of steps below. Examples are when a WHERE predicate is applied in a JOIN, or when it is pushed down to the HAVING clause.

The logical query processing determines logically what the final result set would look like, regardless of how the database engine will manage to generate that result physically.

Here are the phases of the logical query processing in order of processing:

FROM: This is where it all starts! The FROM defines the source table(s) for the processing. If more than one table is included, then a Cartesian product (cross join) is performed between the first two tables. The result of the Cartesian product is every possible combination of a row from the first table and a row from the second table. That is, if one of the tables has M rows and the other one has N rows then the result set will be M x N rows.

ON: Next, the ON filter is applied to the result set. Only rows that match the join condition are selected.

OUTER: If an OUTER join is used, then rows from the preserved table for which a match was not found are added back. In INNER joins this phase is skipped. If more than two tables are in the FROM clause, then FROM/ON/OUTER are applied between the current result set and the next table, until all tables are processed.

WHERE: The next step is to apply the WHERE filter to the result set. Rows that satisfy the where conditions are selected. Only conditions that evaluate to TRUE (not UNKNOWN or FALSE) will pass.

GROUP BY: The result set rows are divided in groups based on the column list specified in GROUP BY. Rows of the grouped set must be only grouping columns, aggregate functions (i.e. COUNT, SUM, AVG, MIN, MAX), function or constants, and an expression made up of the first three items. Important to note here is that NULL values are considered as equal and grouped into one group.

HAVING: Next, the HAVING filter is applied. Only groups that match the having conditions are selected. If a group doesn't satisfy the conditions, then the whole group is removed from the result set. If there is no GROUP BY the entire result set is treated as one group.

SELECT: Here it is, the SELECT list! The SELECT list is processed down here, even that it is the first line in the query. At this time column aliases are added. Steps prior to this in the list cannot use the column aliases, only the following steps will see the aliases. This is the step that will define the columns in the result set.

If there is a SELECT DISTINCT, then the duplicate rows are removed. Just like in GROUP BY, NULLs are treated as matching.

ORDER BY: The rows of the result set are sorted according to the column list specified in the ORDER BY clause. Only using ORDER BY can guarantee a sort order for rows. Otherwise the tables are unordered sets. At this step the result set is transformed to a cursor. Also, NULLs are considered equal for sorting. The ANSI standard doesn't allow to order by columns that are not included in the SELECT list, but SQL Server allows doing that (even by expressions based on those columns). Columns in the ORDER by can be referred to by the alias or by their ordinal number.

A couple more notes. The CUBE & ROLLUP are processed after GROUP BY. At that point the super-groups are added to the result set. Also, TOP which is T-SQL specific is processed after ORDER BY, and there the specified number or percentage or rows are selected in the final result set.

For nested queries, the innermost queries can reference columns and tables in the queries in which they are contained.

6 comments:

Nav said...

Great post! Your blog has provided immense help to me and my peers at work! Everytime I have a question or i'm trying to do something different and i'm stumped i check your blog first. Thanks Plamen.

Vamshi said...

Its little bit changed in SQL Server 2008 (Not a significant change though). See Inside Microsoft® SQL Server® 2008: T-SQL Querying

Naomi said...

Where CROSS/OUTER APPLY fit in this picture?

Plamen Ratchev said...

Hi Naomi,

The APPLY operator fits in the same place where the JOIN operator fits in the logical order. When you have multiple table operators they are processed from left to right. Depending on that the APPLY operator will be logically processed in the order it appears in the FROM clause. Please see Itzik Ben-Gan's poster, it visualizes this very well: http://tsql.solidq.com/books/insidetsql2008/Logical%20Query%20Processing%20Poster.pdf

Trace said...

Plamen,

I have a question regarding the WHERE operator in SQL SERVER 05. In a nested JOIN containing a GROUP BY clause and an aggregate function condition, if I use a WHERE filter between the GROUP BY clause and the FROM clause it does not filter the data. Why is that?

Plamen Ratchev said...

Trace,

Can you please post your query? If you have WHERE clause filters they should apply.