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

Commitea166f1

Browse files
committed
Planner speedup hacking. Avoid saving useless pathkeys, so that path
comparison does not consider paths different when they differ only inuninteresting aspects of sort order. (We had a special case of thisconsideration for indexscans already, but generalize it to apply toordered join paths too.) Be stricter about what is a canonical pathkeyto allow faster pathkey comparison. Cache canonical pathkeys anddispersion stats for left and right sides of a RestrictInfo's clause,to avoid repeated computation. Total speedup will depend on number oftables in a query, but I see about 4x speedup of planning phase fora sample seven-table query.
1 parentdb11f43 commitea166f1

File tree

16 files changed

+617
-360
lines changed

16 files changed

+617
-360
lines changed

‎src/backend/nodes/copyfuncs.c

Lines changed: 6 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -15,7 +15,7 @@
1515
* Portions Copyright (c) 1994, Regents of the University of California
1616
*
1717
* IDENTIFICATION
18-
* $Header: /cvsroot/pgsql/src/backend/nodes/copyfuncs.c,v 1.134 2000/12/12 23:33:32 tgl Exp $
18+
* $Header: /cvsroot/pgsql/src/backend/nodes/copyfuncs.c,v 1.135 2000/12/14 22:30:42 tgl Exp $
1919
*
2020
*-------------------------------------------------------------------------
2121
*/
@@ -1424,7 +1424,12 @@ _copyRestrictInfo(RestrictInfo *from)
14241424
newnode->mergejoinoperator=from->mergejoinoperator;
14251425
newnode->left_sortop=from->left_sortop;
14261426
newnode->right_sortop=from->right_sortop;
1427+
/* Do not copy pathkeys, since they'd not be canonical in a copied query */
1428+
newnode->left_pathkey=NIL;
1429+
newnode->right_pathkey=NIL;
14271430
newnode->hashjoinoperator=from->hashjoinoperator;
1431+
newnode->left_dispersion=from->left_dispersion;
1432+
newnode->right_dispersion=from->right_dispersion;
14281433

14291434
returnnewnode;
14301435
}

‎src/backend/nodes/equalfuncs.c

Lines changed: 4 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -20,7 +20,7 @@
2020
* Portions Copyright (c) 1994, Regents of the University of California
2121
*
2222
* IDENTIFICATION
23-
* $Header: /cvsroot/pgsql/src/backend/nodes/equalfuncs.c,v 1.84 2000/12/12 23:33:33 tgl Exp $
23+
* $Header: /cvsroot/pgsql/src/backend/nodes/equalfuncs.c,v 1.85 2000/12/14 22:30:42 tgl Exp $
2424
*
2525
*-------------------------------------------------------------------------
2626
*/
@@ -515,8 +515,9 @@ _equalRestrictInfo(RestrictInfo *a, RestrictInfo *b)
515515
if (!equal(a->clause,b->clause))
516516
return false;
517517
/*
518-
* ignore eval_cost, since it may not be set yet, and should be
519-
* derivable from the clause anyway
518+
* ignore eval_cost, left/right_pathkey, and left/right_dispersion,
519+
* since they may not be set yet, and should be derivable from the
520+
* clause anyway
520521
*/
521522
if (a->ispusheddown!=b->ispusheddown)
522523
return false;

‎src/backend/nodes/readfuncs.c

Lines changed: 6 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@
88
*
99
*
1010
* IDENTIFICATION
11-
* $Header: /cvsroot/pgsql/src/backend/nodes/readfuncs.c,v 1.101 2000/12/12 23:33:33 tgl Exp $
11+
* $Header: /cvsroot/pgsql/src/backend/nodes/readfuncs.c,v 1.102 2000/12/14 22:30:42 tgl Exp $
1212
*
1313
* NOTES
1414
* Most of the read functions for plan nodes are tested. (In fact, they
@@ -1848,6 +1848,11 @@ _readRestrictInfo(void)
18481848

18491849
/* eval_cost is not part of saved representation; compute on first use */
18501850
local_node->eval_cost=-1;
1851+
/* ditto for cached pathkeys and dispersion */
1852+
local_node->left_pathkey=NIL;
1853+
local_node->right_pathkey=NIL;
1854+
local_node->left_dispersion=-1;
1855+
local_node->right_dispersion=-1;
18511856

18521857
returnlocal_node;
18531858
}

‎src/backend/optimizer/README

Lines changed: 26 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -356,9 +356,13 @@ relation the pathkey is for, *no matter how we formed the join*. It works
356356
as long as the clause has been applied at some point while forming the
357357
join relation. (In the current implementation, we always apply qual
358358
clauses as soon as possible, ie, as far down in the plan tree as possible.
359-
So we can always make this deduction. If we postponed filtering by qual
360-
clauses then we'd not be able to assume pathkey equivalence until after
361-
the equality check(s) had been applied.)
359+
So we can treat the pathkeys as equivalent everywhere. The exception is
360+
when the relations A and B are joined inside the nullable side of an
361+
OUTER JOIN and the equijoin clause comes from above the OUTER JOIN. In this
362+
case we cannot apply the qual as soon as A and B are joined, so we do not
363+
consider the pathkeys to be equivalent. This could be improved if we wanted
364+
to go to the trouble of making pathkey equivalence be context-dependent,
365+
but that seems much more complex than it's worth.)
362366

363367
In short, then: when producing the pathkeys for a merge or nestloop join,
364368
we can keep all of the keys of the outer path, since the ordering of the
@@ -415,18 +419,14 @@ whenever we make a pathkey sublist that mentions any var appearing in an
415419
equivalence set, we instantly add all the other vars equivalenced to it,
416420
whether they appear yet in the pathkey's relation or not. And we also
417421
mandate that the pathkey sublist appear in the same order as the
418-
equivalence set it comes from. (In practice, we simply return a pointer
419-
to the relevant equivalence set without building any new sublist at all.
420-
Each equivalence set becomes a "canonical pathkey" for all its members.)
421-
This makes comparing pathkeys very simple and fast, and saves a lot of
422-
work and memory space for pathkey construction as well.
423-
424-
Note that pathkey sublists having just one item still exist, and are
425-
not expected to be equal() to any equivalence set. This occurs when
426-
we describe a sort order that involves a var that's not mentioned in
427-
any equijoin clause of the WHERE. We could add singleton sets containing
428-
such vars to the query's list of equivalence sets, but there's little
429-
point in doing so.
422+
equivalence set it comes from.
423+
424+
In fact, we can go even further, and say that the canonical representation
425+
of a pathkey sublist is a pointer directly to the relevant equivalence set,
426+
which is kept in a list of pathkey equivalence sets for the query. Then
427+
pathkey sublist comparison reduces to pointer-equality checking! To do this
428+
we also have to add single-element pathkey sublists to the query's list of
429+
equivalence sets, but that's a small price to pay.
430430

431431
By the way, it's OK and even useful for us to build equivalence sets
432432
that mention multiple vars from the same relation. For example, if
@@ -469,4 +469,15 @@ we're given WHERE int2var = int4var AND int4var = int8var, we'll fail
469469
while trying to create a representation of the implied clause
470470
int2var = int8var.
471471

472+
An additional refinement we can make is to insist that canonical pathkey
473+
lists (sort orderings) do not mention the same pathkey set more than once.
474+
For example, a pathkey list ((A) (B) (A)) is redundant --- the second
475+
occurrence of (A) does not change the ordering, since the data must already
476+
be sorted by A. Although a user probably wouldn't write ORDER BY A,B,A
477+
directly, such redundancies are more probable once equijoin equivalences
478+
have been considered. Also, the system is likely to generate redundant
479+
pathkey lists when computing the sort ordering needed for a mergejoin. By
480+
eliminating the redundancy, we save time and improve planning, since the
481+
planner will more easily recognize equivalent orderings as being equivalent.
482+
472483
-- bjm & tgl

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

Lines changed: 2 additions & 4 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.67 2000/11/12 00:36:58 tgl Exp $
11+
* $Header: /cvsroot/pgsql/src/backend/optimizer/path/allpaths.c,v 1.68 2000/12/14 22:30:43 tgl Exp $
1212
*
1313
*-------------------------------------------------------------------------
1414
*/
@@ -162,9 +162,7 @@ set_plain_rel_pathlist(Query *root, RelOptInfo *rel, RangeTblEntry *rte)
162162
create_tidscan_paths(root,rel);
163163

164164
/* Consider index paths for both simple and OR index clauses */
165-
create_index_paths(root,rel,indices,
166-
rel->baserestrictinfo,
167-
rel->joininfo);
165+
create_index_paths(root,rel,indices);
168166

169167
/*
170168
* Note: create_or_index_paths depends on create_index_paths to

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

Lines changed: 47 additions & 129 deletions
Original file line numberDiff line numberDiff line change
@@ -9,7 +9,7 @@
99
*
1010
*
1111
* IDENTIFICATION
12-
* $Header: /cvsroot/pgsql/src/backend/optimizer/path/indxpath.c,v 1.99 2000/11/25 20:33:51 tgl Exp $
12+
* $Header: /cvsroot/pgsql/src/backend/optimizer/path/indxpath.c,v 1.100 2000/12/14 22:30:43 tgl Exp $
1313
*
1414
*-------------------------------------------------------------------------
1515
*/
@@ -87,11 +87,6 @@ static void indexable_joinclauses(RelOptInfo *rel, IndexOptInfo *index,
8787
List**clausegroups,List**outerrelids);
8888
staticList*index_innerjoin(Query*root,RelOptInfo*rel,IndexOptInfo*index,
8989
List*clausegroup_list,List*outerrelids_list);
90-
staticbooluseful_for_mergejoin(RelOptInfo*rel,IndexOptInfo*index,
91-
List*joininfo_list);
92-
staticbooluseful_for_ordering(Query*root,RelOptInfo*rel,
93-
IndexOptInfo*index,
94-
ScanDirectionscandir);
9590
staticboolmatch_index_to_operand(intindexkey,Var*operand,
9691
RelOptInfo*rel,IndexOptInfo*index);
9792
staticboolfunction_index_operand(Expr*funcOpnd,RelOptInfo*rel,
@@ -125,31 +120,31 @@ static Const *string_to_const(const char *str, Oid datatype);
125120
* attributes are available and fixed during any one scan of the indexpath.
126121
*
127122
* An IndexPath is generated and submitted to add_path() for each index
128-
* this routine deems potentially interesting for the current query
129-
* (at most one IndexPath per index on the given relation). An innerjoin
130-
* path is also generated for each interesting combination of outer join
131-
* relations. The innerjoin paths are *not* passed to add_path(), but are
132-
* appended to the "innerjoin" list of the relation for later consideration
133-
* in nested-loop joins.
123+
* this routine deems potentially interesting for the current query.
124+
* An innerjoin path is also generated for each interesting combination of
125+
* outer join relations. The innerjoin paths are *not* passed to add_path(),
126+
* but are appended to the "innerjoin" list of the relation for later
127+
* consideration in nested-loop joins.
134128
*
135129
* 'rel' is the relation for which we want to generate index paths
136130
* 'indices' is a list of available indexes for 'rel'
137-
* 'restrictinfo_list' is a list of restrictinfo nodes for 'rel'
138-
* 'joininfo_list' is a list of joininfo nodes for 'rel'
139131
*/
140132
void
141133
create_index_paths(Query*root,
142134
RelOptInfo*rel,
143-
List*indices,
144-
List*restrictinfo_list,
145-
List*joininfo_list)
135+
List*indices)
146136
{
137+
List*restrictinfo_list=rel->baserestrictinfo;
138+
List*joininfo_list=rel->joininfo;
147139
List*ilist;
148140

149141
foreach(ilist,indices)
150142
{
151143
IndexOptInfo*index= (IndexOptInfo*)lfirst(ilist);
152144
List*restrictclauses;
145+
List*index_pathkeys;
146+
List*useful_pathkeys;
147+
boolindex_is_ordered;
153148
List*joinclausegroups;
154149
List*joinouterrelids;
155150

@@ -179,53 +174,58 @@ create_index_paths(Query *root,
179174
match_index_orclauses(rel,index,restrictinfo_list);
180175

181176
/*
182-
* 2. If the keys of this index match any of the available
183-
* non-'or' restriction clauses, then create a path using those
184-
* clauses as indexquals.
177+
* 2. Match the index against non-'or' restriction clauses.
185178
*/
186179
restrictclauses=group_clauses_by_indexkey(rel,
187180
index,
188181
index->indexkeys,
189182
index->classlist,
190183
restrictinfo_list);
191184

192-
if (restrictclauses!=NIL)
193-
add_path(rel, (Path*)create_index_path(root,rel,index,
194-
restrictclauses,
195-
NoMovementScanDirection));
196-
197185
/*
198-
* 3. If this index can be used for a mergejoin, then create an
199-
* index path for it even if there were no restriction clauses.
200-
* (If there were, there is no need to make another index path.)
201-
* This will allow the index to be considered as a base for a
202-
* mergejoin in later processing. Similarly, if the index matches
203-
* the ordering that is needed for the overall query result, make
204-
* an index path for it even if there is no other reason to do so.
186+
* 3. Compute pathkeys describing index's ordering, if any,
187+
* then see how many of them are actually useful for this query.
205188
*/
206-
if (restrictclauses==NIL)
207-
{
208-
if (useful_for_mergejoin(rel,index,joininfo_list)||
209-
useful_for_ordering(root,rel,index,ForwardScanDirection))
210-
add_path(rel, (Path*)
211-
create_index_path(root,rel,index,
212-
restrictclauses,
213-
ForwardScanDirection));
214-
}
189+
index_pathkeys=build_index_pathkeys(root,rel,index,
190+
ForwardScanDirection);
191+
index_is_ordered= (index_pathkeys!=NIL);
192+
useful_pathkeys=truncate_useless_pathkeys(root,rel,
193+
index_pathkeys);
215194

216195
/*
217-
*Currently, backwards scan is never considered except for the
218-
*case of matching a query result ordering. Possibly should
219-
*consider it in other places?
196+
*4. Generate an indexscan path if there are relevant restriction
197+
*clauses OR the index ordering is potentially useful for later
198+
*merging or final output ordering.
220199
*/
221-
if (useful_for_ordering(root,rel,index,BackwardScanDirection))
200+
if (restrictclauses!=NIL||useful_pathkeys!=NIL)
222201
add_path(rel, (Path*)
223202
create_index_path(root,rel,index,
224203
restrictclauses,
225-
BackwardScanDirection));
204+
useful_pathkeys,
205+
index_is_ordered ?
206+
ForwardScanDirection :
207+
NoMovementScanDirection));
208+
209+
/*
210+
* 5. If the index is ordered, a backwards scan might be interesting.
211+
* Currently this is only possible for a DESC query result ordering.
212+
*/
213+
if (index_is_ordered)
214+
{
215+
index_pathkeys=build_index_pathkeys(root,rel,index,
216+
BackwardScanDirection);
217+
useful_pathkeys=truncate_useless_pathkeys(root,rel,
218+
index_pathkeys);
219+
if (useful_pathkeys!=NIL)
220+
add_path(rel, (Path*)
221+
create_index_path(root,rel,index,
222+
restrictclauses,
223+
useful_pathkeys,
224+
BackwardScanDirection));
225+
}
226226

227227
/*
228-
*4. Create an innerjoin index path for each combination of other
228+
*6. Create an innerjoin index path for each combination of other
229229
* rels used in available join clauses. These paths will be
230230
* considered as the inner side of nestloop joins against those
231231
* sets of other rels.indexable_joinclauses() finds sets of
@@ -904,88 +904,6 @@ indexable_operator(Expr *clause, Oid opclass, Oid relam,
904904
returnInvalidOid;
905905
}
906906

907-
/*
908-
* useful_for_mergejoin
909-
* Determine whether the given index can support a mergejoin based
910-
* on any available join clause.
911-
*
912-
* We look to see whether the first indexkey of the index matches the
913-
* left or right sides of any of the mergejoinable clauses and provides
914-
* the ordering needed for that side. If so, the index is useful.
915-
* Matching a second or later indexkey is not useful unless there is
916-
* also a mergeclause for the first indexkey, so we need not consider
917-
* secondary indexkeys at this stage.
918-
*
919-
* 'rel' is the relation for which 'index' is defined
920-
* 'joininfo_list' is the list of JoinInfo nodes for 'rel'
921-
*/
922-
staticbool
923-
useful_for_mergejoin(RelOptInfo*rel,
924-
IndexOptInfo*index,
925-
List*joininfo_list)
926-
{
927-
int*indexkeys=index->indexkeys;
928-
Oid*ordering=index->ordering;
929-
List*i;
930-
931-
if (!indexkeys||indexkeys[0]==0||
932-
!ordering||ordering[0]==InvalidOid)
933-
return false;/* unordered index is not useful */
934-
935-
foreach(i,joininfo_list)
936-
{
937-
JoinInfo*joininfo= (JoinInfo*)lfirst(i);
938-
List*j;
939-
940-
foreach(j,joininfo->jinfo_restrictinfo)
941-
{
942-
RestrictInfo*restrictinfo= (RestrictInfo*)lfirst(j);
943-
944-
if (restrictinfo->mergejoinoperator)
945-
{
946-
if (restrictinfo->left_sortop==ordering[0]&&
947-
match_index_to_operand(indexkeys[0],
948-
get_leftop(restrictinfo->clause),
949-
rel,index))
950-
return true;
951-
if (restrictinfo->right_sortop==ordering[0]&&
952-
match_index_to_operand(indexkeys[0],
953-
get_rightop(restrictinfo->clause),
954-
rel,index))
955-
return true;
956-
}
957-
}
958-
}
959-
return false;
960-
}
961-
962-
/*
963-
* useful_for_ordering
964-
* Determine whether the given index can produce an ordering matching
965-
* the order that is wanted for the query result.
966-
*
967-
* 'rel' is the relation for which 'index' is defined
968-
* 'scandir' is the contemplated scan direction
969-
*/
970-
staticbool
971-
useful_for_ordering(Query*root,
972-
RelOptInfo*rel,
973-
IndexOptInfo*index,
974-
ScanDirectionscandir)
975-
{
976-
List*index_pathkeys;
977-
978-
if (root->query_pathkeys==NIL)
979-
return false;/* no special ordering requested */
980-
981-
index_pathkeys=build_index_pathkeys(root,rel,index,scandir);
982-
983-
if (index_pathkeys==NIL)
984-
return false;/* unordered index */
985-
986-
returnpathkeys_contained_in(root->query_pathkeys,index_pathkeys);
987-
}
988-
989907
/****************************************************************************
990908
*---- ROUTINES TO DO PARTIAL INDEX PREDICATE TESTS----
991909
****************************************************************************/

0 commit comments

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