Linked list

PostgreSQL Optimize: Linked list Pagination

Video playlist linked list

Create the video playlist table with the linked-list structure

CREATE TABLE public.video_playlist (
	id varchar(100) NOT NULL,
	previous_id varchar(100) NULL,
	next_id varchar(100) NULL,
	user_id varchar(100) NULL,
	group_id varchar(100) NULL,
	"content" varchar(100) NULL,
	created_at timestamptz NULL,
	updated_at timestamptz NULL,
	CONSTRAINT video_playlist_pk PRIMARY KEY (id),
	CONSTRAINT video_playlist_fk FOREIGN KEY (previous_id) REFERENCES public.video_playlist(id),
	CONSTRAINT video_playlist_fk_1 FOREIGN KEY (next_id) REFERENCES public.video_playlist(id)
);
CREATE INDEX video_playlist_next_id_idx ON public.video_playlist USING btree (next_id);
CREATE INDEX video_playlist_previoud_id_idx ON public.video_playlist USING btree (previous_id);

Get the playlist from the first item

We can define the recursive temporary playlist table and start with the first item (null previous_id).

WHERE previous_id IS NULL

Then let the next playlist id equal previous playlist next_id to finish this recursive linked-list playlist;

JOIN video_ordered_playlist_from_first_node pl ON nl.id = pl.next_id

Then run the SQL to this ORDERED temporary playlist table with the specific user_id and the playlist group_id to get the user’s specific playlist (group_id) from the first item.

WITH RECURSIVE video_ordered_playlist_from_first_node AS (
  SELECT id, previous_id, next_id, content, user_id, group_id
  FROM video_playlist
  WHERE previous_id IS NULL
  UNION ALL
  SELECT nl.id, nl.previous_id, nl.next_id, nl.content, nl.user_id, nl.group_id
  FROM video_playlist nl
  JOIN video_ordered_playlist_from_first_node pl ON nl.id = pl.next_id
)

SELECT *
FROM video_ordered_playlist_from_first_node
WHERE
  user_id = 'u-1111'
  group_id = 'g-2222'

You can also add the OFFSET and LIMIT to get the pagination from this ORDERED temporary playlist table

SELECT *
FROM video_ordered_playlist_from_first_node
WHERE
  user_id = 'u-1111'
  group_id = 'g-2222'
OFFSET 10 LIMIT 10

Get the playlist from the last item

We can define the recursive temporary playlist table and start with the last item (null next_id).

WHERE next_id IS NULL

Then let the previous playlist id equal next playlist previous_id to finish this recursive linked-list playlist;

JOIN video_ordered_playlist_from_last_node pl ON pl.id = nl.previoud_id

Then run the SQL to this REVERSE ORDERED temporary playlist table with the specific user_id and the playlist group_id to get the user’s specific playlist (group_id) from the first item.

WITH RECURSIVE video_ordered_playlist_from_last_node AS (
  SELECT id, previous_id, next_id, content, user_id, group_id
  FROM video_playlist
  WHERE next_id IS NULL
  UNION ALL
  SELECT pl.id, pl.previous_id, pl.next_id, pl.content, pl.user_id, pl.group_id
  FROM video_playlist pl
  JOIN video_ordered_playlist_from_last_node pl ON pl.id = nl.previoud_id
)

SELECT *
FROM video_ordered_playlist_from_last_node
WHERE
  user_id = 'u-1111'
  group_id = 'g-2222'

You can also add the OFFSET and LIMIT to get the pagination from this REVERSE ORDERED temporary playlist table

SELECT *
FROM video_ordered_playlist_from_last_node
WHERE
  user_id = 'u-1111'
  group_id = 'g-2222'
OFFSET 10 LIMIT 10

Reference