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: Robert Haas <robertmhaas@gmail.com>
Cc: Tom Lane <tgl@sss.pgh.pa.us>, PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Date: 2019-02-25T20:51:19Z
Lists: pgsql-hackers 
Hi,

On 2019-02-25 13:02:03 -0500, Robert Haas wrote:
> On Sat, Feb 23, 2019 at 9:24 PM Tom Lane <tgl@sss.pgh.pa.us> wrote:
> > Every time this has come up, I've opined that the right fix is to jack
> > up the List API and drive a new implementation underneath, as we did
> > once before (cf commit d0b4399d81).  I thought maybe it was about time
> > to provide some evidence for that position, so attached is a POC patch
> > that changes Lists into expansible arrays, while preserving most of
> > their existing API.
> 
> I'm not really convinced that this is the way to go.  The thing is,
> any third-party code people have that uses a List may simply break.
> If you kept the existing List and changed a bunch of existing code to
> use a new Vector implementation, or Thomas's SimpleVector stuff, then
> that wouldn't happen.  The reason why people - or at least me - have
> been reluctant to accept that you can just jack up the API and drive a
> new implementation underneath is that the new implementation will
> involve breaking guarantees on which existing code relies; indeed,
> your email makes it pretty clear that this is the case.  If you could
> replace the existing implementation without breaking any code, that
> would be a no-brainer but there's no real way to do that and get the
> performance benefits you're seeking to obtain.

Yea, it'd be more convincing. I'm not convinced it'd be a no-brainer
though. Unless you've been hacking PG for a fair bit, the pg_list.h APIs
are very hard to understand / remember. Given this change essentially
requires auditing all code that uses List, ISTM we'd be much better off
also changing the API at the same time.  Yes that'll mean there'll be
vestigial uses nobody bothered to convert in extension etc, but that's
not that bad.

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.