T-SQL Querying (2015)

---

Legacy estimator vs. 2014 cardinality estimator

The two major milestones for significant changes in the cardinality estimator were SQL Server 7.0 and SQL Server 2014. There’s a 16-year difference between the release dates of these versions. The new cardinality estimator is the result of lots of learning, taking into consideration the changes that took place over the years in database workloads. These days, the volume of data and the types of queries are different than they were two decades ago.

There are many changes in the new cardinality estimator compared to the legacy one. Microsoft’s goal was to improve the average case, with the understanding that there could be some cases with regression. SQL Server will use the new cardinality estimator by default when the database compatibility level is that of 2014 (120) or higher, and it will use the legacy estimator with lower compatibility levels. To make sure SQL Server uses the new cardinality estimator in our PerformanceV3 database, set the database compatibility level to 120 by running the following code:

USE PerformanceV3;
ALTER DATABASE PerformanceV3 SET COMPATIBILITY_LEVEL = 120;

If you identify certain queries that will benefit from the nondefault cardinality estimator, you can use a query trace flag to force a specific one. Use trace flag 9481 for the legacy cardinality estimator and trace flag 2312 for the new one. Because our database compatibility will cause SQL Server to use the new one by default, in my examples I will use query trace flag 9481 when I want to demonstrate using the old one. If you need your databases to use compatibility level 120 and up to enable new functionality but still use the old cardinality estimator by default, you can enable the trace flag at the server level with the startup parameter –T9481 or the command DBCC TRACEON(9481, –1).

I’m going to discuss a number of critical changes in cardinality estimation methods between the legacy estimator and the new cardinality estimator, but my coverage is not meant to be exhaustive. You can find more details in the following white paper: http://msdn.microsoft.com/en-us/library/dn673537.aspx.

Implications of underestimations and overestimations

Making accurate cardinality estimations is not a simple task you can do well without actually running the query and without a time machine. If you ever tried getting into the business of fortune telling, you know this. Even with the new cardinality estimator, you will still encounter cases where the estimations will be inaccurate. The implications of inaccurate estimations are generally that they might lead the optimizer to make suboptimal choices.

Underestimations and overestimations tend to have different implications. Underestimations will tend to result in the following (not an exhaustive list):

For filters, preferring an index seek and lookups to a scan.

For aggregates, joins, and distinct, preferring order-based algorithms to hash-based ones.

For sort and hash operations, there might be spills to tempdb as a result of an insufficient memory grant.

Preferring a serial plan over a parallel one.

To demonstrate an underestimation, I’ll use a variable in the query and tell the optimizer to optimize the query for a specified value, like so:

DECLARE @i AS INT = 500000;

SELECT empid, COUNT(*) AS numorders
FROM dbo.Orders
WHERE orderid > @i
GROUP BY empid
OPTION(OPTIMIZE FOR (@i = 999900));

The execution plan for this query is shown in Figure 2-37.

FIGURE 2-37 Plan with underestimated cardinality.

As instructed, the optimizer optimized the query for the variable value 999900, regardless of the run-time value. The optimizer used the histogram on the orderid column to estimate the cardinality of the filter for this input, and it came up with an estimation of 100 rows. In practice, the filter has 500,000 matches. Consequently, you see all four aforementioned implications of an underestimation on the optimizer’s choices. It chose to use a seek in the index PK_Orders and lookups, even though a scan of the table would have been more efficient. It chose to sort the rows and use an order-based aggregate algorithm (Stream Aggregate) even though a hash aggregate would have been more efficient here. The memory grant for the sort operation was insufficient because it was based on the estimate of 100 rows, so the Sort operator ended up spilling to tempdb twice (spill level 2). It chose a serial plan even though a parallel plan would have been more efficient here.

Overestimations will tend to result in pretty much the inverse of underestimations (again, not an exhaustive list):

For filters, preferring a scan to an index seek and lookups.

For aggregates, joins, and distinct, preferring hash-based algorithms to order-based ones.

For sort and hash operations, there won’t be spills, but very likely there will be a larger memory grant than needed, resulting in wasting memory.

Preferring a parallel plan over a serial one.

To demonstrate an overestimation, I’ll simply use a variable in the query and assign it a value that results in a selective filter, like so:

DECLARE @i AS INT = 999900;

SELECT empid, COUNT(*) AS numorders
FROM dbo.Orders
WHERE orderid > @i
GROUP BY empid;

Unlike parameter values, variable values normally cannot be sniffed. That’s because the initial optimization unit that the optimizer gets to work on is the entire batch. The optimizer is not supposed to execute the code preceding the query before optimizing it. In other words, it doesn’t perform the variable assignment before it optimizes the query. So it has to make a cardinality estimate for the predicate orderid > @i based on an unknown variable value. Later, in the section “Unknowns,” I provide a magic table of estimates for unknown inputs in Table 2-1. You will find that for the greater than (>) operator with an unknown input, the optimizer uses a hard-coded estimate of 30 percent matches. Apply 30 percent to the table’s cardinality of 1,000,000 rows, and you get 300,000 rows. That’s compared to an actual number of matches of 100. You can see these estimated and actual numbers in the execution plan for this query, which is shown in Figure 2-38.

FIGURE 2-38 Plan with overestimated cardinality.

You can see the aforementioned implications of an overestimation of cardinality on the optimizer’s choices. It chose to use a scan of some covering index instead of a seek in the index PK_Orders and lookups. It chose a local/global aggregate with a hash-based algorithm for the local aggregate instead of using an order-based aggregate. The memory grant for the hash and sort operations is exaggerated. It chose a parallel plan instead of a serial one.

Of course, it is best if the cardinality estimate is accurate, but between an underestimation and an overestimation, I generally prefer the latter. That’s because I find that the impact of an overestimation on the performance of the query tends to be less severe.

Statistics

SQL Server relies on statistics about the data in its cardinality estimates. Whenever you create an index, SQL Server creates statistics using a full scan of the data. When additional statistics are needed, SQL Server might create them automatically using a sampled percentage of the data. SQL Server creates three main types of statistics: header, density vectors, and a histogram. To demonstrate those, run the following code, which creates an index with the key columns (custid, empid):

CREATE INDEX idx_nc_cid_eid ON dbo.Orders(custid, empid);

SQL Server created the three aforementioned types of statistics to support the index. You can see those by running the DBCC SHOW_STATISTICS command, like so:

DBCC SHOW_STATISTICS(N'dbo.Orders', N'idx_nc_cid_eid');

I got the following output from this command (with the text for the header wrapped to fit in print):

Name Updated Rows Rows Sampled Steps Density Average key length
--------------- -------------------- -------- ------------- ------ ----------- ------------------
idx_nc_cid_eid Oct 21 2014 7:17PM 1000000 1000000 187 0.02002646 18

String Index Filter Expression Unfiltered Rows
------------- ------------------ ----------------
YES NULL 1000000

All density Average Length Columns
------------- -------------- -------------------------
5E-05 11 custid
1.050216E-06 15 custid, empid
1.000042E-06 18 custid, empid, orderdate

RANGE_HI_KEY RANGE_ROWS EQ_ROWS DISTINCT_RANGE_ROWS AVG_RANGE_ROWS
------------ ------------- ------------- -------------------- --------------
C0000000001 0 46 0 1
C0000000130 6437 37 128 50.28906
C0000000252 6089 37 121 50.32232
C0000000310 2918 67 57 51.19298
C0000000539 11538 62 228 50.60526
...
C0000019486 6307 66 126 50.05556
C0000019704 10934 30 217 50.3871
C0000019783 4045 66 78 51.85897
C0000019904 5906 68 120 49.21667
C0000020000 4733 46 95 49.82105

The first part in the statistics is the header. It contains general information about the data, such as the cardinality of the table (1,000,000 rows in our example).

The second part in the statistics is the density vectors. This part records density information for all leading vectors of key columns. You created the index on custid and empid, but internally SQL Server added orderdate as the last key column; that’s because the orderdate column is the clustered index key column and therefore nonclustered indexes use it as the row locator. So, with three key columns, you have three vectors of leading columns. The density of the column represents the average percentage of occurrences per distinct combination of values. For example, there are 20,000 distinct customer IDs in the table, so the average percentage per distinct value is 1 / 20,000 = 0.00005, or 5E-05 as it appears in the statistics. As you add more columns, the density reduces until you get uniqueness. So, for the vector (custid, empid), the density is 0.000001050216, or 1.050216E-06. SQL Server uses the density information when it needs to make cardinality estimates for unknown inputs, or when it considers that the average case is likely to be more accurate.

The third part of the statistics is the histogram. When you create an index, SQL Server creates a histogram on the leading key based on a full scan of the data. In addition, when SQL Server optimizes a query and needs a histogram on a column that is not a leading index key, it can create one on the fly as long as the database option AUTO_CREATE_STATISTICS is enabled. It samples a percentage of the rows for this purpose.

SQL Server supports only single-column histograms with up to 200 steps. Each step represents the range of keys that are greater than the previous step’s RANGE_HI_KEY value and less than or equal to the current RANGE_HI_KEY value. For example, the second step in our histogram represents the range of customer IDs that are greater than C0000000001 and less than or equal to C0000000130. The RANGE_ROWS value indicates the number of rows represented by the step, excluding the ones with the RANGE_HI_KEY value. The EQ_ROWS value represents the number of rows with the RANGE_HI_KEY value. The sum of RANGE_ROWS and EQ_ROWS is the total number of rows that the step represents. The DISTINCT_RANGE_ROWS value represents the distinct count of the key values in the step, excluding the upper bound. The AVG_RANGE_ROWSvalue represents the average number of rows in the step per distinct key value, again, excluding the upper bound.

SQL Server uses the histogram to make cardinality estimates for known inputs. As an example, consider the following query:

SELECT orderid, custid, empid, shipperid, orderdate, filler
FROM dbo.Orders
WHERE custid = 'C0000000001';

The execution plan for this query is shown in Figure 2-39.

FIGURE 2-39 Plan that shows the use of a histogram on a single column based on RANGE_HI_KEY.

SQL Server looked for the step responsible for the input value C0000000001 and found that it belongs to step 1. It so happens that this input value is equal to the RANGE_HI_KEY value in the step, so the cardinality estimate for it is simply the EQ_ROWS value, which is 46. You can see in the query plan that 46 is the estimated number of rows after filtering.

As another example, consider the following query:

SELECT orderid, custid, empid, shipperid, orderdate, filler
FROM dbo.Orders
WHERE custid = 'C0000000002';

Observe the first two steps in the histogram:

RANGE_HI_KEY RANGE_ROWS EQ_ROWS DISTINCT_RANGE_ROWS AVG_RANGE_ROWS
------------ ------------- ------------- -------------------- --------------
C0000000001 0 46 0 1
C0000000130 6437 37 128 50.28906

The input value belongs to step 2. However, it is less than the RANGE_HI_KEY value of the step, so SQL Server uses the AVG_RANGE_ROWS value of 50.2891 as the cardinality estimate. The query plan I got for this query on my system showed an estimated number of rows of 50.2891 and an actual number of 57.

As you can see, with an equality predicate for a known input the cardinality estimate is pretty straightforward. If you have a range predicate, the estimate will be interpolated from the information in the histogram steps. If only one step is involved, the estimate will be interpolated from only that step’s information. If multiple steps are involved, SQL Server will split the filter’s range into the subintervals that intersect with the different steps, interpolate the estimate for each subinterval, and aggregate the estimates.

The next example demonstrates a case where the optimizer uses density vectors. Remember that unlike parameter values, variable values aren’t sniffable. That’s because the initial optimization unit is the batch and the optimizer isn’t supposed to execute the assignments before it optimizes the query. Consider the following code:

DECLARE @cid AS VARCHAR(11) = 'C0000000001';

SELECT orderid, custid, empid, shipperid, orderdate, filler
FROM dbo.Orders
WHERE custid = @cid;

The optimizer cannot sniff the variable value here. Because density information is available for the custid column, the optimizer uses it. Remember that the density for this column is 0.00005. Multiply this value by the table’s cardinality of 1,000,000 rows, and you get 50. The execution plan I got for this query showed an estimated number of rows of 50 and an actual number of 46.

Estimates for multiple predicates

As mentioned, SQL Server supports only single-column histograms. When the query filter involves more than one predicate, SQL Server can make an estimate for each of the predicates based on the respective histogram, but it will need to somehow combine the estimates into a single one. The legacy estimator and new cardinality estimator handle this differently.

I’ll explain the estimation methods with both a conjunction of predicates (predicates separated by AND operators) and a disjunction of predicates (predicates separated by OR operators).

Before I describe estimation methods for multiple predicates, I’ll make a note of the selectivity (percentage of matches) of two specific predicates so that I can use those in my examples. The following query has a filter with a predicate based on the custid column:

SELECT orderid, custid, empid, shipperid, orderdate, filler
FROM dbo.Orders
WHERE custid <= 'C0000001000';

On my system, the query plan shows an estimated number of rows of 52,800. This number translates to a selectivity of 5.28%.

The following query has a filter with a predicate based on the empid column:

SELECT orderid, custid, empid, shipperid, orderdate, filler
FROM dbo.Orders
WHERE empid <= 100;

If there are no statistics on the empid column before you run this query, the execution of this query triggers the creation of such statistics. On my system, the query plan showed an estimated number of rows of 19,800, translating to a selectivity of 19.8%.

The legacy cardinality estimator assumes that when your query has multiple predicates, they are independent of each other. Based on this assumption, for a conjunction of predicates it computes the result selectivity as the product of the individual ones. Consider the following query as an example (notice the trace flag forces the use of the legacy cardinality estimator):

SELECT orderid, custid, empid, shipperid, orderdate, filler
FROM dbo.Orders
WHERE custid <= 'C0000001000'
AND empid <= 100
OPTION(QUERYTRACEON 9481);

On my system, I got the query plan shown in Figure 2-40.

FIGURE 2-40 Estimate for the conjunction with the legacy cardinality estimator.

Remember that the individual estimates on my system were 5.28% and 19.8%, so the product is 5.28% * 19.8% = 10.4%. Indeed, the cardinality estimate in the plan reflects this.

After many years of experience with SQL Server, Microsoft learned that, in reality, there’s usually some level of dependency between predicates. In the average case, predicates are neither completely independent nor completely dependent—rather, they are somewhere in between. Even though my sample data doesn’t reflect this because I used simple randomization to create it, if you think about it, there will typically be some dependency between the customer who places an order and the employee who handles it. With complete independence, statistically a product of the individual estimates should be used. Under complete dependence, the most selective estimate should be used. But because the average case in reality is somewhere in between, Microsoft chose a method called exponential backoff, which is suitable in such a case. This method takes into consideration the most selective estimate as is, and then gradually reduces the effect of the less selective estimates by raising each to the power of a smaller fraction. Assuming S1 is the most selective estimate (expressed as a percentage), S2 is the next most selective, and so on, the exponential backoff formula is the following:

S1 * S2^1/2 * S3^1/4 * S4^1/8 * ...

Of course, the cardinality estimator will multiply the final percentage by the input’s cardinality (1,000,000 in our case) to produce an estimate in terms of a number of rows. In our example, when you apply this method to our two predicates, you get 5.28% * SQRT(19.8%) = 23.5%, which translates to 23,500 rows.

Here’s our query without the trace flag, meaning that the new cardinality estimator will be used:

SELECT orderid, custid, empid, shipperid, orderdate, filler
FROM dbo.Orders
WHERE custid <= 'C0000001000'
AND empid <= 100;

I got the plan shown in Figure 2-41.

FIGURE 2-41 Estimate for the conjunction with the new cardinality estimator.

As you can see, the cardinality estimate here was based on the exponential backoff method, and as a result, you get a higher estimate compared to the legacy method, which is based on a simple product. If you have cases where predicates are truly independent of each other, you can always add trace flag 9481 to the query to force the legacy cardinality estimation method.

For a disjunction of predicates, the legacy cardinality estimator computes the sum of the individual estimates minus their product. Consider the following query as an example:

SELECT orderid, custid, empid, shipperid, orderdate, filler
FROM dbo.Orders
WHERE custid <= 'C0000001000'
OR empid <= 100
OPTION(QUERYTRACEON 9481);

The estimate in this example is computed as 5.28% + 19.8% – (5.28% * 19.8%) = 24%.

The new cardinality estimator uses a method that is more aligned with the method for a conjunction of predicates. It negates (100% minus) the result of an exponential backoff formula that is based on the negation of the individual estimates. In our example, this translates to 100% – (100% – 19.8%) * SQRT(100% – 5.28%) = 21.9%. That’s the estimate I got on my system for our sample query (about 21,900 rows):

SELECT orderid, custid, empid, shipperid, orderdate, filler
FROM dbo.Orders
WHERE custid <= 'C0000001000'
OR empid <= 100;

If you have multiple predicates and you often get inaccurate estimates there are a couple of ways to get better estimates. That’s assuming that all predicates are equality ones or that you have at most one range predicate but all the rest are equality ones. For example, suppose that users often filter the data by customer ID and employee ID, both with equality predicates. So the query filter might look like this: WHERE custid = ‘C0000000003’ AND empid = 5. You create a computed column (call it custid_empid) that concatenates the customer ID and employee ID values. Just the fact that a computed column exists allows SQL Server to create statistics on the column, regardless of whether you index it or not. Your query will need to filter the concatenated value to benefit from such statistics. You can filter by the computed column name or directly by the concatenated expression. In both cases, SQL Server can rely on the histogram on the computed column and on an index if you created one. So the query filter might look like this: WHERE custid_empid = ‘C0000000003_5’.

Another method to use to get better estimates is working with filtered indexes. As long as you have a small number of distinct values in one of the columns, a solution that creates a filtered index per distinct value is maintainable. For example, suppose that in your organization only 10 distinct employees handle orders; in such a case, it’s reasonable to create 10 filtered indexes, one per distinct employee ID. For example, the index for employee ID 5 will have the filter WHERE empid = 5. The index key will be based on the custid column. SQL Server will create a histogram based on the custid column for each filtered index. When the optimizer will need to make a cardinality estimate for a filter such as WHERE custid = ‘C0000000003’ AND empid = 5, it will use the histogram on the custid column in the filtered index for that employee ID (in this example, 5). Effectively, the quality of the estimates will be the same as if you had a multicolumn histogram. You can find more information on filtered indexes later in the chapter, in the section “Indexing features.”

When you’re done, run the following code for cleanup:

DROP INDEX idx_nc_cid_eid ON dbo.Orders;

Ascending key problem

SQL Server normally refreshes statistics once every 500 plus 20 percent of changes in the column in question. Any data added after the statistics were last refreshed is not modeled by the statistics. As an example, the following code creates a table called Orders2 with 900,000 rows and a nonclustered index through a primary key constraint called PK_Orders2:

IF OBJECT_ID(N'dbo.Orders2', N'U') IS NOT NULL DROP TABLE dbo.Orders2;
SELECT * INTO dbo.Orders2 FROM dbo.Orders WHERE orderid <= 900000;
ALTER TABLE dbo.Orders2 ADD CONSTRAINT PK_Orders2 PRIMARY KEY NONCLUSTERED(orderid);

SQL Server creates statistics for the index as part of the index creation; therefore, the histogram on the orderid column models all 900,000 rows from the table. Run the following code to show the statistics for the index:

DBCC SHOW_STATISTICS('dbo.Orders2', 'PK_Orders2');

I got the following output on my system:

Name Updated Rows Rows Sampled Steps Density Average key length
----------- -------------------- ------- ------------- ------ -------- ------------------
PK_Orders2 Oct 21 2014 9:29PM 900000 900000 2 1 4

String Index Filter Expression Unfiltered Rows
------------ ------------------ ----------------
NO NULL 900000

All density Average Length Columns
------------- -------------- --------
1.111111E-06 4 orderid

RANGE_HI_KEY RANGE_ROWS EQ_ROWS DISTINCT_RANGE_ROWS AVG_RANGE_ROWS
------------ ------------- ------------- -------------------- --------------
1 0 1 0 1
900000 899998 1 899998 1

The last part of the output is the histogram on the orderid column. Observe that the maximum order ID value recorded is 900,000, which is indeed currently the maximum value in the table. Next, run the following code to add 100,000 rows:

INSERT INTO dbo.Orders2
SELECT *
FROM dbo.Orders
WHERE orderid > 900000 AND orderid <= 1000000;

Now query the table and filter the rows with an order ID that is greater than 900,000, like so (the trace flag ensures the legacy cardinality estimator is used):

SELECT orderid, custid, empid, shipperid, orderdate, filler
FROM dbo.Orders2
WHERE orderid > 900000
ORDER BY orderdate
OPTION(QUERYTRACEON 9481);

Because the extra 100,000 rows are less than the threshold for refreshing the statistics, the new rows are not modeled by the histogram. You can see this by running DBCC SHOW_STATISTICS again. You will see that the maximum value is still 900,000. The legacy cardinality estimator examines the histogram and sees that the filter’s range is after the maximum value in the histogram. Based on just this information, the estimate should be zero matching rows, but the minimum allowed estimation is 1. Examine the execution plan for the query in Figure 2-42.

FIGURE 2-42 Plan showing the ascending key problem with the legacy cardinality estimator.

Observe that the estimated cardinality of the filter is 1 row, whereas the actual is 100,000. You can see a number of suboptimal choices that the optimizer made based on the inaccurate estimate. This problem typically happens when the column is an ascending key column and you filter recent data. Often the recent data isn’t modeled by the histogram.

The new cardinality estimator handles the estimate differently. If it identifies that the filter’s interval exceeds the recorded maximum, it interpolates the estimate by taking into consideration the count of modifications since the last statistics refresh. Run the sample query again, but this time allow SQL Server to use the new cardinality estimator:

SELECT orderid, custid, empid, shipperid, orderdate, filler
FROM dbo.Orders2
WHERE orderid > 900000
ORDER BY orderdate;

I got the execution plan shown in Figure 2-43.

FIGURE 2-43 Plan showing the ascending key problem solved with the new cardinality estimator.

This time, as you can see, the estimate is accurate. As a result, the choices that the optimizer made are much more optimal.

Another tool you can use to deal with the ascending key problem is trace flag 2389. Unlike the new cardinality estimator, this trace flag is available prior to SQL Server 2014. If you enable this trace flag, when SQL Server refreshes statistics it checks if the values in the source column keep increasing. If they keep increasing in three consecutive refreshes, SQL Server brands the source column as ascending. Then, at query compile time, SQL Server adds a ministep to the histogram to model the data that was added since the last refresh. You can find information about this trace flag here: http://blogs.msdn.com/b/ianjo/archive/2006/04/24/582227.aspx.

With very large tables, the default threshold for an automatic statistics update of every 500 plus 20 percent of changes could be insufficient. Think about it: for a table with 100,000,000 rows, the threshold is 20,000,500 changes. If you enable trace flag 2371, SQL Server will gradually reduce the percentage as the table grows. You can find details about this trace flag, including a graph showing the gradual change, here: http://blogs.msdn.com/b/saponsqlserver/archive/2011/09/07/changes-to-automatic-update-statistics-in-sql-server-traceflag-2371.aspx.

Unknowns

I described some cardinality estimation methods SQL Server uses when statistics are available and the input values are known (for example, when you use constants or parameters). In some cases, SQL Server uses cardinality estimation methods based on unknown inputs. Following are those cases:

No statistics are available.

You use variables (as opposed to parameters). As mentioned earlier, variable values aren’t sniffable because the initial optimization unit is the entire batch.

You use parameters with sniffing disabled (for example, when you specify the OPTIMIZE FOR UNKNOWN hint).

Table 2-1 shows the rules that SQL Server uses to make a cardinality estimate for unknown inputs based on the operator you use.

TABLE 2-1 Magic table of estimates for unknown inputs

I should mention that there are a couple of exceptional cases in which SQL Server won’t use this table. One exception is with variables. I mentioned that normally variable values aren’t sniffable. However, if you force a statement-level recompile with a RECOMPILE query option or an automatic statement-level recompile happens, the query gets optimized after the variable values are assigned. Therefore, the variable values become sniffable to the optimizer, and then SQL Server can use its normal cardinality estimation methods based on statistics.

The other exception is when using variables or parameters with sniffing disabled, and the operator is an equality operator, and a density vector is available for the filtered columns. In such a case, the estimate will be based on the density vector.

Next, I’ll demonstrate examples for estimates that are based on the rules in Table 2-1. Run the following code to check which indexes you currently have on the Orders table:

EXEC sp_helpindex N'dbo.Orders';

The output should show only the following indexes:

idx_cl_od
idx_nc_sid_od_cid
idx_unc_od_oid_i_cid_eid
PK_Orders

If you get any other indexes, drop them.

Run the following code to turn off the auto collection of statistics in the database:

ALTER DATABASE PerformanceV3 SET AUTO_CREATE_STATISTICS OFF;

Run the following query to identify statistics that were created automatically on the Orders table:

SELECT S.name AS stats_name,
QUOTENAME(OBJECT_SCHEMA_NAME(S.object_id)) + N'.' + QUOTENAME(OBJECT_NAME(S.object_id)) AS
object,
C.name AS column_name
FROM sys.stats AS S
INNER JOIN sys.stats_columns AS SC
ON S.object_id = SC.object_id
AND S.stats_id = SC.stats_id
INNER JOIN sys.columns AS C
ON SC.object_id = C.object_id
AND SC.column_id = C.column_id
WHERE S.object_id = OBJECT_ID(N'dbo.Orders')
AND auto_created = 1;

Drop all statistics that this query reports. In my case, I used the following code based on the output of the query; of course, you should drop the statistics that the query reports for you:

DROP STATISTICS dbo.Orders._WA_Sys_00000002_38EE7070;
DROP STATISTICS dbo.Orders._WA_Sys_00000003_38EE7070;

Observe in Table 2-1 that the estimate for unknown with any of the operators >, >=, <, <= is 30%. The following queries demonstrate this estimation method:

-- Query 1
DECLARE @i AS INT = 999900;

SELECT orderid, custid, empid, shipperid, orderdate, filler
FROM dbo.Orders
WHERE orderid > @i;

-- Query 2
SELECT orderid, custid, empid, shipperid, orderdate, filler
FROM dbo.Orders
WHERE custid <= 'C0000000010';

Figure 2-44 shows the plans for these queries.

FIGURE 2-44 Plans showing an estimate of 30 percent.

The first query uses a variable whose value cannot be sniffed. The second uses a constant, but statistics are not available, and you disabled the option to create new ones.

For the BETWEEN and LIKE predicates, Table 2-1 shows an estimate of 9%. An exception to this rule is that in SQL Server 2014 when you use BETWEEN with variables, or parameters with sniffing disabled, the estimate is 16.4317%. The following queries demonstrate these rules:

-- Query 1
DECLARE @i AS INT = 999901, @j AS INT = 1000000;

SELECT orderid, custid, empid, shipperid, orderdate, filler
FROM dbo.Orders
WHERE orderid BETWEEN @i AND @j;

-- Query 2
SELECT orderid, custid, empid, shipperid, orderdate, filler
FROM dbo.Orders
WHERE orderid BETWEEN @i AND @j
OPTION(QUERYTRACEON 9481);

-- Query 3
SELECT orderid, custid, empid, shipperid, orderdate, filler
FROM dbo.Orders
WHERE custid BETWEEN 'C0000000001' AND 'C0000000010';

-- Query 4
SELECT orderid, custid, empid, shipperid, orderdate, filler
FROM dbo.Orders
WHERE custid LIKE '%9999';

The execution plans for these queries are shown in Figure 2-45.

FIGURE 2-45 Plans showing estimates for BETWEEN and LIKE.

The first query falls into the exception that I just described, so it gets an estimate of 16.4317%. The second query is the same as the first, but because you force using the legacy cardinality estimator, you get an estimate of 9%. The third and fourth queries use constants, but there are no statistics available. As an aside, query 4 normally causes string statistics, which contain information about occurrences of substrings, to be created. However, because you disabled automatic creation of statistics in the database, SQL Server did not create those statistics, and it used the estimation method based on unknown inputs instead.

With the equality operator, the estimation method for an unknown input depends on the uniqueness of the column and the version of SQL Server. When the column is unique, the estimate is 1 row. When it’s not unique, in SQL Server 2014 the estimate is C^1/2, where C is the input’s cardinality, and prior to SQL Server 2014 it’s C^3/4.

The following queries demonstrate all three methods:

-- Query 1
DECLARE @i AS INT = 1000000;

SELECT orderid, custid, empid, shipperid, orderdate, filler
FROM dbo.Orders
WHERE orderid = @i;

-- Query 2
SELECT orderid, custid, empid, shipperid, orderdate, filler
FROM dbo.Orders
WHERE custid = 'C0000000001';

-- Query 3
SELECT orderid, custid, empid, shipperid, orderdate, filler
FROM dbo.Orders
WHERE custid = 'C0000000001'
OPTION(QUERYTRACEON 9481);

The execution plans with the estimates for these queries are shown in Figure 2-46.

FIGURE 2-46 Plans showing estimates for equality.

When you’re done experimenting, run the following code to turn the automatic creation of statistics back on:

ALTER DATABASE PerformanceV3 SET AUTO_CREATE_STATISTICS ON;

Feel free to rerun the queries to see how the estimations change when SQL Server automatically creates statistics when it needs those. For example, rerun the query with the LIKE predicate:

SELECT orderid, custid, empid, shipperid, orderdate, filler
FROM dbo.Orders
WHERE custid LIKE '%9999';

I got the query plan shown in Figure 2-47.

FIGURE 2-47 Plan for a query using LIKE with string statistics available.

SQL Server first created string statistics on the custid column and then performed the estimate based on those statistics. Compared to the previous estimate you got for this query in Figure 2-45 (it was Query 4 in that figure), this time the estimate is much more accurate.

Another curious difference between the legacy and new cardinality estimators is in how they handle a filter with an expression that manipulates a column. Take the expression orderid % 2 = 0 as an example. The legacy cardinality estimator simply treats the case as an unknown input. As such, the estimate for an equality operator is C^3/4. With our Orders table, this translates to 1,000,000^3/4 = 31,622. That’s likely to be a significant underestimation. The new cardinality estimator is more sophisticated. Here, it actually realizes that the expression uses the modulo (%) operator. Statistically, with % 2 = 0, you’re going to get 50% matches. Accordingly, the estimation for this case is 500,000 rows. This will likely be much closer to the actual number than the estimation made by the legacy cardinality estimator.

Indexing features

This section covers various indexing features. It includes information about descending indexes, included non-key columns, filtered indexes and statistics, columnstore indexes, and inline index definition. The features are covered in the order in which they were added to SQL Server.

Descending indexes

With SQL Server, you can indicate the direction of key columns in an index definition. By default, the direction is ascending, but using the DESC keyword you can request descending order, as in (col1, col2 DESC).

Indexes on disk-based tables have a doubly linked list in their leaf level. So SQL Server can scan the rows in the leaf in forward and backward order. As an aside, as you will learn in Chapter 10, BW-Tree indexes on memory-optimized tables are unidirectional. But back to B-tree-based indexes on disk-based tables, at the beginning it might seem like there’s no need for descending indexes, but there are a few use cases.

As it turns out, the storage engine is currently able to process only forward scans with parallelism. Whenever you have a backward scan, it is processed serially. Take the following queries as an example:

-- Query 1, parallel
SELECT orderid, custid, empid, shipperid, orderdate, filler
FROM dbo.Orders
WHERE orderid <= 100000
ORDER BY orderdate;

-- Query 2, serial
SELECT orderid, custid, empid, shipperid, orderdate, filler
FROM dbo.Orders
WHERE orderid <= 100000
ORDER BY orderdate DESC;

Figure 2-48 shows the execution plans for these queries.

FIGURE 2-48 Plans showing that there’s no parallel backward scan.

I have 8 logical CPUs on my machine. According to SQL Server’s costing formulas, with that many CPUs, a query against a table with 1,000,000 rows that filters 100,000 rows should get a parallel plan. That’s why the plan for the first query uses a parallel scan. However, because a backward scan cannot be processed with parallelism, the plan for the second query uses a serial one.

It’s interesting to see what the optimizer does when you try to force parallelism with the second query using query trace flag 8649, like so:

SELECT orderid, custid, empid, shipperid, orderdate, filler
FROM dbo.Orders
WHERE orderid <= 100000
ORDER BY orderdate DESC
OPTION(QUERYTRACEON 8649);

The plan for this query is shown in Figure 2-49.

FIGURE 2-49 Plan with forced parallelism.

Not being able to use a parallel backward-order scan, the optimizer chose a plan that uses a parallel unordered scan, and then an explicit sort operation. Clearly, it’s a very inefficient plan. If you find that parallelism is a critical factor in the performance of the query, you can arrange a descending index. Of course, if at some point Microsoft introduces support for parallel backward scans, you won’t need descending indexes for this purpose anymore.

Another curious case where descending indexes are useful is with window functions that have both a window partition clause and a window order clause. Consider the following queries:

-- Query 1
SELECT shipperid, orderdate, custid,
ROW_NUMBER() OVER(PARTITION BY shipperid ORDER BY orderdate) AS rownum
FROM dbo.Orders;

-- Query 2
SELECT shipperid, orderdate, custid,
ROW_NUMBER() OVER(PARTITION BY shipperid ORDER BY orderdate DESC) AS rownum
FROM dbo.Orders;

-- Query 3
SELECT shipperid, orderdate, custid,
ROW_NUMBER() OVER(PARTITION BY shipperid ORDER BY orderdate DESC) AS rownum
FROM dbo.Orders
ORDER BY shipperid DESC;

Currently, there is a covering index called idx_nc_sid_od_cid on the table, defined with the key list (shipperid, orderdate, custid). Examine the execution plans for these queries as shown in Figure 2-50.

FIGURE 2-50 Plans for queries with a window function.

The plan for query 1 shows that as long as there’s a covering index with a key list that starts with the partition columns in ascending order, and continues with the order columns in the order specified in the window function, the optimizer chooses an ordered scan of the index and avoids an explicit sort operation.

In query 2, the window function’s specification is similar to the one in query 1, but with descending order for the window order column orderdate. Theoretically, the optimizer could have chosen a plan that scans our covering index in descending order. After all, absent a presentation ORDER BY clause, SQL Server might return the rows in any order in the output. But it seems like SQL Server somehow wants to process the rows in ascending order of the window partition elements, so it adds an explicit sort operation.

Oddly, as you can see in the plan for query 3, if you do add a presentation ORDER BY clause with the shipperid column in descending order, suddenly the optimizer figures that it can use a backward scan both to compute the window function and to support the desired presentation order. I learned this last bit from Brad Shultz, mind you, while presenting a session in front of hundreds of people.

Another use case for descending indexes is when SQL Server needs to process rows based on multiple columns with opposite directions. For example, if your query has an ORDER BY clause with col1, col2 DESC, it can benefit from an index with the key list col1, col2 DESC or col1 DESC, col2. An index with both columns in ascending order isn’t optimal; SQL Server would still need to explicitly sort the rows.

As an anecdote, almost two decades ago, shortly after SQL Server 2000 was released, my friend Wayne Snyder discovered one of the most amazing bugs I’ve seen in SQL Server. If you created a clustered index with col1 DESC as the key, and issued a DELETE statement with the filtercol1 > @n, SQL Server deleted all rows where col1 < @n. This bug existed in SQL Server 2000 RTM and, of course, was fixed in Service Pack 1.

Included non-key columns

When you define a nonclustered index, you specify a vector of columns as the key list to determine the order of the rows in the index. SQL Server can perform ordered scans and range scans based on this key list to support operations such as ordering, filtering, grouping, joining, and others. However, if you need to add columns to the index for coverage purposes (to avoid lookups) and those columns don’t serve any ordering-related purpose, you add those columns in a designated INCLUDE clause.

Unlike key columns, included columns appear only in the index leaf rows. Also, SQL Server imposes fewer restrictions on those. For example, the key list cannot have more than 16 columns, whereas included columns can. The key list cannot have more than 900 bytes, whereas included columns can. The key list cannot have special types like XML and other large object types, whereas the include list can. Moreover, when you update a row in the table, naturally SQL Server needs to update all respective index rows that contain the updated columns. If an index key column value changes, the sort position of the row might change, in which case SQL Server will need to relocate the row. If an included column value changes, the sort position remains the same, and the update can happen in place (assuming the row doesn’t expand).

As an example for a use case for the INCLUDE clause, consider the following query:

SELECT orderid, custid, empid, shipperid, orderdate, filler
FROM dbo.Orders
WHERE custid = 'C0000000001';

I showed this query earlier as part of the discussion about the access method unordered nonclustered index scan + lookups, and I provided the query execution plan in Figure 2-31. At the moment, there is no optimal index for this query. The plan scans the entire leaf level of some noncovering nonclustered index that contains the custid column as a nonleading key, and then it applies lookups for the matching cases. The execution of this plan performed 4,006 logical reads on my system.

A far more optimal index is one defined with custid as the key column to support the filter, and all remaining columns defined as included columns to avoid lookups, like so:

CREATE INDEX idx_nc_cid_i_oid_eid_sid_od_flr ON dbo.Orders(custid)
INCLUDE(orderid, empid, shipperid, orderdate, filler);

Run the query again:

SELECT orderid, custid, empid, orderdate, filler
FROM dbo.Orders
WHERE custid = 'C0000000001';

The plan for this query is shown in Figure 2-51.

FIGURE 2-51 Plan that uses an index with included columns.

I got only 5 logical reads reported for this query.

When you’re done, run the following code for cleanup:

DROP INDEX dbo.Orders.idx_nc_cid_i_oid_eid_sid_od_flr;

Filtered indexes and statistics

A filtered index is an index on a subset of rows from the underlying table defined based on a predicate. You specify the predicate in a WHERE clause as part of the index definition. Filtered indexes are cheaper to create and maintain than nonfiltered ones because only modifications to the relevant subset of rows need to be reflected in the index. Also, filtered distribution statistics (histograms) are more accurate than nonfiltered statistics. That’s because the maximum number of steps in a histogram is 200, and with filtered statistics that number is used to represent a smaller set of rows. Furthermore, because the histogram is created on the leading key of the index only for the subset of rows that satisfy the index filter, effectively you get a quality of estimates as if you had a multicolumn histogram.

In cases where the index itself is not really important but statistics are, you can also create filtered statistics. You do so using the CREATE STATISTICS command, and specify the filter predicate in a WHERE clause.

As an example of a filtered index, suppose that you often query orders for the ship country USA and a certain order date period (since the beginning of the week, month, year). Perhaps you don’t issue similar queries for other ship countries as frequently. You need to speed up the queries specifically for the USA. You create an index with a filter based on the predicate shipcountry = N‘USA’ and specify the orderdate column as the key. If it’s important for you to avoid lookups, you will want to specify all remaining columns from the query as included columns. Run the following code to create such a filtered index:

USE TSQLV3;

CREATE NONCLUSTERED INDEX idx_USA_orderdate
ON Sales.Orders(orderdate)
INCLUDE(orderid, custid, requireddate)
WHERE shipcountry = N'USA';

Queries such as the following will then greatly benefit from the new index:

SELECT orderid, custid, orderdate, requireddate
FROM Sales.Orders
WHERE shipcountry = N'USA'
AND orderdate >= '20140101';

The execution plan for this query is shown in Figure 2-52.

FIGURE 2-52 Plan with a filtered index and an inaccurate cardinality estimate.

Because the index filter matches the query filter, the optimizer considered the index as potentially useful. By the way, if the query filter is a subinterval of the index filter, the index can still be used. For example, if the index filter is col1 > 10 and the query filter is col1 > 20, the index can be used. Back to our example, because the index key column matches the column in the query’s range predicate, the optimizer could use a seek and a range scan to get the qualifying rows. Because the index covers the query, there was no need for lookups. The index is optimal for this query.

Curiously, despite what I said about the improved quality of cardinality estimates with filtered indexes, if you look at the query plan in Figure 2-52, the estimate doesn’t seem to be very accurate. In fact, it reflects the estimate for the filter based on the orderdate column alone. The thing is that here you’re not doing anything with the filtered rows, so the optimizer doesn’t really need a more accurate estimate. For example, if you add ORDER BY orderid to the query, you will see that the estimated number of rows coming out of the sort will be accurate.

An interesting tip I learned from Paul White is that if you add the filtered column (shipcountry in our case) to the index—for example, as an included column—the estimate will be based on the filtered statistics to begin with. With this in mind, re-create the index with shipcountry as an included column, like so:

CREATE NONCLUSTERED INDEX idx_USA_orderdate
ON Sales.Orders(orderdate)
INCLUDE(orderid, custid, requireddate, shipcountry)
WHERE shipcountry = N'USA'
WITH ( DROP_EXISTING = ON );

Rerun the query:

SELECT orderid, custid, orderdate, requireddate
FROM Sales.Orders
WHERE shipcountry = N'USA'
AND orderdate >= '20140101';

The execution plan for this query is shown in Figure 2-53.

FIGURE 2-53 Plan with a filtered index and an accurate cardinality estimate.

Observe that this time the estimate is accurate.

You can also use filtered indexes to solve a common request related to enforcing data integrity. The UNIQUE constraint supported by SQL Server treats two NULLs as equal for the purposes of enforcing uniqueness. This means that if you define a UNIQUE constraint on a NULLable column, you are allowed only one row with a NULL in that column. In some cases, though, you might need to enforce the uniqueness only of non-NULL values but allow multiple NULLs. Standard SQL does support such a kind of UNIQUE constraint, but SQL Server never implemented it. With filtered indexes, it’s quite easy to handle this need. Simply create a unique filtered index based on a predicate in the form WHERE <column> IS NOT NULL. As an example, run the following code to create a table called T1 with such a filtered index on the column col1:

IF OBJECT_ID(N'dbo.T1', N'U') IS NOT NULL DROP TABLE dbo.T1;
CREATE TABLE dbo.T1(col1 INT NULL, col2 VARCHAR(10) NOT NULL);
GO
CREATE UNIQUE NONCLUSTERED INDEX idx_col1_notnull ON dbo.T1(col1) WHERE col1 IS NOT NULL;

Run the following code in an attempt to insert two rows with the same non-NULL col1 value:

INSERT INTO dbo.T1(col1, col2) VALUES(1, 'a'), (1, 'b');

The attempt fails with the following error:

Msg 2601, Level 14, State 1, Line 1023
Cannot insert duplicate key row in object 'dbo.T1' with unique index 'idx_col1_notnull'. The
duplicate key value is (1).
The statement has been terminated.

Try to insert two rows with a NULL in col1:

INSERT INTO dbo.T1(col1, col2) VALUES(NULL, 'c'), (NULL, 'd');

This time the code succeeds.

When you’re done, run the following code for cleanup:

USE TSQLV3;
DROP INDEX idx_USA_orderdate ON Sales.Orders;
DROP TABLE dbo.T1;

Columnstore indexes

Columnstore technology is a game changer in the database world. It was introduced initially in SQL Server 2012 and significantly improved in SQL Server 2014. This technology targets mainly data-warehousing workloads. Consider the classic star schema model for data warehouses as shown in Figure 2-54.

FIGURE 2-54 Star schema.

You have the dimension tables that keep track of the subjects you analyze the data by, like customers, employees, products, and time. Each dimension table has a surrogate key. The bulk of the data resides in the Fact table. This table has a column for the surrogate key of each of the dimension tables, plus columns representing measures like quantities and amounts. The traditional internal representation of the data in SQL Server before the introduction of columnstore technology has always been based on rowstore technology. This means that the data is stored and processed in a row-oriented mode. With the growing volume of data in data warehouses in recent years, rowstore technology tends to be inefficient on a number of levels, and columnstore technology addresses those inefficiencies.

To understand why rowstore is inefficient for large data warehouse environments, consider the typical data warehouse queries (also known as star join queries). They usually join the Fact table with some of the dimension tables, filter, group, and aggregate. Here’s an example of a typical data warehouse query in our PerformanceV3 database:

USE PerformanceV3;
SET STATISTICS IO, TIME ON; -- turn on performance statistics

SELECT D1.attr1 AS x, D2.attr1 AS y, D3.attr1 AS z,
COUNT(*) AS cnt, SUM(F.measure1) AS total
FROM dbo.Fact AS F
INNER JOIN dbo.Dim1 AS D1
ON F.key1 = D1.key1
INNER JOIN dbo.Dim2 AS D2
ON F.key2 = D2.key2
INNER JOIN dbo.Dim3 AS D3
ON F.key3 = D3.key3
WHERE D1.attr1 <= 10
AND D2.attr1 <= 15
AND D3.attr1 <= 10
GROUP BY D1.attr1, D2.attr1, D3.attr1;

The execution plan for this query is shown in Figure 2-55.

FIGURE 2-55 Plan for a star join query against a rowstore.

I got the following performance statistics for this query on my system:

Table 'Fact'. Scan count 122, logical reads 29300
CPU time = 890 ms, elapsed time = 490 ms.

The Fact table in the sample database has only 2,500,000 rows. Usually, data warehouses have much bigger tables. Our table is big enough, though, to justify a parallel plan and to allow me to illustrate the differences between rowstore and columnstore technologies. The bigger the tables are, the more advantageous it is to use columnstore technology, so keep in mind that in reality you will see much bigger differences than what you will see in my examples.

As mentioned, the rowstore technology has a number of drawbacks. There are so many possibilities in terms of indexing, causing you to spend a lot of time and energy on index tuning. If you have lots of query patterns in the system, it’s not going to be very practical for you to create the perfect covering index on the Fact table per query. You’ll end up with too many indexes. In an attempt to limit the number of indexes you create, you prioritize queries for tuning and also try to consolidate multiple queries with roughly similar indexing requirements. For example, if you have a number of queries that can benefit from indexes with the same key list but different include lists, you will probably prefer to create one index with a superset of the included columns. The result is that many queries won’t have truly optimal indexes to support them, and each query will likely end up using indexes that contain more than just the columns that are relevant to it. As you can realize, this means that queries will tend to perform more reads than the optimal number.

With rowstore, data is not compressed by default; rather, you need to explicitly request to compress it with row or page compression. Even if you do, because the data is stored a row at a time, the compression levels SQL Server can achieve are nowhere near what it can achieve with columnstore.

Another drawback of the rowstore technology is that currently the execution model for it is a row-execution model. This means that the different operators in the query plan are all limited to processing one row at a time. You can see this in the execution plan for our sample query in Figure 2-55. All operators in the plan will show the execution mode Row. (I highlighted this property for the clustered index seek against the Fact table and one of the hash joins.) A lot of CPU cycles are wasted because the operators process one row at a time. Any metadata information the operator needs to evaluate is evaluated per row. Any internal functions the operator needs to invoke are invoked per row.

Columnstore technology changes things quite dramatically. Note though that SQL Server 2012 is limited only to nonclustered, nonupdateable, columnstore indexes. SQL Server 2014 adds support for clustered, updateable indexes, making the technology much more accessible.

Use the following code to create a nonclustered columnstore index on our Fact table:

CREATE NONCLUSTERED COLUMNSTORE INDEX idx_nc_cs
ON dbo.Fact(key1, key2, key3, measure1, measure2, measure3, measure4);

You want to list all columns from the Fact table in the index. The order in which you list them isn’t significant. Unlike the key list in a rowstore index, which defines order, there is no similar concept of ordering in a columnstore index. Figure 2-56 illustrates how the data is organized in the columnstore index.

FIGURE 2-56 Columnstore applied to the Fact table.

SQL Server arranges the data in units called rowgroups. Each rowgroup has up to about 1,000,000 rows (more precisely, up to 2²⁰). You can find information about the rowgroups by querying the view sys.column_store_row_groups. Each rowgroup is split into the individual column segments, and each column segment is stored in a highly compressed form on a separate set of pages. You can find information about the column segments in the view sys.column_store_segments, including the minimum and maximum values in the column segment. SQL Server reduces storage requirements by using dictionaries that map entry numbers to the actual larger values. SQL Server always uses dictionaries for strings, and sometimes also for other types when there are few enough distinct values. You can find information about the dictionaries in the view sys.column_store_dictionaries.

Run our sample query again after creating the columnstore index:

SELECT D1.attr1 AS x, D2.attr1 AS y, D3.attr1 AS z,
COUNT(*) AS cnt, SUM(F.measure1) AS total
FROM dbo.Fact AS F
INNER JOIN dbo.Dim1 AS D1
ON F.key1 = D1.key1
INNER JOIN dbo.Dim2 AS D2
ON F.key2 = D2.key2
INNER JOIN dbo.Dim3 AS D3
ON F.key3 = D3.key3
WHERE D1.attr1 <= 10
AND D2.attr1 <= 15
AND D3.attr1 <= 10
GROUP BY D1.attr1, D2.attr1, D3.attr1;

The execution plan for this query is shown in Figure 2-57.

FIGURE 2-57 Plan for a star join query against a columnstore.

I got the following performance statistics for this query on my system:

Table 'Fact'. Scan count 8, logical reads 13235
CPU time = 172 ms, elapsed time = 185 ms.

As mentioned, our Fact table is pretty small in data warehousing terms. In practice, you will tend to work with much bigger tables and you will get much bigger performance differences between rowstore and columnstore.

One of the greatest things about the columnstore technology is that it pretty much eliminates the need to do index tuning on the Fact table. You just create one index. To fulfill a query, SQL Server constructs the result set only from the relevant columns. This is quite profound if you think about it; it’s as if you have all possible covering indexes without really needing to create a separate index for each case. Also, the fact that SQL Server constructs the result set only from the relevant columns tends to result in a significant reduction of I/O costs compared to rowstore.

Two other aspects of the columnstore technology tend to further reduce I/O costs. As mentioned, the level of compression that Microsoft managed to achieve with columnstore is much higher than with rowstore. Furthermore, remember that SQL Server records internally the minimum and maximum values of each column segment. If your query filters by a certain column, and the filtered values fall outside of the range covered by a column segment, the entire respective rowgroup is excluded. This capability is known as segment elimination.

An interesting aspect of the way the columnstore technology was implemented in SQL Server is that it is memory optimized, but it doesn’t require the entire data set to fit in memory. The columnstore technology also greatly benefits from parallel processing.

I described some aspects of the technology that tend to reduce I/O costs. There’s an aspect of the technology that tends to reduce CPU costs. Along with the columnstore technology, Microsoft introduced batch execution in SQL Server. A batch consists of a vectorized form of the relevant columns for a subset of the rows. Usually, the batch size is close to a thousand rows. Operators that were enhanced to support batch mode process a batch at a time instead of a row at a time. Internal functions that the operator executes use a batch as their input instead of a row. In the plan for our sample query, the operators that use batch mode are Columnstore Index Scan, all Hash operators, and the Compute Scalar operator. Figure 2-57 highlights two of the operators that use batch mode in this plan. Such operators will apply fewer iterations. Also, they evaluate the metadata information per batch instead of per row. All this translates to fewer CPU cycles. Currently, batch mode is used only when the data is organized as columnstore, but there’s nothing inherent in the technology that prevents it from being used also with rowstore. So perhaps we will see such support in the future.

As mentioned, support for columnstore in SQL Server 2012 was limited in a number of ways. You could create only a nonclustered columnstore index, which meant you had to create it in addition to the main rowstore-based representation of the data. With very large data warehouses, you have to consider the extra space requirements and the maintenance of two different representations of your data. The biggest limitation, though, is that once you create a nonclustered columnstore index, the table becomes nonupdateable. One way around this limitation is to maintain two tables with the same structure. One is a static partitioned table with a nonclustered columnstore index. Another is a trickle table without a columnstore index that absorbs the real-time changes. As soon as you are ready to make the trickle table part of the partitioned table, you create the nonclustered columnstore index on it, switch it into the partitioned table, and create a new trickle table to absorb the real-time changes. This solution also requires you to query both tables and unify the results.

The SQL Server 2012 implementation also has a number of limitations with the batch-execution feature. There’s a limited set of operators that support batch execution, and those that do, in some cases, will have to revert to row mode. For example, take the classic hash join algorithm, which is typically used in star join queries. The hash join operator can use batch execution only if the logical join type is an inner join; it always uses row mode with outer joins. Similarly, scalar aggregates are limited to row mode. In addition, if an operator doesn’t have enough memory and has to spill to tempdb, it switches to row mode. The process of switching from one mode to another is very static and can be done only at very specific points in the plan.

The SQL Server 2012 implementation is also more limited in its data type support with columnstore indexes. For example, it doesn’t support NUMERIC with a precision beyond 18, DATETIMEOFFSET with a precision beyond 2, BINARY, VARBINARY, UNIQUEIDENTIFIER, and others.

SQL Server 2014 has a number of significant improvements to the columnstore technology. The biggest one is support for clustered, updateable, columnstore indexes. Note, though, that if you create one, it cannot be unique, and you cannot create any other indexes on the table. As an example, the following code creates a table called FactCS with a clustered columnstore index and populates it with the rows from the table Fact:

CREATE TABLE dbo.FactCS
(
key1 INT NOT NULL,
key2 INT NOT NULL,
key3 INT NOT NULL,
measure1 INT NOT NULL,
measure2 INT NOT NULL,
measure3 INT NOT NULL,
measure4 NVARCHAR(50) NULL,
filler BINARY(100) NOT NULL DEFAULT (0x)
);

CREATE CLUSTERED COLUMNSTORE INDEX idx_cl_cs ON dbo.FactCS;

INSERT INTO dbo.FactCS WITH (TABLOCK) SELECT * FROM dbo.Fact;

When you use large-enough bulk inserts (102,400 rows or more) to add data to the table, SQL Server converts batches of up to 1,048,576 rows to columnstore format. When you perform nonbulk trickle inserts, SQL Server stores those in a rowgroup that uses a normal B-tree rowstore representation. Such a rowgroup is also known as a deltastore. As long as the deltastore keeps accepting new data, it will appear in the sys.column_store_row_groups view with the state description OPEN. Once the deltastore reaches the maximum size allowed for a rowgroup (1,048,576), it will stop accepting new data and SQL Server will mark it as CLOSED. A background process called tuple mover will then convert the data from the deltastore to the compressed columnstore format. When the process is done, the state of the rowgroup will appear as COMPRESSED.

SQL Server also supports deletes and updates. A delete of a row that resides in a deltastore is processed as a regular delete from a B-tree. A delete of a row from a compressed rowgroup causes the row ID of the deleted row to be written to a delete bitmap (an actual bitmap in memory and a B-tree on disk). When you query the data, SQL Server consults the delete bitmap to know which rows to consider as deleted. An update is handled as a delete followed by an insert.

The best thing about all this is that the query-processing layer is oblivious to this split between compressed rowgroups and deltastores; the storage-engine layer takes care of the details. This means that from the user’s perspective, it’s business as usual. The user submits reads and writes against the table, and behind the scenes the storage engine handles the writing to and reading from the deltastores and compressed rowgroups. One thing you do need to be aware of is that a large delete bitmap will slow down your queries. So, after a large number of deletes and updates, it would be a good idea to rebuild the table, like so:

ALTER TABLE dbo.FactCS REBUILD;

If the table is partitioned, you can rebuild the relevant partition by adding to the code PARTITION = <partition_number>.

SQL Server 2014 makes a number of improvements in batch-mode processing. For example, it can use batch mode in hash join operators that handle outer joins, in scalar aggregates, and in operators that spill to tempdb. It also handles cases where it needs to switch from one mode to another more dynamically. SQL Server 2014 also relaxes some of the restrictions related to data types. For example, it supports NUMERIC beyond precision 18, DATETIMEOFFSET beyond precision 2, BINARY and VARBINARY (although not with the MAX specifier), and UNIQUEIDENTIFIER.

Run the following star join query with the FactCS table this time:

SELECT D1.attr1 AS x, D2.attr1 AS y, D3.attr1 AS z,
COUNT(*) AS cnt, SUM(F.measure1) AS total
FROM dbo.FactCS AS F
INNER JOIN dbo.Dim1 AS D1
ON F.key1 = D1.key1
INNER JOIN dbo.Dim2 AS D2
ON F.key2 = D2.key2
INNER JOIN dbo.Dim3 AS D3
ON F.key3 = D3.key3
WHERE D1.attr1 <= 10
AND D2.attr1 <= 15
AND D3.attr1 <= 10
GROUP BY D1.attr1, D2.attr1, D3.attr1;

Note that the first time you run the query SQL Server will likely need to refresh existing statistics and create new ones, so the parse and compile time might take a bit longer. Run the query a second time to get a sense of the more typical run time. SQL Server reported the following performance statistics for this query on my system:

Table 'FactCS'. Scan count 8, logical reads 13556
CPU time = 139 ms, elapsed time = 219 ms.

For more information about the columnstore technology and the improvements in SQL Server 2014, see the following white paper: http://research.microsoft.com/apps/pubs/default.aspx?id=193599.

When you’re done, run the following code for cleanup:

SET STATISTICS IO OFF;
SET STATISTICS TIME OFF;
DROP INDEX idx_nc_cs ON dbo.Fact;
DROP TABLE dbo.FactCS;

Inline index definition

As you will learn in Chapter 10, SQL Server 2014 introduces support for memory-optimized tables as part of the In-Memory OLTP feature. In this first implementation, DDL changes are not allowed after the table creation. To allow you to define indexes on such tables as part of the table creation, Microsoft introduced syntax for inline index definition. Because Microsoft already made the effort mainly in the parser component, it extended the support for such a syntax also for disk-based tables, including table variables.

Remember that you cannot alter the definition of table variables once you declare them, so you cannot define indexes on existing table variables. Previously, you could define indexes only on table variables through PRIMARY KEY and UNIQUE constraints as part of the table definition, and therefore the indexes had to be unique. Now with the new inline index syntax, you can define nonunique indexes as part of the table variable definition, like so:

DECLARE @T1 AS TABLE
(
col1 INT NOT NULL
INDEX idx_cl_col1 CLUSTERED, -- column index
col2 INT NOT NULL,
col3 INT NOT NULL,
INDEX idx_nc_col2_col3 NONCLUSTERED (col2, col3) -- table index
);

Just like with constraints, you can define column-level indexes as part of a column definition and table-level indexes based on a composite key list as a separate item. Note that in the SQL Server 2014 implementation, inline indexes do not support the options UNIQUE, INCLUDE, and WHERE. For uniqueness, define the indexes like you used to indirectly through PRIMARY KEY or UNIQUE constraints.

Prioritizing queries for tuning with extended events

If you experience general performance problems in your system, besides trying to find and fix the bottlenecks, a common thing to do is to tune queries to be more efficient. The tricky part is that if you have lots of query patterns in the system, it’s not realistic to try and tune them all. You want to prioritize the queries for tuning so that you can spend more time on cases that, when tuned, will have a bigger impact on the system as a whole.

You need to decide which performance measure to use to prioritize the queries. It could be duration because that’s the user’s perception of performance. But it could also be that you identified a specific bottleneck in the system and need to rely on related measures. For example, if you identify a bottleneck in the I/O subsystem, you naturally will want to focus on I/O-related measures like writes and reads.

To measure query performance, you can capture a typical workload in your system using an Extended Events session with statement completed events. Remember that statement completed events carry performance information. For demonstration purposes, I’ll submit the sample workload with ad hoc queries from a specific SSMS session, so I’ll capture the sql_statement_completed event and filter by the session ID of the session in question. If the queries are submitted in your environment from stored procedures, you will need to capture the sp_statement_completedevent and apply any filters that are relevant to you.

A critical element that can help you prioritize which queries to tune is the query_hash action. It’s available to statement completed events starting with SQL Server 2012. This is a hash value that represents the template, or parameterized, form of the query string. Query strings that have the same template will get the same query hash value even if their input values are different. After you capture the workload, you group the events by the query hash value and order the groups (query templates) by the total relevant performance measure (say, duration in our example), descending. Then you spend more time and energy on the top templates.

Use the following code to create an Extended Events session that will capture the performance workload from the specified session into the specified target file (make sure to replace the session ID and file path with the ones relevant to you):

CREATE EVENT SESSION query_perf ON SERVER
ADD EVENT sqlserver.sp_statement_completed(
ACTION(sqlserver.query_hash)
WHERE (sqlserver.session_id=(54))),
ADD EVENT sqlserver.sql_statement_completed(
ACTION(sqlserver.query_hash)
WHERE (sqlserver.session_id=(54)))
ADD TARGET package0.event_file(SET filename=N'C:\Temp\query_perf.xel');

Use the following code to start the session:

ALTER EVENT SESSION query_perf ON SERVER STATE = START;

Assuming that the following set of queries represents your typical workload, run it a few times from the source SSMS session (54 in my case):

SELECT orderid, custid, empid, shipperid, orderdate
FROM dbo.Orders
WHERE orderid >= 1000000;

SELECT orderid, custid, empid, shipperid, orderdate
FROM dbo.Orders
WHERE custid = 'C0000000001';

SELECT orderid, custid, empid, shipperid, orderdate
FROM dbo.Orders
WHERE orderdate = '20140101';

SELECT orderid, custid, empid, shipperid, orderdate
FROM dbo.Orders
WHERE orderid >= 1000001;

SELECT orderid, custid, empid, shipperid, orderdate
FROM dbo.Orders
WHERE custid = 'C0000001000';

SELECT orderid, custid, empid, shipperid, orderdate
FROM dbo.Orders
WHERE orderdate = '20140201';

When you’re done running the workload, run the following code to stop the session:

ALTER EVENT SESSION query_perf ON SERVER STATE = STOP;

The event data was captured in the target file in XML format. Use the following code to copy the data from the file through the table function sys.fn_xe_file_target_read_file into a temporary table called #Events:

SELECT CAST(event_data AS XML) AS event_data_XML
INTO #Events
FROM sys.fn_xe_file_target_read_file('C:\Temp\query_perf*.xel', null, null, null) AS F;

Query the #Events table, and then extract the event columns from the XML using the value() method, placing them into a temporary table called #Queries, like so:

SELECT
event_data_XML.value ('(/event/action[@name=''query_hash'' ]/value)[1]', 'NUMERIC(38, 0)')
AS query_hash,
event_data_XML.value ('(/event/data [@name=''duration'' ]/value)[1]', 'BIGINT' )
AS duration,
event_data_XML.value ('(/event/data [@name=''cpu_time'' ]/value)[1]', 'BIGINT' )
AS cpu_time,
event_data_XML.value ('(/event/data [@name=''physical_reads'']/value)[1]', 'BIGINT' )
AS physical_reads,
event_data_XML.value ('(/event/data [@name=''logical_reads'' ]/value)[1]', 'BIGINT' )
AS logical_reads,
event_data_XML.value ('(/event/data [@name=''writes'' ]/value)[1]', 'BIGINT' )
AS writes,
event_data_XML.value ('(/event/data [@name=''row_count'' ]/value)[1]', 'BIGINT' )
AS row_count,
event_data_XML.value ('(/event/data [@name=''statement'' ]/value)[1]', 'NVARCHAR(4000)')
AS statement
INTO #Queries
FROM #Events;

CREATE CLUSTERED INDEX idx_cl_query_hash ON #Queries(query_hash);

You can now examine the query performance information conveniently by querying the #Queries table, like so:

SELECT query_hash, duration, cpu_time, physical_reads AS physreads,
logical_reads AS logreads, writes, row_count AS rowcnt, statement
FROM #Queries;

I got the following output on my system (the statement column is displayed on two lines to fit the printed page):

Query_hash duration cpu_time physreads logreads writes rowcnt statement
--------------------- --------- --------- ---------- --------- ------- ------- ----------------
3195161633580410947 234514 0 0 22 0 692 ... orderdate =
'20140101'
3195161633580410947 189375 0 0 21 0 671 ... orderdate =
'20140201'
...
14791727431994962596 272909 281000 0 4028 0 46 ... custid =
'C0000000001'
14791727431994962596 270893 281000 0 4016 0 42 ... custid =
'C0000001000'
...
15020196184001629514 405 0 0 6 0 1 ... orderid >=
1000000
15020196184001629514 354 0 0 3 0 0 ... orderid >=
1000001
...

Observe that queries that are based on the same template got the same query hash value even though their input values were different.

The final step is to issue a query against the table #Queries that groups the events by the query hash value and orders the groups by the sum of the desired performance measure (in this example, based on duration), descending, like so:

SELECT
query_hash, SUM(duration) AS sumduration,
CAST(100. * SUM(duration) / SUM(SUM(duration)) OVER() AS NUMERIC(5, 2)) AS pct,
(SELECT TOP (1) statement
FROM #Queries AS Q2
WHERE Q2.query_hash = Q1.query_hash) AS queryexample
FROM #Queries AS Q1
GROUP BY query_hash
ORDER BY SUM(duration) DESC;

I got the following output on my system:

query_hash sumduration pct queryexample
--------------------- ------------ ------ ----------------------------------------------------
14791727431994962596 3159476 58.13 SELECT orderid, custid, empid, shipperid, orderdate
FROM dbo.Orders
WHERE custid = 'C0000000001'

3195161633580410947 2267599 41.72 SELECT orderid, custid, empid, shipperid, orderdate
FROM dbo.Orders
WHERE orderdate = '20140101'

15020196184001629514 7963 0.15 SELECT orderid, custid, empid, shipperid, orderdate
FROM dbo.Orders
WHERE orderid >= 1000001

I had only three query templates in my sample workload. Naturally, in an active system you will have many more. At this point, you know which queries are more important to tune in terms of the potential effect on the system as a whole.

When you’re done, drop the temporary tables and the Extended Events session by running the following code:

DROP TABLE #Events, #Queries;
DROP EVENT SESSION query_perf ON SERVER;

Index and query information and statistics

SQL Server provides you with a wealth of performance-related information about your indexes and queries through dynamic management views (DMVs) and dynamic management functions (DMFs). This section describes some objects I find particularly useful.

Earlier in the chapter, I discussed index fragmentation. You can query the sys.dm_db_index_physical_stats function to get physical statistics about your indexes, including fragmentation levels. For example, the following code returns information about all indexes in the PerformanceV3 database (the NULLs stand for all tables, all indexes, and all partitions):

SELECT database_id, object_id, index_id, partition_number,
avg_fragmentation_in_percent, avg_page_space_used_in_percent
FROM sys.dm_db_index_physical_stats( DB_ID('PerformanceV3'), NULL, NULL, NULL, 'SAMPLED' );

To evaluate fragmentation, I examine two measures: avg_fragmentation_in_percent is the percentage of out-of-order pages (also known as logical scan fragmentation), and avg_page_space_used_in_percent is the average page population expressed as a percentage.

You want to be careful when you run such code in a production environment because the information is actually gathered when you query this object. The DETAILED mode is the most expensive one because it involves full scans of the data. The LIMITED mode is the cheapest because it examines only parent index pages (nonleaf), but for this reason it cannot report the average page population. The SAMPLED mode scans one percent of the data, and therefore is a good compromise between the two.

When you have a high level of logical scan fragmentation and you find that it negatively affects your query performance, the remedy is to rebuild or reorganize the index. Similarly, if you have too much free space, or too little (which results in splits), you rebuild the index and, if relevant, specify the desired fill factor.

Use ALTER INDEX REBUILD to rebuild the index, like so:

ALTER INDEX <index_name> ON <table_name> REBUILD WITH (FILLFACTOR = 70 /*, ONLINE = ON */);

Use ALTER INDEX REORGANIZE to reorganize the index, like so:

ALTER INDEX <index_name> ON <table_name> REORGANIZE;

The REBUILD option allows specifying a fill factor, and its result tends to be more effective than the REORGANIZE option; however, the former is an offline operation, whereas the latter is an online one. You can rebuild an index as a mostly online operation if you’re using the Enterprise edition of SQL Server by adding the ONLINE = ON option; however, an online rebuild is a longer and more expensive operation, so you better do it as an offline one if you can allow some downtime.

You need to be able to identify which indexes are used more often and which are rarely or never used. You don’t want to keep indexes that are rarely used, because they do have a negative performance effect on modifications. SQL Server collects index-usage information in the background and enables you to query it through dynamic management objects called dm_db_index_operational_stats and dm_db_index_usage_stats. The dm_db_index_operational_stats function gives you low-level I/O, locking, latching, and access-method activity information. For example, to get information about all objects, indexes, and partitions in the PerformanceV3 database, you query the function like so:

SELECT * FROM sys.dm_db_index_operational_stats( DB_ID('PerformanceV3'), null, null, null );

The dm_db_index_usage_stats view gives you usage counts of the different access methods (scan, seek, lookup):

SELECT * FROM sys.dm_db_index_usage_stats;

Recall from earlier examples, such as in Figure 2-31, that in some plans SQL Server identifies missing indexes. SQL Server also records such missing index information internally and exposes it through the dynamic management objects sys.dm_db_missing_index_details,sys.dm_db_missing_index_group_stats, sys.dm_db_missing_index_groups, and sys.dm_db_missing_index_columns. Query those objects to get missing index information that was collected since SQL Server was last restarted.

The sys.dm_db_missing_index_details view contains most of the interesting information. Run the following code to query the view in your system:

SELECT * FROM sys.dm_db_missing_index_details;

This view has a row for each missing index. The attributes equality_columns and inequality_columns report the columns that are candidates as key columns in the index. The included_columns attribute reports the columns that are candidates as included columns in the index if it’s important for you to avoid lookups.

Make sure, though, that you apply your knowledge, your experience, and some common sense in choosing which recommendations to follow. You might find redundant recommendations. For example, if two queries look the same but only slightly differ in the returned set of columns (for example, one returns col1 and col2 and the other returns col1 and col3), you will get different missing index recommendations. You can easily consolidate such recommendations and create one index with the superset of included columns (col1, col2, and col3).

The view sys.dm_db_missing_index_group_stats gives you summary statistics about groups of missing indexes, like the average user impact. At the moment, an index group contains only one index. Perhaps the thinking was to allow the future arrangement of multiple indexes in groups. Run the following code to query the view in your system:

SELECT * FROM sys.dm_db_missing_index_group_stats;

The view sys.dm_db_missing_index_groups gives you a group-to-index connection (again, at the moment, it is a one-to-one relationship). Use the following code to query the view in your system:

SELECT * FROM sys.dm_db_missing_index_groups;

Query the sys.dm_db_missing_index_columns function with a specific index handle you obtain from the sys.dm_db_missing_index_details view to get information about the columns of the missing index individually. The result will tell you if the column role is equality or inequality. Such information can help you determine which columns to specify in the index key list and which to specify in the include list. Query the function like so:

SELECT * FROM sys.dm_db_missing_index_columns(<handle>);

SQL Server supports a handy view called sys.dm_exec_query_stats that aggregates query performance information for queries whose plans are in cache. Querying such a view is so much easier than working with an Extended Events session to get query performance information, but keep in mind that this view won’t report information for queries whose plans are not in cache. The information that this view provides for each cached query plan includes, among other things, the following:

A SQL handle that you can provide as input to the function sys.dm_exec_sql_text to get the text of the parent query or batch of the current query. You also get the start and end offsets of the query that the current row represents so that you can extract it from the full parent query or batch text. Note that the offsets are zero based and are specified in bytes, although the text is Unicode (meaning two bytes of storage per character).

A plan handle that you can provide as input to the function sys.dm_exec_query_plan to get the XML form of the plan.

The creation time and last execution time.

The execution count.

Performance information, including worker (CPU) time, physical reads, logical reads, CLR time, and elapsed time. For each performance counter, you get the total for all invocations of the plan: last, minimum, and maximum.

Query hash and plan hash values. You use the former to identify queries with the same query template (similar to the query_hash action in Extended Events). With the latter, you can identify similar query execution plans.

Row counts.

Run the following code to query the view in your system:

SELECT * FROM sys.dm_exec_query_stats;

If you want to isolate top query templates that represent more work, you can group the data in the view by the query_hash attribute, and order the groups by the sum of the performance measure of interest, descending, like so (using duration in this example):

SELECT TOP (5)
MAX(query) AS sample_query,
SUM(execution_count) AS cnt,
SUM(total_worker_time) AS cpu,
SUM(total_physical_reads) AS reads,
SUM(total_logical_reads) AS logical_reads,
SUM(total_elapsed_time) AS duration
FROM (SELECT
QS.*,
SUBSTRING(ST.text, (QS.statement_start_offset/2) + 1,
((CASE statement_end_offset
WHEN -1 THEN DATALENGTH(ST.text)
ELSE QS.statement_end_offset END
- QS.statement_start_offset)/2) + 1
) AS query
FROM sys.dm_exec_query_stats AS QS
CROSS APPLY sys.dm_exec_sql_text(QS.sql_handle) AS ST
CROSS APPLY sys.dm_exec_plan_attributes(QS.plan_handle) AS PA
WHERE PA.attribute = 'dbid'
AND PA.value = DB_ID('PerformanceV3')) AS D
GROUP BY query_hash
ORDER BY duration DESC;

This query generated the following output on my system:

sample_query cnt cpu reads logical_reads duration
---------------------------------------- ---- -------- ------ -------------- ---------
SELECT ... WHERE custid = 'C0000001000' 10 3155513 92 40305 3158897
SELECT ... FROM dbo.FactCS AS F 8 2021766 1 110332 2929692
SELECT ... WHERE orderid <= 100000 1 463615 0 25339 2805217
SELECT ... WHERE orderdate = '20140201' 10 15054 0 215 2266620
SELECT ... WHERE custid LIKE '%9999' 1 1828461 0 4283 1887095

SQL Server provides you with similar views called sys.dm_exec_procedure_stats and sys.dm_exec_trigger_stats to query procedure and trigger performance statistics. Run the following code to query these views in your system:

SELECT * FROM sys.dm_exec_procedure_stats;
SELECT * FROM sys.dm_exec_trigger_stats;

SQL Server 2014 introduces a curious new DMV called sys.dm_exec_query_profiles. This view provides real-time query plan progress. It returns a row for every operator in an active actual query plan or, more precisely, for every operator and thread in the plan, with progress information. It shows the estimated row count as well as the actual row count produced so far, I/O, CPU and elapsed time information, open and close times, first and last times the operator was active, first and last times it produced a row, and more. It’s a supercool feature. Note, though, that you need to have some form of an actual query plan enabled for the view to report information about the plan. To achieve this, you can enable the Include Actual Execution Plan option in SSMS, turn on the STATISTICS PROFILE or STATISTICS XML session options, run an Extended Events session with the event query_post_execution_showplan, or a trace with the events Showplan Statistics Profile or Showplan XML Statistics Profile.

As an example, enable the Include Actual Execution Plan option in SSMS and run the following expensive query:

SELECT O1.orderid, O1.orderdate, MAX(O2.orderdate) AS mxdate
FROM dbo.Orders AS O1
INNER JOIN dbo.Orders AS O2
ON O2.orderid <= O1.orderid
GROUP BY O1.orderid, O1.orderdate;

To see the live query progress, query the view in a different query pane, like so:

SELECT * FROM sys.dm_exec_query_profiles;

I’m just waiting for some company like SQL Sentry, which developed the popular Plan Explorer tool, to come forward and, based on the information in the view, provide a graphical animated view of the real-time progress of a query plan. Who knows, perhaps by the time you read these words some company will have already done this.

Temporary objects

This section covers the use of temporary tables and table variables as tools to aid in query tuning. These objects are often misunderstood, and this misunderstanding tends to lead to suboptimal solutions. Hopefully, with the information in this section you will be equipped with correct understanding of these objects, and will use them efficiently. I’ll refer to temporary tables and table variables collectively as temporary objects.

Temporary objects are used for various purposes, not just performance related. For example, you need such objects when you have a process that requires you to set aside intermediate result sets for further processing. Because the focus of this chapter is query tuning, I’ll discuss the use of such objects mainly for query tuning purposes.

In a number of cases, you’ll find it beneficial to use temporary objects from a query-tuning perspective. One case is when you have an expensive query that generates a small result set and you need to refer to this result set multiple times. Naturally, you want to avoid repeating the work. Another case is to help improve cardinality estimates. SQL Server uses statistics to make cardinality estimates mainly in the leaf nodes of the plan, but the farther the data flows in the plan, the more likely it is that the quality of cardinality estimates will degrade. If you have a query that involves a lot of tables and a lot of manipulation, and you observe suboptimal choices in the plan that you connect to inaccurate cardinality estimates, one way to deal with those is to split the original solution into steps. Extract the part of the work, like a subset of the joins, up to the point where you see the problem in the plan, and write the result to a temporary object. Then apply the next step between the temporary object and the rest of the tables. This will give the optimizer a fresh start and, I hope, lead to a more efficient solution overall.

In the upcoming sections, I compare and contrast the different types of temporary objects that SQL Server supports. I compare local temporary tables (named with a number sign as prefix, as in #MyTable), table variables (named with the at sign as prefix, as in @MyTable), and table expressions such as derived tables and CTEs. For reference purposes, Table 2-2 has a summary of the comparison.

TABLE 2-2 Temporary objects

There are a number of common misconceptions concerning the use of temporary objects. Probably the oldest one is that some people incorrectly believe that table variables reside only in memory and have no disk-based representation. The source for this misconception is probably that people intuitively think that a variable is always a memory-only resident object. The reality is that temporary tables and table variables are represented the same way as a set of pages in tempdb and can incur disk activity.

Interestingly, the technology seems to be catching up with the misconception. Certain improvements in recent versions of SQL Server could result in reduced activity or no disk activity. For example, starting with SQL Server 2014 you can define a table type as a memory-optimized one (using the MEMORY_OPTIMIZED = ON option). Then, when you declare a table variable of this type, it is represented as a memory-optimized table. This feature is part of the In-Memory OLTP engine and is described in Chapter 10.

Another improvement in SQL Server 2014 (also backported to SQL Server 2012) is related to how SQL Server handles what’s called eager writes for bulk operations like SELECT INTO in tempdb. Normally, eager writes eagerly flush dirty pages associated with bulk operations to disk to prevent such operations from flooding the memory with new pages. With the new feature, when you perform bulk operations in tempdb, the eager-writing behavior is relaxed, not forcing the flushing of dirty pages as quickly as before. This improvement can be beneficial when you create and populate a temporary object with a bulk operation, query it, and drop it quickly. Now such work can be done with reduced activity or no disk activity.

Another common misconception concerns table expressions like derived tables and CTEs. Some intuitively think that when you use a table expression, SQL Server persists the inner query’s result in a work table if it is beneficial to do so from a performance perspective. Theoretically, such potential exists, but the reality is that, so far, Microsoft has not introduced such a capability to the engine. Any reference to a table expression gets unnested (inlined), and the query plan interacts with the underlying objects directly. This fact is especially important to remember when you have an expensive query and you need to interact with its result set multiple times—perhaps even with the same query. All references to the table expression will be inlined, and the expensive work will be repeated. It’s easy to demonstrate this behavior. Start by running the following code to enable reporting performance statistics:

SET STATISTICS IO, TIME ON;

Consider the following query, which computes yearly order counts:

SELECT YEAR(orderdate) AS orderyear, COUNT(*) AS numorders
FROM dbo.Orders
GROUP BY YEAR(orderdate);

I got the following performance statistics for this query on my system: logical reads = 2,641, CPU time = 861 ms, elapsed time = 289 ms.

You need to come up with a solution that, for each current year, returns the year with the closest count of orders and the difference between the order counts between the two years. To achieve this, you use the following query (if you’re not familiar with the CROSS APPLY operator, you can find details in Chapter 3):

WITH C AS
(
SELECT YEAR(orderdate) AS orderyear, COUNT(*) AS numorders
FROM dbo.Orders
GROUP BY YEAR(orderdate)
)
SELECT C1.orderyear, C1.numorders,
A.orderyear AS otheryear, C1.numorders - A.numorders AS diff
FROM C AS C1 CROSS APPLY
(SELECT TOP (1) C2.orderyear, C2.numorders
FROM C AS C2
WHERE C2.orderyear <> C1.orderyear
ORDER BY ABS(C1.numorders - C2.numorders)) AS A
ORDER BY C1.orderyear;

Examine the query plan for this query as shown in Figure 2-58.

FIGURE 2-58 Query plan with a CTE shows the expensive work is repeated.

The middle branch in the plan (outer input of the Nested Loops operator) represents the instance of the CTE called C1, which is referenced in the FROM clause of the outer query. It involves scanning, grouping, and aggregating the data from the Orders table once. The bottom branch in the plan (the inner input of the Nested Loops operator) represents the instance of the CTE called C2, which is referenced by the TOP (1) subquery. This branch also involves scanning, grouping, and aggregating the data from the Orders table. Because there are five years currently in the outer table C1, this branch is activated five times. In total, the expensive work was repeated six times. I got the following performance statistics from this query: logical reads = 15,696 (6 scans), CPU time = 4763 ms, elapsed time = 1938 ms.

To avoid repeating the expensive work, you should persist the result of the grouped query in a temporary table or a table variable. Here’s an example of how you can achieve this using a table variable:

DECLARE @T AS TABLE
(
orderyear INT,
numorders INT
);

INSERT INTO @T(orderyear, numorders)
SELECT YEAR(orderdate) AS orderyear, COUNT(*) AS numorders
FROM dbo.Orders
GROUP BY YEAR(orderdate)

SELECT T1.orderyear, T1.numorders,
A.orderyear AS otheryear, T1.numorders - A.numorders AS diff
FROM @T AS T1 CROSS APPLY
(SELECT TOP (1) T2.orderyear, T2.numorders
FROM @T AS T2
WHERE T2.orderyear <> T1.orderyear
ORDER BY ABS(T1.numorders - T2.numorders)) AS A
ORDER BY T1.orderyear;

The execution plans for these statements are shown in Figure 2-59.

FIGURE 2-59 Query plan with a table variable shows the expensive work is not repeated.

The first execution plan is for the code that computes the yearly aggregates and writes those to the table variable. Observe that 100 percent of the cost of the batch (in reality it’s almost 100 percent) is associated with this activity. The second execution plan is for the query against the table variable. The important thing here is that this solution executes the bulk of the work only once. The table variable is accessed six times by the second query, but it’s so tiny that this part of the work is negligible. Here are the performance statistics I got for this solution: logical reads = 2,622, CPU time = 468 ms, elapsed time = 572 ms. That’s one-sixth of the reads and less than one-third of the run time of the solution with the CTE. In short, remember that table expressions don’t have a physical side to them; they don’t get persisted anywhere. When you query them, SQL Server translates the work directly to the underlying objects. If you need to persist the result somewhere, you should be using temporary tables or table variables.

The key difference between temporary tables and table variables from a performance perspective is in the kinds of statistics that SQL Server maintains for each. SQL Server maintains the same types of statistics for temporary tables that it does for permanent ones. This includes the statistics header, density vectors, and histogram. For table variables, SQL Server maintains only the table’s cardinality, and even this limited information is typically not visible to the optimizer, as I will demonstrate shortly. Theoretically, because temporary tables have more statistics, queries involving them should get more accurate cardinality estimates, and therefore more optimal plans than table variables. In some cases, that’s what you will experience. But you know what Einstein said about theory and practice: “In theory, theory and practice are the same. In practice, they are not.” You should be aware that especially when using temporary tables in stored procedures, certain complications can lead to inaccurate estimates. I’ll elaborate on this point later. Pro tem, for simplicity’s sake, assume that with temporary tables, because of the existence of more statistics, you will tend to get better plans than with table variables.

If you tend to get better plans with temporary tables, why even bother with table variables? There are both performance reasons and logical ones. From a performance standpoint, because table variables don’t have statistics, you don’t pay the costs related to creating and maintaining those. Furthermore, you will tend to get fewer recompilations. If you think about it, when the volume of data you need to store in the temporary object is very small (just a few pages), you don’t really care much about the accuracy of the estimates. Then you might as well use table variables and benefit from the fewer recompiles. Such is the case with our last solution. When working with data beyond just a few pages, you will typically care about the quality of the estimates, and the cost of maintaining statistics and the related recompilations associated with temporary tables will typically be worth it.

I mentioned that the table cardinality is recorded for table variables but that often it’s not visible to the optimizer. This has much to do with the earlier discussion about cardinality estimates when variables are involved. I explained that because the initial optimization unit is the batch and not the statement, normally the optimizer cannot sniff variable values. The same applies to table variables. If the same batch declares, populates, and queries the table variable, the optimizer gets to optimize the query before the table variable is populated. So it cannot know what the cardinality of the table is. Like with regular variables, if you add the RECOMPILE query option, the query will get optimized after the table variable is populated; therefore, its cardinality will be visible to the optimizer. But this will cost you a recompile every time you execute the code. Another option to make the table cardinality visible is to pass the table variable as a table-valued parameter to a stored procedure, and this way get parameter sniffing.

I’ll use the following code and the related query plans to demonstrate cardinality estimates with table variables:

DECLARE @T AS TABLE
(
col1 INT NOT NULL PRIMARY KEY NONCLUSTERED,
col2 INT NOT NULL,
filler CHAR(200) NOT NULL
);

INSERT INTO @T(col1, col2, filler)
SELECT n AS col1, n AS col2, 'a' AS filler
FROM TSQLV3.dbo.GetNums(1, 100000) AS Nums;

-- Query 1
SELECT col1, col2, filler
FROM @T
WHERE col1 <= 100
ORDER BY col2;

-- Query 2
SELECT col1, col2, filler
FROM @T
WHERE col1 <= 100
ORDER BY col2
OPTION(RECOMPILE);

-- Query 3
SELECT col1, col2, filler
FROM @T
WHERE col1 >= 100
ORDER BY col2
OPTION(RECOMPILE);

The execution plans for these three queries are shown in Figure 2-60.

FIGURE 2-60 Query plans with a table variable.

The code declares a table variable called @T with three columns called col1, col2, and filler, with a nonclustered index called PK_T1 defined on col1. The code populates the table variable with 100,000 rows. The code then issues three queries. Query 1 filters the rows where col1 <= 100. Query 2 filters the rows where col1 <= 100 and has the RECOMPILE option. Query 3 filters the rows where col1 >= 100 and has the RECOMPILE option. All queries order the result rows by col2. The index PK_T1 can support the query filters, but because it’s not a covering index, if the optimizer decides to use it, lookups will be involved. Because the first two queries are very selective, they would benefit from a plan that uses the index and applies a few lookups. The last query is nonselective and would benefit from a scan.

Looking at the plans in Figure 2-60, you see inefficient choices in all three plans. In the first plan, the optimizer doesn’t have the table cardinality available, so it assumes that it’s very small. As a result, it uses a scan. In the second plan, thanks to the RECOMPILE query option, the optimizer does have the table cardinality available; however, because there’s no histogram available and you used the <= operator, it estimates 30% matches. (Remember the magic table of estimates in Table 2-1?) In the third plan—again, thanks to the RECOMPILE query option—the optimizer does have the table cardinality available, and also here the estimate is 30% because you used the operator >=. However, in this case, 30% is an underestimate, which results in a spill of the sort operation to tempdb.

Another option to make the cardinality of a table variable visible is to use trace flag 2453, which is available in SQL Server 2014 RTM CU3 and later and in SQL Server 2012 SP2 and later. This trace flag causes SQL Server to trigger recompiles based on the same thresholds that it uses for normal tables. This means that instead of forcing a recompile explicitly in every execution of the query, you will get fewer automated recompiles. When an automated recompile does happen, the table cardinality becomes available. You can find details about this trace flag here:http://support.microsoft.com/kb/2952444/en-us.

With temporary tables, you will tend to get better cardinality estimates and, consequently, better plans, as the following code demonstrates:

CREATE TABLE #T
(
col1 INT NOT NULL PRIMARY KEY NONCLUSTERED,
col2 INT NOT NULL,
filler CHAR(200) NOT NULL
);

INSERT INTO #T(col1, col2, filler)
SELECT n AS col1, n AS col2, 'a' AS filler
FROM TSQLV3.dbo.GetNums(1, 100000) AS Nums
OPTION(MAXDOP 1);
GO

-- Query 1
SELECT col1, col2, filler
FROM #T
WHERE col1 <= 100
ORDER BY col2;

-- Query 2
SELECT col1, col2, filler
FROM #T
WHERE col1 >= 100
ORDER BY col2;
GO

-- Cleanup
DROP TABLE #T;

The execution plans for the two queries are shown in Figure 2-61.

FIGURE 2-61 Query plans with a temporary table.

You can see in the plans that the cardinality estimates are accurate. As expected, the plan for the first query performs a seek and lookups. The plan for the second query is a parallel plan that performs a scan, and the sort doesn’t spill to tempdb.

I mentioned that in theory queries involving temporary tables should get better cardinality estimates, but that in practice things are not always that simple. The complications have to do with a certain caching mechanism SQL Server uses for temporary tables, table variables, and worktables SQL Server creates as part of the query plan. Recall from the discussions about the internal data structures earlier in the book that, by default, the first eight page allocations for a new table are done from mixed extents. Also remember that SQL Server uses SGAM pages to map the extents in the file that are mixed and have a page available for allocation. Temporary objects start empty, and the first few allocations for those will tend to be single-page allocations from mixed extents. Every time your modification allocates a page from a mixed extent, it needs to obtain an update latch on the respective SGAM page. As you can realize, with many temporary objects created at the same time, the situation can potentially lead to a bottleneck as a result of page-latch contention against the SGAM pages.

SQL Server has an internal caching mechanism designed to reduce such contention. Say that you execute a stored procedure where you use a temporary table or a table variable. When the procedure finishes, the temporary object is normally supposed to be destroyed. With this caching mechanism, SQL Server keeps some resources of the temporary object in cache. Those include the metadata entries, one IAM page, and one data page. The next time you (or someone else) execute the stored procedure, if such resources are available in cache, SQL Server can connect your new logical temporary object to those cached physical resources. By doing so, some page allocations are avoided and, thus, contention is reduced.

All this sounds nice in theory. In practice, there’s a small problem; apparently, SQL Server also caches and reuses the statistics for those temporary objects. The odd thing is that the internal modification counter of changes in the temporary objects, which SQL Server uses to know whetherto trigger a refresh of the statistics, accumulates across procedure calls. Consequently, if SQL Server optimizes a query against a temporary object in a stored procedure and the recompilation threshold wasn’t reached yet, it might end up using distribution information that was created earlier for a different execution of the procedure. You must be thinking, “No way!” Well, I’m afraid it’s “Yes way!” Enough said by me. I cannot do this topic as good a service as Paul White did with the following two brilliant articles:

http://sqlblog.com/blogs/paul_white/archive/2012/08/15/temporary-tables-in-stored-procedures.aspx

http://sqlblog.com/blogs/paul_white/archive/2012/08/17/temporary-object-caching-explained.aspx

Not only is the information in these articles gold, the articles are also a sheer pleasure to read.

Paul’s recommendation is that in those targeted cases where you find the problem, you can explicitly update statistics in the temporary table right before the query and add the RECOMPILE option to the query. This will trigger a refresh of the statistics and a recompile.

Back to the discussion about the differences between temporary tables and table variables: another difference is in scope and visibility. Like regular variables, a table variable is visible only to the batch that declared it. A local temporary table is visible only to the session that created it, including the entire level in which it was created as well as all inner levels in the call stack. It gets automatically destroyed (logically, at least) as soon as the level that created it goes out of scope. With ad hoc code, this means that the temporary table will even be able to cross batch boundaries. With stored procedures and triggers, as soon as the module that created the temporary table terminates, the temporary table is destroyed. This means that if you create a temporary table in one level, you will be able to interact with it in inner levels like an inner procedure, trigger, or dynamic batch. If your scope requirements dictate that the temporary object should be visible in an inner level in the call stack, you will have to use a temporary table. If you create a global temporary table (with two number signs as a prefix, as in ##MyTable), it’s visible globally (not just to the session that created it) and destroyed as soon as the session that created it terminates and there are no active references.

Another curious difference between temporary tables and table variables is what happens when you modify them in a transaction that eventually rolls back. In such a case, changes against a temporary table are undone just like changes against a permanent table. But with table variables, only a single-statement change that doesn’t complete is undone. As soon as a single-statement change completes, the changes survive a rollback. This capability of table variables makes them extremely useful in transactions and triggers that fail (or when you fail them) and where you need to keep information created by the transaction. For example, suppose that you make changes in a transaction within a TRY block. If the transaction fails, it enters a doomed state and control is passed to the CATCH block. You have to roll back the doomed transaction. But what if there’s critical information that the transaction generated and you need to save. The trick is to copy the data you need to save into table variables in the CATCH block and then roll back the transaction. The data in the table variables survives the rollback, and you can then save it wherever you need in a new transaction.

In a similar manner, suppose that you have a trigger and, in certain conditions, you need to issue a rollback from the trigger. But you need to save the information from the inserted and deleted tables. If you issue a rollback, all data in inserted and deleted disappears. If you first copy the data from inserted and deleted to the target tables and then do the rollback, the copying to the target tables will be undone too. The solution is that before you issue the rollback, you copy the data from inserted and deleted into table variables. You then issue a rollback, and after the rollback you copy the data from the table variables to the target tables.

Set-based vs. iterative solutions

One of the common dilemmas people have when they need to solve a querying task is whether to use a set-based approach or an iterative one in their solution. The relational model is based, in part, on mathematical set theory. You solve a task using a set-based approach by applying principles that are based on set theory. Here’s the definition of a set as formulated by Georg Cantor—the creator of set theory:

By a “set” we mean any collection M into a whole of definite, distinct objects m (which are called the “elements” of M) of our perception or of our thought.

—Joseph W. Dauben, Georg Cantor (Princeton University Press, 1990)

To me, a set-based solution interacts with an input table as a whole, and it doesn’t make any assumptions about the physical order of the data in terms of the correctness of the solution. You can implement such solutions with T-SQL queries without iterations. Conversely, an iterative solution manipulates one row at a time and can rely on the order of the data. You can manipulate one row at a time using a cursor mechanism or a loop with TOP (1) queries.

There are two main reasons why I generally prefer to use the set-based approach as my default and consider the iterative approach only in exceptional cases. One reason is philosophical, and the other is pragmatic. The philosophical dimension is that I feel that an approach based on strong mathematical foundations is likely going to result in more stable and robust solutions. The relational model survived so many years probably because it is based on strong mathematical foundations, unlike so many other aspects of computing that are based more on intuition and tend to be shorter lasting.

The pragmatic dimension is that iterative constructs in T-SQL are very inefficient compared to iterative constructs in many other programming languages. For example, the T-SQL WHILE loop is much slower than a while loop in C#. Similarly, working with a T-SQL cursor is much slower than working with the SQLDataReader object in .NET. So T-SQL set-based solutions tend to perform better than T-SQL iterative ones.

Interestingly, the execution model SQL Server uses when it executes a query plan for a T-SQL set-based solution is, after all, iterative. When SQL Server executes a query plan, the various operators perform iterations (hence, they are also known as iterators) to process one row at a time. But the language that SQL Server uses to perform those iterations isn’t T-SQL; rather, it is some low-level language that is highly efficient in applying them.

I consider iterative solutions in exceptional cases where the optimizer doesn’t do a good job at optimizing my set-based solution and I feel that I exhausted my tuning options. But then, I can get much better performance by implementing a CLR-based iterative solution rather than a T-SQL-based one.

To demonstrate how expensive a T-SQL iterative solution can be compared to a set-based one, I’ll use a task such as grouping and aggregating as my example. To make the problem a bit more interesting than just a basic grouping problem, I’ll add a filtering dimension as well. The task involves the Shippers and Orders tables in the PerformanceV3 database. Use the following code to add a few more shippers and orders to the sample data:

SET NOCOUNT ON;
USE PerformanceV3;

INSERT INTO dbo.Shippers(shipperid, shippername)
VALUES ('B', 'Shipper_B'),
('D', 'Shipper_D'),
('F', 'Shipper_F'),
('H', 'Shipper_H'),
('X', 'Shipper_X'),
('Y', 'Shipper_Y'),
('Z', 'Shipper_Z');

INSERT INTO dbo.Orders(orderid, custid, empid, shipperid, orderdate)
VALUES (1000001, 'C0000000001', 1, 'B', '20090101'),
(1000002, 'C0000000001', 1, 'D', '20090101'),
(1000003, 'C0000000001', 1, 'F', '20090101'),
(1000004, 'C0000000001', 1, 'H', '20090101');

The task is to identify shippers who handled orders placed prior to 2010 but haven’t handled any orders placed since then. The bulk of the work in this task is to compute the maximum order date per shipper. The qualifying shippers are the ones with a maximum order date before January 1, 2010. The optimal index for this task is a nonclustered index on the Orders table with the key list (shipperid, orderdate). Run the following code to create such an index:

CREATE NONCLUSTERED INDEX idx_nc_sid_od ON dbo.Orders(shipperid, orderdate);

The gross leaf row size in this index is about 20 bytes. So you can fit about 400 rows per leaf page. With 1,000,004 rows in the table, the index leaf level contains about 2,500 pages. There are 12 shippers in the Shippers table, out of which three are entirely new—namely, those three that have not shipped any orders yet. Nine of the shippers have shipped orders, but four of them have not shipped orders that were placed in 2010 or later. Those are the four shippers your solution should return.

One of the critical things you need to think about when tuning queries is the data characteristics. In our case, the grouping, or partitioning, column shipperid is very dense. There are only nine distinct shipper IDs in the index, each appears on average in over 100,000 rows. Your solution needs to somehow obtain the order date from the last row in each shipper section (that’s the maximum order date for the shipper), and if that date is before 2010, return the shipper.

Remember that before you test your solutions, you need to determine whether to do a cold cache test or a hot cache one, depending on the cache state you expect to have in production. I’ll assume a cold cache state for our example, so make sure to use the following code to clear the data cache before you run each solution:

CHECKPOINT;
DBCC DROPCLEANBUFFERS;

I’ll first present a cursor-based solution and then a set-based one.