PostgreSQL v12 merge, MK sort, performance

[Heikki Linnakangas]

Hi!

The PostgreSQL v12 merge is getting close to finish, and we have started
to so some benchmarking.

TL;DR summary:

On my laptop, TPC-DS query 67 is slower on the merge branch than on
master, because we lost the MK sort.


Longer story:

Ashwin, Alex and others have set up a testing rig to run TPC-DS
benchmarks, and compare between the merge branch, master, and 6X_STABLE.
Zhenghua Lyu analyzed the results, and one takeaway is that query 67 is
much slower on the merge branch, because you get different plan, which
does the final aggregation stage in the QD, instead of in parallel in
the QEs.

That's a different result than what I'm seeing with on my laptop, with a
smaller dataset and fewer segments. I'm seeing the same plan on the
merge branch and on master. The 6X_STABLE plan looks different, and is
indeed doing the aggregation in parallel, but on my laptop that doesn't
seem to be the bottleneck. The bottleneck on all three branches is
sorting the data. I trust Zhenghua's analysis too, it's a different test
case, on different hardware, so I think should be treated as an
independent issue.

To keep things simple, I've focused on this simplified version of TPC-DS
query #67:

select i_category
,i_class
,i_brand
,i_product_name
,d_year
,d_qoy
,d_moy
,s_store_id
,sum(coalesce(ss_sales_price*ss_quantity,0)) sumsales
from store_sales
,date_dim
,store
,item
where ss_sold_date_sk=d_date_sk
and ss_item_sk=i_item_sk
and ss_store_sk = s_store_sk
and d_month_seq between 1201 and 1201+11
group by rollup(i_category, i_class, i_brand, i_product_name,
d_year, d_qoy, d_moy,s_store_id)

The plan on merge and master branches looks like this (the 6X_STABLE
plan is different, but sorting is significant there too):
QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------------------------------------------
GroupAggregate
Group Key: item.i_category, item.i_class, item.i_brand,
item.i_product_name, date_dim.d_year, date_dim.d_qoy, date_dim.d_moy,
store.s_store_id
Group Key: item.i_category, item.i_class, item.i_brand,
item.i_product_name, date_dim.d_year, date_dim.d_qoy, date_dim.d_moy
Group Key: item.i_category, item.i_class, item.i_brand,
item.i_product_name, date_dim.d_year, date_dim.d_qoy
Group Key: item.i_category, item.i_class, item.i_brand,
item.i_product_name, date_dim.d_year
Group Key: item.i_category, item.i_class, item.i_brand,
item.i_product_name
Group Key: item.i_category, item.i_class, item.i_brand
Group Key: item.i_category, item.i_class
Group Key: item.i_category
Group Key: ()
-> Gather Motion 3:1 (slice1; segments: 3)
Merge Key: item.i_category, item.i_class, item.i_brand,
item.i_product_name, date_dim.d_year, date_dim.d_qoy, date_dim.d_moy,
store.s_store_id
-> Sort
Sort Key: item.i_category, item.i_class, item.i_brand,
item.i_product_name, date_dim.d_year, date_dim.d_qoy, date_dim.d_moy,
store.s_store_id
-> Hash Join
Hash Cond: (store_sales.ss_item_sk = item.i_item_sk)
-> Hash Join
Hash Cond: (store_sales.ss_store_sk =
store.s_store_sk)
-> Hash Join
Hash Cond:
(store_sales.ss_sold_date_sk = date_dim.d_date_sk)
-> Seq Scan on store_sales
-> Hash
-> Broadcast Motion 3:3
(slice2; segments: 3)
-> Seq Scan on date_dim
Filter:
((d_month_seq >= 1201) AND (d_month_seq <= 1212))
-> Hash
-> Broadcast Motion 3:3 (slice3;
segments: 3)
-> Seq Scan on store
-> Hash
-> Seq Scan on item
Optimizer: Postgres query optimizer
(31 rows)


How does this actually perform? With statement_mem set high enough that
the sorts are performed in memory:

master: 26 s
merge: 35 s
6X_STABLE: 51 s

When I look at the "actual time" spent in the Sort node with EXPLAIN
ANALYZE, the difference is even more stark:

master: 12 s
merge: 20 s
6X_STABLE: 12 s


One change is that as part of the merge, we removed the code for
so-called "MK sort", or multi-key sort. It's a different implementation
of sorting, supposedly faster than the upstream algorithm when you sort
by multiple columns. We've discussed it on this list before. This query
is very sympathetic to the MK sort. It's got a lot of sort keys, and
lots of duplicate in the leading columns. That explains the difference.

Another contributing factor could be the change to use MinimalTuples
instead of MemTuples in sorting. In a MemTuple, it is supposedly faster
to fetch individual columns from the tuple, and that could also make the
upstream sort faster. A lot of CPU time is now spent fetching the
non-leading sort columns from tuples. The MK sort would do less of that,
and a MemTuple would be faster at doing that.

So on my laptop, TPC-DS query 67 is slower on the merge branch than on
master, because we lost the MK sort, and perhaps the MemTuples.

Maybe that's acceptable. But if we can re-implement the MK sort and
submit it to pgsql-hackers, that would be good.

- Heikki