Re: [COMMITTERS] pgsql: Install some slightly realistic cost

I believe Tom is completing this TODO item:

* Allow non-bitmap indexes to be combined by creating bitmaps in memory

Bitmap indexes index single columns that can be combined with other bitmap
indexes to dynamically create a composite index to match a specific query.
Each index is a bitmap, and the bitmaps are bitwise AND'ed or OR'ed to be
combined. They can index by tid or can be lossy requiring a scan of the
heap page to find matching rows, or perhaps use a mixed solution where
tids are recorded for pages with only a few matches and per-page bitmaps
are used for more dense pages. Another idea is to use a 32-bit bitmap
for every page and set a bit based on the item number mod(32).

---------------------------------------------------------------------------

Mike Rylander wrote:
> On 4/21/05, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> > Christopher Kings-Lynne <chriskl(at)familyhealth(dot)com(dot)au> writes:
> > > Is this totally rad bitmap index support going in? :D Does it require
> > > new index types or does it work with existing ones, etc?
> >
> > Works with the existing ones. It's the same idea that's been discussed
> > several times, eg
> > http://archives.postgresql.org/pgsql-hackers/2005-02/msg00867.php
>
> I scanned the archives but couldn't find a direct answer to something,
> though I seem to remember it being discussed at the beginning of the
> "bitmap index" planning.
>
> Will the new Bitmap[Or|And] nodes work with lossy index types?
> Specifically, I'd like to experiment with tsearch2 and "&" type
> queries and joining the results of a ts2 index scan to a btree index
> scan, but I seem to remember you (Tom) saying that the in-memory
> bitmaps would only be useful for btree indexes. I hope I'm
> mis-remembering... :)
>
> >
> > It's sort of working now, but since I don't have any planner frontend
> > code yet except for a truly ugly kluge in orindxpath.c, the only cases
> > it can deal with are simple ORs:
> >
>
> [snip NEW query plan]
>
> > Total runtime: 16.913 ms
> > (10 rows)
> >
> > This is only marginally faster than the equivalent 8.0 plan:
> >
>
> [snip 8.0 query plan]
>
> > Total runtime: 18.712 ms
> > (3 rows)
> >
> > although it should scale better to large numbers of tuples.
> >
>
> It will also keep long lists of ORs from turning what would have been
> a >10% index scan into a seq scan, yes? I suppose there is some
> balance that needs to be calculated on
> number-of-conditions-per-index-scan vs startup-cost-of-X-index-scans.
> E.g., if you have table with 10M rows and an IN clause with 500
> elements, it might be better to start 20 index scans with 25 condition
> each instead of a single big index scan (what we do now if the cost
> isn't too high), 500 index scans (what a simple "spin off a scan per
> condition" algo would do, and what it _looks_ like the new code did to
> your test query...), or a seq scan.
>
> > Things will get more interesting once we can AND the results of
> > unrelated indexes ...
>
> I can't wait! How close to initial testing is the AND stuff for
> unrelated indexes? Could this bitmapping code be used to combine
> indexes from different tables, say in a large UNION or inherited table
> setup?
>
> >
> > regards, tom lane
> >
>
> --
> Mike Rylander
> mrylander(at)gmail(dot)com
> GPLS -- PINES Development
> Database Developer
> http://open-ils.org
>
> ---------------------------(end of broadcast)---------------------------
> TIP 2: you can get off all lists at once with the unregister command
> (send "unregister YourEmailAddressHere" to majordomo(at)postgresql(dot)org)
>

--
Bruce Momjian | http://candle.pha.pa.us
pgman(at)candle(dot)pha(dot)pa(dot)us | (610) 359-1001
+ If your life is a hard drive, | 13 Roberts Road
+ Christ can be your backup. | Newtown Square, Pennsylvania 19073