I am trying to coax some more performance out of a query that is accessing a table with ~250-million records. From my reading of the actual (not estimated) execution plan, the first bottleneck is a query that looks like this:

    dbo.hugetable a
    inner join
    #smalltable b on a.fk = b.pk
    a.added between @start and @end;

See further down for the definitions of the tables & indexes involved.

The execution plan indicates that a nested loop is being used on #smalltable, and that the index scan over hugetable is being executed 480 times (for each row in #smalltable). This seems backwards to me, so I've tried to force a merge join to be used instead:

    dbo.hugetable a with(index = ix_hugetable)
    inner merge join
    #smalltable b with(index(1)) on a.fk = b.pk
    a.added between @start and @end;

The index in question (see below for full definition) covers columns fk (the join predicate), added (used in the where clause) & id (useless) in ascending order, and includes value.

When I do this, however, the query blows out from 2 1/2 minutes to over 9. I would have hoped that the hints would force a more efficient join that only does a single pass over each table, but clearly not.

Any guidance is welcome. Additional information provided if required.

Update (2011/06/02)

Having reorganised the indexing on the table, I have made significant performance inroads, however I have hit a new obstacle when it comes to summarising the data in the huge table. The outcome is a summarisation by month, which currently looks like the following:

    datediff(month, 0, a.added),
    sum(case when a.value > 0 else 1 end) -- this triples the running time!
    dbo.hugetable a
    inner join
    #smalltable b on a.fk = b.pk
group by
    datediff(month, 0, a.added);

At present, hugetable has a clustered index pk_hugetable (added, fk) (the primary key), and a non-clustered index going the other way ix_hugetable (fk, added).

Without the 4th column above, the optimiser uses a nested loop join as before, using #smalltable as the outer input, and a non-clustered index seek as the inner loop (executing 480 times again). What concerns me is the disparity between the estimated rows (12,958.4) and actual rows (74,668,468). The relative cost of these seeks is 45%. Running time is however under a minute.

With the 4th column, the running time spikes to 4 minutes. It seeks on the clustered index this time (2 executions) for the same relative cost (45%), aggregates via a hash match (30%), then does a hash join on #smalltable (0%).

I'm unsure as to my next course of action. My concern is that neither the date range search nor the join predicate is guaranteed or even all that likely to drastically reduce the result set. The date range in most cases will only trim maybe 10-15% of records, and the inner join on fk may filter out maybe 20-30%.

As requested by Will A, the results of sp_spaceused:

name      | rows      | reserved    | data        | index_size  | unused
hugetable | 261774373 | 93552920 KB | 18373816 KB | 75167432 KB | 11672 KB

#smalltable is defined as:

create table #endpoints (
    pk uniqueidentifier primary key clustered,
    stuff varchar(6) null

While dbo.hugetable is defined as:

create table dbo.hugetable (
    id uniqueidentifier not null,
    fk uniqueidentifier not null,
    added datetime not null,
    value decimal(13, 3) not null,

    constraint pk_hugetable primary key clustered (
        fk asc,
        added asc,
        id asc
    with (
        pad_index = off, statistics_norecompute = off,
        ignore_dup_key = off, allow_row_locks = on,
        allow_page_locks = on
    on [primary]
on [primary];

With the following index defined:

create nonclustered index ix_hugetable on dbo.hugetable (
    fk asc, added asc, id asc
) include(value) with (
    pad_index = off, statistics_norecompute = off,
    sort_in_tempdb = off, ignore_dup_key = off,
    drop_existing = off, online = off,
    allow_row_locks = on, allow_page_locks = on
on [primary];

The id field is redundant, an artefact from a previous DBA who insisted that all tables everywhere should have a GUID, no exceptions.

  • Could you include the result of sp_spaceused 'dbo.hugetable', please? – Will A May 31 '11 at 6:34
  • Done, added just above the start of the table definitions. – Quick Joe Smith May 31 '11 at 6:45
  • It sure is. Its ridiculous size is the reason I'm looking into this. – Quick Joe Smith May 31 '11 at 6:55

Your ix_hugetable looks quite useless because:

  • it is the clustered index (PK)
  • the INCLUDE makes no difference because a clustered index INCLUDEs all non-key columns (non-key values at lowest leaf = INCLUDEd = what a clustered index is)

In addition: - added or fk should be first - ID is first = not much use

Try changing the clustered key to (added, fk, id) and drop ix_hugetable. You've already tried (fk, added, id). If nothing else, you'll save a lot of disk space and index maintenance

Another option might be to try the FORCE ORDER hint with table order boh ways and no JOIN/INDEX hints. I try not to use JOIN/INDEX hints personally because you remove options for the optimiser. Many years ago I was told (seminar with a SQL Guru) that FORCE ORDER hint can help when you have huge table JOIN small table: YMMV 7 years later...

Oh, and let us know where the DBA lives so we can arrange for some percussion adjustment

Edit, after 02 Jun update

The 4th column is not part of the non-clustered index so it uses the clustered index.

Try changing the NC index to INCLUDE the value column so it doesn't have to access the value column for the clustered index

create nonclustered index ix_hugetable on dbo.hugetable (
    fk asc, added asc
) include(value)

Note: If value is not nullable then it is the same as COUNT(*) semantically. But for SUM it need the actual value, not existence.

As an example, if you change COUNT(value) to COUNT(DISTINCT value) without changing the index it should break the query again because it has to process value as a value, not as existence.

The query needs 3 columns: added, fk, value. The first 2 are filtered/joined so are key columns. value is just used so can be included. Classic use of a covering index.

  • Hah, I had it in my head that the clustered and non-clustered indexes had fk & added in different order. I can't believe I didn't notice that, almost as much as I can't believe it was setup this way in the first place. I will change the clustered index tomorrow, then go down the street for a coffee while it rebuilds. – Quick Joe Smith May 31 '11 at 13:04
  • I have altered the indexing and had a bash with FORCE ORDER in an attempt to reduce the number of seeks on the large table but to no avail. My question has been updated. – Quick Joe Smith Jun 2 '11 at 2:16
  • @Quick Joe Smith: updated my answer – gbn Jun 2 '11 at 7:19
  • Yes, I tried that not long afterwards. Because index rebuilding takes so long, I forgot about it and initially thought that I'd sped it up doing something entirely unrelated. – Quick Joe Smith Jun 2 '11 at 12:18

Define an index on hugetable on just the added column.

DB's will use a multi-part (multi column) index only as far right of the column list as it has values counting from the left. Your query doesn't specify fk in the where clause of the first query, so it ignores the index.

  • The execution plan shows that the index (ix_hugetable) is being seeked. Or are you saying that this index is not appropriate for the query? – Quick Joe Smith May 31 '11 at 6:26
  • The index is not appropriate. Who knows how it is "using the index". Experience tells me this is your problem. Try it and tell us how it goes. – Bohemian May 31 '11 at 6:30
  • @Quick Joe Smith - did you try @Bohemian's suggestion? What where the results? – Lieven Keersmaekers May 31 '11 at 7:18
  • 2
    I disagree: the ON clause is logically processed first and is effectively a WHERE in practice so OP has to try both columns first. No indexing on fk at all = clustered index scan or key lookup to get the fk value for the JOIN. Can you add some references to the behaviour you have described too please? Especially for SQL Server given you have little previous history answering for this RDBMS. Actually, -1 in retrospect as aI type this comment – gbn May 31 '11 at 7:30

The execution plan indicates that a nested loop is being used on #smalltable, and that the index scan over hugetable is being executed 480 times (for each row in #smalltable).

This is the order I'd expect the query optimizer to use, assuming that a loop join in the right choice. The alternative is to loop 250M times and perform a lookup into the #temp table each time - which could well take hours / days.

The index you're forcing to be used in the MERGE join is pretty much 250M rows * 'the size of each row' - not small, at least a couple of GB. Judging from the sp_spaceused output 'a couple of GB' might be quite an understatement - the MERGE join requires that you trawl through index which is going to be very I/O intensive.

  • My understanding is that there is 3 types of join algorithms, and that the merge join has the best performance when both inputs are ordered by the join predicate. Rightly or wrongly, this is the outcome I'm trying to get. – Quick Joe Smith May 31 '11 at 6:37
  • 2
    But there's more to it than this. If #smalltable had a large number of rows then a merge join might be appropriate. If, as it's name suggests, it has a small number of rows then a loop join could be the right choice. Imagine #smalltable had one or two rows, and matched vs. a handful of rows from the other table - it would be hard to justify a merge join here. – Will A May 31 '11 at 6:39
  • I figured there was more to it; I just didn't know what that might be. Database optimisation is not exactly my strong suit, as you have probably already guessed. – Quick Joe Smith May 31 '11 at 6:46
  • @Quick Joe Smith - thanks for the sp_spaceused. 75GB of index and 18GB of data - is ix_hugetable not the only index on the table? – Will A May 31 '11 at 6:46
  • 1
    +1 Will. The planner is currently doing the right thing. The issue lies in random disk seeks due to the way your tables are clustered. – Denis de Bernardy May 31 '11 at 9:06

Your index is incorrect. See indexes dos and donts.

As things stand, your only useful index is that on the small table's primary key. The only reasonable plan is thus to seq scan the small table and to nest loop the mess with the huge one.

Try adding a clustered index on hugetable(added, fk). This should make the planner seek out applicable rows from the huge table, and nest loop or merge join them with the small table.

  • Thanks for that link. I will try this when I get to work tomorrow. – Quick Joe Smith May 31 '11 at 13:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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