Thread: Re: [COMMITTERS] pgsql: Install some slightly realistic cost estimation
Re: [COMMITTERS] pgsql: Install some slightly realistic cost estimation
From
Christopher Kings-Lynne
Date:
Hi Tom, I hate to slow you down when you're coding, but it'd be cool if you could explain to me (and other interested parties) what's going on here :) Is this totally rad bitmap index support going in? :D Does it require new index types or does it work with existing ones, etc? Chris Tom Lane wrote: > Log Message: > ----------- > Install some slightly realistic cost estimation for bitmap index scans. > > Modified Files: > -------------- > pgsql/src/backend/nodes: > outfuncs.c (r1.247 -> r1.248) > (http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/nodes/outfuncs.c.diff?r1=1.247&r2=1.248) > pgsql/src/backend/optimizer/path: > costsize.c (r1.142 -> r1.143) > (http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/optimizer/path/costsize.c.diff?r1=1.142&r2=1.143) > indxpath.c (r1.174 -> r1.175) > (http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/optimizer/path/indxpath.c.diff?r1=1.174&r2=1.175) > orindxpath.c (r1.67 -> r1.68) > (http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/optimizer/path/orindxpath.c.diff?r1=1.67&r2=1.68) > pgsql/src/backend/optimizer/plan: > createplan.c (r1.180 -> r1.181) > (http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/optimizer/plan/createplan.c.diff?r1=1.180&r2=1.181) > pgsql/src/backend/optimizer/util: > pathnode.c (r1.116 -> r1.117) > (http://developer.postgresql.org/cvsweb.cgi/pgsql/src/backend/optimizer/util/pathnode.c.diff?r1=1.116&r2=1.117) > pgsql/src/include/nodes: > relation.h (r1.105 -> r1.106) > (http://developer.postgresql.org/cvsweb.cgi/pgsql/src/include/nodes/relation.h.diff?r1=1.105&r2=1.106) > pgsql/src/include/optimizer: > cost.h (r1.64 -> r1.65) > (http://developer.postgresql.org/cvsweb.cgi/pgsql/src/include/optimizer/cost.h.diff?r1=1.64&r2=1.65) > > ---------------------------(end of broadcast)--------------------------- > TIP 2: you can get off all lists at once with the unregister command > (send "unregister YourEmailAddressHere" to majordomo@postgresql.org)
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 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: regression=# explain analyze select * from tenk1 where (unique1 >= 1000 and unique1 < 1500) or (unique1 >= 2000 and unique1< 2400) or (unique1 > 300 and unique1 < 399); QUERYPLAN -------------------------------------------------------------------------------------------------------------------------------------------------Bitmap HeapScan on tenk1 (cost=14.12..397.62 rows=991 width=244) (actual time=4.107..12.512 rows=998 loops=1) Recheck Cond: (((unique1>= 1000) AND (unique1 < 1500)) OR ((unique1 >= 2000) AND (unique1 < 2400)) OR ((unique1 > 300) AND (unique1 < 399))) -> BitmapOr (cost=0.00..14.12 rows=1021 width=0) (actual time=2.942..2.942 rows=0 loops=1) -> Bitmap IndexScan on tenk1_unique1 (cost=0.00..6.14 rows=523 width=0) (actual time=1.547..1.547 rows=500 loops=1) IndexCond: ((unique1 >= 1000) AND (unique1 < 1500)) -> Bitmap Index Scan on tenk1_unique1 (cost=0.00..5.43 rows=405width=0) (actual time=1.072..1.072 rows=400 loops=1) Index Cond: ((unique1 >= 2000) AND (unique1 < 2400)) -> Bitmap Index Scan on tenk1_unique1 (cost=0.00..2.56 rows=93 width=0) (actual time=0.283..0.283 rows=98loops=1) Index Cond: ((unique1 > 300) AND (unique1 < 399))Total runtime: 16.913 ms (10 rows) This is only marginally faster than the equivalent 8.0 plan: regression=# explain analyze select * from tenk1 where (unique1 >= 1000 and unique1 < 1500) or (unique1 >= 2000 and unique1< 2400) or (unique1 > 300 and unique1 < 399); QUERY PLAN -------------------------------------------------------------------------------------------------------------------------------------------------------------Index Scanusing tenk1_unique1, tenk1_unique1, tenk1_unique1 on tenk1 (cost=0.00..2590.19 rows=981 width=244) (actual time=0.145..14.293rows=998 loops=1) Index Cond: (((unique1 >= 1000) AND (unique1 < 1500)) OR ((unique1 >= 2000) AND (unique1< 2400)) OR ((unique1 > 300) AND (unique1 < 399)))Total runtime: 18.712 ms (3 rows) although it should scale better to large numbers of tuples. Things will get more interesting once we can AND the results of unrelated indexes ... regards, tom lane
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
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
Mike Rylander <mrylander@gmail.com> writes:
> Will the new Bitmap[Or|And] nodes work with lossy index types?
Sure. Obviously the lossy conditions need to be rechecked, and
depending on how bright the planner ends up being, that might
cause the whole WHERE to get rechecked. For example given
WHERE (x ~ y) OR (x ~~ z)
where let's suppose ~~ is a lossy operator, we could make bitmaps
of the index hits for each condition and OR them together; but once
we finally do visit the tuple I think we'll have to evaluate the
whole WHERE not just the lossy operator to be sure we are getting
the right answer.
We could *not* use a lossy index for something like a difference
condition (x ~ y AND NOT x ~~ z), but I'm not planning to support
that in the first go-round anyway.
> 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... :)
I'm pretty sure I never said that. If I did, I was wrong.
> It will also keep long lists of ORs from turning what would have been
> a >10% index scan into a seq scan, yes?
It should look more attractive than the old method, yes. At some point
you still end up deciding you might as well seqscan. I'm not sure
whether the cost estimation model I put in last night gets the crossover
point right --- we'll need to get some field experience as soon as the
code is reasonably functional.
That reminds me: at least for testing purposes, it'd be a good idea
to have an additional planner "enable" switch for this plan type,
analogous to enable_seqscan and enable_indexscan. Any objections to
adding one? Should I call it "enable_bitmapscan", or can someone
think of a less ugly name?
regards, tom lane
On 4/21/05, Bruce Momjian <pgman@candle.pha.pa.us> wrote: > > I believe Tom is completing this TODO item: > > * Allow non-bitmap indexes to be combined by creating bitmaps in memory > Thanks Bruce. That definitely answers my first question about lossy index types. Sorry for asking a TODO answered question. [MENTAL NOTE: Check TODOs as well as archives...] I'm still curious about the implications of this (my) assumption: > > 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. > > Though I'm not sure if I was completely clear there... And just to be clear, unless I'm just misunderstanding the TODO, it looks like this: > > unrelated indexes? Could this bitmapping code be used to combine > > indexes from different tables, say in a large UNION or inherited table > > setup? should be true when the implementation is complete. The reason I ask about the inherited table index bitmapping is that it might provide a way to check for cross-partition UNIQUE constraints. Perhaps something like: ALTER TABLE base_table ADD CONSTRAINT col_global_uniq_constraint GLOBALLY UNIQUE (unique_column); That could use a bitmapped OR scan of indexes on "unique_column" on the base table and all descendant tables to check for a unique value across a "partitioned table". Hmmm... thinking more, I suppose it could just to a quick scan of each index in order, so that might not be useful. -- Mike Rylander mrylander@gmail.com GPLS -- PINES Development Database Developer http://open-ils.org
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...
regards, tom lane
Mike Rylander <mrylander@gmail.com> writes:
> unrelated indexes? Could this bitmapping code be used to combine
> indexes from different tables, say in a large UNION or inherited table
> setup?
> should be true when the implementation is complete.
No, it's only for combining indexes on a single table --- the bitmaps
only store TIDs, which are relative to a particular table. I don't
think there'd be any advantage to extending the technique to handle
multiple tables; the real win comes when you AND or OR overlapping
bitmaps, and there could never be any overlap between two different
tables.
If we had multi-table indexes it'd be a different story of course.
regards, tom lane
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
Tom Lane wrote: > > It will also keep long lists of ORs from turning what would have been > > a >10% index scan into a seq scan, yes? > > It should look more attractive than the old method, yes. At some point > you still end up deciding you might as well seqscan. I'm not sure > whether the cost estimation model I put in last night gets the crossover > point right --- we'll need to get some field experience as soon as the > code is reasonably functional. > > That reminds me: at least for testing purposes, it'd be a good idea > to have an additional planner "enable" switch for this plan type, > analogous to enable_seqscan and enable_indexscan. Any objections to > adding one? Should I call it "enable_bitmapscan", or can someone > think of a less ugly name? I think "enable_bitmapscan" is the best we can do. -- 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