Search results matching tags 'Query Plans', 'Internals', and 'Query Optimizer'

Fun with Aggregates

Paul White — Sun, 11 Mar 2012 15:49:00 GMT

There are interesting things to be learned from even the simplest queries. For example, imagine you are given the task of writing a query to list AdventureWorks product names where the product has at least one entry in the transaction history table, but fewer than ten.

One possible query to meet that specification is:

     SELECT

        p.Name

    FROM Production.Product AS p

    JOIN Production.TransactionHistory AS th ON

        p.ProductID = th.ProductID

    GROUP BY

        p.ProductID,

        p.Name

    HAVING

        COUNT_BIG(*) < 10;

That query correctly returns 23 rows (execution plan and data sample shown below):

The execution plan looks a bit different from the written form of the query: the base tables are accessed in reverse order, and the aggregation is performed before the join. The general idea is to read all rows from the history table, compute the count of rows grouped by ProductID, merge join the results to the Product table on ProductID, and finally filter to only return rows where the count is less than ten.

This ‘fully-optimized’ plan has an estimated cost of around 0.33 units. The reason for the quote marks there is that this plan is not quite as optimal as it could be – surely it would make sense to push the Filter down past the join too? To answer that, let’s look at some other ways to formulate this query. This being SQL, there are any number of ways to write logically-equivalent query specifications, so we’ll just look at a couple of interesting ones. The first query is an attempt to reverse-engineer T-SQL from the optimized query plan shown above. It joins the result of pre-aggregating the history table to the Product table before filtering:

    SELECT p.Name

    FROM

    (

        SELECT 

            th.ProductID, 

            cnt = COUNT_BIG(*) 

        FROM Production.TransactionHistory AS th 

        GROUP BY

            th.ProductID

    ) AS q1

    JOIN Production.Product AS p 

        ON p.ProductID = q1.ProductID

    WHERE

        q1.cnt < 10;

Perhaps a little surprisingly, we get a slightly different execution plan:

The results are the same (23 rows) but this time the Filter is pushed below the join! The optimizer chooses nested loops for the join, because the cardinality estimate for rows passing the Filter is a bit low (estimate 1 versus 23 actual), though you can force a merge join with a hint and the Filter still appears below the join. In yet another variation, the < 10 predicate can be ‘manually pushed’ by specifying it in a HAVING clause in the “q1” sub-query instead of in the WHERE clause as written above.

The reason this predicate can be pushed past the join in this query form, but not in the original formulation is simply an optimizer limitation – it does make efforts (primarily during the simplification phase) to encourage logically-equivalent query specifications to produce the same execution plan, but the implementation is not completely comprehensive.

Moving on to a second example, the following query specification results from phrasing the requirement as “list the products where there exists fewer than ten correlated rows in the history table”:

    SELECT p.Name

    FROM Production.Product AS p

    WHERE EXISTS 

    (

        SELECT *

        FROM Production.TransactionHistory AS th 

        WHERE th.ProductID = p.ProductID 

        HAVING COUNT_BIG(*) < 10

    );

Unfortunately, this query produces an incorrect result (86 rows):

The problem is that it lists products with no history rows, though the reasons are interesting. The COUNT_BIG(*) in the EXISTS clause is a scalar aggregate (meaning there is no GROUP BY clause) and scalar aggregates always produce a value, even when the input is an empty set. In the case of the COUNT aggregate, the result of aggregating the empty set is zero (the other standard aggregates produce a NULL). To make the point really clear, let’s look at product 709, which happens to be one for which no history rows exist:

    -- Scalar aggregate

    SELECT COUNT_BIG(*)

    FROM Production.TransactionHistory AS th 

    WHERE th.ProductID = 709;

    -- Vector aggregate

    SELECT COUNT_BIG(*)

    FROM Production.TransactionHistory AS th 

    WHERE th.ProductID = 709

    GROUP BY th.ProductID;

The estimated execution plans for these two statements are almost identical:

You might expect the Stream Aggregate to have a Group By for the second statement, but this is not the case. The query includes an equality comparison to a constant value (709), so all qualified rows are guaranteed to have the same value for ProductID and the Group By is optimized away.

In fact there are some minor differences between the two plans (the first is auto-parameterized and qualifies for trivial plan, whereas the second is not auto-parameterized and requires cost-based optimization), but there is nothing to indicate that one is a scalar aggregate and the other is a vector aggregate. This is something I would like to see exposed in show plan so I suggested it on Connect. Anyway, the results of running the two queries show the difference at runtime:

The scalar aggregate (no GROUP BY) returns a result of zero, whereas the vector aggregate (with a GROUP BY clause) returns nothing at all. Returning to our EXISTS query, we could ‘fix’ it by changing the HAVING clause to reject rows where the scalar aggregate returns zero:

    SELECT p.Name

    FROM Production.Product AS p

    WHERE EXISTS 

    (

        SELECT *

        FROM Production.TransactionHistory AS th 

        WHERE th.ProductID = p.ProductID 

        HAVING COUNT_BIG(*) BETWEEN 1 AND 9

    );

The query now returns the correct 23 rows:

Unfortunately, the execution plan is less efficient now – it has an estimated cost of 0.78 compared to 0.33 for the earlier plans. Let’s try adding a redundant GROUP BY instead of changing the HAVING clause:

    SELECT p.Name

    FROM Production.Product AS p

    WHERE EXISTS 

    (

        SELECT *

        FROM Production.TransactionHistory AS th 

        WHERE th.ProductID = p.ProductID

        GROUP BY th.ProductID

        HAVING COUNT_BIG(*) < 10

    );

Not only do we now get correct results (23 rows), this is the execution plan:

I like to compare that plan to quantum physics: if you don’t find it shocking, you haven’t understood it properly :) The simple addition of a redundant GROUP BY has resulted in the EXISTS form of the query being transformed into exactly the same optimal plan we found earlier. What’s more, in SQL Server 2008 and later, we can replace the odd-looking GROUP BY with an explicit GROUP BY on the empty set:

    SELECT p.Name

    FROM Production.Product AS p

    WHERE EXISTS 

    (

        SELECT *

        FROM Production.TransactionHistory AS th 

        WHERE th.ProductID = p.ProductID

        GROUP BY ()

        HAVING COUNT_BIG(*) < 10

    );

I offer that as an alternative because some people find it more intuitive (and it perhaps has more geek value too). Whichever way you prefer, it’s rather satisfying to note that the result of the sub-query does not exist for a particular correlated value where a vector aggregate is used (the scalar COUNT aggregate always returns a value, even if zero, so it always ‘EXISTS’ regardless which ProductID is logically being evaluated).

The following query forms also produce the optimal plan and correct results, so long as a vector aggregate is used (you can probably find more equivalent query forms):

WHERE Clause

    SELECT

        p.Name

    FROM Production.Product AS p

    WHERE 

    (

        SELECT COUNT_BIG(*) 

        FROM Production.TransactionHistory AS th

        WHERE th.ProductID = p.ProductID

        GROUP BY ()

    ) < 10;

APPLY

    SELECT p.Name

    FROM Production.Product AS p

    CROSS APPLY

    (

        SELECT NULL

        FROM Production.TransactionHistory AS th 

        WHERE th.ProductID = p.ProductID

        GROUP BY ()

        HAVING COUNT_BIG(*) < 10

    ) AS ca (dummy);

FROM Clause

    SELECT q1.Name 

    FROM

    (

        SELECT

            p.Name, 

            cnt = 

            (

                SELECT COUNT_BIG(*) 

                FROM Production.TransactionHistory AS th 

                WHERE th.ProductID = p.ProductID 

                GROUP BY ()

            )

        FROM Production.Product AS p

    ) AS q1 

    WHERE

        q1.cnt < 10;

This last example uses SUM(1) instead of COUNT and does not require a vector aggregate…you should be able to work out why :)

    SELECT q.Name 

    FROM

    (

        SELECT

            p.Name, 

            cnt = 

            (

                SELECT SUM(1)

                FROM Production.TransactionHistory AS th 

                WHERE th.ProductID = p.ProductID

            )

        FROM Production.Product AS p

    ) AS q

    WHERE q.cnt < 10;

The semantics of SQL aggregates are rather odd in places. It definitely pays to get to know the rules, and to be careful to check whether your queries are using scalar or vector aggregates. As we have seen, query plans do not show in which ‘mode’ an aggregate is running and getting it wrong can cause poor performance, wrong results, or both.

Twitter: @SQL_Kiwi
email: SQLkiwi@gmail.com

A Tale of Two Index Hints

Paul White — Wed, 22 Sep 2010 21:44:00 GMT

If you look up Table Hints in Books Online, you’ll find the following statement:

If a clustered index exists, INDEX(0) forces a clustered index scan and INDEX(1) forces a clustered index scan or seek.
If no clustered index exists, INDEX(0) forces a table scan and INDEX(1) is interpreted as an error.

The interesting thing there is that both hints can result in a scan. If that is the case, you might wonder if there is any effective difference between the two. This blog entry explores that question, and highlights an optimizer quirk that can result in a much less efficient query plan when using INDEX(0). I’ll also cover some stuff about ordering guarantees.

Test Environment

As usual, we need to create a test table:

USE     tempdb;
SET     NOCOUNT ON;
GO
IF      OBJECT_ID(N'Test.Orders', N'U')
        IS NOT NULL
        DROP TABLE Test.Orders;
GO
IF      SCHEMA_ID(N'Test')
        IS NOT NULL
        DROP SCHEMA Test;
GO
CREATE  SCHEMA Test

        CREATE  TABLE Orders
                (
                order_id    INTEGER NOT NULL,
                product_id  INTEGER NOT NULL,
                quantity    INTEGER NOT NULL,
                padding     CHAR(980) NOT NULL DEFAULT (SPACE(0)),
                
                CONSTRAINT  [PK Test.Orders order_id]
                PRIMARY KEY CLUSTERED (order_id ASC)
                );
GO
CREATE  NONCLUSTERED INDEX  [IX Test.Orders quantity]
ON      Test.Orders (quantity ASC)
        INCLUDE (padding);
GO
DECLARE @Counter    INTEGER = 1,
        @RowCount   INTEGER = 64 * 8;
        
WHILE   @Counter <= @RowCount
BEGIN
        INSERT  Test.Orders
                (order_id, product_id, quantity)
        VALUES  (
                @RowCount - @Counter,
                @RowCount - @Counter,
                @RowCount - @Counter
                );
                
        SET     @Counter += 1;
END;
GO

The test table has 512 rows, padded so that eight rows fit on each 8KB data page. The table is clustered on the order_id column, and there is a nonclustered index on the quantity column, with the padding column INCLUDEd to again ensure that eight rows fit on each nonclustered index page.

The script also deliberately generates a very high level of logical fragmentation, which we can see with the following query:

SELECT  SI.name,
        IPS.index_type_desc,
        IPS.avg_fragmentation_in_percent,
        IPS.fragment_count,
        IPS.page_count
FROM    sys.dm_db_index_physical_stats
        (
        DB_ID(),
        OBJECT_ID(N'Test.Orders', N'U'),
        DEFAULT,
        DEFAULT,
        DEFAULT
        ) IPS
JOIN    sys.indexes SI
        ON  SI.[object_id] = IPS.[object_id]
        AND SI.index_id = IPS.index_id
ORDER   BY
        IPS.index_id;
GO

The reason for the fragmentation will become apparent later on. These are the results I saw on my machine:

Background Information on Scans

A scan of a table or index processes every row, whereas a seek returns one or more rows from one or more ranges of the index.

Scan Strategies

When the SQL Server optimizer produces a plan containing a scan of an index or clustered table, the Storage Engine may be able to choose from two different strategies: scanning the pages in logical order, or the order in which they were allocated. In the first case, it follows the doubly-linked list at the leaf level of the index. In the second case, it can use the Index Allocation Map (IAM) pages to drive the scan.

A scan of a heap always uses the IAM pages of course (there is no clustered index to provide a logical page order), but this post is concerned mainly with indexes and clustered tables, so I won’t talk much more about heaps.

The advantage of an IAM-driven scan is that pages will tend to be read in physical order on the disk, which generally results in sequential I/O, and promotes effective read-ahead. How efficient scanning the pages in logical order is depends on the level of logical fragmentation: if fragmentation is high, the scan will tend to result in a high proportion of random I/Os, and read-ahead may be much less effective.

The downside to the IAM-driven scan is that it is not guaranteed to return results in logical key order (in fact it usually won’t), and there is an extra start-up cost in accessing the IAM pages, and planning the scan.

IAM-driven scans

The Storage Engine may choose an IAM-driven scan if:

The index contains 64 or more pages (giving the method a chance to recover the start-up cost);
The optimizer indicates that an ordered scan is not required for correct results; and
Either the data cannot change during the scan, or the query indicates that incorrect results are acceptable.

Hopefully the first point makes sense on it’s own. The second point refers to a flag that the optimizer can set on a scanning iterator in a query plan. This flag shows up as an “Ordered:True” or “Ordered:False” property of the iterator. When set to true, it indicates that the Storage Engine must perform a scan in logical key order for the plan to produce correct results. When set to false, it means that the order does not matter. In the latter case, the Storage Engine has the choice of performing either type of scan. The query plan does not show which type of scan was chosen.

The third point comes in two parts, but both relate to the fact that an IAM-driven scan does not take the locks necessary to prevent other concurrent operations from changing the data in the table, or moving the pages around (perhaps as the result of a page split).

The simplest way to satisfy the first part (to ensure that the data cannot be changed or moved) is to take a shared table lock. The second part (acceptable incorrect results) refers to transaction isolation level. If the scan runs at an effective isolation level of READ UNCOMMITTED (either explicitly or through the use of a NOLOCK hint) we are effectively saying that we don’t care about reading consistent data. More than that, we imply that we are happy to read the same data twice, or not at all.

The Reason for the Fragmentation

Our test table has been created with a high level of fragmentation. This allows us to see whether the Storage Engine used an IAM-driven scan or not. If the results come back in logical key order, we can be sure (in these specific examples) that the scan was performed by following the doubly-linked list at the leaf level of the index. If the results come back in allocation order, they will look very different, and we can infer that an IAM-driven scan was performed.

Important: Please don’t take any of that to mean that you can rely on query results to come back in a particular order in more general cases. The very simple tests shown here are carefully crafted to encourage the ordering behaviour I have just described, but there are no guarantees. Never rely on plan details to provide ordering – always use an ORDER BY clause if you require ordered results.

Scanning Examples

Let’s look first at two simple queries that return all columns and all rows from our test table:

-- Query 1
SELECT  T.*
FROM    Test.Orders T;
 
-- Query 2
SELECT  T.*
FROM    Test.Orders T 
ORDER   BY 
        T.order_id ASC;

Both queries produce very similar execution plans, but the first specifies “Ordered:False” while the second specifies “Ordered:True”. The second example avoids an expensive explicit Sort iterator by requiring the Storage Engine to return rows from the scan in logical key order (the clustered index is on order_id, remember).

Both queries return records ordered by the clustering key; Query 1 because the Storage Engine cannot perform an IAM-driven scan (we haven’t met all the conditions); and Query 2 because an ordered scan was requested by the optimizer.

Query 1 is not guaranteed to return records in that order, but Query 2 (almost) is. In case you are wondering what might cause Query 1 to return records in a different order, consider the effect of a parallel plan, or Enterprise Edition’s Advanced Scan feature. For anyone that follows that second link, I should mention that Advanced Scan is only possible when the Ordered flag is set to False.

An IAM-driven Scan

Query 1 above meets two of the conditions for an IAM-driven scan: the index contains at least 64 pages, and the optimizer did not specify Ordered:True. We can meet the third condition by adding a WITH (TABLOCK) hint:

SELECT  T.*
FROM    Test.Orders T WITH (TABLOCK);

We receive the following result set:

Each group of eight records (each 8KB page) comes back ordered by the clustering key, but the overall order of pages is in the order the pages were written. This is the result of an IAM-driven scan: pages in allocation order, records within the pages in clustered key order. As you may have guessed, neither of these two observed orderings can be relied on either – I mention them for pure geek interest value.

Adding the TABLOCK hint to Query 2 does not result in an IAM-driven scan, because the optimizer continues to specify Ordered:True on the scan (to avoid the sort that would be necessary to honour the ORDER BY clause).

For Query 2, the optimizer does still consider a plan with an unordered scan followed by a sort, but rejects it as being more expensive than an ordered scan. For very large tables, the optimizer may calculate that an IAM-driven scan might save more time than would be consumed by the extra sort, and a plan featuring the unordered scan + sort would be chosen. This is a heuristic optimization: the optimizer knows nothing about the actual fragmentation level of an index (though it does know how many pages it occupies).

Index Hints

Let’s now run the Query 1 test again, this time specifying INDEX(0) or INDEX(1) hints, as well as choosing to specify TABLOCK or not:

SELECT  T.* FROM Test.Orders T WITH (INDEX(0));
SELECT  T.* FROM Test.Orders T WITH (INDEX(1));
SELECT  T.* FROM Test.Orders T WITH (INDEX(0), TABLOCK);
SELECT  T.* FROM Test.Orders T WITH (INDEX(1), TABLOCK);

In all cases, the results are the same: if we specify TABLOCK, we meet the conditions for an IAM-driven scan, and the records comes back in physical order. If we omit TABLOCK, we happen to get results in clustered-key order – but we know that is just coincidental. All four query plans look exactly the same as the simple clustered index scans shown earlier, and all feature “Ordered:False”.

Let’s try the same thing with the ORDER BY clause (Query 2):

SELECT  T.* FROM Test.Orders T WITH (INDEX(0)) ORDER BY T.order_id;
SELECT  T.* FROM Test.Orders T WITH (INDEX(0), TABLOCK) ORDER BY T.order_id;
SELECT  T.* FROM Test.Orders T WITH (INDEX(1)) ORDER BY T.order_id;
SELECT  T.* FROM Test.Orders T WITH (INDEX(1), TABLOCK) ORDER BY T.order_id;

All four queries produce the same results, in the same order, and are guaranteed to do so thanks to the ORDER BY clause. The execution plans are rather different, however:

Both INDEX(1) plans produce the plan shown on the left, with the scan showing “Ordered:True”, and a cost of 0.05.
Both INDEX(0) plans produce the plan shown on the right, with the scan showing “Ordered:False”, and a cost of 0.07.

Optimizer Bug, Limitation, or “By Design”?

It seems that INDEX(0) forces “Ordered:False” on the scan. As a consequence, we get an explicit Sort iterator when the ORDER BY clause is present. Why should INDEX(0) force an unordered scan?

One can imagine a line of reasoning that says we would normally specify INDEX(0) only on a heap table, where an ordered scan is not possible. The flaw in this argument is that INDEX(1) does not enable us to force a scan of a clustered table – it will result in a seek if at all possible.

INDEX(0) and Ordered:True

Nevertheless, it is possible to produce “Ordered:True” when INDEX(0) is specified, in an INSERT, UPDATE or DELETE query. Let’s look at three alternative formulations of a trivial UPDATE query on our test table:

All three plans feature the “Ordered:True” flag, but the one with INDEX(0) includes a sort on order_id. That sort is probably redundant, since the Clustered Index Scan (with “Ordered:True”) ought to be guaranteed to produce rows in that same order. Not only will that sort slow down your query, it will require a memory grant, and might even spill to tempdb.

A Data Modification Optimization

When performing our UPDATE query, the optimizer takes into account the effect of ordering. If rows arrive at the update iterator in clustered index order, the pattern of updates will likely result in sequential I/O. If rows are in a different order, the updates will likely cause random I/O as the index is updated row by row.

Often, the optimizer may choose to pre-sort the records on the clustered index key to optimize for sequential I/O. On other occasions, it may decide that the cost of the sort would exceed the savings made – this is seen when the number of rows to be updated is very small, and the rows can be located most efficiently from a nonclustered index.

When the rows are sourced from the clustered index, the optimizer always adds the “Ordered:True” flag to maximize the chances for sequential I/O, regardless of the estimated number of rows. This explains how the Clustered Index Scan above manages to acquire the “Ordered:True” flag when INDEX(0) was specified. It seems that the optimizer misses the fact that by adding the ordering flag, the sort is now redundant.

Final Thoughts

Although I have concentrated very much on clustered indexes in this entry, I want to stress that the two scanning strategies apply to both clustered and non-clustered indexes. I created a nonclustered index on the test table so you can verify for yourself that IAM-driven scans are possible with nonclustered indexes, and the rules are exactly the same.

It is also not necessary to specify TABLOCK explicitly to get an IAM-driven scan: if the index in question happens to have row and page locks disabled (using ALTER INDEX (…) SET ALLOW_ROW_LOCKS = OFF, ALLOW_PAGE_LOCKS = OFF) the Storage Engine will recognise that a table lock has to be taken. Other circumstances like the database being read-only will also meet the underlying requirement that the data cannot change during the scan.

Beware of using NOLOCK when the other conditions for an IAM-driven scan are met. Not only might you read data that has not been committed yet, you can also read committed data twice, or not at all. Your query might also fail completely with the dreaded error: “Could not continue scan with NOLOCK due to data movement”.

Finally, watch out for unnecessary sorts in plans that use the INDEX(0) table hint – consider using INDEX(1) instead, or rewriting the query to avoid the hint altogether.

Paul White
Email: SQLkiwi@gmail.com
Twitter: @SQL_Kiwi