Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit2689390

Browse files
committed
Allow create_index_paths() to consider multiple join bitmapscan paths.
In the initial cut at the "parameterized paths" feature, I'd simplifiedcreate_index_paths() to the point where it would only generate a singleparameterized bitmap path per relation. Experimentation with an examplesupplied by Josh Berkus convinces me that that's not good enough: we reallyneed to consider a bitmap path for each possible outer relation. Otherwisewe have regressions relative to pre-9.2 versions, in which the plannerpicks a plain indexscan where it should have used a bitmap scan in queriesinvolving three or more tables. Indeed, after fixing this, several queriesin the regression tests show improved plans as a result of using bitmap notplain indexscans.
1 parentd652469 commit2689390

File tree

2 files changed

+99
-27
lines changed

2 files changed

+99
-27
lines changed

‎src/backend/optimizer/path/indxpath.c

Lines changed: 82 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -309,26 +309,92 @@ create_index_paths(PlannerInfo *root, RelOptInfo *rel)
309309
}
310310

311311
/*
312-
* Likewise, if we found anything usable, generatea BitmapHeapPathfor
313-
*themost promisingcombination of join bitmap index paths. Note there
314-
*will be only one such pathno matter how many join clauses are
315-
*available. (XXX is that good enough, or do we need to consider even
316-
*more paths for different subsets of possible join partners?Also,
317-
*should we add in restriction bitmap paths as well?)
312+
* Likewise, if we found anything usable, generateBitmapHeapPathsfor the
313+
* most promisingcombinations of join bitmap index paths.Our strategy
314+
*is to generate one such pathfor each distinct parameterization seen
315+
*among the available bitmap index paths.This may look pretty
316+
*expensive, but usually there won't be very many distinct
317+
*parameterizations.
318318
*/
319319
if (bitjoinpaths!=NIL)
320320
{
321-
Path*bitmapqual;
322-
Relidsrequired_outer;
323-
doubleloop_count;
324-
BitmapHeapPath*bpath;
321+
List*path_outer;
322+
List*all_path_outers;
323+
ListCell*lc;
325324

326-
bitmapqual=choose_bitmap_and(root,rel,bitjoinpaths);
327-
required_outer=get_bitmap_tree_required_outer(bitmapqual);
328-
loop_count=get_loop_count(root,required_outer);
329-
bpath=create_bitmap_heap_path(root,rel,bitmapqual,
330-
required_outer,loop_count);
331-
add_path(rel, (Path*)bpath);
325+
/*
326+
* path_outer holds the parameterization of each path in bitjoinpaths
327+
* (to save recalculating that several times), while all_path_outers
328+
* holds all distinct parameterization sets.
329+
*/
330+
path_outer=all_path_outers=NIL;
331+
foreach(lc,bitjoinpaths)
332+
{
333+
Path*path= (Path*)lfirst(lc);
334+
Relidsrequired_outer;
335+
boolfound= false;
336+
ListCell*lco;
337+
338+
required_outer=get_bitmap_tree_required_outer(path);
339+
path_outer=lappend(path_outer,required_outer);
340+
341+
/* Have we already seen this param set? */
342+
foreach(lco,all_path_outers)
343+
{
344+
Relidsexisting_outers= (Relids)lfirst(lco);
345+
346+
if (bms_equal(existing_outers,required_outer))
347+
{
348+
found= true;
349+
break;
350+
}
351+
}
352+
if (!found)
353+
{
354+
/* No, so add it to all_path_outers */
355+
all_path_outers=lappend(all_path_outers,required_outer);
356+
}
357+
}
358+
359+
/* Now, for each distinct parameterization set ... */
360+
foreach(lc,all_path_outers)
361+
{
362+
Relidsmax_outers= (Relids)lfirst(lc);
363+
List*this_path_set;
364+
Path*bitmapqual;
365+
Relidsrequired_outer;
366+
doubleloop_count;
367+
BitmapHeapPath*bpath;
368+
ListCell*lcp;
369+
ListCell*lco;
370+
371+
/* Identify all the bitmap join paths needing no more than that */
372+
this_path_set=NIL;
373+
forboth(lcp,bitjoinpaths,lco,path_outer)
374+
{
375+
Path*path= (Path*)lfirst(lcp);
376+
Relidsp_outers= (Relids)lfirst(lco);
377+
378+
if (bms_is_subset(p_outers,max_outers))
379+
this_path_set=lappend(this_path_set,path);
380+
}
381+
382+
/*
383+
* Add in restriction bitmap paths, since they can be used
384+
* together with any join paths.
385+
*/
386+
this_path_set=list_concat(this_path_set,bitindexpaths);
387+
388+
/* Select best AND combination for this parameterization */
389+
bitmapqual=choose_bitmap_and(root,rel,this_path_set);
390+
391+
/* And push that path into the mix */
392+
required_outer=get_bitmap_tree_required_outer(bitmapqual);
393+
loop_count=get_loop_count(root,required_outer);
394+
bpath=create_bitmap_heap_path(root,rel,bitmapqual,
395+
required_outer,loop_count);
396+
add_path(rel, (Path*)bpath);
397+
}
332398
}
333399
}
334400

‎src/test/regress/expected/join.out

Lines changed: 17 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -2731,11 +2731,13 @@ where t1.unique1 = 1;
27312731
Index Cond: (unique1 = 1)
27322732
-> Nested Loop
27332733
Join Filter: (t1.ten = t3.ten)
2734-
-> Index Scan using tenk1_hundred on tenk1 t2
2735-
Index Cond: (t1.hundred = hundred)
2734+
-> Bitmap Heap Scan on tenk1 t2
2735+
Recheck Cond: (t1.hundred = hundred)
2736+
-> Bitmap Index Scan on tenk1_hundred
2737+
Index Cond: (t1.hundred = hundred)
27362738
-> Index Scan using tenk1_unique2 on tenk1 t3
27372739
Index Cond: (unique2 = t2.thousand)
2738-
(9 rows)
2740+
(11 rows)
27392741

27402742
explain (costs off)
27412743
select * from tenk1 t1 left join
@@ -2749,32 +2751,36 @@ where t1.unique1 = 1;
27492751
Index Cond: (unique1 = 1)
27502752
-> Nested Loop
27512753
Join Filter: ((t1.ten + t2.ten) = t3.ten)
2752-
-> Index Scan using tenk1_hundred on tenk1 t2
2753-
Index Cond: (t1.hundred = hundred)
2754+
-> Bitmap Heap Scan on tenk1 t2
2755+
Recheck Cond: (t1.hundred = hundred)
2756+
-> Bitmap Index Scan on tenk1_hundred
2757+
Index Cond: (t1.hundred = hundred)
27542758
-> Index Scan using tenk1_unique2 on tenk1 t3
27552759
Index Cond: (unique2 = t2.thousand)
2756-
(9 rows)
2760+
(11 rows)
27572761

27582762
explain (costs off)
27592763
select count(*) from
27602764
tenk1 a join tenk1 b on a.unique1 = b.unique2
27612765
left join tenk1 c on a.unique2 = b.unique1 and c.thousand = a.thousand
27622766
join int4_tbl on b.thousand = f1;
2763-
QUERY PLAN
2764-
--------------------------------------------------------------------------
2767+
QUERY PLAN
2768+
-------------------------------------------------------------------------
27652769
Aggregate
27662770
-> Nested Loop Left Join
27672771
Join Filter: (a.unique2 = b.unique1)
27682772
-> Nested Loop
27692773
-> Nested Loop
27702774
-> Seq Scan on int4_tbl
2771-
-> Index Scan using tenk1_thous_tenthous on tenk1 b
2772-
Index Cond: (thousand = int4_tbl.f1)
2775+
-> Bitmap Heap Scan on tenk1 b
2776+
Recheck Cond: (thousand = int4_tbl.f1)
2777+
-> Bitmap Index Scan on tenk1_thous_tenthous
2778+
Index Cond: (thousand = int4_tbl.f1)
27732779
-> Index Scan using tenk1_unique1 on tenk1 a
27742780
Index Cond: (unique1 = b.unique2)
27752781
-> Index Only Scan using tenk1_thous_tenthous on tenk1 c
27762782
Index Cond: (thousand = a.thousand)
2777-
(12 rows)
2783+
(14 rows)
27782784

27792785
select count(*) from
27802786
tenk1 a join tenk1 b on a.unique1 = b.unique2

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp