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

Commite8140ad

Browse files
committed
Further sort-order twiddling in optimizer: be smart about
case where ORDER BY and GROUP BY request the same sort order.
1 parentc9d040d commite8140ad

File tree

4 files changed

+97
-57
lines changed

4 files changed

+97
-57
lines changed

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

Lines changed: 6 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -9,7 +9,7 @@
99
*
1010
*
1111
* IDENTIFICATION
12-
* $Header: /cvsroot/pgsql/src/backend/optimizer/plan/createplan.c,v 1.75 1999/08/2220:14:47 tgl Exp $
12+
* $Header: /cvsroot/pgsql/src/backend/optimizer/plan/createplan.c,v 1.76 1999/08/2223:56:44 tgl Exp $
1313
*
1414
*-------------------------------------------------------------------------
1515
*/
@@ -51,7 +51,6 @@ static List *fix_indxqual_sublist(List *indexqual, IndexPath *index_path,
5151
Form_pg_indexindex);
5252
staticNode*fix_indxqual_operand(Node*node,IndexPath*index_path,
5353
Form_pg_indexindex);
54-
staticNoname*make_noname(List*tlist,List*pathkeys,Plan*plan_node);
5554
staticIndexScan*make_indexscan(List*qptlist,List*qpqual,Indexscanrelid,
5655
List*indxid,List*indxqual,List*indxqualorig);
5756
staticNestLoop*make_nestloop(List*qptlist,List*qpqual,Plan*lefttree,
@@ -926,12 +925,12 @@ copy_costsize(Plan *dest, Plan *src)
926925
* 'tlist' is the target list of the scan to be sorted or materialized
927926
* 'pathkeys' is the list of pathkeys by which the result is to be sorted
928927
*(NIL implies no sort needed, just materialize it)
929-
* 'plan_node' is the node which yields input tuples
928+
* 'subplan' is the node which yields input tuples
930929
*/
931-
staticNoname*
930+
Noname*
932931
make_noname(List*tlist,
933932
List*pathkeys,
934-
Plan*plan_node)
933+
Plan*subplan)
935934
{
936935
List*noname_tlist;
937936
intnumsortkeys;
@@ -946,15 +945,15 @@ make_noname(List *tlist,
946945
/* need to sort */
947946
retval= (Plan*)make_sort(noname_tlist,
948947
_NONAME_RELATION_ID_,
949-
plan_node,
948+
subplan,
950949
numsortkeys);
951950
}
952951
else
953952
{
954953
/* no sort */
955954
retval= (Plan*)make_material(noname_tlist,
956955
_NONAME_RELATION_ID_,
957-
plan_node,
956+
subplan,
958957
0);
959958
}
960959

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

Lines changed: 30 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -7,7 +7,7 @@
77
*
88
*
99
* IDENTIFICATION
10-
* $Header: /cvsroot/pgsql/src/backend/optimizer/plan/planmain.c,v 1.42 1999/08/2220:14:48 tgl Exp $
10+
* $Header: /cvsroot/pgsql/src/backend/optimizer/plan/planmain.c,v 1.43 1999/08/2223:56:45 tgl Exp $
1111
*
1212
*-------------------------------------------------------------------------
1313
*/
@@ -44,11 +44,14 @@ static Plan *subplanner(Query *root, List *flat_tlist, List *qual);
4444
* qual is the qualification of the query
4545
*
4646
* Note: the Query node now also includes a query_pathkeys field, which
47+
* is both an input and an output of query_planner(). The input value
4748
* signals query_planner that the indicated sort order is wanted in the
48-
* final output plan. If, for some reason, query_planner is unable to
49-
* comply, it sets query_pathkeys to NIL before returning. (The reason
50-
* query_pathkeys is a Query field and not a passed parameter is that
51-
* the low-level routines in indxpath.c need to see it.)
49+
* final output plan. The output value is the actual pathkeys of the
50+
* selected path. This might not be the same as what the caller requested;
51+
* the caller must do pathkeys_contained_in() to decide whether an
52+
* explicit sort is still needed. (The main reason query_pathkeys is a
53+
* Query field and not a passed parameter is that the low-level routines
54+
* in indxpath.c need to see it.)
5255
*
5356
* Returns a query plan.
5457
*/
@@ -255,7 +258,11 @@ subplanner(Query *root,
255258
if (root->query_pathkeys==NIL||
256259
pathkeys_contained_in(root->query_pathkeys,
257260
final_rel->cheapestpath->pathkeys))
261+
{
262+
root->query_pathkeys=final_rel->cheapestpath->pathkeys;
258263
returncreate_plan(final_rel->cheapestpath);
264+
}
265+
259266
/*
260267
* Otherwise, look to see if we have an already-ordered path that is
261268
* cheaper than doing an explicit sort on cheapestpath.
@@ -271,6 +278,7 @@ subplanner(Query *root,
271278
if (sortedpath->path_cost <=cheapest_cost)
272279
{
273280
/* Found a better presorted path, use it */
281+
root->query_pathkeys=sortedpath->pathkeys;
274282
returncreate_plan(sortedpath);
275283
}
276284
/* otherwise, doing it the hard way is still cheaper */
@@ -300,21 +308,31 @@ subplanner(Query *root,
300308
* then poke the result.
301309
*/
302310
Plan*sortedplan=create_plan(sortedpath);
311+
List*sortedpathkeys;
303312

304313
Assert(IsA(sortedplan,IndexScan));
305314
((IndexScan*)sortedplan)->indxorderdir=BackwardScanDirection;
315+
/*
316+
* Need to generate commuted keys representing the actual
317+
* sort order. This should succeed, probably, but just in
318+
* case it does not, use the original root->query_pathkeys
319+
* as a conservative approximation.
320+
*/
321+
sortedpathkeys=copyObject(sortedpath->pathkeys);
322+
if (commute_pathkeys(sortedpathkeys))
323+
root->query_pathkeys=sortedpathkeys;
324+
306325
returnsortedplan;
307326
}
308327
}
309328
}
310329

311-
/* Nothing for it but to sort the cheapestpath...
312-
*
313-
*We indicate we failed to sort the plan, and let thecaller
314-
*stick the appropriate sort node on top. union_planner has to be
315-
*able to add a sort node anyway, so no need for extra code here.
330+
/* Nothing for it but to sort the cheapestpath --- but we let the
331+
* caller do that. union_planner has to be able to add a sort node
332+
*anyway, so no need for extra code here. (Furthermore, thegiven
333+
*pathkeys might involve something we can't compute yet, such as
334+
*an aggregate function...)
316335
*/
317-
root->query_pathkeys=NIL;/* sorry, it ain't sorted */
318-
336+
root->query_pathkeys=final_rel->cheapestpath->pathkeys;
319337
returncreate_plan(final_rel->cheapestpath);
320338
}

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

Lines changed: 59 additions & 37 deletions
Original file line numberDiff line numberDiff line change
@@ -7,7 +7,7 @@
77
*
88
*
99
* IDENTIFICATION
10-
* $Header: /cvsroot/pgsql/src/backend/optimizer/plan/planner.c,v 1.64 1999/08/2220:14:48 tgl Exp $
10+
* $Header: /cvsroot/pgsql/src/backend/optimizer/plan/planner.c,v 1.65 1999/08/2223:56:45 tgl Exp $
1111
*
1212
*-------------------------------------------------------------------------
1313
*/
@@ -39,7 +39,7 @@ static List *make_subplanTargetList(Query *parse, List *tlist,
3939
AttrNumber**groupColIdx);
4040
staticPlan*make_groupplan(List*group_tlist,booltuplePerGroup,
4141
List*groupClause,AttrNumber*grpColIdx,
42-
boolis_sorted,Plan*subplan);
42+
boolis_presorted,Plan*subplan);
4343
staticPlan*make_sortplan(List*tlist,List*sortcls,Plan*plannode);
4444

4545
/*****************************************************************************
@@ -91,7 +91,7 @@ union_planner(Query *parse)
9191
List*rangetable=parse->rtable;
9292
Plan*result_plan= (Plan*)NULL;
9393
AttrNumber*groupColIdx=NULL;
94-
boolis_sorted= false;
94+
List*current_pathkeys=NIL;
9595
Indexrt_index;
9696

9797
if (parse->unionClause)
@@ -102,6 +102,11 @@ union_planner(Query *parse)
102102
parse->commandType,
103103
parse->resultRelation,
104104
parse->rtable);
105+
/*
106+
* We leave current_pathkeys NIL indicating we do not know sort order.
107+
* Actually, for a normal UNION we have done an explicit sort; ought
108+
* to change interface to plan_union_queries to pass that info back!
109+
*/
105110
}
106111
elseif ((rt_index=first_inherit_rt_entry(rangetable))!=-1)
107112
{
@@ -135,6 +140,10 @@ union_planner(Query *parse)
135140

136141
if (parse->rowMark!=NULL)
137142
elog(ERROR,"SELECT FOR UPDATE is not supported for inherit queries");
143+
/*
144+
* We leave current_pathkeys NIL indicating we do not know sort order
145+
* of the Append-ed results.
146+
*/
138147
}
139148
else
140149
{
@@ -182,25 +191,25 @@ union_planner(Query *parse)
182191
}
183192
}
184193

194+
/*
195+
* Generate appropriate target list for subplan; may be different
196+
* from tlist if grouping or aggregation is needed.
197+
*/
198+
sub_tlist=make_subplanTargetList(parse,tlist,&groupColIdx);
199+
185200
/*
186201
* Figure out whether we need a sorted result from query_planner.
187202
*
188203
* If we have a GROUP BY clause, then we want a result sorted
189-
* properly for grouping. Otherwise, if there is an ORDER BY clause
190-
* and no need for an aggregate node, we want to sort by the ORDER BY
191-
* clause. (XXX In some cases, we could presort even when there is
192-
* an aggregate, but I'll leave that refinement for another day.)
193-
*
194-
* NOTE: the reason we put the target pathkeys into the Query node
195-
* rather than passing them as an argument to query_planner is that
196-
* the low-level routines in indxpath.c want to be able to see them.
204+
* properly for grouping. Otherwise, if there is an ORDER BY clause,
205+
* we want to sort by the ORDER BY clause.
197206
*/
198207
if (parse->groupClause)
199208
{
200209
parse->query_pathkeys=
201210
make_pathkeys_for_sortclauses(parse->groupClause,tlist);
202211
}
203-
elseif (parse->sortClause&& !parse->hasAggs)
212+
elseif (parse->sortClause)
204213
{
205214
parse->query_pathkeys=
206215
make_pathkeys_for_sortclauses(parse->sortClause,tlist);
@@ -210,23 +219,16 @@ union_planner(Query *parse)
210219
parse->query_pathkeys=NIL;
211220
}
212221

213-
/*
214-
* Generate appropriate target list for subplan; may be different
215-
* from tlist if grouping or aggregation is needed.
216-
*/
217-
sub_tlist=make_subplanTargetList(parse,tlist,&groupColIdx);
218-
219222
/* Generate the (sub) plan */
220223
result_plan=query_planner(parse,
221224
parse->commandType,
222225
sub_tlist,
223226
(List*)parse->qual);
224227

225-
/* query_plannersets query_pathkeys to NIL if it didn't make
226-
*a properly sorted plan
228+
/* query_plannerreturns actual sort order (which is not
229+
*necessarily what we requested) in query_pathkeys.
227230
*/
228-
if (parse->query_pathkeys)
229-
is_sorted= true;
231+
current_pathkeys=parse->query_pathkeys;
230232
}
231233

232234
/* query_planner returns NULL if it thinks plan is bogus */
@@ -241,6 +243,8 @@ union_planner(Query *parse)
241243
{
242244
booltuplePerGroup;
243245
List*group_tlist;
246+
List*group_pathkeys;
247+
boolis_sorted;
244248

245249
/*
246250
* Decide whether how many tuples per group the Group node needs
@@ -261,18 +265,33 @@ union_planner(Query *parse)
261265
else
262266
group_tlist=tlist;
263267

268+
/*
269+
* Figure out whether the path result is already ordered the way we
270+
* need it --- if so, no need for an explicit sort step.
271+
*/
272+
group_pathkeys=make_pathkeys_for_sortclauses(parse->groupClause,
273+
tlist);
274+
if (pathkeys_contained_in(group_pathkeys,current_pathkeys))
275+
{
276+
is_sorted= true;/* no sort needed now */
277+
/* current_pathkeys remains unchanged */
278+
}
279+
else
280+
{
281+
/* We will need to do an explicit sort by the GROUP BY clause.
282+
* make_groupplan will do the work, but set current_pathkeys
283+
* to indicate the resulting order.
284+
*/
285+
is_sorted= false;
286+
current_pathkeys=group_pathkeys;
287+
}
288+
264289
result_plan=make_groupplan(group_tlist,
265290
tuplePerGroup,
266291
parse->groupClause,
267292
groupColIdx,
268293
is_sorted,
269294
result_plan);
270-
271-
/*
272-
* Assume the result of the group step is not ordered suitably
273-
* for any ORDER BY that may exist. XXX it might be; improve this!
274-
*/
275-
is_sorted= false;
276295
}
277296

278297
/*
@@ -325,20 +344,23 @@ union_planner(Query *parse)
325344
/* HAVING clause, if any, becomes qual of the Agg node */
326345
result_plan->qual= (List*)parse->havingQual;
327346

328-
/*
329-
* Assume result is not ordered suitably for ORDER BY.
330-
* XXX it might be; improve this!
331-
*/
332-
is_sorted= false;
347+
/* Note: Agg does not affect any existing sort order of the tuples */
333348
}
334349

335350
/*
336351
* If we were not able to make the plan come out in the right order,
337352
* add an explicit sort step.
338353
*/
339-
if (parse->sortClause&& !is_sorted)
354+
if (parse->sortClause)
340355
{
341-
result_plan=make_sortplan(tlist,parse->sortClause,result_plan);
356+
List*sort_pathkeys;
357+
358+
sort_pathkeys=make_pathkeys_for_sortclauses(parse->sortClause,
359+
tlist);
360+
if (!pathkeys_contained_in(sort_pathkeys,current_pathkeys))
361+
{
362+
result_plan=make_sortplan(tlist,parse->sortClause,result_plan);
363+
}
342364
}
343365

344366
/*
@@ -474,12 +496,12 @@ make_groupplan(List *group_tlist,
474496
booltuplePerGroup,
475497
List*groupClause,
476498
AttrNumber*grpColIdx,
477-
boolis_sorted,
499+
boolis_presorted,
478500
Plan*subplan)
479501
{
480502
intnumCols=length(groupClause);
481503

482-
if (!is_sorted)
504+
if (!is_presorted)
483505
{
484506
/*
485507
* The Sort node always just takes a copy of the subplan's tlist

‎src/include/optimizer/planmain.h‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -6,7 +6,7 @@
66
*
77
* Copyright (c) 1994, Regents of the University of California
88
*
9-
* $Id: planmain.h,v 1.32 1999/08/2220:14:56 tgl Exp $
9+
* $Id: planmain.h,v 1.33 1999/08/2223:56:43 tgl Exp $
1010
*
1111
*-------------------------------------------------------------------------
1212
*/
@@ -33,6 +33,7 @@ extern Sort *make_sort(List *tlist, Oid nonameid, Plan *lefttree,
3333
externAgg*make_agg(List*tlist,Plan*lefttree);
3434
externGroup*make_group(List*tlist,booltuplePerGroup,intngrp,
3535
AttrNumber*grpColIdx,Plan*lefttree);
36+
externNoname*make_noname(List*tlist,List*pathkeys,Plan*subplan);
3637
externUnique*make_unique(List*tlist,Plan*lefttree,char*uniqueAttr);
3738
externResult*make_result(List*tlist,Node*resconstantqual,Plan*subplan);
3839

0 commit comments

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