Horton

Re: POC: converting Lists into arrays

Robert Haas <robertmhaas@gmail.com>

View thread View on postgr.es
From: Robert Haas <robertmhaas@gmail.com>
To: Tom Lane <tgl@sss.pgh.pa.us>
Cc: PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Date: 2019-02-25T18:02:03Z
Lists: pgsql-hackers 
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.

It is also perhaps worth mentioning that reimplementing a List as an
array means that it is... not a list.  That is a pretty odd state of
affairs, and to me is another sign that we want to leave the existing
thing alone and convert some/most/all core code to use a new thing.

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company

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.