Re: Rules, Windows and ORDER BY

Martijn van Oosterhout <kleptog(at)svana(dot)org> writes:
> On Fri, Aug 24, 2012 at 09:32:32AM +0000, Jason Dusek wrote:
>> Why are the individual indices not useful? The tests that the
>> query does -- equality on key and realm and ordering on at --
>> are each supported by indices. Does it have to do with the cost
>> of loading the three indices?

> I'm not entirely sure, but I'll take a stab at it. I think it has to do
> with the fact that you want order. Combining multiple indexes so you
> use them at the same time works as an BitmapAnd. That is, it uses each
> index to determine blocks that are interesting and then find the blocks
> that are listed by all tindexes, and then it loads the blocks and chcks
> them.

Yeah. While you *can* in principle solve the problem with the
individual indexes, it's much less efficient than a single index.
In particular, BitmapAnd plans are far from being a magic bullet
for combining two individually-not-very-selective conditions.
(That realm constraint is surely not very selective; dunno about
the key one.) That implies reading a large number of entries from
each index, forming a rather large bitmap for each one, and then
ANDing those bitmaps to get a smaller one. And even after all that
work, you're still not done, because you have no idea which bit in
the bitmap represents the row with largest "at" value.

> In theory you could BitmapAnd the 'k' and 'realm' indexes and then scan
> the 'at' index only checking rows that the bitmap shows are
> interesting. But I'm not sure if postgres can do that.

No, it can't, and that likely wouldn't be a very effective plan anyway;
you could end up scanning a very large fraction of the "at" index, since
you'd have to start at the end (the latest entry anywhere in the table).
Even if you didn't make many trips to the heap, that's not cheap.

In constrast, given a three-column btree index organized with the
equality-constrained columns first, the btree code can descend the
index tree straight to the entry you want. We've expended a lot of
sweat on optimizing that case, and it will absolutely blow the doors
off anything involving a bitmap scan.

Of course the downside is that the three-column index might be
relatively useless for queries of forms other than this one.
So it's a tradeoff between flexibility and performance. But since
the OP is asking, I'm assuming he cares a lot about performance of
queries of this exact form.

regards, tom lane