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

Commit056467e

Browse files
committed
Teach planner how to propagate pathkeys from sub-SELECTs in FROM up to
the outer query. (The implementation is a bit klugy, but it would takenontrivial restructuring to make it nicer, which this is probably notworth.) This avoids unnecessary sort steps in examples likeSELECT foo,count(*) FROM (SELECT ... ORDER BY foo,bar) sub GROUP BY foowhich means there is now a reasonable technique for controlling theorder of inputs to custom aggregates, even in the grouping case.
1 parent50c4190 commit056467e

File tree

9 files changed

+172
-29
lines changed

9 files changed

+172
-29
lines changed

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

Lines changed: 6 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88
*
99
*
1010
* IDENTIFICATION
11-
* $Header: /cvsroot/pgsql/src/backend/optimizer/path/allpaths.c,v 1.96 2003/02/08 20:20:54 tgl Exp $
11+
* $Header: /cvsroot/pgsql/src/backend/optimizer/path/allpaths.c,v 1.97 2003/02/15 20:12:40 tgl Exp $
1212
*
1313
*-------------------------------------------------------------------------
1414
*/
@@ -291,6 +291,7 @@ set_subquery_pathlist(Query *root, RelOptInfo *rel,
291291
Indexrti,RangeTblEntry*rte)
292292
{
293293
Query*subquery=rte->subquery;
294+
List*pathkeys;
294295

295296
/*
296297
* If there are any restriction clauses that have been attached to the
@@ -351,8 +352,11 @@ set_subquery_pathlist(Query *root, RelOptInfo *rel,
351352
/* Mark rel with estimated output rows, width, etc */
352353
set_baserel_size_estimates(root,rel);
353354

355+
/* Convert subquery pathkeys to outer representation */
356+
pathkeys=build_subquery_pathkeys(root,rel,subquery);
357+
354358
/* Generate appropriate path */
355-
add_path(rel,create_subqueryscan_path(rel));
359+
add_path(rel,create_subqueryscan_path(rel,pathkeys));
356360

357361
/* Select cheapest path (pretty easy in this case...) */
358362
set_cheapest(rel);

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

Lines changed: 138 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -11,7 +11,7 @@
1111
* Portions Copyright (c) 1994, Regents of the University of California
1212
*
1313
* IDENTIFICATION
14-
* $Header: /cvsroot/pgsql/src/backend/optimizer/path/pathkeys.c,v 1.46 2003/02/08 20:20:54 tgl Exp $
14+
* $Header: /cvsroot/pgsql/src/backend/optimizer/path/pathkeys.c,v 1.47 2003/02/15 20:12:40 tgl Exp $
1515
*
1616
*-------------------------------------------------------------------------
1717
*/
@@ -366,6 +366,31 @@ canonicalize_pathkeys(Query *root, List *pathkeys)
366366
returnnew_pathkeys;
367367
}
368368

369+
370+
/*
371+
* count_canonical_peers
372+
* Given a PathKeyItem, find the equi_key_list subset it is a member of,
373+
* if any. If so, return the number of other members of the set.
374+
* If not, return 0 (without actually adding it to our equi_key_list).
375+
*
376+
* This is a hack to support the rather bogus heuristics in
377+
* build_subquery_pathkeys.
378+
*/
379+
staticint
380+
count_canonical_peers(Query*root,PathKeyItem*item)
381+
{
382+
List*cursetlink;
383+
384+
foreach(cursetlink,root->equi_key_list)
385+
{
386+
List*curset=lfirst(cursetlink);
387+
388+
if (member(item,curset))
389+
returnlength(curset)-1;
390+
}
391+
return0;
392+
}
393+
369394
/****************************************************************************
370395
*PATHKEY COMPARISONS
371396
****************************************************************************/
@@ -597,6 +622,9 @@ get_cheapest_fractional_path_for_pathkeys(List *paths,
597622
*
598623
* If 'scandir' is BackwardScanDirection, attempt to build pathkeys
599624
* representing a backwards scan of the index.Return NIL if can't do it.
625+
*
626+
* We generate the full pathkeys list whether or not all are useful for the
627+
* current query. Caller should do truncate_useless_pathkeys().
600628
*/
601629
List*
602630
build_index_pathkeys(Query*root,
@@ -699,9 +727,10 @@ find_indexkey_var(Query *root, RelOptInfo *rel, AttrNumber varattno)
699727

700728
foreach(temp,rel->targetlist)
701729
{
702-
Var*tle_var=get_expr(lfirst(temp));
730+
Var*tle_var=(Var*) ((TargetEntry*)lfirst(temp))->expr;
703731

704-
if (IsA(tle_var,Var)&&tle_var->varattno==varattno)
732+
if (IsA(tle_var,Var)&&
733+
tle_var->varattno==varattno)
705734
returntle_var;
706735
}
707736

@@ -714,6 +743,112 @@ find_indexkey_var(Query *root, RelOptInfo *rel, AttrNumber varattno)
714743
returnmakeVar(relid,varattno,vartypeid,type_mod,0);
715744
}
716745

746+
/*
747+
* build_subquery_pathkeys
748+
* Build a pathkeys list that describes the ordering of a subquery's
749+
* result (in the terms of the outer query). The subquery must already
750+
* have been planned, so that its query_pathkeys field has been set.
751+
*
752+
* It is not necessary for caller to do truncate_useless_pathkeys(),
753+
* because we select keys in a way that takes usefulness of the keys into
754+
* account.
755+
*/
756+
List*
757+
build_subquery_pathkeys(Query*root,RelOptInfo*rel,Query*subquery)
758+
{
759+
List*retval=NIL;
760+
intretvallen=0;
761+
intouter_query_keys=length(root->query_pathkeys);
762+
List*l;
763+
764+
foreach(l,subquery->query_pathkeys)
765+
{
766+
List*sub_pathkey= (List*)lfirst(l);
767+
List*j;
768+
PathKeyItem*best_item=NULL;
769+
intbest_score=0;
770+
List*cpathkey;
771+
772+
/*
773+
* The sub_pathkey could contain multiple elements (representing
774+
* knowledge that multiple items are effectively equal). Each
775+
* element might match none, one, or more of the output columns
776+
* that are visible to the outer query. This means we may have
777+
* multiple possible representations of the sub_pathkey in the
778+
* context of the outer query. Ideally we would generate them all
779+
* and put them all into a pathkey list of the outer query, thereby
780+
* propagating equality knowledge up to the outer query. Right now
781+
* we cannot do so, because the outer query's canonical pathkey
782+
* sets are already frozen when this is called. Instead we prefer
783+
* the one that has the highest "score" (number of canonical pathkey
784+
* peers, plus one if it matches the outer query_pathkeys).
785+
* This is the most likely to be useful in the outer query.
786+
*/
787+
foreach(j,sub_pathkey)
788+
{
789+
PathKeyItem*sub_item= (PathKeyItem*)lfirst(j);
790+
Node*sub_key=sub_item->key;
791+
List*k;
792+
793+
foreach(k,subquery->targetList)
794+
{
795+
TargetEntry*tle= (TargetEntry*)lfirst(k);
796+
797+
if (!tle->resdom->resjunk&&
798+
equal(tle->expr,sub_key))
799+
{
800+
/* Found a representation for this sub_key */
801+
Var*outer_var;
802+
PathKeyItem*outer_item;
803+
intscore;
804+
805+
outer_var=makeVar(rel->relid,
806+
tle->resdom->resno,
807+
tle->resdom->restype,
808+
tle->resdom->restypmod,
809+
0);
810+
outer_item=makePathKeyItem((Node*)outer_var,
811+
sub_item->sortop);
812+
/* score = # of mergejoin peers */
813+
score=count_canonical_peers(root,outer_item);
814+
/* +1 if it matches the proper query_pathkeys item */
815+
if (retvallen<outer_query_keys&&
816+
member(outer_item,
817+
nth(retvallen,root->query_pathkeys)))
818+
score++;
819+
if (score>best_score)
820+
{
821+
best_item=outer_item;
822+
best_score=score;
823+
}
824+
}
825+
}
826+
}
827+
828+
/*
829+
* If we couldn't find a representation of this sub_pathkey,
830+
* we're done (we can't use the ones to its right, either).
831+
*/
832+
if (!best_item)
833+
break;
834+
835+
/* Canonicalize the chosen item (we did not before) */
836+
cpathkey=make_canonical_pathkey(root,best_item);
837+
838+
/*
839+
* Eliminate redundant ordering info; could happen if outer
840+
* query equijoins subquery keys...
841+
*/
842+
if (!ptrMember(cpathkey,retval))
843+
{
844+
retval=lappend(retval,cpathkey);
845+
retvallen++;
846+
}
847+
}
848+
849+
returnretval;
850+
}
851+
717852
/*
718853
* build_join_pathkeys
719854
* Build the path keys for a join relation constructed by mergejoin or

‎src/backend/optimizer/plan/planner.c

Lines changed: 15 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88
*
99
*
1010
* IDENTIFICATION
11-
* $Header: /cvsroot/pgsql/src/backend/optimizer/plan/planner.c,v 1.146 2003/02/09 23:57:19 tgl Exp $
11+
* $Header: /cvsroot/pgsql/src/backend/optimizer/plan/planner.c,v 1.147 2003/02/15 20:12:40 tgl Exp $
1212
*
1313
*-------------------------------------------------------------------------
1414
*/
@@ -469,6 +469,9 @@ inheritance_planner(Query *parse, List *inheritlist)
469469
/* Save the target-relations list for the executor, too */
470470
parse->resultRelations=inheritlist;
471471

472+
/* Mark result as unordered (probably unnecessary) */
473+
parse->query_pathkeys=NIL;
474+
472475
return (Plan*)make_append(subplans, true,tlist);
473476
}
474477

@@ -491,7 +494,8 @@ inheritance_planner(Query *parse, List *inheritlist)
491494
* The normal case is to pass -1, but some callers pass values >= 0 to
492495
* override this routine's determination of the appropriate fraction.
493496
*
494-
* Returns a query plan.
497+
* Returns a query plan. Also, parse->query_pathkeys is returned as the
498+
* actual output ordering of the plan (in pathkey format).
495499
*--------------------
496500
*/
497501
staticPlan*
@@ -1191,10 +1195,13 @@ grouping_planner(Query *parse, double tuple_fraction)
11911195
if (parse->sortClause)
11921196
{
11931197
if (!pathkeys_contained_in(sort_pathkeys,current_pathkeys))
1198+
{
11941199
result_plan= (Plan*)make_sort_from_sortclauses(parse,
11951200
tlist,
11961201
result_plan,
11971202
parse->sortClause);
1203+
current_pathkeys=sort_pathkeys;
1204+
}
11981205
}
11991206

12001207
/*
@@ -1232,6 +1239,12 @@ grouping_planner(Query *parse, double tuple_fraction)
12321239
parse->limitCount);
12331240
}
12341241

1242+
/*
1243+
* Return the actual output ordering in query_pathkeys for possible
1244+
* use by an outer query level.
1245+
*/
1246+
parse->query_pathkeys=current_pathkeys;
1247+
12351248
returnresult_plan;
12361249
}
12371250

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

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88
*
99
*
1010
* IDENTIFICATION
11-
* $Header: /cvsroot/pgsql/src/backend/optimizer/util/pathnode.c,v 1.87 2003/02/08 20:20:55 tgl Exp $
11+
* $Header: /cvsroot/pgsql/src/backend/optimizer/util/pathnode.c,v 1.88 2003/02/15 20:12:40 tgl Exp $
1212
*
1313
*-------------------------------------------------------------------------
1414
*/
@@ -676,13 +676,13 @@ hash_safe_tlist(List *tlist)
676676
* returning the pathnode.
677677
*/
678678
Path*
679-
create_subqueryscan_path(RelOptInfo*rel)
679+
create_subqueryscan_path(RelOptInfo*rel,List*pathkeys)
680680
{
681681
Path*pathnode=makeNode(Path);
682682

683683
pathnode->pathtype=T_SubqueryScan;
684684
pathnode->parent=rel;
685-
pathnode->pathkeys=NIL;/* for now, assume unordered result */
685+
pathnode->pathkeys=pathkeys;
686686

687687
/* just copy the subplan's cost estimates */
688688
pathnode->startup_cost=rel->subplan->startup_cost;

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

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88
*
99
*
1010
* IDENTIFICATION
11-
* $Header: /cvsroot/pgsql/src/backend/optimizer/util/relnode.c,v 1.47 2003/02/08 20:20:55 tgl Exp $
11+
* $Header: /cvsroot/pgsql/src/backend/optimizer/util/relnode.c,v 1.48 2003/02/15 20:12:40 tgl Exp $
1212
*
1313
*-------------------------------------------------------------------------
1414
*/
@@ -381,11 +381,11 @@ new_join_tlist(List *tlist,
381381

382382
foreach(i,tlist)
383383
{
384-
TargetEntry*xtl=lfirst(i);
384+
TargetEntry*tle=lfirst(i);
385385

386386
resdomno+=1;
387387
t_list=lappend(t_list,
388-
create_tl_element(get_expr(xtl),resdomno));
388+
create_tl_element((Var*)tle->expr,resdomno));
389389
}
390390

391391
returnt_list;

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

Lines changed: 1 addition & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88
*
99
*
1010
* IDENTIFICATION
11-
* $Header: /cvsroot/pgsql/src/backend/optimizer/util/tlist.c,v 1.54 2003/01/20 18:54:57 tgl Exp $
11+
* $Header: /cvsroot/pgsql/src/backend/optimizer/util/tlist.c,v 1.55 2003/02/15 20:12:40 tgl Exp $
1212
*
1313
*-------------------------------------------------------------------------
1414
*/
@@ -204,15 +204,6 @@ add_to_flat_tlist(List *tlist, List *vars)
204204
returntlist;
205205
}
206206

207-
Var*
208-
get_expr(TargetEntry*tle)
209-
{
210-
Assert(tle!=NULL);
211-
Assert(tle->expr!=NULL);
212-
213-
return (Var*)tle->expr;
214-
}
215-
216207
/*
217208
* get_sortgroupclause_tle
218209
*Find the targetlist entry matching the given SortClause

‎src/include/optimizer/pathnode.h

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -7,7 +7,7 @@
77
* Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group
88
* Portions Copyright (c) 1994, Regents of the University of California
99
*
10-
* $Id: pathnode.h,v 1.49 2003/02/08 20:20:55 tgl Exp $
10+
* $Id: pathnode.h,v 1.50 2003/02/15 20:12:41 tgl Exp $
1111
*
1212
*-------------------------------------------------------------------------
1313
*/
@@ -41,7 +41,7 @@ extern ResultPath *create_result_path(RelOptInfo *rel, Path *subpath,
4141
externMaterialPath*create_material_path(RelOptInfo*rel,Path*subpath);
4242
externUniquePath*create_unique_path(Query*root,RelOptInfo*rel,
4343
Path*subpath);
44-
externPath*create_subqueryscan_path(RelOptInfo*rel);
44+
externPath*create_subqueryscan_path(RelOptInfo*rel,List*pathkeys);
4545
externPath*create_functionscan_path(Query*root,RelOptInfo*rel);
4646

4747
externNestPath*create_nestloop_path(Query*root,

‎src/include/optimizer/paths.h

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88
* Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group
99
* Portions Copyright (c) 1994, Regents of the University of California
1010
*
11-
* $Id: paths.h,v 1.65 2003/01/25 23:10:30 tgl Exp $
11+
* $Id: paths.h,v 1.66 2003/02/15 20:12:41 tgl Exp $
1212
*
1313
*-------------------------------------------------------------------------
1414
*/
@@ -104,6 +104,8 @@ extern Path *get_cheapest_fractional_path_for_pathkeys(List *paths,
104104
externList*build_index_pathkeys(Query*root,RelOptInfo*rel,
105105
IndexOptInfo*index,
106106
ScanDirectionscandir);
107+
externList*build_subquery_pathkeys(Query*root,RelOptInfo*rel,
108+
Query*subquery);
107109
externList*build_join_pathkeys(Query*root,
108110
RelOptInfo*joinrel,
109111
List*outer_pathkeys);

‎src/include/optimizer/tlist.h

Lines changed: 1 addition & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -7,7 +7,7 @@
77
* Portions Copyright (c) 1996-2002, PostgreSQL Global Development Group
88
* Portions Copyright (c) 1994, Regents of the University of California
99
*
10-
* $Id: tlist.h,v 1.33 2003/01/20 18:55:06 tgl Exp $
10+
* $Id: tlist.h,v 1.34 2003/02/15 20:12:41 tgl Exp $
1111
*
1212
*-------------------------------------------------------------------------
1313
*/
@@ -26,8 +26,6 @@ extern List *new_unsorted_tlist(List *targetlist);
2626
externList*flatten_tlist(List*tlist);
2727
externList*add_to_flat_tlist(List*tlist,List*vars);
2828

29-
externVar*get_expr(TargetEntry*tle);
30-
3129
externTargetEntry*get_sortgroupclause_tle(SortClause*sortClause,
3230
List*targetList);
3331
externNode*get_sortgroupclause_expr(SortClause*sortClause,

0 commit comments

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