Avoid O(N^2) cost in ExecFindRowMark().
Tom Lane <tgl@sss.pgh.pa.us>
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
Files
| Path | Change | +/− |
|---|---|---|
| src/backend/executor/execCurrent.c | modified | +6 −5 |
| src/backend/executor/execMain.c | modified | +61 −55 |
| src/backend/executor/execUtils.c | modified | +7 −2 |
| src/include/nodes/execnodes.h | modified | +8 −5 |
Discussion
- executor relation handling 62 messages · 2018-08-16 → 2019-02-10