The Problem

PostgreSQL users requiring physical data ordering and efficient vector similarity search must choose between btree's limited pruning, sequential scan's high I/O cost, or external vector extensions that lack storage-integrated zone maps. The pg_sorted_heap extension addresses this by physically sorting tables by primary key and exposing per-page zone maps that the planner can use to skip irrelevant blocks during scan operations, particularly for time-series, event log, and vector similarity workloads.

What This Does

pg_sorted_heap provides table access methods (table AMs) for PostgreSQL with three surface areas: a stable sorted_heap AM for physically ordered storage with zone-map pruning, a stable sorted_hnsw index AM for planner-integrated KNN search on svec/hsvec types, and a GraphRAG API surface covering fact-clustered retrieval, routing, and expand/rerank helpers. The src/ directory contains the C implementation of the table AMs (pg_sorted_heap.c, flashhadamard.c, pq.c), while sql/ hosts the SQL surface including flashhadamard_experimental.sql. The scripts/ directory holds 183 files encompassing benchmarks (bench_fh_kernel_real.c, bench_gutenberg_k8s_ann.sh) and measurement scripts (measure_ivf_scan_rate.py, measure_lsh_skip_rate.py). The poc/ directory contains 8 proof-of-concept files demonstrating the core techniques. The README documents that at 100M rows a point query reads 1 buffer versus 8 for btree or 520K for seq scan, and that zone map pruning can reduce block access from 12,500 to 3 for range queries on sorted data.

How It Is Wired

Execution begins at the PostgreSQL backend when a table is declared USING sorted_heap. The table AM's sampinit and compatible hooks initialize the zone map infrastructure; get_next_tuple traverses physically sorted pages, and bitmapqualgetbitmap integrates zone map pruning into query planning. The sorted_hnsw index AM routes KNN queries through a shared decoded cache with exact rerank inside the index scan, implemented in the same src/ C files. GraphRAG functions (sorted_heap_graph_rag, sorted_heap_graph_route) reside in the SQL layer and depend on the underlying sorted storage for fact clustering by (entity_id, relation_id, target_id). The import graph contains 39 internal modules with zero circular dependencies across 197 analyzed code files, but the four-project structure (scripts, sql, src, poc) means no single architecture binds the whole repository—changes to the C table AM in src/pg_sorted_heap.c ripple across all projects using the extension, while the poc/ measurement scripts operate as isolated benchmarks. The widest blast radius resides in src/flashhadamard.c and src/pg_sorted_heap.c, each exceeding 1,800 lines of C code.

How To Use It

Setup: Install the extension into a PostgreSQL instance with CREATE EXTENSION pg_sorted_heap;. The Makefile provides build targets; the Dockerfile.cnpg defines a container base image ghcr.io/cloudnative-pg/postgresql:18.1-202511240807-standard-trixie.

Configuration: No environment variables or keys are required. Table definitions use USING sorted_heap with a primary key, e.g.:

CREATE TABLE events (
    ts    timestamptz,
    src   text,
    data  jsonb,
    PRIMARY KEY (ts, src)
) USING sorted_heap;

Running it: Bulk load data via COPY events FROM '/path/to/events.csv'; the sort occurs automatically during COPY. After load, run SELECT sorted_heap_compact('events'); to rebuild zone maps. Execute range queries that the zone map prunes:

SELECT * FROM events
WHERE ts BETWEEN '2026-01-01' AND '2026-01-02'
  AND src = 'sensor-42';

Real-World Use

An IoT sensor network stores readings in a readings table with composite primary key (device_id, ts) using sorted_heap. Zone maps track both columns, so a query like SELECT * FROM readings WHERE device_id = 42 AND ts BETWEEN '2024-01-01' AND '2024-01-02' reads only the blocks containing that device's time range, skipping irrelevant device data entirely. For vector similarity, create a sorted_hnsw index on an svec column and issue SELECT * FROM embeddings ORDER BY embedding_vector <-> '[0.5, -0.3, ...]' LIMIT 5; for planner-integrated KNN with exact rerank inside the index scan.

Code Health & Issues

  • [HIGH] Add a test suite; this repository has none. Evidence: 57 source files, no test files. Any change ships with no signal that existing behaviour still holds, so a regression reaches production undetected. Fix: Add one test per public entry point, then a CI step that runs them.
  • [MEDIUM] Declare least-privilege permissions for GITHUB_TOKEN - .github/workflows/ci.yml. Evidence: 4 workflow(s) declare no permissions. With no declaration the token inherits the repository default, so any injected step can push commits or mint releases from inside your own CI. Fix: Add permissions: contents: read at the top of the workflow and widen per job only where needed.
  • [MEDIUM] Enable Dependabot or Renovate. Evidence: 1 manifest(s), no update bot configured. Without a bot a published advisory sits unpatched until someone audits by hand. Fix: Commit .github/dependabot.yml covering the repo ecosystems plus github-actions.
  • [MEDIUM] Pin the container base image by digest - Dockerfile.cnpg. Evidence: ghcr.io/cloudnative-pg/postgresql:18.1-202511240807-standard-trixie. An untagged or mutable base means today's build and last month's contain different libc and a different CVE set, with no record of which shipped. Fix: Use image:tag@sha256:<digest> and enable Dependabot's docker ecosystem.
  • [MEDIUM] Gate pull requests on a dependency vulnerability scan - .github/workflows. Evidence: no dependency scan in CI. This is the one gate that would catch a known-vulnerable package before it reaches a build. Fix: Add dependency-review-action on pull_request, or osv-scanner on push and a schedule.
  • [MEDIUM] Set persist-credentials: false on checkout - .github/workflows/ci.yml. Evidence: checkout keeps the token, then dependencies are installed. The token stays in .git/config for every later step, so a malicious postinstall script reads a pushable credential without one ever being passed to it. Fix: Add with: persist-credentials: false, and pass an explicit token only to the step that pushes.
  • [LOW] Set timeout-minutes on the workflow jobs - .github/workflows/perf-compare-selftest.yml. Evidence: 1 workflow(s) declare no job timeout. A wedged step runs to the six-hour platform default, which on a two-hourly schedule means three runs overlap behind it. Fix: Add timeout-minutes with a realistic bound to each job.

The Bottom Line

The repository delivers a practical PostgreSQL extension that physically sorts data and exposes zone maps for block-pruned scans, with measurable I/O savings at scale. The C implementation in src/ is functional but oversized and lacks test coverage; the measurement scripts in poc/ show the techniques working but suffer from duplicated logic. Teams needing efficient time-series or vector storage in PostgreSQL will find immediate value, particularly if they can tolerate the current gaps in automated testing and dependency governance.