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

From: Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>
To: Bruce Momjian <pgman(at)candle(dot)pha(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 estimation
Date: 2005-04-21 14:49:41
Message-ID: 15309.1114094981@sss.pgh.pa.us
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-committers pgsql-hackers

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

regards, tom lane

In response to

Responses

Browse pgsql-committers by date

  From Date Subject
Next Message Tom Lane 2005-04-21 14:57:57 Re: [COMMITTERS] pgsql: Install some slightly realistic cost estimation
Previous Message Mike Rylander 2005-04-21 14:45:46 Re: [COMMITTERS] pgsql: Install some slightly realistic cost estimation

Browse pgsql-hackers by date

  From Date Subject
Next Message Tom Lane 2005-04-21 14:57:57 Re: [COMMITTERS] pgsql: Install some slightly realistic cost estimation
Previous Message Mike Rylander 2005-04-21 14:45:46 Re: [COMMITTERS] pgsql: Install some slightly realistic cost estimation