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

3 files changed, 14 insertions, 12 deletions

diff --git a/src/include/executor/executor.h b/src/include/executor/executor.h
index 83ce989e3a..830f42dfe3 100644
--- a/src/include/executor/executor.h
+++ b/src/include/executor/executor.h
@@ -514,6 +514,15 @@ extern bool ExecRelationIsTargetRelation(EState *estate, Index scanrelid);
 
 extern Relation ExecOpenScanRelation(EState *estate, Index scanrelid, int eflags);
 
+extern void ExecInitRangeTable(EState *estate, List *rangeTable);
+
+static inline RangeTblEntry *
+exec_rt_fetch(Index rti, EState *estate)
+{
+	Assert(rti > 0 && rti <= estate->es_range_table_size);
+	return estate->es_range_table_array[rti - 1];
+}
+
 extern Relation ExecGetRangeTableRelation(EState *estate, Index rti);
 
 extern int	executor_errposition(EState *estate, int location);
diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h
index 35646231a4..657b593663 100644
--- a/src/include/nodes/execnodes.h
+++ b/src/include/nodes/execnodes.h
@@ -36,6 +36,7 @@ struct PlanState;				/* forward references in this file */
 struct ParallelHashJoinState;
 struct ExprState;
 struct ExprContext;
+struct RangeTblEntry;			/* avoid including parsenodes.h here */
 struct ExprEvalStep;			/* avoid including execExpr.h everywhere */
 
 
@@ -486,7 +487,9 @@ typedef struct EState
 	Snapshot	es_snapshot;	/* time qual to use */
 	Snapshot	es_crosscheck_snapshot; /* crosscheck time qual for RI */
 	List	   *es_range_table; /* List of RangeTblEntry */
-	Relation   *es_relations;	/* Array of per-es_range_table-entry Relation
+	struct RangeTblEntry **es_range_table_array;	/* equivalent array */
+	Index		es_range_table_size;	/* size of the range table arrays */
+	Relation   *es_relations;	/* Array of per-range-table-entry Relation
 								 * pointers, or NULL if not yet opened */
 	PlannedStmt *es_plannedstmt;	/* link to top of plan tree */
 	const char *es_sourceText;	/* Source text from QueryDesc */
@@ -563,7 +566,7 @@ typedef struct EState
 	 * return, or NULL if nothing to return; es_epqTupleSet[] is true if a
 	 * particular array entry is valid; and es_epqScanDone[] is state to
 	 * remember if the tuple has been returned already.  Arrays are of size
-	 * list_length(es_range_table) and are indexed by scan node scanrelid - 1.
+	 * es_range_table_size and are indexed by scan node scanrelid - 1.
 	 */
 	HeapTuple  *es_epqTuple;	/* array of EPQ substitute tuples */
 	bool	   *es_epqTupleSet; /* true if EPQ tuple is provided */
diff --git a/src/include/parser/parsetree.h b/src/include/parser/parsetree.h
index dd9ae658ac..fe16d7d1fa 100644
--- a/src/include/parser/parsetree.h
+++ b/src/include/parser/parsetree.h
@@ -32,16 +32,6 @@
 	((RangeTblEntry *) list_nth(rangetable, (rangetable_index)-1))
 
 /*
- *		getrelid
- *
- *		Given the range index of a relation, return the corresponding
- *		relation OID.  Note that InvalidOid will be returned if the
- *		RTE is for a non-relation-type RTE.
- */
-#define getrelid(rangeindex,rangetable) \
-	(rt_fetch(rangeindex, rangetable)->relid)
-
-/*
  * Given an RTE and an attribute number, return the appropriate
  * variable name or alias for that attribute of that RTE.
  */