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