Query Optimizer

Query Optimization Research Papers

Two of the questions I’ve been asked sometimes are which sources I researched to write my Query Optimizer book and which research papers can I recommend to learn more about query optimization. Since I got asked about it again at the Tampa SQLSaturday last week, I wrote this short article on my flight back to Los Angeles to discuss this topic.

But first a warning: reading these academic papers may require a strong computer science background and they are usually more complicated than the SQL Server documentation, books or blogs we read every day. In addition, there are dozens or even hundreds of these articles, covering more than 40 years of query optimization research. Although I cannot list all the ones I have read I can definitely give you a way to get started so you can continue with the topics that may interest you.

Research papers reference other papers in the text and you can find the referenced paper details at the end of each article, so if you are interested in one particular area you can go and read that paper directly. By following other listed sources, which will also have additional references, you could find an almost unlimited source of information.

Although research papers usually focus on a specific area or problem you can get started by reading a few articles which are a more general overview before trying to read more specific topics. Some of these papers to get started are:

An Overview of Query Optimization in Relational Systems by Surajit Chaudhuri

Query Optimization by Yannis E. Ioannidis

An Overview of Data Warehousing and OLAP Technology by Surajit Chaudhuri, Umeshwar Dayal

By following references on those and other similar papers you can find dozens of articles which would be impossible to list here, but just to give you three examples:

Optimizing Join Orders by Michael Steinbrunn, Guido Moerkotte, Alfons Kemper

An Overview of Cost-based Optimization of Queries with Aggregates by Surajit Chaudhuri

Counting, Enumerating, and Sampling of Execution Plans in a Cost-Based Query Optimizer by Florian Waas, Cesar Galindo-Legaria

Some of these papers may be SQL Server related:

Query Processing for SQL Updates by Cesar Galindo-Legaria, Stefano Stefani, Florian Waas

Self-Tuning Database Systems: A Decade of Progress by Surajit Chaudhuri

An Efficient Cost-Driven Index Selection Tool for Microsoft SQL Server by Surajit Chaudhuri, Vivek Narasayya

SQL Server implemented its own cost-based query optimizer based on the Cascades Framework, when its database engine was re-architected for the release of SQL Server 7.0. Cascades is also based on other previous research work: Volcano and Exodus. You can read about these research projects here:

The Cascades Framework for Query Optimization by Goetz Graefe

The Volcano optimizer generator: Extensibility and efficient search by Goetz Graefe

The EXODUS Optimizer Generator by Goetz Graefe, David J. DeWitt

Finally, in this post I covered query optimization papers but obviously you can also find information on other areas of database research as well.

Statistics on Ascending Keys

Feb 26th, 2013

by Benjamin Nevarez.

8 comments

One query processor problem I’ve been trying to research since some time ago is that of statistics on ascending keys. The traditional recommendation from Microsoft to fix this problem is to manually update statistics after loading data as explained here. The document describes the problem in the following way:

“Statistics on ascending or descending key columns, such as IDENTITY or real-time timestamp columns, might require more frequent statistics updates than the query optimizer performs. Insert operations append new values to ascending or descending columns. The number of rows added might be too small to trigger a statistics update. If statistics are not up-to-date and queries select from the most recently added rows, the current statistics will not have cardinality estimates for these new values. This can result in inaccurate cardinality estimates and slow query performance. For example, a query that selects from the most recent sales order dates will have inaccurate cardinality estimates if the statistics are not updated to include cardinality estimates for the most recent sales order dates.”

Trace flags 2389 and 2390, which were first published by Ian Jose in his article Ascending Keys and Auto Quick Corrected Statistics, can help to address this problem. Ian explains that when data typically ascends, most new insertions are out of the previously found range. My testing shows that these new values fall outside the range of values of the existing statistics histogram. This can lead to poorly performing plans as filters selecting recent data seem to exclude the entire relation when in fact a significant number of rows may be included.

To show you what the problem is and how this mystery trace flags 2389 works, let us start by creating a table in AdventureWorks2012.

CREATE TABLE dbo.SalesOrderHeader (
    SalesOrderID int NOT NULL,
    RevisionNumber tinyint NOT NULL,
    OrderDate datetime NOT NULL,
    DueDate datetime NOT NULL,
    ShipDate datetime NULL,
    Status tinyint NOT NULL,
    OnlineOrderFlag dbo.Flag NOT NULL,
    SalesOrderNumber nvarchar(25) NOT NULL,
    PurchaseOrderNumber dbo.OrderNumber NULL,
    AccountNumber dbo.AccountNumber NULL,
    CustomerID int NOT NULL,
    SalesPersonID int NULL,
    TerritoryID int NULL,
    BillToAddressID int NOT NULL,
    ShipToAddressID int NOT NULL,
    ShipMethodID int NOT NULL,
    CreditCardID int NULL,
    CreditCardApprovalCode varchar(15) NULL,
    CurrencyRateID int NULL,
    SubTotal money NOT NULL,
    TaxAmt money NOT NULL,
    Freight money NOT NULL,
    TotalDue money NOT NULL,
    Comment nvarchar(128) NULL,
    rowguid uniqueidentifier NOT NULL,
    ModifiedDate datetime NOT NULL
)

Populate the table with some initial data and create an index on it (notice that both tables have the same name but in the dbo and Sales schemas)

INSERT INTO dbo.SalesOrderHeader SELECT * FROM Sales.SalesOrderHeader 
WHERE OrderDate < '2008-07-20 00:00:00.000'
CREATE INDEX IX_OrderDate ON SalesOrderHeader(OrderDate)

The problem

After creating the index SQL Server will also create a statistics object for it, so a query like this will have a good cardinality estimate as shown next (as there is data for July 19 and it is captured on the last step of the statistics histogram object, which you can verify by using the DBCC SHOW_STASTISTICS statement).

SELECT * FROM dbo.SalesOrderHeader WHERE OrderDate = '2008-07-19 00:00:00.000'

Now, let us suppose we add new data for July 20th.

INSERT INTO dbo.SalesOrderHeader SELECT * FROM Sales.SalesOrderHeader 
WHERE OrderDate = '2008-07-20 00:00:00.000'

Changing the query to look for records for July 20

SELECT * FROM dbo.SalesOrderHeader WHERE OrderDate = '2008-07-20 00:00:00.000'

Since the number of rows added is too small, it does not trigger an automatic update of statistics. And since the value July 20 is not represented on the histogram SQL Server will use an estimate of 1 as shown in the following plan

Although both plans showed in this example are very similar a bad cardinality estimate may produce bad plans in some more realistic scenarios and queries.

Using trace flag 2389

Now let us see how trace flag 2389 helps on this problem. Run the next statements (notice that trace flag 2388 has not been mentioned before and will be explained shortly)

DBCC TRACEON (2388)
DBCC TRACEON (2389)

Trace flag 2389, which was introduced with SQL Server 2005 Service Pack 1, begins to track the nature of columns via subsequent operations of updating statistics. When the statistics are seen to increase three times in a row the column is branded ascending.

Trace flag 2388 is not required to enable the behavior described in this article but we can use it to show how trace flags 2390 works and determine if a column has been branded ascending. The trace flag changes the output of the DBCC SHOW_STATISTICS statement to show you a historical look at the most recent statistics update operations.

Trace flag 2390 enables a similar behavior than 2389 even if the ascending nature of the column is not known but I will not cover it here.

Run DBCC SHOW_STASTISTICS

DBCC SHOW_STATISTICS ('dbo.SalesOrderHeader', 'IX_OrderDate')

The statement shows the following output

Updated              Table Cardinality      Snapshot Ctr         Steps  Density                Rows Above             Rows Below             Squared Variance Error Inserts Since Last Update Deletes Since Last Update Leading column Type
-------------------- ---------------------- -------------------- ------ ---------------------- ---------------------- ---------------------- ---------------------- ------------------------- ------------------------- -------------------
Feb 26 2013  2:31AM  31095                  31095                199    0.000899280596058816   NULL                   NULL                   NULL                   NULL                      NULL                      Unknown

Not much data for now. But I’ll show you this output after three consecutive batches inserting data and updating statistics. Run the following statement to update statistics including the data you just added for February 20th.

UPDATE STATISTICS dbo.SalesOrderHeader WITH FULLSCAN

DBCC SHOW_STATISTICS now shows

Updated              Table Cardinality      Snapshot Ctr         Steps  Density                Rows Above             Rows Below             Squared Variance Error Inserts Since Last Update Deletes Since Last Update Leading column Type
-------------------- ---------------------- -------------------- ------ ---------------------- ---------------------- ---------------------- ---------------------- ------------------------- ------------------------- -------------------
Feb 26 2013  2:40AM  31125                  31125                199    0.000898472615517676   30                     0                      0.0135968539563045     30                        0                         Unknown
Feb 26 2013  2:31AM  31095                  31095                199    0.000899280596058816   NULL                   NULL                   NULL                   NULL                      NULL                      NULL

where ‘Rows Above’ and ‘Insert Since Last Update’ accounts for the 30 rows added previously (you may need to scroll to the right). Now run the second batch

INSERT INTO dbo.SalesOrderHeader SELECT * FROM Sales.SalesOrderHeader 
WHERE OrderDate = '2008-07-21 00:00:00.000'

Again running this query will verify the one row estimate in the plan

SELECT * FROM dbo.SalesOrderHeader WHERE OrderDate = '2008-07-21 00:00:00.000'

Update statistics again

UPDATE STATISTICS dbo.SalesOrderHeader WITH FULLSCAN

DBCC SHOW_STATISTICS now shows this. Notice a new record with ‘Insert Since Last Update’ and ‘Rows Above’ with a value of 27. ‘Leading column Type’ still shows ‘Unknown’.

Updated              Table Cardinality      Snapshot Ctr         Steps  Density                Rows Above             Rows Below             Squared Variance Error Inserts Since Last Update Deletes Since Last Update Leading column Type
-------------------- ---------------------- -------------------- ------ ---------------------- ---------------------- ---------------------- ---------------------- ------------------------- ------------------------- -------------------
Feb 26 2013  2:44AM  31152                  31152                199    0.000897666090168059   27                     0                      0.0122265623860741     27                        0                         Unknown
Feb 26 2013  2:40AM  31125                  31125                199    0.000898472615517676   30                     0                      0.0135968539563045     30                        0                         NULL
Feb 26 2013  2:31AM  31095                  31095                199    0.000899280596058816   NULL                   NULL                   NULL                   NULL                      NULL                      NULL

A third batch

INSERT INTO dbo.SalesOrderHeader SELECT * FROM Sales.SalesOrderHeader 
WHERE OrderDate = '2008-07-22 00:00:00.000'

Update statistics one last time

UPDATE STATISTICS dbo.SalesOrderHeader WITH FULLSCAN

DBCC SHOW_STATISTICS now shows

Updated              Table Cardinality      Snapshot Ctr         Steps  Density                Rows Above             Rows Below             Squared Variance Error Inserts Since Last Update Deletes Since Last Update Leading column Type
-------------------- ---------------------- -------------------- ------ ---------------------- ---------------------- ---------------------- ---------------------- ------------------------- ------------------------- -------------------
Feb 26 2013  2:47AM  31184                  31184                199    0.000896860961802304   32                     0                      0.0144758706820584     32                        0                         Ascending
Feb 26 2013  2:44AM  31152                  31152                199    0.000897666090168059   27                     0                      0.0122265623860741     27                        0                         NULL
Feb 26 2013  2:40AM  31125                  31125                199    0.000898472615517676   30                     0                      0.0135968539563045     30                        0                         NULL
Feb 26 2013  2:31AM  31095                  31095                199    0.000899280596058816   NULL                   NULL                   NULL                   NULL                      NULL                      NULL

In addition to the new record accounting for the 32 rows added, now you can notice that the branding was changed to ‘Ascending’. Once the column is branded ‘Ascending’ SQL Server will be able to give you a better cardinality estimate, without the need to manually update statistics.

Now try this batch

INSERT INTO dbo.SalesOrderHeader SELECT * FROM Sales.SalesOrderHeader 
WHERE OrderDate = '2008-07-23 00:00:00.000'

And run the following query

SELECT * FROM dbo.SalesOrderHeader WHERE OrderDate = '2008-07-23 00:00:00.000'

This time we get a better cardinality estimate. Notice that no UPDATE STATISTICS was required this time.

Instead the estimated of one row now we get 27.9677. But where is this value coming from? The query optimizer is now using the density information of the statistics object. The definition of density is 1 / number of distinct values and the estimated number of rows is obtained using the density multiplied by the number of records in the table which in this case is 0.000896861 * 31184, or 27.967713424 as shown in the plan. Also notice that density information is only used for values not covered in the histogram (You can see the density information using the same DBCC SHOW_STATISTICS statement but in another session where trace flag 2388 is not enabled).

In addition, if we look for data that does not exist we still get the one row estimate which is always adequate since it will return 0 records.

SELECT * FROM dbo.SalesOrderHeader WHERE OrderDate = '2008-07-23 00:00:00.000'

Notice that branding a column ascending requires statistics to increase three times in a row. If later we insert older data, breaking the ascending sequence, the column ‘Leading column Type’ will show ‘Stationary’ and the query processor will be back to the original cardinality estimate behavior. Three new additional updates in a row with increasing values can brand it as Ascending again.

Finally, at this moment I am not able to verify if these trace flags are “officially” documented and supported by Microsoft. Interestingly they are documented in the article FIX: You may notice a large increase in compile time when you enable trace flags 2389 and 2390 in SQL Server 2005 Service Pack 1 (look at the ‘More Information’ section). Another fix is documented here. Anyway, in any case talk to Microsoft and obviously test your application carefully if you think that these trace flags can improve the performance of your application.

More Undocumented Query Optimizer Trace Flags

Apr 28th, 2012

by Benjamin Nevarez.

6 comments

This is my second post discussing some query optimizer undocumented trace flags (you can read the first one, “Inside the Query Optimizer Memo Structure”, here). Although is not the purpose of this post to discuss the entire optimization process or go into detail on any of the optimization phases, you can read more about it in my book Inside the SQL Server Query Optimizer, which you can download for free from the simple-talk website. And same as before, please bear in mind that all these trace flags are undocumented and unsupported, and should not be used on a production environment. You can use them as a way to explore and understand how the query optimizer works.

As mentioned in my previous post, you will first have to enable the trace flag 3604 to redirect the trace output to the client executing the command, in this case to the Messages tab in SQL Server Management Studio.

DBCC TRACEON(3604)

I’ll start with three trace flags which display logical and physical trees used during the optimization process. First, trace flag 8605 will display the query initial tree representation created by SQL Server. Test if by running

SELECT e.EmployeeID FROM HumanResources.Employee AS e
INNER JOIN Sales.SalesPerson AS s ON e.EmployeeID = s.SalesPersonID
OPTION (RECOMPILE, QUERYTRACEON 8605)

It will show the following output

*** Converted Tree: ***
    LogOp_Project QCOL: [e].EmployeeID
        LogOp_Join
            LogOp_Get TBL: HumanResources.Employee(alias TBL: e) HumanResources.Employee TableID=901578250 TableReferenceID=0 IsRow: COL: IsBaseRow1001 
            LogOp_Get TBL: Sales.SalesPerson(alias TBL: s) Sales.SalesPerson TableID=1042102753 TableReferenceID=0 IsRow: COL: IsBaseRow1003 
            ScaOp_Comp x_cmpEq
                ScaOp_Identifier QCOL: [e].EmployeeID
                ScaOp_Identifier QCOL: [s].SalesPersonID
        AncOp_PrjList

Trace flag 8606 will display additional logical trees used during the optimization process. Run

SELECT e.EmployeeID FROM HumanResources.Employee AS e
INNER JOIN Sales.SalesPerson AS s ON e.EmployeeID = s.SalesPersonID
OPTION (RECOMPILE, QUERYTRACEON 8606)

The output shows several different logical trees: input tree, simplified tree, join-collapsed tree, tree before project normalization, and tree after project normalization. These trees will include logical operators only. Part of the output is shown next.

*** Input Tree: *** LogOp_Project QCOL: [e].EmployeeID LogOp_Select LogOp_Join LogOp_Get TBL: HumanResources.Employee(alias TBL: e) HumanResources.Employee TableID=901578250 TableReferenceID=0 IsRow: COL: IsBaseRow1001 LogOp_Get TBL: Sales.SalesPerson(alias TBL: s) Sales.SalesPerson TableID=1042102753 TableReferenceID=0 IsRow: COL: IsBaseRow1003 ScaOp_Const TI(bit,ML=1) XVAR(bit,Not Owned,Value=1) ScaOp_Comp x_cmpEq ScaOp_Identifier QCOL: [e].EmployeeID ScaOp_Identifier QCOL: [s].SalesPersonID AncOp_PrjList *******************

*** Simplified Tree: *** LogOp_Join LogOp_Get TBL: HumanResources.Employee(alias TBL: e) HumanResources.Employee TableID=901578250 TableReferenceID=0 IsRow: COL: IsBaseRow1001 LogOp_Get TBL: Sales.SalesPerson(alias TBL: s) Sales.SalesPerson TableID=1042102753 TableReferenceID=0 IsRow: COL: IsBaseRow1003 ScaOp_Comp x_cmpEq ScaOp_Identifier QCOL: [s].SalesPersonID ScaOp_Identifier QCOL: [e].EmployeeID ******************* *** Join-collapsed Tree: *** LogOp_Join LogOp_Get TBL: HumanResources.Employee(alias TBL: e) HumanResources.Employee TableID=901578250 TableReferenceID=0 IsRow: COL: IsBaseRow1001 LogOp_Get TBL: Sales.SalesPerson(alias TBL: s) Sales.SalesPerson TableID=1042102753 TableReferenceID=0 IsRow: COL: IsBaseRow1003 ScaOp_Comp x_cmpEq ScaOp_Identifier QCOL: [s].SalesPersonID ScaOp_Identifier QCOL: [e].EmployeeID ******************* *** Tree Before Project Normalization *** LogOp_Join LogOp_Get TBL: HumanResources.Employee(alias TBL: e) HumanResources.Employee TableID=901578250 TableReferenceID=0 IsRow: COL: IsBaseRow1001 LogOp_Get TBL: Sales.SalesPerson(alias TBL: s) Sales.SalesPerson TableID=1042102753 TableReferenceID=0 IsRow: COL: IsBaseRow1003 ScaOp_Comp x_cmpEq ScaOp_Identifier QCOL: [s].SalesPersonID ScaOp_Identifier QCOL: [e].EmployeeID ***************************************** *** Tree After Project Normalization *** LogOp_Join LogOp_Get TBL: HumanResources.Employee(alias TBL: e) HumanResources.Employee TableID=901578250 TableReferenceID=0 IsRow: COL: IsBaseRow1001 LogOp_Get TBL: Sales.SalesPerson(alias TBL: s) Sales.SalesPerson TableID=1042102753 TableReferenceID=0 IsRow: COL: IsBaseRow1003 ScaOp_Comp x_cmpEq ScaOp_Identifier QCOL: [s].SalesPersonID ScaOp_Identifier QCOL: [e].EmployeeID **************************************** *** Stop search, level 1 ***

One interesting example is seeing how a tree is simplified when the query optimizer can detect a contradiction during the simplification phase. The purpose of the simplification stage is to reduce the query tree into a simpler form in order to make the optimization process easier. Contradiction detection is one of several possible simplifications. Following on an example on my book and this blog post, run the following query

SELECT * FROM HumanResources.Employee
WHERE VacationHours > 300
OPTION (RECOMPILE, QUERYTRACEON 8606)

Part of the output is next

*** Input Tree: ***
        LogOp_Project QCOL: [AdventureWorks].[HumanResources].[Employee].EmployeeID QCOL: [AdventureWorks].[HumanResources].[Employee].NationalIDNumber QCOL: [AdventureWorks].[HumanResources].[Employee].ContactID QCOL: [AdventureWorks].[HumanResources].[Employee].LoginID QCOL: [AdventureWorks].[HumanResources].[Employee].ManagerID QCOL: [AdventureWorks].[HumanResources].[Employee].Title QCOL: [AdventureWorks].[HumanResources].[Employee].BirthDate QCOL: [AdventureWorks].[HumanResources].[Employee].MaritalStatus QCOL: [AdventureWorks].[HumanResources].[Employee].Gender QCOL: [AdventureWorks].[HumanResources].[Employee].HireDate QCOL: [AdventureWorks].[HumanResources].[Employee].SalariedFlag QCOL: [AdventureWorks].[HumanResources].[Employee].VacationHours QCOL: [AdventureWorks].[HumanResources].[Employee].SickLeaveHours QCOL: [AdventureWorks].[HumanResources].[Employee].CurrentFlag QCOL: [AdventureWorks].[HumanResources].[Employee].rowguid QCOL: [AdventureWorks].[HumanResources].[Employee].ModifiedDate
            LogOp_Select
                LogOp_Get TBL: HumanResources.Employee HumanResources.Employee TableID=901578250 TableReferenceID=0 IsRow: COL: IsBaseRow1001 
                ScaOp_Comp x_cmpGt
                    ScaOp_Identifier QCOL: [AdventureWorks].[HumanResources].[Employee].VacationHours
                    ScaOp_Const TI(smallint,ML=2) XVAR(smallint,Not Owned,Value=300)
            AncOp_PrjList 
*******************
*** Simplified Tree: ***
        LogOp_ConstTableGet (0) COL: Chk1000  COL: IsBaseRow1001  QCOL: [AdventureWorks].[HumanResources].[Employee].EmployeeID QCOL: [AdventureWorks].[HumanResources].[Employee].NationalIDNumber QCOL: [AdventureWorks].[HumanResources].[Employee].ContactID QCOL: [AdventureWorks].[HumanResources].[Employee].LoginID QCOL: [AdventureWorks].[HumanResources].[Employee].ManagerID QCOL: [AdventureWorks].[HumanResources].[Employee].Title QCOL: [AdventureWorks].[HumanResources].[Employee].BirthDate QCOL: [AdventureWorks].[HumanResources].[Employee].MaritalStatus QCOL: [AdventureWorks].[HumanResources].[Employee].Gender QCOL: [AdventureWorks].[HumanResources].[Employee].HireDate QCOL: [AdventureWorks].[HumanResources].[Employee].SalariedFlag QCOL: [AdventureWorks].[HumanResources].[Employee].VacationHours QCOL: [AdventureWorks].[HumanResources].[Employee].SickLeaveHours QCOL: [AdventureWorks].[HumanResources].[Employee].CurrentFlag QCOL: [AdventureWorks].[HumanResources].[Employee].rowguid QCOL: [AdventureWorks].[HumanResources].[Employee].ModifiedDate
*******************
*** Join-collapsed Tree: ***
        LogOp_ConstTableGet (0) COL: Chk1000  COL: IsBaseRow1001  QCOL: [AdventureWorks].[HumanResources].[Employee].EmployeeID QCOL: [AdventureWorks].[HumanResources].[Employee].NationalIDNumber QCOL: [AdventureWorks].[HumanResources].[Employee].ContactID QCOL: [AdventureWorks].[HumanResources].[Employee].LoginID QCOL: [AdventureWorks].[HumanResources].[Employee].ManagerID QCOL: [AdventureWorks].[HumanResources].[Employee].Title QCOL: [AdventureWorks].[HumanResources].[Employee].BirthDate QCOL: [AdventureWorks].[HumanResources].[Employee].MaritalStatus QCOL: [AdventureWorks].[HumanResources].[Employee].Gender QCOL: [AdventureWorks].[HumanResources].[Employee].HireDate QCOL: [AdventureWorks].[HumanResources].[Employee].SalariedFlag QCOL: [AdventureWorks].[HumanResources].[Employee].VacationHours QCOL: [AdventureWorks].[HumanResources].[Employee].SickLeaveHours QCOL: [AdventureWorks].[HumanResources].[Employee].CurrentFlag QCOL: [AdventureWorks].[HumanResources].[Employee].rowguid QCOL: [AdventureWorks].[HumanResources].[Employee].ModifiedDate
*******************
*** Tree Before Project Normalization ***
        LogOp_ConstTableGet (0) COL: Chk1000  COL: IsBaseRow1001  QCOL: [AdventureWorks].[HumanResources].[Employee].EmployeeID QCOL: [AdventureWorks].[HumanResources].[Employee].NationalIDNumber QCOL: [AdventureWorks].[HumanResources].[Employee].ContactID QCOL: [AdventureWorks].[HumanResources].[Employee].LoginID QCOL: [AdventureWorks].[HumanResources].[Employee].ManagerID QCOL: [AdventureWorks].[HumanResources].[Employee].Title QCOL: [AdventureWorks].[HumanResources].[Employee].BirthDate QCOL: [AdventureWorks].[HumanResources].[Employee].MaritalStatus QCOL: [AdventureWorks].[HumanResources].[Employee].Gender QCOL: [AdventureWorks].[HumanResources].[Employee].HireDate QCOL: [AdventureWorks].[HumanResources].[Employee].SalariedFlag QCOL: [AdventureWorks].[HumanResources].[Employee].VacationHours QCOL: [AdventureWorks].[HumanResources].[Employee].SickLeaveHours QCOL: [AdventureWorks].[HumanResources].[Employee].CurrentFlag QCOL: [AdventureWorks].[HumanResources].[Employee].rowguid QCOL: [AdventureWorks].[HumanResources].[Employee].ModifiedDate
*****************************************
*** Tree After Project Normalization ***
        LogOp_ConstTableGet (0) COL: Chk1000  COL: IsBaseRow1001  QCOL: [AdventureWorks].[HumanResources].[Employee].EmployeeID QCOL: [AdventureWorks].[HumanResources].[Employee].NationalIDNumber QCOL: [AdventureWorks].[HumanResources].[Employee].ContactID QCOL: [AdventureWorks].[HumanResources].[Employee].LoginID QCOL: [AdventureWorks].[HumanResources].[Employee].ManagerID QCOL: [AdventureWorks].[HumanResources].[Employee].Title QCOL: [AdventureWorks].[HumanResources].[Employee].BirthDate QCOL: [AdventureWorks].[HumanResources].[Employee].MaritalStatus QCOL: [AdventureWorks].[HumanResources].[Employee].Gender QCOL: [AdventureWorks].[HumanResources].[Employee].HireDate QCOL: [AdventureWorks].[HumanResources].[Employee].SalariedFlag QCOL: [AdventureWorks].[HumanResources].[Employee].VacationHours QCOL: [AdventureWorks].[HumanResources].[Employee].SickLeaveHours QCOL: [AdventureWorks].[HumanResources].[Employee].CurrentFlag QCOL: [AdventureWorks].[HumanResources].[Employee].rowguid QCOL: [AdventureWorks].[HumanResources].[Employee].ModifiedDate

In this case the query optimizer makes use of an existing check constraint to conclude that no records qualify for the predicate VacationHours > 300, replacing the entire tree with a LogOp_ConstTableGet logical operator. If you try displaying an output tree, as discussed next, you will get a PhyOp_ConstTableScan physical operator, and you will get a constant scan operator on the final execution plan. You can see a different behavior if you try the same query with a predicate like VacationHours > 20.

Trace flag 8607 shows the optimization output tree. Try the following sentence

SELECT e.EmployeeID FROM HumanResources.Employee AS e
INNER JOIN Sales.SalesPerson AS s ON e.EmployeeID = s.SalesPersonID
OPTION (RECOMPILE, QUERYTRACEON 8607)

Notice that this time we have physical operators and the output tree is closer to the final execution plan.

****************************************
*** Output Tree: ***
        PhyOp_Apply lookup TBL: HumanResources.Employee (0) (x_jtInner)
            PhyOp_Range TBL: Sales.SalesPerson(alias TBL: s)(2) ASC  Bmk ( QCOL: [s].SalesPersonID) IsRow: COL: IsBaseRow1003 
            PhyOp_Range TBL: HumanResources.Employee(alias TBL: e)(1) ASC  Bmk ( QCOL: [e].EmployeeID) IsRow: COL: IsBaseRow1001 
                ScaOp_Comp x_cmpEq
                    ScaOp_Identifier QCOL: [s].SalesPersonID
                    ScaOp_Identifier QCOL: [e].EmployeeID
********************
** Query marked as Cachable
********************

Trace flag 8675 shows the query optimization phases for a specific optimization along with some other information like cost estimation, tasks, etc. You may want to test it with complex queries to see different optimization phases like in the following example

SELECT I.CustomerID, C.FirstName, C.LastName, A.AddressLine1, A.City,
SP.Name AS State, CR.Name AS CountryRegion
FROM Person.Contact AS C
JOIN Sales.Individual AS I ON C.ContactID = I.ContactID
JOIN Sales.CustomerAddress AS CA ON CA.CustomerID = I.CustomerID
JOIN Person.Address AS A ON A.AddressID = CA.AddressID
JOIN Person.StateProvince SP ON
SP.StateProvinceID = A.StateProvinceID
JOIN Person.CountryRegion CR ON
CR.CountryRegionCode = SP.CountryRegionCode
ORDER BY I.CustomerID
OPTION (RECOMPILE, QUERYTRACEON 8675)

It shows the following output

End of simplification, time: 0.003 net: 0.003 total: 0.003 net: 0.003
end exploration, tasks: 275 no total cost time: 0.005 net: 0.005 total: 0.009 net: 0.009
end exploration, tasks: 642 no total cost time: 0.003 net: 0.003 total: 0.012 net: 0.012
end search(0),  cost: 9.04 tasks: 681 time: 0 net: 0 total: 0.013 net: 0.013
end exploration, tasks: 1465 Cost = 9.04 time: 0.004 net: 0.004 total: 0.017 net: 0.017
end exploration, tasks: 2518 Cost = 9.04 time: 0.007 net: 0.007 total: 0.024 net: 0.024
end search(1),  cost: 5.86879 tasks: 2609 time: 0 net: 0 total: 0.025 net: 0.025
end exploration, tasks: 2610 Cost = 5.86879 time: 0 net: 0 total: 0.025 net: 0.025
end exploration, tasks: 5170 Cost = 5.86879 time: 0.021 net: 0.021 total: 0.047 net: 0.047
end search(1),  cost: 5.86248 tasks: 5469 time: 0.001 net: 0.001 total: 0.048 net: 0.048
end exploration, tasks: 5756 Cost = 5.86248 time: 0.001 net: 0.001 total: 0.05 net: 0.05
end exploration, tasks: 6434 Cost = 5.86248 time: 0.005 net: 0.005 total: 0.055 net: 0.055
end search(2),  cost: 5.84575 tasks: 7092 time: 0.004 net: 0.004 total: 0.059 net: 0.059
End of post optimization rewrite, time: 0 net: 0 total: 0.059 net: 0.059
End of query plan compilation, time: 0 net: 0 total: 0.06 net: 0.06

Note the optimization phases search(0), search(1) and search(2). Also, as mentioned in my book, you need at least three tables to qualify for search 0, so the following query will go directly to search 1 (you can also test this with trace flag 2372 as described later):

SELECT * FROM HumanResources.Employee
WHERE ManagerID = 12
OPTION (RECOMPILE, QUERYTRACEON 8675)

Trace flags 2372 and 2373 show memory utilization during the optimization process but we can also use them to gain information about the activities the query optimizer is performing for a particular query. Trace flag 2372 shows memory utilization during the different optimization stages. Same as before, more complicated queries will show more optimization stages.

SELECT I.CustomerID, C.FirstName, C.LastName, A.AddressLine1, A.City,
SP.Name AS State, CR.Name AS CountryRegion
FROM Person.Contact AS C
JOIN Sales.Individual AS I ON C.ContactID = I.ContactID
JOIN Sales.CustomerAddress AS CA ON CA.CustomerID = I.CustomerID
JOIN Person.Address AS A ON A.AddressID = CA.AddressID
JOIN Person.StateProvince SP ON
SP.StateProvinceID = A.StateProvinceID
JOIN Person.CountryRegion CR ON
CR.CountryRegionCode = SP.CountryRegionCode
ORDER BY I.CustomerID
OPTION (RECOMPILE, QUERYTRACEON 2372)

The output is next

Memory before NNFConvert: 13
Memory after NNFConvert: 14
Memory before project removal: 15
Memory after project removal: 15
Memory before simplification: 15
Memory after simplification: 35
Memory before heuristic join reordering: 35
Memory after heuristic join reordering: 46
Memory before project normalization: 46
Memory after project normalization: 46
Memory before stage TP: 46
Memory after stage TP: 81
Memory before stage QuickPlan: 81
Memory after stage QuickPlan: 144
Memory before stage Full: 144
Memory after stage Full: 156
Memory before copy out: 156
Memory after copy out: 157

Notice that “stage TP” or transaction processing phase is the same as search(0) shown before with trace flag 8675. In the same way, “stage QuickPlan” is the search(1) and “stage Full” is search(2).

Trace flag 2373 shows memory utilization while applying optimization rules and deriving properties.

SELECT e.EmployeeID FROM HumanResources.Employee AS e
INNER JOIN Sales.SalesPerson AS s ON e.EmployeeID = s.SalesPersonID
OPTION (RECOMPILE, QUERYTRACEON 2373)

Part of the output is next

Memory before rule IJtoIJSEL: 14
Memory after rule IJtoIJSEL: 14
Memory before rule MatchGet: 14
Memory after rule MatchGet: 14
Memory before rule MatchGet: 14
Memory after rule MatchGet: 14
Memory before rule JoinToIndexOnTheFly: 14
Memory after rule JoinToIndexOnTheFly: 14
Memory before rule JoinCommute: 14
Memory after rule JoinCommute: 14
Memory before rule JoinToIndexOnTheFly: 14
Memory after rule JoinToIndexOnTheFly: 14
Memory before rule JNtoIdxLookup: 14

Finally, trace 8757 can be used to skip the trivial plan optimization and basically force a full optimization. As a reminder, the trivial plan optimization is used for very simple queries that don’t require any cost estimation decision. For example, the following query will produce a trivial plan, which you can verify by looking at the optimization level or StatementOptmLevel property in your execution plan

SELECT * FROM dbo.DatabaseLog

By applying trace flag 8757, the trivial plan optimization will be skipped as you can verify by running the following query and once again verifying the optimization level property.

SELECT * FROM dbo.DatabaseLog
OPTION (QUERYTRACEON 8757)

Inside the Query Optimizer Memo Structure

Apr 25th, 2012

by Benjamin Nevarez.

3 comments

I just learned a few query-optimizer-related undocumented trace flags from my friend Dmitry Pilugin, who blogged about them in his blog in Russian, SomewhereSomehow’s Blog, and asked me if I could be interested in posting something in English. Some of these interesting trace flags allow us to see the contents of the memo structure, something I was trying to find while writing my book Inside the SQL Server Query Optimizer.

But first, a quick reminder of what the memo structure is. The memo is a search data structure that is used to store the alternatives generated and analyzed by the SQL Server query optimizer. These alternatives can be logical or physical operators and are organized into groups such that each alternative in the same group produces the same results. The query optimizer first copies the original query tree’s logical expressions into the memo structure, placing each operator from the query tree in its own group, and then triggers the entire optimization process. During this process, transformation rules are applied to generate all the alternatives, starting with these initial logical expressions. As the transformation rules produce new alternatives, these are added to their equivalent groups. Transformation rules may also produce a new expression which is not equivalent to any existing group, and which causes a new group to be created. A new memo structure is created for each optimization.

But instead of trying to explain the basics of how the memo structure works you can refer to my book, Inside the SQL Server Query Optimizer, which you can download for free from the simple-talk website. In this post I will show you how to see the contents of the memo structure. First enable the trace flag 3604 to redirect the trace output to the client executing the command, in this case SQL Server Management Studio.

DBCC TRACEON(3604)

Next I will be using the undocumented trace flags 8608 and 8615 but, although I can still use DBCC TRACEON, this time I will use the also undocumented QUERYTRACEON query hint. Please bear in mind that all these are undocumented SQL Server statements and should not be used on a production environment.

The first trace flag, 8608, will show the initial memo structure, which you can see in the Messages tab of the Query window in Management Studio.

SELECT e.EmployeeID FROM HumanResources.Employee AS e 
INNER JOIN Sales.SalesPerson AS s ON e.EmployeeID = s.SalesPersonID
OPTION (QUERYTRACEON 8608)

Running the previous query will show the following output

--- Initial Memo Structure ---
Root Group 5: Card=8.33333 (Max=10000, Min=0)
   0 LogOp_Join 0 1 4 
Group 4: 
   0 ScaOp_Comp  2 3 
Group 3: 
   0 ScaOp_Identifier  
Group 2: 
   0 ScaOp_Identifier  
Group 1: Card=17 (Max=10000, Min=0)
   0 LogOp_Get 
Group 0: Card=290 (Max=10000, Min=0)
   0 LogOp_Get

The next query uses trace flag 8615 to display the final memo structure

SELECT e.EmployeeID FROM HumanResources.Employee AS e 
INNER JOIN Sales.SalesPerson AS s ON e.EmployeeID = s.SalesPersonID
OPTION (QUERYTRACEON 8615)

which shows the following output

--- Final Memo Structure ---
Group 9: Card=1 (Max=1, Min=0)
   0 LogOp_SelectIdx 8 4 
Group 8: Card=17 (Max=10000, Min=0)
   0 LogOp_GetIdx 
Group 7: Card=1 (Max=1, Min=0)
   1 PhyOp_Range 1 ASC 4.0 Cost(RowGoal 0,ReW 0,ReB 16,Dist 17,Total 17)= 0.0058127
   0 LogOp_SelectIdx 6 4 
Group 6: Card=290 (Max=10000, Min=0)
   0 LogOp_GetIdx 
Root Group 5: Card=8.33333 (Max=10000, Min=0)
   2 PhyOp_Applyx_jtInner 1.2 7.1 Cost(RowGoal 0,ReW 0,ReB 0,Dist 0, …)= 0.00918446
   1 LogOp_Join 1 0 4 
   0 LogOp_Join 0 1 4 
Group 4: 
   0 ScaOp_Comp  2.0 3.0  Cost(RowGoal 0,ReW 0,ReB 0,Dist 0,Total 0)= 3
Group 3: 
   0 ScaOp_Identifier   Cost(RowGoal 0,ReW 0,ReB 0,Dist 0,Total 0)= 1
Group 2: 
   0 ScaOp_Identifier   Cost(RowGoal 0,ReW 0,ReB 0,Dist 0,Total 0)= 1
Group 1: Card=17 (Max=10000, Min=0)
   3 PhyOp_Range 1 ASC   Cost(RowGoal 0,ReW 0,ReB 0,Dist 0,Total 0)= 0.0033007
   2 PhyOp_Range 2 ASC   Cost(RowGoal 0,ReW 0,ReB 0,Dist 0,Total 0)= 0.0033007
   0 LogOp_Get 
Group 0: Card=290 (Max=10000, Min=0)
   0 LogOp_Get

You can notice that among other things the output shows information about operators, groups, cardinality information (Card) and cost estimation. I will be discussing a few more undocumented trace flags on a second post very soon.

Speaking at the PASS Summit and other Southern California events

Sep 8th, 2011

by Benjamin Nevarez.

No comments yet

I am currently working on the two sessions that I will be presenting at the PASS Summit: Inside the SQL Server Query Optimizer and Parameter Sniffing: the Query Optimizer vs. the Plan Cache. In addition, I will be presenting these two new sessions in other SQL Server events in Southern California including SQLSatuday #95.

First, I will be speaking at the Los Angeles SQL Server Professionals Group on Thursday September 15th. The meeting will be hosted at the UCLA Anderson School of Management and will start at 6:30 PM. I will present only one session, Inside the SQL Server Query Optimizer, in this meeting. You can find additional information about the meeting and directions on their website.

Two days later, on September 17th, I will be speaking at SQLSaturday #95 in San Diego, CA. Of course, this SQLSaturday will also have many other great speakers and the final schedule is already posted here. In addition to presenting both of my sessions described before I will be participating in the Ask the Experts – SQL Server Q&A session coordinated by Thomas Mueller. For more details and directions for SQLSaturday #95 please go to their website here.

On October 7th I will be presenting my Query Optimizer session at the Orange County SQL Server Professionals User Group in Mission Viejo, CA. Details and directions will be posted soon on their website here.

Then it is time for the PASS Summit, the largest SQL Server and BI conference in the world. The PASS Summit is hosted again this year in Seattle, WA and it is scheduled for October 11-14. The schedule for my two sessions is not final at the moment of writing this but so far it looks like I will be speaking on Wednesday and Friday.

I am flying back from the PASS Summit on Saturday and planning to present my two sessions at the SoCal Code Camp the following day, Sunday October 16th. The SoCal Code Camp is a community driven event for developers to come and learn from their peers. At this moment they are still accepting sessions so no schedule has been created yet. You can register, find additional information and directions on their website here.

Finally, although I am not going to be speaking, I will be attending SQL in the City in Los Angeles, CA on October 28th. SQL in the City is a one day SQL Server training event which will include several SQL Server MVPs and you can look at their site here for more details and information.

I look forward to meeting lots of SQL Server professionals on these events.

Code from my book Inside the SQL Server Query Optimizer

Jul 25th, 2011

by Benjamin Nevarez.

No comments yet

Recently I’ve been requested the code of my book Inside the Server Query Optimizer so I am including it in this post. The book contains a large number of example SQL queries, all of which are based on the AdventureWorks database and Chapter 6 additionally uses the AdventureWorksDW database. All code has been tested on both SQL Server 2008 and SQL Server 2008 R2. Note that these sample databases are not included by default in your SQL Server installation, but can be downloaded from the CodePlex website.

Inside the SQL Server Query Optimizer code – InsideQueryOptimizerCode.txt

Query Optimization with Denali Columnstore Indexes

Jul 18th, 2011

by Benjamin Nevarez.

3 comments

In a previous post I talked about the new columnstore indexes and their related processing algorithms which are available in SQL Server code-named Denali. In this post I will cover the query processing part of the technology in more detail and will show you some examples that you can test on the recently released CTP3 (Community Technology Preview) of the product.

Same as with previous versions of SQL Server, in Denali the query optimizer can choose between the available access methods, which now also include columnstore indexes, and as always, this will be a cost-based decision. A new choice the query optimizer will have to make is the selection of an execution mode. The new query processing algorithms mentioned in my previous post will run in what is called a batch execution mode, which is different from the traditional processing mode, now called row mode.

In the row execution mode operators process data one row at a time. The new batch execution mode process data in batches which is more efficient for large amounts of data, like the workloads present on data warehouse queries. Each operator in an execution plan can use the row execution mode and, when columnstore indexes are available, some operators can also use the batch mode. There is both an estimated and an actual execution mode and this information is displayed on the query execution plan as I will show later. It is also worth mentioning that, although columnstore indexes can speed up the performance of data warehouse queries, they are not a good choice for very selective queries returning only a few records. In this case the query optimizer may have to rely on row stores, like clustered or regular nonclustered indexes, to find those records quickly. There are no seeks on columnstore indexes.

Same as with previous versions of SQL Server, you still have the choice to use a hint to force any index in the cases where the query optimizer is not giving you a good execution plan. This can happen for example when the query optimizer is choosing a columnstore index when it shouldn’t or when you want to force a columnstore index when it is not being selected. You can also use the new IGNORE_NONCLUSTERED_COLUMNSTORE_INDEX hint to ask the query optimizer to avoid using any columnstore index.

Let me show you an example which you can test on SQL Server Denali CTP3, currently available for download here. To follow this example you will also need the AdventureWorksDWDenali database, available at CodePlex and I will use the same example on BOL to skip the basics and go directly to analyze the batch processing mode (By the way the BOL example didn’t work directly with the AdventureWorksDWDenali database so I had to add a few more columns at the end of the CREATE TABLE statement.)

First, use the following BOL code to create a partition function, a partition scheme and a new partitioned table with a columnstore index

USE AdventureWorksDWDenali;
GO

CREATE PARTITION FUNCTION [ByOrderDateMonthPF](int) AS RANGE RIGHT 
FOR VALUES (
    20050701, 20050801, 20050901, 20051001, 20051101, 20051201, 
    20060101, 20060201, 20060301, 20060401, 20060501, 20060601, 
    20060701, 20060801, 20060901, 20061001, 20061101, 20061201, 
    20070101, 20070201, 20070301, 20070401, 20070501, 20070601, 
    20070701, 20070801, 20070901, 20071001, 20071101, 20071201, 
    20080101, 20080201, 20080301, 20080401, 20080501, 20080601, 
    20080701, 20080801, 20080901, 20081001, 20081101, 20081201
) 
GO

CREATE PARTITION SCHEME [ByOrderDateMonthRange] 
AS PARTITION [ByOrderDateMonthPF] 
ALL TO ([PRIMARY]) 
GO

-- Create a partitioned version of the FactResellerSales table
CREATE TABLE [dbo].[FactResellerSalesPtnd]( 
    [ProductKey] [int] NOT NULL, 
    [OrderDateKey] [int] NOT NULL, 
    [DueDateKey] [int] NOT NULL, 
    [ShipDateKey] [int] NOT NULL, 
    [ResellerKey] [int] NOT NULL, 
    [EmployeeKey] [int] NOT NULL, 
    [PromotionKey] [int] NOT NULL, 
    [CurrencyKey] [int] NOT NULL, 
    [SalesTerritoryKey] [int] NOT NULL, 
    [SalesOrderNumber] [nvarchar](20) NOT NULL, 
    [SalesOrderLineNumber] [tinyint] NOT NULL, 
    [RevisionNumber] [tinyint] NULL, 
    [OrderQuantity] [smallint] NULL, 
    [UnitPrice] [money] NULL, 
    [ExtendedAmount] [money] NULL, 
    [UnitPriceDiscountPct] [float] NULL, 
    [DiscountAmount] [float] NULL, 
    [ProductStandardCost] [money] NULL, 
    [TotalProductCost] [money] NULL, 
    [SalesAmount] [money] NULL, 
    [TaxAmt] [money] NULL, 
    [Freight] [money] NULL, 
    [CarrierTrackingNumber] [nvarchar](25) NULL, 
    [CustomerPONumber] [nvarchar](25) NULL,
    [OrderDate] datetime NULL,
    [DueDate] datetime NULL,
    [ShipDate] datetime NULL
) ON ByOrderDateMonthRange(OrderDateKey);
GO

-- Copy the data from the FactResellerSales into the new table
INSERT INTO dbo.FactResellerSalesPtnd WITH(TABLOCK)
SELECT * FROM dbo.FactResellerSales;
GO

-- Create the columnstore index
CREATE NONCLUSTERED COLUMNSTORE INDEX [csindx_FactResellerSalesPtnd]
ON [FactResellerSalesPtnd]
( 
    [ProductKey], 
    [OrderDateKey], 
    [DueDateKey], 
    [ShipDateKey], 
    [ResellerKey], 
    [EmployeeKey], 
    [PromotionKey], 
    [CurrencyKey], 
    [SalesTerritoryKey], 
    [SalesOrderNumber], 
    [SalesOrderLineNumber], 
    [RevisionNumber], 
    [OrderQuantity], 
    [UnitPrice], 
    [ExtendedAmount], 
    [UnitPriceDiscountPct], 
    [DiscountAmount], 
    [ProductStandardCost], 
    [TotalProductCost], 
    [SalesAmount], 
    [TaxAmt], 
    [Freight], 
    [CarrierTrackingNumber], 
    [CustomerPONumber] 
);

Now run the following query

SELECT SalesTerritoryKey, SUM(ExtendedAmount) AS SalesByTerritory
FROM FactResellerSalesPtnd
GROUP BY SalesTerritoryKey;

This will create the following plan where you can see the new Columnstore Index Scan operator

The properties of the Columnstore Index Scan operator are shown next

You may notice that the actual and estimated execution mode is Row (lines 3 and 4 on the list of properties). Row execution mode was selected because the table is not large enough to require the batch execution mode. We can use the undocumented ROWCOUNT and PAGECOUNT options of the UPDATE STATISTICS statement to simulate a larger table as shown next (for more information about how this works see my post about the DTA here)

UPDATE STATISTICS FactResellerSalesPtnd WITH ROWCOUNT = 10000000, PAGECOUNT = 1000000

Removing the existing plan (using for example DBCC FREEPROCCACHE) and running the same query again will now show the following plan (only part is shown), which this time is using parallelism.

In addition, by looking at the properties of the Columnstore Index Scan you can notice that this time it is using the batch execution mode

You can also use the new IGNORE_NONCLUSTERED_COLUMNSTORE_INDEX hint to disallow the use of a columnstore index. Run the following code

SELECT SalesTerritoryKey, SUM(ExtendedAmount) AS SalesByTerritory
FROM FactResellerSalesPtnd
GROUP BY SalesTerritoryKey
OPTION (IGNORE_NONCLUSTERED_COLUMNSTORE_INDEX);

This will show you the following plan which as you can see it is now directly using the FactResellerSalesPtnd table, without using the columnstore index.

Finally, since the number of records and pages of the FactResellerSalesPtnd table was altered for this test, perhaps you want drop it and create a new copy if you need to do some additional testing

DROP TABLE FactResellerSalesPtnd

Speaking at the PASS Summit 2011

Jun 19th, 2011

by Benjamin Nevarez.

No comments yet

I am honored to be speaking at the PASS Summit again this year. I’ve been attending this SQL Server conference every year since 2003 and this will be my fourth year speaking. Same as last year I will again be presenting two sessions.

On my first session, Inside the SQL Server Query Optimizer, I will go into the internals of the Query Optimizer and will show you the steps that it performs in the background covering everything from the time a query is submitted to SQL Server until an execution plan is generated. On my second session, Parameter Sniffing: the Query Optimizer vs. the Plan Cache, I will show you how the Query Optimizer uses parameter sniffing to produce a plan tailored to the current parameters of a query and why in some cases it could be a performance problem, including troubleshooting and solutions to these cases.

The PASS Summit is less than four months away and you can register here. I look forward to meeting lots of SQL Server professionals, including those whom I only know via twitter. See you in Seattle in October.

Statistics on Computed Columns

Jun 8th, 2011

by Benjamin Nevarez.

2 comments

Another interesting topic that I usually talk about on my presentations is statistics on computed columns so I will use this post to show you how they work and how they can help you to improve the performance of your queries.

A problem faced by some queries using scalar expressions is that they usually cannot benefit from statistics and, without them, the Query Optimizer will use the 30% selectivity guess on inequality comparisons. A solution to this problem can be the use of computed columns, as SQL Server can automatically create and update statistics on these columns which can help the Query Optimizer to create better execution plans. An additional benefit of this solution is that you don’t need to specify the name of the computed column in your queries for SQL Server to use its statistics. The Query Optimizer automatically matches the computed column definition to an existing scalar expression in a query, so your applications do not need to be changed. Although computed columns have been available in previous versions of SQL Server, the automatic matching feature was only introduced with SQL Server 2005.

To see an example, run this query, which creates the plan shown next:

SELECT * FROM Sales.SalesOrderDetail
WHERE OrderQty * UnitPrice > 25000

The estimated number of rows is 36,395.1, which is 30% of the total number of rows, 121,317, although the query returns only 5 records. SQL Server is obviously using a selectivity guess, as it cannot estimate the selectivity of the expression OrderQty * UnitPrice > 25000.

Now create a computed column:

ALTER TABLE Sales.SalesOrderDetail
ADD cc AS OrderQty * UnitPrice

Run the previous SELECT statement again and note that, this time, the estimated number of rows has changed to 84.3101 which is very close to the actual number of rows returned by the query, as shown in the following plan:

You can optionally test replacing the 25,000 in the query with some other values, like 1,000, 10,000, or 20,000 and verify that the estimated again will be close to the actual number of rows returned.

Note that creating the computed column does not create statistics; these statistics are created the first time that the query is optimized, and you can run the next query to display the information about the statistics objects for the Sales.SalesOrderDetail table:

SELECT * FROM sys.stats
WHERE object_id = object_id('Sales.SalesOrderDetail')

The newly created statistics object will most likely be at the end of the list. Copy its name and use the following command to display the details about the statistics object (I’ve used the name of my local object, but you should replace that as appropriate). You can also use "cc" as the name of the object to get the same results. In both cases, the "cc" column should be shown on the Columns field in the density section.

DBCC SHOW_STATISTICS ('Sales.SalesOrderDetail', _WA_Sys_0000000C_2645B050)

Unfortunately, for the automatic matching feature to work, the expression must be exactly the same as the computed column definition. So, if I change the query to UnitPrice * OrderQty, instead of OrderQty * UnitPrice, the execution plan will show an estimated number of rows of 30% again, as this query will demonstrate:

SELECT * FROM Sales.SalesOrderDetail
WHERE UnitPrice * OrderQty > 25000

As mentioned, the computed column provides statistics so the Query Optimizer can try to get you a better execution plan. In addition, you can create an index on the existing computed column to provide a better navigational alternative. Create the following index

CREATE INDEX IX_cc on Sales.SalesOrderDetail(cc)

By running the original SELECT statement again the Query Optimizer will now choose the newly created index and will produce a more efficient plan using an Index Seek/Key Lookup instead of a Clustered Index Scan, as shown next.

Finally, drop the index and computed column you’ve just created:

DROP INDEX Sales.SalesOrderDetail.IX_cc
GO
ALTER TABLE Sales.SalesOrderDetail
DROP COLUMN cc

The Query Optimizer and Contradiction Detection

Jun 1st, 2011

by Benjamin Nevarez.

6 comments

As covered in my book Inside the SQL Server Query Optimizer, contradiction detection is a query rewrite (or tree rewrite?) performed at the simplification phase of the optimization process in which query contradictions are detected and removed. Since these parts of the query are not executed at all, SQL Server saves resources like I/O, locks, memory and CPU, making the query to be executed faster. For example, the Query Optimizer may know that no records can satisfy a predicate even before touching any page of data. A contradiction may be related to a check constraint, or may be related to the way the query is written. I will show you examples of both cases next.

First, I need to find a table with a check constraint in AdventureWorks and, handily, the Employee table has the following check constraint definition:

([VacationHours]>=(-40) AND [VacationHours]<=(240))

This check constraint makes sure that the number of vacation hours is a number between –40 and 240, so when I request

SELECT * FROM HumanResources.Employee
WHERE VacationHours > 80

… SQL Server uses a Clustered Index Scan operator, as shown next

However, if I request all of the employees with more than 300 vacation hours then, because of this check constraint, the Query Optimizer must immediately know that no records qualify for predicate. Run the following code

SELECT * FROM HumanResources.Employee
WHERE VacationHours > 300

As expected, the query will return no records, but this time it will show the following execution planNote that, this time, instead of a Clustered Index Scan, SQL Server is using a Constant Scan operator. Since there is no need to access the table at all, SQL Server saves resources like I/O, locks, memory and CPU, making the query to be executed faster. Now, let’s see what happens if I disable the check constraint

ALTER TABLE HumanResources.Employee NOCHECK CONSTRAINT CK_Employee_VacationHours

This time, running the last query once again uses a Clustered Index Scan operator, as the Query Optimizer can no longer use the check constraint to guide its decisions. Don’t forget to enable the constraint again by running the following statement:

ALTER TABLE HumanResources.Employee WITH CHECK CHECK CONSTRAINT
CK_Employee_VacationHours

The second type of contradiction case is when the query itself explicitly contains a contradiction. Take a look at the next query

SELECT * FROM HumanResources.Employee
WHERE ManagerID > 10 AND ManagerID < 5

In this case there is no check constraint involved; both predicates are valid and each will individually return records, but they contradict each other when they are run together. As a result, the query returns no records and the plan shows again a Constant Scan operator similar to the plan shown previously. This may just look like a badly written query, but remember that some predicates may already be included in, for example, view definitions, and the developer of the query may be unaware of those. For example, in our last query, a view may include the predicate ManagerID > 10 and a developer may call this view using the predicate ManagerID < 5. Since both predicates contradict each other a Constant Scan operator will be used again instead.

Query Optimizer

Query Optimization Research Papers

Statistics on Ascending Keys

The problem

Using trace flag 2389

More Undocumented Query Optimizer Trace Flags

Inside the Query Optimizer Memo Structure

Speaking at the PASS Summit and other Southern California events

Code from my book Inside the SQL Server Query Optimizer

Query Optimization with Denali Columnstore Indexes

Speaking at the PASS Summit 2011

Statistics on Computed Columns

The Query Optimizer and Contradiction Detection

My Book

Recent Posts

Search

Meta

Query Optimizer

The problem

Using trace flag 2389

My Book

Recent Posts

Tags

Search

Meta