From f9eb7c14b08d2cc5eda62ffaf37a356c05e89b93 Mon Sep 17 00:00:00 2001 From: Tom Lane Date: Mon, 8 Oct 2018 10:41:34 -0400 Subject: 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 --- src/backend/executor/execUtils.c | 9 +++++++-- 1 file changed, 7 insertions(+), 2 deletions(-) (limited to 'src/backend/executor/execUtils.c') diff --git a/src/backend/executor/execUtils.c b/src/backend/executor/execUtils.c index d98e90e7117..71c6b5dc0a8 100644 --- a/src/backend/executor/execUtils.c +++ b/src/backend/executor/execUtils.c @@ -113,6 +113,7 @@ CreateExecutorState(void) estate->es_range_table_array = NULL; estate->es_range_table_size = 0; estate->es_relations = NULL; + estate->es_rowmarks = NULL; estate->es_plannedstmt = NULL; estate->es_junkFilter = NULL; @@ -142,8 +143,6 @@ CreateExecutorState(void) estate->es_tupleTable = NIL; - estate->es_rowMarks = NIL; - estate->es_processed = 0; estate->es_lastoid = InvalidOid; @@ -709,6 +708,12 @@ ExecInitRangeTable(EState *estate, List *rangeTable) */ estate->es_relations = (Relation *) palloc0(estate->es_range_table_size * sizeof(Relation)); + + /* + * es_rowmarks is also parallel to the es_range_table_array, but it's + * allocated only if needed. + */ + estate->es_rowmarks = NULL; } /* -- cgit v1.2.3