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 d73f4c7

Browse filesBrowse files
tglsfdctglsfdc
committed
In the executor, use an array of pointers to access the rangetable.
Instead of doing a lot of list_nth() accesses to es_range_table, create a flattened pointer array during executor startup and index into that to get at individual RangeTblEntrys. This eliminates one source of O(N^2) behavior with lots of partitions. (I'm not exactly convinced that it's the most important source, but it's an easy one to fix.) Amit Langote and David Rowley Discussion: https://postgr.es/m/468c85d9-540e-66a2-1dde-fec2b741e688@lab.ntt.co.jp
1 parent 9ddef36 commit d73f4c7
Copy full SHA for d73f4c7

File tree

Expand file treeCollapse file tree

11 files changed

+87
-52
lines changed
Filter options
Expand file treeCollapse file tree

11 files changed

+87
-52
lines changed

‎contrib/postgres_fdw/postgres_fdw.c

Copy file name to clipboardExpand all lines: contrib/postgres_fdw/postgres_fdw.c
+6-6Lines changed: 6 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -1345,7 +1345,7 @@ postgresBeginForeignScan(ForeignScanState *node, int eflags)
13451345
rtindex = fsplan->scan.scanrelid;
13461346
else
13471347
rtindex = bms_next_member(fsplan->fs_relids, -1);
1348-
rte = rt_fetch(rtindex, estate->es_range_table);
1348+
rte = exec_rt_fetch(rtindex, estate);
13491349
userid = rte->checkAsUser ? rte->checkAsUser : GetUserId();
13501350

13511351
/* Get info about foreign table. */
@@ -1731,8 +1731,8 @@ postgresBeginForeignModify(ModifyTableState *mtstate,
17311731
FdwModifyPrivateRetrievedAttrs);
17321732

17331733
/* Find RTE. */
1734-
rte = rt_fetch(resultRelInfo->ri_RangeTableIndex,
1735-
mtstate->ps.state->es_range_table);
1734+
rte = exec_rt_fetch(resultRelInfo->ri_RangeTableIndex,
1735+
mtstate->ps.state);
17361736

17371737
/* Construct an execution state. */
17381738
fmstate = create_foreign_modify(mtstate->ps.state,
@@ -2036,7 +2036,7 @@ postgresBeginForeignInsert(ModifyTableState *mtstate,
20362036
* correspond to this partition if it is one of the UPDATE subplan target
20372037
* rels; in that case, we can just use the existing RTE as-is.
20382038
*/
2039-
rte = list_nth(estate->es_range_table, resultRelation - 1);
2039+
rte = exec_rt_fetch(resultRelation, estate);
20402040
if (rte->relid != RelationGetRelid(rel))
20412041
{
20422042
rte = copyObject(rte);
@@ -2396,7 +2396,7 @@ postgresBeginDirectModify(ForeignScanState *node, int eflags)
23962396
* ExecCheckRTEPerms() does.
23972397
*/
23982398
rtindex = estate->es_result_relation_info->ri_RangeTableIndex;
2399-
rte = rt_fetch(rtindex, estate->es_range_table);
2399+
rte = exec_rt_fetch(rtindex, estate);
24002400
userid = rte->checkAsUser ? rte->checkAsUser : GetUserId();
24012401

24022402
/* Get info about foreign table. */
@@ -5752,7 +5752,7 @@ conversion_error_callback(void *arg)
57525752
RangeTblEntry *rte;
57535753
Var *var = (Var *) tle->expr;
57545754

5755-
rte = rt_fetch(var->varno, estate->es_range_table);
5755+
rte = exec_rt_fetch(var->varno, estate);
57565756

57575757
if (var->varattno == 0)
57585758
is_wholerow = true;

‎src/backend/commands/copy.c

Copy file name to clipboardExpand all lines: src/backend/commands/copy.c
+2-3Lines changed: 2 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -2484,9 +2484,8 @@ CopyFrom(CopyState cstate)
24842484
estate->es_result_relations = resultRelInfo;
24852485
estate->es_num_result_relations = 1;
24862486
estate->es_result_relation_info = resultRelInfo;
2487-
estate->es_range_table = cstate->range_table;
2488-
estate->es_relations = (Relation *) palloc0(list_length(cstate->range_table) *
2489-
sizeof(Relation));
2487+
2488+
ExecInitRangeTable(estate, cstate->range_table);
24902489

24912490
/* Set up a tuple slot too */
24922491
myslot = ExecInitExtraTupleSlot(estate, tupDesc);

‎src/backend/commands/trigger.c

Copy file name to clipboardExpand all lines: src/backend/commands/trigger.c
+1-1Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -75,7 +75,7 @@ static int MyTriggerDepth = 0;
7575
* to be changed, however.
7676
*/
7777
#define GetUpdatedColumns(relinfo, estate) \
78-
(rt_fetch((relinfo)->ri_RangeTableIndex, (estate)->es_range_table)->updatedCols)
78+
(exec_rt_fetch((relinfo)->ri_RangeTableIndex, estate)->updatedCols)
7979

8080
/* Local function prototypes */
8181
static void ConvertTriggerToFK(CreateTrigStmt *stmt, Oid funcoid);

‎src/backend/executor/execExprInterp.c

Copy file name to clipboardExpand all lines: src/backend/executor/execExprInterp.c
+3-3Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -3934,10 +3934,10 @@ ExecEvalWholeRowVar(ExprState *state, ExprEvalStep *op, ExprContext *econtext)
39343934
* perhaps other places.)
39353935
*/
39363936
if (econtext->ecxt_estate &&
3937-
variable->varno <= list_length(econtext->ecxt_estate->es_range_table))
3937+
variable->varno <= econtext->ecxt_estate->es_range_table_size)
39383938
{
3939-
RangeTblEntry *rte = rt_fetch(variable->varno,
3940-
econtext->ecxt_estate->es_range_table);
3939+
RangeTblEntry *rte = exec_rt_fetch(variable->varno,
3940+
econtext->ecxt_estate);
39413941

39423942
if (rte->eref)
39433943
ExecTypeSetColNames(output_tupdesc, rte->eref->colnames);

‎src/backend/executor/execMain.c

Copy file name to clipboardExpand all lines: src/backend/executor/execMain.c
+14-20Lines changed: 14 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -109,9 +109,9 @@ static void EvalPlanQualStart(EPQState *epqstate, EState *parentestate,
109109
* to be changed, however.
110110
*/
111111
#define GetInsertedColumns(relinfo, estate) \
112-
(rt_fetch((relinfo)->ri_RangeTableIndex, (estate)->es_range_table)->insertedCols)
112+
(exec_rt_fetch((relinfo)->ri_RangeTableIndex, estate)->insertedCols)
113113
#define GetUpdatedColumns(relinfo, estate) \
114-
(rt_fetch((relinfo)->ri_RangeTableIndex, (estate)->es_range_table)->updatedCols)
114+
(exec_rt_fetch((relinfo)->ri_RangeTableIndex, estate)->updatedCols)
115115

116116
/* end of local decls */
117117

@@ -823,15 +823,7 @@ InitPlan(QueryDesc *queryDesc, int eflags)
823823
/*
824824
* initialize the node's execution state
825825
*/
826-
estate->es_range_table = rangeTable;
827-
828-
/*
829-
* Allocate an array to store an open Relation corresponding to each
830-
* rangeTable item, and initialize entries to NULL. Relations are opened
831-
* and stored here as needed.
832-
*/
833-
estate->es_relations = (Relation *) palloc0(list_length(rangeTable) *
834-
sizeof(Relation));
826+
ExecInitRangeTable(estate, rangeTable);
835827

836828
estate->es_plannedstmt = plannedstmt;
837829

@@ -918,9 +910,9 @@ InitPlan(QueryDesc *queryDesc, int eflags)
918910
resultRelIndex))
919911
{
920912
Relation resultRelDesc;
913+
Oid reloid = exec_rt_fetch(resultRelIndex, estate)->relid;
921914

922-
resultRelDesc = heap_open(getrelid(resultRelIndex, rangeTable),
923-
NoLock);
915+
resultRelDesc = heap_open(reloid, NoLock);
924916
Assert(CheckRelationLockedByMe(resultRelDesc, RowExclusiveLock, true));
925917
heap_close(resultRelDesc, NoLock);
926918
}
@@ -962,7 +954,7 @@ InitPlan(QueryDesc *queryDesc, int eflags)
962954
continue;
963955

964956
/* get relation's OID (will produce InvalidOid if subquery) */
965-
relid = getrelid(rc->rti, rangeTable);
957+
relid = exec_rt_fetch(rc->rti, estate)->relid;
966958

967959
switch (rc->markType)
968960
{
@@ -1619,8 +1611,8 @@ static void
16191611
ExecEndPlan(PlanState *planstate, EState *estate)
16201612
{
16211613
ResultRelInfo *resultRelInfo;
1622-
int num_relations;
1623-
int i;
1614+
Index num_relations;
1615+
Index i;
16241616
ListCell *l;
16251617

16261618
/*
@@ -1661,7 +1653,7 @@ ExecEndPlan(PlanState *planstate, EState *estate)
16611653
* close whatever rangetable Relations have been opened. We did not
16621654
* acquire locks in ExecGetRangeTableRelation, so don't release 'em here.
16631655
*/
1664-
num_relations = list_length(estate->es_range_table);
1656+
num_relations = estate->es_range_table_size;
16651657
for (i = 0; i < num_relations; i++)
16661658
{
16671659
if (estate->es_relations[i])
@@ -3087,7 +3079,7 @@ EvalPlanQualBegin(EPQState *epqstate, EState *parentestate)
30873079
/*
30883080
* We already have a suitable child EPQ tree, so just reset it.
30893081
*/
3090-
int rtsize = list_length(parentestate->es_range_table);
3082+
Index rtsize = parentestate->es_range_table_size;
30913083
PlanState *planstate = epqstate->planstate;
30923084

30933085
MemSet(estate->es_epqScanDone, 0, rtsize * sizeof(bool));
@@ -3136,11 +3128,11 @@ static void
31363128
EvalPlanQualStart(EPQState *epqstate, EState *parentestate, Plan *planTree)
31373129
{
31383130
EState *estate;
3139-
int rtsize;
3131+
Index rtsize;
31403132
MemoryContext oldcontext;
31413133
ListCell *l;
31423134

3143-
rtsize = list_length(parentestate->es_range_table);
3135+
rtsize = parentestate->es_range_table_size;
31443136

31453137
epqstate->estate = estate = CreateExecutorState();
31463138

@@ -3164,6 +3156,8 @@ EvalPlanQualStart(EPQState *epqstate, EState *parentestate, Plan *planTree)
31643156
estate->es_snapshot = parentestate->es_snapshot;
31653157
estate->es_crosscheck_snapshot = parentestate->es_crosscheck_snapshot;
31663158
estate->es_range_table = parentestate->es_range_table;
3159+
estate->es_range_table_array = parentestate->es_range_table_array;
3160+
estate->es_range_table_size = parentestate->es_range_table_size;
31673161
estate->es_relations = parentestate->es_relations;
31683162
estate->es_plannedstmt = parentestate->es_plannedstmt;
31693163
estate->es_junkFilter = parentestate->es_junkFilter;

‎src/backend/executor/execUtils.c

Copy file name to clipboardExpand all lines: src/backend/executor/execUtils.c
+45-4Lines changed: 45 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -26,6 +26,8 @@
2626
*
2727
* ExecOpenScanRelation Common code for scan node init routines.
2828
*
29+
* ExecInitRangeTable Set up executor's range-table-related data.
30+
*
2931
* ExecGetRangeTableRelation Fetch Relation for a rangetable entry.
3032
*
3133
* executor_errposition Report syntactic position of an error.
@@ -108,6 +110,8 @@ CreateExecutorState(void)
108110
estate->es_snapshot = InvalidSnapshot; /* caller must initialize this */
109111
estate->es_crosscheck_snapshot = InvalidSnapshot; /* no crosscheck */
110112
estate->es_range_table = NIL;
113+
estate->es_range_table_array = NULL;
114+
estate->es_range_table_size = 0;
111115
estate->es_relations = NULL;
112116
estate->es_plannedstmt = NULL;
113117

@@ -670,6 +674,43 @@ ExecOpenScanRelation(EState *estate, Index scanrelid, int eflags)
670674
return rel;
671675
}
672676

677+
/*
678+
* ExecInitRangeTable
679+
* Set up executor's range-table-related data
680+
*
681+
* We build an array from the range table list to allow faster lookup by RTI.
682+
* (The es_range_table field is now somewhat redundant, but we keep it to
683+
* avoid breaking external code unnecessarily.)
684+
* This is also a convenient place to set up the parallel es_relations array.
685+
*/
686+
void
687+
ExecInitRangeTable(EState *estate, List *rangeTable)
688+
{
689+
Index rti;
690+
ListCell *lc;
691+
692+
/* Remember the range table List as-is */
693+
estate->es_range_table = rangeTable;
694+
695+
/* Set up the equivalent array representation */
696+
estate->es_range_table_size = list_length(rangeTable);
697+
estate->es_range_table_array = (RangeTblEntry **)
698+
palloc(estate->es_range_table_size * sizeof(RangeTblEntry *));
699+
rti = 0;
700+
foreach(lc, rangeTable)
701+
{
702+
estate->es_range_table_array[rti++] = lfirst_node(RangeTblEntry, lc);
703+
}
704+
705+
/*
706+
* Allocate an array to store an open Relation corresponding to each
707+
* rangetable entry, and initialize entries to NULL. Relations are opened
708+
* and stored here as needed.
709+
*/
710+
estate->es_relations = (Relation *)
711+
palloc0(estate->es_range_table_size * sizeof(Relation));
712+
}
713+
673714
/*
674715
* ExecGetRangeTableRelation
675716
* Open the Relation for a range table entry, if not already done
@@ -681,13 +722,13 @@ ExecGetRangeTableRelation(EState *estate, Index rti)
681722
{
682723
Relation rel;
683724

684-
Assert(rti > 0 && rti <= list_length(estate->es_range_table));
725+
Assert(rti > 0 && rti <= estate->es_range_table_size);
685726

686727
rel = estate->es_relations[rti - 1];
687728
if (rel == NULL)
688729
{
689730
/* First time through, so open the relation */
690-
RangeTblEntry *rte = rt_fetch(rti, estate->es_range_table);
731+
RangeTblEntry *rte = exec_rt_fetch(rti, estate);
691732

692733
Assert(rte->rtekind == RTE_RELATION);
693734

@@ -876,7 +917,7 @@ ExecLockNonLeafAppendTables(List *partitioned_rels, EState *estate)
876917
ListCell *l;
877918
Index rti = lfirst_int(lc);
878919
bool is_result_rel = false;
879-
Oid relid = getrelid(rti, estate->es_range_table);
920+
Oid relid = exec_rt_fetch(rti, estate)->relid;
880921

881922
/* If this is a result relation, already locked in InitPlan */
882923
foreach(l, stmt->nonleafResultRelations)
@@ -911,7 +952,7 @@ ExecLockNonLeafAppendTables(List *partitioned_rels, EState *estate)
911952
else
912953
lockmode = AccessShareLock;
913954

914-
Assert(lockmode == rt_fetch(rti, estate->es_range_table)->rellockmode);
955+
Assert(lockmode == exec_rt_fetch(rti, estate)->rellockmode);
915956

916957
LockRelationOid(relid, lockmode);
917958
}

‎src/backend/executor/nodeLockRows.c

Copy file name to clipboardExpand all lines: src/backend/executor/nodeLockRows.c
+1-1Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -400,7 +400,7 @@ ExecInitLockRows(LockRows *node, EState *estate, int eflags)
400400
/*
401401
* Create workspace in which we can remember per-RTE locked tuples
402402
*/
403-
lrstate->lr_ntables = list_length(estate->es_range_table);
403+
lrstate->lr_ntables = estate->es_range_table_size;
404404
lrstate->lr_curtuples = (HeapTuple *)
405405
palloc0(lrstate->lr_ntables * sizeof(HeapTuple));
406406

‎src/backend/replication/logical/worker.c

Copy file name to clipboardExpand all lines: src/backend/replication/logical/worker.c
+1-2Lines changed: 1 addition & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -200,8 +200,7 @@ create_estate_for_relation(LogicalRepRelMapEntry *rel)
200200
rte->relid = RelationGetRelid(rel->localrel);
201201
rte->relkind = rel->localrel->rd_rel->relkind;
202202
rte->rellockmode = AccessShareLock;
203-
estate->es_range_table = list_make1(rte);
204-
estate->es_relations = (Relation *) palloc0(1 * sizeof(Relation));
203+
ExecInitRangeTable(estate, list_make1(rte));
205204

206205
resultRelInfo = makeNode(ResultRelInfo);
207206
InitResultRelInfo(resultRelInfo, rel->localrel, 1, NULL, 0);

‎src/include/executor/executor.h

Copy file name to clipboardExpand all lines: src/include/executor/executor.h
+9Lines changed: 9 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -514,6 +514,15 @@ extern bool ExecRelationIsTargetRelation(EState *estate, Index scanrelid);
514514

515515
extern Relation ExecOpenScanRelation(EState *estate, Index scanrelid, int eflags);
516516

517+
extern void ExecInitRangeTable(EState *estate, List *rangeTable);
518+
519+
static inline RangeTblEntry *
520+
exec_rt_fetch(Index rti, EState *estate)
521+
{
522+
Assert(rti > 0 && rti <= estate->es_range_table_size);
523+
return estate->es_range_table_array[rti - 1];
524+
}
525+
517526
extern Relation ExecGetRangeTableRelation(EState *estate, Index rti);
518527

519528
extern int executor_errposition(EState *estate, int location);

‎src/include/nodes/execnodes.h

Copy file name to clipboardExpand all lines: src/include/nodes/execnodes.h
+5-2Lines changed: 5 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -36,6 +36,7 @@ struct PlanState; /* forward references in this file */
3636
struct ParallelHashJoinState;
3737
struct ExprState;
3838
struct ExprContext;
39+
struct RangeTblEntry; /* avoid including parsenodes.h here */
3940
struct ExprEvalStep; /* avoid including execExpr.h everywhere */
4041

4142

@@ -486,7 +487,9 @@ typedef struct EState
486487
Snapshot es_snapshot; /* time qual to use */
487488
Snapshot es_crosscheck_snapshot; /* crosscheck time qual for RI */
488489
List *es_range_table; /* List of RangeTblEntry */
489-
Relation *es_relations; /* Array of per-es_range_table-entry Relation
490+
struct RangeTblEntry **es_range_table_array; /* equivalent array */
491+
Index es_range_table_size; /* size of the range table arrays */
492+
Relation *es_relations; /* Array of per-range-table-entry Relation
490493
* pointers, or NULL if not yet opened */
491494
PlannedStmt *es_plannedstmt; /* link to top of plan tree */
492495
const char *es_sourceText; /* Source text from QueryDesc */
@@ -563,7 +566,7 @@ typedef struct EState
563566
* return, or NULL if nothing to return; es_epqTupleSet[] is true if a
564567
* particular array entry is valid; and es_epqScanDone[] is state to
565568
* remember if the tuple has been returned already. Arrays are of size
566-
* list_length(es_range_table) and are indexed by scan node scanrelid - 1.
569+
* es_range_table_size and are indexed by scan node scanrelid - 1.
567570
*/
568571
HeapTuple *es_epqTuple; /* array of EPQ substitute tuples */
569572
bool *es_epqTupleSet; /* true if EPQ tuple is provided */

‎src/include/parser/parsetree.h

Copy file name to clipboardExpand all lines: src/include/parser/parsetree.h
-10Lines changed: 0 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -31,16 +31,6 @@
3131
#define rt_fetch(rangetable_index, rangetable) \
3232
((RangeTblEntry *) list_nth(rangetable, (rangetable_index)-1))
3333

34-
/*
35-
* getrelid
36-
*
37-
* Given the range index of a relation, return the corresponding
38-
* relation OID. Note that InvalidOid will be returned if the
39-
* RTE is for a non-relation-type RTE.
40-
*/
41-
#define getrelid(rangeindex,rangetable) \
42-
(rt_fetch(rangeindex, rangetable)->relid)
43-
4434
/*
4535
* Given an RTE and an attribute number, return the appropriate
4636
* variable name or alias for that attribute of that RTE.

0 commit comments

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