Horton

Re: POC: converting Lists into arrays

Tom Lane <tgl@sss.pgh.pa.us>

View thread View on postgr.es
From: Tom Lane <tgl@sss.pgh.pa.us>
To: Andres Freund <andres@anarazel.de>
Cc: David Rowley <david.rowley@2ndquadrant.com>, PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Date: 2019-03-03T18:29:04Z
Lists: pgsql-hackers 
Andres Freund <andres@anarazel.de> writes:
> 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 doubt that you'll get far with that; if this experiment is anything
to go by, it's going to be really hard to make the case that twiddling
the representation of widely-known data structures is worth the work
and bug hazards.

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

Well, I did that in the v3 patch, and it still hasn't moved the needle
noticeably in any test case I've tried.  At this point I'm really
struggling to see a reason why we shouldn't just mark this patch rejected
and move on.  If you have test cases that suggest differently, please
show them don't just handwave.

The cases I've been looking at suggest to me that we'd make far
more progress on the excessive-palloc'ing front if we could redesign
things to reduce unnecessary copying of parsetrees.  Right now the
planner does an awful lot of copying because of fear of unwanted
modifications of multiply-linked subtrees.  I suspect that we could
reduce that overhead with some consistently enforced rules about
not scribbling on input data structures; but it'd take a lot of work
to get there, and I'm afraid it'd be easily broken :-(

			regards, tom lane

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.