pg.ddx.io  pgsql-committers@postgresql.org mailing list archive  
help / color / mirror / Atom feed
pgsql: Avoid some other O(N^2) hazards in list manipulation.
3+ messages / 1 participants
[nested] [flat]

* pgsql: Avoid some other O(N^2) hazards in list manipulation.
@ 2021-11-01 20:24 Tom Lane <tgl@sss.pgh.pa.us>
  0 siblings, 0 replies; 3+ messages in thread

From: Tom Lane @ 2021-11-01 20:24 UTC (permalink / raw)
  To: pgsql-committers@lists.postgresql.org

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(-)



^ permalink  raw  reply  [nested|flat] 3+ messages in thread

* pgsql: Avoid some other O(N^2) hazards in list manipulation.
@ 2021-11-01 20:24 Tom Lane <tgl@sss.pgh.pa.us>
  0 siblings, 0 replies; 3+ messages in thread

From: Tom Lane @ 2021-11-01 20:24 UTC (permalink / raw)
  To: pgsql-committers@lists.postgresql.org

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
------
REL_14_STABLE

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

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(-)



^ permalink  raw  reply  [nested|flat] 3+ messages in thread

* pgsql: Avoid some other O(N^2) hazards in list manipulation.
@ 2021-11-01 20:24 Tom Lane <tgl@sss.pgh.pa.us>
  0 siblings, 0 replies; 3+ messages in thread

From: Tom Lane @ 2021-11-01 20:24 UTC (permalink / raw)
  To: pgsql-committers@lists.postgresql.org

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
------
REL_13_STABLE

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

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(-)



^ permalink  raw  reply  [nested|flat] 3+ messages in thread


end of thread, other threads:[~2021-11-01 20:24 UTC | newest]

Thread overview: 3+ messages (download: mbox mbox.gz follow: Atom feed)
-- links below jump to the message on this page --
2021-11-01 20:24 pgsql: Avoid some other O(N^2) hazards in list manipulation. Tom Lane <tgl@sss.pgh.pa.us>
2021-11-01 20:24 pgsql: Avoid some other O(N^2) hazards in list manipulation. Tom Lane <tgl@sss.pgh.pa.us>
2021-11-01 20:24 pgsql: Avoid some other O(N^2) hazards in list manipulation. Tom Lane <tgl@sss.pgh.pa.us>

This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox