Keyset pagination and fuzzy search in PostgreSQL

Almost every app has a list you can page through and search. The usual way to build one is LIMIT ... OFFSET for paging and ILIKE '%term%' for search. Both work fine on small tables. Both break in predictable ways as the data grows.

Paging gets slower the deeper you go. Search finds nothing if the user gets a single letter wrong.

This post explains why both problems happen and which PostgreSQL features fix them. For paging, that's keyset pagination with a matching index. For search, it's trigram similarity from the pg_trgm extension. I'll also cover one connection-pool trap that makes fuzzy search behave inconsistently.

Why OFFSET gets slower with every page

Take a simple table and a typical paged query:

SELECT id, name
FROM customers
ORDER BY name, id
LIMIT 25 OFFSET 5000;

It reads like "jump to row 5,000 and return 25". But PostgreSQL has no way to jump. An index on (name, id) lets it read rows in order. It still has to step through the first 5,000 entries one by one and throw them away before it can return your 25. Without a usable index it's worse: it sorts every matching row first.

So the cost of a page grows with OFFSET + LIMIT, not just LIMIT. Page 1 is cheap. Page 20 does twenty times the work, and page 200 does two hundred times the work. The query plan isn't broken. The work is built into the question.

OFFSET has a correctness problem too. If a row is added or deleted between two page requests, every later row shifts by one. The user sees a duplicate at the top of the next page, or quietly misses a row.

Keyset pagination

Keyset pagination (also called cursor or seek pagination) changes the question. Instead of "skip N rows", you ask for "the rows that come after the last one I saw". The client keeps the sort key of the last row on the current page and sends it back:

SELECT id, name
FROM customers
WHERE (name, id) > ($1, $2)   -- last row of the previous page
ORDER BY name, id
LIMIT 25;

The (name, id) > ($1, $2) form is a row-value comparison. PostgreSQL compares the pairs in dictionary order: first by name, and by id only when the names are equal. That's exactly the order of ORDER BY name, id. This is why the two must match column for column.

With a btree index (the standard sorted index) on (name, id), the database jumps straight to the cursor position in the index and reads the next 25 entries. It never touches the rows before the cursor. So every page costs about the same, however deep it is.

Three rules make keyset pagination correct and fast:

1. 1.The sort key must be unique. If two rows can share a name, add a unique column such as id as a tiebreaker. Otherwise rows that tie at a page boundary get skipped or repeated.
2. 2.The index must match the ORDER BY exactly: same columns, same order, same direction.
3. 3.Expressions count. If you sort by lower(name), an index on name won't help. You need an expression index on lower(name).

CREATE INDEX customers_name_lower_id ON customers (lower(name), id);

SELECT id, name
FROM customers
WHERE (lower(name), id) > (lower($1), $2)
ORDER BY lower(name), id
LIMIT 25;

The trade-off is that you can't jump to an arbitrary page number. You get "next", and "previous" if you flip the comparison and the sort. For infinite scroll, map lists and API cursors, that's what you want anyway.

Things that quietly force a full sort

Even with a cursor, some things make PostgreSQL sort everything before it can return the first row.

DISTINCT ON (col) keeps one row per group. To do that, it needs the input sorted by the distinct key first. If that key differs from your ORDER BY, PostgreSQL sorts the whole result once to remove duplicates, then again to order it.

Before you use DISTINCT ON in a paged query, check whether a plain filter says the same thing. For example: "only the primary record of each group".

The other common cause is an index that can find rows but can't order them. That brings us to search.

Why ILIKE fails on typos

name ILIKE '%term%' is all or nothing. Either the term is a substring or it isn't. A user who types "Riversde" will never find "Riverside". To handle typos, you need a way to measure how close two strings are.

pg_trgm gives you one. It splits text into trigrams: the three-character sequences in a string, padded with spaces at word edges. Then it measures how many trigrams two strings share. "Riverside" and "Riversde" share most of theirs, so they count as similar even though neither contains the other.

CREATE EXTENSION IF NOT EXISTS pg_trgm;
CREATE INDEX customers_name_trgm ON customers USING gin (lower(name) gin_trgm_ops);

A GIN trigram index stores, for each trigram, the rows that contain it. So it's very good at answering "which rows share enough trigrams with this query". It can also speed up ILIKE '%term%'.

What it can't do is return rows in any order. It has no idea of alphabetical position or score. Matching and ordering are different jobs. A list that's both searched and sorted usually needs a btree for the order and a GIN index for the match.

similarity, word_similarity and the %> operator

pg_trgm offers several comparisons. Picking the wrong one gives poor results.

Whole-string similarity() is a poor fit for search. Users type short queries, and names are often long. Compare a short query with a long name and you get a low score, even when the name contains the query word exactly. That's because most of the long name's trigrams have no match in the query. Correct matches end up ranked below noise.

word_similarity(query, text) asks how well the query matches some continuous part of the text. That's what a person searching actually means. Its operator form, text %> query, returns true when the score clears a threshold. And that operator can be answered from the GIN index.

In practice, you filter with the operator and rank with the function:

SELECT id, name
FROM customers
WHERE lower(name) ILIKE '%' || lower($1) || '%'
   OR lower(name) %> lower($1)
ORDER BY
    (lower(name) ILIKE '%' || lower($1) || '%') DESC,  -- exact substring first
    word_similarity(lower($1), lower(name)) DESC
LIMIT 25;

Exact substring matches come first, so someone who types a name correctly sees it at the top. Fuzzy matches follow, closest first. The ranking only scores rows the index has already picked.

Thresholds are session settings

%> compares against pg_trgm.word_similarity_threshold, which defaults to 0.6. That's strict, and you'll usually want something lower. The catch is that it's a session setting. It applies to one database connection, not to the whole database.

Apps rarely use one connection. They use a pool, which opens connections over time and hands a different one to each request. Running SET pg_trgm.word_similarity_threshold = 0.3 once only changes the connection that ran it. Every other connection, and every one opened later, stays at 0.6.

Search then behaves differently depending on which connection a request happens to get. That's very hard to debug.

The fix is to apply session settings whenever a connection is created. In Go with pgx, that's the pool's AfterConnect hook:

cfg.AfterConnect = func(ctx context.Context, conn *pgx.Conn) error {
    _, err := conn.Exec(ctx, "SET pg_trgm.word_similarity_threshold = 0.3")
    return err
}

You can also use ALTER ROLE app_user SET pg_trgm.word_similarity_threshold = 0.3, or the same at database level. Both apply to every new session. Whichever you pick, make it part of connection setup, not something a request does.

Choosing a threshold by testing

The threshold is a trade-off. Too strict, and real typos find nothing. Too loose, and random input starts matching unrelated rows. Don't guess. Build a small test set:

1. 1.Collect real misspellings of names in your data, ideally from search logs.
2. 2.Add nonsense strings that should match nothing.
3. 3.Run the search at a few thresholds and count hits on both sets.
4. 4.Pick the loosest threshold that still returns nothing for the nonsense.

Where I ran into this

At work, an admin map groups about 55,000 locations into grid cells. Clicking a marker opens a paged, searchable, alphabetical list of the locations in that cell. Two things were wrong with that list.

Paging used OFFSET and DISTINCT ON. The DISTINCT ON gave one row per building, since duplicates are merged with a merged_into_id column. The only index on the name was a trigram GIN index, which can't order. Page 20 took 10.8 s, and deep pages took over a minute. Search used ILIKE, so a single wrong letter found nothing.

I made three changes. I replaced DISTINCT ON with merged_into_id IS NULL, because in this view "one row per building" meant "only primary records". I added a btree index on (lower(name), id). And I switched to a keyset cursor:

CREATE INDEX IF NOT EXISTS idx_locations_name_lower_order ON locations (lower(name), id);

      AND l.merged_into_id IS NULL
      AND l.geom && ST_Expand(ST_SnapToGrid(ST_SetSRID(ST_MakePoint(@longitude::float8, @latitude::float8), 4326), @cell::float8), @cell::float8)
      AND ST_SnapToGrid(l.geom, @cell::float8) = ST_SnapToGrid(ST_SetSRID(ST_MakePoint(@longitude::float8, @latitude::float8), 4326), @cell::float8)
      AND (@after_name::text = ''
           OR (lower(l.name), l.id) > (lower(@after_name::text), @after_id::uuid))
ORDER BY lower(l.name) ASC, l.id ASC
LIMIT @lim::int;

The spatial conditions are in that order on purpose. The bounding-box && check can use the PostGIS GiST index (PostGIS is PostgreSQL's geography extension). So it cheaply narrows the candidates first. The exact grid-cell check, which no index can serve, then runs only on the few that remain.

For search, I kept the substring match and added %> as a fallback, ranked by word_similarity. I set the threshold in the pool's AfterConnect. Then I tested thresholds against six real-world typos of names in the data, and against nonsense input:

Nonsense input returned nothing at both thresholds.

Patterns and common mistakes

• Use keyset pagination for anything users scroll deep into. Keep OFFSET for small, bounded admin tables where jumping to page N matters.
• Always add a unique tiebreaker to the sort key, and build the index on the exact sort expression.
• Give API clients the cursor as an opaque token, so you can change the sort key later without breaking them.
• Check the plan with EXPLAIN (ANALYZE) on a deep page, not page 1. Problems only show up with depth.
• Don't sort a whole table by similarity(). Filter with an indexable operator first, then rank what's left.
• Keep a btree for ordering and a GIN trigram index for matching. One index rarely does both.
• Put every session setting in connection setup, never in request code.

Takeaways

• OFFSET gets slower with depth because skipped rows are still read and thrown away.
• Keyset pagination with a row-value comparison makes every page cost the same.
• The index must match the ORDER BY exactly, including expressions like lower().
• DISTINCT ON and indexes that can't order quietly force a full sort.
• For search, word_similarity and %> suit short queries against long names, and the operator can use a GIN index.
• pg_trgm thresholds are per session. Set them in the pool's AfterConnect, and choose them by testing against real typos.