pgsql: Avoid some other O(N^2) hazards in list manipulation.

From: Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>
To: pgsql-committers(at)lists(dot)postgresql(dot)org
Subject: pgsql: Avoid some other O(N^2) hazards in list manipulation.
Date: 2021-11-01 20:24:56
Message-ID: E1mhdrU-0001fE-8A@gemulon.postgresql.org
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-committers

Avoid some other O(N^2) hazards in list manipulation.

In the same spirit as 6301c3ada, fix some more places where we were
using list_delete_first() in a loop and thereby risking O(N^2)
behavior. It's not clear that the lists manipulated in these spots
can get long enough to be really problematic ... but it's not clear
that they can't, either, and the fixes are simple enough.

As before, back-patch to v13.

Discussion: https://postgr.es/m/CD2F0E7F-9822-45EC-A411-AE56F14DEA9F@amazon.com

Branch
------
master

Details
-------
https://git.postgresql.org/pg/commitdiff/e9d9ba2a4ddc39e331dd8461b511aa59ec0dc8af

Modified Files
--------------
contrib/pg_trgm/trgm_regexp.c | 25 +++++++++++++++++--------
src/backend/executor/nodeAgg.c | 17 +++++------------
src/backend/jit/llvm/llvmjit.c | 10 +++++-----
3 files changed, 27 insertions(+), 25 deletions(-)

Browse pgsql-committers by date

  From Date Subject
Next Message Daniel Gustafsson 2021-11-01 21:56:02 pgsql: Replace unicode characters in comments with ascii
Previous Message Alvaro Herrera 2021-11-01 16:08:56 pgsql: Handle XLOG_OVERWRITE_CONTRECORD in DecodeXLogOp