• Shortcuts : 'n' next unread feed - 'p' previous unread feed • Styles : 1 2

» Publishers, Monetize your RSS feeds with FeedShow:  More infos  (Show/Hide Ads)


Date: Wednesday, 20 Sep 2006 20:00

After a few months, we're pretty happy with the content and readership we have created.  This is a great way to work more closely with our customers and to give them guidance that helps them be effective using our software.

One thing we have realized, however, is that we'd also like to get our query execution team involved in this effort as well.  So, we're creating a new blog that will cover both teams.  The focus of the blog will remain the same but we'll get additional perspectives from some of our experts on issues like memory tuning, prefetching, locking, that we haven't had as much time to cover so far.

Please join us over at the new blog:

http://blogs.msdn.com/sqlqueryprocessing/default.aspx

Thanks,

Conor

Author: "QueryOptTeam"
Comments Send by mail Print  Save  Delicious 
Date: Friday, 15 Sep 2006 02:46

I've been busy reading the SQL Customer Team's blog.  Lots of good data on how to build a good application in there - I recommend it:

http://blogs.msdn.com/sqlcat/

Thanks,

Conor Cunningham

Author: "QueryOptTeam"
Comments Send by mail Print  Save  Delicious 
Date: Tuesday, 29 Aug 2006 22:56

(2006-09-01 added a paragraph on parallel query plans)

 

In SQL Server, “Statistics Profile” is a mode in which a query is run where you can see the number of invocations of each physical plan operator in the tree.  Instead of running a query and just printing the output rows, this mode also collects and returns per-operator row counts.  Statistics Profile is used by the SQL Query Optimizer Team to identify issues with a plan which can cause the plan to perform poorly.  For example, it can help identify a poor index choice or poor join order in a plan.  Oftentimes, it can help identify the needed solution, such as updating statistics (as in the histograms and other statistical information used during plan generation) or perhaps adding a plan hint.  This document describes how to read the statistics profile information from a query plan so that you can also debug plan issues.

 

A simple example query demonstrates how to retrieve the statistics profile output from a query:

 

use nwind

set statistics profile on

select * from customers c inner join orders o on c.customerid = o.customerid;

 

The profile output has a number of columns and is a bit tricky to print in a regular document.  The key pieces of information that it prints are the plan, which looks like this:

 

StmtText                                                                                               

------------------------------------------------------------------------------------------------------

select * from customers c inner join orders o on c.customerid = o.customerid                          

  |--Hash Match(Inner Join, HASH:([c].[CustomerID])=([o].[CustomerID]),

       |--Clustered Index Scan(OBJECT:([nwind].[dbo].[Customers].[aaaaa_PrimaryKey] AS [c]))          

       |--Clustered Index Scan(OBJECT:([nwind].[dbo].[Orders].[aaaaa_PrimaryKey] AS [o]))             

 

Other pieces of useful information are the estimated row count and the actual row count for each operator and the estimated and actual number of invocations of this operator.  Note that the actual rows and # of executions are physically listed as early columns, while the other columns are listed later in the output column list (so you typically have to scroll over to see them).

 

Rows                 Executes           

-------------------- --------------------

1078                 1                  

1078                 1                  

91                   1                  

1078                 1                  

 

EstimateRows            

------------------------

1051.5834               

1051.5834               

91.0                    

1078.0                  

 

EstimateExecutions      

------------------------

NULL

1.0

1.0

1.0

 

Other fields, such as the estimated cost of the subtree, the output columns, the average row size, also exist in the output (but are omitted for space in this document).

 

Note: The output from statistics profile is typically easiest to read if you set the output from your client (Query Analyzer or SQL Server Management Studio) to output to text, using a fixed-width font.  You can then see the columns pretty easily and you can even move the results into a tool like Excel if you want to cluster the estimates and actual results near each other by rearranging the columns (SSMS also can let you do this).

 

There are a few key pieces of information needed to understand the output from Statistics profile.  First, query plans are generally represented as trees.  In the output, children are printed below their parents and are indented:

StmtText                                                                                               

------------------------------------------------------------------------------------------------------

select * from customers c inner join orders o on c.customerid = o.customerid                           

  |--Hash Match(Inner Join, HASH:([c].[CustomerID])=([o].[CustomerID]),

       |--Clustered Index Scan(OBJECT:([nwind].[dbo].[Customers].[aaaaa_PrimaryKey] AS [c]))          

       |--Clustered Index Scan(OBJECT:([nwind].[dbo].[Orders].[aaaaa_PrimaryKey] AS [o]))             

 

In this example, the scan of Customers and Orders are both below a hash join operator.  Next, the “first” child of the operator is listed first.  So, the Customers Scan is the first child of the hash join.  Subsequent operators follow, in order.  Finally, query execution plans are executed in this “first” to “last” order.  So, for this plan, the very first row is returned from the Customers table.  (A more detailed discussion of operators will happen later in the article).  Notice that the output from the graphical showplan is similar but slightly different:

 

(see attachment tree.jpg).

 

In this tree representation, both Scans are printed to the right on the screen, and the first child is above the other operators.  In most Computer Science classes, trees are printed in a manner transposed from this:

 

     Hash Join

     /       \

 Customers  Orders

 

The transposition makes printing trees in text easier.  In this classical view, the tree is evaluated left to right with rows flowing bottom to top. 

 

With an understanding of the nuances of the query plan display, it is possible to understand what happens during the execution of this query plan.  The query returns 1078 rows.  Not coincidentally, there are also 1078 orders in this database.  Since there’s a Foreign Key relationship between Orders and Customers, it requires that a match exist for each order to each customer.  So, the 91 rows in Customers match the 1078 rows in Orders to return the result.

 

The query estimates that the join will return 1051.5834 rows.  First, this is a bit less than the actual (1078) but is not a substantial difference.  Given that the Query Optimizer is making educated guesses based on sampled statistical information that may itself be out-of-date, this estimate is actually pretty good.  Second, the number is not an integer because we use floating point for our estimates to improve accuracy on estimates we make.  For this query, the number of executions is 1 for both the estimate and actual.  This won’t always be the case, but it happens to be true for this query because of the way hash joins work.  In a hash join, the first child is scanned and a hash table is built.  Once the hash join is built, the second child is then scanned and each row probes the hash table to see if there is a matching row. 

 

Loops join does not work this way, as we’ll see in a slightly modified example. 

 

select * from customers c with (index=1) inner loop join orders o with (index=1) on c.customerid = o.customerid

 

In this example, I’ve forced a loop join and the use of clustered indexes for each table.  The plan now looks like this:

 

StmtText                                                        

-----------------------------------------------------------------

select * from customers c with (index=1) inner loop join orders o

  |--Nested Loops(Inner Join, WHERE:([nwind].[dbo].[Orders].[Cust

       |--Clustered Index Scan(OBJECT:([nwind].[dbo].[Customers].

       |--Table Spool                                           

            |--Clustered Index Scan(OBJECT:([nwind].[dbo].[Orders

 

Beyond the different join algorithm, you’ll notice that there is now a table spool added to the plan.  The spool is on the second child (also called the “inner” child for loops join because it is usually invoked multiple times).  The spool scans rows from its child and can store them for future invocations of the inner child.  The actual row count and execution count from the statistics profile is a bit different from the previous plan:

 

Rows                 Executes             

-------------------- --------------------

1078                 1                   

1078                 1       <--- Loop Join

91                   1       <--- Scan of Customers

98098                91      <--- Spool

1078                 1       <--- Scan of Orders

 

In this plan, the second child of the loop join is scanned 91 times returning a total number of 98098 rows.  For the actual executions, the total number of rows is to sum of all invocations of that operator, so it is 91*1078=98098.  This means that the inner side of this tree is scanned 91 times.  Nested Loops joins require rescans of the inner subtree (Hash Joins do not, as you saw in the first example).  Note that the spool causes only one scan of the Orders table, and it only has one execution as a result.  It isn’t hard to see that there are far more rows touched in this plan compared to the hash join, and thus it shouldn’t be a huge surprise that this plan runs more slowly.

 

Note: When comparing the estimated vs. actual number of rows, it is important to remember that the actual counts need to be divded by the actual number of executions to get a value that is comparable to the estimated number of rows returned.  The estimate is the per-invocation estimate.

 

As a more complicated example, we can try something with a few more operators and see how things work on one of the TPC-H benchmark queries (Query 8, for those who are interested, on a small-scale 100MB database):

 

SELECT O_YEAR,

       SUM(CASE      WHEN   NATION = 'MOROCCO'

                     THEN   VOLUME

                     ELSE   0

                     END) / SUM(VOLUME)   AS MKT_SHARE

FROM   (      SELECT datepart(yy,O_ORDERDATE)          AS O_YEAR,

                     L_EXTENDEDPRICE * (1-L_DISCOUNT)  AS VOLUME,

                     N2.N_NAME                         AS NATION

              FROM   PART,

                     SUPPLIER,

                     LINEITEM,

                     ORDERS,

                     CUSTOMER,

                     NATION N1,

                     NATION N2,

                     REGION

              WHERE  P_PARTKEY     = L_PARTKEY AND

                     S_SUPPKEY     = L_SUPPKEY AND

                     L_ORDERKEY    = O_ORDERKEY AND

                     O_CUSTKEY     = C_CUSTKEY AND

                     C_NATIONKEY   = N1.N_NATIONKEY AND

                     N1.N_REGIONKEY       = R_REGIONKEY AND

                     R_NAME        = 'AFRICA' AND

                     S_NATIONKEY   = N2.N_NATIONKEY AND

                     O_ORDERDATE   BETWEEN '1995-01-01' AND '1996-12-31' AND

                     P_TYPE        = 'PROMO BURNISHED NICKEL' AND

                     L_SHIPDATE    >= CONVERT(datetime,(1156)*(30),121) AND                      L_SHIPDATE       <  CONVERT(datetime,((1185)+(1))*(30),121)     

       )      AS     ALL_NATIONS

GROUP  BY     O_YEAR

ORDER  BY     O_YEAR

 

As the queries get more complex, it gets harder to print them in a standard page of text.  So, I’ve truncated the plan somewhat in this example.  Notice that the same tree format still exists, and the main operators in this query are Scans, Seeks, Hash Joins, Stream Aggregates, a Sort, and a Loop Join.  I’ve also included the actual number of rows and actual number of executions columns as well.

 

Rows  Executes   Plan

0      0 Compute Scalar(DEFINE:([Expr1028]=[Expr1026]/[Expr1027]))             

2      1   |--Stream Aggregate(GROUP BY:([Expr1024]) DEFINE:([Expr1026]=SUM([par

2      1        |--Nested Loops(Inner Join, OUTER REFERENCES:([N1].[N_REGIONKEY]

10     1             |--Stream Aggregate(GROUP BY:([Expr1024], [N1].[N_REGIONKEY

1160   1             |    |--Sort(ORDER BY:([Expr1024] ASC, [N1].[N_REGIONKEY] A

1160   1             |         |--Hash Match(Inner Join, HASH:([N2].[N_NATIONKEY

25     1             |              |--Clustered Index Scan(OBJECT:([tpch100M].[

1160   1             |              |--Hash Match(Inner Join, HASH:([N1].[N_NATI

25     1             |                   |--Index Scan(OBJECT:([tpch100M].[dbo].

1160   1             |                   |--Hash Match(Inner Join, HASH:([tpch10

1000   1             |                        |--Index Scan(OBJECT:([tpch100M].[

1160   1             |                        |--Hash Match(Inner Join, HASH:([t

1160   1             |                             |--Hash Match(Inner Join, HAS

1432   1             |                             |    |--Hash Match(Inner Join

126    1             |                             |    |    |--Clustered Index

0      0             |                             |    |    |--Compute Scalar(D

224618 1             |                             |    |         |--Clustered I

0      0             |                             |    |--Compute Scalar(DEFINE

45624  1             |                             |         |--Clustered Index

15000  1             |                             |--Index Scan(OBJECT:([tpch10

2      10            |--Clustered Index Seek(OBJECT:([tpch100M].[dbo].[REGION].[

 

I’ll point out a few details about the statistics profile output.  Notice that the Compute Scalars (also called Projects) return zero for both columns.  Since Compute Scalar always returns exactly as many rows as it is given from its child, there isn’t any logic to count rows again in this operator simply for performance reasons.  The zeros can be safely ignored, and the values for its child can be used instead.  Another interesting detail can be seen in the last operator in this printout (the Seek into the Region table).  In this operator, there are 10 executions but only 2 rows returned.  This means that even though there were 10 attempts to find rows in this index, only two rows were ever found.  The parent operator (the Nested Loops near the top) has 10 rows coming from its first (left) child and only 2 rows output by the operator, which matches what you see in the seek.  Another interesting tidbit can be found if you look at the estimates for the Seek operator:

 

Est.# rows  Est. #executes

1.0                                           20.106487

 

The SQL Server Query Optimizer will estimate a minimum of one row coming out of a seek operator.  This is done to avoid the case when a very expensive subtree is picked due to an cardinality underestimation.  If the subtree is estimated to return zero rows, many plans cost about the same and there can be errors in plan selection as a result.  So, you’ll notice that the estimation is “high” for this case, and some errors could result.  You also might notice that we estimate 20 executions of this branch instead of the actual 10.  However, given the number of joins that have been evaluated before this operator, being off by a factor of 2 (10 rows) isn’t considered to be too bad.  (Errors can increase exponentially with the number of joins).

 

SQL Server supports executing query plans in parallel.  Parallelism can add complexity to the statistics profile output as there are different kinds of parallelism that have different impacts on the counters for each operator.  Parallel Scans exist at the leaves of the tree, and these will count all rows from the table into each thread even through each thread only returns a fraction of the rows.  The number of executions (the second column in the output) will also have 1 execution for each thread.  So, it is typical to just divide the number of threads into the total number of rows to see how many rows were actually returned by the table.  Parallel zones higher in the tree usually work the same way.  These will have N (where N is the degree of parallelism) more executions than the equivalent non-parallel query.  There are a few cases where we will broadcast one row to multiple threads.  If you examine the type of the parallelism exchange operation, you can identify these cases and notice that one row becomes multiple rows through the counts in the statistics profile results.

 

The most common use of the statistics profile output is to identify areas where the Optimizer may be seeing and using incomplete or incorrect information.  This is often the root cause of many performance problems in queries.  If you can identify areas where the estimated and actual cardinality values are far apart, then you likely have found a reason why the Optimizer is not returning the “best” plan.  The reasons for the estimate being incorrect can vary, but it can include missing or out-of-date statistics, too low of a sample rate on those statistics, correlations between data columns, or use of operators outside of the optimizer’s statistical model, to name a few common cases.

 

Future posts will cover some of the details associated with tracking down each of these cases.

Attached Media: image/jpeg ( 54 ko)
Author: "QueryOptTeam"
Comments Send by mail Print  Save  Delicious 
Date: Wednesday, 02 Aug 2006 00:19

A quick post for today.  It's actually more of a storage engine concept, but you'd be surprised how much this can help in understanding update plans.  So, as I'm re-reading some of these to refresh my memory, I'll give you the chance to read along, so to speak.

For those interested in how and why locking works, there's a few various texts you can read.  "Transaction Processing: Concepts and Techniques" by Jim Gray and Andreas Reuter is a book you should read first.  It covers lots of things, but Part 4 (in my edition) is the section on concurrency and isolation levels.

So, after you're done with that short paperback <g>, you should read David Lomet's paper on some of the more interesting details of key range locking in practical, scalable implementations.  It's called "Key Range Locking Strategies for Improved Concurrency".  You can get it here: http://citeseer.ist.psu.edu/lomet93key.html.  While this isn't exactly what SQL Server does, it's close enough to give you a pretty good idea of what's happening under the covers.

I hope to post up a few examples to show how you can use the DMVs with a few of our queries to take a look at the locking behavior.

Enjoy!

Conor Cunningham

 

Author: "QueryOptTeam"
Comments Send by mail Print  Save  Delicious 
Date: Saturday, 22 Jul 2006 02:08

If you read the Books Online page describing the UPDATE STATISTICS command, you will see that there are some undocumented options.

 

UPDATE STATISTICS table | view
    [
        {
            { index | statistics_name }
          | ( { index |statistics_name } [ ,...n ] )
                }
    ]
    [    WITH
        [
            [ FULLSCAN ]
            | SAMPLE number { PERCENT | ROWS } ]
            | RESAMPLE
            | <update_stats_stream_option> [ ,...n ]
        ]
        [ [ , ] [ ALL | COLUMNS | INDEX ]
        [ [ , ] NORECOMPUTE ]
    ] ;

<update_stats_stream_option> ::=
    [ STATS_STREAM = stats_stream ]
    [ ROWCOUNT = numeric_constant ]
    [ PAGECOUNT = numeric contant ]

 

<update_stats_stream_option>

    This syntax is for internal use only and is not supported. Microsoft reserves the right to change this syntax at any time.

 

There is a very good reason why these options are undocumented. They are meant for testing and debugging purposes, and should never ever be used on production systems.

 

However, these options can also be extremely helpful to create examples and sample scripts to demonstrate various features and behaviors of the Query Optimizer and the related query plan shapes. We decided to explain what ROWCOUNT and PAGECOUNT do, so that to be able to use these commands in examples we’ll be posting in some future. Feel free to use these options on development systems for experimental and educational purposes, but please do not play with fire and do not use them in production!

 

As the name of these options suggest, ROWCOUNT and PAGECOUNT alter the internal metadata of the specified table or index by overriding the counters containing the row and page counts of the object. These counters are in turn read by the Query Optimizer when processing queries that access the table and/or index in question. These commands can basically cheat the Optimizer into thinking that a table or index is extremely large.

 

SQL Server’s Query Optimization process is structured in multiple stages. Further optimization stages consider a progressively larger and more sophisticated set of possible tree transformations and query optimizations. Later stages of optimization are only entered when the estimated cost of the query is sufficiently high, in order to avoid wasting precious CPU cycles against simple queries that do not need that level of sophistication anyway. The multiple optimization stages are a mean to produce efficient query plans without consuming excessive amounts of CPU. Typically, in order to make the Optimizer “think” a lot and enter these later stages it is necessary to have big tables with a large number of rows and pages, which in turn take time and space to populate. Using ROWCOUNT and PAGECOUNT allows us to exercise these code paths with relatively simple scripts that do not require an extremely complex setup phase.

 

Here is an example. When running this simple script on your SQL 2005 instance you will likely see a different query plan for the two selects before and after updating the statistics. The recompile option is used to ensure that the query plans are regenerated. From the statistics profile, you’ll also see very different estimated row counts and consequently costs.

 

use tempdb

go

 

create table t1(i int, j int)

go

 

create table t2(h int, k int)

go

 

set statistics profile on

go

 

select distinct(i) from t1

go

 

select * from t1, t2 where i = k order by j + k

go

 

update statistics t1 with rowcount = 10000, pagecount = 10000

update statistics t2 with rowcount = 100000, pagecount = 100000

go

 

select distinct(i) from t1 option (recompile)

go

 

select * from t1, t2 where i = k order by j + k option (recompile)

go

 

Enjoy!

Stefano

Author: "QueryOptTeam"
Comments Send by mail Print  Save  Delicious 
Date: Saturday, 15 Jul 2006 02:30

Not everyone knows that query level hints (like loop join) will impact the entirety of a DML query plan. This includes foreign key validation and indexed view maintenance.

 

Let us look at an example with two tables involved in a foreign key constraint.

 

use tempdb

go

 

create table department(deptid int primary key clustered, deptname varchar(10))

go

 

create table employee(empid int primary key clustered, empname varchar(10), deptid int references department(deptid))

go

 

insert department values(1, 'Optimizer')

go

 

At first glance, it might seem useless to provide a join hint for a scalar insert - like when inserting a row to the employee table – because the query contains no joins. However, this can make sense in presence of foreign key validations, because the Optimizer will automatically augment the query plan with a join for the purpose of validating the constraint. For example, this insert statement here

 

insert employee select 1 empid, 'Stefano' empname, 1 deptid option (merge join)

 

will produce a plan with a merge join between the employee and department tables. The join will enforce that the value of the deptid column actually exists in the primary table, department. The “Assert” operator will raise an error if a matching row is not found.

 

  |--Assert

       |--Merge Join

            |--Clustered Index Insert(employee)

            |--Clustered Index Scan(department)

 

Unfortunately, this technique is restricted to only query (vs. table) level hints, so it's not possible for example to force the indexes being used when accessing the other table involved in the constraint (department in the example). Also, TSQL syntax does not allow specifying query level hints for scalar inserts, like "insert table values...", but the easy workaround is to rewrite the statement as "insert select" like in the example. Update and delete statements do regularly accept query level hints.

 

update employee set empname = 'Conor', deptid = 2 where empid = 1 option (loop join)

 

  |--Assert

       |--Nested Loops

            |--Clustered Index Update(employee)

            |--Clustered Index Seek(department)

 



 

Let us now look at slightly more complex example with an indexed view.


use tempdb

go

 

SET ANSI_NULLS ON

SET ANSI_PADDING ON

SET ANSI_WARNINGS ON

SET CONCAT_NULL_YIELDS_NULL ON

SET NUMERIC_ROUNDABORT OFF

SET QUOTED_IDENTIFIER ON

go

 

create table t1(i int, j int)

go

 

create table t2(h int, k int)

go

 

create view v with schemabinding as

select i, h, count_big(*) c from dbo.t1, dbo.t2

where j = k

group by i, h

go

 

create unique clustered index v_ih on v(i, h)

go

 

The changes to either table t1 or t2 need to be propagated to the indexed view v1, in order to keep it consistent at all times. Since the indexed view contains a join and an aggregation in its definition, the Optimizer will automatically augment DML query plans against t1 or t2 with joins and aggregations. Query level hints can be used to influence the join and/or grouping strategy employed by the Optimizer in the query plan.

 

insert into t1 select 1, 2 option (hash join, hash group)

 

  |--Sequence

       |--Table Spool

       |    |--Table Insert(t1)

       |--Clustered Index Update(v)

            |--Collapse

                 |--Sort

                      |--Compute Scalar

                           |--Hash Match(Right Outer Join)

                                |--Clustered Index Scan(v)

                                |--Hash Match(Aggregate)

                                     |--Hash Match(Inner Join)

                                          |--Table Spool

                                          |--Table Scan(t2)

 

insert into t1 select 1, 2 option (loop join, order group)

 

  |--Sequence

       |--Table Spool

       |    |--Table Insert(t1)

       |--Clustered Index Update(v)

            |--Collapse

                 |--Sort

                      |--Compute Scalar

                           |--Nested Loops(Left Outer Join)

                                |--Stream Aggregate

                                |    |--Sort

                                |         |--Nested Loops(Inner Join)

                                |              |--Table Spool

                                |              |--Table Scan(t2)

                                |--Clustered Index Seek(v)

 

Needless to say, query hints are fully documented in Books Online – look for the “Query Hint (Transact-SQL)” topic.

 

Ciao,

Stefano

Author: "QueryOptTeam"
Comments Send by mail Print  Save  Delicious 
Date: Saturday, 08 Jul 2006 00:45

A question we are frequently asked is what happens when an update statement assigns a column to its same current value. For example,

 

use tempdb

go

 

create table t(i int, cc as i + 1)

create index t_cc on t(cc)

go

 

insert into t values(1)

go

 

update t set i = 1

go

 

update t set i = i

go

 

Columns do get updated even if the value does not change. However, to be honest, i wouldn't worry too much about it.
The runtime cost for updating a row is roughly equal to

a) locating the row in the heap or B-Tree

b) locking the row

c) changing the updated column values

d) logging the change.

For updates to columns that fit in the 8Kb page, i don't think that avoiding part of the copy would make too much of a difference. Realistically, performing a comparison to tell what changed with memcmp would roughly cost as much as changing the value with memcpy. And this cost would surely be overshadowed by a) + b) + d). Updates to columns that don't fit in the 8Kb page are inherently slower, and i think it is up to the application to avoid making unnecessary changes to these.

Now a), b), c) and d) need to be performed for every index carrying one or more columns being modified. So a major factor for the runtime cost of an update query is the number of nonclustered indexes that need to be maintained. In SQL 2005 we introduced an optimization to skip nonclustered index maintenance if none of the updated columns stored in the index actually changed. The reasoning is that running the comparison for only the modified columns stored in one or more nonclustered indexes introduces a runtime overhead that is very small, and surely significantly lower than a), b) and d). Given that columns stored in an index are typically pretty small in size, it is very easy to break even if the optimization actually saves a small minority of nonclustered index row updates. The optimization does not apply to the clustered index, as we want to ensure to always exclusively lock the affected rows even if no columns are really changing.

You can see the new optimization in action by comparing the statistics profile output for one of the update statements in the previous example in SQL 2000 and 2005 (see attached image).


set statistics profile on
go

update t set i = i

go

In SQL 2000, the lack of the optimization leads to updating the nonclustered index even if the value is not changing.
 

In the SQL 2005 plan, it is possible to appreciate

- a “Compute Scalar” operator that compares the current value and new value of the column being modified

- a new filter operator that on a row by row basis will determine whether the nonclustered index is being affected or not

- the fact that nonclustered index maintenance is now bypassed

 

This new SQL 2005 optimization allows to better address the problem of maintaining a diverse set of columns across multiple recurring update statements against a certain table. In SQL 2000 there was a tradeoff between building dynamic SQL statements and possibly incur in frequent compilations, to only maintain the modified columns vs. using a parameterized and standard statement that updated all the columns, but would also maintain all the nonclustered indexes all the time. Like i said before, special precautions should still be taken for columns that don't fit the 8Kb page limit.

 

Ciao,

Stefano

Attached Media: image/x-png ( 38 ko)
Author: "QueryOptTeam"
Comments Send by mail Print  Save  Delicious 
Date: Friday, 02 Jun 2006 02:16

We've been hard at work up here on a little prototype for you guys to try.  This attachment is a basic automatic indexing solution built on top of SQL Server 2005 using the Missing Index DMVs that we discussed in our previous blog post:

http://blogs.msdn.com/queryoptteam/archive/2006/04/06/570176.aspx

Effectively, this will periodically determine top index candidates for your workload.  It currently runs in a recommendation mode, but you can also have it run fully automated if you uncomment a line in the file.

We'd like to ask you guys to give it a try and let us know what you think.  We're interested in learing about the kinds of workloads that it can handle and the kinds of workloads that it can't.  We've played with this idea on a few workloads that we have, but we'd like to use this forum to experiment with how we get feedback from our customers to better serve you in the future.

It's also just cool, so give it a try ;).

Legal Mumbo-Jumbo - these are scripts, and you can do with them as you please, but please don't blame us if it breaks your stuff.  It should work alright, but just be aware that we can't support these scripts to the level that we do for our regular product.  We may be able to ship a similar feature in a future release based on the feedback we recieve.

Enjoy!

Jianjun and Conor

Attached Media: application/x-zip-compressed ( 6 ko)
Author: "QueryOptTeam"
Comments Send by mail Print  Save  Delicious 
Date: Thursday, 04 May 2006 02:56

A question came in about when to use the FAST hint.

If you remember from the row goals post (http://blogs.msdn.com/controlpanel/blogs/posteditor.aspx?SelectedNavItem=Posts&sectionid=6255&postid=564912), it is possible to get a different plan based on the row goal (for example, you can get a nested loops plan instead of a merge/hash join if you have a low enough row goal).  TOP is a common reason to get a row goal in the optimization process.  TOP queries can also be used to page through a result set using a series of queries (if you remember the last row you saw + a few other conditions).

The FAST hint is a way to get the plan you would get with TOP but without the hard limit on the number of rows being returned.  So, if you want to get one "page" of rows quickly, you can use FAST to enable that.  If you want the ability to continue reading from the result set, you can use the FAST hint to get that "give me rows quickly" plan. 

Typically, ISVs that do paging themselves without server-side cursors may consider this hint.  In general, I wouldn't recommend that you use it unless you have a good reason to do so.  If you can ignore it, as with all hints, please do so.  If you have really specific requirements on how your application should work, then you can consider it as a technique that picks more loops joins and minimizes stop-and-go operators, where possible.

Thanks,

Conor

Author: "QueryOptTeam"
Comments Send by mail Print  Save  Delicious 
Date: Wednesday, 03 May 2006 02:00

SQL is a declarative language that returns multi-sets (sets allowing duplicates) of rows.  The operations exposed in SQL, such as join, filter, group by, and project, do not inherently have any ordering guarantees.  ANSI SQL does expose an ORDER BY clause for the top-most SELECT scope in a query, and this can be used to return rows in a presentation order to the user (or to a cursor so that you can iterate over the results of query).  This is the only operation in ANSI SQL that actually guarantees row order.

 

Microsoft SQL Server provides additional ordering guarantees beyond ANSI, mostly for backwards-compatibility with previous releases of the product.  For example, variable assignment in the top-most SELECT list when an ORDER BY is specified is done in the presentation order of the query. 

Example:

SELECT @a = @a + col FROM Table ORDER BY col2;

 

SQL Server also contains a non-ANSI operator called TOP.  TOP allows you to limit a result set to a certain number or percentage of the result set.  If an ORDER BY is used in the same scope, it qualifies rows based on the ORDER BY.  So, TOP 1 … ORDER BY col will return the “first” row from that result set based on the order by list.  However, SQL Server does not guarantee that the rows will be returned in that order from the intermediate result set.  It only guarantees which rows actually qualify.  You’d need to put an ORDER BY at the top of the query to guarantee the output order returned to the client.  (In a previous blog entry, I noted how SQL 2005 actually doesn’t bother processing TOP 100 PERCENT … ORDER BY since it is “meaningless” under this definition).

 

Other operations in SQL Server also have this “which rows qualify” semantic.  ROW_NUMBER, RANK, DENSERANK, and NTILE contain an OVER clause in which an ORDER BY can be specified.  This order by guarantees the output of the operation, but not the order in which the rows are output.  So, the following is valid output for the row_number query – the function outputs row values as if it had been evaluated in a specific order.

 

SELECT col2, ROW_NUMBER() OVER (ORDER BY col1) FROM T

Col2  Col1 row_num

1          1          1

3          3          3

2          2          2

 

Now, in practice, we don’t currently generate a plan that would return rows in this order for this specific query.  However, different query plans for the same query can return rows in different order, so it is important to understand what is guaranteed and what is not.  When you build an assumption in your SQL application during development about one query plan, then deploy it and a customer with their own data in the database gets a different plan, you can very quickly learn about this dependency the hard way.  (A more plausible possibility for this example is that we could assign the row numbers backwards if we knew the exact rowcount from a previously completed operation in the SQL query plan).

 

Essentially, the SQL Server Query Optimizer is guaranteeing that the internal operator in the query tree will process its input in a particular order.  There is no corresponding guarantee that the output of that operator will imply that the next operator in the query tree is performed in that order.  The reordering rules can and will violate this assumption (and do so when it is inconvenient to you, the developer ;).  Please understand that when we reorder operations to find a more efficient plan, we can cause the ordering behavior to change for intermediate nodes in the tree.  If you’ve put an operation in the tree that assumes a particular intermediate ordering, it can break.

 

Thanks,

 

Conor

Author: "QueryOptTeam"
Comments Send by mail Print  Save  Delicious 
Date: Tuesday, 18 Apr 2006 19:31

Today's topic is a general primer on something that is called "local-global aggregation".  Effectively, this is a technique to allow you to take a query containing joins and group bys and perform the group by partially "before" the joins.  This can dramatically reduce the number of rows that a query has to process to return a result, and therefore it is a very powerful operation.  This technique is also quite useful to split a grouping operation into something that can be done in parallel.  That obviously can also speed your query as well.

I hope to put something more formal together soon, work permitting, but here is an introduction that you can read in the meantime:

http://citeseer.ist.psu.edu/jaedicke97framework.html

Thanks,

Conor

Author: "QueryOptTeam"
Comments Send by mail Print  Save  Delicious 
Date: Thursday, 13 Apr 2006 05:13

I ran into one of my colleagues in the hallway the other day from another part of the product, and he told me about the blog that the Programmability team has been doing.

http://blogs.msdn.com/sqlprogrammability/

Effectively this is the compliment in the expressability story to what we do in queries.  So, there are a lot of details about various functions, how T-SQL works in more detail, etc.  If you need help with those issues, please check out their site.

There are some very interesting areas where the two intersect, actually, and I'll try to get some entries together about them in the future (for example, user-defined table-valued functions).

Enjoy!

Conor

Author: "QueryOptTeam"
Comments Send by mail Print  Save  Delicious 
Date: Wednesday, 12 Apr 2006 23:28

The Optimizer model makes several assumptions when making plan choice decisions.  These decisions can be false for particular queries and data sets, and sometimes this can cause plan issues.  One such problem is called “The Sorted Seek Problem” by the Optimizer Team, and it affects plan selection, usually between clustered index or heap scan plans and bookmark lookup plans.

 

When costing a series of bookmark lookup operations (for a heap) or index seek operations (for an index), the costing code will effectively treat these as a series of random I/Os.  These are much more expensive than sequential I/Os because the disk arm needs to be moved and the disk needs to spin around to find the right sector(s).  When the correct page is found, it is loaded into the buffer pool and the engine will cache it for future references.  The costing code also understands, on average, how often a page is likely to be found on subsequent operations in the cache, and it costs these accesses much more cheaply than the original access.

 

When a query needs to perform lookups into an access method, the costing code makes the assumption that rows are uniformly distributed over the pages in the table/index.  Under this assumption, effectively each row that is accessed is expensive because we assume that it needs to be loaded from disk.  (At some point, all pages may be in the buffer pool and no longer require the expensive random I/O operation to load a different record from a previously accessed page).

 

In practice, rows are usually not randomly distributed.  In fact, many common user patterns will insert rows in physically clustered order.  For example, you likely would insert all of the order details for an order at the time that the order was created.  These could end up clustered on a very few data pages.  As such, a plan that does a bookmark or index lookup into this structure may complete more quickly than the costing model has forecast.  As a result, the Query Optimizer may pick a different plan that runs more slowly for the customer’s installation. 

 

To be fair, there are a number of scenarios where the rows are uniformly distributed, so they would be broken under a different assumption.  In the future, we may be able to provide additional features to find and fix such problems for customers.  Today, your best option in such situations is to use query hints to force the index plan if you know that you have data that is physically clustered.

 

The following sanitized customer example demonstrates this scenario in more detail.  The table is contains about 80 columns and 5.5 million rows.  In the query, the filter qualifies just over 21,000 rows. 

 

SELECT * FROM CustTable  WHERE col='someconstvalue'

 

  |--Parallelism(Gather Streams)

       |--Table Scan(OBJECT:(CustTable), WHERE:(col=’someconstvalue’))

 

Table ‘CustTable’. Scan count 3, logical reads 416967, physical reads 22, read-ahead reads 413582, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

Completed in 3 minutes 9 seconds

 

SELECT * FROM CustTable with (index=idxoncol) WHERE col='someconstvalue'

  |--Nested Loops(Inner Join, OUTER REFERENCES:([Bmk1000], [Expr1005]) WITH UNORDERED PREFETCH)

       |--Index Seek(OBJECT:(idxoncol), SEEK:(col=’someconstvalue’) ORDERED FORWARD)

       |--RID Lookup(OBJECT:(CustTable), SEEK:([Bmk1000]=[Bmk1000]) LOOKUP ORDERED FORWARD)

 

Table 'CustTable'. Scan count 1, logical reads 21167, physical reads 387, read-ahead reads 1354, lob logical reads 0, lob physical reads 0, lob read-ahead reads 0.

Completed in 11 seconds

 

The first query is the original user query, and the default plan picked is a parallel scan of the base table, applying the filter as a pushed non-SARGable predicate into the scan.  It takes over 3 minutes to complete. The second plan uses an index hint to force a bookmark lookup plan.  It completes in 11 seconds.  If you assume that a random disk seek takes approximately 10 ms, you can’t do more than 100 in a second.  For this query, 21,000 seeks would probably take over 3 minutes to do if each was a random I/O against a single disk.  Therefore, there are likely fewer than 21,000 random I/Os happening.  We can see this from the statistics I/O output – there are only 387 + 1354 actual page reads in the query.

 

The actual data distribution is not uniform.  In fact, it is heavily physically grouped.  I ran a query that counted the physical row position in the heap and then filtered out the rows that qualified in this query.  The rows should be somewhat randomly distributed through the set of rows to match the uniformity assumption.  I copied this output into Excel and charted it:

 

[see attachment] 

 

(The pre-filter row number is the y-axis, and the post-filter row number is the x-axis).

 

As you can see, the rows are very clustered on the disk.  As such, many of the rows used in the bookmark lookups are found on pages that are already loaded into the buffer pool from previous I/Os.  This significantly speeds up the query. 

 

The recomendation for these cases is to use query hints if this is a significant issue for your query.

 

Enjoy,

 

Conor

Attached Media: image/jpeg ( 49 ko)
Author: "QueryOptTeam"
Comments Send by mail Print  Save  Delicious 
Date: Tuesday, 11 Apr 2006 19:21

I'd like to point you to a white paper that Eric, one of our program managers, did on Indexed Views in SQL 2005.  This logic mostly applies to the Enterprise Edition of our product.

http://www.microsoft.com/technet/prodtechnol/sql/2005/impprfiv.mspx

This white paper focuses on the functionality in our product.  If you have questions or things that we can make clearer, please let us know and we'll roll them up into the next revision of this (that goes for any of our published works, btw).

I'll try to put together some additional literature on indexed views/materialized views from the academic literature, as this is a topic that can take some time to digest.

Thanks,

Conor

Author: "QueryOptTeam"
Comments Send by mail Print  Save  Delicious 
Date: Thursday, 06 Apr 2006 23:10

I saw a post in one of the newsgroups today that referenced a piece of information Microsoft published on how the Optimizer makes decisions about remoting certain operations.

http://msdn.microsoft.com/library/default.asp?url=/library/en-us/optimsql/odp_tun_1a_6oxf.asp

It's slightly out-of-date, and I'll work on trying to get it updated.  Specifically, SQL 2005 will remote uniqueidentifiers (and it will support statistics over them as well).  We'll remote queries from SQL 2005 to SQL 2000 that contain filters comparing columns to constant uniqueidentifier values as well.

We published a research paper last year on how the Distributed Query feature works in more detail.  While it does not cover every practical detail of the implementation, you may find it as an interesting reference if you use distributed queries.

http://citeseer.ist.psu.edu/732761.html

If you have other remoting questions/problems, please post comments on them and we'll see if we can get them answered for you.

Thanks,

Conor

Author: "QueryOptTeam"
Comments Send by mail Print  Save  Delicious 
Date: Thursday, 06 Apr 2006 21:29

There are many cases where the database administrator does not control the queries being submitted of the system.  As a result, the physical database design is often not tuned as well as it could be.  In a number of actual customer cases where we investigated performance issues with them, we’ve found that this can often be the an effective way to improve performance.

 

Some reasons indexes are helpful in a deployed system:

  1. To pre-materialize a sort over the data
  2. To enable singleton lookups (seeks) for particular values
  3. To reduce locking requirements caused by scans
  4. To reduce memory requirements caused by hash joins

 

The first two are more generally understood benefits.  You can avoid a sort in your plan with (1) and you can avoid scans with (2).  As long as the update cost to maintain these indexes is acceptable, then you can improve select query performance with an index.

 

The third issue, locking, is a problem in many applications about which there isn’t really a lot written.  Some applications are “bound” on how many locks they take.  One example could be a billing application with a number of small queries that access individual (or a small number) of rows but have many, many such queries concurrently.  If the query plans chosen are all seeks, then shared or exclusive locks are likely only taken on the rows being specifically accessed/changed in the query results.  However, if one plan changes to be a scan instead of a seek, the number of locks will increase dramatically.  These locks may also be held for longer (depending on the isolation level), since the query may be running longer as well.  An index can improve the performance of such an application because it improves overall query throughput for many concurrent users.

 

Memory contention is another throughput-related issue that can cause problems when an application runs with many concurrent connections.  In SQL Server, queries reserve memory for the duration of their execution.  This prevents some queries from failing on a memory allocation after they have completed only a portion of the query.  If the system does not have any more memory to give, not-yet-started queries will be blocked and wait for previous queries to complete (and release their memory reservations).  In some applications, the total system throughput is limited by the available memory necessary to enable operations like hash joins. 

 

Memory contention is most likely a problem for scaled applications running on 32-bit hardware that use a lot of memory at peak load.  While Microsoft Windows does have a mechanism called AWE that enables a process to use more than the normal maximum memory (usually 2 GB), that mechanism is only really useful to store pages from the database in memory.  Internal memory consumers, such as the Query Optimizer and Query Execution, are limited to the memory available in the virtual address space (usually 2 GB minus whatever is used for the database page buffer pool and other internal caches/memory consumers).  This can constrain systems that have few indexes but many queries requiring joins without backing indexes because a hash join is often a good choice for the Optimizer.  Additionally, the optimizer does not pick different plan shapes based on system load in SQL Server 2005.  So, creating an index can cause the system to pick loops joins or merge joins in cases where hash joins would be picked otherwise.  Creating an index or two on such a system can reduce memory contention and improve overall system throughput.

 

SQL Server has long shipped a program to help with physical database design called the Index Tuning Wizard (and now the Database Tuning Advisor in SQL Server 2005).  This can help find a reasonably optimal index set for a set of queries.  It works by running the Optimizer with a series of “what if” scenarios and evaluating the cost of the plan the optimizer picked in each case.  It then reasons about the best set of indexes to match the workload.

 

There is also a newer mechanism that you can use in SQL Server 2005 that compliments the existing Database Tuning Advisor Tool.  It does not require that you pre-identify a workload, and it is integrated into the engine and runs as part of the regular operation of the server (you do not need to run anything).  It does not do as much work as the DTA, but it can find the common problems that cause significant performance problems in deployed systems.  The development team used this to debug a number of customer applications and found that it did identify “better” indexes in a number of cases.  If you have to debug a live system where the physical database design is not known to be close to optimal, this may be a useful tool to help improve the system performance.

 

The specific details of the DMVs are documented here:

http://msdn2.microsoft.com/en-US/library/ms345434(SQL.90).aspx

http://msdn2.microsoft.com/en-US/library/ms345407(SQL.90).aspx

http://msdn2.microsoft.com/en-us/library/ms345421(SQL.90).aspx

 

The following examples show an example about how they can be used to identify and improve the physical database design in a simple example:

 

use tempdb

 

drop table t

create table t(col1 int, col2 int, col3 binary(500))

declare @i int

set @i = 0

while @i < 10000

begin

insert into t(col1, col2) values (@i, rand()*1000)

set @i = @i + 1

end

 

set showplan_text on

select * from t as t1 inner join t as t2 on t1.col1=t2.col1 where t2.col2 = 500

 

StmtText                                                                                                                                                    

------------------------------------------------------------------------------------------------------------------------------------------------------------

  |--Hash Match(Inner Join, HASH:([t2].[col1])=([t1].[col1]), RESIDUAL:([t].[col1] as [t2].[col1]= [t].[col1] as [t1].[col1]))

       |--Table Scan(OBJECT:( [t] AS [t2]), WHERE:( [t].[col2] as [t2].[col2]=(500)))

       |--Table Scan(OBJECT:( [t] AS [t1]))

 

set showplan_text off

 

-- run the query

select * from t as t1 inner join t as t2 on t1.col1=t2.col1 where t2.col2 = 500

 

-- look at our management views to see what recommendations exist for this query

select * from sys.dm_db_missing_index_details

select * from sys.dm_db_missing_index_groups

select * from sys.dm_db_missing_index_group_stats

 

(columns removed for space)

index_handle database_id object_id   equality_columns      included_columns 

------------ ----------- ----------- ----------------------------------------

11           2           741577680   [col2]                NULL             

9            2           741577680   [col1]                [col2], [col3]    

 

(2 row(s) affected)

 

index_group_handle index_handle

------------------ ------------

10                 9

12                 11

 

(2 row(s) affected)

 

group_handle unique_compiles      user_seeks           user_scans           last_user_seek                                         last_user_scan                                         avg_total_user_cost                                   avg_user_impact                                       system_seeks         system_scans         last_system_seek                                       last_system_scan                                       avg_total_system_cost                                 avg_system_impact                                    

------------ -------------------- -------------------- -------------------- ------------------------------------------------------ ------------------------------------------------------ ----------------------------------------------------- ----------------------------------------------------- -------------------- -------------------- ------------------------------------------------------ ------------------------------------------------------ ----------------------------------------------------- -----------------------------------------------------

10           1                    1                    0                    2006-04-06 11:14:55.130                                NULL                                                   1.2693552627256595                                    50.409999999999997                                    0                    0                    NULL                                                   NULL                                                   0.0                                                   0.0

12           1                    1                    0                    2006-04-06 11:14:55.130                                NULL                                                   1.2693552627256595                                    46.479999999999997                                    0                    0                    NULL                                                   NULL                                                   0.0                                                   0.0

 

(2 row(s) affected)

 

 

create index i1 on t(col2)

 

-- let's see if the plan changed

set showplan_text on

select * from t as t1 inner join t as t2 on t1.col1=t2.col1 where t2.col2 = 500

 

 

-- now we have an index seek, followed by a bookmark lookup, then followed by a hash join

StmtText                                                                                                                                                    

------------------------------------------------------------------------------------------------------------------------------------------------------------

  |--Hash Match(Inner Join, HASH:([t2].[col1])=([t1].[col1]), RESIDUAL:([t].[col1] as [t2].[col1]= [t].[col1] as [t1].[col1]))

       |--Nested Loops(Inner Join, OUTER REFERENCES:([Bmk1003]))

       |    |--Index Seek(OBJECT:([t].[i1] AS [t2]), SEEK:([t2].[col2]=(500)) ORDERED FORWARD)

       |    |--RID Lookup(OBJECT:([t] AS [t2]), SEEK:([Bmk1003]=[Bmk1003]) LOOKUP ORDERED FORWARD)

       |--Table Scan(OBJECT:([tempdb].[dbo].[t] AS [t1]))

 

set showplan_text off

 

-- run the query again (it should be a bit faster now)

select * from t as t1 inner join t as t2 on t1.col1=t2.col1 where t2.col2 = 500

 

-- let's look at our management views again

 

select * from sys.dm_db_missing_index_details

select * from sys.dm_db_missing_index_groups

select * from sys.dm_db_missing_index_group_stats

 

(columns removed for space)

index_handle database_id object_id   equality_columns included_columns 

------------ ----------- ----------- -----------------------------------

13           2           741577680   [col1]           [col2], [col3]  

 

(1 row(s) affected)

 

index_group_handle index_handle

------------------ ------------

14                 13

 

(1 row(s) affected)

 

group_handle unique_compiles      user_seeks           user_scans           last_user_seek                                         last_user_scan                                         avg_total_user_cost                                   avg_user_impact                                       system_seeks         system_scans         last_system_seek                                       last_system_scan                                       avg_total_system_cost                                 avg_system_impact                                    

------------ -------------------- -------------------- -------------------- ------------------------------------------------------ ------------------------------------------------------ ----------------------------------------------------- ----------------------------------------------------- -------------------- -------------------- ------------------------------------------------------ ------------------------------------------------------ ----------------------------------------------------- -----------------------------------------------------

14           1                    1                    0                    2006-04-06 11:17:01.617                                NULL                                                   0.70575013268039988                                   90.670000000000002                                    0                    0                    NULL                                                   NULL                                                   0.0                                                   0.0

 

create clustered index i2 on t(col1)

 

-- let's see if the plan changed

set showplan_text on

select * from t as t1 inner join t as t2 on t1.col1=t2.col1 where t2.col2 = 500

StmtText                                                                                                                                                                                     

--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

  |--Nested Loops(Inner Join, OUTER REFERENCES:([t2].[col1]))

       |--Nested Loops(Inner Join, OUTER REFERENCES:([Uniq1005], [t2].[col1]))

       |    |--Index Seek(OBJECT:([t].[i1] AS [t2]), SEEK:([t2].[col2]=(500)) ORDERED FORWARD)

       |    |--Clustered Index Seek(OBJECT:([t].[i2] AS [t2]), SEEK:([t2].[col1]= [t].[col1] as [t2].[col1] AND [Uniq1005]=[Uniq1005]) LOOKUP ORDERED FORWARD)

       |--Clustered Index Seek(OBJECT:([t].[i2] AS [t1]), SEEK:([t1].[col1]=[t].[col1] as [t2].[col1]) ORDERED FORWARD)

 

set showplan_text off

 

-- now run the query again (it should be even faster)

select * from t as t1 inner join t as t2 on t1.col1=t2.col1 where t2.col2 = 500

 

I hope that this gives you enough information to experiment with this on your own applications.

 

Thanks,

 

Conor

Author: "QueryOptTeam"
Comments Send by mail Print  Save  Delicious 
Date: Friday, 31 Mar 2006 19:04

Parameters are a useful way to improve overall system performance when there are many common queries with the same shape.  Instead of compiling each query, one plan can be used for all similar queries.  This can significantly reduce CPU overhead and improve throughput.  As long as the queries would have really returned the same plan, this is a big performance winner.  SQL Server internally tries to automatically turn simple non-parameterized user queries into parameterized queries to take advantage of this performance gain.

 

Parameter use, especially in more complex scenarios, can also cause performance issues.  If the queries are complex and/or the data distribution on the columns against which the parameter is compared vary, the cost of different plan choices can change.  A plan that is optimal for one parameter value may perform poorly for another value.  The query optimizer still needs to estimate the selectivity and cardinality of predicates using a parameter value.  This section describes how this process works in more detail.

 

The default implementation would be to use the average number of duplicates per value (average frequency) to guess how many rows that the parameter would match.  For an equality predicate, that’s exactly what will happen in the base case.  However, the optimizer tries to find out any specific value available at the time that the query is compiled and will use that value to estimate cardinality instead.  This process of using the parameter value to estimate selectivity and cardinality is called “parameter sniffing”.

 

There are some non-obvious implementation details that can get in the way of giving the optimizer the chance to use that value.  One common issue is that SQL Server’s procedural language, T-SQL, is interpreted.  Additionally, the compilation model for batches of commands will compile all commands and then execute them.  If you set a parameter value and then run a query that uses that parameter within the same batch, the value isn’t available to the optimizer (and therefore it can’t be sniffed).

 

Here’s some SQL examples to demonstrate the various behaviors in SQL 2005:

 

use tempdb

 

-- create a table with 2000 rows.  1000 of them have the values 1 to 1000 each once (no

-- duplicates).  Then we have 1000 rows with the value 5000.

drop table t

create table t(col1 int)

declare @i int

set @i = 0

while @i < 1000

begin

insert into t(col1) values (@i)

set @i = @i + 1

end

set @i = 0

while @i < 1000

begin

insert into t(col1) values (5000)

set @i = @i + 1

end

 

-- Let's create some fullscan statistics on the column in our table

create statistics t_col1 on t(col1) with fullscan

 

-- note that the selectivity for the table in the statistics is 1/1001 = 9.9900097E-4;  There are 1001 distinct values in the table

dbcc show_statistics ('dbo.t','t_col1')

 

-- compile with no value to sniff.  We should use the "density" for the whole table to make our estimate

-- which means that we'll take 2000 rows * 1/1001 = about 2 rows returned

dbcc freeproccache

declare @p int

select * from t where col1 = @p

-- (look at the output plan to see the estimate)

 

-- same scenario but set a value.  The value 5000 has 1000 instances, but we estimate 2 rows. 

-- Why? Well, we compile the batch before we execute it, so the optimizer in 2005 does not see

-- the parameter value and we treat this the same as the previous case because it hasn’t been

-- actually set when the query is compiled

dbcc freeproccache

declare @p int

set @p = 5000

select * from t where col1 = @p

 

-- Let's use the option recompile as a workaround.

-- The first optimization has the same problem as before - estimates 2 rows

dbcc freeproccache

declare @p int

set @p = 1

select * from t where col1 = @p

option(recompile)

 

-- now look at the compiled plan for this case - we've recompiled and correctly estimate 1 row

select * from t where col1 = @p

option(recompile)

 

-- Another (better) workaround is to use the new optimize for hint - it avoids the recompile

-- and we estimate 1 row

dbcc freeproccache

declare @p int

set @p = 1

select * from t where col1 = @p

option (optimize for (@p = 1))

 

-- last workaround - use a stored procedure.  This will create a new context in the

-- server and lets the optimizer "see" the parameter and sniff it during compilation.

create procedure foo (@p int)

as

return select * from t where col1 = @p

 

-- compile and examine the plan for this - estimates 1 row instead of 2

dbcc freeproccache

execute foo @p=1

 

-- how does one see if the plan used a sniffed parameter?  If sniffed, the information

-- is visible in showplan_xml

set showplan_xml on

execute foo @p=1

 

-- look for a node like this:

- <ParameterList>

  <ColumnReference Column="@p" ParameterCompiledValue="(1)" />

  </ParameterList>

 

 

 

The examples here demonstrate how the cardinality estimates change based on the patterns you use to invoke your queries.  In the examples, we expect to see an estimate of 1 row for each time we sniff a parameter with a value between 1-1000 since there is exactly one of each row.  If we sniff nothing, we’d expect to use the average frequency (which is 2 rows for this example).  If you pick the outlier (in this case we have 1000 rows with the value 5000), then you should see a higher estimate.

 

For the examples I’ve given here, I purposely picked a very simple query plan so that you could easily see the differences in the cardinality estimates without having to explain any other oddities in the query plan.  While there is no plan choice impact for these examples, cardinality estimation errors such as the ones introduced here do cause changes in more complex queries. 

 

The main points that you need to remember are:

  1. If you don’t see any problems due to parameters in your application, you don’t need to do anything.  Just keep this information in the back of your head, just in case.
  2. If you find that the optimizer is picking different plans over time that have varying performance characteristics, consider using a parameter hint with a representative “average” value to get a good, common query plan that will work reasonably for all values.
  3. If you are running really complex queries and need the plan choice to be exact in each case, you can consider using the “recompile” hint – just know that it will compile each time it runs, so this is likely more appropriate for longer-running queries to justify that compilation cost.
  4. Moving a query into a stored procedure can put it into a separate procedural context and can be a good way to get that value visible to the optimizer (Note: this works in SQL 2000 as well)
Author: "QueryOptTeam"
Comments Send by mail Print  Save  Delicious 
Date: Thursday, 30 Mar 2006 18:20

Today, we'll talk about row goals.  The optimizer in SQL Server has a feature that can bias plan choices to retrieve a certain number of rows quickly instead of the whole results.  This shows up in a few places, but the primary areas are in TOP N queries and in subqueries that need to check for the existance of "a" row - WHERE EXISTS, for example.  The query hint "option (fast N)" also translates into the same feature. 

 

One of the problems that can arise with row goals is that the query plan can change when you add them into a query request.  Especially with the option(fast N) hint, you can find cases where the first row may come back quickly but the whole results come back more slowly.  So, if you send option(fast N) but retrieve the whole results, your system won't perform as well.

 

Effectively, we bias the optimizer to favor plans that can return a few rows quickly compared to the minimum cost to return all rows.  In practice, this often means that joins will choose nested loops joins for row-goal limited plans and hash joins otherwise.


The following example demonstrates the issue:

 

use tempdb

 

create table A(col1 int, col2 binary(100), col3 int)

declare @i int

set @i = 0

while @i < 5000

begin

insert into A(col1, col2, col3) values (@i, 0x3333, rand()*1000)

set @i = @i + 1

end

 

create clustered index i1 on A(col1)

 

set statistics time on

-- should pick a series of hash joins

select A1.* from

A as A1 inner join A as A2 on A1.col1 = A2.col1

inner join A as A3 on A1.col1 = A3.col1

 

-- if there is a row goal, we’ll pick the loop join plan that returns one (or a few) row(s) quickly

set statistics time on

select A1.* from

A as A1 inner join A as A2 on A1.col1 = A2.col1

inner join A as A3 on A1.col1 = A3.col1

option (fast 1)

 

You can run these on your installation to see the time difference for retrieving all rows with the hash join plan vs. the loop join plan (just keep adding rows until you see the difference). 

 

This pattern is caused by the row goal logic in the optimizer.  When we have a very low row goal, the nested loops join is preferred because its initial cost (the cost for the first row) is comparatively low – it just involves a single seek for this example.  The hash join plan has a higher initial cost because it has to build a hash table before any rows can be returned.  Once built, however, the hash join plan is generally cheaper and would be picked if the estimated number of rows gets large.
Author: "QueryOptTeam"
Comments Send by mail Print  Save  Delicious 
Date: Monday, 27 Mar 2006 20:25

Ian had a blog that contains a number of interestig tips/tricks, mostly about cardinality estimation during query optimization.

I've chatted with him and will be migrating/expanding some content over to the team site.

If you have specific requests from topics in his Blog that would interest you, post them up and I'll find someone on the team to work on them.

Ian's Blog: http://blogs.msdn.com/ianjo/default.aspx

Thanks,

Conor

 

Author: "QueryOptTeam"
Comments Send by mail Print  Save  Delicious 
Date: Saturday, 25 Mar 2006 00:55

(Updated 2006-27-03 9:00am Pacfiic Time - at the bottom)

SQL is a declarative language.  That means that the language declares the form of the output but not the method used to generate those results.  There are cases, however, where the language is not quite rich enough to describe what customers want.  There are also cases where it is possible to over-infer guarantees that are not really in the language at all.

ORDER BY is an example that I'd like to discuss in this post.  In ANSI SQL, the language has the ability to specify the output order of a query (the "presentation order").   This applies to query results and to cursor results, if a cursor is being used.  This is exposed via ORDER BY, and this is really only legal in the ANSI spec on the outer-most query block of a query.  Microsoft SQL Server allows this in more places than the spec indicates (which is something we can do and still be in-line with the specification).  Specifically, we allow the use of ORDER BY in sub-selects or in view definitions to help define the set of rows that qualify with a TOP operation (TOP is not in ANSI SQL, by the way).

The default plan implementation for this code happens to sort the rows as part of performing the TOP operation.  Often this meant that the results happened to be returned in sorted order, and this led customers to believe that there was a guarantee that rows were sorted.  This is actually not the case.  If you want rows to be returned to the user in sorted order, you need to use an ORDER BY on the outermost query block (per ANSI) to guarantee the output presentation order. 

In SQL Server 2005, you can see how the output order is *not* guaranteed through the following example:

use tempdb

create table t1 (col1 int, col2 int)
declare @i int
set @i = 0
while @i < 20
begin
insert into t1(col1, col2) values (@i, rand()*1000)
set @i = @i + 1
end

create view v as (select top 100 percent * from t1 order by col1 desc)

set showplan_text on
select * from v

The output from this example is:

StmtText                                      
----------------------------------------------
  |--Table Scan(OBJECT:([tempdb].[dbo].[t1]))

col1        col2       
----------- -----------
0           443
1           418
2           291
3           726
4           948
5           315
6           835
7           247
8           755
9           78
10          88
11          906
12          640
13          876
14          422
15          746
16          528
17          909
18          186
19          868

You'll notice that the original table was created as a heap (no clustered index) and that no secondary indexes are defined.  So, if there were an ordering guarantee for the query based on the order by in the view, the rows should be sorted in descending order and the query plan would need to have a sort in it to make that happen.  However, you'll notice that the query plan contains only a Table Scan, which will return the rows back in the order they happen to be read from disk.  In this particular case, the optimizer recognizes that TOP 100 PERCENT qualifies all rows and does not need to be computed at all.  It gets removed from the query plan, and there is no other reason to do an intermediate sorting operation.  As such, the output isn't returned in any particular order.

So, please do not assume that nested sub-selects will guarantee order.  The optimizer will consider rewrites that invalidates this assumption.  If you need rows returned in a particular order, please add that to the outermost block of your SELECT statement.

Thanks,

Conor Cunningham

PS: Update... One comment I received seeks a bit more detail on why the ORDER BY is "ignored" in this case.  I'll try to expand a bit more to see if that helps. 

From the semantics of the query, the optimizer only really honors the ORDER BY as part of the evaluation of the TOP in that same scope.  The syntax is a bit unfortunate because it causes people to believe that things "will be ordered".  However, it really only says "I want this set of rows".  Presentation orders only apply to the output of the query, not intermediate nodes.  Since we can reorder operations, you can't actually view this as a procedural guarantee "first I sort, then I do whatever is 'above' the sort".  You don't need an optimizer if that were the case, as you aren't asking declarative questions anymore. 

The bottom line is that even if we do the sort as part of the TOP operation in a sub-select, it does NOT guarantee anything about the output order of the query. 

SELECT TOP 99 PERCENT * FROM T ORDER BY col1

is not the same as:

SELECT * FROM (SELECT TOP 99 PERCENT * FROM T ORDER BY col1) AS A

The top query guarantees the output order of the query.  The bottom query does not (even if the rows happen to come back in sorted order)

 

 

Author: "QueryOptTeam"
Comments Send by mail Print  Save  Delicious 
Next page
» You can also retrieve older items : Read
» © All content and copyrights belong to their respective authors.«
» © FeedShow - Online RSS Feeds Reader