Re: Possible optimisation: push down SORT and LIMIT nodes - Mailing list pgsql-hackers

On Jun 1, 2018, at 11:12 AM, Steven Winfield <Steven.Winfield@cantabcapital.com> wrote:

It does indeed!

                                                                           QUERY PLAN

----------------------------------------------------------------------------------------------------------------------------------------------------------------

Limit  (cost=398.50..398.50 rows=100 width=32) (actual time=10.359..10.378 rows=100 loops=1)

   Output: inventory.date, asset.name, inventory.quantity

   ->  Incremental Sort  (cost=398.50..403.27 rows=5006001 width=32) (actual time=10.357..10.365 rows=100 loops=1)

         Output: inventory.date, asset.name, inventory.quantity

         Sort Key: inventory.date, asset.name

         Presorted Key: inventory.date

         Sort Method: quicksort  Memory: 103kB

         Sort Groups: 1

         ->  Nested Loop Left Join  (cost=0.71..1702372.39 rows=5006001 width=32) (actual time=0.030..2.523 rows=1002 loops=1)

               Output: inventory.date, asset.name, inventory.quantity

               Inner Unique: true

               ->  Index Scan using inventory_pkey on temp.inventory  (cost=0.43..238152.40 rows=5006001 width=12) (actual time=0.016..0.290 rows=1002 loops=1)

                     Output: inventory.date, inventory.id_asset, inventory.quantity

               ->  Index Scan using asset_pkey on temp.asset  (cost=0.28..0.29 rows=1 width=28) (actual time=0.002..0.002 rows=1 loops=1002)

                     Output: asset.id, asset.name

                     Index Cond: (asset.id = inventory.id_asset)

 

I’m guessing the feature-freeze for v11 means we won’t see this in the that version, though, and the extra GUC it requires means it will be in v12 at the earliest?

 

From: James Coleman [mailto:jtc331@gmail.com] 
Sent: 01 June 2018 13:50
To: Christopher Wilson
Cc: pgsql-hackers@lists.postgresql.org; Steven Winfield
Subject: Re: FW: Possible optimisation: push down SORT and LIMIT nodes

 

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.wilson@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-performance@postgresql.org'
Cc: Steven Winfield (steven.winfield@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):

 

<image001.png>

 

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