Richard Poole <richard.poole@vi.net> writes:
> [ snip a bunch of commentary about optimizer statistics ]
> Can someone who really knows this stuff (Tom?) step in if what I've
> just said is completely wrong?
Looked good to me.
>> select domain from history_entries group by domain;
>>
>> To me, since there is an index on domain, it seems like this should be a
>> rather fast thing to do? It takes a *very* long time, no matter if I turn
>> seqscan on or off.
> The reason this is slow is that Postgres always has to look at heap
> tuples, even when it's been sent there by indexes. This in turn is
> because of the way the storage manager works (only by looking in the
> heap can you tell for sure whether a tuple is valid for the current
> transaction). So a "group by" always has to look at every heap tuple
> (that hasn't been eliminated by a where clause). "select distinct"
> has the same problem. I don't think there's a way to do what you
> want here with your existing schema without a sequential scan over
> the table.
But this last I object to. You certainly could use an index scan here,
it's just that it's not very likely to be faster. The way that Postgres
presently does GROUP BY and SELECT DISTINCT is to sort the tuples into
order and then combine/eliminate adjacent duplicates. (If you've ever
used a "sort | uniq" pipeline in Unix then you know the principle.)
So the initial requirement for this query is to scan the history_entries
tuples in order by domain. We can do this either by a sequential scan
and explicit sort, or by an index scan using an ordered index on domain.
It turns out that unless the physical order of the tuples is pretty
close to their index order, the index-scan method is actually slower,
because it results in a lot of random-access thrashing. But neither way
is exactly speedy.
One thing that's on the to-do list is to look at reimplementing these
operations using in-memory hash tables, with one hash entry per distinct
value of the GROUP/DISTINCT columns. Then you can just do a sequential
scan, with no sort, and as long as there aren't so many distinct values
as to make the hash table overflow memory you're going to win. However
until we have statistics that can give us some idea how many distinct
values there might be, there's no way for the planner to make an
intelligent choice between this way and the sort/uniq way...
regards, tom lane
