Skip to content

Instantly share code, notes, and snippets.

@niwinz
Created September 27, 2022 12:18
Show Gist options
  • Save niwinz/5348541e6ec7714e1cae2988b61fc6b9 to your computer and use it in GitHub Desktop.
Save niwinz/5348541e6ec7714e1cae2988b61fc6b9 to your computer and use it in GitHub Desktop.
Linked List in PostgreSQL (using recursive queries)
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;
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment