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
Appearance settings

Commit f9eb7c1

Browse filesBrowse files
tglsfdctglsfdc
committed
Avoid O(N^2) cost in ExecFindRowMark().
If there are many ExecRowMark structs, we spent O(N^2) time in ExecFindRowMark during executor startup. Once upon a time this was not of great concern, but the addition of native partitioning has squeezed out enough other costs that this can become the dominant overhead 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 very efficient now. If we ever decide it is a bottleneck, constructing a hash table for lookup-by-tableoid would likely be the thing to do. Per complaint from Amit Langote, though this is different from his fix proposal. Discussion: https://postgr.es/m/468c85d9-540e-66a2-1dde-fec2b741e688@lab.ntt.co.jp
1 parent eee01d6 commit f9eb7c1
Copy full SHA for f9eb7c1

File tree

Expand file treeCollapse file tree

4 files changed

+82
-67
lines changed
Filter options
Expand file treeCollapse file tree

4 files changed

+82
-67
lines changed

‎src/backend/executor/execCurrent.c

Copy file name to clipboardExpand all lines: src/backend/executor/execCurrent.c
+6-5Lines 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+
Index i;
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

Copy file name to clipboardExpand all lines: src/backend/executor/execMain.c
+61-55Lines 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 ExecRowMark list from the PlanRowMark(s), if any.
912+
* Next, build the ExecRowMark array 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-
Oid relid;
919-
Relation relation;
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+
Oid relid;
922+
Relation relation;
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-
case ROW_MARK_EXCLUSIVE:
933-
case ROW_MARK_NOKEYEXCLUSIVE:
934-
case ROW_MARK_SHARE:
935-
case ROW_MARK_KEYSHARE:
936-
case ROW_MARK_REFERENCE:
937-
relation = ExecGetRangeTableRelation(estate, rc->rti);
938-
break;
939-
case ROW_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+
case ROW_MARK_EXCLUSIVE:
936+
case ROW_MARK_NOKEYEXCLUSIVE:
937+
case ROW_MARK_SHARE:
938+
case ROW_MARK_KEYSHARE:
939+
case ROW_MARK_REFERENCE:
940+
relation = ExecGetRangeTableRelation(estate, rc->rti);
941+
break;
942+
case ROW_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, Index rti, bool missing_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
return erm;
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

Copy file name to clipboardExpand all lines: src/backend/executor/execUtils.c
+7-2Lines 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

Copy file name to clipboardExpand all lines: src/include/nodes/execnodes.h
+8-5Lines changed: 8 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -34,6 +34,7 @@
3434

3535
struct PlanState; /* forward references in this file */
3636
struct ParallelHashJoinState;
37+
struct ExecRowMark;
3738
struct ExprState;
3839
struct ExprContext;
3940
struct RangeTblEntry; /* avoid including parsenodes.h here */
@@ -491,6 +492,8 @@ typedef struct EState
491492
Index es_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+
struct ExecRowMark **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
const char *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
uint64 es_processed; /* # of tuples processed */
543544
Oid es_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
typedef struct ExecRowMark
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 in es_rowMarks,
635+
* deal with. In addition to a pointer to the related entry in es_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
typedef struct ExecAuxRowMark
640643
{
641-
ExecRowMark *rowmark; /* related entry in es_rowMarks */
644+
ExecRowMark *rowmark; /* related entry in es_rowmarks */
642645
AttrNumber ctidAttNo; /* resno of ctid junk attribute, if any */
643646
AttrNumber toidAttNo; /* resno of tableoid junk attribute, if any */
644647
AttrNumber wholeAttNo; /* resno of whole-row junk attribute, if any */

0 commit comments

Comments
0 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.