Implementing indexes in POSTGRESQL

D.V. Zvazhii, S.S. Gorokhovsky

Abstract


This article explores the process of designing and implementing a new index access method in the PostgreSQL database management system, using a suffix tree–based index as a case study. Suffix trees provide optimal theoretical search complexity; however, classical descriptions of this data structure assume unlimited memory, arbitrary pointer manipulation, and single-threaded access — conditions that PostgreSQL does not provide. The paper systematically examines the key architectural subsystems of PostgreSQL that directly affect index design: the "one process per connection" multi-process model, page-based storage organization with a fixed 8 KB block size, and the two-level memory management system based on the shared buffer pool and hierarchical memory contexts. Using a concrete implementation as an example, the paper analyzes the key design decisions a developer faces when building a new index: the strategy for mapping logical tree nodes onto physical pages, the organization of intra-page storage for variable-length edges with separation into identification and payload components, the design of the page special area for navigational metadata and suffix links, and mechanisms for page type identification. Particular attention is given to open implementation challenges — edge label compression, parallelism limitations of Ukkonen’s algorithm, and the feasibility of supporting index-only scans. It is shown that implementing a new index structure in a DBMS of PostgreSQL’s caliber is not merely a matter of adapting an algorithm to a specific programming interface, but also of aligning it with the internal invariants, protocols, and subsystem interaction logic that define the permissible space of architectural decisions.

Problems in programming 2026; 1: 14-24

 


Keywords


PostgreSQL; indexes; data structures; memory management; generalized suffix trees; database architecture

References


ComerD.Ubiquitous B-Tree. ACM Comput. Surv. 11. 1979. Vol. 11., no. 2. P.121–137.

Hash Indexes. PostgreSQL Documentation. https://www.postgresql.org/docs/17/hash-index.html

GiST Indexes. PostgreSQL Documentation. https://www.postgresql.org/docs/17/gist.html

Walid A.G., Ilyas I. F. SP-GiST: An Extensible Database Index for Supporting Space Partitioning Trees. Journal of Intelligent In formation Systems. 2001. Vol. 11., no. 2. P.215–240.

SP-GiST Indexes. PostgreSQL Documentation. https://www.postgresql.org/docs/17/spgist.html

GIN Indexes. PostgreSQL Documentation. https://www.postgresql.org/docs/17/gin.html

BRIN Indexes. PostgreSQL Documentation. https://www.postgresql.org/docs/17/brin.html

BasicAPIStructurefor Indexes.PostgreSQL Documentation. https://www.postgresql.org/docs/17/index-api.html

Stonebraker M., Rowe L. A. The design of POSTGRES. SIGMOD. 1986. Vol. 15., no. 2. P. 340—355.

Suffix Tree Based AM Index Method Source Code. https://github.com/Uaman/postgres/tree/feature-string-search-am

Hellerstein J. M., Naughton J. F., Pfeffer A. Generalized Search Trees for Database Systems. Encyclopedia of Database Systems Morgan Kaufmann Publishers Inc. 1998. P. 1-3.

Eltabakh M., Ramy E., Walid A. Space-Partitioning Trees in PostgreSQL: Realization and Performance. 2006.

Schoemans M., Walid G. A., Zimányi E., Sakr M. Multi-Entry Generalized Search Trees for Indexing Trajectories. Proceedings of the 32nd ACM International Conference on Advances in Geographic Information Systems. 2024. P. 21–31.

Weiner P. Linear Pattern Matching Algorithm. 1973.

McCreight E. M. ASpace-Economical Suffix Tree Construction Algorithm. J. ACM . 1976. Vol.23., no.2. P. 262–272.

Ukkonen E.. On-Line Construction of Suffix Trees. Algorithmica. 1995. Vol.14., no.3. P. 249–260.

Manber U., Gene M. Suffix Arrays: A New Method for on-Line String Searches. SIAM Journal on Computing. 1993. Vol. 22., no. 5. P. 935–248.

Xu W., Haoyu C., Yidong H., Xuedong H., Ge N. Full-Text Search Engine with Suffix Index for Massive Heterogeneous Data. In formation Systems. 2022.

Gusfield D. Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University

Press. 1997.


Refbacks

  • There are currently no refbacks.