Collation and Text Sort Cost #

Two ORDER BY clauses over the same 20 million rows: sorting by a bigint takes 4 seconds, sorting by a text column takes 31. The data volume is similar and the plan is identical apart from the sort key. Text comparison under a linguistic collation is simply far more expensive per comparison than integer comparison, and a sort performs a lot of comparisons.

Sort mechanics are covered in sort and hash node analysis. This page is about what the collation adds.

The Condition #

Comparing two strings under a linguistic collation means applying language rules — accent and case weighting, character expansions, ignorable punctuation — through the operating system’s or ICU’s collation library. That is orders of magnitude more work than comparing two integers.

Three factors decide the cost:

The collation itself. C (or POSIX) compares byte by byte and is by far the cheapest. Linguistic collations, whether from libc or ICU, are much more expensive; ICU is generally faster than glibc for the same locale and offers deterministic behaviour across systems.
Abbreviated keys. For sorting, PostgreSQL can compute a fixed-size abbreviated key per value and compare those first, falling back to full comparison only on ties. This optimisation applies to text under most collations and dramatically reduces the number of full comparisons — but it is disabled for nondeterministic collations (those with deterministic = false, used for case- or accent-insensitive comparison).
String length and shared prefixes. Values sharing long prefixes force comparisons deeper into the string.

Collation also affects indexes: an index is built under a specific collation, and a query ordering by a different collation cannot use it for ordering. Changing a database or column collation therefore invalidates the ordering property of existing indexes, which is why a collation change requires rebuilding them.

Annotated EXPLAIN Evidence #

EXPLAIN (ANALYZE, BUFFERS)
SELECT id, display_name FROM customers ORDER BY display_name LIMIT 1000;

Under a linguistic collation:

Limit  (actual time=31204.6..31206.1 rows=1000 loops=1)
  ->  Sort  (actual time=31204.6..31205.8 rows=1000 loops=1)
        Sort Key: display_name
        Sort Method: top-N heapsort  Memory: 412kB
        ->  Seq Scan on customers  (actual rows=20412004 loops=1)
Execution Time: 31208.4 ms
-- a top-N heapsort of 1,000 rows over 20M inputs: 20M comparisons against the heap
-- the cost is in the comparisons, not in memory or I/O

The same query with the column declared COLLATE "C":

  ->  Sort  (actual time=4102.1..4103.4 rows=1000 loops=1)
        Sort Key: display_name COLLATE "C"
        Sort Method: top-N heapsort  Memory: 412kB
Execution Time: 4106.2 ms
-- byte comparison: 7.6× faster, but "Ä" no longer sorts next to "A"

And with an index under the query’s collation:

CREATE INDEX CONCURRENTLY customers_display_name_idx ON customers (display_name);

Limit  (actual time=0.04..0.9 rows=1000 loops=1)
  ->  Index Scan using customers_display_name_idx on customers  (actual rows=1000 loops=1)
Execution Time: 1.1 ms
-- no comparisons at all: the index is already in collation order

Step-by-Step Resolution #

Confirm the cost is comparisons. A sort with small Memory: and a long runtime is comparison-bound, not memory-bound.
Prefer an index in the query’s collation. It removes the comparisons entirely for ordered scans, and is the only fix that also helps LIMIT queries return immediately.

Check which collation is in force:

SELECT collname, collprovider, collisdeterministic
FROM pg_collation WHERE oid = (SELECT collation FROM pg_attribute
                               WHERE attrelid = 'customers'::regclass AND attname = 'display_name');

Prefer ICU over libc for linguistic collations where both are available: it is generally faster and versioned independently of the operating system, avoiding index corruption after OS upgrades change libc’s collation behaviour.
Use C collation where ordering is technical, not human-facing — identifiers, codes, hashes, URLs. Declare it on the column so every comparison and index uses it:
```
ALTER TABLE events ALTER COLUMN external_id TYPE text COLLATE "C";
```
For human-facing ordering that must be case-insensitive, prefer a stored normalised sort-key column in C collation over a nondeterministic collation, keeping the display value separate.
Rebuild indexes after any collation change, since their order depends on it.

Before and After #

-- BEFORE: linguistic collation, no index
Sort  Sort Key: display_name  top-N heapsort  Memory: 412kB              Execution Time: 31208.4 ms

-- AFTER: index on display_name in the same collation
Index Scan using customers_display_name_idx  (first 1,000 rows)           Execution Time: 1.1 ms

Collation changes and index validity #

An index on a text column stores entries in that collation’s order. If the collation’s behaviour changes — a glibc upgrade that alters sorting rules, or moving the database to a host with a different library version — existing indexes can contain entries in an order the current library disagrees with. The symptoms are subtle and serious: unique constraints that no longer detect duplicates, index scans that miss rows, and range scans that return incomplete results.

PostgreSQL records collation version information and warns when a mismatch is detected, and the remedy is REINDEX. Two practices reduce the exposure: using ICU collations, whose versions are tracked explicitly and change deliberately, and using C collation for columns where linguistic ordering is irrelevant, since byte order never changes.

This is one of the few areas where a performance choice and a correctness concern point the same way: C collation for technical identifiers is both faster and immune to collation-version problems, while human-facing text needs a linguistic collation and the discipline to reindex after library upgrades.

Common Pitfalls #

Sorting technical identifiers linguistically. Hashes and codes gain nothing from language rules. Diagnostic signal: text sorts on opaque identifiers. Fix: C collation on those columns.

Nondeterministic collations for ordering. They disable abbreviated keys and are the slowest option. Diagnostic signal: case-insensitive collations on large sorted columns. Fix: a normalised sort-key column.

Index in a different collation than the query. The index cannot provide the ordering. Diagnostic signal: a Sort above an index scan on the sorted column. Fix: match the collations, or index the expression with an explicit COLLATE.

Ignoring collation version warnings. Index correctness is at stake. Diagnostic signal: warnings after an OS upgrade. Fix: REINDEX the affected indexes.

Frequently Asked Questions #

Why is sorting text so much slower than sorting numbers? #

Because comparing strings under a linguistic collation applies language rules through a collation library, which costs far more per comparison than comparing two integers, and a sort performs many comparisons.

Does the C collation make sorting faster? #

Substantially — it compares bytes directly and enables the cheapest comparison path. It sorts by byte value rather than by language rules, so it is appropriate for identifiers and codes but not for names shown to users.

Do I need to reindex after changing a collation? #

Yes. An index’s entries are ordered according to the collation in force when it was built, so changing the collation — or an underlying library version that alters ordering — requires REINDEX for the index to remain correct.

Sort and Hash Node Analysis — parent guide: sort nodes
External Merge Sort Spill Diagnosis — the memory side of sorting
Descending and NULLS Ordering in B-Tree Indexes — matching an index to an ORDER BY

Up: Sort and Hash Node Analysis