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/execCurrent.c | 11 ++++++----- 1 file changed, 6 insertions(+), 5 deletions(-) (limited to 'src/backend/executor/execCurrent.c') diff --git a/src/backend/executor/execCurrent.c b/src/backend/executor/execCurrent.c index 7480cf50ad0..aadf7493827 100644 --- a/src/backend/executor/execCurrent.c +++ b/src/backend/executor/execCurrent.c @@ -91,21 +91,22 @@ execCurrentOf(CurrentOfExpr *cexpr, * the other code can't, while the non-FOR-UPDATE case allows use of WHERE * CURRENT OF with an insensitive cursor. */ - if (queryDesc->estate->es_rowMarks) + if (queryDesc->estate->es_rowmarks) { ExecRowMark *erm; - ListCell *lc; + Index i; /* * Here, the query must have exactly one FOR UPDATE/SHARE reference to * the target table, and we dig the ctid info out of that. */ erm = NULL; - foreach(lc, queryDesc->estate->es_rowMarks) + for (i = 0; i < queryDesc->estate->es_range_table_size; i++) { - ExecRowMark *thiserm = (ExecRowMark *) lfirst(lc); + ExecRowMark *thiserm = queryDesc->estate->es_rowmarks[i]; - if (!RowMarkRequiresRowShareLock(thiserm->markType)) + if (thiserm == NULL || + !RowMarkRequiresRowShareLock(thiserm->markType)) continue; /* ignore non-FOR UPDATE/SHARE items */ if (thiserm->relid == table_oid) -- cgit v1.2.3