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

Commitf598392

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 parent56ba337 commitf598392

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
@@ -2725,11 +2725,13 @@ where t1.unique1 = 1;
27252725
Index Cond: (unique1 = 1)
27262726
-> Nested Loop
27272727
Join Filter: (t1.ten = t3.ten)
2728-
-> Index Scan using tenk1_hundred on tenk1 t2
2729-
Index Cond: (t1.hundred = hundred)
2728+
-> Bitmap Heap Scan on tenk1 t2
2729+
Recheck Cond: (t1.hundred = hundred)
2730+
-> Bitmap Index Scan on tenk1_hundred
2731+
Index Cond: (t1.hundred = hundred)
27302732
-> Index Scan using tenk1_unique2 on tenk1 t3
27312733
Index Cond: (unique2 = t2.thousand)
2732-
(9 rows)
2734+
(11 rows)
27332735

27342736
explain (costs off)
27352737
select * from tenk1 t1 left join
@@ -2743,32 +2745,36 @@ where t1.unique1 = 1;
27432745
Index Cond: (unique1 = 1)
27442746
-> Nested Loop
27452747
Join Filter: ((t1.ten + t2.ten) = t3.ten)
2746-
-> Index Scan using tenk1_hundred on tenk1 t2
2747-
Index Cond: (t1.hundred = hundred)
2748+
-> Bitmap Heap Scan on tenk1 t2
2749+
Recheck Cond: (t1.hundred = hundred)
2750+
-> Bitmap Index Scan on tenk1_hundred
2751+
Index Cond: (t1.hundred = hundred)
27482752
-> Index Scan using tenk1_unique2 on tenk1 t3
27492753
Index Cond: (unique2 = t2.thousand)
2750-
(9 rows)
2754+
(11 rows)
27512755

27522756
explain (costs off)
27532757
select count(*) from
27542758
tenk1 a join tenk1 b on a.unique1 = b.unique2
27552759
left join tenk1 c on a.unique2 = b.unique1 and c.thousand = a.thousand
27562760
join int4_tbl on b.thousand = f1;
2757-
QUERY PLAN
2758-
--------------------------------------------------------------------------
2761+
QUERY PLAN
2762+
-------------------------------------------------------------------------
27592763
Aggregate
27602764
-> Nested Loop Left Join
27612765
Join Filter: (a.unique2 = b.unique1)
27622766
-> Nested Loop
27632767
-> Nested Loop
27642768
-> Seq Scan on int4_tbl
2765-
-> Index Scan using tenk1_thous_tenthous on tenk1 b
2766-
Index Cond: (thousand = int4_tbl.f1)
2769+
-> Bitmap Heap Scan on tenk1 b
2770+
Recheck Cond: (thousand = int4_tbl.f1)
2771+
-> Bitmap Index Scan on tenk1_thous_tenthous
2772+
Index Cond: (thousand = int4_tbl.f1)
27672773
-> Index Scan using tenk1_unique1 on tenk1 a
27682774
Index Cond: (unique1 = b.unique2)
27692775
-> Index Only Scan using tenk1_thous_tenthous on tenk1 c
27702776
Index Cond: (thousand = a.thousand)
2771-
(12 rows)
2777+
(14 rows)
27722778

27732779
select count(*) from
27742780
tenk1 a join tenk1 b on a.unique1 = b.unique2

0 commit comments

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