Why does a query take so much longer for 1 additional identical join?

Question

I am trying to figure out why with the query below, adding the last join takes so much longer.

If I run it with the last join commented out ( level 3) it runs in less than a second. Adding the 3rd join in it takes 20+ seconds.

It appears that the last join uses materialize rather than a nested loop left join but why? Doing this adds a significant amount of time.

Query

select   
   t4.head_id
from 
   table_links t4
left join -- level 1
   table_links t5 on t5.head_id = t4.tail_id and t5.linkdef_id = -10 and t5.latest = 1
left join -- level 2
   table_links t6 on t6.head_id = t5.tail_id and  t6.linkdef_id = -10 AND t6.latest = 1
left join -- level 3
   table_links t7 on t7.head_id = t6.tail_id and t7.linkdef_id = -10 AND t7.latest = 1          
where 
   t4.head_id = '1141399'::integer and t4.linkdef_id = -10 AND t4.latest = 1  

System Version

PostgreSQL 9.5.17 on x86_64-pc-linux-gnu, compiled by gcc (GCC) 4.8.5 20150623 (Red Hat 4.8.5-36), 64-bit

Table and index definition

CREATE TABLE public.table_links
(
    link_id integer NOT NULL,
    linkdef_id integer NOT NULL,
    hierarchical integer,
    latest integer NOT NULL,
    version integer NOT NULL,
    suppressed integer NOT NULL,
    version_mode integer,
    head_id integer NOT NULL,
    tail_id integer NOT NULL,
    orig_tail_name character varying(64) COLLATE pg_catalog."default"
)
WITH (
    OIDS = FALSE
)
TABLESPACE pg_default;



CREATE INDEX idx_table_links
    ON public.table_links USING btree
    (head_id)
    TABLESPACE pg_default    WHERE linkdef_id = '-10'::integer AND latest = 1
;

Explain Analyze

Depesz link

"Merge Left Join  (cost=925531.10..1076126.36 rows=9095384 width=4) (actual time=16950.609..20162.688 rows=513 loops=1)"
"  Merge Cond: (t6.tail_id = t7.head_id)"
"  ->  Sort  (cost=53175.43..53587.15 rows=164689 width=8) (actual time=31.134..31.230 rows=335 loops=1)"
"        Sort Key: t6.tail_id"
"        Sort Method: quicksort  Memory: 40kB"
"        ->  Nested Loop Left Join  (cost=1.30..38905.64 rows=164689 width=8) (actual time=1.331..30.969 rows=335 loops=1)"
"              ->  Nested Loop Left Join  (cost=0.86..1124.63 rows=2982 width=8) (actual time=0.760..6.643 rows=125 loops=1)"
"                    ->  Index Scan using idx_table_links on table_links t4  (cost=0.43..19.80 rows=54 width=8) (actual time=0.404..0.411 rows=13 loops=1)"
"                          Index Cond: (head_id = 1141399)"
"                    ->  Index Scan using idx_table_links on table_links t5  (cost=0.43..19.91 rows=55 width=8) (actual time=0.403..0.474 rows=9 loops=13)"
"                          Index Cond: (head_id = t4.tail_id)"
"              ->  Index Scan using idx_table_links on table_links t6  (cost=0.43..12.12 rows=55 width=8) (actual time=0.173..0.192 rows=2 loops=125)"
"                    Index Cond: (head_id = t5.tail_id)"
"  ->  Materialize  (cost=872355.67..899037.78 rows=5336422 width=4) (actual time=16640.144..19616.065 rows=5816034 loops=1)"
"        ->  Sort  (cost=872355.67..885696.72 rows=5336422 width=4) (actual time=16640.141..19079.265 rows=5816012 loops=1)"
"              Sort Key: t7.head_id"
"              Sort Method: external merge  Disk: 81168kB"
"              ->  Bitmap Heap Scan on table_links t7  (cost=44115.15..233344.48 rows=5336422 width=4) (actual time=681.658..7882.374 rows=5935232 loops=1)"
"                    Recheck Cond: ((linkdef_id = '-10'::integer) AND (latest = 1))"
"                    Heap Blocks: exact=101723"
"                    ->  Bitmap Index Scan on idx_table_links  (cost=0.00..42781.04 rows=5336422 width=0) (actual time=658.355..658.355 rows=5935232 loops=1)"
"Planning time: 1.496 ms"
"Execution time: 20173.394 ms"

UPDATE

Adding the index requested by @LuisAlbertoBarandiaran decreased the time to 2 seconds which is fabulous but I do wonder why it still isn't the same.

Added this index

CREATE INDEX idx_table_links2 ON public.table_links USING btree (head_id, tail_id, linkdef_id, latest ) TABLESPACE pg_default ;

Explain Analyze

Depesz link

"Merge Left Join  (cost=26338.58..398495.40 rows=9095384 width=4) (actual time=175.809..2034.940 rows=513 loops=1)"
"  Merge Cond: (t6.tail_id = t7.head_id)"
"  ->  Sort  (cost=26338.02..26749.75 rows=164689 width=8) (actual time=0.405..0.480 rows=335 loops=1)"
"        Sort Key: t6.tail_id"
"        Sort Method: quicksort  Memory: 40kB"
"        ->  Nested Loop Left Join  (cost=1.68..12068.23 rows=164689 width=8) (actual time=0.015..0.370 rows=335 loops=1)"
"              ->  Nested Loop Left Join  (cost=1.12..241.95 rows=2982 width=8) (actual time=0.012..0.069 rows=125 loops=1)"
"                    ->  Index Only Scan using idx_table_links2 on table_links  t4  (cost=0.56..3.81 rows=54 width=8) (actual time=0.006..0.007 rows=13 loops=1)"
"                          Index Cond: ((head_id = 1141399) AND (linkdef_id = '-10'::integer) AND (latest = 1))"
"                          Heap Fetches: 0"
"                    ->  Index Only Scan using idx_table_links2 on table_links  t5  (cost=0.56..3.86 rows=55 width=8) (actual time=0.003..0.004 rows=9 loops=13)"
"                          Index Cond: ((head_id = t4.tail_id) AND (linkdef_id = '-10'::integer) AND (latest = 1))"
"                          Heap Fetches: 0"
"              ->  Index Only Scan using idx_table_links2 on table_links  t6  (cost=0.56..3.42 rows=55 width=8) (actual time=0.002..0.002 rows=2 loops=125)"
"                    Index Cond: ((head_id = t5.tail_id) AND (linkdef_id = '-10'::integer) AND (latest = 1))"
"                    Heap Fetches: 0"
"  ->  Materialize  (cost=0.56..248244.23 rows=5336422 width=4) (actual time=0.012..1537.433 rows=5816034 loops=1)"
"        ->  Index Only Scan using idx_table_links2 on table_links  t7  (cost=0.56..234903.17 rows=5336422 width=4) (actual time=0.012..874.000 rows=5816012 loops=1)"
"              Index Cond: ((linkdef_id = '-10'::integer) AND (latest = 1))"
"              Heap Fetches: 0"
"Planning time: 0.737 ms"
"Execution time: 2035.066 ms"

Answer 1

The following index should reduce your query time:

CREATE INDEX idx_table_links2 ON public.table_links 
USING btree (head_id, tail_id, linkdef_id, latest ) TABLESPACE pg_default ;

The reason why your query is taking more time, it's because you are joining each "level" with an ID computed from the previous one, and thus increasing the calculation needed to get a result.

So Level1 computes for around 50+ rows, Level2 increases to 300+ or so rows, while Level3 shoots this to 5,3+ Million rows (and that's why it takes so much time).

Answer 2

The planner thinks that every successive join is going to fan out by 55 fold, but the reality is much lower than that. By the time it gets to the last join, it thinks it would need to probe the index 164689 times (but really only 335 times) in order to find 9095384 tuples (but really only 513 tuples). At that scale, it thinks processing the table wholesale will be faster than doing it retail.

Why it is so wrong is hard to say. Maybe things with latest=1 are selectively depleted in things with linkdef_id = -10, but the planner assumes those conditions are independent. Or maybe most of your linked lists (or trees, whatever those things are representing) are short, meaning that "tail_id" is more likely to be NULL the further down the join tree you are, something the planner would also have a hard time estimating. It is also possible that the planner is correct in general, but the specific chain starting with 1141399 is just unusual in having a low fan out factor. If you are really curious, you can play around with you data a bit to see which of these is likely to be the case. If you identify it, you might be able to collect some custom statistics (CREATE STATISTICS) to fix it, but you would have to upgrade your version as those were not introduced until v10.

If you want to force it away from the current plan, you can set enable_mergejoin=off and re-run the query to see what it chooses then. Note you mention "materialize" a few times. The merge join is really the meat of the issue, the "materialize" is just a minor accouterment to that.

---

Note that the index you are using is not optimal. "tail_id" is not part of any of your index conditions, and having it as the second column makes the columns after less useful. (They are still usable as an internal filter, but can't jump to the specific part of the index where it knows those will be satisfied, so they are useful but much less useful than they could be. Unfortunately the reported execution plan does not distinguish between these two types of usability.) You still want "tail_id" in the index to support index-only scans, but want it as the end of the column list so it doesn't spoil the selectivity of the other ones:

create index on table_links (head_id, linkdef_id, latest, tail_id ) 

This won't make a huge difference, because is it not the bottleneck, but is probably worth changing.

But that probably still isn't optimal. The scan over t7 in your last shown execution plan can't make best use of that index, because it is using head_id to get ordering, which means it can't jump to the part of the index that satisfies linkdef_id and latest conditions but has to internally filter on them instead. Re-ordering it this way would best satisfy all the index usages shows in your last plan:

create index on table_links (linkdef_id, latest, head_id, tail_id ) 

Or even more tailored to your specific query:

create index on table_links (head_id, tail_id ) where linkdef_id = -10 AND latest = 1

But of course the last one is only useful if the constants -10 and 1 don't get changed from those values.