Horton

Re: POC: converting Lists into arrays

Daniel Gustafsson <daniel@yesql.se>

View thread View on postgr.es
From: Daniel Gustafsson <daniel@yesql.se>
To: Tom Lane <tgl@sss.pgh.pa.us>
Cc: David Rowley <david.rowley@2ndquadrant.com>, Jesper Pedersen <jesper.pedersen@redhat.com>, Andres Freund <andres@anarazel.de>, Robert Haas <robertmhaas@gmail.com>, PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
Date: 2019-07-17T14:12:28Z
Lists: pgsql-hackers

Attachments

> On 17 Jul 2019, at 01:06, Tom Lane <tgl@sss.pgh.pa.us> wrote:

> There are a bunch of places that are using list_delete_first to remove
> the next-to-process entry from a List used as a queue.  In principle,
> we could invert the order of those queues and then use list_delete_last,
> but I thought this would probably be too confusing: it's natural to
> think of the front of the list as being the head of the queue.  I doubt
> that any of those queues get long enough for it to be a serious
> performance problem to leave them as-is.

For cases where an Oid list is copied and then head elements immediately
removed, as in fetch_search_path, couldn’t we instead use a counter and
list_copy_tail to avoid repeated list_delete_first calls?  Something like the
attached poc.

> +List *
> +list_delete_last(List *list)
> +{
> +	check_list_invariants(list);
> +
> +	if (list == NIL)
> +		return NIL;				/* would an error be better? */

Since we’ve allowed list_delete_first on NIL for a long time, it seems
reasonable to do the same for list_delete_last even though it’s hard to come up
with a good usecase for deleting the last element without inspecting the list
(a stack growing from the bottom perhaps?).  It reads better to check for NIL
before calling check_list_invariants though IMO.

Looking mainly at 0001 for now, I agree that the order is insignificant.

cheers ./daniel

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.