If you’re not already a regular reader
of Brad Schulz’s blog, you’re missing out on some great material. In his latest entry, he is tasked with optimizing a query run against tables that have no indexes at all. The problem is, predictably, that performance is not very good. The catch is that we are not allowed to create any indexes (or even new statistics) as part
of our optimization efforts. In this post, I’m going to look at the problem from a slightly different angle, and present an alternative solution to the one Brad found. Inevitably, there’s going to be some overlap between our entries, and while you don’t necessarily need to read Brad’s post before this one, I do strongly recommend that you read it at some stage; he covers some important points that I won’t cover again here. The Example We’ll use data from the AdventureWorks database, copied to temporary unindexed tables. A script to create these structures is shown below: CREATE TABLE #Custs
(
CustomerID INTEGER NOT NULL,
TerritoryID INTEGER NULL,
CustomerType NCHAR(1) COLLATE SQL_Latin1_General_CP1_CI_AI NOT NULL,
);
GO
CREATE TABLE #Prods
(
ProductMainID INTEGER NOT NULL,
ProductSubID INTEGER NOT NULL,
ProductSubSubID INTEGER NOT NULL,
Name NVARCHAR(50) COLLATE SQL_Latin1_General_CP1_CI_AI NOT NULL,
);
GO
CREATE TABLE #OrdHeader
(
SalesOrderID INTEGER NOT NULL,
OrderDate DATETIME NOT NULL,
SalesOrderNumber NVARCHAR(25) COLLATE SQL_Latin1_General_CP1_CI_AI NOT NULL,
CustomerID INTEGER NOT NULL,
);
GO
CREATE TABLE #OrdDetail
(
SalesOrderID INTEGER NOT NULL,
OrderQty SMALLINT NOT NULL,
LineTotal NUMERIC(38,6) NOT NULL,
ProductMainID INTEGER NOT NULL,
ProductSubID INTEGER NOT NULL,
ProductSubSubID INTEGER NOT NULL,
);
GO
INSERT #Custs
(
CustomerID,
TerritoryID,
CustomerType
)
SELECT C.CustomerID,
C.TerritoryID,
C.CustomerType
FROM AdventureWorks.Sales.Customer C
WITH (TABLOCK);
GO
INSERT #Prods
(
ProductMainID,
ProductSubID,
ProductSubSubID,
Name
)
SELECT P.ProductID,
P.ProductID,
P.ProductID,
P.Name
FROM AdventureWorks.Production.Product P
WITH (TABLOCK);
GO
INSERT #OrdHeader
(
SalesOrderID,
OrderDate,
SalesOrderNumber,
CustomerID
)
SELECT H.SalesOrderID,
H.OrderDate,
H.SalesOrderNumber,
H.CustomerID
FROM AdventureWorks.Sales.SalesOrderHeader H
WITH (TABLOCK);
GO
INSERT #OrdDetail
(
SalesOrderID,
OrderQty,
LineTotal,
ProductMainID,
ProductSubID,
ProductSubSubID
)
SELECT D.SalesOrderID,
D.OrderQty,
D.LineTotal,
D.ProductID,
D.ProductID,
D.ProductID
FROM AdventureWorks.Sales.SalesOrderDetail D
WITH (TABLOCK);
The query itself is a simple join
of the four tables:
SELECT P.ProductMainID AS PID,
P.Name,
D.OrderQty,
H.SalesOrderNumber,
H.OrderDate,
C.TerritoryID
FROM #Prods P
JOIN #OrdDetail D
ON P.ProductMainID = D.ProductMainID
AND P.ProductSubID = D.ProductSubID
AND P.ProductSubSubID = D.ProductSubSubID
JOIN #OrdHeader H
ON D.SalesOrderID = H.SalesOrderID
JOIN #Custs C
ON H.CustomerID = C.CustomerID
ORDER BY
P.ProductMainID ASC
OPTION (RECOMPILE, MAXDOP 1);
Remember that these tables have no indexes at all, and only the single-column sampled statistics SQL Server automatically creates (assuming default settings). The estimated query plan produced for the test query looks like this (click to enlarge):
The Problem
The problem here is one
of cardinality estimation – the number
of rows SQL Server expects to find at each step
of the plan. The lack
of indexes and useful statistical information means that SQL Server does not have the information it needs to make a good estimate. Every join in the plan shown above estimates that it will produce just a single row as output. Brad covers the factors that lead to the low estimates in his post.
In reality, the join between the #Prods and #OrdDetail tables will produce 121,317 rows. It should not surprise you that this has rather dire consequences for the remainder
of the query plan. In particular, it makes a nonsense
of the optimizer’s decision to use Nested Loops to join to the two remaining tables.
Instead
of scanning the #OrdHeader and #Custs tables once (as it expected), it has to perform 121,317 full scans
of each. The query takes somewhere in the region
of twenty minutes to run to completion on my development machine.
A Solution
At this point, you may be thinking the same thing I was: if we really are stuck with no indexes, the best we can do is to use
hash joins everywhere.
We can force the exclusive use
of hash joins in several ways, the two most common being join and query hints. A join hint means writing the query using the INNER
HASH JOIN syntax; using a query hint involves adding OPTION (HASH JOIN) at the bottom
of the query. The difference is that using join hints also forces the order
of the join, whereas the query hint gives the optimizer freedom to reorder the joins at its discretion.
Adding the OPTION (HASH JOIN) hint results in this estimated plan:
That produces the correct output in around seven seconds, which is quite an improvement! As a purely practical matter, and given the rigid rules
of the environment we find ourselves in, we might leave things there. (We can improve the hashing solution a bit – I’ll come back to that later on).
Faster Nested Loops
It might surprise you to hear that we can beat the performance
of the
hash join solution shown above using nested loops joins exclusively, and without breaking the rules we have been set.
The key to this part is to realize that a condition like (A = B) can be expressed as (A <= B) AND (A >= B). Armed with this tremendous new insight, we can rewrite the join predicates like so:
SELECT P.ProductMainID AS PID,
P.Name,
D.OrderQty,
H.SalesOrderNumber,
H.OrderDate,
C.TerritoryID
FROM #OrdDetail D
JOIN #OrdHeader H
ON D.SalesOrderID >= H.SalesOrderID
AND D.SalesOrderID <= H.SalesOrderID
JOIN #Custs C
ON H.CustomerID >= C.CustomerID
AND H.CustomerID <= C.CustomerID
JOIN #Prods P
ON P.ProductMainID >= D.ProductMainID
AND P.ProductMainID <= D.ProductMainID
AND P.ProductSubID = D.ProductSubID
AND P.ProductSubSubID = D.ProductSubSubID
ORDER BY
D.ProductMainID
OPTION (RECOMPILE, LOOP JOIN, MAXDOP 1, FORCE ORDER);
I’ve also added LOOP JOIN and FORCE ORDER query hints to ensure that only nested loops joins are used, and that the tables are joined in the order they appear. The new estimated execution plan is:
This new query runs in under 2 seconds.
Why Is It Faster?
The main reason for the improvement is the appearance
of the eager Index Spools, which are also known as index-on-the-fly spools. If you read my Inside The Optimiser series you might be interested to know that the rule responsible is called JoinToIndexOnTheFly.
An eager index spool consumes all rows from the table it sits above, and builds a index suitable for the join to seek on. Taking the index spool above the #Custs table as an example, it reads all the CustomerID and TerritoryID values with a single scan
of the table, and builds an index keyed on CustomerID. The term ‘eager’ means that the spool consumes all
of its input rows when it starts up. The index is built in a work table in tempdb, has no associated statistics, and only exists until the query finishes executing.
The result is that each unindexed table is only scanned once, and just for the columns necessary to build the temporary index. From that point on, every execution
of the inner side
of the join is answered by a seek on the temporary index – not the base table.
A second optimization is that the sort on ProductMainID (required by the ORDER BY clause) is performed early, on just the rows coming from the #OrdDetail table. The optimizer has a good estimate for the number
of rows it needs to sort at that stage – it is just the cardinality
of the table itself. The accuracy
of the estimate there is important because it helps determine the memory grant given to the sort operation. Nested loops join preserves the order
of rows on its outer input, so sorting early is safe. (Hash joins do not preserve order in this way,
of course).
The extra lazy spool on the #Prods branch is a further optimization that avoids executing the seek on the temporary index if the value being joined (the ‘outer reference’) hasn’t changed from the last row received on the outer input. It takes advantage
of the fact that rows are still sorted on ProductMainID, so if duplicates exist, they will arrive at the join operator one after the other.
The optimizer is quite conservative about introducing index spools into a plan, because creating and dropping a temporary index is a relatively expensive operation. It’s presence in a plan is often an indication that a useful index is missing.
I want to stress that I rewrote the query in this way primarily as an educational exercise – I can’t imagine having to do something so horrible to a production system.
Improving the
Hash Join
I promised I would return to the solution that uses
hash joins. You might be puzzled that SQL Server can create three new indexes (and perform all those nested loops iterations) faster than it can perform three
hash joins. The answer, again, is down to the poor information available to the optimizer. Let’s look at the
hash join plan again:
Two
of the
hash joins have single-row estimates on their build inputs. SQL Server fixes the amount
of memory available for the
hash table based on this cardinality estimate, so at run time the
hash join very quickly runs out
of memory.
This results in the join spilling
hash buckets to disk, and any rows from the probe input that
hash to the spilled buckets also get written to disk. The join process then continues, and may again run out
of memory. This is a recursive process, which may eventually result in SQL Server resorting to a bailout join algorithm, which is guaranteed to complete eventually, but may be very slow. The data sizes in the example tables are not large enough to force a
hash bailout, but it does result in multiple levels
of hash recursion. You can see this for yourself by tracing the
Hash Warning event using the Profiler tool.
The final sort in the plan also suffers from a similar problem: it receives very little memory and has to perform multiple sort passes, saving intermediate runs to disk (the Sort Warnings Profiler event can be used to confirm this). Notice also that because
hash joins don’t preserve sort order, the sort cannot be pushed down the plan toward the #OrdDetail table, as in the nested loops plan.
Ok, so now we understand the problems, what can we do to fix it? We can address the
hash spilling by forcing a different order for the joins:
SELECT P.ProductMainID AS PID,
P.Name,
D.OrderQty,
H.SalesOrderNumber,
H.OrderDate,
C.TerritoryID
FROM #Prods P
JOIN #Custs C
JOIN #OrdHeader H
ON H.CustomerID = C.CustomerID
JOIN #OrdDetail D
ON D.SalesOrderID = H.SalesOrderID
ON P.ProductMainID = D.ProductMainID
AND P.ProductSubID = D.ProductSubID
AND P.ProductSubSubID = D.ProductSubSubID
ORDER BY
D.ProductMainID
OPTION (MAXDOP 1,
HASH JOIN, FORCE ORDER);
With this plan, each
of the inputs to the
hash joins has a good estimate, and no
hash recursion occurs. The final sort still suffers from the one-row estimate problem, and we get a single-pass sort warning as it writes rows to disk. Even so, the query runs to completion in three or four seconds. That’s around half the time
of the previous hashing solution, but still not as fast as the nested loops trickery.
Final Thoughts
SQL Server’s optimizer makes cost-based decisions, so it is vital to provide it with accurate information. We can’t really blame the performance problems highlighted here on anything other than the decision to use completely unindexed tables, and not to allow the creation
of additional statistics.
I should probably stress that the nested loops solution shown above is not one I would normally contemplate in the real world. It’s there primarily for its educational and entertainment value. I might perhaps use it to demonstrate to the sceptical that SQL Server itself is crying out for an index.
Be sure to read Brad’s original post for more details. My grateful thanks to him for granting permission to reuse some
of his material.
Paul White
Email:
[email protected]
Twitter: @PaulWhiteNZ
