Dear Postgres developers,
I sent this query to the performance list a couple of days ago, but nobody has
come up with any suggestions. I was wondering if you'd like to consider it?
If this is interesting but nobody has time to implement it, then I would
potentially be willing to implement and submit it myself, in my own time. I am
experienced with C and C++, but I have not modified Postgres before, and I
would need significant support (e.g. on IRC) to help me to find my way around
the codebase and finish the task in an acceptable amount of time.
Thanks, Chris.
From: Christopher Wilson
Sent: 30 May 2018 16:47
To: 'pgsql-performa...@postgresql.org'
Cc: Steven Winfield (steven.winfi...@cantabcapital.com)
Subject: Possible optimisation: push down SORT and LIMIT nodes
Hi all,
We have a query which is rather slow (about 10 seconds), and it looks like this:
select inventory.date, asset.name, inventory.quantity
from temp.inventory
left outer join temp.asset on asset.id = id_asset
order by inventory.date, asset.name
limit 100
The inventory table has the quantity of each asset in the inventory on each
date (complete SQL to create and populate the tables with dummy data is below).
The query plan looks like this (the non-parallel version is similar):
[cid:image002.png@01D3F831.EEE55810]
Or in text form:
Limit (cost=217591.77..217603.60 rows=100 width=32) (actual
time=9122.235..9122.535 rows=100 loops=1)
Buffers: shared hit=6645, temp read=6363 written=6364
-> Gather Merge (cost=217591.77..790859.62 rows=4844517 width=32) (actual
time=9122.232..9122.518 rows=100 loops=1)
Workers Planned: 3
Workers Launched: 3
Buffers: shared hit=6645, temp read=6363 written=6364
-> Sort (cost=216591.73..220628.83 rows=1614839 width=32) (actual
time=8879.909..8880.030 rows=727 loops=4)
Sort Key: inventory.date, asset.name
Sort Method: external merge Disk: 50904kB
Buffers: shared hit=27365, temp read=25943 written=25947
-> Hash Join (cost=26.52..50077.94 rows=1614839 width=32)
(actual time=0.788..722.095 rows=1251500 loops=4)
Hash Cond: (inventory.id_asset = asset.id)
Buffers: shared hit=27236
-> Parallel Seq Scan on inventory (cost=0.00..29678.39
rows=1614839 width=12) (actual time=0.025..237.977 rows=1251500 loops=4)
Buffers: shared hit=27060
-> Hash (cost=14.01..14.01 rows=1001 width=28) (actual
time=0.600..0.600 rows=1001 loops=4)
Buckets: 1024 Batches: 1 Memory Usage: 68kB
Buffers: shared hit=32
-> Seq Scan on asset (cost=0.00..14.01 rows=1001
width=28) (actual time=0.026..0.279 rows=1001 loops=4)
Buffers: shared hit=32
Planning time: 0.276 ms
Execution time: 9180.144 ms
I can see why it does this, but I can also imagine a potential optimisation,
which would enable it to select far fewer rows from the inventory table.
As we are joining to the primary key of the asset table, we know that this join
will not add extra rows to the output. Every output row comes from a distinct
inventory row. Therefore only 100 rows of the inventory table are required. But
which ones?
If we selected exactly 100 rows from inventory, ordered by date, then all of
the dates that were complete (every row for that date returned) would be in the
output. However, if there is a date which is incomplete (we haven't emitted all
the inventory records for that date), then it's possible that we would need
some records that we haven't emitted yet. This can only be known after joining
to the asset table and sorting this last group by both date and asset name.
But we do know that there can only be 0 or 1 incomplete groups: either the last
group (by date) is incomplete, if the LIMIT cut it off in mid-group, or its end
coincided with the LIMIT boundary and it is complete. As long as we continue
selecting rows from this table until we exhaust the prefix of the overall SORT
which applies to it (in this case, just the date) then it will be complete, and
we will have all the inventory rows that can appear in the output (because no
possible values of columns that appear later in the sort order can cause any
rows with different dates to appear in the output).
I'm imagining something like a sort-limit-finish node, which sorts its input
and then returns at least the limit number of rows, but keeps returning rows
until it exhausts the last sort prefix that it read.
This node could be created from an ordinary SORT and LIMIT pair:
SORT + LIMIT -> SORT-LIMIT-FINISH + SORT + LIMIT
And then pushed down through either a left join, or an inner join on a foreign
key, when the right side is unique, and no columns from the right side appear
in WHERE conditions, nor anywhere in the sort order except at the end. This
sort column suffix would be removed by pushing the node down. The resulting
query plan would then look something like:
Index Scan on inventory
SORT-LIMIT-FINISH(sort=[inventory.date], limit=100) (pushed down through the
join to asset)
Seq Scan on asset
Hash Left Join (inventory.id_asset = asset.id)
Sort (inventory.date, asset.name)
Limit (100)
And would emit only about 100-1000 inventory rows from the index scan.
Does this sound correct, reasonable and potentially interesting to Postgres
developers?
SQL to reproduce:
create schema temp;
create table temp.asset (
id serial primary key,
name text
);
insert into temp.asset (name) select 'Thing ' || random()::text as name from
generate_series(0, 1000) as s;
create table temp.inventory (
date date,
id_asset int,
quantity int,
primary key (date, id_asset),
CONSTRAINT id_asset_fk FOREIGN KEY (id_asset) REFERENCES temp.asset
(id) MATCH SIMPLE
);
insert into temp.inventory (date, id_asset, quantity)
select current_date - days, asset.id, random() from temp.asset,
generate_series(0, 5000) as days;
Thanks, Chris.
This email is confidential. If you are not the intended recipient, please
advise us immediately and delete this message.
The registered name of Cantab- part of GAM Systematic is Cantab Capital
Partners LLP.
See - http://www.gam.com/en/Legal/Email+disclosures+EU for further information
on confidentiality, the risks of non-secure electronic communication, and
certain disclosures which we are required to make in accordance with applicable
legislation and regulations.
If you cannot access this link, please notify us by reply message and we will
send the contents to you.
GAM Holding AG and its subsidiaries (Cantab – GAM Systematic) will collect and
use information about you in the course of your interactions with us.
Full details about the data types we collect and what we use this for and your
related rights is set out in our online privacy policy at
https://www.gam.com/en/legal/privacy-policy.
Please familiarise yourself with this policy and check it from time to time for
updates as it supplements this notice.
