Re: Best way to scan on-disk bitmaps

Greg Stark <gsstark(at)mit(dot)edu> writes:
> Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> writes:
>> Plan B would be to remove that restriction and teach btree and gist to
>> cope. While a btree couldn't use a nonconsecutive restriction as part
>> of its where-to-scan logic, I don't see any good reason why it couldn't
>> still perform the test before returning the TID, thus possibly saving a
>> trip to the heap.

> [ snip ]

> In this model the columns listed in the gist index are unordered. Any subset
> of columns can be used to perform an index lookup. Making it more like the
> bitmap index behaviour you're looking at than the btree index behaviour.

I thought some more about this since sending my earlier message. As far
as I can recall at the moment, there really isn't anything fundamental
that depends on the consecutive-columns rule. The one place where the
rubber meets the road is in the index cost estimation functions: if we
were to relax that rule, then btcostestimate would have to be taught to
include only the consecutive columns when estimating how much of a btree
index is going to be touched.

And more than that: if you've studied the btree code at all, you realize
that that's only an incomplete heuristic anyway. For instance, if the
leading key is a > xxx, second keys like b > yyy and b < yyy act
completely differently in terms of indexscan cost, but btcostestimate
doesn't presently know that.

I wonder if we shouldn't migrate the amcostestimate functions into the
individual index AMs (which would mean adding a column to pg_am, but so
what). btcostestimate could be much less phony about this if it had
access to the same infrastructure that _bt_first uses to examine the
index clauses.

regards, tom lane