]> granicus.if.org Git - postgresql/commit
Avoid O(N^2) cost in ExecFindRowMark().
authorTom Lane <tgl@sss.pgh.pa.us>
Mon, 8 Oct 2018 14:41:34 +0000 (10:41 -0400)
committerTom Lane <tgl@sss.pgh.pa.us>
Mon, 8 Oct 2018 14:41:34 +0000 (10:41 -0400)
commitf9eb7c14b08d2cc5eda62ffaf37a356c05e89b93
tree9ebff1fa4bbee6b88e8856dcc9016be1969b86c6
parenteee01d606eb40f760799320e75d45c84022353d8
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
src/backend/executor/execMain.c
src/backend/executor/execUtils.c
src/include/nodes/execnodes.h