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

From Bruce Momjian
Subject Re: [COMMITTERS] pgsql: Install some slightly realistic cost
Date
Msg-id 200504211520.j3LFK8E19330@candle.pha.pa.us
Whole thread Raw
In response to Re: [COMMITTERS] pgsql: Install some slightly realistic cost estimation  (Tom Lane <tgl@sss.pgh.pa.us>)
List pgsql-hackers
Tom Lane wrote:
> Bruce Momjian <pgman@candle.pha.pa.us> writes:
> > 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).
> 
> The one-line summary looks like what I am doing, but the paragraph of
> discussion seems largely off target :-(
> 
> What is actually happening in the current code is: scan any standard
> index type, but don't go to the heap with the TIDs the index AM returns;
> instead form a sparse, possibly lossy bitmap holding the TIDs (see
> src/backend/nodes/tidbitmap.c).  Then, potentially AND or OR this with
> other bitmaps formed in the same way by scanning other indexes (or the
> same index with different restriction conditions).  Finally visit the
> heap in TID order using the bitmap to tell where to look.
> 
> At the moment the code is basically all there except for planner
> frontend, ie the code to recognize suitable combinations of indexable
> clauses and make Paths for them.  I hope to have a first cut at some
> frontend logic in a day or two, barring other demands on my time.
> You might be able to play with it by the weekend...

OK, updated TODO text:

* Allow non-bitmap indexes to be combined by creating bitmaps in memory
 This feature allows separate indexes to be ANDed or ORed together.  This is particularly useful for data warehousing
applicationsthat need to query the database in an many permutations.  This feature scans an index and creates an
in-memorybitmap, and allows that bitmap to be combined with other bitmap created in a similar way.  The bitmap can
eitherindex all TIDs, or be lossy, meaning it records just page numbers and each page tuple has to be checked for
validityin a separate pass.
 

--  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
 


pgsql-hackers by date:

Previous
From: Tom Lane
Date:
Subject: Re: Postgres: pg_hba.conf, md5, pg_shadow, encrypted passwords
Next
From: Bruce Momjian
Date:
Subject: Re: [COMMITTERS] pgsql: Install some slightly realistic cost