SLQ Server: How Query Optimization Works

As you already know from the previous section, the query optimization phase can be divided into the following phases:

  • Query analysis
  • Index selection
  • Join order selection
  • Join processing techniques

The following sections describe these phases. Also, at the end of this section, plan caching will be introduced.

1. Query Analysis

During the query analysis, the optimizer examines the query for search arguments, the use of the OR operator, and the existence of join criteria, in that order. Because the use of the OR operator and the existence of join criteria are self-explanatory, only search arguments are discussed.

A search argument is the part of a query that restricts the intermediate result set of the query. The main purpose of search arguments is to allow the use of existing indices in relation to the given expression. The following are examples of search arguments:

  • emp_fname = ‘Moser’
  • salary >= 50000
  • emp_fname = ‘Moser’ AND salary >= 50000

There are several expression forms that cannot be used by the optimizer as search arguments. To the first group belongs all expressions with the NOT (<>) operator. Also, if you use the expression on the left side of the operator, the existing expression cannot be used as a search argument.

The following are examples of expressions that are not search arguments:

  • NOT IN (‘d1’, ‘d2’)
  • emp_no <> 9031
  • budget * 0.59 > 55000

The main disadvantage of expressions that cannot be used as search arguments is that the optimizer cannot use existing indices in relation to the expression to speed up the performance of the corresponding query. In other words, the only access the optimizer uses in this case is the table scan.

2. Index Selection

The identification of search arguments allows the optimizer to decide whether one or more existing indices will be used. In this phase, the optimizer checks each search argument to see if there are indices in relation to the corresponding expression. If an index exists, the optimizer decides whether or not to use it. This decision depends mainly on the selectivity of the corresponding expression. The selectivity of an expression is defined as the ratio of the number of rows satisfying the condition to the total number of rows in the table. The smaller the number of rows satisfying the condition, the higher the selectivity.

The optimizer checks the selectivity of an expression with the indexed column by using statistics that are created in relation to the distribution of values in a column. The query optimizer uses this information to determine the optimal query execution plan by estimating the cost of using an index to execute the query.

The following sections discuss in detail selectivity of an expression with the indexed column and statistics. (Because statistics exist in relation to both indices and columns, they are discussed separately in two sections.)

NOTE The Database Engine automatically creates (index and column) statistics if the database option called AUTO_CREATE_STATISTICS is activated. (This option is described later in this chapter.) Also, you can explicitly create statistics using the CREATE STATISTICS statement (as demonstrated in Example 19.12 later in this chapter).

2.1. Selectivity of an Expression with the Indexed Column

As you already know, the optimizer uses indices to improve query execution time. When you query a table that doesn’t have indices, or if the optimizer decides not to use an existing index, the system performs a table scan. During the table scan, the Database Engine sequentially reads the table’s data pages to find the rows that belong to the result set. Index access is an access method in which the database system reads and writes data pages using an existing index. Because index access significantly reduces the number of I/O read operations, it often outperforms a table scan.

The Database Engine uses a nonclustered index to search for data in one of two ways. If you have a heap (a table without a clustered index), the system first traverses the nonclustered index structure and then retrieves a row using the row identifier (RID). If you have a clustered table, however, the traversal of the nonclustered index structure is followed by the traversal of the index structure of the table’s clustered index. On the other hand, the use of a clustered index to search for data is always unique: the Database Engine starts from the root of the corresponding B+-tree and usually after three or four read operations reaches the leaf nodes, where the data is stored. For this reason, the traversing of the index structure of a clustered index is almost always significantly faster than the traversing of the index structure of the corresponding nonclustered index.

From the preceding discussion, you can see that the answer to which access method (index scan or table scan) is faster isn’t straightforward and depends on the selectivity and the index type.

Tests that I performed showed that a table scan often starts to perform better than a nonclustered index access when at least 10 percent of the rows are selected. In this case, the optimizer’s decision of when to switch from nonclustered index access to a table scan must not be correct. (If you think that the optimizer forces a table scan prematurely, you can use the INDEX query hint to change its decision, as discussed later in this chapter.)

For several reasons, the clustered index usually performs better than the nonclustered index. When the system scans a clustered index, it doesn’t need to leave the B+-tree structure to scan data pages, because the pages already exist at the leaf level of the tree. Also, a nonclustered index requires more I/O operations than a corresponding clustered index. The nonclustered index either needs to read data pages after traversing the B+-tree or, if a clustered index for another table’s column(s) exists, needs to read the clustered index’s B+-tree structure.

Therefore, you can expect a clustered index to perform significantly better than a table scan even when selectivity is poor (that is, the percentage of returned rows is high, because the query returns many rows). The tests that I performed showed that when the selectivity of an expression is 75 percent or less, the clustered index access is generally faster than the table scan.

2.2. Index Statistics

Index statistics are generally created when an index for the particular column(s) is created. The creation of index statistics for an index means that the Database Engine creates a histogram based on up to 200 values of the column. (Therefore, up to 199 intervals are built.) The histogram specifies, among other things, how many rows exactly match each interval, the average number of rows per distinct value inside the interval, and the density of values.

NOTE Index statistics are always created for one column. If your index is a composite (multicolumn)

index, the system generates statistics for the first column in the index.

If you want to create index statistics explicitly, you can use the following tools:

  • sp_createstats system procedure
  • SQL Server Management Studio

The sp_createstats system procedure creates single-column statistics for all columns of all user tables in the current database. The new statistic has the same name as the column where it is created.

To use Management Studio for index statistics creation, expand the server, expand the Databases folder, expand the database, expand the Tables folder, expand the table, right-click Statistics, and choose New Statistics. The New Statistics on Table dialog box appears. In the dialog box, specify first the name for the new statistics. After that, click the Add button, select column(s) of the table to which to add the statistics, and click OK. Finally, click OK in the New Statistics on Table dialog box.

As the data in a column changes, index statistics become out of date. The out-of-date statistics can significantly influence the performance of the query. The Database Engine can automatically update index statistics if the database option AUTO_UPDATE_STATISTICS is activated (set to ON). In that case, any out-of-date statistics required by a query for optimization are automatically updated during query optimization.

2.3. Column Statistics

As you already know from the previous section, the Database Engine creates statistics for every existing index and the corresponding column. The system can create statistics for nonindexed columns too. These statistics are called column statistics. Together with index statistics, column statistics are used to optimize execution plans. The Database Engine creates statistics for a nonindexed column that is a part of the condition in the WHERE clause.

There are several situations in which the existence of column statistics can help the optimizer to make the right decision. One of them is when you have a composite index on two or more columns. For such an index, the system generates statistics only for the first column in the index. The existence of column statistics for the second column (and all other columns) of the composite index can help the optimizer to choose the optimal execution plan.

The Database Engine supports two catalog views in relation to column statistics (these views can be used to edit the information concerning index statistics, too):

  •  sys.stats
  • sys.stats_columns

The sys.stats view contains a row for each statistic of a table or a view. Besides the name column, which specifies the name of the statistics, this catalog view has, among others, two other columns:

  • auto_created Statistics created by the optimizer
  • user_created Statistics explicitly created by the user

The sys.stats_columns view contains additional information concerning columns that are part of the sys.stats view. (To ascertain this additional information, you have to join both views using the object_id column in both tables as join columns.)

The information provided by the sys.stats and sys.stats_columns catalog views is similar to the information provided by the sys.dm_exec_query_stats dynamic management view (as shown in Example 19.10 later in the chapter).

3. Join Order Selection

Generally, the order in which two or more joined tables are written in the FROM clause of a SELECT statement doesn’t influence the decision made by the optimizer in relation to their processing order.

As you will see in the next section, many different factors influence the decision of the optimizer regarding which table will be accessed first. On the other hand, you can influence the join order selection by using the FORCE ORDER hint (discussed in detail later in the chapter).

4. Join Processing Techniques

The join operation is the most time-consuming operation in query processing. The Database Engine supports the following three different join processing techniques, so the optimizer can choose one of them depending on the statistics for both tables:

  • Nested loop
  • Merge join
  • Hash join

The following subsections describe these techniques.

4.1. Nested Loop

The nested loop processing technique works by “brute force.” In other words, for each row of the outer table, each row from the inner table is retrieved and compared. The pseudo-code in Algorithm 19.1 demonstrates the nested loop processing technique for two tables.

Algorithm 19.1

(A and B are two tables.)

for each row in the outer table A do:

read the row

for each row in the inner table B do:

read the row

if A.join_column = B.join_column then

accept the row and add it to the resulting set

end if

end for

end for

In Algorithm 19.1, every row selected from the outer table (table A) causes the access of all rows of the inner table (table B). After that, the comparison of the values in the join columns is performed and the row is added to the result set if the values in both columns are equal.

The nested loop technique is very slow if there is no index for the join column of the inner table. Without such an index, the Database Engine would have to scan the outer table once and the inner table n times, where n is the number of rows of the outer table. Therefore, the query optimizer usually chooses this method if the join column of the inner table is indexed, so the inner table does not have to be scanned for each row in the outer table.

4.2. Merge Join

The merge join technique provides a cost-effective alternative to the nested loop technique. The rows of the joined tables must be physically sorted using the values of the join column. Both tables are then scanned in order of the join columns, matching the rows with the same value for the join columns. The pseudo-code in Algorithm 19.2 demonstrates the merge join processing technique for two tables.

Algorithm 19.2

    1. Sort the outer table A in ascending order using the join column
    2. Sort the inner table B in ascending order using the join column

for each row in the outer table A do:

read the row

for each row from the inner table B with a value less than or equal to

the join column do:

read the row

if A.join_column = B.join_column then

accept the row and add it to the resulting set

end if

end for

end for

The merge join processing technique has a high overhead if the rows from both tables are unsorted. However, this method is preferable when the values of both join columns are sorted in advance. (This is always the case when both join columns are primary keys of corresponding tables, because the Database Engine creates by default the clustered index for the primary key of a table.)

4.3. Hash Join

The hash join technique is usually used when there are no indices for join columns. In the case of the hash join technique, both tables that have to be joined are considered as two inputs: the build input and the probe input. (The smaller table usually represents the build input.) The process works as follows:

  1. The value of the join column of a row from the build input is stored in a hash bucket depending on the number returned by the hashing algorithm.
  2. Once all rows from the build input are processed, the processing of the rows from the probe input starts.
  3. Each value of the join column of a row from the probe input is processed using the same hashing algorithm.
  4. The corresponding rows in each bucket are retrieved and used to build the result set.

NOTE The hash join technique requires no index. Therefore, this method is highly applicable for ad hoc queries, where indices cannot be expected. Also, if the optimizer uses this processing technique, it could be a hint that you should create additional indices for one or both join columns.

5. Plan Caching

The Database Engine uses a set of memory caches as a storage space for data and for execution plans of queries. The first time such a query is executed, the compiled version of the query is stored in the plan cache (the part of memory used to store compiled query plans). When the same query is executed for the second time, the Database Engine checks whether an existing plan is stored in the plan cache. If so, the plan is used, and the recompilation of the query does not take place.

NOTE The process of plan caching for stored procedures is analogous.

5.1. Influencing Plan Caching

There are several ways in which you can influence plan caching. This section describes two of them:

  • The optimize for ad hoc workloads option

optimize for ad hoc workloads is an advanced configuration option that prevents the system from placing an execution plan in cache on the first execution of the corresponding statement. In other words, the Database Engine places only a stub of the execution plan instead of the entire plan. This stub contains the minimum information necessary for the system to find matches with future queries. The idea behind this is to reduce the uncontrolled growth of the plan cache by storing execution plans only for such queries that are executed more than one time. (Keep in mind that the execution plan for the simple query with a couple of indexed columns in the SELECT list needs about 20KB of memory. The plan cache for complicated queries can be significantly larger.)

DBCC FREEPROCCACHE removes all plans from the plan cache. This command can be useful for testing purposes. In other words, if you want to determine which plans are cached, you can clear the cache using this command. You can also use the command to remove a specific plan from the plan cache by specifying the unique value for its plan handle. (Each query plan stored in the cache is identified by a unique identifier called a plan handle.)

5.2. Displaying Plan Cache Information

To display information concerning the plan cache, you can use the following dynamic management views (functions):

  • dm_exec_cached_plans
  • dm_exec_query_stats
  • dm_exec_sql_text

All these views and functions will be described in the section “Dynamic Management Views and Query Optimizer” later in the chapter.

Source: Petkovic Dusan (2020), Microsoft SQL Server 2019: A Beginner’s Guide, Seventh Edition-McGraw-Hill Education.

Leave a Reply

Your email address will not be published. Required fields are marked *