From: | Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> |
---|---|
To: | pgsql-committers(at)lists(dot)postgresql(dot)org |
Subject: | pgsql: Avoid O(N^2) cost in ExecFindRowMark(). |
Date: | 2018-10-08 14:41:39 |
Message-ID: | E1g9Wj5-0002Xc-S4@gemulon.postgresql.org |
Views: | Raw Message | Whole Thread | Download mbox | Resend email |
Thread: | |
Lists: | pgsql-committers |
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
Branch
------
master
Details
-------
https://git.postgresql.org/pg/commitdiff/f9eb7c14b08d2cc5eda62ffaf37a356c05e89b93
Modified Files
--------------
src/backend/executor/execCurrent.c | 11 ++--
src/backend/executor/execMain.c | 116 +++++++++++++++++++------------------
src/backend/executor/execUtils.c | 9 ++-
src/include/nodes/execnodes.h | 13 +++--
4 files changed, 82 insertions(+), 67 deletions(-)
From | Date | Subject | |
---|---|---|---|
Next Message | Tom Lane | 2018-10-08 16:19:27 | pgsql: Improve snprintf.c's handling of NaN, Infinity, and minus zero. |
Previous Message | Alvaro Herrera | 2018-10-08 13:39:23 | Re: pgsql: Fix event triggers for partitioned tables |