Horton

Re: POC: converting Lists into arrays

Andres Freund <andres@anarazel.de>

View thread View on postgr.es
From: Andres Freund <andres@anarazel.de>
To: Tom Lane <tgl@sss.pgh.pa.us>
Cc: David Rowley <david.rowley@2ndquadrant.com>, PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Date: 2019-03-03T04:34:24Z
Lists: pgsql-hackers 
Hi,

On 2019-03-02 18:11:43 -0500, Tom Lane wrote:
> I wonder what test cases Andres has been looking at that convince
> him that we need a reimplementation of Lists.

My main observation was from when the expression evaluation was using
lists all over. List iteration overhead was very substantial there. But
that's not a problem anymore, because all of those are gone now due to
the expression rewrite.  I personally wasn't actually advocating for a
new list implementation, I was/am advocating that we should move some
tasks over to a more optimized representation.

I still regularly see list overhead matter in production workloads. A
lot of it being memory allocator overhead, which is why I'm concerned
with a rewrite that doesn't reduce the number of memory allocations. And
a lot of it is stuff that you won't see in pgbench - e.g. there's a lot
of production queries that join a bunch of tables with a few dozen
columns, where e.g. all the targetlists are much longer than what you'd
see in pgbench -S.

Greetings,

Andres Freund

Commits

  1. Remove EState.es_range_table_array.

  2. Rationalize use of list_concat + list_copy combinations.

  3. Cosmetic improvements in setup of planner's per-RTE arrays.

  4. Make better use of the new List implementation in a couple of places

  5. Fix sepgsql test results for commit d97b714a2.

  6. Avoid using lcons and list_delete_first where it's easy to do so.

  7. Remove lappend_cell...() family of List functions.

  8. Clean up some ad-hoc code for sorting and de-duplicating Lists.

  9. Redesign the API for list sorting (list_qsort becomes list_sort).

  10. Remove dead code.

  11. Represent Lists as expansible arrays, not chains of cons-cells.

  12. Standardize some more loops that chase down parallel lists.

  13. Reimplement the linked list data structure used throughout the backend.