Chapter 2 - Query Tuning

It may be tempting to address a performance problem solely by system-level server performance tuning, for example, memory size, type of file system, number and type of processors, and so forth. Experience has shown that most performance problems cannot be resolved this way. They must be addressed by analyzing the application, queries, and updates that the application is submitting to the database, and how these queries and updates interact with the database schema.

Unexpectedly long-lasting queries and updates can be caused by:

  • Slow network communication. 

  • Inadequate memory in the server computer, or not enough memory available for Microsoft SQL Server. 

  • Lack of useful statistics. 

  • Out-of-date statistics. 

  • Lack of useful indexes. 

  • Lack of useful data striping. 

When a query or update takes longer than expected, use the following checklist to improve performance.

Note It is recommended that this checklist be consulted prior to contacting your technical support provider.

  1. Is the performance problem related to a component other than queries? For example, is the problem slow network performance? Are there any other components that might be causing or contributing to performance degradation? Windows NT Performance Monitor can be used to monitor the performance of SQL Server and non-SQL Server related components. For more information, see "Monitoring with Windows NT Performance Monitor" in Microsoft SQL Server Administrator's Companion.

  2. If the performance issue is related to queries, which query or set of queries is involved? Use SQL Server Profiler to help identify the slow query or queries. For more information, see "Monitoring with SQL Server Profiler" in Microsoft SQL Server Administrator's Companion.

    The performance of a database query can be determined by using the SET statement to enable the SHOWPLAN, STATISTICS IO, STATISTICS TIME, and STATISTICS PROFILE options.

    • SHOWPLAN describes the method chosen by the SQL Server query optimizer to retrieve data. For more information, see "SET SHOWPLAN_ALL" in Microsoft SQL Server Transact-SQL and Utilities Reference.

    • STATISTICS IO reports information about the number of scans, logical reads (pages accessed in cache), and physical reads (number of times the disk was accessed) for each table referenced in the statement. For more information, see "SET STATISTICS IO" in Microsoft SQL Server Transact-SQL and Utilities Reference.

    • STATISTICS TIME displays the amount of time (in milliseconds) required to parse, compile, and execute a query. For more information, see "SET STATISTICS TIME" in Microsoft SQL Server Transact-SQL and Utilities Reference.

    • STATISTICS PROFILE displays a result set after each executed query representing a profile of the execution of the query. For more information, see "SET STATISTICS PROFILE" in Microsoft SQL Server Transact-SQL and Utilities Reference.

    In SQL Server Query Analyzer, you can also turn on the graphical execution plan option to view a graphical representation of how SQL Server retrieves data. 

    The information gathered by these tools allows you to determine how a query is being executed by the SQL Server query optimizer and which indexes are being used. Using this information, you can determine if performance improvements can be made by rewriting the query, changing the indexes on the tables, or perhaps modifying the database design where possible. For more information, see "Analyzing a Query" in this volume.

  3. Was the query optimized with useful statistics? 

    Statistics regarding the distribution of values in a column are created on indexed columns automatically by SQL Server. They can also be created on nonindexed columns either manually, using SQL Server Query Analyzer or the CREATE STATISTICS statement, or automatically, if the auto create statistics database option is set to true. These statistics can be used by the query processor to determine the optimal strategy for evaluating a query. Maintaining additional statistics on nonindexed columns involved in join operations can improve query performance. For more information, see "Statistical Information" in Microsoft SQL Server Database Developer's Companion.

    Monitor the query using SQL Server Profiler or the graphical execution plan in SQL Server Query Analyzer to determine if the query has enough statistics. For more information, see "Error and Warning Event Category" in Microsoft SQL Server Administrator's Companion.

  4. Are the query statistics up-to-date? Are the statistics automatically updated? 

    SQL Server automatically creates and updates query statistics on indexed columns (as long as automatic query statistic updating is not disabled). Additionally, statistics can be updated on nonindexed columns either manually, using SQL Server Query Analyzer or the UPDATE STATISTICS statement, or automatically, if the auto update statistics database option is set to true. Up-to-date statistics are not dependent upon date or time data. If no UPDATE operations have taken place, then the query statistics are still up-to-date.

    If statistics are not set to update automatically, then set them to do so. For more information, see "Statistical Information" in Microsoft SQL Server Database Developer's Companion.

  5. Are suitable indexes available? Would adding one or more indexes improve query performance? For more information, see "Index Tuning Recommendations" in this volume.

  6. Are there any data or index hot spots? Consider using disk striping. For more information, see "Data Placement Using Filegroups" and "RAID" in this volume.

  7. Is the query optimizer provided with the best opportunity to optimize a complex query? For more information, see "Query Tuning Recommendations" in this volume.

See Also 

In Other Volumes 

"Advanced Query Concepts" in Microsoft SQL Server Database Developer's Companion 

"Monitoring with SQL Server Enterprise Manager" in Microsoft SQL Server Administrator's Companion 

"Parallel Query Processing" in Microsoft SQL Server Introduction 

"Query Processor Architecture" in Microsoft SQL Server Introduction 

"SET" in Microsoft SQL Server Transact-SQL and Utilities Reference 

Analyzing a Query

Microsoft SQL Server offers three ways to present information on how it navigates tables and uses indexes to access the data for a query:

  • Graphically displaying the execution plan using SQL Server Query Analyzer 

    In SQL Server Query Analyzer, click Query and select Display Execution Plan. After executing a query, you can select the Execution Plan tab to see a graphical representation of execution plan output. For more information, see "Graphically Displaying the Execution Plan Using SQL Server Query Analyzer" in this volume.

  • SET SHOWPLAN_TEXT ON

    After this statement is executed, SQL Server returns the execution plan information for each query. For more information, see "SET SHOWPLAN_TEXT" in Microsoft SQL Server Transact-SQL and Utilities Reference.

  • SET SHOWPLAN_ALL ON 

    This statement is similar to SET SHOWPLAN_TEXT, except that the output is in a concise format. For more information, see "SET SHOWPLAN_ALL" in Microsoft SQL Server Transact-SQL and Utilities Reference.

When you display the execution plan, the statements you submit to the server are not executed; instead, SQL Server analyzes the query and displays how the statements would have been executed as a series of operators.

Note Because statements are not executed when the execution plan is displayed, Transact-SQL operations such as creating a table do not cause the table to be created. Therefore, subsequent operations involving the table return errors because the table does not exist.

The best execution plan used by the query engine for individual data manipulation language (DML) and Transact-SQL statements is displayed, and reveals compile-time information about stored procedures, triggers invoked by a batch, and called stored procedures and triggers invoked to an arbitrary number of calling levels. For example, executing a SELECT statement can show that SQL Server uses a table scan to obtain the data. Alternatively, an index scan may have been used instead if the index was determined to be a faster method of retrieving the data from the table.

The results returned by the SHOWPLAN_TEXT and SHOWPLAN_ALL statements are a tabular representation (rows and columns) of a tree structure. The execution plan tree structure uses one row in the result set for each node in the tree, each node representing a logical or physical operator used to manipulate the data to produce expected results. SQL Server Query Analyzer instead graphically displays each logical and physical operator as an icon. For more information, see "Logical and Physical Operators" in this volume.

Graphically Displaying the Execution Plan Using SQL Server Query Analyzer

SQL Server Query Analyzer is an interactive, graphical tool that enables a database administrator or developer to write queries, execute multiple queries simultaneously, view results, analyze the query plan, and receive assistance to improve the query performance. The Execution Plan options graphically display the data retrieval methods chosen by the Microsoft SQL Server query optimizer. The graphical execution plan uses icons to represent the execution of specific statements and queries in SQL Server rather than the tabular representation produced by the SET SHOWPLAN_ALL or SET SHOWPLAN_TEXT statements. This is very useful for understanding the performance characteristics of a query. Additionally, SQL Server Query Analyzer shows suggestions for additional indexes and statistics on nonindexed columns that would improve the query optimizer's ability to process a query efficiently. In particular, SQL Server Query Analyzer shows which statistics are missing, thereby forcing the query optimizer to make estimates about predicate selectivity, and then permits those missing statistics to be easily created.

The following icons displayed in the graphical execution plan represent the physical operators used by SQL Server to execute statements. For more information, see "Logical and Physical Operators" in this volume.

Icon

Physical operator

 

Cc917579.alert(en-us,TechNet.10).gif

Assert

 

Cc917579.splocate(en-us,TechNet.10).gif

Bookmark Lookup

 

Cc917579.spidxdel(en-us,TechNet.10).gif

Clustered Index Delete

 

Cc917579.spinsidx(en-us,TechNet.10).gif

Clustered Index Insert

 

Cc917579.spidxsc(en-us,TechNet.10).gif

Clustered Index Scan

 

Cc917579.spidxsk(en-us,TechNet.10).gif

Clustered Index Seek

 

Cc917579.spidxupd(en-us,TechNet.10).gif

Clustered Index Update

 

Cc917579.spstmagr(en-us,TechNet.10).gif

Collapse

 

Cc917579.spproj(en-us,TechNet.10).gif

Compute Scalar

 

Cc917579.spconcat(en-us,TechNet.10).gif

Concatenation

 

Cc917579.spcnstsc(en-us,TechNet.10).gif

Constant Scan

 

Cc917579.sptsql(en-us,TechNet.10).gif

Deleted Scan

 

Cc917579.spfilter(en-us,TechNet.10).gif

Filter

 

Cc917579.splan_hr(en-us,TechNet.10).gif

Hash Match Root

 

Cc917579.sphashte(en-us,TechNet.10).gif

Hash Match Team

 

Cc917579.spidxdel(en-us,TechNet.10).gif

Index Delete

 

Cc917579.spinsidx(en-us,TechNet.10).gif

Index Insert

 

Cc917579.spidxsc(en-us,TechNet.10).gif

Index Scan

 

Cc917579.spidxsk(en-us,TechNet.10).gif

Index Seek

 

Cc917579.splan_is(en-us,TechNet.10).gif

Index Spool

 

Cc917579.spidxupd(en-us,TechNet.10).gif

Index Update

 

Cc917579.sptsql(en-us,TechNet.10).gif

Inserted Scan

 

Cc917579.logscan(en-us,TechNet.10).gif

Log Row Scan

 

Cc917579.spmrgjn(en-us,TechNet.10).gif

Merge Join

 

Cc917579.spnestlp(en-us,TechNet.10).gif

Nested Loops

 

Cc917579.bmp00001(en-us,TechNet.10).gif

Parallelism

 

Cc917579.paramtab(en-us,TechNet.10).gif

Parameter Table Scan

 

Cc917579.splan_de(en-us,TechNet.10).gif

Remote Delete

 

Cc917579.spremins(en-us,TechNet.10).gif

Remote Insert

 

Cc917579.spremqry(en-us,TechNet.10).gif

Remote Query

 

Cc917579.spremscn(en-us,TechNet.10).gif

Remote Scan

 

Cc917579.splan_r_(en-us,TechNet.10).gif

Remote Update

 

Cc917579.spcnstsc(en-us,TechNet.10).gif

Row Count Spool

 

Cc917579.spconcat(en-us,TechNet.10).gif

Sequence

 

Cc917579.spsorta(en-us,TechNet.10).gif

Sort

 

Cc917579.spstmagr(en-us,TechNet.10).gif

Stream Aggregate

 

Cc917579.splan_ta(en-us,TechNet.10).gif

Table Delete

 

Cc917579.tabl_in(en-us,TechNet.10).gif

Table Insert

 

Cc917579.sptabsc(en-us,TechNet.10).gif

Table Scan

 

Cc917579.spcnstsc(en-us,TechNet.10).gif

Table Spool

 

Cc917579.spupdate(en-us,TechNet.10).gif

Table Update

 

Cc917579.sptop(en-us,TechNet.10).gif

Top

The following icons displayed in the graphical execution plan represent the cursor physical operators used by SQL Server to execute statements.

Icon

Cursor physical operator

 

Cc917579.bitmap1(en-us,TechNet.10).gif

Dynamic

 

Cc917579.cur(en-us,TechNet.10).gif

Fetch Query

 

Cc917579.keyset(en-us,TechNet.10).gif

Keyset

 

Cc917579.pop(en-us,TechNet.10).gif

Population Query

 

Cc917579.cur(en-us,TechNet.10).gif

Refresh Query

 

Cc917579.snapsht(en-us,TechNet.10).gif

Snapshot

Reading the Graphical Execution Plan Output 

The graphical execution plan output in SQL Server Query Analyzer is read from right to left and from top to bottom. Each query in the batch that is analyzed is displayed, including the cost of each query as a percentage of the total cost of the batch.

  • Each node in the tree structure is represented as an icon that specifies the logical and physical operator used to execute part of the query or statement. 

  • Each node is related to a parent node. All nodes with the same parent are drawn in the same column. Rules with arrowheads connect each node to its parent. 

  • Recursive operations are shown with an iteration symbol. 

  • Operators are shown as symbols related to a specific parent. 

  • When the query contains multiple statements, multiple query execution plans are drawn. 

  • The parts of the tree structures are determined by the type of statement executed. 

Type of statement

Tree structure element

Transact-SQL and stored procedures

If the statement is a stored procedure or Transact-SQL statement, it becomes the root of the graphical execution plan tree structure. The stored procedure can have multiple children that represent statements called by the stored procedure. Each child is a node or branch of the tree.

Data manipulation language (DML)

If the statement analyzed by the SQL Server query optimizer is a DML statement, such as SELECT, INSERT, DELETE, or UPDATE, the DML statement is the root of the tree. DML statements can have up to two children. The first child is the execution plan for the DML statement. The second child represents a trigger, if used in or by the statement.

Conditional

The graphical execution plan divides conditional statements such as IF...ELSE statements (if condition exists, then do the following, else do this statement instead) into three children. The IF...ELSE statement is the root of the tree. The if condition becomes a subtree node. The then and else conditions are represented as statement blocks. WHILE and DO-UNTIL statements are represented using a similar plan.

Relational operators

Operations performed by the query engine, such as table scans, joins, and aggregations, are represented as nodes on the tree.

DECLARE CURSOR

The DECLARE CURSOR statement is the root of the graphical execution plan tree, with its related statement as a child or node.

Each node displays ToolTip information when the cursor is pointed at it. The ToolTip information can include:

  • The physical operator (Physical Operation) used, such as Hash Join or Nested Loops. Physical operators displayed in red indicate that the query optimizer has issued a warning, such as missing column statistics or missing join predicates. This can cause the query optimizer to choose a less-efficient query plan than otherwise expected. For more information about column statistics, see "Statistical Information" in Microsoft SQL Server Database Developer's Companion. The graphical execution plan suggests remedial action, such as creating or updating statistics, or creating an index. The missing column statistics and indexes can be immediately created or updated using the context menus of SQL Server Query Analyzer. 

  • The logical operator (Logical Operation) that matches the physical operator, such as the Join operator. The logical operator, if different from the physical operator, is listed after the physical operator at the top of the ToolTip and separated by a forward slash ( / ). 

  • The number of rows (Row Count) output by the operator. 

  • The estimated size of the row (Estimated Row Size) output by the operator. 

  • The estimated cost (I/O Cost) of all I/O activity for the operation. This value should be as low as possible. 

  • The estimated cost for all CPU activity (CPU Cost) for the operation. 

  • The number of times the operation was executed (Number of executes) during the query. 

  • The cost to the query optimizer (Cost) in executing this operation, including cost of this operation as a percentage of the total cost of the query. Because the query engine selects the most efficient operation to perform the query or execute the statement, this value should be as low as possible. 

  • The total cost to the query optimizer (Subtree cost) in executing this operation and all operations preceding it in the same subtree. 

  • The predicates and parameters (Argument) used by the query. 

See Also 

In Other Volumes 

"SET SHOWPLAN_ALL" in Microsoft SQL Server Transact-SQL and Utilities Reference 

"SET SHOWPLAN_TEXT" in Microsoft SQL Server Transact-SQL and Utilities Reference 

Logical and Physical Operators

The logical and physical operators describe how a query or update was executed. The physical operators describe the physical implementation algorithm used to process a statement, for example, scanning a clustered index. Each step in the execution of a query or update statement involves a physical operator. The logical operators describe the relational algebraic operation used to process a statement, for example, performing an aggregation. Not all steps used to process a query or update involve logical operations.

Assert

The Assert logical and physical operator verifies a condition. For example, it validates referential integrity or check constraints, or ensures that a scalar subquery returns one row. For each input row, the Assert operator evaluates the expression in the Argument column. If this expression evaluates to NULL, the row is passed through the Assert operator. If this expression evaluates to a nonnull value, the appropriate error will be raised.

Aggregate

The Aggregate logical operator groups the input by a set of columns and calculates aggregate expressions (MIN, MAX, SUM, and so on).

See Also 

In Other Volumes 

"Aggregate Functions" in Microsoft SQL Server Transact-SQL and Utilities Reference 

Bookmark Lookup

The Bookmark Lookup logical and physical operator uses a bookmark (row ID or clustering key) to look up the corresponding row in the table or clustered index. The Argument column contains the bookmark label used to look up the row in the table or clustered index. The Argument column also contains the name of the table or clustered index in which the row is looked up. If the WITH PREFETCH clause appears in the Argument column, then the query processor has determined that it is optimal to use asynchronous prefetching (read-ahead) when looking up bookmarks in the table or clustered index.

Clustered Index Delete

The Clustered Index Delete physical operator deletes rows from the clustered index specified in the Argument column. If a WHERE:() predicate is present in the Argument column, then only those rows that satisfy the predicate are deleted.

See Also 

In Other Volumes 

"Using Clustered Indexes" in Microsoft SQL Server Database Developer's Companion 

Clustered Index Insert

The Clustered Index Insert physical operator inserts rows from its input into the clustered index specified in the Argument column. The Argument column will also contain a SET:() predicate, which indicates the value to which each column is set.

See Also 

In Other Volumes 

"Using Clustered Indexes" in Microsoft SQL Server Database Developer's Companion 

Clustered Index Update

The Clustered Index Update physical operator updates input rows in the clustered index specified in the Argument column.

If a WHERE:() predicate is present, only those rows that satisfy this predicate are updated. If a SET:() predicate is present, it indicates the value to which each updated column is set. If a DEFINE:() predicate is present, this lists the values that this operator defines. These values may be referenced in the SET clause or elsewhere within this operator and elsewhere within this query.

See Also 

In Other Volumes 

"Using Clustered Indexes" in Microsoft SQL Server Database Developer's Companion 

Clustered Index Scan

The Clustered Index Scan logical and physical operator scans the clustered index specified in the Argument column. When an optional WHERE:() predicate is present, only those rows that satisfy the predicate are returned. If the Argument column contains the ORDERED clause, the query processor has requested that the rows' output be returned in the order in which the clustered index has sorted them. If the ORDERED clause is not present, the storage engine will scan the index in the optimal way (not guaranteeing the output to be sorted).

See Also 

In Other Volumes 

"Using Clustered Indexes" in Microsoft SQL Server Database Developer's Companion 

Clustered Index Seek

The Clustered Index Seek logical and physical operator uses the seeking ability of indexes to retrieve rows from a clustered index.

The Argument column contains the name of the clustered index being used and the SEEK:() predicate. The storage engine uses the index to process only those rows that satisfy this SEEK:() predicate. It optionally can include a WHERE:() predicate, which the storage engine evaluates against all rows satisfying the SEEK:() predicate (it does not use indexes to do this).

If the Argument column contains the ORDERED clause, the query processor has determined that the rows must be returned in the order in which the clustered index has sorted them. If the ORDERED clause is not present, the storage engine searches the index in the optimal way (not guaranteeing the output to be sorted). Allowing the output to retain its ordering can be less efficient than producing nonsorted output.

See Also 

In Other Volumes 

"Using Clustered Indexes" in Microsoft SQL Server Database Developer's Companion 

Collapse

The Collapse logical and physical operator optimizes update processing. When an update is performed, it can be split (using the Split operator) into a delete and an insert. If the Argument column contains a GROUP BY:() predicate and a list of key columns being grouped, the query processor groups by the set of key columns to optimize these update operations by removing any temporary, unneeded intermediate changes to each row.

See Also 

In This Volume 

Split

Compute Scalar

The Compute Scalar logical and physical operator evaluates an expression to produce a computed scalar value, which may be returned to the user and/or referenced elsewhere in the query, for example, in a filter predicate or join predicate.

See Also 

In Other Volumes 

"Functions" in Microsoft SQL Server Transact-SQL and Utilities Reference 

Concatenation

The Concatenation logical and physical operator scans multiple inputs, returning each row scanned.

Constant Scan

The Constant Scan logical and physical operator introduces a constant row into a query. It will return either zero or one row, which usually contains no columns. A Compute Scalar operator is often used to add columns to the row produced by a Constant Scan.

See Also 

In This Volume 

Compute Scalar

Cross Join

The Cross Join logical operator joins each row from the first (top) input with each row from the second (bottom) input.

See Also 

In Other Volumes 

"Using Cross Joins" in Microsoft SQL Server Database Developer's Companion 

Delete

The Delete logical operator deletes from an object rows that satisfy the optional predicate in the Argument column.

See Also 

In Other Volumes 

"DELETE" in Microsoft SQL Server Transact-SQL and Utilities Reference 

Deleted Scan

The Deleted Scan logical and physical operator scans the deleted table within a trigger.

See Also 

In Other Volumes 

"Using the Special Inserted and Deleted Tables" in Microsoft SQL Server Database Developer's Companion 

Distinct

The Distinct logical operator scans the input, removing duplicates.

See Also 

In Other Volumes 

"Eliminating Duplicates with DISTINCT" in Microsoft SQL Server Database Developer's Companion 

Distinct Sort

The Distinct Sort logical operator scans the input, removing duplicates and sorting by the columns specified in the DISTINCT ORDER BY:() predicate of the Argument column.

See Also 

In This Volume 

Distinct

In Other Volumes 

"Eliminating Duplicates with DISTINCT" in Microsoft SQL Server Database Developer's Companion 

Distribute Streams

The Distribute Streams logical operator is used only in parallel query plans. The Distribute Streams operator consumes a single input stream of records and produces multiple output streams. The record contents and format are not changed. Each record from the input stream appears in one of the output streams. This operator automatically preserves the relative order of the input records in the output streams. Usually, hashing is used to decide to which output stream a particular input record belongs.

If the output is partitioned, then the Argument column contains a PARTITION COLUMNS:() predicate and the partitioning columns.

See Also 

In This Volume 

Gather Streams

Parallelism

Repartition Streams

In Other Volumes 

"Parallel Query Processing" in Microsoft SQL Server Introduction 

Eager Spool

The Eager Spool logical operator will consume the entire input, storing each row in a hidden temporary object stored in the tempdb database. If the operator is rewound (for example, by a Nested Loops operator) but no rebinding is needed, the spooled data is used instead of rescanning the input. If rebinding is needed, the spooled data is discarded and the spool object is rebuilt by rescanning the (rebound) input.

The Eager Spool operator will build its spool file eagerly. When the spool's parent operator asks for the first row, the spool operator will consume all rows from its input operator and store them in the spool.

Note An alternative way of building a spool file is with the Lazy Spool operator.

Filter

The Filter logical and physical operator scans the input, returning only those rows that satisfy the filter expression (predicate) that appears in the Argument column.

Flow Distinct

The Flow Distinct logical operator scans the input, removing duplicates. Whereas the Distinct operator consumes all input before producing any output, the Flow Distinct operator returns each row as it is obtained from the input (unless that row is a duplicate, in which case it is discarded).

See Also 

In This Volume 

Distinct

In Other Volumes 

"Eliminating Duplicates with DISTINCT" in Microsoft SQL Server Database Developer's Companion 

Full Outer Join

The Full Outer Join logical operator returns each row satisfying the join predicate from the first (top) input joined with each row from the second (bottom) input. It also returns rows from:

  • The first input that had no matches in the second input. 

  • The second input that had no matches in the first input. 

The input that does not contain the matching values is returned as a null value.

See Also 

In Other Volumes 

"Using Outer Joins" in Microsoft SQL Server Database Developer's Companion 

Gather Streams

The Gather Streams logical operator is only used in parallel query plans. The Gather Streams operator consumes several input streams and produces a single output stream of records by combining the input streams. The record contents and format are not changed. If this operator is order-preserving, then all input streams must be ordered.

If the output is ordered, then the Argument column contains an ORDER BY:() predicate and the names of columns being ordered.

See Also 

In This Volume 

Distribute Streams

Parallelism

Repartition Streams

In Other Volumes 

"Parallel Query Processing" in Microsoft SQL Server Introduction 

Hash Match

The Hash Match physical operator builds a hash table by computing a hash value for each row from its build input. A HASH:() predicate with a list of columns used to create a hash value appears in the Argument column. Then, for each probe row (as applicable), it computes a hash value (using the same hash function) and looks in the hash table for matches. If a residual predicate is present (identified by RESIDUAL:() in the Argument column), that predicate must also be satisfied for rows to be considered a match. Behavior is slightly different based on the logical operation being performed:

  • For any joins, use the first (top) input to build the hash table and the second (bottom) input to probe the hash table. Output matches (or nonmatches) as dictated by the join type. If multiple joins use the same join column, these operations are grouped into a hash team. 

  • For the distinct or aggregate operators, use the input to build the hash table (removing duplicates and computing any aggregate expressions). When the hash table is built, scan the table and output all entries. 

  • For the union operator, use the first input to build the hash table (removing duplicates). Use the second input (which must have no duplicates) to probe the hash table, returning all rows that have no matches, then scan the hash table and return all entries. 

See Also 

In This Volume 

Distinct

Hash Match Team

Understanding Hash Joins

Union

Hash Match Root

The Hash Match Root physical operator coordinates the operation of all Hash Match Team operators directly below it. The Hash Match Root operator and all Hash Match Team operators directly below it share a common hash function and partitioning strategy. The Hash Match Root operator always returns output to an operator that is not a member of its team.

See Also 

In This Volume 

Hash Match Team

Understanding Hash Joins

Hash Match Team

The Hash Match Team physical operator is part of a team of connected hash operators sharing a common hash function and partitioning strategy.

See Also 

In This Volume 

Hash Match Root

Index Delete

The Index Delete physical operator will delete input rows from the nonclustered index specified in the Argument column. If a WHERE:() predicate is present, only those rows that satisfy this predicate will be deleted.

See Also 

In Other Volumes 

"DELETE" in Microsoft SQL Server Transact-SQL and Utilities Reference 

"Using Nonclustered Indexes" in Microsoft SQL Server Database Developer's Companion 

Index Insert

The Index Insert physical operator inserts rows from its input into the nonclustered index specified in the Argument column. The Argument column will also contain a SET:() predicate, which indicates the value to which each column is set.

See Also 

In Other Volumes 

"INSERT" in Microsoft SQL Server Transact-SQL and Utilities Reference 

"Using Nonclustered Indexes" in Microsoft SQL Server Database Developer's Companion 

Index Scan

The Index Scan logical and physical operator retrieves all rows from the nonclustered index specified in the Argument column. If an optional WHERE:() predicate appears in the Argument column, only those rows that satisfy the predicate are returned.

If the Argument column must contain the ORDERED clause, the query processor has determined that the rows be returned in the order in which the nonclustered index has sorted them. If the ORDERED clause is not present, the storage engine will search the index in the optimal way (which does not guarantee that the output will be sorted).

See Also 

In Other Volumes 

"SELECT" in Microsoft SQL Server Transact-SQL and Utilities Reference 

"Using Nonclustered Indexes" in Microsoft SQL Server Database Developer's Companion 

Index Seek

The Index Seek logical and physical operator uses the seeking ability of indexes to retrieve rows from a nonclustered index.

The Argument column contains the name of the nonclustered index being used. It also contains the SEEK:() predicate. The storage engine uses the index to process only those rows that satisfy the SEEK:() predicate. It optionally may include a WHERE:() predicate, which the storage engine will evaluate against all rows that satisfy the SEEK:() predicate (it does not use the indexes to do this).

If the Argument column contains the ORDERED clause, the query processor has determined that the rows must be returned in the order in which the nonclustered index has sorted them. If the ORDERED clause is not present, the storage engine searches the index in the optimal way (which does not guarantee that the output will be sorted). Allowing the output to retain its ordering may be less efficient than producing nonsorted output.

See Also 

In Other Volumes 

"SELECT" in Microsoft SQL Server Transact-SQL and Utilities Reference 

"Using Nonclustered Indexes" in Microsoft SQL Server Database Developer's Companion 

Index Spool

The Index Spool physical operator contains a SEEK:() predicate in the Argument column. The Index Spool operator scans its input rows, placing a copy of each row in a hidden spool file (stored in the tempdb database and existing only for the lifetime of the query), and builds an index on the rows. This allows you to use the seeking capability of indexes to output only those rows that satisfy the SEEK:() predicate.

If the operator is rewound (for example, by a Nested Loops operator) but no rebinding is needed, the spooled data is used instead of rescanning the input.

See Also 

In Other Volumes 

"Creating an Index" in Microsoft SQL Server Database Developer's Companion 

Index Update

The Index Update physical operator updates rows from its input in the nonclustered index specified in the Argument column.

If a WHERE:() predicate is present, only those rows that satisfy this predicate are updated. If a SET:() predicate is present, it indicates the value to which each updated column is set. If a DEFINE:() predicate is present, it lists the values that this operator defines. These values may be referenced in the SET clause, or elsewhere within this operator and elsewhere within this query.

See Also 

In Other Volumes 

"UPDATE" in Microsoft SQL Server Transact-SQL and Utilities Reference 

"Using Nonclustered Indexes" in Microsoft SQL Server Database Developer's Companion 

Inner Join

The Inner Join logical operator returns each row that satisfies the join of the first (top) input with the second (bottom) input.

See Also 

In Other Volumes 

"Using Inner Joins" in Microsoft SQL Server Database Developer's Companion 

Insert

The Insert logical operator inserts each row from its input into the object specified in the Argument column. The physical operator will be either the Table Insert, Index Insert, or Clustered Index Insert operator.

See Also 

In This Volume 

Clustered Index Insert

Index Insert

Table Insert

Inserted Scan

The Inserted Scan logical and physical operator scans the inserted table within a trigger.

See Also 

In Other Volumes 

"Using the Special Inserted and Deleted Tables" in Microsoft SQL Server Database Developer's Companion 

Lazy Spool

The Lazy Spool logical operator stores each row from its input in a hidden temporary object stored in the tempdb database. If the operator is rewound (for example, by a Nested Loops operator) but no rebinding is needed, the spooled data is used instead of rescanning the input. If rebinding is needed, the spooled data is discarded and the spool object is rebuilt by rescanning the (rebound) input.

The Lazy Spool operator will build its spool file in a lazy (noneager) manner. Each time the spool's parent operator asks for a row, the spool operator gets a row from its input operator and stores it in the spool.

See Also 

In This Volume 

Eager Spool

Left Anti Semi Join

The Left Anti Semi Join logical operator returns each row from the first (top) input when there is no matching row in the second (bottom) input. If no join predicate exists in the Argument column, each row is a matching row.

See Also 

In Other Volumes 

"Using Joins" in Microsoft SQL Server Database Developer's Companion 

Left Outer Join

The Left Outer Join logical operator returns each row that satisfies the join of the first (top) input with the second (bottom) input. It also returns any rows from the first input that had no matching rows in the second input. The nonmatching rows in the second input are returned as null values. If no join predicate exists in the Argument column, each row is a matching row.

See Also 

In Other Volumes 

"Using Outer Joins" in Microsoft SQL Server Database Developer's Companion 

Left Semi Join

The Left Semi Join logical operator returns each row from the first (top) input when there is a matching row in the second (bottom) input. If no join predicate exists in the Argument column, each row is a matching row.

See Also 

In Other Volumes 

"Using Joins" in Microsoft SQL Server Database Developer's Companion 

Log Row Scan

The Log Row Scan logical and physical operator scans the transaction log.

See Also 

In Other Volumes 

"Transaction Logs" in Microsoft SQL Server Database Developer's Companion 

Merge Interval

The Merge Interval logical and physical operator merges multiple (potentially overlapping) intervals to produce minimal, nonoverlapping intervals that are then used to seek index entries. This operator typically appears above one or more Compute Scalar operators over Constant Scan operators, which construct the intervals (represented as columns in a row) that this operator merges.

See Also 

In This Volume 

Compute Scalar

Constant Scan

Understanding Hash Joins

Merge Join

The Merge Join physical operator performs the Inner Join, Left Outer Join, Left Semi Join, Left Anti Semi Join, Right Outer Join, Right Semi Join, Right Anti Semi Join, and Union logical operations.

In the Argument column, the Merge Join operator contains a MERGE:() predicate if the operation is performing a one-to-many join, or a MANY-TO-MANY MERGE:() predicate if the operation is performing a many-to-many join. The Argument column also includes a comma-separated list of columns used to

perform the operation. The Merge Join operator requires two inputs sorted on their respective columns, possibly by inserting explicit sort operations into the query plan. Merge join is particularly effective if explicit sorting is not required, for example, if there is a suitable B-tree index in the database or if the sort order can be exploited for multiple operations, such as a merge join and grouping with roll up.

See Also 

In This Volume 

Understanding Merge Joins

Nested Loops

The Nested Loops physical operator performs the Inner Join, Left Outer Join, Left Semi Join, and Left Anti Semi Join logical operations.

Nested loops joins perform a search on the inner table for each row of the outer table, typically using an index. Microsoft SQL Server decides, based on anticipated costs, whether to sort the outer input in order to improve locality of the searches on the index over the inner input.

Any rows that satisfy the (optional) predicate in the Argument column are returned (as applicable based on the logical operation being performed).

See Also 

In This Volume 

Understanding Nested Loops Joins

Parallelism

The Parallelism physical operator performs the Distribute Streams, Gather Streams, and Repartition Streams logical operations. The Argument columns can contain a PARTITION COLUMNS:() predicate with a comma-separated list of the columns being partitioned. The Argument columns can also contain an ORDER BY:() predicate with a list of the columns for which the sort order is preserved during partitioning.

See Also 

In This Volume 

Distribute Streams

Gather Streams

Repartition Streams

Parameter Table Scan

The Parameter Table Scan logical and physical operator scans a table that is acting as a parameter in the current query. Typically, this is used for INSERT queries within a stored procedure.

See Also 

In Other Volumes 

"INSERT" in Microsoft SQL Server Transact-SQL and Utilities Reference 

Remote Delete

The Remote Delete logical and physical operator deletes the input rows from a remote object.

Remote Insert

The Remote Insert logical and physical operator inserts the input rows into a remote object.

Remote Query

The Remote Query logical and physical operator submits a query to a remote source. The text of the query sent to the remote server appears in the Argument column.

See Also 

In This Volume 

Optimizing Distributed Queries

Remote Scan

The Remote Scan logical and physical operator will scan a remote object. The name of the remote object appears in the Argument column.

Remote Update

The Remote Update logical and physical operator updates the input rows in a remote object.

Repartition Streams

The Repartition Streams logical operator is used only in parallel query plans. The Repartition Streams operator consumes multiple streams and produces multiple streams of records. The record contents and format are not changed. Each record from an input stream is placed into one output stream. If this operator is order-preserving, then all input streams must be ordered and merged into several ordered output streams.

If the output is partitioned, then the Argument column contains a PARTITION COLUMNS:() predicate and the partitioning columns.

If the output is ordered, then the Argument column contains an ORDER BY:() predicate and the columns being ordered.

See Also 

In This Volume 

Distribute Streams

Gather Streams

In Other Volumes 

"Parallel Query Processing" in Microsoft SQL Server Introduction 

Right Anti Semi Join

The Right Anti Semi Join logical operator will output each row from the second (bottom) input when a matching row in the first (top) input does not exist. A matching row is defined as a row that satisfies the predicate in the Argument column (if no predicate exists, each row is a matching row).

See Also 

In Other Volumes 

"Using Joins" in Microsoft SQL Server Database Developer's Companion 

Right Outer Join

The Right Outer Join logical operator returns each row that satisfies the join of the second (bottom) input with each matching row from the first (top) input. It will also return any rows from the second input that had no matching rows in the first input, joined with NULL. If no join predicate exists in the Argument column, each row is a matching row.

See Also 

In Other Volumes 

"Using Outer Joins" in Microsoft SQL Server Database Developer's Companion 

Right Semi Join

The Right Semi Join logical operator returns each row from the second (bottom) input when there is a matching row in the first (top) input. If no join predicate exists in the Argument column, each row is a matching row.

See Also 

In Other Volumes 

"Using Joins" in Microsoft SQL Server Database Developer's Companion 

Row Count Spool

The Row Count Spool physical operator scans the input, counting how many rows are present and returning that many rows without any data in them. This operator is used when it is important to check for the existence of rows rather than the data contained in the rows. For example, if a Nested Loops operator performs a left semi join operation and the join predicate applies to inner input, a row count spool may be placed at the top of the Nested Loops operator's inner input. Then the Nested Loops operator can look at how many rows are output by the row count spool (since the actual data from the inner side is not needed) to determine whether to return the outer row.

See Also 

In This Volume 

Left Semi Join

Nested Loops

Sequence

The Sequence logical and physical operator drives wide update plans. Functionally, it executes each input in sequence (top to bottom). Each input is usually an update of a different object. It returns only those rows that come from its last (bottom) input.

Sort

The Sort logical and physical operator sorts all incoming rows. The Argument column contains a DISTINCT ORDER BY:() predicate if duplicates are removed by this operation or an ORDER BY:() predicate with a comma-separated list of the columns being sorted. The columns are prefixed with the value ASC if the columns are sorted in ascending order, or the value DESC if the columns are sorted in descending order.

See Also 

In Other Volumes 

"SELECT" in Microsoft SQL Server Transact-SQL and Utilities Reference 

Split

The Split logical and physical operator is used to optimize update processing. It splits each update operation into a delete and an insert operation.

See Also 

In This Volume 

Collapse

Stream Aggregate

The Stream Aggregate physical operator optionally groups by a set of columns and calculates one or more aggregate expressions returned by the query and/or referenced elsewhere within the query. This operator requires that the input be ordered by the columns by which it groups.

If the Stream Aggregate operator groups by columns, a GROUP BY:() predicate and the list of columns appear in the Argument column. If the Stream Aggregate operator computes any aggregate expressions, a list of them will appear in the Defined Values column of the output from the SHOWPLAN_ALL statement or the Argument column of the graphical execution plan.

See Also 

In Other Volumes 

"Aggregate Functions" in Microsoft SQL Server Transact-SQL and Utilities Reference 

Table Delete

The Table Delete physical operator deletes rows from the table specified in the argument column. If a WHERE:() predicate is present in the Argument column, only those rows that satisfy the predicate will be deleted.

See Also 

In Other Volumes 

"DELETE" in Microsoft SQL Server Transact-SQL and Utilities Reference 

Table Insert

The Table Insert physical operator inserts rows from its input into the table specified in the Argument column. The Argument column also contains a SET:() predicate, which indicates the value to which each column is set.

See Also 

In Other Volumes 

"INSERT" in Microsoft SQL Server Transact-SQL and Utilities Reference 

Table Scan

The Table Scan logical and physical operator retrieves all rows from the table specified in the Argument column. If a WHERE:() predicate appears in the Argument column, only those rows that satisfy the predicate are returned.

See Also 

In Other Volumes 

"SELECT" in Microsoft SQL Server Transact-SQL and Utilities Reference 

Table Spool

The Table Spool physical operator scans the input and places a copy of each row in a hidden spool table (stored in the tempdb database and existing only for the lifetime of the query). If the operator is rewound (for example, by a Nested Loops operator) but no rebinding is needed, the spooled data is used instead of rescanning the input.

Table Update

The Table Update physical operator updates input rows in the table specified in the Argument column. If a WHERE:() predicate is present, only those rows that satisfy this predicate are updated. If a SET:() predicate is present, it indicates the value to which each updated column is set. If a DEFINE:() predicate is present, this lists the values that this operator defines. These values may be referenced in the SET clause or elsewhere within this operator and elsewhere within this query.

See Also 

In Other Volumes 

"UPDATE" in Microsoft SQL Server Transact-SQL and Utilities Reference 

Top

The Top logical and physical operator will scan the input, returning only the first specified number or percent of rows. The Argument column can optionally contain a list of the columns that are being checked for ties. In update plans, the Top operator is used to enforce row count limits.

See Also 

In Other Volumes 

"Limiting Result Sets Using TOP and PERCENT" in Microsoft SQL Server Database Developer's Companion 

"SET ROWCOUNT" in Microsoft SQL Server Transact-SQL and Utilities Reference 

Union

The Union logical operator scans multiple inputs, outputting each row scanned and removing duplicates.

See Also 

In Other Volumes 

"UNION" in Microsoft SQL Server Transact-SQL and Utilities Reference 

Update

The Update logical operator updates each row from its input in the object specified in the Argument column. The physical operator is Table Update, Index Update, or Clustered Index Update.

See Also 

In Other Volumes 

"UPDATE" in Microsoft SQL Server Transact-SQL and Utilities Reference 

Cursor Logical and Physical Operators

The Cursor logical and physical operators are used to describe how a query or update involving cursor operations are executed. The physical operators describe the physical implementation algorithm used to process the cursor, for example, using a keyset-driven cursor. Each step in the execution of a cursor involves a physical operator. The logical operators describe a property of the cursor, such as the cursor is read only.

Logical Operators 

The Cursor logical operators include:

Asynchronous

The cursor table is populated asynchronously. For more information, see "Asynchronous Population" in Microsoft SQL Server Database Developer's Companion.

Optimistic

This cursor uses the optimistic mode of concurrency. For more information, see "Cursor Concurrency" in Microsoft SQL Server Database Developer's Companion.

Primary

This is the primary fetch query for this cursor.

Read Only

This cursor uses read-only semantics for concurrency. This cursor can only read data, not insert, update, or delete it. For more information, see "Cursor Concurrency" in Microsoft SQL Server Database Developer's Companion.

Scroll Locks

This cursor uses scroll locks for concurrency. For more information, see "Cursor Concurrency" in Microsoft SQL Server Database Developer's Companion.

Secondary

This is the secondary fetch query (used if the primary fetch query fails).

Synchronous

The cursor table is populated synchronously.

Physical Operators 

The Cursor physical operators include:

Dynamic

This cursor can see all changes made by others. For more information, see "Dynamic Cursors" in Microsoft SQL Server Database Developer's Companion.

Fetch Query

This query retrieves rows when a fetch is issued against a cursor.

Keyset

This cursor can see updates made by others, but not inserts. For more information, see "Keyset-driven Cursors" in Microsoft SQL Server Database Developer's Companion.

Population Query

This query populates a cursor's work table when the cursor is opened.

Refresh Query

This query fetches current data for rows in the cursor fetch buffer.

Snapshot

This cursor does not see changes made by others. For more information, see "Static Cursors" in Microsoft SQL Server Database Developer's Companion.

See Also 

In Other Volumes 

"Cursors" in Microsoft SQL Server Database Developer's Companion 

Query Tuning Recommendations

Some queries are inherently resource intensive. This is related to fundamental database and index issues. These queries are not inefficient, because the query optimizer will implement the queries in the most efficient fashion possible. However, they are resource intensive, and the set-oriented nature of Transact-SQL can make them appear inefficient. No degree of query optimizer intelligence can eliminate the inherent resource cost of these constructs. They are intrinsically costly when compared to a less complex query. Although Microsoft SQL Server will use the most optimal access plan, this is limited by what is fundamentally possible. For example, the following types of queries can be resource intensive:

  • Queries returning large result sets 

  • Highly nonunique WHERE clauses 

However, recommendations for tuning queries and improving query performance include:

  • Add more memory (especially if the server runs many complex queries and several of the queries execute slowly). 

  • Run SQL Server on a computer with more than one processor. Multiple processors allow SQL Server to make use of parallel queries. For more information, see "Parallel Query Processing" in Microsoft SQL Server Introduction. 

    Consider rewriting the query.

    • If the query uses cursors, determine if the cursor query could be written more efficiently using either a more efficient cursor type, such as fast forward-only, or a single query. Single queries typically outperform cursor operations. Because a set of cursor statements is typically an outer loop operation, in which each row in the outer loop is processed once using an inner statement, consider using either a GROUP BY or CASE statement or a subquery instead. 

    • If an application uses a loop, consider putting the loop inside the query. Often an application will contain a loop that contains a parameterized query, which is executed many times and requires a network round trip between the computer running the application and SQL Server. Instead, create a single, more complex query using a temporary table. Only one network round trip is necessary, and the query optimizer can better optimize the single query. 

    • Do not use multiple aliases for a single table in the same query to simulate index intersection. This is no longer necessary because SQL Server automatically considers index intersection and can make use of multiple indexes on the same table in the same query. For example, given the sample query: 


      SELECT * FROM lineitem 
      WHERE partkey BETWEEN 17000 AND 17100 AND
      shipdate BETWEEN '1/1/1994' AND '1/31/1994"
      

      SQL Server can exploit indexes on both the partkey and shipdate columns, and then perform a hash match between the two subsets to obtain the index intersection. 

    • Make use of query hints only if necessary. Queries using hints executed against earlier versions of SQL Server should be tested without the hints specified. The hints can prevent the query optimizer from choosing a better execution plan. For more information, see "SELECT" in Microsoft SQL Server Transact-SQL and Utilities Reference.

  • Make use of the query governor configuration option and setting. The query governor configuration option can be used to prevent long-running queries from executing, thus preventing system resources from being consumed. By default, the query governor configuration option allows all queries to execute, no matter how long they take. However, the query governor can be set to the maximum number of seconds that all queries for all connections, or just the queries for a specific connection, are allowed to execute. Because the query governor is based on estimated query cost, rather than actual elapsed time, it does not have any run-time overhead. It also stops long-running queries before they start, rather than running them until some predefined limit is hit. For more information, see "query governor cost limit Option" in Microsoft SQL Server Administrator's Companion and "SET QUERY_GOVERNOR_COST_LIMIT" in Microsoft SQL Server Transact-SQL and Utilities Reference.

See Also 

In Other Volumes 

"CASE" in Microsoft SQL Server Transact-SQL and Utilities Reference 

"GROUP BY Fundamentals" in Microsoft SQL Server Database Developer's Companion 

"Subquery Fundamentals" in Microsoft SQL Server Database Developer's Companion 

Advanced Query Tuning Concepts

Microsoft SQL Server performs sort, intersect, union, and difference operations using in-memory sorting and hash join technology. Using this type of query plan, SQL Server supports vertical table partitioning, sometimes called columnar storage.

SQL Server employs three types of join operations:

  • Nested loops joins 

  • Merge joins 

  • Hash joins 

If one join input is quite small (such as fewer than 10 rows) and the other join input is fairly large and indexed on its join columns, index nested loops are the fastest join operation because they require the least I/O and the fewest comparisons. For more information about nested loops, see "Understanding Nested Loops" in this volume.

If the two join inputs are not small but are sorted on their join column (for example, if they were obtained by scanning sorted indexes), merge join is the fastest join operation. If both join inputs are large and the two inputs are of similar sizes, merge join with prior sorting and hash join offer similar performance. However, hash join operations are often much faster if the two input sizes differ significantly from each other. For more information, see "Understanding Merge Joins" in this volume.

Hash joins can process large, unsorted, nonindexed inputs efficiently. They are useful for intermediate results in complex queries because:

  • Intermediate results are not indexed (unless explicitly saved to disk and then indexed) and often are not produced suitably sorted for the next operation in the query plan. 

  • Query optimizers estimate only intermediate result sizes. Because estimates can be an order of magnitude wrong in complex queries, algorithms to process intermediate results not only must be efficient but also must degrade gracefully if an intermediate result turns out to be much larger than anticipated. 

The hash join allows reductions in the use of denormalization to occur. Denormalization is typically used to achieve better performance by reducing join operations, in spite of the dangers of redundancy, such as inconsistent updates. Hash joins reduce the need to denormalize. Hash joins allow vertical partitioning (representing groups of columns from a single table in separate files or indexes) to become a viable option for physical database design. For more information, see "Understanding Hash Joins" in this volume.

Understanding Nested Loops Joins

The nested loops join, also called nested iteration, uses one join input as the outer input table (shown as the top input in the graphical execution plan) and one as the inner (bottom) input table. The outer loop consumes the outer input table row by row. The inner loop, executed for each outer row, searches for matching rows in the inner input table. In the simplest case, the search scans an entire table or index; this is called a naive nested loops join. If the search exploits an index, it is called an index nested loops join. If the index is built as part of the query plan (and destroyed upon completion of the query), it is called a temporary index nested loops join. All these variants are considered by the query optimizer. A nested loops join is particularly effective if the outer input is quite small and the inner input is preindexed and quite large. In many small transactions, such as those affecting only a small set of rows, index nested loops joins are far superior to both merge joins and hash joins. In large queries, however, nested loops joins are often not the optimal choice.

Understanding Merge Joins

The merge join requires that both inputs be sorted on the merge columns, which are defined by the equality (WHERE) clauses of the join predicate. The query optimizer typically scans an index, if one exists on the proper set of columns, or places a sort operator below the merge join. In rare cases, there may be multiple equality clauses, but the merge columns are taken from only some of the available equality clauses.

Since each input is sorted, the Merge Join operator will get a row from each input and compare them. For example, for inner join operations, the rows are returned if they are equal. If they are not equal, whichever row has the lower value is discarded and another row is obtained from that input. This process repeats until all rows have been processed.

The merge join operation may be either a regular or a many-to-many operation. A many-to-many merge join uses a temporary table to store rows. If there are duplicate values from each input, one of the inputs will have to rewind to the start of the duplicates as each duplicate from the other input is processed.

If a residual predicate is present, all rows that satisfy the merge predicate will evaluate the residual predicate, and only those rows that satisfy it will be returned.

Merge join itself is very fast, but it can be an expensive choice if sort operations are required. However, if the data volume is large and the desired data can be obtained presorted from existing B-tree indexes, merge join is often the fastest available join algorithm.

Understanding Hash Joins

The hash join has two inputs: the build input and probe input. The query optimizer assigns these roles so that the smaller of the two inputs is the build input.

Hash joins are used for many types of set-matching operations: inner join; left, right, and full outer join; left and right semi-join; intersection; union; and difference. Moreover, a variant of the hash join can do duplicate removal and grouping (such as SUM(salary) GROUP BY department). These modifications use only one input for both the build and probe roles.

Similar to a merge join, a hash join can be used only if there is at least one equality (WHERE) clause in the join predicate. However, because joins are typically used to reassemble relationships, expressed with an equality predicate between a primary key and a foreign key, most joins have at least one equality clause. The set of columns in the equality predicate is called the hash key, because these are the columns that contribute to the hash function. Additional predicates are possible and are evaluated as residual predicates separate from the comparison of hash values. The hash key can be an expression, as long as it can be computed exclusively from columns in a single row. In grouping operations, the columns of the group by list are the hash key. In set operations such as intersection, as well as in the removal of duplicates, the hash key consists of all columns.

In-memory Hash Join 

The hash join first scans or computes the entire build input and then builds a hash table in memory. Each row is inserted into a hash bucket depending on the hash value computed for the hash key. If the entire build input is smaller than the available memory, all rows can be inserted into the hash table. This build phase is followed by the probe phase. The entire probe input is scanned or computed one row at a time, and for each probe row, the hash key's value is computed, the corresponding hash bucket is scanned, and the matches are produced.

Grace Hash Join 

If the build input does not fit in memory, a hash join proceeds in several steps. Each step has a build phase and probe phase. Initially, the entire build and probe inputs are consumed and partitioned (using a hash function on the hash keys) into multiple files. The number of such files is called the partitioning fan-out. Using the hash function on the hash keys guarantees that any two joining records must be in the same pair of files. Therefore, the task of joining two large inputs has been reduced to multiple, but smaller, instances of the same tasks. The hash join is then applied to each pair of partitioned files.

Recursive Hash Join 

If the build input is so large that inputs for a standard external merge sorts would require multiple merge levels, multiple partitioning steps and multiple partitioning levels are required. If only some of the partitions are large, additional partitioning steps are used only for those. In order to make all partitioning steps as fast as possible, large, asynchronous I/O operations are used so that a single thread can keep multiple disk drives busy.

Note If the build input is larger but not a lot larger than the available memory, elements of in-memory hash join and grace hash join are combined in a single step, producing a hybrid hash join.

It is not always possible during optimization to determine which hash join will be used. Therefore, Microsoft SQL Server starts using an in-memory hash join and gradually transitions to grace hash join and recursive hash join depending on the size of the build input.

If the optimizer anticipates wrongly which of the two inputs is smaller and therefore should have been the build input, the build and probe roles are reversed dynamically. The hash join makes sure that it uses the smaller overflow file as build input. This technique is called role reversal.

Cc917579.spacer(en-us,TechNet.10).gif

Show: