What is the recommended way to join junction tables for efficient ordering/pagination?

Question

Summary: I have a simple database schema but even with just a few 10's of thousands of records the performance on basic queries is already becoming a problem.

Database: PostgreSQL 9.6

Simplified schema:

CREATE TABLE article (
  id bigint PRIMARY KEY,
  title text NOT NULL,
  score int NOT NULL
);
CREATE TABLE tag (
  id bigint PRIMARY KEY,
  name text NOT NULL
);
CREATE TABLE article_tag (
  article_id bigint NOT NULL REFERENCES article (id),
  tag_id bigint NOT NULL REFERENCES tag (id),
  PRIMARY KEY (article_id, tag_id)
);
CREATE INDEX ON article (score);

Production data info:

All tables are read/write. Low write volume, only a new record every couple minutes or so.

Approximate record counts:

• ~66K articles
• ~63K tags
• ~147K article_tags

Average of 5 tags per article.

Question: I want to create a view article_tags which includes an array of tags for every article record, can be ordered by article.score and paginated with or without additional filtering.

In my first attempt I was surprised to see that the query took ~350 ms to execute and wasn't using the indexes. In subsequent attempts I was able to get it down to ~5 ms but I don't understand what is going on. I would expect all these queries to take the same amount of time. What crucial concept am I missing here?

Attempts (SQL Fiddles):

1. multi-table joins (~350 ms), (~5 ms if ordered by article.id!) -- seemed like the most natural solution
2. subquery join (~300 ms) -- also seemed like a natural solution
3. limited subquery join (~5 ms) -- super awkward, can't be used for view
4. lateral join (~5 ms) -- is this really what I should be using? seems like a misuse of lateral
5. ...something else?

Answer 1

Pagination

For pagination, LIMIT (and OFFSET) are simple, but typically inefficient tools for bigger tables. Your tests with LIMIT 10 only show the tip of the iceberg. Performance is going to degrade with a growing OFFSET, no matter which query you choose.

If you have no or little concurrent write access, the superior solution is a MATERIALIZED VIEW with an added row number, plus index on that. And all your queries select rows by row numbers.

Under concurrent write load, such a MV is outdated quickly (But a compromise like refreshing the MV CONCURRENTLY every N minutes may be acceptable).
LIMIT / OFFSET is not going to work properly at all since "the next page" is a moving target there, and LIMIT / OFFSET cannot cope with that. The best technique depends on undisclosed information.

Related:

• Database engine with counting b-trees for efficient paging support
• Optimize query with OFFSET on large table

Index

Your indexes generally look good. But your comment indicates that table tag has many rows. Typically, there is very little write load on a table like tag, which is perfect for index-only support. So add a multicolumn ("covering") index:

CREATE INDEX ON tag(id, name);

Related:

• Can Postgres use an index-only scan for this query with joined tables?

Just the top N rows

If you don't actually need more pages (which isn't strictly "paging"), then any query style is good that reduces qualifying rows from article before retrieving details from the related tables (expensively). Your "limited subquery" (3.) and "lateral join" (4.) solutions are good. But you can do better:

Use an ARRAY constructor for the LATERAL variant:

SELECT a.id, a.title, a.score, tags.names
FROM   article a
LEFT   JOIN LATERAL (
   SELECT ARRAY (
      SELECT t.name
      FROM   article_tag a_t 
      JOIN   tag t ON t.id = a_t.tag_id
      WHERE  a_t.article_id = a.id
   -- ORDER  BY t.id  -- optionally sort array elements
      )
  ) AS tags(names) ON true
ORDER  BY a.score DESC
LIMIT  10;

The LATERAL subquery assembles tags for a single article_id at a time, so GROUP BY article_id is redundant, as well as the join condition ON tags.article_id = article.id, and a basic ARRAY constructor is cheaper than array_agg(tag.name) for the remaining simple case.

• Why is array_agg() slower than the non-aggregate ARRAY() constructor?

Or use a lowly correlated subquery, typically even faster, yet:

SELECT a.id, a.title, a.score
     , ARRAY (
         SELECT t.name
         FROM   article_tag a_t 
         JOIN   tag t ON t.id = a_t.tag_id
         WHERE  a_t.article_id = a.id
      -- ORDER  BY t.id  -- optionally sort array elements
      ) AS names
FROM   article a
ORDER  BY a.score DESC
LIMIT  10;

db<>fiddle here
SQL Fiddle