HEAPs o’ Trouble With Multi-Column JOINs

You would just love the database that I’m dealing with at a client site.

First of all, the database has impossible-to-decipher 5-character table names, and their column names are just as bad, so I’m dealing with objects with awful names that look like XQUMB.XUMHF and YRWNO.YWNVZ.

Second of all, every table in the database is a Heap with no primary keys or indexes defined at all.

Great, huh?

But wait… that’s not all!

There are no small simple surrogate keys to logically tie the tables together in any kind of a relationship. Many of the tables have a logical key made up of multiple columns. So when I look at the stored procedures that JOIN the tables together, I see ugly stuff like this:

select X.XUMHF
      ,X.XUMRO
      ,X.XUMBC
      ,X.XUMPU
      ,Y.YWNOQ
      ,B.BFUCP
      ,B.BFUVX
from XQUMB as X 
join YRWNO as Y on X.XUMHF=Y.YWNHF 
                and X.XUMRO=Y.YWNRO 
                and X.XUMBC=Y.YWNBC
join BRFUP as B on Y.YWNHF=B.BFUHF 
                and Y.YWNRO=B.BFURO 
                and Y.YWNBC=B.BFUBC 
                and Y.YWNCP=B.BFUCP
 

Doesn’t that look like fun?

None of the tables are really that large in terms of rows, so I figured performance would not be that big of a deal.

WRONG!

Bad assumption.

I’ve been so spoiled by only dealing with databases with well-defined keys and indexes that I never realized what a heap o’ trouble Heaps can be… especially when it comes to multi-column JOINs.

Let me illustrate with our old friend the AdventureWorks database.

Here’s a simple JOIN of 4 tables in the original database (with appropriate keys and indexes):

select p.ProductID as PID
      ,p.Name
      ,d.OrderQty
      ,h.SalesOrderNumber
      ,h.OrderDate
      ,c.TerritoryID
from AdventureWorks.Production.Product p
join AdventureWorks.Sales.SalesOrderDetail d on p.ProductID=d.ProductID
join AdventureWorks.Sales.SalesOrderHeader h on d.SalesOrderID=h.SalesOrderID
join AdventureWorks.Sales.Customer c on h.CustomerID=c.CustomerID 
order by p.ProductID
/*
PID Name                  OrderQty SalesOrderNumber OrderDate  TerritoryID
--- --------------------- -------- ---------------- ---------- -----------
707 Sport-100 Helmet, Red        1 SO43665          2001-07-01           1
707 Sport-100 Helmet, Red        2 SO43668          2001-07-01           6
707 Sport-100 Helmet, Red        4 SO43673          2001-07-01           2
. . .
999 Road-750 Black, 52           1 SO73926          2004-06-27           4
999 Road-750 Black, 52           1 SO74094          2004-06-29           9
999 Road-750 Black, 52           1 SO74143          2004-06-30          10
  
(121317 rows total in 2.7 seconds)        
*/

SSMS will spit that sorted result of 121,317 rows out in under 3 seconds.

Now let’s create some Heaps out of those 4 tables. And we will change the Products table so that its logical key is in 3 parts… instead of ProductID, we will have a multiple-column logical key of ProductMainID, ProductSubID, and ProductSubSubID. And, of course, we’ll have those same 3 columns in SalesOrderDetail to act as a (logical) foreign key reference into the Products table:

select ProductID as ProductMainID
      ,ProductID as ProductSubID
      ,ProductID as ProductSubSubID
      ,Name
into #Prods
from AdventureWorks.Production.Product
 
select SalesOrderID
      ,OrderDate
      ,SalesOrderNumber
      ,CustomerID
into #OrdHeader
from AdventureWorks.Sales.SalesOrderHeader
 
select SalesOrderID
      ,OrderQty
      ,LineTotal
      ,ProductID as ProductMainID
      ,ProductID as ProductSubID
      ,ProductID as ProductSubSubID
into #OrdDetail
from AdventureWorks.Sales.SalesOrderDetail
 
select CustomerID
      ,TerritoryID
      ,CustomerType
into #Custs
from AdventureWorks.Sales.Customer
 

Now let’s do our query again using those Heaps, but of course, we have to use multiple columns to JOIN the #Prods and #OrdDetail 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 
/*
PID Name                           OrderQty SalesOrderNumber OrderDate  TerritoryID
--- ------------------------------ -------- ---------------- ---------- -----------
878 Fender Set - Mountain                 1 SO53960          2003-09-07           1
881 Short-Sleeve Classic Jersey, S        1 SO53987          2003-09-08           9
712 AWC Logo Cap                          1 SO53987          2003-09-08           9
. . .
871 Mountain Bottle Cage                  1 SO53426          2003-08-31           6
870 Water Bottle - 30 oz.                 1 SO53426          2003-08-31           6
873 Patch Kit/8 Patches                   1 SO53426          2003-08-31           6
  
(121317 rows total in 5.7 seconds)
*/

Well, that’s not that bad. Instead of 2.7 seconds, it took 5.7 seconds. It’s not the end of the world. In fact, it kind of surprises me that---

Oops… Sorry about that. I forgot the ORDER BY clause. Silly me!

Let’s add the ORDER BY and run it again:

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
/*
OMIGOSH!!!
The addition of the ORDER BY made the query take 24 minutes!
*/

WHAT!!!??? Are you kidding me?? Just adding that ORDER BY made the time increase from 5.7 seconds to 24 minutes! The query duration increased by a whopping 25132%! Heck, I could probably sort 100,000 records myself manually with pencil and paper in under 24 minutes!

Here are the utterly shocking Profiler Statistics comparing the two queries:

/*
Description                CPU Time  Logical Reads     Duration Time
---------------------------------------------------------------------------
Query Without ORDER BY        733ms          2,825      5,675ms =  5.7 Secs
Query With ORDER BY     1,426,536ms     46,102,492  1,431,938ms = 23.9 Mins
---------------------------------------------------------------------------
*/

So why is SQL Server so slow at sorting these rows?

Well… it’s not really the Sort’s fault… it’s something else.

Take a look at the estimated plan of the first query without the ORDER BY:



All the tables are JOINed with Hash Join operators. That makes sense, considering there are no primary keys or indexes defined. A Merge Join operator would require pre-sorted (i.e. indexed) data and a Nested Loops Join operator would do a SEEK on its inner input (which requires an index). So a Hash Join is the best (and really only) choice to JOIN the tables.

Now take a look at the estimated query plan with the ORDER BY added to the query:



Hmmm… The SORT operator is not at the top (i.e. left) of the tree but is instead placed further down the tree, with the JOIN of the #Prods and #OrdDetail tables. I guess that makes sense since we wanted the query to be ORDERed BY #Prods.ProductID. But the remaining Hash Joins got converted into Nested Loops Joins.

How come?

Notice the very thin arrow lines connecting the JOIN operators… in both plans above. The optimizer estimated that only 1 row (!!) would result from the JOIN of the #Prods and #OrdDetail tables. And because only 1 row is estimated, the optimizer figured it could just use a Nested Loops Join... because, hey, there’s only 1 row, and besides, a Nested Loops Join would preserve the order of the sorted rows, whereas a Hash Join may not.

But you and I know the reality of the situation is that there is not going to be only 1 row moving in the flow up the query tree… there are going to be 121,317 rows. The estimate is waaaay off.

Here’s what the Actual plan looks like for the 24-minute-long ORDER BY query.



Note the huge thick arrow lines now? They represent the actual number of rows processed. The Nested Loops Join to the #OrdHeader table performed a Table Scan of the 31465-row #OrdHeader table 121,317 times! So that resulted in 31465 * 121317 = 3,817,239,405 rows being processed. Similarly, a whopping 2,327,466,645 rows were processed out of the #Custs table. No wonder it took 24 minutes! Our friend Nora Nested-Loops must have been thoroughly exhausted at the end of this query!

So why the gross underestimation of the rows? Why did the optimizer figure that only 1 row would result in the JOIN of #Prods and #OrdDetail?

It’s those #$@*% multiple columns in the JOIN.

Take a look at how the estimates dramatically decrease as we add an additional predicate to the JOIN condition:

select p.ProductMainID as PID
      ,p.Name
      ,d.OrderQty
from #Prods p
join #OrdDetail d on p.ProductMainID=d.ProductMainID
/*
97783.6 Rows Estimated
*/
 
select p.ProductMainID as PID
      ,p.Name
      ,d.OrderQty
from #Prods p
join #OrdDetail d on p.ProductMainID=d.ProductMainID
                  and p.ProductSubID=d.ProductSubID 
/*
156.38 Rows Estimated
*/
 
select p.ProductMainID as PID
      ,p.Name
      ,d.OrderQty
from #Prods p
join #OrdDetail d on p.ProductMainID=d.ProductMainID
                  and p.ProductSubID=d.ProductSubID 
                  and p.ProductSubSubID=d.ProductSubSubID
/*
1 Row Estimated
*/

The optimizer does use statistics to attempt to estimate the row count, but the problem is that statistics are automatically created for each column individually… they are not created for the columns collectively. So when the optimizer sees two predicates in the JOIN condition (or three), it assumes the predicates are independent and therefore more and more selective.

In reality, that is not always the case in the real world. For example, let’s say you had a JOIN condition based on Make and Model and Year of automobile. If we’re trying to join on (’Toyota’, ’Prius’, 2010), the optimizer would make estimates based on how selective ‘Toyota’ is among all other Makes and on how selective ‘Prius’ is among all other Models (regardless of Make). A Prius is very selective among all Models… it’s one of hundreds. But a Prius is not that selective among Toyotas… it’s only one of about a dozen or so.

So this is what I was dealing with in this database… Lots of multi-column JOINs between Heaps which totally annihilate performance because of bad estimates.

In my case I was not able to create any indexes… Don’t ask me why… I don’t want to talk about it… It was essentially outside the scope of the project.

I mentioned earlier that statistics are automatically created on individual columns referenced in JOIN/WHERE conditions if they don’t exist already, but statistics for collective multiple columns are NOT automatically created. The great thing about indexes, though, is that a multi-column index WILL create collective multiple-column statistics, so the optimizer can make much better estimates when dealing with multiple-column predicates. So chalk that up as another really good reason to use indexes.

Actually, we can manually create collective multi-column statistics on our own like so, and upon doing so, the query is much much faster:

create statistics Stat_PID_Main_Sub_SubSub 
  on #Prods (ProductMainID,ProductSubID,ProductSubSubID)
create statistics Stat_PID_Main_Sub_SubSub 
  on #OrdDetail (ProductMainID,ProductSubID,ProductSubSubID)
go
 
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
/*
2910ms Duration
*/

With those multi-column stats created, the estimated query plan now gets a very different shape:



Unfortunately, creating these multi-column statistics was also outside of the scope of my project with this client.

What was I to do?

I ended up going with hints… Not the greatest solution, but one that I could apply quickly to the code.

You may recall a blog post I wrote in August 2010 regarding Query Hints. In one example in that blog post, I introduced a hint to force the optimizer to use a Nested Loops Join rather than a Hash Join.

In this case, though, in dealing with the Heaps and their multi-column joins, I ended up doing the exact opposite… I introduced hints to force the use of Hash Joins rather than those pesky Nested Loops Joins.

So let’s change the query to the following, specifying a Hash Join for each Join:

select p.ProductMainID as PID
      ,p.Name
      ,d.OrderQty
      ,h.SalesOrderNumber
      ,h.OrderDate
      ,c.TerritoryID
from #Prods p
inner hash join #OrdDetail d on p.ProductMainID=d.ProductMainID
                             and p.ProductSubID=d.ProductSubID
                             and p.ProductSubSubID=d.ProductSubSubID
inner hash join #OrdHeader h on d.SalesOrderID=h.SalesOrderID
inner hash join #Custs c on h.CustomerID=c.CustomerID 
order by d.ProductMainID
/*
9701ms Duration
*/

That doesn’t run quite so quickly as the query that had the advantage of the multi-column stats, but 9.7 seconds is certainly better than 24 minutes!

The estimated query plan for the Hash Join Hint query looks like this:



It’s pretty much just like the plan for the non-ORDERBY query, except it has a SORT operator thrown in to execute at the top of the tree, after all the JOINs. When the optimizer sees Hash Join hints, it forces the query to be processed in order of how the JOINs are introduced in the query, so it first JOINs the #Prods and #OrdDetail, then the #OrdHeader, then the #Custs table.

By the way, for those of you who want to save typing, the same thing could be accomplished via the OPTION clause (instead of specifying individual JOIN hints), forcing the optimizer to use Hash Joins for every JOIN in the query:

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 d.ProductMainID
option (hash join)
/*
9701ms Duration
*/

We could force the topology of the query plan to be just like the one that resulted from creating the statistics by rewriting the query like so:

select p.ProductMainID as PID
      ,p.Name
      ,d.OrderQty
      ,h.SalesOrderNumber
      ,h.OrderDate
      ,c.TerritoryID
from #Prods p
inner hash join (#OrdDetail d 
                 inner hash join (#OrdHeader h 
                                  inner hash join #Custs c 
                                             on h.CustomerID=c.CustomerID)
                            on d.SalesOrderID=h.SalesOrderID)
           on p.ProductMainID=d.ProductMainID
           and p.ProductSubID=d.ProductSubID
           and p.ProductSubSubID=d.ProductSubSubID                
order by d.ProductMainID
 

This forces the #Custs and #OrdHeader to JOIN first, then that result is JOINed to #OrdDetail, and then that result is finally JOINed to #Prods… just like the query plan that was able to use the multi-column stats. And it runs just as fast… 2.9 seconds.

However, that code is really difficult to read and figure out what’s going on. (It’s kinda cool, though, that we have the flexibility to write it that way, dontcha think?)

So we’ll have to settle for the 9.7 second query.

But thank goodness we can bring about these changes in behavior with the use of hints. They can certainly be a godsend when you don’t have any other options available to you.

Update Dec09,2010: Paul White wrote an excellent must-read follow-up to this article, giving some wonderful additional insights. If you’re not a regular reader of his blog, I must insist that you subscribe to it immediately. It’s a gold mine of terrific material.

It's the Natural Order of Things... NOT!

In moving from the Visual FoxPro (VFP) world to the SQL Server world, the biggest thing that I had to un-learn was the concept of a “natural order” of a table. In VFP, when you add rows to a table, they ALWAYS get appended to the end of the table. No exceptions. So when you do a SELECT FROM the table, the rows will ALWAYS appear in the same order no matter what. You can create as many indexes as you like on the table, and it still won’t make any difference, because VFP will ALWAYS use the “natural order” un-indexed rows when you do a SELECT FROM the table.

All of that gets thrown out the window when it comes to SQL Server. I see many posts on the MSDN T-SQL Forum from people who present some sample data and want some kind of solution that assumes a certain order in the table. For example, here’s a typical example of a post I’ve seen many times:

My data looks like this:

Code  Quantity
----  --------
A           23
A           15
A           11
B           14
B           18
A           43
C           12

And I want to sum up the quantities by Code and get this result:

Code  TotQuantity
----  -----------
A              49
B              32
A              43
C              12

The inevitable and immediate question from others on the forum trying to help is: “You can’t do what you want unless you order on some other column. Is there a datetime column or something?” And many times, the answer is no, there is no order. This is just what they see when they do a SELECT * and they assume that this is a “natural” order of the rows as they were chronologically INSERTed into the table.

Wrong-o.

I can certainly understand that this is a natural assumption to make. Coming from the VFP world, it’s certainly the assumption I would have made… until I learned more about how SQL Server works.

Let’s see just how wrong this assumption is.

Create a table and insert 10 rows into it and let’s take a look at what we get when we do a SELECT * from it:

create table #test 
(
  col1 varchar(900) not null
 ,col2 char(1) not null
)
  
insert #test values ('B'+replicate('.',899),'N')
insert #test values ('R'+replicate('.',899),'A')
insert #test values ('A'+replicate('.',899),'T')
insert #test values ('D'+replicate('.',899),'U')
insert #test values ('S'+replicate('.',899),'R')
insert #test values ('C'+replicate('.',899),'A')
insert #test values ('H'+replicate('.',899),'L')
insert #test values ('U'+replicate('.',899),'O')
insert #test values ('L'+replicate('.',899),'R')
insert #test values ('Z'+replicate('.',899),'D')
 
select * from #test
/*
col1      col2
--------- ----
B........ N
R........ A
A........ T
D........ U
S........ R
C........ A
H........ L
U........ O
L........ R
Z........ D
*/

Great. That makes sense. It’s the “natural” chronologically-entered order of the rows. You can see my name (Brad Schulz) spelled down vertically in the first column and “Natural Ord” spelled down vertically in the second column. That’s the order we put them in, and so it’s not surprising that’s the way they come out.

Now let’s insert two more rows and do another SELECT *:

insert #test values ('X','X')
insert #test values ('Y','Y')
select * from #test
/*
col1      col2
--------- ----
B........ N
R........ A
A........ T
D........ U
S........ R
C........ A
H........ L
U........ O
X         X
Y         Y
L........ R
Z........ D
*/

Huh? Why didn’t it append them at the end? Well, because SQL Server just doesn’t do an append. Table data is stored as a collection of 8-KB (8192-byte) pages. If you subtract the space for page header information and other overhead, that leaves 8060 bytes for the data on each page. And here’s the key: a row of data can not span multiple pages.

The first 10 rows I created were 901 bytes each. The first 8 rows took up 8 * 901 = 7208 bytes, leaving 8060 - 7208 = 852 bytes left in the page. The ninth row of 901 bytes was too big to fit in that page, so it was placed on a whole new page, along with the tenth row (since it, too, was too big to fit on the first page).

But when I added an 11th and 12th row, I purposely made those rows only 2 bytes each. And SQL Server plopped them on the first data page of the table because there was easily enough room for them. So now when we do a SELECT *, we are getting the first page’s worth of data followed by the second page.

You can read more at Books Online about SQL’s data storage in pages.

Now let's stir things up and create a clustered index on col1:

create clustered index ix_test1 on #test (col1)
select * from #test
/*
col1      col2
--------- ----
A........ T
B........ N
C........ A
D........ U
H........ L
L........ R
R........ A
S........ R
U........ O
X         X
Y         Y
Z........ D
*/

The table is no longer a heap of unordered rows… the table is now ordered on the column we called col1. So a SELECT is now going to retrieve data from the table in that order. If you look at the query plan, you can see that it’s doing a Clustered Index Scan.

But wait, that’s not all…

Now create a nonclustered index on col2:

create nonclustered index ix_test2 on #test (col2)
select * from #test
/*
col1      col2
--------- ----
C........ A
R........ A
Z........ D
H........ L
B........ N
U........ O
L........ R
S........ R
A........ T
D........ U
X         X
Y         Y
*/

Hmmm… Why does it now come out in col2 order? After all, we did a SELECT on ALL columns of the table, and all the data is stored in the clustered index. So why does the query plan show that an Index Scan was done on the nonclustered index instead of doing a Clustered Index Scan?

Our nonclustered index on col2 (and any nonclustered index we create) automatically includes col1 in the index as well, because it needs that to do a lookup into the clustered index in case it needs to acquire any further columns. So our nonclustered index has both col1 and col2 in it… all the columns of our table are in it!

And why does SQL prefer the NonClustered Index Scan over the Clustered Index Scan, even though they both have exactly the same amount of data? Well, in normal real-life situations, a nonclustered index will have less data in its pages than a clustered one (since the clustered index contains ALL columns). The size of a nonclustered index will be either equal to or less than the size of a clustered index… it will never be bigger… so for that reason, SQL builds an execution plan that will always favor a covering nonclustered index.

Now let’s remove the two indexes… no ordering at all. What happens?

drop index #test.ix_test1
drop index #test.ix_test2
select * from #test
/*
col1      col2
--------- ----
A........ T
B........ N
C........ A
D........ U
H........ L
L........ R
R........ A
S........ R
U........ O
X         X
Y         Y
Z........ D
*/

Wait a minute… We got rid of the clustered index. Why is the data in col1 order now? I assume that when we removed the clustered index, SQL scanned the clustered index (in col1 order) and re-wrote the data into a heap (a bunch o’ data without a clustered index).

I find it interesting, though, that it didn’t follow the rules of putting a new row into the first page it can find that has room. In other words, it wrote out the first 8 rows (the ones where col1 starts with A, B, C, D, H, L, R, and S), taking up 7208 bytes. Then row number 9’s 901 bytes was too big to fit, so it started a new page. But then row numbers 10 and 11 were our 2-byte rows, and they were apparently APPENDED AFTER row 9 in the second page and WERE NOT put into the first page where there was ample room for them. Perhaps, in order to remove the clustered index as quickly as possible, it’s just faster to spit out the rows onto successive pages rather than trying to do a “first page that fits” algorithm for every single row. (If anyone has any insight into this, please chime in).

If we add a new row, we can see that it follows the “first page that fits” rule, just as we had seen the last time we manually inserted records, putting the row into the first page:

insert #test values ('Z','Z')
select * from #test
/*
col1      col2
--------- ----
A........ T
B........ N
C........ A
D........ U
H........ L
L........ R
R........ A
S........ R
Z         Z
U........ O
X         X
Y         Y
Z........ D
*/

So, after all this, I think we can throw the “natural order” concept out the window, don't you? There’s just no such thing.