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

Commitf9eb7c1

Browse files
committed
Avoid O(N^2) cost in ExecFindRowMark().
If there are many ExecRowMark structs, we spent O(N^2) time inExecFindRowMark during executor startup. Once upon a time this wasnot of great concern, but the addition of native partitioning hassqueezed out enough other costs that this can become the dominantoverhead in some use-cases for tables with many partitions.To fix, simply replace that List data structure with an array.This adds a little bit of cost to execCurrentOf(), but not much,and anyway that code path is neither of large importance nor veryefficient now. If we ever decide it is a bottleneck, constructing ahash table for lookup-by-tableoid would likely be the thing to do.Per complaint from Amit Langote, though this is different fromhis fix proposal.Discussion:https://postgr.es/m/468c85d9-540e-66a2-1dde-fec2b741e688@lab.ntt.co.jp
1 parenteee01d6 commitf9eb7c1

File tree

4 files changed

+82
-67
lines changed

4 files changed

+82
-67
lines changed

‎src/backend/executor/execCurrent.c‎

Lines changed: 6 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -91,21 +91,22 @@ execCurrentOf(CurrentOfExpr *cexpr,
9191
* the other code can't, while the non-FOR-UPDATE case allows use of WHERE
9292
* CURRENT OF with an insensitive cursor.
9393
*/
94-
if (queryDesc->estate->es_rowMarks)
94+
if (queryDesc->estate->es_rowmarks)
9595
{
9696
ExecRowMark*erm;
97-
ListCell*lc;
97+
Indexi;
9898

9999
/*
100100
* Here, the query must have exactly one FOR UPDATE/SHARE reference to
101101
* the target table, and we dig the ctid info out of that.
102102
*/
103103
erm=NULL;
104-
foreach(lc,queryDesc->estate->es_rowMarks)
104+
for (i=0;i<queryDesc->estate->es_range_table_size;i++)
105105
{
106-
ExecRowMark*thiserm=(ExecRowMark*)lfirst(lc);
106+
ExecRowMark*thiserm=queryDesc->estate->es_rowmarks[i];
107107

108-
if (!RowMarkRequiresRowShareLock(thiserm->markType))
108+
if (thiserm==NULL||
109+
!RowMarkRequiresRowShareLock(thiserm->markType))
109110
continue;/* ignore non-FOR UPDATE/SHARE items */
110111

111112
if (thiserm->relid==table_oid)

‎src/backend/executor/execMain.c‎

Lines changed: 61 additions & 55 deletions
Original file line numberDiff line numberDiff line change
@@ -909,61 +909,68 @@ InitPlan(QueryDesc *queryDesc, int eflags)
909909
}
910910

911911
/*
912-
* Next, build the ExecRowMarklist from the PlanRowMark(s), if any.
912+
* Next, build the ExecRowMarkarray from the PlanRowMark(s), if any.
913913
*/
914-
estate->es_rowMarks=NIL;
915-
foreach(l,plannedstmt->rowMarks)
914+
if (plannedstmt->rowMarks)
916915
{
917-
PlanRowMark*rc= (PlanRowMark*)lfirst(l);
918-
Oidrelid;
919-
Relationrelation;
920-
ExecRowMark*erm;
916+
estate->es_rowmarks= (ExecRowMark**)
917+
palloc0(estate->es_range_table_size*sizeof(ExecRowMark*));
918+
foreach(l,plannedstmt->rowMarks)
919+
{
920+
PlanRowMark*rc= (PlanRowMark*)lfirst(l);
921+
Oidrelid;
922+
Relationrelation;
923+
ExecRowMark*erm;
921924

922-
/* ignore "parent" rowmarks; they are irrelevant at runtime */
923-
if (rc->isParent)
924-
continue;
925+
/* ignore "parent" rowmarks; they are irrelevant at runtime */
926+
if (rc->isParent)
927+
continue;
925928

926-
/* get relation's OID (will produce InvalidOid if subquery) */
927-
relid=exec_rt_fetch(rc->rti,estate)->relid;
929+
/* get relation's OID (will produce InvalidOid if subquery) */
930+
relid=exec_rt_fetch(rc->rti,estate)->relid;
928931

929-
/* open relation, if we need to access it for this mark type */
930-
switch (rc->markType)
931-
{
932-
caseROW_MARK_EXCLUSIVE:
933-
caseROW_MARK_NOKEYEXCLUSIVE:
934-
caseROW_MARK_SHARE:
935-
caseROW_MARK_KEYSHARE:
936-
caseROW_MARK_REFERENCE:
937-
relation=ExecGetRangeTableRelation(estate,rc->rti);
938-
break;
939-
caseROW_MARK_COPY:
940-
/* no physical table access is required */
941-
relation=NULL;
942-
break;
943-
default:
944-
elog(ERROR,"unrecognized markType: %d",rc->markType);
945-
relation=NULL;/* keep compiler quiet */
946-
break;
947-
}
932+
/* open relation, if we need to access it for this mark type */
933+
switch (rc->markType)
934+
{
935+
caseROW_MARK_EXCLUSIVE:
936+
caseROW_MARK_NOKEYEXCLUSIVE:
937+
caseROW_MARK_SHARE:
938+
caseROW_MARK_KEYSHARE:
939+
caseROW_MARK_REFERENCE:
940+
relation=ExecGetRangeTableRelation(estate,rc->rti);
941+
break;
942+
caseROW_MARK_COPY:
943+
/* no physical table access is required */
944+
relation=NULL;
945+
break;
946+
default:
947+
elog(ERROR,"unrecognized markType: %d",rc->markType);
948+
relation=NULL;/* keep compiler quiet */
949+
break;
950+
}
948951

949-
/* Check that relation is a legal target for marking */
950-
if (relation)
951-
CheckValidRowMarkRel(relation,rc->markType);
952-
953-
erm= (ExecRowMark*)palloc(sizeof(ExecRowMark));
954-
erm->relation=relation;
955-
erm->relid=relid;
956-
erm->rti=rc->rti;
957-
erm->prti=rc->prti;
958-
erm->rowmarkId=rc->rowmarkId;
959-
erm->markType=rc->markType;
960-
erm->strength=rc->strength;
961-
erm->waitPolicy=rc->waitPolicy;
962-
erm->ermActive= false;
963-
ItemPointerSetInvalid(&(erm->curCtid));
964-
erm->ermExtra=NULL;
965-
966-
estate->es_rowMarks=lappend(estate->es_rowMarks,erm);
952+
/* Check that relation is a legal target for marking */
953+
if (relation)
954+
CheckValidRowMarkRel(relation,rc->markType);
955+
956+
erm= (ExecRowMark*)palloc(sizeof(ExecRowMark));
957+
erm->relation=relation;
958+
erm->relid=relid;
959+
erm->rti=rc->rti;
960+
erm->prti=rc->prti;
961+
erm->rowmarkId=rc->rowmarkId;
962+
erm->markType=rc->markType;
963+
erm->strength=rc->strength;
964+
erm->waitPolicy=rc->waitPolicy;
965+
erm->ermActive= false;
966+
ItemPointerSetInvalid(&(erm->curCtid));
967+
erm->ermExtra=NULL;
968+
969+
Assert(erm->rti>0&&erm->rti <=estate->es_range_table_size&&
970+
estate->es_rowmarks[erm->rti-1]==NULL);
971+
972+
estate->es_rowmarks[erm->rti-1]=erm;
973+
}
967974
}
968975

969976
/*
@@ -2394,13 +2401,12 @@ ExecUpdateLockMode(EState *estate, ResultRelInfo *relinfo)
23942401
ExecRowMark*
23952402
ExecFindRowMark(EState*estate,Indexrti,boolmissing_ok)
23962403
{
2397-
ListCell*lc;
2398-
2399-
foreach(lc,estate->es_rowMarks)
2404+
if (rti>0&&rti <=estate->es_range_table_size&&
2405+
estate->es_rowmarks!=NULL)
24002406
{
2401-
ExecRowMark*erm=(ExecRowMark*)lfirst(lc);
2407+
ExecRowMark*erm=estate->es_rowmarks[rti-1];
24022408

2403-
if (erm->rti==rti)
2409+
if (erm)
24042410
returnerm;
24052411
}
24062412
if (!missing_ok)
@@ -3131,6 +3137,7 @@ EvalPlanQualStart(EPQState *epqstate, EState *parentestate, Plan *planTree)
31313137
estate->es_range_table_array=parentestate->es_range_table_array;
31323138
estate->es_range_table_size=parentestate->es_range_table_size;
31333139
estate->es_relations=parentestate->es_relations;
3140+
estate->es_rowmarks=parentestate->es_rowmarks;
31343141
estate->es_plannedstmt=parentestate->es_plannedstmt;
31353142
estate->es_junkFilter=parentestate->es_junkFilter;
31363143
estate->es_output_cid=parentestate->es_output_cid;
@@ -3148,7 +3155,6 @@ EvalPlanQualStart(EPQState *epqstate, EState *parentestate, Plan *planTree)
31483155
}
31493156
/* es_result_relation_info must NOT be copied */
31503157
/* es_trig_target_relations must NOT be copied */
3151-
estate->es_rowMarks=parentestate->es_rowMarks;
31523158
estate->es_top_eflags=parentestate->es_top_eflags;
31533159
estate->es_instrument=parentestate->es_instrument;
31543160
/* es_auxmodifytables must NOT be copied */

‎src/backend/executor/execUtils.c‎

Lines changed: 7 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -113,6 +113,7 @@ CreateExecutorState(void)
113113
estate->es_range_table_array=NULL;
114114
estate->es_range_table_size=0;
115115
estate->es_relations=NULL;
116+
estate->es_rowmarks=NULL;
116117
estate->es_plannedstmt=NULL;
117118

118119
estate->es_junkFilter=NULL;
@@ -142,8 +143,6 @@ CreateExecutorState(void)
142143

143144
estate->es_tupleTable=NIL;
144145

145-
estate->es_rowMarks=NIL;
146-
147146
estate->es_processed=0;
148147
estate->es_lastoid=InvalidOid;
149148

@@ -709,6 +708,12 @@ ExecInitRangeTable(EState *estate, List *rangeTable)
709708
*/
710709
estate->es_relations= (Relation*)
711710
palloc0(estate->es_range_table_size*sizeof(Relation));
711+
712+
/*
713+
* es_rowmarks is also parallel to the es_range_table_array, but it's
714+
* allocated only if needed.
715+
*/
716+
estate->es_rowmarks=NULL;
712717
}
713718

714719
/*

‎src/include/nodes/execnodes.h‎

Lines changed: 8 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -34,6 +34,7 @@
3434

3535
structPlanState;/* forward references in this file */
3636
structParallelHashJoinState;
37+
structExecRowMark;
3738
structExprState;
3839
structExprContext;
3940
structRangeTblEntry;/* avoid including parsenodes.h here */
@@ -491,6 +492,8 @@ typedef struct EState
491492
Indexes_range_table_size;/* size of the range table arrays */
492493
Relation*es_relations;/* Array of per-range-table-entry Relation
493494
* pointers, or NULL if not yet opened */
495+
structExecRowMark**es_rowmarks;/* Array of per-range-table-entry
496+
* ExecRowMarks, or NULL if none */
494497
PlannedStmt*es_plannedstmt;/* link to top of plan tree */
495498
constchar*es_sourceText;/* Source text from QueryDesc */
496499

@@ -537,8 +540,6 @@ typedef struct EState
537540

538541
List*es_tupleTable;/* List of TupleTableSlots */
539542

540-
List*es_rowMarks;/* List of ExecRowMarks */
541-
542543
uint64es_processed;/* # of tuples processed */
543544
Oides_lastoid;/* last oid processed (by INSERT) */
544545

@@ -607,7 +608,9 @@ typedef struct EState
607608
* node that sources the relation (e.g., for a foreign table the FDW can use
608609
* ermExtra to hold information).
609610
*
610-
* EState->es_rowMarks is a list of these structs.
611+
* EState->es_rowmarks is an array of these structs, indexed by RT index,
612+
* with NULLs for irrelevant RT indexes. es_rowmarks itself is NULL if
613+
* there are no rowmarks.
611614
*/
612615
typedefstructExecRowMark
613616
{
@@ -629,7 +632,7 @@ typedef struct ExecRowMark
629632
* additional runtime representation of FOR [KEY] UPDATE/SHARE clauses
630633
*
631634
* Each LockRows and ModifyTable node keeps a list of the rowmarks it needs to
632-
* deal with. In addition to a pointer to the related entry ines_rowMarks,
635+
* deal with. In addition to a pointer to the related entry ines_rowmarks,
633636
* this struct carries the column number(s) of the resjunk columns associated
634637
* with the rowmark (see comments for PlanRowMark for more detail). In the
635638
* case of ModifyTable, there has to be a separate ExecAuxRowMark list for
@@ -638,7 +641,7 @@ typedef struct ExecRowMark
638641
*/
639642
typedefstructExecAuxRowMark
640643
{
641-
ExecRowMark*rowmark;/* related entry ines_rowMarks */
644+
ExecRowMark*rowmark;/* related entry ines_rowmarks */
642645
AttrNumberctidAttNo;/* resno of ctid junk attribute, if any */
643646
AttrNumbertoidAttNo;/* resno of tableoid junk attribute, if any */
644647
AttrNumberwholeAttNo;/* resno of whole-row junk attribute, if any */

0 commit comments

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