The incremental sort patch seems to significantly improve performance for your query: https://commitfest.postgresql.org/17/1124/
On Fri, Jun 1, 2018 at 7:46 AM, Christopher Wilson < chris.wil...@cantabcapital.com> wrote: > 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): > > > > > > 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 > <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 > <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------------------------------ * >
