Re: POC: converting Lists into arrays

On Mon, 4 Mar 2019 at 07:29, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>
> Andres Freund <andres(at)anarazel(dot)de> writes:
> > 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.

I think we discussed this before, but... if this patch is not a win by
itself (and we've already seen it's not really causing much in the way
of regression, if any), then we need to judge it on what else we can
do to exploit the new performance characteristics of List. For
example list_nth() is now deadly fast.

My primary interest here is getting rid of a few places where we build
an array version of some List so that we can access the Nth element
more quickly. What goes on in ExecInitRangeTable() is not particularly
great for queries to partitioned tables with a large number of
partitions where only one survives run-time pruning. I've hacked
together a patch to show you what wins we can have with the new list
implementation.

Using the attached, (renamed to .txt to not upset CFbot) I get:

setup:

create table hashp (a int, b int) partition by hash (a);
select 'create table hashp'||x||' partition of hashp for values with
(modulus 10000, remainder '||x||');' from generate_Series(0,9999) x;
\gexec
alter table hashp add constraint hashp_pkey PRIMARY KEY (a);

postgresql.conf
plan_cache_mode = force_generic_plan
max_parallel_workers_per_gather=0
max_locks_per_transaction=256

bench.sql

\set p random(1,10000)
select * from hashp where a = :p;

master:

tps = 189.499654 (excluding connections establishing)
tps = 195.102743 (excluding connections establishing)
tps = 194.338813 (excluding connections establishing)

your List reimplementation v3 + attached

tps = 12852.003735 (excluding connections establishing)
tps = 12791.834617 (excluding connections establishing)
tps = 12691.515641 (excluding connections establishing)

The attached does include [1], but even with just that the performance
is not as good as with the arraylist plus the follow-on exploits I
added. Now that we have a much faster bms_next_member() some form of
what in there might be okay.

A profile shows that in this workload we're still spending 42% of the
12k TPS in hash_seq_search(). That's due to LockReleaseAll() having a
hard time of it due to the bloated lock table from having to build the
generic plan with 10k partitions. [2] aims to fix that, so likely
we'll be closer to 18k TPS, or about 100x faster.

In fact, I should test that...

tps = 18763.977940 (excluding connections establishing)
tps = 18589.531558 (excluding connections establishing)
tps = 19011.295770 (excluding connections establishing)

Yip, about 100x.

I think these are worthy goals to aspire to.

[1] https://commitfest.postgresql.org/22/1897/
[2] https://commitfest.postgresql.org/22/1993/

--
David Rowley http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Training & Services