Why is this PostgreSQL query with LIMIT so slow?

Question

I have a .NET WebApi with two entities (please forgive the silly names, it's just an example):

public class Father
{
    public int Id { get; set; }
    public string Name { get; set; } = null!;
    public int? ChildAId { get; set; }
    public int? ChildBId { get; set; }
    public int? ChildCId { get; set; }
    public int? ChildDId { get; set; }
    public int? ChildEId { get; set; }
    public int? ChildFId { get; set; }
    public int? ChildGId { get; set; }
    public int? ChildHId { get; set; }
    public int? ChildIId { get; set; }
    public int? ChildJId { get; set; }
    public int? ChildKId { get; set; }
    public int? ChildLId { get; set; }
    public int? ChildMId { get; set; }
    public int? ChildNId { get; set; }
    public int? ChildOId { get; set; }
    public int? ChildPId { get; set; }
    public int? ChildQId { get; set; }
    public int? ChildRId { get; set; }
    public int? ChildSId { get; set; }
    public int? ChildTId { get; set; }
    public int? ChildUId { get; set; }
    public int? ChildVId { get; set; }
    public int? ChildWId { get; set; }
    public int? ChildXId { get; set; }
    public int? ChildYId { get; set; }
    public int? ChildZId { get; set; }
    public int? Child0Id { get; set; }
    public int? Child1Id { get; set; }
    public int? Child2Id { get; set; }
    public int? Child3Id { get; set; }
    public int? Child4Id { get; set; }
    public int? Child5Id { get; set; }
    public int? Child6Id { get; set; }
    public int? Child7Id { get; set; }
    public int? Child8Id { get; set; }
    public int? Child9Id { get; set; }
public Child? ChildA { get; set; }
public Child? ChildB { get; set; }
public Child? ChildC { get; set; }
public Child? ChildD { get; set; }
public Child? ChildE { get; set; }
public Child? ChildF { get; set; }
public Child? ChildG { get; set; }
public Child? ChildH { get; set; }
public Child? ChildI { get; set; }
public Child? ChildJ { get; set; }
public Child? ChildK { get; set; }
public Child? ChildL { get; set; }
public Child? ChildM { get; set; }
public Child? ChildN { get; set; }
public Child? ChildO { get; set; }
public Child? ChildP { get; set; }
public Child? ChildQ { get; set; }
public Child? ChildR { get; set; }
public Child? ChildS { get; set; }
public Child? ChildT { get; set; }
public Child? ChildU { get; set; }
public Child? ChildV { get; set; }
public Child? ChildW { get; set; }
public Child? ChildX { get; set; }
public Child? ChildY { get; set; }
public Child? ChildZ { get; set; }
public Child? Child0 { get; set; }
public Child? Child1 { get; set; }
public Child? Child2 { get; set; }
public Child? Child3 { get; set; }
public Child? Child4 { get; set; }
public Child? Child5 { get; set; }
public Child? Child6 { get; set; }
public Child? Child7 { get; set; }
public Child? Child8 { get; set; }
public Child? Child9 { get; set; }

}
public class Child
{
    public int Id { get; set; }
    public string Name { get; set; } = null!;
    public string Description { get; set; } = null!;
}

I have inserted 100.000 fathers with their children from A to Z populated. Now I'm trying to recover them from the database using EF Core (but PgAdmin gives the same results).

20 FATHERS WITH LIMIT/OFFSET

SELECT f."Id", f."Child0Id", f."Child1Id", f."Child2Id", f."Child3Id", f."Child4Id", f."Child5Id", f."Child6Id", f."Child7Id", f."Child8Id", f."Child9Id", f."ChildAId", f."ChildBId", f."ChildCId", f."ChildDId", f."ChildEId", f."ChildFId", f."ChildGId", f."ChildHId", f."ChildIId", f."ChildJId", f."ChildKId", f."ChildLId", f."ChildMId", f."ChildNId", f."ChildOId", f."ChildPId", f."ChildQId", f."ChildRId", f."ChildSId", f."ChildTId", f."ChildUId", f."ChildVId", f."ChildWId", f."ChildXId", f."ChildYId", f."ChildZId", f."Name"
FROM "Father" AS f
LIMIT 20 OFFSET 98000

Query completes in 130ms

20 FATHERS WITH ALL THEIR CHILDREN AND LIMIT/OFFSET

  SELECT t."Id", t."Child0Id", t."Child1Id", t."Child2Id", t."Child3Id", t."Child4Id", t."Child5Id", t."Child6Id", t."Child7Id", t."Child8Id", t."Child9Id", t."ChildAId", t."ChildBId", t."ChildCId", t."ChildDId", t."ChildEId", t."ChildFId", t."ChildGId", t."ChildHId", t."ChildIId", t."ChildJId", t."ChildKId", t."ChildLId", t."ChildMId", t."ChildNId", t."ChildOId", t."ChildPId", t."ChildQId", t."ChildRId", t."ChildSId", t."ChildTId", t."ChildUId", t."ChildVId", t."ChildWId", t."ChildXId", t."ChildYId", t."ChildZId", t."Name", c."Id", c."Description", c."Name", c0."Id", c0."Description", c0."Name", c1."Id", c1."Description", c1."Name", c2."Id", c2."Description", c2."Name", c3."Id", c3."Description", c3."Name", c4."Id", c4."Description", c4."Name", c5."Id", c5."Description", c5."Name", c6."Id", c6."Description", c6."Name", c7."Id", c7."Description", c7."Name", c8."Id", c8."Description", c8."Name", c9."Id", c9."Description", c9."Name", c10."Id", c10."Description", c10."Name", c11."Id", c11."Description", c11."Name", c12."Id", c12."Description", c12."Name", c13."Id", c13."Description", c13."Name", c14."Id", c14."Description", c14."Name", c15."Id", c15."Description", c15."Name", c16."Id", c16."Description", c16."Name", c17."Id", c17."Description", c17."Name", c18."Id", c18."Description", c18."Name", c19."Id", c19."Description", c19."Name", c20."Id", c20."Description", c20."Name", c21."Id", c21."Description", c21."Name", c22."Id", c22."Description", c22."Name", c23."Id", c23."Description", c23."Name", c24."Id", c24."Description", c24."Name", c25."Id", c25."Description", c25."Name", c26."Id", c26."Description", c26."Name", c27."Id", c27."Description", c27."Name", c28."Id", c28."Description", c28."Name", c29."Id", c29."Description", c29."Name", c30."Id", c30."Description", c30."Name", c31."Id", c31."Description", c31."Name", c32."Id", c32."Description", c32."Name", c33."Id", c33."Description", c33."Name", c34."Id", c34."Description", c34."Name"
  FROM (
      SELECT f."Id", f."Child0Id", f."Child1Id", f."Child2Id", f."Child3Id", f."Child4Id", f."Child5Id", f."Child6Id", f."Child7Id", f."Child8Id", f."Child9Id", f."ChildAId", f."ChildBId", f."ChildCId", f."ChildDId", f."ChildEId", f."ChildFId", f."ChildGId", f."ChildHId", f."ChildIId", f."ChildJId", f."ChildKId", f."ChildLId", f."ChildMId", f."ChildNId", f."ChildOId", f."ChildPId", f."ChildQId", f."ChildRId", f."ChildSId", f."ChildTId", f."ChildUId", f."ChildVId", f."ChildWId", f."ChildXId", f."ChildYId", f."ChildZId", f."Name"
      FROM "Father" AS f
      LIMIT 20 OFFSET 98000
  ) AS t
  LEFT JOIN "Child" AS c ON t."ChildAId" = c."Id"
  LEFT JOIN "Child" AS c0 ON t."ChildBId" = c0."Id"
  LEFT JOIN "Child" AS c1 ON t."ChildCId" = c1."Id"
  LEFT JOIN "Child" AS c2 ON t."ChildDId" = c2."Id"
  LEFT JOIN "Child" AS c3 ON t."ChildEId" = c3."Id"
  LEFT JOIN "Child" AS c4 ON t."ChildFId" = c4."Id"
  LEFT JOIN "Child" AS c5 ON t."ChildGId" = c5."Id"
  LEFT JOIN "Child" AS c6 ON t."ChildHId" = c6."Id"
  LEFT JOIN "Child" AS c7 ON t."ChildIId" = c7."Id"
  LEFT JOIN "Child" AS c8 ON t."ChildJId" = c8."Id"
  LEFT JOIN "Child" AS c9 ON t."ChildKId" = c9."Id"
  LEFT JOIN "Child" AS c10 ON t."ChildLId" = c10."Id"
  LEFT JOIN "Child" AS c11 ON t."ChildMId" = c11."Id"
  LEFT JOIN "Child" AS c12 ON t."ChildNId" = c12."Id"
  LEFT JOIN "Child" AS c13 ON t."ChildOId" = c13."Id"
  LEFT JOIN "Child" AS c14 ON t."ChildPId" = c14."Id"
  LEFT JOIN "Child" AS c15 ON t."ChildQId" = c15."Id"
  LEFT JOIN "Child" AS c16 ON t."ChildRId" = c16."Id"
  LEFT JOIN "Child" AS c17 ON t."ChildSId" = c17."Id"
  LEFT JOIN "Child" AS c18 ON t."ChildTId" = c18."Id"
  LEFT JOIN "Child" AS c19 ON t."ChildUId" = c19."Id"
  LEFT JOIN "Child" AS c20 ON t."ChildVId" = c20."Id"
  LEFT JOIN "Child" AS c21 ON t."ChildWId" = c21."Id"
  LEFT JOIN "Child" AS c22 ON t."ChildXId" = c22."Id"
  LEFT JOIN "Child" AS c23 ON t."ChildYId" = c23."Id"
  LEFT JOIN "Child" AS c24 ON t."ChildZId" = c24."Id"
  LEFT JOIN "Child" AS c25 ON t."Child0Id" = c25."Id"
  LEFT JOIN "Child" AS c26 ON t."Child1Id" = c26."Id"
  LEFT JOIN "Child" AS c27 ON t."Child2Id" = c27."Id"
  LEFT JOIN "Child" AS c28 ON t."Child3Id" = c28."Id"
  LEFT JOIN "Child" AS c29 ON t."Child4Id" = c29."Id"
  LEFT JOIN "Child" AS c30 ON t."Child5Id" = c30."Id"
  LEFT JOIN "Child" AS c31 ON t."Child6Id" = c31."Id"
  LEFT JOIN "Child" AS c32 ON t."Child7Id" = c32."Id"
  LEFT JOIN "Child" AS c33 ON t."Child8Id" = c33."Id"
  LEFT JOIN "Child" AS c34 ON t."Child9Id" = c34."Id"

Query completes in 300ms

SINGLE FATHER BY ID (WITH LIMIT SET BY SINGLEORDEFAULT)

SELECT f."Id", f."Child0Id", f."Child1Id", f."Child2Id", f."Child3Id", f."Child4Id", f."Child5Id", f."Child6Id", f."Child7Id", f."Child8Id", f."Child9Id", f."ChildAId", f."ChildBId", f."ChildCId", f."ChildDId", f."ChildEId", f."ChildFId", f."ChildGId", f."ChildHId", f."ChildIId", f."ChildJId", f."ChildKId", f."ChildLId", f."ChildMId", f."ChildNId", f."ChildOId", f."ChildPId", f."ChildQId", f."ChildRId", f."ChildSId", f."ChildTId", f."ChildUId", f."ChildVId", f."ChildWId", f."ChildXId", f."ChildYId", f."ChildZId", f."Name"
      FROM "Father" AS f
      WHERE f."Id" = 1
      LIMIT 2

Query completes in 115ms

NOW COMES THE PROBLEM: SINGLE FATHER WITH ALL CHILDREN BY ID (WITH LIMIT SET BY SINGLEORDEFAULT)

  SELECT f."Id", f."Child0Id", f."Child1Id", f."Child2Id", f."Child3Id", f."Child4Id", f."Child5Id", f."Child6Id", f."Child7Id", f."Child8Id", f."Child9Id", f."ChildAId", f."ChildBId", f."ChildCId", f."ChildDId", f."ChildEId", f."ChildFId", f."ChildGId", f."ChildHId", f."ChildIId", f."ChildJId", f."ChildKId", f."ChildLId", f."ChildMId", f."ChildNId", f."ChildOId", f."ChildPId", f."ChildQId", f."ChildRId", f."ChildSId", f."ChildTId", f."ChildUId", f."ChildVId", f."ChildWId", f."ChildXId", f."ChildYId", f."ChildZId", f."Name", c."Id", c."Description", c."Name", c0."Id", c0."Description", c0."Name", c1."Id", c1."Description", c1."Name", c2."Id", c2."Description", c2."Name", c3."Id", c3."Description", c3."Name", c4."Id", c4."Description", c4."Name", c5."Id", c5."Description", c5."Name", c6."Id", c6."Description", c6."Name", c7."Id", c7."Description", c7."Name", c8."Id", c8."Description", c8."Name", c9."Id", c9."Description", c9."Name", c10."Id", c10."Description", c10."Name", c11."Id", c11."Description", c11."Name", c12."Id", c12."Description", c12."Name", c13."Id", c13."Description", c13."Name", c14."Id", c14."Description", c14."Name", c15."Id", c15."Description", c15."Name", c16."Id", c16."Description", c16."Name", c17."Id", c17."Description", c17."Name", c18."Id", c18."Description", c18."Name", c19."Id", c19."Description", c19."Name", c20."Id", c20."Description", c20."Name", c21."Id", c21."Description", c21."Name", c22."Id", c22."Description", c22."Name", c23."Id", c23."Description", c23."Name", c24."Id", c24."Description", c24."Name", c25."Id", c25."Description", c25."Name", c26."Id", c26."Description", c26."Name", c27."Id", c27."Description", c27."Name", c28."Id", c28."Description", c28."Name", c29."Id", c29."Description", c29."Name", c30."Id", c30."Description", c30."Name", c31."Id", c31."Description", c31."Name", c32."Id", c32."Description", c32."Name", c33."Id", c33."Description", c33."Name", c34."Id", c34."Description", c34."Name"
  FROM "Father" AS f
  LEFT JOIN "Child" AS c ON f."ChildAId" = c."Id"
  LEFT JOIN "Child" AS c0 ON f."ChildBId" = c0."Id"
  LEFT JOIN "Child" AS c1 ON f."ChildCId" = c1."Id"
  LEFT JOIN "Child" AS c2 ON f."ChildDId" = c2."Id"
  LEFT JOIN "Child" AS c3 ON f."ChildEId" = c3."Id"
  LEFT JOIN "Child" AS c4 ON f."ChildFId" = c4."Id"
  LEFT JOIN "Child" AS c5 ON f."ChildGId" = c5."Id"
  LEFT JOIN "Child" AS c6 ON f."ChildHId" = c6."Id"
  LEFT JOIN "Child" AS c7 ON f."ChildIId" = c7."Id"
  LEFT JOIN "Child" AS c8 ON f."ChildJId" = c8."Id"
  LEFT JOIN "Child" AS c9 ON f."ChildKId" = c9."Id"
  LEFT JOIN "Child" AS c10 ON f."ChildLId" = c10."Id"
  LEFT JOIN "Child" AS c11 ON f."ChildMId" = c11."Id"
  LEFT JOIN "Child" AS c12 ON f."ChildNId" = c12."Id"
  LEFT JOIN "Child" AS c13 ON f."ChildOId" = c13."Id"
  LEFT JOIN "Child" AS c14 ON f."ChildPId" = c14."Id"
  LEFT JOIN "Child" AS c15 ON f."ChildQId" = c15."Id"
  LEFT JOIN "Child" AS c16 ON f."ChildRId" = c16."Id"
  LEFT JOIN "Child" AS c17 ON f."ChildSId" = c17."Id"
  LEFT JOIN "Child" AS c18 ON f."ChildTId" = c18."Id"
  LEFT JOIN "Child" AS c19 ON f."ChildUId" = c19."Id"
  LEFT JOIN "Child" AS c20 ON f."ChildVId" = c20."Id"
  LEFT JOIN "Child" AS c21 ON f."ChildWId" = c21."Id"
  LEFT JOIN "Child" AS c22 ON f."ChildXId" = c22."Id"
  LEFT JOIN "Child" AS c23 ON f."ChildYId" = c23."Id"
  LEFT JOIN "Child" AS c24 ON f."ChildZId" = c24."Id"
  LEFT JOIN "Child" AS c25 ON f."Child0Id" = c25."Id"
  LEFT JOIN "Child" AS c26 ON f."Child1Id" = c26."Id"
  LEFT JOIN "Child" AS c27 ON f."Child2Id" = c27."Id"
  LEFT JOIN "Child" AS c28 ON f."Child3Id" = c28."Id"
  LEFT JOIN "Child" AS c29 ON f."Child4Id" = c29."Id"
  LEFT JOIN "Child" AS c30 ON f."Child5Id" = c30."Id"
  LEFT JOIN "Child" AS c31 ON f."Child6Id" = c31."Id"
  LEFT JOIN "Child" AS c32 ON f."Child7Id" = c32."Id"
  LEFT JOIN "Child" AS c33 ON f."Child8Id" = c33."Id"
  LEFT JOIN "Child" AS c34 ON f."Child9Id" = c34."Id"
  WHERE f."Id" = 1
  LIMIT 2

Query completes in MORE THAN TWO SECONDS! 2300ms

Can someone explain me why and how to optimize this query? I have indexes on all PKs and FKs.

Does this answer your question? Why would adding LIMIT 200 cause a query to slow down? — John K. N., Mar 21 '24 at 11:44
Welcome to the DBA.SE community. Please have a look at some of the search results for [postgresql] limit order by slow. — John K. N., Mar 21 '24 at 11:46
Yes, I've read the other posts, but I've found nothing similar to my case — Alessandro, Mar 21 '24 at 11:48
Please add the EXPLAIN ANALYZE .... output for each SELECT statement in your question (via the [edit] link). It can help pinpoint issues. — John K. N., Mar 21 '24 at 12:24
What is the reason for that peculiar structure? Why not use arrays, lists, link tables?... — bobflux, Mar 21 '24 at 21:28
@bobflux I can constraint ChildAId on table Father is not null, but how can I be sure there is a corresponding ChildA in a linked table Children? — Alessandro, Mar 22 '24 at 07:28
OK, that's a reason, but if it can't be null and the child row must exist, why left join? Can't say more about the query until you post explain analyze like asked above. Please put it on https://explain.depesz.com/ and share the link. — bobflux, Mar 22 '24 at 07:59
@bobflux some children can be null, while other not. Query plan: https://explain.depesz.com/s/O4nT — Alessandro, Mar 22 '24 at 11:35
All the time (2.278s) is in the planning, execution takes 1.2ms. It's weird. I tested it on my computer and it runs in 10ms including planning. What's your postgresql version? — bobflux, Mar 22 '24 at 12:11
I've tried on the latest version. I'll add that option and let you know. — Alessandro, Mar 23 '24 at 13:05

score 1 · Accepted Answer · answered Mar 21 '24 at 18:55

Intuitively, having ~36 joins is a bit hard to reason on WRT performance. All the same, the LIMIT 2 term is deceptive as it will likely render across the entire 1:n join before returning the first 2

As a different approach, let's try:

take any query on fathers, and for each father record, create a JSON object of that row. ie for each father
Use JSON_EACH to traverse the father row for all values that do NOT come from the ID or name fields. ie for any child
JOIN to children for each of the children IDs that we produced in step 2.

All together, I got:

WITH 
-- Query, with whatever limits, the father table
-- for each father, jsonify the father object
dad AS (SELECT to_json(father.*) AS father_obj, * FROM father)
SELECT *
FROM ((SELECT dad.*, mapkey.* 
       -- now explode each father object into a row for each child ID
       FROM dad, json_each(dad.father_obj) AS mapkey 
       -- The list of field names that do NOT contain child IDs
       WHERE key::TEXT NOT IN ('id', 'Name'))) as childIDs
-- Join children on each of the IDs + JSON coersion -> INTEGER
INNER JOIN children ON children.child_id = value::TEXT::INTEGER;

father_obj	father_id	childAId	childBId	childCId	childDId	key	value	child_id	v1
{"father_id":1,"childAId":1,"childBId":2,"childCId":3,"childDId":4}	1	1	2	3	4	childAId	1	1	child1
{"father_id":1,"childAId":1,"childBId":2,"childCId":3,"childDId":4}	1	1	2	3	4	childBId	2	2	child2
{"father_id":1,"childAId":1,"childBId":2,"childCId":3,"childDId":4}	1	1	2	3	4	childCId	3	3	child3
{"father_id":1,"childAId":1,"childBId":2,"childCId":3,"childDId":4}	1	1	2	3	4	childDId	4	4	child4
{"father_id":2,"childAId":5,"childBId":6,"childCId":7,"childDId":8}	2	5	6	7	8	childAId	5	5	child5
{"father_id":2,"childAId":5,"childBId":6,"childCId":7,"childDId":8}	2	5	6	7	8	childBId	6	6	child6
{"father_id":2,"childAId":5,"childBId":6,"childCId":7,"childDId":8}	2	5	6	7	8	childCId	7	7	child7
{"father_id":2,"childAId":5,"childBId":6,"childCId":7,"childDId":8}	2	5	6	7	8	childDId	8	8	child8

Note:

I updated the Id field of the children table to be child_id for clarity; so too with the father_id field.
You should be able to substitute an condition on the father table in the CTE/WITH statement
Please try your queries and the query above, and try prefixing EXPLAIN ANALYZE before the SELECT keyword, and post back your results.

The dissection of the row into the JSON format is a little odd, but would give your a path to exploding the child IDs, doing 1, single JOIN, and an easy query for the planner to resolve via simple indexes

Thanks for your kind answer. What I don't understand is why LIMIT 20 OFFSET 98000 is fine and LIMIT 2 not... by the way I have to express that query using Entity Framework, and I don't think it's possible. — Alessandro, Mar 22 '24 at 07:29
Understood. Without familiarity with entity framework, my "optimization" path would be the same: for each row, collect all child IDs and join once.
How is the table indexed? How are the column indices ordered? can you provide a query plan - ie. Replace SELECT in your query with EXPLAIN ANALYZE SELECT and post back the plan & realization results? — Jeff Vermeer, Mar 22 '24 at 15:40
Out of interest, what was the query plans that EXPLAIN ANALYZE SELECT produced? — Jeff Vermeer, Mar 26 '24 at 14:19
Interesting - 1.245 ms and all index scans... how many rows are returned when the query takes 2 seconds v. 1ms? — Jeff Vermeer, Mar 27 '24 at 02:50
Sure - one row - but how many joins are actually being fulfilled. Note that using LEFT JOIN will of course allow NULL on the right side of a join - so what I am trying to ask is - how many of those JOINs do NOT return NULL on the right side, between runtimes? — Jeff Vermeer, Mar 27 '24 at 14:41

Why is this PostgreSQL query with LIMIT so slow?

1 Answers1