Execution Plan

books

Why I started my blog with some posts about query optimizer, execution plans and logical processing? Well, before you learn about codes and more codes we need to know how this works in SQL Server. For example, the developer know how to write a single select, insert or update statement or  a batch with conditions clauses like IF, but what happens when you execute the query? We need to know how the whole thing works and the concepts to work with sets.

So, SQL Server and others databases has a lot of information for your simple or complex batch to work well and others tools to help our job. The most important is to write the best query as possible. If you write a simple select, the first thing your have to see before you put in your application is the execution plan, IO and time of query response.

People are not very keen on waiting. They get nervous in a traffic jam. They are not too satisfied if they have to sit without a drink for a while in a bar. Similarly, they want their applications to be as responsive as possible. End users perceive performance problems through waiting.

Except for very simple queries, a query can be executed in many different ways. How many ways? Well, the number of different ways of execution or execution plans grows exponentially with query complexity.

For example, analyze the following pseudo-query very superficially:
SELECT
    A.col5
    , SUM (C.col6) AS col6sum
FROM
    TableA AS A
INNER JOIN TableB AS ON A.col1 B.col1
INNER JOIN TableC AS C ON B.col2 = C.col2
WHERE
    A.col3constant1 AND B.col4 constant2
GROUP BY
    A.col5;

Start with the FROM part. Which tables should SQL Server join first, TableA and TableB or TableB and TableC? And in each join, which of the two tables joined should be the left and which one the right table? The number of all possibilities is six, if the two joins are evaluated linearly, one after another. With evaluation of multiple joins at the same time, the number of
all possible combinations for processing the joins is already 12. The actual formula for possible combinations of join evaluation is n!, or n factorial, for linear evaluation, and (2n -2)!/ (n-1)! for parallel evaluation of possible joins.

This already gives four options for each join. So far, there are 6 x 4 = 24 different options for only the FROM part of this query. But the real situation is even worse. SQL Server can execute a hash join in three different ways. As mentioned, this is just a quick superficial analysis of pseudo-query execution, and for this introduction to query optimization problems, such details are not needed.

In the WHERE clause, two expressions are connected with a logical AND operator. The logical AND operator is commutative, so SQL Server can evaluate the second expression first.

Again, there are two choices. Altogether, there are already 6 x 4 x 2 = 48 choices. And again, the real situation is much worse. Because in the pseudo-query all joins are inner joins and because expressions in the WHERE clause are commutative, SQL Server can even start executing the query with any of the expressions of the WHERE clause, then switch to the FROM clause and perform first a join, evaluate the second expression from the WHERE clause, and so on.

So the number of possible plans is already much higher than 48. For this superficial overview, continue with the GROUP BY clause. SQL Server can execute this part in two ways, as an ordered group or as a hash group. Therefore, the number of options for executing the pseudo-query is already 6 x 4 x 2 x 2 = 96.

The important conclusion is that you can see that the number of different possible execution plans for a query grows factorially with query complexity. You can quickly get billions of possible execution plans. SQL Server has to decide which one to use in a very short time. You wouldn’t want to wait, for example, for a whole day for SQL Server to find out the best possible plan and then execute your queries in 5 seconds instead of in 15 seconds. Now you can imagine the complexity of the problems the SQL Server Query Optimizer has to solve with any single query.

 Writing queries requires basic T-SQL knowledge; writing well-performing queries needs much more advanced knowledge.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s