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

Commit624e440

Browse files
committed
Improve the heuristic for ordering child paths of a parallel append.
Commitab72716 introduced code that attempts to order the childscans of a Parallel Append node in a way that will minimize executiontime, based on total cost and startup cost. However, it failed tothink hard about what to do when estimated costs are exactly equal;a case that's particularly likely to occur when comparing on startupcost. In such a case the ordering of the child paths would be leftto the whims of qsort, an algorithm that isn't even stable.We can improve matters by applying the rule used elsewhere in theplanner: if total costs are equal, sort on startup cost, andvice versa. When both cost estimates are exactly equal, ratherthan letting qsort do something unpredictable, sort based on thechild paths' relids, which should typically result in sorting ininheritance order. (The latter provision requires inventing aqsort-style comparator for bitmapsets, but maybe we'll have usefor that for other reasons in future.)This results in a few plan changes in the select_parallel test,but those all look more reasonable than before, when the actualunderlying cost numbers are taken into account.Discussion:https://postgr.es/m/4944.1515446989@sss.pgh.pa.us
1 parent80259d4 commit624e440

File tree

4 files changed

+73
-22
lines changed

4 files changed

+73
-22
lines changed

‎src/backend/nodes/bitmapset.c

Lines changed: 45 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -172,6 +172,50 @@ bms_equal(const Bitmapset *a, const Bitmapset *b)
172172
return true;
173173
}
174174

175+
/*
176+
* bms_compare - qsort-style comparator for bitmapsets
177+
*
178+
* This guarantees to report values as equal iff bms_equal would say they are
179+
* equal. Otherwise, the highest-numbered bit that is set in one value but
180+
* not the other determines the result. (This rule means that, for example,
181+
* {6} is greater than {5}, which seems plausible.)
182+
*/
183+
int
184+
bms_compare(constBitmapset*a,constBitmapset*b)
185+
{
186+
intshortlen;
187+
inti;
188+
189+
/* Handle cases where either input is NULL */
190+
if (a==NULL)
191+
returnbms_is_empty(b) ?0 :-1;
192+
elseif (b==NULL)
193+
returnbms_is_empty(a) ?0 :+1;
194+
/* Handle cases where one input is longer than the other */
195+
shortlen=Min(a->nwords,b->nwords);
196+
for (i=shortlen;i<a->nwords;i++)
197+
{
198+
if (a->words[i]!=0)
199+
return+1;
200+
}
201+
for (i=shortlen;i<b->nwords;i++)
202+
{
203+
if (b->words[i]!=0)
204+
return-1;
205+
}
206+
/* Process words in common */
207+
i=shortlen;
208+
while (--i >=0)
209+
{
210+
bitmapwordaw=a->words[i];
211+
bitmapwordbw=b->words[i];
212+
213+
if (aw!=bw)
214+
return (aw>bw) ?+1 :-1;
215+
}
216+
return0;
217+
}
218+
175219
/*
176220
* bms_make_singleton - build a bitmapset containing a single member
177221
*/
@@ -838,7 +882,7 @@ bms_add_range(Bitmapset *a, int lower, int upper)
838882
if (lwordnum==uwordnum)
839883
{
840884
a->words[lwordnum] |= ~(bitmapword) (((bitmapword)1 <<lbitnum)-1)
841-
& (~(bitmapword)0) >>ushiftbits;
885+
& (~(bitmapword)0) >>ushiftbits;
842886
}
843887
else
844888
{

‎src/backend/optimizer/util/pathnode.c

Lines changed: 20 additions & 14 deletions
Original file line numberDiff line numberDiff line change
@@ -1274,38 +1274,44 @@ create_append_path(RelOptInfo *rel,
12741274

12751275
/*
12761276
* append_total_cost_compare
1277-
* list_qsort comparator for sorting append child paths by total_cost
1277+
* qsort comparator for sorting append child paths by total_cost descending
1278+
*
1279+
* For equal total costs, we fall back to comparing startup costs; if those
1280+
* are equal too, break ties using bms_compare on the paths' relids.
1281+
* (This is to avoid getting unpredictable results from qsort.)
12781282
*/
12791283
staticint
12801284
append_total_cost_compare(constvoid*a,constvoid*b)
12811285
{
12821286
Path*path1= (Path*)lfirst(*(ListCell**)a);
12831287
Path*path2= (Path*)lfirst(*(ListCell**)b);
1288+
intcmp;
12841289

1285-
if (path1->total_cost>path2->total_cost)
1286-
return-1;
1287-
if (path1->total_cost<path2->total_cost)
1288-
return1;
1289-
1290-
return0;
1290+
cmp=compare_path_costs(path1,path2,TOTAL_COST);
1291+
if (cmp!=0)
1292+
return-cmp;
1293+
returnbms_compare(path1->parent->relids,path2->parent->relids);
12911294
}
12921295

12931296
/*
12941297
* append_startup_cost_compare
1295-
* list_qsort comparator for sorting append child paths by startup_cost
1298+
* qsort comparator for sorting append child paths by startup_cost descending
1299+
*
1300+
* For equal startup costs, we fall back to comparing total costs; if those
1301+
* are equal too, break ties using bms_compare on the paths' relids.
1302+
* (This is to avoid getting unpredictable results from qsort.)
12961303
*/
12971304
staticint
12981305
append_startup_cost_compare(constvoid*a,constvoid*b)
12991306
{
13001307
Path*path1= (Path*)lfirst(*(ListCell**)a);
13011308
Path*path2= (Path*)lfirst(*(ListCell**)b);
1309+
intcmp;
13021310

1303-
if (path1->startup_cost>path2->startup_cost)
1304-
return-1;
1305-
if (path1->startup_cost<path2->startup_cost)
1306-
return1;
1307-
1308-
return0;
1311+
cmp=compare_path_costs(path1,path2,STARTUP_COST);
1312+
if (cmp!=0)
1313+
return-cmp;
1314+
returnbms_compare(path1->parent->relids,path2->parent->relids);
13091315
}
13101316

13111317
/*

‎src/include/nodes/bitmapset.h

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -65,6 +65,7 @@ typedef enum
6565

6666
externBitmapset*bms_copy(constBitmapset*a);
6767
externboolbms_equal(constBitmapset*a,constBitmapset*b);
68+
externintbms_compare(constBitmapset*a,constBitmapset*b);
6869
externBitmapset*bms_make_singleton(intx);
6970
externvoidbms_free(Bitmapset*a);
7071

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

Lines changed: 7 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -21,12 +21,12 @@ explain (costs off)
2121
Workers Planned: 3
2222
-> Partial Aggregate
2323
-> Parallel Append
24-
-> Parallel Seq Scan on a_star
25-
-> Parallel Seq Scan on b_star
26-
-> Parallel Seq Scan on c_star
2724
-> Parallel Seq Scan on d_star
28-
-> Parallel Seq Scan on e_star
2925
-> Parallel Seq Scan on f_star
26+
-> Parallel Seq Scan on e_star
27+
-> Parallel Seq Scan on b_star
28+
-> Parallel Seq Scan on c_star
29+
-> Parallel Seq Scan on a_star
3030
(11 rows)
3131

3232
select round(avg(aa)), sum(aa) from a_star a1;
@@ -49,10 +49,10 @@ explain (costs off)
4949
-> Parallel Append
5050
-> Seq Scan on d_star
5151
-> Seq Scan on c_star
52-
-> Parallel Seq Scan on a_star
53-
-> Parallel Seq Scan on b_star
54-
-> Parallel Seq Scan on e_star
5552
-> Parallel Seq Scan on f_star
53+
-> Parallel Seq Scan on e_star
54+
-> Parallel Seq Scan on b_star
55+
-> Parallel Seq Scan on a_star
5656
(11 rows)
5757

5858
select round(avg(aa)), sum(aa) from a_star a2;

0 commit comments

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