Re: [COMMITTERS] pgsql: Install some slightly realistic cost - Mailing list pgsql-hackers

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
indexto match a specific query. Each index is a bitmap, and the bitmaps are bitwise AND'ed or OR'ed to be combined.
Theycan index by tid or can be lossy requiring a scan of the heap page to find matching rows, or perhaps use a mixed
solutionwhere tids are recorded for pages with only a few matches and per-page bitmaps are used for more dense pages.
Anotheridea 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@sss.pgh.pa.us> wrote:
> > Christopher Kings-Lynne <chriskl@familyhealth.com.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@gmail.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@postgresql.org)
> 

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