Home, Query Optimizer, BenchmarksServer Systems ProcessorsStorageScripts ExecStats

Query Optimizer and Performance Tuning

The SQL Server Query Optimizer

Sometime in 2008, I started what was to be a series on SQLBlog about the SQL Server execution plan cost model, i.e., the Cost Based Optimizer (CBO). This was to be an update of my material on the SQL Server 2000 execution plan formulas to SQL Server 2005. At the time, I could not upload images and an explanation without pictures is very tedious to follow. This is the same topic, except that I can now upload images, so important points are now illustrated. Also, because of the lateness, I will probably discontinue any work on SQL Server 2005. Any near term work will be on SQL Server 2008 SP1 or SP2 when it comes, and then shift to 2008 R2.

  1)  Examples with AdventureWorks,
  2)  Index Seek and Key Lookup,
  3)  Multi-Row Key Lookups,
  4)  Table Scan,
  5)  Loop, Hash, Merge Joins,
  6)  Insert, Update, Delete,
  7)  Parallelism I (2010?)
  8)  Parallelism II
  9)  Parallelism III

The coverage here includes Index Seek, Key Lookup (formerly Bookmark Lookup),Table Scans, Nested Loops, Hash and Merge joins. In SQL Server 2005 and later, Key Lookups to a clustered index and the Nested Loops (or loop join) are now the same operation.

I started with using the Adventure Works database, as everyone can get the exact copy of this database. However, Adventure Works is too small to demonstrate parallel execution plans. The TPC-H database is suitable and the data generator is available on the TPC website. The project is now build-able directly from Visual Studio, no editing required. There is also a data generator for TPC-E. (I can build version 1.8 on VS2010, but not on later VS nor can I build version 1.12?)

Cost Model versus Actual (2020-07)

I don't have time to do a proper write up of what the actual cost structure is relative to the Query Optimizer Cost Model. For the time being, a very very simple model is as following.

The SQL Server Query Optimizer Cost model is roughly as follows, first for IO:
Random (& first page of scan) IO:   0.003215 (1/320 -> 320 IOPS)
Sequential (incremental) IO:           0.00074074 (1/1350 -> 1350 pages/sec)

The CPU cost is :
First row of page:   0.0001581
incremental row:    0.0000011

In the modern era, despite people that insisting they need more memory, the really is that a full boat server system has more than enough memory that a properly designed transaction processing system has almost all active data in the buffer cache. The actual cost model is then based on data being in memory, and IO is not accounted for.

The first step of an operation, excluding connection setup cost, might be high, on the order of ten micro-seconds (forever in core clocks). The cost of an incremental index seek might be on the order of 2-3 µs and we expect this to depend on index depth among other factors. An accurate cost model might be unpredicatable because everything depends on the contents of the processor core L1, L2 and L3 caches.

Index Seek or Key Lookup:   2-3 µs
Scan - incremental page       0.8 µs
row touch cost:                   0.05 µs

The important point is that this representation of actual cost is very different from the SQL Server Query Optimizer Cost Model.

Additional Query Optimizer and Performance Tuning Material

The Cluster Key 2020-02 (in-progress)

Indexes - a Quantitative Basis 2019-11 (in-progress)

The SQL Server Execution Plan Cost Model 2019-09

Mysterious Performance Symptoms in SQL Server 2018-07

Memory Allocated To Plan Caching 2017-08, updated 2017-12 (on SQL Blog)

SQL Server Scaling Project Overview 2016-12

Insert Performance Limitations with Sequentially Increasing Index 2016-10

Statistics that need special attention 2014-11

Top Clause and Other Factors in Problematic Execution Plans 2014-04 (Relativity 8.1)

Bush Joins 2014-04

Hekaton and Benchmarks 2014-03 (preliminary)

Column Store, Parallelism and Decimal 2014-02

Load Testing 2013-06

kCura Relativity 2013-04 (version 7.x), updated 2013-09 (some 8.0),
  Updates based on Relativity version 8.1:
  TOP Clause and Other Factors, ZCodeArtifact & Statistics

Job History Row Limiter in msdb 2013-03

Path to In-Memory Databases - Hekaton 2013-02

Queries barely over the Cost Threshold for Parallelism 2012-11
(formerly Parallelism in Queries with Intermediate Plan Cost),

Decoding Stats Stream 2012-06, Update 2018-12-24

Query Optimizer Gone Wild - Complex AND-OR Combinations,

Query Optimizer Gone Wild - Full-Text Search Query Plans,

Query Optimizer Gone Wild - Loop Join to Table Scan,

Every now and then, a query that normally runs within a reasonable time, runs forever. This is one example.

The Skip Scan feature that has been in Oracle for a long time. Now that I have been advocating DW on SSD, I think it is important for SQL Server to have this feature as well. Never be afraid to borrow other people's good ideas.

SIMD Extensions for the Database Storage Engine


Parallelism Strategy and Comments (2010 Oct?),

Execution Plan Cost Model,

IO Cost Structure (2010 Oct?),

Logical IO as a Metric,

Excerpts from BOL,

and from SQL-Server-Performance A First Look at Execution Plan Costs in Yukon Beta 1 2005-01

The SQL Server 2000 Cost Based Optimizer

Back in 2002, I published on Sql-Server-Performance explaining in detail how the formulas used by SQL Server 2000 CBO can be derived using a set of tables populated to a range of specific row and page values. The cost model changed from SQL Server 2000 to 2005, but the full detail derivation of the exact SQL Server 2005 and 2008 cost model is not provided here. Rather, the Adventure Works database will be used to demonstrate basic points of the CBO model.

The original document for the SQL Server 2000 plan cost formulas seem to have broken links. I am reposting an interim copy for now SQL Server 2000 CBO. The formatting is rough, as it will take a while to clean up the html.

Performance Overview

Some discussion on the big picture diagram from the home page.


The previous version below


Of course, that does not mean it is complete, so please send feedback via Joe on SQLblogs

Below is an image of the SQL Server Engine, not sure who is the original source (It might be from an EMC whitepaper on SQL Server?).


One source is EMC document H12341, "Microsoft SQL Server Best Practices and Design Guidelines for EMC Storage," 2013. A new version is H14621, 2015


Oracle links

Below are links to Oracle query optimization material that may be of interest. We should not be averse to see what is happening outside of SQL Server world.

Oracle adaptive query optimization Optimizer with Oracle Database 12c(pdf).
Oracle Query Optimizer Concepts
University of Maryland CS slide-deck Adaptive Query Processing,