Skip to content

Commit d73f4c7

Browse 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

File tree

11 files changed

+87
-52
lines changed

11 files changed

+87
-52
lines changed

‎contrib/postgres_fdw/postgres_fdw.c

Lines 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

Lines 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

Lines 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

Lines 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

Lines 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

Lines 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

Lines 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

Lines 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

Lines 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

Lines 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

Lines 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)