Why some rows are missing in my recursive CTE?

These are my 2 tables id_hierarchy and hierarchy_link:

CREATE TABLE id_hierarchy
(
    id integer NOT NULL,
    hierarchy integer
);
insert into id_hierarchy values (11,2),(22,3),(44,5),(77,8),(170,11),
(190,13),(240,18),(255,20);

CREATE TABLE hierarchy_link
(
    hid integer NOT NULL,
    parent_hid integer
);
insert into hierarchy_link values (1,0),(2,1),(3,2),(5,3),(8,5),(11,8),
(13,11),(15,13),(18,15),(20,18);

With id_hierarchy.hierarchy=hierarchy_link.hid

For the below CTE query:

with recursive rt1 as(
    select id,hid,parent_hid||'->'||hid as str 
    from rt2 
    where rt2.parent_hid=1
    union
    select t.id,t.hid,s.str||'->'||t.hid as str 
    from rt2 t 
    inner join rt1 s on (s.hid=t.parent_hid)
),
rt2 as (
    select id, hid, parent_hid, hierarchy 
    from hierarchy_link h 
    inner join id_hierarchy u on (u.hierarchy=h.hid)
)
select id, hid, str as hierarchy 
from rt1 
order by 1

I am getting this result:

id;  hid; hierarchy
11;  2;   "1->2"
22;  3;   "1->2->3"
44;  5;   "1->2->3->5"
77;  8;   "1->2->3->5->8"
170; 11;  "1->2->3->5->8->11"
190; 13;  "1->2->3->5->8->11->13"

Rows 240,18 and 255,20 are missing from id_hierarchy.

Where is my mistake?

If we slice your query, the first cte (rt2) returns this:

id   hid     parent_hid  hierarchy
11    2         1            2
22    3         2            3
44    5         3            5
77    8         5            8
170  11         8           11
190  13         11          13
240  18         15          18
255  20         18          20

The first SELECT ([root]) in the second cte (rt1) returns this:

id   hid     parent_hid  hierarchy
11    2         1            2

This is indeed the only row with parent_hid = 1. The recursive CTE starts with this single value and goes all the way down the hierarchy until there is no match anymore.

From this, the second SELECT recursively joins rt2 with rt1 on rt1.hid = rt2.parent_id:

id   hid     parent_hid  hierarchy
11    2         1            2 -+                1->2                   => start 
22    3         2            3 -+ -+             1->2->3                => previous + 3
44    5         3            5    -+ -+          1->2->3->5             => previous + 5
77    8         5            8       -+ -+       1->2->3->5->8          => previous + 8
170  11         8           11          -+ -+    1->2->3->5->8->11      => previous + 11
190  13         11          13             -+    1->2->3->5->8->11->13  => breaks here
240  18         15          18
255  20         18          20

It breaks on 190 because there is no match on parent_hid = 13 where hid = 13 (row for id = 190).

It breaks because your are only looking for hierarchy starting with a root at 1.

I am not sure what your expected output should be but if you are looking for hierarchies with no parent (i.e. parent_hid not in hid [the root]), you will also get the hierarchy 15->18->20.

Replace where rt2.parent_hid=1 by WHERE NOT EXISTS (SELECT 1 FROM rt2 WHERE hid = r.parent_hid) and starting roots will be:

id  hid hierarchy
11  2   1->2
240 18  15->18

And output will be:

id  hid hierarchy
11  2   1->2
22  3   1->2->3
44  5   1->2->3->5
77  8   1->2->3->5->8
170 11  1->2->3->5->8->11
190 13  1->2->3->5->8->11->13
240 18  15->18
255 20  15->18->20

It seems that only hierarchy_link is needed to built up the hierarchy. Therefore rt2 should be remove:

;WITH rt1 AS (
    SELECT hid, parent_hid, CAST(parent_hid as varchar(50)) + '->' + CAST(hid as varchar(50)) as [str] 
    FROM hierarchy_link r
    WHERE r.parent_hid = 1
    UNION ALL
    SELECT l.hid, l.parent_hid, CAST(r.[str] as varchar(50)) + '->' + CAST(l.hid as varchar(50)) as [str] 
    FROM hierarchy_link l
    INNER JOIN rt1 r ON r.hid = l.parent_hid
)
SELECT h.id, r.hid, r.[str] as hierarchy 
FROM rt1 r
INNER JOIN id_hierarchy h ON h.hierarchy = r.hid;

The id from id_hierarchy is only added at the end once the hierarchy from rt1 is ready:

id  hid hierarchy
11  2   1->2
22  3   1->2->3
44  5   1->2->3->5
77  8   1->2->3->5->8
170 11  1->2->3->5->8->11
190 13  1->2->3->5->8->11->13
240 18  1->2->3->5->8->11->13->15->18
255 20  1->2->3->5->8->11->13->15->18->20

StackExchange Database Administrators Q#144429, answer score: 6