Can I optimize a SELECT DISTINCT x FROM hugeTable

问题:

I have a huge table, having a much smaller number (by orders of magnitude) of distinct values on some column x.

I need to do a query like SELECT DISTINCT x FROM hugeTable, and I want to do this relatively fast.

I did something like CREATE INDEX hugeTable_by_x ON hugeTable(x), but for some reason, even though the output is small, the query execution is not as fast. The query plan shows that 97% of the time is spent on Index Scan of hugeTable_by_x, with an estimated number of rows equal to the size of the entire table. This is followed by, among other things, a Hash Match operation.

Since I created an index on column x, can I not expect this query to run very quickly?

Note that I'm using Microsoft SQL Server 2005.

回答1:

This is likely not a problem of indexing, but one of data design. Normalization, to be precise. The fact that you need to query distinct values of a field, and even willing to add an index, is a strong indicator that the field should be normalized into a separate table with a (small) join key. Then the distinct values will be available immediately by scanning the much smaller lookup foreign table.

Update
As a workaround, you can create an indexed view on an aggregate by the 'distinct' field. COUNT_BIG is an aggregate that is allowed in indexed views:

create view vwDistinct
with schemabinding
as select x, count_big(*)
from schema.hugetable
group by x;

create clustered index cdxDistinct on vwDistinct(x);

select x from vwDistinct with (noexpand);

回答2:

SQL Server does not implement any facility to seek directly to the next distinct value in an index skipping duplicates along the way.

If you have many duplicates then you may be able to use a recursive CTE to simulate this. The technique comes from here. ("Super-fast DISTINCT using a recursive CTE"). For example:

with recursivecte as (
  select min(t.x) as x
  from hugetable t
  union all
  select ranked.x
  from (
    select t.x,
           row_number() over (order by t.x) as rnk
    from hugetable t
    join recursivecte r
      on r.x < t.x
  ) ranked
  where ranked.rnk = 1
)
select *
from recursivecte
option (maxrecursion 0)

回答3:

If you know the values in advance and there is an index on column x (or if each value is likely to appear quickly on a seq scan of the whole table), it is much faster to query each one individually:

select vals.x
from [values] as vals (x)
where exists (select 1 from bigtable where bigtable.x = vals.x);

Proceeding using exists() will do as many index lookups as there are valid values.

The way you've written it (which is correct if the values are not known in advance), the query engine will need to read the whole table and hash aggregate the mess to extract the values. (Which makes the index useless.)

回答4:

No. But there are some workarounds (excluding normalization):

Once the index is in place, then its possible to implement in SQL what the optimizer could be doing automatically:

https://stackoverflow.com/a/29286754/538763 (multiple workarounds cited)

Other answers say you can normalize which would solve your issue but even once its normalized SQL Server still likes to perform a scan to find the max() within group(s). Workarounds:

https://dba.stackexchange.com/questions/48848/efficiently-query-max-over-multiple-ranges?rq=1

回答5:

When doing a SELECT DISTINCT on an indexed field, an index scan makes sense, as execution still has to scan each value in the index for the entire table (assuming no WHERE clause, as seems to be the case by your example).

Indexes usually have more of an impact on WHERE conditions, JOINS, and ORDER BY clauses.

回答6:

As per your description of the execution plan, I would believe it's the best possible execution.

The Index Scan reads the entire index as stored (not in index order), the HASH MATCH does the distinct.

There might be other ways around your problem. In SQL Server, Indexed Views come to my mind. However, that might give you a big hit for write's on that table.

回答7:

Possibly. Though it is not guaranteed - it entirely depends on the query.

I suggest reading this article by Gail Shaw (part 1 and part 2).