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

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