Linked List in PostgreSQL (using recursive queries)

test.sql

DROP TABLE task;
CREATE TABLE task (id bigint not null, parent_id bigint null);

-- Create many unrelated linked lists in the same table

INSERT INTO task values (1, null);
INSERT INTO task (id, parent_id)
  SELECT i, i-1 FROM generate_series(2, 50000) AS t(i);

INSERT INTO task values (50001, null);
INSERT INTO task (id, parent_id)
  SELECT i, i-1 FROM generate_series(50002, 100000) AS t(i);

INSERT INTO task values (100001, null);
INSERT INTO task (id, parent_id)
  SELECT i, i-1 FROM generate_series(100002, 150000) AS t(i);

INSERT INTO task values (150001, null);
INSERT INTO task (id, parent_id)
  SELECT i, i-1 FROM generate_series(150002, 200000) AS t(i);

INSERT INTO task values (200001, null);
INSERT INTO task (id, parent_id)
  SELECT i, i-1 FROM generate_series(200002, 250000) AS t(i);

CREATE INDEX ON task(parent_id, id);

-- Example query for a single linked list

WITH RECURSIVE tasks AS (
  SELECT *, 1 AS depth
    FROM task
   WHERE parent_id IS NULL AND id = 150001
  UNION ALL
  SELECT t.*, ts.depth + 1 AS depth
    FROM task AS t
    JOIN tasks AS ts ON (ts.id = t.parent_id)
)
SELECT * FROM tasks ORDER BY depth DESC LIMIT 1000;