Is it possible to reduce the number of rows in a left join using postgre recursion?

Question

I have a database query that takes over two minutes to complete when I add the last channel condition (channel.code) the main conceptual problem is that I only need to get 10 orders per page, while I am filtering the orders table in a subquery, but then I still need to do a few left joins to arrive at the final condition, at which point I'm joining 5 million matching orders with all tables that contain some several million records.

I want to know if it is possible to somehow make a cycle using Postgres, in which, for example, it would take, for example, 100 orders (preliminarily filtered by the conditions of the table) and only then connect them with the rest of the tables, and fulfill the conditions at the end, then if among the selected 100 orders were suitable, then he added them to the final result. This can be done?

All indexes are already there. Here is an example query that I want to optimize:

SELECT ord.billing_number,
       ord.amount_total_sum,
       ord.fare_sum,
       ord.service_fee_sum,
       ord.service_time_limit,
       ord.tax_sum,
       ord.currency,
       ord.pos,
       ord.updated,
       ord.created,
       ord.user_id,
       ord.hidden,
       ord.id,
       ord.marker,
       status.code                                                 as status,
       status.title                                                as status_title,
       partner.code                                                as code,
       partner.fee                                                 as fee,
       partner.fee_refund                                          as fee_refund,
       partner.config                                              as config,
       partner.project,
       COALESCE(contract_parent_partner.code, parent_partner.code) as parent_code,
       u.email                                                     as user_email
FROM (SELECT * FROM tol.order WHERE billing_number::char <> '4') ord
 LEFT JOIN tol.service_cart service_cart ON ord.id = service_cart.order_id
 INNER JOIN tol.ticket_avia_v2 ticket
            ON service_cart.ticket_uid = ticket.id AND service_cart.service_table_name = 'vw_ticket_avia'
 LEFT JOIN tol.user u ON u.id = ord.user_id
 LEFT JOIN tol.partner partner ON ord.partner_id = partner.id
 LEFT JOIN tol.status status ON ord.status_id = status.id
 LEFT JOIN tol.order_channel order_channel ON ord.id = order_channel.order_id
 LEFT JOIN tol.partner_contract partner_contract ON ord.partner_contract_id = partner_contract.id
 LEFT JOIN tol.partner parent_partner ON parent_partner.id = partner.parent_id
 LEFT JOIN tol.channel channel ON order_channel.channel_id = channel.id
 LEFT JOIN tol.partner contract_parent_partner
           ON contract_parent_partner.id = partner_contract.parent_partner_id
WHERE (EXISTS (SELECT 1
               FROM tol.flight
               WHERE tol.flight.ticket_uid = ticket.id
                 AND tol.flight.carrier_code = 'carrier_code'
               ORDER BY tol.flight.id))
  AND (channel.code = 'channel_code')
ORDER BY ord.id DESC
LIMIT 10;

Tried to use subqueries in joins, but since I use a left join, it gives a different result than the current query.

Here is EXPLAIN (ANALYZE, BUFFERS, SETTINGS)

Limit  (cost=3226993.73..3226993.74 rows=1 width=515) (actual time=1051.938..1055.143 rows=0 loops=1)
  Buffers: shared hit=65 read=2
  ->  Sort  (cost=3226993.73..3226993.74 rows=1 width=515) (actual time=32.786..35.991 rows=0 loops=1)
"        Sort Key: ""order"".id DESC"
        Sort Method: quicksort  Memory: 25kB
        Buffers: shared hit=65 read=2
        ->  Nested Loop Left Join  (cost=2038882.89..3226993.72 rows=1 width=515) (actual time=32.724..35.926 rows=0 loops=1)
              Join Filter: (contract_parent_partner.id = partner_contract.parent_partner_id)
              Buffers: shared hit=62 read=2
              ->  Nested Loop Left Join  (cost=2038882.89..3225588.32 rows=1 width=492) (actual time=32.723..35.924 rows=0 loops=1)
                    Join Filter: (parent_partner.id = partner.parent_id)
                    Buffers: shared hit=62 read=2
                    ->  Gather  (cost=2038882.89..3224182.92 rows=1 width=491) (actual time=32.722..35.922 rows=0 loops=1)
                          Workers Planned: 2
                          Workers Launched: 2
                          Buffers: shared hit=62 read=2
                          ->  Nested Loop Semi Join  (cost=2037882.89..3223182.82 rows=1 width=491) (actual time=0.723..0.728 rows=0 loops=3)
                                Buffers: shared hit=62 read=2
                                ->  Hash Join  (cost=2037812.20..3215337.24 rows=105 width=523) (actual time=0.723..0.726 rows=0 loops=3)
                                      Hash Cond: (order_channel.channel_id = channel.id)
                                      Buffers: shared hit=62 read=2
                                      ->  Hash Left Join  (cost=2037803.88..3206741.25 rows=3271051 width=527) (never executed)
"                                            Hash Cond: (""order"".partner_contract_id = partner_contract.id)"
                                            ->  Hash Left Join  (cost=2037462.25..3197812.02 rows=3271051 width=527) (never executed)
"                                                  Hash Cond: (""order"".status_id = status.id)"
                                                  ->  Parallel Hash Left Join  (cost=2037460.83..3187308.80 rows=3271051 width=475) (never executed)
"                                                        Hash Cond: (""order"".partner_id = partner.id)"
                                                        ->  Parallel Hash Left Join  (cost=1941872.95..3083133.07 rows=3271051 width=166) (never executed)
"                                                              Hash Cond: (""order"".user_id = u.id)"
                                                              ->  Parallel Hash Join  (cost=1646731.87..2615342.48 rows=3271051 width=152) (never executed)
"                                                                    Hash Cond: (service_cart.order_id = ""order"".id)"
                                                                    ->  Parallel Hash Join  (cost=582600.12..1337818.87 rows=5341282 width=44) (never executed)
                                                                          Hash Cond: (service_cart.order_id = order_channel.order_id)
                                                                          ->  Parallel Hash Join  (cost=402211.21..1040928.08 rows=5341282 width=36) (never executed)
                                                                                Hash Cond: (ticket.id = service_cart.ticket_uid)
                                                                                ->  Parallel Index Only Scan using ticket_avia_v2_id on ticket_avia_v2 ticket  (cost=0.56..521205.61 rows=6446412 width=16) (never executed)
                                                                                      Heap Fetches: 0
                                                                                ->  Parallel Hash  (cost=284286.30..284286.30 rows=6423068 width=20) (never executed)
                                                                                      ->  Parallel Seq Scan on service_cart  (cost=0.00..284286.30 rows=6423068 width=20) (never executed)
                                                                                            Filter: (service_table_name = 'vw_ticket_avia'::text)
                                                                          ->  Parallel Hash  (cost=100494.85..100494.85 rows=4869685 width=8) (never executed)
                                                                                ->  Parallel Seq Scan on order_channel  (cost=0.00..100494.85 rows=4869685 width=8) (never executed)
                                                                    ->  Parallel Hash  (cost=883642.55..883642.55 rows=6000656 width=116) (never executed)
"                                                                          ->  Parallel Seq Scan on ""order""  (cost=0.00..883642.55 rows=6000656 width=116) (never executed)"
                                                                                Filter: ((billing_number)::character(1) <> '4'::bpchar)
                                                              ->  Parallel Hash  (cost=221481.48..221481.48 rows=4012048 width=18) (never executed)
"                                                                    ->  Parallel Seq Scan on ""user"" u  (cost=0.00..221481.48 rows=4012048 width=18) (never executed)"
                                                        ->  Parallel Hash  (cost=95389.05..95389.05 rows=15906 width=321) (never executed)
                                                              ->  Parallel Index Scan using partner_parent_index on partner  (cost=0.29..95389.05 rows=15906 width=321) (never executed)
                                                  ->  Hash  (cost=1.19..1.19 rows=19 width=60) (never executed)
                                                        ->  Seq Scan on status  (cost=0.00..1.19 rows=19 width=60) (never executed)
                                            ->  Hash  (cost=243.50..243.50 rows=7850 width=8) (never executed)
                                                  ->  Seq Scan on partner_contract  (cost=0.00..243.50 rows=7850 width=8) (never executed)
                                      ->  Hash  (cost=8.30..8.30 rows=1 width=4) (actual time=0.484..0.484 rows=0 loops=3)
                                            Buckets: 1024  Batches: 1  Memory Usage: 8kB
                                            Buffers: shared hit=6 read=2
                                            ->  Index Scan using uniq_6cae9c8d77153098 on channel  (cost=0.29..8.30 rows=1 width=4) (actual time=0.483..0.483 rows=0 loops=3)
                                                  Index Cond: (code = 'channel_code'::text)
                                                  Buffers: shared hit=6 read=2
                                ->  Bitmap Heap Scan on flight  (cost=70.69..74.71 rows=1 width=16) (never executed)
                                      Recheck Cond: ((ticket_uid = service_cart.ticket_uid) AND (carrier_code = 'carrier_code'::text))
                                      ->  BitmapAnd  (cost=70.69..70.69 rows=1 width=0) (never executed)
                                            ->  Bitmap Index Scan on flight_ticket_idx  (cost=0.00..4.35 rows=36 width=0) (never executed)
                                                  Index Cond: (ticket_uid = service_cart.ticket_uid)
                                            ->  Bitmap Index Scan on idx_flight_carrier_code  (cost=0.00..65.28 rows=3295 width=0) (never executed)
                                                  Index Cond: (carrier_code = 'carrier_code'::text)
                    ->  Seq Scan on partner parent_partner  (cost=0.00..1067.40 rows=27040 width=9) (never executed)
              ->  Seq Scan on partner contract_parent_partner  (cost=0.00..1067.40 rows=27040 width=9) (never executed)
Planning Time: 48.168 ms
JIT:
  Functions: 228
"  Options: Inlining true, Optimization true, Expressions true, Deforming true"
"  Timing: Generation 23.199 ms, Inlining 51.477 ms, Optimization 580.442 ms, Emission 386.265 ms, Total 1041.384 ms"
Execution Time: 1078.301 ms

Please post details for your performance question as instructed in the tag wiki: https://stackoverflow.com/tags/postgresql-performance/info. The hidden `SELECT` list would help to determine which tables are actually required in the `FROM` clause. Plus, what do you get for `SHOW join_collapse_limit;` And there should not be a cast here: `billing_number::char` - it disables plain indexes. — Erwin Brandstetter, May 07 '23 at 04:55
Try moving the expression ,`AND (channel.code = 'channel_code')`, from the `WHERE` clause to the `JOIN` condition between `channel` and `order_channel` and change the `LEFT JOIN` between those tables to a `JOIN`. Having that condition in the `WHERE` clause effectively makes the result the same as if it had not been an `OUTER JOIN`. While not part of the performance problem, also remove the redundant table aliases. They add noise without contributing any value. — JohnH, May 07 '23 at 05:38

Erwin Brandstetter · Answer 1 · 2023-05-09T21:45:54.117

What you ask for

... is possible, of course. Build a function to loop over patches of sorted rows, or ranges of values to force a certain "query plan", where Postgres has a blind spot. One sophisticated example:

Can spatial index help a "range - order by - limit" query

More often than not, the better solution is to get server configuration, data model and column statistics straight. If one particular index driving the query is the fastest approach, Postgres should arrive at that query plan all by itself.

... but that's leading nowhere for the given case. Your added query plan reveals rows=0. No qualifying rows are found. That's often a worst case scenario for a query with ORDER BY and a small LIMIT - if the query plan ends up walking along the sort order until enough rows are found. Your idea of forcing Postgres to do just that in small patches of 100 rows would only make it worse.

Server configuration

Your query plan does not show any non-standard settings (which it would when EXPLAIN is called with the SETTINGS option. If your input is reliable, that means you are running Postgres with default settings, which is only good for very basic needs. Start with server configuration. Here are some starters:

https://wiki.postgresql.org/wiki/Slow_Query_Questions

General improvements

You are joining 11 tables (and it's unclear if you actually need to involve all of them). That's beyond the default setting for join_collapse_limit. So the order of joins as written becomes relevant. See:

Why does a slight change in the search term slow down the query so much?

Move joins that actually filter rows to the front, and move joins that multiply rows to the end. That might already improve performance a lot:

SELECT ord.billing_number
  --  , ... (a lot of fields)
FROM   tol.order              ord
JOIN   tol.order_channel               ON order_channel.order_id = ord.id
JOIN   tol.channel                     ON channel.id = order_channel.channel_id  -- move to the top !!
JOIN   tol.service_cart                ON service_cart.order_id = ord.id
JOIN   tol.ticket_avia_v2     ticket   ON ticket.id = service_cart.ticket_uid
                                      AND service_cart.service_table_name = 'vw_ticket_avia'
LEFT   JOIN tol.user          u        ON u.id = ord.user_id
LEFT   JOIN tol.status                 ON status.id = ord.status_id
LEFT   JOIN tol.partner                ON partner.id = ord.partner_id
LEFT   JOIN tol.partner       parent_partner ON parent_partner.id = partner.parent_id
LEFT   JOIN tol.partner_contract       ON partner_contract.id = ord.partner_contract_id
LEFT   JOIN tol.partner       contract_parent_partner ON contract_parent_partner.id = partner_contract.parent_partner_id
WHERE  ord.billing_number ^@ '4'  -- "starts with" operator - more efficient
AND    EXISTS (
   SELECT FROM tol.flight f
   WHERE  f.ticket_uid = ticket.id
   AND    f.carrier_code = 'carrier_code'
   )
AND    channel.code = 'channel_code'
ORDER  BY ord.id DESC
LIMIT  10;

Also, some instances of LEFT JOIN are effectively [INNER] JOIN. See:

Postgres LEFT JOIN with WHERE condition

That does not normally matter much, Postgres does the right thing either way. But it might matter for manually optimizing the sequence of joins. See:

Assuming order.billing_number is a string type, replace billing_number::char <> '4') ord with ord.billing_number ^@ '4', that's generally much cheaper, and allows using a plain index with COLLATE "C" Like:

CREATE INDEX text_b ON tol.order (billing_number COLLATE "C");

See:

PostgreSQL LIKE query performance variations

If it's a different data type, optimize in a different way ...

ORDER BY makes no sense in an EXISTS subquery expression. I dropped that.

(At least) the joins to contract_parent_partner looks like it might multiply rows. Is that so? And do you want to return multiple rows per qualifying orders in that case?

If all of this still does not get you acceptable performance then, yes, some kind of recursion or loop might help (a lot) to fill your tiny LIMIT 10 - for queries that actually do find rows. Or you can optimize some indexes and update / improve statistics to get a different query plan. That's beyond the scope of a question here on SO.

Thank you very much for your answer, I edited my query and wrote which fields I select, so I need joins for these tables. I wanted to ask you why you take out the filtering by order billing down from the subquery at the beginning, because it allows you to significantly reduce orders with inappropriate billing in join operations.(Reduces the number of rows in the join) — Михаил Удинцев, May 07 '23 at 06:27
One condition for filtering by channel code increases the query execution plan by 20 rows, and its time increases tenfold. But still, it seems wrong to me to join 5 million rows when I only need the last 10 orders that satisfy the filters. I don’t know if it’s possible to make it take, for example, 100 - 1000 last orders and join to the remaining tables, and if a part is suitable, then it is added to the final result, and when it reaches 10, it returns — Михаил Удинцев, May 07 '23 at 06:37
@МихаилУдинцев There are ways. Please [edit] your question with requested info. Follow the link I gave in my comment. Most importantly, the result of `EXPLAIN (ANALYZE, BUFFERS, SETTINGS) SELECT ...` — Erwin Brandstetter, May 08 '23 at 07:08

Is it possible to reduce the number of rows in a left join using postgre recursion?

1 Answers1

What you ask for

Server configuration

General improvements