Re: Best way to scan on-disk bitmaps

On Sun, 15 May 2005, Tom Lane wrote:

> Greg Stark <gsstark(at)mit(dot)edu> writes:
>> Bruce Momjian <pgman(at)candle(dot)pha(dot)pa(dot)us> writes:
>>>> Hmm. That particular case will work, but the planner believes that only
>>>> consecutive columns in the index are usable --- that is, if you have
>>>> quals for a and c but not for b, it will think that the condition for c
>>>> isn't usable with the index.
>>>
>>> We do have a TODO for this:
>>>
>>> * Use index to restrict rows returned by multi-key index when used with
>>> non-consecutive keys to reduce heap accesses
>
>> That TODO is something else.
>
> No, I think Bruce is right --- it's essentially the same thing. It
> certainly would be a good idea to change btrees to work like that,
> if we are going to modify the planner to relax the restriction for
> other index types.
>
> I think it would be easy to change the planner and btree to handle
> this (where "easy" means "I remember where all the skeletons are
> buried"). But I don't know the gist code hardly at all. Can anyone
> offer an informed opinion on whether gist can handle this now, and
> if not what it would take to handle it?

I think that handling this in GiST is depends solely on how users consistent
function designed to handle NULLs in keys. Other words, it should works as
soon as users consistent function "know" what to do with NULLs in internal keys.

Teodor will comment multi-key GiST tomorrow.

We used Paul Aoki paper "Generalizing ''Search'' in Generalized Search Trees",
(available from http://www.sai.msu.su/~megera/postgres/gist/papers/csd-97-950.pdf )
for implementation of multi-key GiST index support. It's true, that first
key is used for splitting, but elements with duplicated first key could
be shuffled to get better clustering on second key.

>
> (hash and rtree are not at issue since they don't support multi-key
> indexes.)
>
> regards, tom lane
>
> ---------------------------(end of broadcast)---------------------------
> TIP 1: subscribe and unsubscribe commands go to majordomo(at)postgresql(dot)org
>

Regards,
Oleg
_____________________________________________________________
Oleg Bartunov, sci.researcher, hostmaster of AstroNet,
Sternberg Astronomical Institute, Moscow University (Russia)
Internet: oleg(at)sai(dot)msu(dot)su, http://www.sai.msu.su/~megera/
phone: +007(095)939-16-83, +007(095)939-23-83