13

I have just watched this video by Pinal Dave.

He has a SELECT query that produces ~370k reads in tempdb and ~1200 reads of the table the query is SELECTing from.

He then creates an index (Let's call it, Index1) which removes the tempdb spool and therefore improves the performance of the query. All OK so far.

However, he then creates a further index (we'll call it Index2) and leaves the Index1 intact.

He then runs his query again and despite Index2 not being used, the query performance returns to how it was originally, with the ~370k tempdb spool still in place.

He doesn't actually seem to desribe what causes this (unless I missed it)

The code to reproduce is below (thanks to Martin Smith for providing the Pastebin) This assumes a vanilla version of AdventureWorks with the standard indexes on SalesOrderDetail

SET STATISTICS XML ON;
SET STATISTICS IO ON
GO

-- The query
DBCC FREEPROCCACHE;
SELECT SalesOrderID, ProductId,SalesOrderDetailID, OrderQty
FROM   Sales.SalesOrderDetail sod
WHERE  ProductID = (SELECT AVG(ProductID)
                    FROM   Sales.SalesOrderDetail sod1
                    WHERE  sod.SalesOrderID = sod1.SalesOrderID
                    GROUP  BY sod1.SalesOrderID);
/* 
(11110 rows affected)
Table 'Worktable'. Scan count 3, logical reads 368495, physical reads 0, page server reads 0, read-ahead reads 0, page server read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob page server reads 0, lob read-ahead reads 0, lob page server read-ahead reads 0.
Table 'SalesOrderDetail'. Scan count 1, logical reads 1246, physical reads 2, page server reads 0, read-ahead reads 1284, page server read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob page server reads 0, lob read-ahead reads 0, lob page server read-ahead reads 0.
*/

here is the plan before we do anything (nested loops and table spools)

Then we create an index

CREATE NONCLUSTERED INDEX IX_Index1 ON Sales.SalesOrderDetail (SalesOrderID, ProductId) INCLUDE (SalesOrderDetailID, OrderQty);

We can then run the query again and see an improved plan and the tempdb spools gone:

DBCC FREEPROCCACHE;
SELECT SalesOrderID, ProductId,SalesOrderDetailID, OrderQty
FROM   Sales.SalesOrderDetail sod
WHERE  ProductID = (SELECT AVG(ProductID)
                    FROM   Sales.SalesOrderDetail sod1
                    WHERE  sod.SalesOrderID = sod1.SalesOrderID
                    GROUP  BY sod1.SalesOrderID);
/*
(11110 rows affected)
Table 'SalesOrderDetail'. Scan count 2, logical reads 608, physical reads 0, page server reads 0, read-ahead reads 0, page server read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob page server reads 0, lob read-ahead reads 0, lob page server read-ahead reads 0.
*/

The plan

Then we create another (not useful for our query) index

CREATE NONCLUSTERED INDEX IX_Index2 ON Sales.SalesOrderDetail (ProductId,SalesOrderID) INCLUDE (SalesOrderDetailID, OrderQty);

Then we run our query again:

-- Run the same query again
DBCC FREEPROCCACHE;
SELECT SalesOrderID, ProductId,SalesOrderDetailID, OrderQty
FROM   Sales.SalesOrderDetail sod
WHERE  ProductID = (SELECT AVG(ProductID)
                    FROM   Sales.SalesOrderDetail sod1
                    WHERE  sod.SalesOrderID = sod1.SalesOrderID
                    GROUP  BY sod1.SalesOrderID);

/*
(11110 rows affected)
Table 'Worktable'. Scan count 3, logical reads 368495, physical reads 0, page server reads 0, read-ahead reads 0, page server read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob page server reads 0, lob read-ahead reads 0, lob page server read-ahead reads 0.
Table 'SalesOrderDetail'. Scan count 1, logical reads 304, physical reads 0, page server reads 0, read-ahead reads 0, page server read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob page server reads 0, lob read-ahead reads 0, lob page server read-ahead reads 0.
*/

The reads and the plan are the same as they were before we added any indexes.

I can even try and force the use of IX_Index1:

-- Run the query an force the index
DBCC FREEPROCCACHE;
SELECT SalesOrderID, ProductId,SalesOrderDetailID, OrderQty
FROM   Sales.SalesOrderDetail sod WITH (INDEX = IX_Index1)
WHERE  ProductID = (SELECT AVG(ProductID)
                    FROM   Sales.SalesOrderDetail sod1 WITH (INDEX = IX_Index1)
                    WHERE  sod.SalesOrderID = sod1.SalesOrderID
                    GROUP  BY sod1.SalesOrderID);
/*
(11110 rows affected)
Table 'Worktable'. Scan count 3, logical reads 368495, physical reads 0, page server reads 0, read-ahead reads 0, page server read-ahead reads 0, lob logical reads 0, lob physical reads 0, lob page server reads 0, lob read-ahead reads 0, lob page server read-ahead reads 0.
Table '

and I still get the spools plan

Again thanks to Martin Smith who has observed the following;

If we create IX_Index2 and run the query, the bad plan is used (makes sense as it doesn't help the query) However, if we then create IX_Index1 and run the query, the good plan is used so suggests that it is not the fact that both indexes exist that is the problem but the order in which they are created.

I also watched this video where Pinal is presenting on the same problem. He seems to suggest that indexes reduce SELECT performance and should be dropped completely due to this problem (Unless I am misunderstanding him)

My first question is: what would cause this behaviour?

My second question is, how common is this behaviour (The second video makes me think it would be fairly common if he suggests not creating indexes at all)

0

2 Answers 2

15

Current State

In your "good" case the plan looks as below. The upper branch is sorted by SalesOrderID (and therefore also by SalesOrderID,ProductId as the grouping ensures there is only one row per SalesOrderID). The lower branch reads the index in SalesOrderID,ProductId order and they are merge joined together.

enter image description here

Your "bad" case uses a typical execution plan for a row-mode windowed aggregate (with a common subexpression spool). It isn't as bad as the linked video makes out. Reads are reported per row read not per page read for these work tables (so multiplying reads by 8 KB to calculate the data in the spool is certainly invalid) but nonetheless the "bad" case is costed more according to SQL Server's cost model so why does it choose it?

Merge join refresher

A merge join on columns X,Y requires both inputs to the merge join be ordered in a compatible manner. At a minimum both inputs must be ordered at least by the same initial column (i.e. both ordered by X or both ordered by Y). For greatest efficiency (i.e. ideally to avoid overhead of "many to many" merge join) they should generally both be ordered in the same manner for all keys involved in the equi join predicate - i.e. either ORDER BY X,Y or ORDER BY Y,X (the ASC, DESC direction of each key is not important but must be the same in both inputs)

How does it choose between ORDER BY X,Y and ORDER BY Y,X?

This seems to be a general limitation of merge join and composite join predicates. In the absence of any external reason to choose a specified ordering (e.g. an explicit ORDER BY) it will just decide a somewhat arbitrary column order.

For table sources apparently it will look for the first index it comes across that is suitable for providing the required columns in either order and adopt the key column order from that as the order required for the merge join.

The order used for index matching appears to be in reverse order of indexid. This will generally correlate with index creation order but not always (as clustered indexes are reserved an indexid of 1 or a gap in ids may be filled in following a DROP INDEX)

It will not do any analysis as to whether subsequent indexes might be better suited (e.g. as narrower or more compatible with index hints already used in the query).

I'm not 100% certain that this is the code responsible but the call stack below indicates that the implementation rule for sort merge join is looking in table metadata to find out some "Natural Sort"

enter image description here

Another example of adding an index making the plan worse - concentrating on merge join

CREATE TABLE #Test(X INT, Y INT, Filler CHAR(8000),INDEX IX1 UNIQUE /*Index id = 2*/ (X,Y));

INSERT INTO #Test (X,Y) SELECT TOP 10000 ROW_NUMBER() OVER (ORDER BY 1/0), ROW_NUMBER() OVER (ORDER BY 1/0) FROM sys.all_objects o1, sys.all_objects o2;

SET STATISTICS IO ON;

--#1 logical reads 60 uses IX1 - merge join chosen organically
SELECT t1.X, t1.Y
FROM #Test t1 
INNER JOIN #Test t2 ON t1.X = t2.X and t1.Y = t2.Y

SET STATISTICS IO OFF;
CREATE UNIQUE CLUSTERED INDEX ix2 ON #Test(Y,X) 
SET STATISTICS IO ON;

--#2 logical reads 50, Still using IX1 and merge join. The clustered index just created has an id of 1 so lower than 2. 
--IX1 no longer contains a RID so reads a bit lower than previously
SELECT t1.X, t1.Y
FROM #Test t1 
INNER JOIN #Test t2 ON t1.X = t2.X and t1.Y = t2.Y

SET STATISTICS IO OFF;
CREATE UNIQUE INDEX ix3 ON #Test(Y,X) INCLUDE (Filler);
SET STATISTICS IO ON;

--#3 logical reads 20,068 - No longer chooses MERGE join of its own accord and if forced uses more expensive index
SELECT t1.X, t1.Y
FROM #Test t1 
INNER MERGE JOIN #Test t2 ON t1.X = t2.X and t1.Y = t2.Y;

--#4 Back to 50 reads. The merge join is happy to use the order required by the ORDER BY
SELECT t1.X, t1.Y
FROM #Test t1 
INNER MERGE JOIN #Test t2 ON t1.X = t2.X and t1.Y = t2.Y
ORDER BY t1.X, t1.Y;

--#5 50 reads but now uses hash join 
SELECT t1.X, t1.Y
FROM #Test t1 
INNER JOIN #Test t2 ON t1.X = t2.X and t1.Y+0 = t2.Y+0;

--#6 50 reads, Forcing the merge join and looking at properties shows it is now seen as "many to many"
SELECT t1.X, t1.Y
FROM #Test t1 
INNER MERGE JOIN #Test t2 ON t1.X = t2.X and t1.Y+0 = t2.Y+0;

SET STATISTICS IO OFF;

--What if there is no useful index?
DROP INDEX ix3 ON #Test
DROP INDEX ix1 ON #Test
DROP INDEX ix2 ON #Test
CREATE CLUSTERED INDEX ix4 ON #Test(X)

--#7 Sorts are by X, Y 
SELECT t1.X, t1.Y
FROM #Test t1 
INNER MERGE JOIN #Test t2 ON t1.X = t2.X and t1.Y = t2.Y;

--#8 Sorts are by Y, X 
SELECT t1.X, t1.Y
FROM #Test t1 
INNER MERGE JOIN #Test t2 ON  t1.Y = t2.Y AND t1.X = t2.X;


DROP TABLE #Test
  • #1 There is a covering non clustered index on the table with columns (X,Y) - Merge join is chosen naturally (without hints) and uses index ordered scan.
  • #2 Add a clustered index with keys ordered (Y,X). Merge join still chosen naturally and using originally created index. The clustered index will have an id of 1 - which is lower than the pre-existing index.
  • #3 Add a covering nonclustered index with keys ordered (Y,X). This requires a lot more reads to scan than IX1 as includes a very wide column (Filler) - Nonetheless SQL Server now only considers (Y,X) ordered merge join and will not select merge join without hints due to the extra reads...
  • #4 ... Except if it has an additional reason to use the (X,Y) order. Adding an ORDER BY t1.X, t1.Y reverts to the original plan.
  • #5 Changing the predicate to t1.Y+0 = t2.Y+0 defeats the attempt to match (Y,X) but without hints it chooses a hash join
  • #6 Hinting the MERGE join shows it is now seen as "many to many" - Which is why SQL Server does not automatically select it. But when hinted it is able to use the narrower (X,Y) index.
  • #7 After dropping all useful indexes and creating a clustered index with single key column X it appears the merge join now wants X,Y order (rather than using the index on X to do a many to many merge join with a residual predicate)
  • #8 Inverting the order of the predicates from case #7 now also results in a different sort order for the merge join (of Y,X)

Why don't index hints work?

In the final example in your question where you use index hints SQL Server does consider merge join but as the merge join has already decided it is going to require column order of ProductId,SalesOrderID then a plan that used both the hinted indexes and a merge join would require a scan on the hinted index followed by a sort to get it into the needed order for the join. So this idea is dismissed on cost grounds (as the memo paths with <EnforceSort>PhyOp_Sort are more expensive than the eventual plan selected).

Related answer: Why does changing the declared join column order introduce a sort?

Addendum

Paul White added this insightful comment to the answer

another way to get the merge join without sorts in the question query is to change to ...WHERE ProductID + 0 = (SELECT AVG(ProductID)... Finding optimal ordering is NP-hard so database engines rely on heuristics.

In the case of the +0 workaround the merge join predicate is now on (SalesOrderID, Expr1004) = (SalesOrderID, Expr1002) so this is sufficient to prevent it trying to match an index with leading column ProductId. This does also rely on the semantics of GROUP BY guaranteeing that there is only one row in the upper input per SalesOrderID. Otherwise the extra opacity might cause SQL Server to conclude the merge join will be many to many so try other join types (as in the example now added to my example code above)

1
  • 1
    @SEarle1986 - As the compilation process clearly seems to be dependant on the order of index creation in some way I wondered if I could see any function names that appeared relevant to that. The call stack wasn't from stepping through in a debugger, just recompiling the query in a loop for a few seconds whilst Window Performance Recorder was running and then letting that resolve symbol names and poking around to see if I could see anything related to sort merge and table indexes. So at this point it could be the "offending" code - or could be a red herring. Commented Feb 17, 2020 at 22:41
6

Trying to get the better performing execution plan structure by adding hints

ImplRestrRemap

The query rule ImplRestrRemap is used on the secondary query when the index is added as a result of it being estimated to be cheaper in query bucks than the merge join. This is more of a consequence of the problem. Why it has a lower subtree cost than using a merge join in your specific case is further down below.

You can find the use of this rule by checking the output tree by adding traceflags:

OPTION(
RECOMPILE, 
QUERYTRACEON 3604,
QUERYTRACEON 8607)

You can disable the rule by adding OPTION(QUERYRULEOFF ImplRestrRemap) to the query.

SELECT SalesOrderID, ProductId,SalesOrderDetailID, OrderQty
FROM   Sales.SalesOrderDetail sod
WHERE  ProductID = (SELECT AVG(ProductID)
                    FROM   Sales.SalesOrderDetail sod1
                    WHERE  sod.SalesOrderID = sod1.SalesOrderID
                    GROUP  BY sod1.SalesOrderID)
OPTION 
(
    QUERYRULEOFF ImplRestrRemap
);

This does give a hash join instead of a merge join and a higher estimated subtree cost than the spool plan. Another difference is the use of the two created nonclustered indexes instead of accessing one twice.

enter image description here

Merge Join

When trying to add the merge join back to the plan as well as disabling the rule you will see a sort added to the query plan:

OPTION 
(
    QUERYRULEOFF ImplRestrRemap, 
    MERGE JOIN
);

enter image description here

The estimated subtree cost is higher than the hash join, this hash join's estimated subtree cost is in turn higher than the spool plan. Explaining the choice of plan without the hints.

Once again it is still using the two created NC indexes.

Index hints

If we want to force the use of the same index for both table accesses to try and get the 'sample' plan, you could add index hints.

SELECT SalesOrderID, ProductId,SalesOrderDetailID, OrderQty
FROM   Sales.SalesOrderDetail sod WITH(INDEX(IX_SalesOrderID_ProductId))
WHERE  ProductID = (SELECT AVG(ProductID)
                    FROM   Sales.SalesOrderDetail  sod1 WITH(INDEX(IX_SalesOrderID_ProductId))
                    WHERE  sod.SalesOrderID = sod1.SalesOrderID
                    GROUP  BY sod1.SalesOrderID)
OPTION 
(
    QUERYRULEOFF ImplRestrRemap, 
    MERGE JOIN
);

This adds another sort operator:

enter image description here

enter image description here

Differences

Join direction

Because of the inner & outer side join columns of the merge join being swapped

No sort merge join execution plan

<InnerSideJoinColumns>
  <ColumnReference Database="[AdventureWorks2017]" Schema="[Sales]" Table="[SalesOrderDetail]" Alias="[sod]" Column="SalesOrderID" />
  <ColumnReference Database="[AdventureWorks2017]" Schema="[Sales]" Table="[SalesOrderDetail]" Alias="[sod]" Column="ProductID" />
</InnerSideJoinColumns>
<OuterSideJoinColumns>
  <ColumnReference Database="[AdventureWorks2017]" Schema="[Sales]" Table="[SalesOrderDetail]" Alias="[sod1]" Column="SalesOrderID" />
  <ColumnReference Column="Expr1002" />
</OuterSideJoinColumns>

Double sort merge join execution plan

<InnerSideJoinColumns>
  <ColumnReference Database="[AdventureWorks2017]" Schema="[Sales]" Table="[SalesOrderDetail]" Alias="[sod]" Column="ProductID" />
  <ColumnReference Database="[AdventureWorks2017]" Schema="[Sales]" Table="[SalesOrderDetail]" Alias="[sod]" Column="SalesOrderID" />
</InnerSideJoinColumns>
<OuterSideJoinColumns>
  <ColumnReference Column="Expr1002" />
  <ColumnReference Database="[AdventureWorks2017]" Schema="[Sales]" Table="[SalesOrderDetail]" Alias="[sod1]" Column="SalesOrderID" />
</OuterSideJoinColumns>

In the sense that the better performing query plan can pass through the index key path of

--> SalesOrderId - SalesOrderId --> ProductId - ProductId (Agg)

Whereas the sorting query plan can only follow

--> ProductId (Agg) - ProductId --> SalesOrderId - SalesOrderId

And as expected due to the added sorts, the index scan is not ordered when using the double sort merge join plan

 <IndexScan Ordered="false" ForcedIndex="true" ForceSeek="false" ForceScan="false" NoExpandHint="false" Storage="RowStore">

Trying to force the better performing query plan

When trying to force the correct plan, for example running the query after creating the indexes in the order that does not provide an issue and then capturing the plan xml:

drop index if exists IX_ProductId_SalesOrderID on Sales.SalesOrderDetail;
drop index if exists IX_SalesOrderID_ProductId on Sales.SalesOrderDetail;

CREATE NONCLUSTERED INDEX IX_ProductId_SalesOrderID ON Sales.SalesOrderDetail (ProductId,SalesOrderID) INCLUDE (SalesOrderDetailID, OrderQty);
CREATE NONCLUSTERED INDEX IX_SalesOrderID_ProductId ON Sales.SalesOrderDetail (SalesOrderID, ProductId) INCLUDE (SalesOrderDetailID, OrderQty);

And then using that plan XML together with recreating the indexes in a different order:

drop index if exists IX_ProductId_SalesOrderID on Sales.SalesOrderDetail;
drop index if exists IX_SalesOrderID_ProductId on Sales.SalesOrderDetail;
CREATE NONCLUSTERED INDEX IX_SalesOrderID_ProductId ON Sales.SalesOrderDetail (SalesOrderID, ProductId) INCLUDE (SalesOrderDetailID, OrderQty);
CREATE NONCLUSTERED INDEX IX_ProductId_SalesOrderID ON Sales.SalesOrderDetail (ProductId,SalesOrderID) INCLUDE (SalesOrderDetailID, OrderQty);

The USE PLAN HINT reports an error for the same query and same indexes:

Msg 8698, Level 16, State 0, Line 1 Query processor could not produce query plan because USE PLAN hint contains plan that could not be verified to be legal for query. Remove or replace USE PLAN hint. For best likelihood of successful plan forcing, verify that the plan provided in the USE PLAN hint is one generated automatically by SQL Server for the same query.

Showing that using the same sort order in the merge join is not even possible and it has to revert back to use the sort operators as a best option for the merge join.

The reverse of this, applying the spool plan with a USE PLAN hint to the query when it is able to use the better performing Merge join plan is in fact possible.

The points brought up in this Q/A give more information as to why this is happening.

Solution

Order by

Adding an order by as specified in the Q/A previously mentioned results in the correct execution plan being chosen, even when the index create order is different.

SELECT SalesOrderID, ProductId
FROM   Sales.SalesOrderDetail2 sod 
WHERE  ProductID = (SELECT AVG(ProductID)
                    FROM   Sales.SalesOrderDetail2  sod1  
                    WHERE  sod.SalesOrderID = sod1.SalesOrderID
                    GROUP  BY sod1.SalesOrderID
                    )
ORDER BY SalesOrderID;

enter image description here

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.