# Abbreviated keys: exploiting locality to improve PostgreSQL's text sort performance

DevFeed: [Abbreviated keys: exploiting locality to improve PostgreSQL's text sort performance](<https://devfeed.tech/articles/abbreviated-keys-exploiting-locality-to-improve-postgresql-s-text-sort-performance-33650.md>)

Original publisher: [Read original article](<https://pgeoghegan.blogspot.com/2015/01/abbreviated-keys-exploiting-locality-to.html>)

Author: Peter Geoghegan (noreply@blogger.com)

Published: 2015-01-24T00:43:00Z

Content type: article

Language: en

Sources: [Peter Geoghegan's blog](<https://devfeed.tech/sources/peter-geoghegan-s-blog.md>)

Topics: [PostgreSQL](<https://devfeed.tech/topics/postgresql.md>), [Sorting](<https://devfeed.tech/topics/sorting.md>), [Databases](<https://devfeed.tech/topics/databases.md>), [SQL](<https://devfeed.tech/topics/sql.md>)

Tags: [abbreviation](<https://devfeed.tech/tags/abbreviation.md>), [c](<https://devfeed.tech/tags/c.md>), [index](<https://devfeed.tech/tags/index.md>), [internals](<https://devfeed.tech/tags/internals.md>), [performance](<https://devfeed.tech/tags/performance.md>), [postgresql](<https://devfeed.tech/tags/postgresql.md>), [sorting](<https://devfeed.tech/tags/sorting.md>), [sql](<https://devfeed.tech/tags/sql.md>)

## AI overview

The article explains PostgreSQL's abbreviated keys patch, which improves text sorting performance by exploiting locality. It reports that, in realistic cases, text-based CREATE INDEX operations in PostgreSQL 9.5 are over three times faster than in PostgreSQL 9.4, while noting that the improvement varies by workload.

## Source excerpt

On Monday, Robert Haas committed a patch of mine that considerably speeds up the sorting of text in PostgreSQL. This was the last and the largest in a series of such patches, the patch that adds "abbreviated keys". PostgreSQL 9.5 will have big improvements in sort performance. In realistic cases, CREATE INDEX operations on text are over 3 times faster than in PostgreSQL 9.4. Not every such utility operation, or data warehousing query involving a big sort is sped up by that much, but many will be. This was a piece of work that I spent a considerable amount of time on over the past few months. It's easy to justify that effort, though: sorting text is a very fundamental capability of any database system. Sorting is likely the dominant cost when creating B-Tree indexes, performing CLUSTER operations, and, most obviously, for sort nodes that are required by many plans that are executed in the service of queries with ORDER BY or DISTINCT clauses, or aggregates using the GroupAggregate strategy. Most of the utility statements that need to perform sorts must perform them with a very disruptive lock on the target relation (CREATE INDEX CONCURRENTLY is a notable exception), so quite apart from the expense of the sort, the duration of sorts often strongly influences how long a production system is seriously disrupted. My interest in sorting is not new: I first worked on it in 2011. Early research on it back then prompted Robert Haas and Tom Lane to write the SortSupport infrastructure, which I've now extended here. Originally, the SortSupport infrastructure was all about providing alternative versions of comparators for use in sort routines, versions that avoided certain overhead otherwise inherent to calling functions that are generally accessible from SQL. As a highly extensible system, PostgreSQL requires that sort behavior be defined in terms of a default B-Tree operator class, which is itself defined in terms of SQL operators with underlying SQL-callable functions. These