From: | Bruce Momjian <pgman(at)candle(dot)pha(dot)pa(dot)us> |
---|---|
To: | Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> |
Cc: | Mike Rylander <mrylander(at)gmail(dot)com>, Hackers <pgsql-hackers(at)postgresql(dot)org> |
Subject: | Re: [COMMITTERS] pgsql: Install some slightly realistic cost |
Date: | 2005-04-21 15:20:08 |
Message-ID: | 200504211520.j3LFK8E19330@candle.pha.pa.us |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Thread: | |
Lists: | pgsql-committers pgsql-hackers |
Tom Lane wrote:
> Bruce Momjian <pgman(at)candle(dot)pha(dot)pa(dot)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 applications that need to
query the database in an many permutations. This feature scans an index
and creates an in-memory bitmap, and allows that bitmap to be combined
with other bitmap created in a similar way. The bitmap can either index
all TIDs, or be lossy, meaning it records just page numbers and each
page tuple has to be checked for validity in a separate pass.
--
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
From | Date | Subject | |
---|---|---|---|
Next Message | Bruce Momjian | 2005-04-21 15:20:40 | pgsql: Updated text for bitmaps: < Bitmap indexes index single |
Previous Message | Tom Lane | 2005-04-21 14:57:57 | Re: [COMMITTERS] pgsql: Install some slightly realistic cost estimation |
From | Date | Subject | |
---|---|---|---|
Next Message | Bruce Momjian | 2005-04-21 15:21:57 | Re: [COMMITTERS] pgsql: Install some slightly realistic cost |
Previous Message | Tom Lane | 2005-04-21 15:15:07 | Re: Postgres: pg_hba.conf, md5, pg_shadow, encrypted passwords |