Horton

Thread

Commits

  1. Use ExprStates for hashing in GROUP BY and SubPlans

  2. Speedup Hash Joins with dedicated functions for ExprState hashing

  3. Remove unused field from SubPlanState struct

  1. Add ExprState hashing for GROUP BY and hashed SubPlans

    David Rowley <dgrowleyml@gmail.com> — 2024-09-01T11:49:19Z

    adf97c156 added support to allow ExprStates to support hashing and
adjusted Hash Join to make use of that. That allowed a speedup in hash
value generation as it allowed JIT compilation of hash values. It also
allowed more efficient tuple deforming as all required attributes are
deformed in one go rather than on demand when hashing each join key.

The attached does the same for GROUP BY and hashed SubPlans. The win
for the tuple deformation does not exist here, but there does seem to
be some gains still to be had from JIT compilation.

Using a scale=1 TPC-H lineitem table, I ran the attached script.

The increase is far from impressive, but likely worth migrating these
over to use ExprState too.

master:

alter system set jit = 0;
latency average = 1509.116 ms
latency average = 1502.496 ms
latency average = 1507.560 ms
alter system set jit = 1;
latency average = 1396.015 ms
latency average = 1392.138 ms
latency average = 1396.476 ms
alter system set jit_optimize_above_cost = 0;
latency average = 1290.463 ms
latency average = 1293.364 ms
latency average = 1290.366 ms
alter system set jit_inline_above_cost = 0;
latency average = 1294.540 ms
latency average = 1300.970 ms
latency average = 1302.181 ms

patched:

alter system set jit = 0;
latency average = 1500.183 ms
latency average = 1500.911 ms
latency average = 1504.150 ms (+0.31%)
alter system set jit = 1;
latency average = 1367.427 ms
latency average = 1367.329 ms
latency average = 1366.473 ms (+2.03%)
alter system set jit_optimize_above_cost = 0;
latency average = 1273.453 ms
latency average = 1265.348 ms
latency average = 1272.598 ms (+1.65%)
alter system set jit_inline_above_cost = 0;
latency average = 1264.657 ms
latency average = 1272.661 ms
latency average = 1273.179 ms (+2.29%)

David

  2. Re: Add ExprState hashing for GROUP BY and hashed SubPlans

    Andrei Lepikhov <lepihov@gmail.com> — 2024-10-28T08:51:02Z

    On 9/1/24 18:49, David Rowley wrote:
> adf97c156 added support to allow ExprStates to support hashing and
> adjusted Hash Join to make use of that. That allowed a speedup in hash
> value generation as it allowed JIT compilation of hash values. It also
> allowed more efficient tuple deforming as all required attributes are
> deformed in one go rather than on demand when hashing each join key.
> 
> The attached does the same for GROUP BY and hashed SubPlans. The win
> for the tuple deformation does not exist here, but there does seem to
> be some gains still to be had from JIT compilation.
> 
> Using a scale=1 TPC-H lineitem table, I ran the attached script.
> 
> The increase is far from impressive, but likely worth migrating these
> over to use ExprState too.
Having remembered that SQL Server uses lightweight threads to execute 
massive hash and aggregate operations in parallel, I think this patch is 
promising. Unfortunately, it causes SEGFAULT on 'make check'.

-- 
regards, Andrei Lepikhov

  3. Re: Add ExprState hashing for GROUP BY and hashed SubPlans

    David Rowley <dgrowleyml@gmail.com> — 2024-10-29T09:47:22Z

    On Mon, 28 Oct 2024 at 21:51, Andrei Lepikhov <lepihov@gmail.com> wrote:
> Having remembered that SQL Server uses lightweight threads to execute
> massive hash and aggregate operations in parallel, I think this patch is
> promising. Unfortunately, it causes SEGFAULT on 'make check'.

Thanks for having a look. The crash is because I'd not quite gotten
around to adjusting this to account for the changes made in 9ca67658d
yet. Without adjustment, the ExprState evaluation code would be
looking at an uninitialised location to store the intermediate hash
value.

I've attached an updated patch with a few other fixes. Whilr checking
this tonight, noticed that master does not use
SubPlanState.tab_eq_funcs for anything. I resisted removing that in
this patch. Perhaps a follow-on patch can remove that. I suspect it's
not been used for a long time now, but I didn't do the archaeology
work to find out.

David

  4. Re: Add ExprState hashing for GROUP BY and hashed SubPlans

    David Rowley <dgrowleyml@gmail.com> — 2024-10-31T01:16:07Z

    On Tue, 29 Oct 2024 at 22:47, David Rowley <dgrowleyml@gmail.com> wrote:
> I've attached an updated patch with a few other fixes. Whilr checking
> this tonight, noticed that master does not use
> SubPlanState.tab_eq_funcs for anything. I resisted removing that in
> this patch. Perhaps a follow-on patch can remove that. I suspect it's
> not been used for a long time now, but I didn't do the archaeology
> work to find out.

3974bc319 removed the SubPlanState.tab_eq_funcs field, so here's a
rebased patch.

David

  5. Re: Add ExprState hashing for GROUP BY and hashed SubPlans

    Andrei Lepikhov <lepihov@gmail.com> — 2024-10-31T02:30:06Z

    On 10/31/24 08:16, David Rowley wrote:
> On Tue, 29 Oct 2024 at 22:47, David Rowley <dgrowleyml@gmail.com> wrote:
>> I've attached an updated patch with a few other fixes. Whilr checking
>> this tonight, noticed that master does not use
>> SubPlanState.tab_eq_funcs for anything. I resisted removing that in
>> this patch. Perhaps a follow-on patch can remove that. I suspect it's
>> not been used for a long time now, but I didn't do the archaeology
>> work to find out.
> 
> 3974bc319 removed the SubPlanState.tab_eq_funcs field, so here's a
> rebased patch.
Thanks for sharing this.
I still need to dive deeply into the code. But I have one annoying user 
case where the user complained about a 4x SQL server speedup in 
comparison to Postgres, and I guess it is a good benchmark for your code.
This query is remarkable because of high grouping computation load. Of 
course, I can't provide the user's data, but I have prepared a synthetic 
test to reproduce the case (see attachment).
Comparing the master with and without your patch, the first, I see is 
more extensive usage of memory (see complete explains in the attachment):

Current master:
---------------

Partial HashAggregate  (cost=54492.60..55588.03 rows=19917 width=889)
   (actual time=20621.028..20642.664 rows=10176 loops=9)
   Group Key: t1.x1, t1.x2, t1.x3, t1.x4, t1.x5
   Batches: 1  Memory Usage: 74513kB


Patched:
--------

Partial HashAggregate  (cost=54699.91..55799.69 rows=19996 width=889)
   (actual time=57213.280..186216.604 rows=10302738 loops=9)
   Group Key: t1.x1, t1.x2, t1.x3, t1.x4, t1.x5
   Batches: 261  Memory Usage: 527905kB  Disk Usage: 4832656kB

I wonder what causes memory consumption, but it is hard to decide on the 
patch's positive outcome for now.

-- 
regards, Andrei Lepikhov

  6. Re: Add ExprState hashing for GROUP BY and hashed SubPlans

    David Rowley <dgrowleyml@gmail.com> — 2024-10-31T23:17:27Z

    On Thu, 31 Oct 2024 at 15:30, Andrei Lepikhov <lepihov@gmail.com> wrote:
> Comparing the master with and without your patch, the first, I see is
> more extensive usage of memory (see complete explains in the attachment):
>
> Current master:
>    Batches: 1  Memory Usage: 74513kB

> Patched:
>    Batches: 261  Memory Usage: 527905kB  Disk Usage: 4832656kB

Thanks for testing that. I had forgotten to adjust the storage
location for the hash initial value when I rebased the patch against
the changes made in 9ca67658d. I've fixed that in the attached patch.

The patched version comes out faster for me now:

master: Execution Time: 15515.401 ms
v4 patch: Execution Time: 15024.395 ms

David

  7. Re: Add ExprState hashing for GROUP BY and hashed SubPlans

    Andrei Lepikhov <lepihov@gmail.com> — 2024-11-02T09:13:16Z

    On 11/1/24 06:17, David Rowley wrote:
> On Thu, 31 Oct 2024 at 15:30, Andrei Lepikhov <lepihov@gmail.com> wrote:
>> Comparing the master with and without your patch, the first, I see is
>> more extensive usage of memory (see complete explains in the attachment):
>>
>> Current master:
>>     Batches: 1  Memory Usage: 74513kB
> 
>> Patched:
>>     Batches: 261  Memory Usage: 527905kB  Disk Usage: 4832656kB
> 
> Thanks for testing that. I had forgotten to adjust the storage
> location for the hash initial value when I rebased the patch against
> the changes made in 9ca67658d. I've fixed that in the attached patch.
Okay, I passed through the code. It looks good. Hashing expressions are 
too simple to give notably impressive results, but it is a step in the 
right direction.
I found only one minor issue: an outdated comment (see attachment).
Also, to make a hash calculation as fast as possible, should we add the 
call of murmurhash32 as an optional step of ExprState in the 
ExecBuildHash32FromAttrs?

-- 
regards, Andrei Lepikhov

  8. Re: Add ExprState hashing for GROUP BY and hashed SubPlans

    David Rowley <dgrowleyml@gmail.com> — 2024-11-05T20:38:09Z

    On Sat, 2 Nov 2024 at 22:13, Andrei Lepikhov <lepihov@gmail.com> wrote:
> Okay, I passed through the code. It looks good. Hashing expressions are
> too simple to give notably impressive results, but it is a step in the
> right direction.
> I found only one minor issue: an outdated comment (see attachment).

Thanks for looking. I ended up doing a bit more work on that comment.
See attached.

I was performing some final benchmarks on this and found that there's
a small performance regression for hashed subplans.

The test case is:
create table t1 (a int);
insert into t1 select a from generate_series(1,100000)a;

select * from t1 where a not in(select a from t1);

With my Zen4 laptop I get:

gcc:
master tps = 58.0375255
v5-0001 tps = 56.11840762

clang:
master tps = 58.72993378
v5-0001 tps = 53.39965968

Zen2 3990x
gcc:
master tps = 34.30392818
v5-0001 tps = 33.22067202

clang:
master tps = 34.0497471
v5-0001 tps = 33.34801254

That's the average over 50 runs starting and stopping the server on
each 10 second run.

I'm still thinking about what to do about this. In the meantime, I'm
not going to commit it.

> Also, to make a hash calculation as fast as possible, should we add the
> call of murmurhash32 as an optional step of ExprState in the
> ExecBuildHash32FromAttrs?

I wrote enough of this patch to test the performance. It does not
help. See attached 0002.

David

  9. Re: Add ExprState hashing for GROUP BY and hashed SubPlans

    David Rowley <dgrowleyml@gmail.com> — 2024-11-28T07:05:09Z

    On Wed, 6 Nov 2024 at 09:38, David Rowley <dgrowleyml@gmail.com> wrote:
> I was performing some final benchmarks on this and found that there's
> a small performance regression for hashed subplans.

> I'm still thinking about what to do about this. In the meantime, I'm
> not going to commit it.

I spent quite a bit more time on this both benchmarking and adjusting
the patch.  I've now added some dedicated ExecJust* evaluation
functions for hashing a single Var. This should give something similar
to the JITted performance with optimisation and no inlining for single
columns.  The v6-0002 patch does contain some additional ExecJust*
functions to improve the performance of Hash Joins. I'll remove those
and test them independently.

The benchmark results are often very close and often the numbers are
different on both patched and unpatched if I stop and start the server
and prewarm the tables again.  For this reason, I ended up running the
benchmarks 50 times each stopping and starting the server between each
run. I added a 10-second sleep as it's quite warm weather here
currently and I did start to get thermal throttling on the Zen4 laptop
without this.

Setup:
create table t1 (a int);
insert into t1 values(1);
create table t2 (a int);
insert into t2 select 1 from generate_series(1,1000000);
vacuum freeze analyze t1,t2;

notin.sql: select a from t2 where a not in (select a from t1);

I made it so the hash table contains only a single record and I probe
that record each time. I did that to ensure the hash table item was
always in L1.

groupby.sql: select a from t2 group by a;

This produces a single group. That was done to eliminate CPU cache
related variations and to try and exaggerate any difference with the
ExprState hashing performance as much as possible.

for i in {1..50}; do pg_ctl stop -D pgdata > /dev/null && pg_ctl start
-D pgdata -l pg.log > /dev/null && psql -c "select
pg_prewarm('t1'),pg_prewarm('t2');" postgres > /dev/null && sleep 10
&& pgbench -n -f notin.sql -T 10 -M prepared postgres | grep tps; done

Please see the attached 6 graphs for the results.  Note the left axis
is not scaled to zero. I adjusted the lower end of that axis to be
just below the lowest results value as without that, the lines were
often too close to notice the difference.  I also included a dotted
line with the percentage of performance increase the patched version
gave. These are on the righthand vertical axis.  For both AMD
machines, I compiled with gcc and clang.

The only slowdown I saw was the NOT IN test on the AMD3990x machine.
It's about 3.6% slower with gcc and 1% slower with clang.  All the
other tests show a performance gain. The AMD3990x's GROUP BY test saw
a 13% improvement and the NOT IN test on the Zen4 with gcc averages
almost 33% faster.

I'm pretty happy with this now. The only part I'm not so sure about is
what to pass as the "parent" parameter for ExecBuildHash32FromAttrs()
in nodeSubplan.c.  I think the existing call to
ExecBuildGroupingEqual() is passing the wrong PlanState. I believe
this should be passing the PlanState for the SubPlanState.

David

  10. Re: Add ExprState hashing for GROUP BY and hashed SubPlans

    David Rowley <dgrowleyml@gmail.com> — 2024-12-10T11:44:52Z

    On Thu, 28 Nov 2024 at 20:05, David Rowley <dgrowleyml@gmail.com> wrote:
> The v6-0002 patch does contain some additional ExecJust*
> functions to improve the performance of Hash Joins. I'll remove those
> and test them independently.

Slightly revised plan. I feel that it's better to add the ExecJust*
functions first as these benefit hash joins. With those added, they
can be used for the GROUP BY and NOT IN code right away.

I benchmarked a slightly revised version of the v6-0002 (attached as
v7-0001) with the following hash join case.

create table t1 as select a/100000 as a from generate_series(0,999999)a;
create table t2 as select a from generate_series(0,9)a;

vacuum freeze analyze t1,t2;

bench.sql:
select * from t1 inner join t2 on t1.a=t2.a offset 1000000;

for i in {1..50}; do pg_ctl stop -D pgdata > /dev/null && pg_ctl start
-D pgdata -l pg.log > /dev/null && psql -c "select
pg_prewarm('t1'),pg_prewarm('t2');" postgres > /dev/null && sleep 10
&& pgbench -n -f bench.sql -T 10 -M prepared postgres | grep tps; done

The patch gave me a 10.62% speed-up for an inner hash join on a single
column using an AMD Zen4 7945HX. The attached graph shows master vs
v7-0001 patch with the percentage of performance improvement on the
right axis and the tps on the left vertical axis. Each of the tps from
the 50 runs were sorted and the tps value is displayed for each.

I'm planning on pushing the v7-0001 patch tomorrow and will look
further at the 0002 after that.

David

  11. Re: Add ExprState hashing for GROUP BY and hashed SubPlans

    David Rowley <dgrowleyml@gmail.com> — 2024-12-10T22:36:30Z

    On Wed, 11 Dec 2024 at 00:44, David Rowley <dgrowleyml@gmail.com> wrote:
> I benchmarked a slightly revised version of the v6-0002 (attached as
> v7-0001) with the following hash join case.
>
> create table t1 as select a/100000 as a from generate_series(0,999999)a;
> create table t2 as select a from generate_series(0,9)a;
>
> vacuum freeze analyze t1,t2;
>
> bench.sql:
> select * from t1 inner join t2 on t1.a=t2.a offset 1000000;
>
> for i in {1..50}; do pg_ctl stop -D pgdata > /dev/null && pg_ctl start
> -D pgdata -l pg.log > /dev/null && psql -c "select
> pg_prewarm('t1'),pg_prewarm('t2');" postgres > /dev/null && sleep 10
> && pgbench -n -f bench.sql -T 10 -M prepared postgres | grep tps; done
>
> The patch gave me a 10.62% speed-up for an inner hash join on a single
> column using an AMD Zen4 7945HX. The attached graph shows master vs
> v7-0001 patch with the percentage of performance improvement on the
> right axis and the tps on the left vertical axis. Each of the tps from
> the 50 runs were sorted and the tps value is displayed for each.
>
> I'm planning on pushing the v7-0001 patch tomorrow and will look
> further at the 0002 after that.

I did some further benchmarking of this.  The Apple M2 machine I have
here saw a 6.8% speedup on the above test and the AMD3990x machine saw
1.93%. That was over 50 runs, starting and stopping Postgres each run.
Graphs attached.

I've now pushed v7-0001.

David

  12. Re: Add ExprState hashing for GROUP BY and hashed SubPlans

    David Rowley <dgrowleyml@gmail.com> — 2024-12-11T00:49:42Z

    On Wed, 11 Dec 2024 at 11:36, David Rowley <dgrowleyml@gmail.com> wrote:
> I've now pushed v7-0001.

... and, after a few comment tweaks, I've also pushed the v7-0002 patch.

Thanks for your reviews, Andrei.

David