Submit Podcast or Channel

pg_textsearch 1.0: How We Built a BM25 Search Engine on Postgres Pages

April 8, 20260 comments♥ 0
00:00 This audio is presented by Hacker Noon, where anyone can learn anything about any technology. P.G underscore text search 1.0. How we build a BM25 search engine on Postgres pages. By Tiger Data, creators of timescale DB. Design, implementation, and benchmarks of a native BM25 index for Postgres. No generally available to all Tiger Cloud customers and freely available via open source. If you have used Postgres' built in TS understores, score rank for full text search at any meaningful scale, you already know the limitations. Ranking quality degrades as your corpus grows. There is no inverse document frequency, so common words carid same weight as rare ones. There is no term frequency saturation, so a document that mentions, database, 50 times outranks one that mentions it once. There is no
00:51 efficient top K path. Scoring requires touching every matching row. Most teams work around this by bolting on Elasticsearch or TypeSense as a sidecar. That works, but now you are syncing data between two systems, operating two clusters, and debugging consistency issues when they diverge. PG underscore text search takes a different approach. Real BM25 scoring, built from scratch and see on top of Postgres' own storage layer. You create an index, write a query, and get results ranked by relevance. The operator returns a BM25 relevance score. Scores are negated. so Thapostgres' default ascending order by returns the most relevant results first. The index is stored entirely in standard Postgres pages managed by the buffer cache.
01:38 It participates in Wall, works with PG underscore dump and streaming replication, and requires no external storage or special backup procedures. What shipped in 1.0 from preview to production. In October 2025, we released a preview that held the entire inverted index in shared memory, Rebuilt from the heap on restart, Preview Blog. In the five months and 180 plus commits since, the extension has been substantially rewritten. Disc-based segments replaced the memory-only architecture. Block Max Wand plus Wand Optimization for Fast Top K queries.
02:13 Posting list compression with SIMD accelerated decoding, 41% smaller indexes. Parallel index builds, 138M documents in under 18 minutes. 2.4X to 6. 5x faster than parade db tantavi for two to four term queries at 138 m scale 8 7x higher concurrent throughput this post covers the architecture query optimization strategy and benchmark results we include a candid discussion of where parade db is faster and a full accounting of current limitations background y bm 25 in postgres postgres ships with for full text ranking uses an ad hoc scoring function that lacks the three
02:55 properties that make BM25 effective. Inverse document frequency IDF. Downweight's common terms so that rarer, more informative terms drive the ranking. Term frequency saturation prevents a document from scoring arbitrarily high by repeating a term many times. A document mentioning database 50 times is not 50 times more relevant than one mentioning at once. Document length normalization accounts for the fact that a term match in a short document is more informative than the same match in a long one, one. For applications where ranking quality matters, rag pipelines, search-driven UIs, hybrid retrieval, this is a material limitation. At scale, also has no top K optimization path. Ranking by relevance requires scoring every matching row. The primary
03:44 existing BM25 extension for Postgres is Parade DBPG underscore search, which wraps the Tantavy search library written in Rust. Early versions stored the index in auxiliary. files outside the wall, current versions use Postgres pages. PG underscore text search takes a different approach, rather than wrapping an external search library, the entire search engine, tokenization, compression, query optimization, is built from scratch and see on top of Postgres' storage layer. Architecture. The hybrid Memtable Plus segment design PG underscore TextSurch uses an LSM tree-inspired architecture
04:22 for incoming rights go tone in memory inverted index. index, the Memtable, which periodically spills TO immutable on disk segments. Segments compact in levels. When a level accumulates enough segments, default 8, they merge into the next level. Fewer segments means fewer posting lists to consult per query term, which directly reduces query latency. This is the same right optimized Memtable, read optimized segment pattern used in RocksDB, 5, and other LSM-based engines, adapted here for Postgres' page-based storage.
04:55 The right path. Memtable the Memtable lives in Postgres shared memory, one per index, accessible to all backends. It contains a string interning hash table that stores each unique term exactly once, per term posting lists recording document ids and term frequencies, and corpus statistics, document count and average document length, maintained incrementally so that BM25 scores can be computed without a separate pass over the index. When the Memtable exceeds a configurable threshold, default, 32M post-inj entries, it spills to a L-E-V-E-L-0 disk segment at transaction commit. A secondary trigger, default, 100K unique terms per transaction, handles large single-transaction loads
05:40 like bulk imports. The mem table is rebuilt from the heap on startup. Since the heap is wall logged, no data is lost if Postgres crashes before a spill completes. This is analogous-o how right-ahead log protects an LSM. MEMTable, except here the wall is Postgres' own. The rebuild cost is proportional to the amount of data not yet spilled to segments. For indexes where most data has been spilled, startup is fast. The read path. Segment segments are immutable and stored in standard Postgres pages. Each segment contains a term dictionary, a sorted array of offsets into a string pool, binary
06:17 searchable for O, log-n, term lookup. Posting blocks of up to 128 documents each. containing delta encoded doc IDs, packed term frequencies, and quantized document lengths, field norms. A separate skip index stores one entry per posting block with upper bound score metadata used by block max wand optimization, described below. A field norm table mapping document lengths to one byte quantized values using Lucene, Tantavis small float encoding, six. This encoding is exact for lengths zero to 39, covering most short documents, for longer documents, quantization error increases from approximately 5% to approximately 11%. In practice, the impact on ranking is smaller than these numbers suggest.
07:03 BM25 scores depend on the ratio of document length to average document length, which dampens quantization error and the B parameter, default 0. 75, further reduces length's influence, a doc ID to CTID mapping that translates internal document IDs to Postgres tipple identifiers for heap fetches. Minimizing page ACCEESS storing data in Postgres pages means every access goes through the buffer manager. Even for pages already in cache, each access involves a buffer table look UP, pin acquisition, and lock handling. That overhead adds up in a scoring loop processing millions of postings. This constraint shaped several design decisions.
07:45 Each segment assigns compact 4 byte, segment local document IDs, 0 to N1, which mapped to Postgres'Sys 6 byte CT IDs, keep double identifiers. After collecting all documents for a segment, doc IDs are reassigned so that Doc underscore it order matches CTID order. Sequential iteration through posting lists then produces sequential access to the CTID mapping, maximizing cache locality. CTIDs themselves error stored as two separate arrays, four byte page numbers and two byte offsets. Rather than interleaved six byte records, doubling cash line utilization. The scoring loop works entirely with doc IDs, term frequencies, and field norms. It never touches the CTID arrays. CTIDs are resolved only for the final top K results in a single batch pass. A top 10 query that scores thousands of candidates resolves 10
08:40 CTIDs, not thousands. Postgres integration because the index is stored in standard buffer managed pages, PG- underscore text search participates in Postgres infrastructure without special handling, MVCC visibility, proper rollback on abort, wall and physical replication, VACUUM with correct dead entry removal, and planner hooks that detect the operator and select index scans automatically. Logical replication works in the usual way. Row changes are replicated and the index is rebuilt on the subscriber. Query Optimization Block Max Wand. The The top K problem naive BM25 evaluation scores every document matching any query term. For a three-term query on MS Marco v2, 138M documents, this means decoding and scoring posting
09:30 lists with tens of millions of entries. Most applications need only the top 10 or 100 results. The challenge is finding them without scoring everything. Block MaxWW-DPG underscore text search implements Block MaxW, 2, which uses block-level upper bounds to skip non-contributing posting blocks during top K evaluation. Lucini adopted a similar approach in version 8, 0, 7, the core idea, maintain the score of the KTH best result seen so far as a threshold, and skip any posting block whose upper-bound score cannot exceed it. Each 128 document posting block has a corresponding skip entry
10:09 storing the maximum term frequency in the block and the minimum field norm, the shortest document, which would score highest for a given term frequency. From these two values, BMW can compute a tight upper bound on the block's BM25 contribution without decompressing it. If the upper bound falls below the current threshold, the entire block, all 128 documents, is skipped. To illustrate, consider a single term top 10 query on a large corpus. After scanning a few thousand postings, the algorithm has accumulated 10 results with a minimum
10:42 score of, say, 12. 3. It now encounters a block where the upper bound BM25 score, computed from the blocks stored metadata, is 9. Since 9, 1 less than 12. 3, no document in this block can enter the top 10, and the entire block is skipped without decompression. For short queries on large corpora, the vast majority of blocks are skipped this way. Want pivot selection for multi-term queries. P.G underscore text search adds the WAND algorithm, three, for cross-term skipping. Terms are ordered by their current document ID, and the algorithm identifies a pivot term. The first term whose cumulative maximum score exceeds the current threshold. All terms before the pivot advance to at least the pivot's current doc ID, skipping entire ranges of documents across multiple posting lists simultaneously,
11:33 before block level BMW bounds are even checked. For multi-term queries, BMW compares the sum of per-term block upper bounds against the threshold, extending the single-term logic described above. The combination of wand, cross-term skipping, and BMW, within list block skipping, is most effective for short queries. 1 to 4 terms, which account for the majority of real-world search traffic. In the full MS-Marcov1 query set, 1,010,916 queries from Bing, 72. 6% have 2 to 4 L-Xemes after English stemming and stop word removal, with a mean of 3. 7 in a mode of 3. The speed up narrows four longer queries, where more blocks contain at least one term with a potentially high scoring document. Grand et all. Seven, observe the same pattern in Lucene's BMW implementation. Compression and storage,
12:29 posting blocks use a compression scheme designed for fast random access decoding. Doc IDs are delta encoded, storing differences between consecutive IDs rather than absolute values, then packed with variable width bitpacking. The maximum delta in the block determines the bit width, and all deltas use that width. Term frequencies are packed separately with their own bit width. Field norms are the one-byte small float values described above. The bitpack decode path uses branchless direct indexed UINT-64 loads rather tonne byte at a time accumulator, eliminating branch misprediction in the interdecode loop. Where available, S-IMD Intrinsics, S-S-E-2 on X8664, Neon on Arm 64, accelerate the mask and store step. A scalar fallback handles other platforms.
13:18 Compression reduces index size by 41% compared to uncompressed storage. Decode overhead is approximately 6% of query time, measured by profiling, which is more than offset by reduced buffer cash pressure. The scheme prioritizes. is decode speed over compression ratio. A note on index size comparisons, PG- underscore text search does not store term positions, so it cannot support phrase queries natively, see limitations. This makes its indexes inherently smaller than engines like Tantavi that store positions by default. The 19 to 26% size advantage reported in our benchmarks reflects both compression and this feature difference. Parallel index build, for large tables, serial index construction can take hours.
14:03 P.G underscore text search useesposgresses built-in parallel worker infrastructure to distribute the work. The leader launches workers and assigns each a range of heap blocks. Workers scan their assigned blocks, tokenize documents via, build local and memory indexes, and write intermediate segments to temporary buff files. The leader then performs an N-way merge of all worker output, writing a single merged segment directly to index pages. Workers run concurrently in the scan, tokenize, build phase, the leader merga sequentially. The expensive part, heap scanning, tokenization, posting list assembly is CPU bound and parallelize as well. The merge, right phase is comparatively cheap,
14:46 so a serial merge captures most of the speed up with minimal complexity. It also produces a single fully compacted segment that is optimal for query performance. On MS-Marco v2, 138m passages, 15 workers complete the build in 17 minutes 37 seconds, benchmarks. Methodology all benchmarks use the MS-Marco passage ranking dataset, 8, a standard information retrieval benchmark drawn from real Bing search queries. We compare PG underscore text search against Parade DBV-0. 21, 6, which wraps Tantavi. Both extensions use their default configurations, Postgres tuning as specified per experiment. Both systems configure
15:29 English stemming and stopword removal. Queries are drawn uniformly from eight token count buckets, 100 queries per bucket in V1, up to 100 per bucket on version 2. Weighted average metrics use the MS Marco version 1 Lexime distribution as weights, reflecting real search traffic. Cache state. All query benchmarks are warm cache, a warm-up pass runs before timing begins, and the working set fits in the OS page cache and shared underscore buffers for all configurations tested. Results reflect CPU and algorithmic efficiency, not I.O. We have not benchmarked memory-constrained configurations where the index exceeds available cache. Ranking. Both systems produce BM25 rankings using the same tokenization, English stemming, and stop words.
16:17 We have not performed a systematic ranking equivalence comparison. Both implement standard BM25 with the same default parameters, K1 equals 1. 2. B equals 0, 75, but differences in IDF computation and tokenization edge cases may produce different orderings for some queries. MS-Marco query length distribution the following histogram shows the distribution of query lengths in the full MS-Marco v1 query set. 1,010,916 queries measured in L-Xemes after English stopword removal and stemming via Postgres. This distribution is broadly consistent with web search query length studies, 9, 10. The MS-Marco mean of 3.7-L-exemes, after stemming, stopword removal, corresponds to roughly 5 to 6 raw words, consistent with the corpus statistics reported
17:08 by Nguyen et al, 8. We use the V1 distribution for weighting throughout as it provides the largest sample. Results. MS. Marko v. 2, 138M passages, environment. Dedicated C6I, 4 extra large EC, 2 instance. Intel Zeon Platinum 837C, 8 cores, 16 threads, 123 gigabites RAM, NVME SSD. Postgres 17. 4 with shared underscore buffers equals 31 gigabytes. Both indexes fit in the buffer cache. Index build. MetricPG underscore text search parade DB index size 17 gigabytes, 23GB build time 17 minutes 37 seconds, 8 minutes 55 sec, documents, 138,364, 158,138, 364,164,158 parallel workers 1514PG underscore text search index is 26% smaller. Parade DB builds approximately 2x faster. Single client query latency, P50 median, top 10 queries, Lexa Mesp underscore text search,
18:18 Ms, speed up 15. 1159, 8311, 7 by 29, 1459, 656, 5 by 320, 0477, 623, 9 by 4141, 92 98, 892, 4 by 567, 76,125, 381,9 by 6,102, 82,148, 781, 481, 4 by 7,159, 37, 151, 161, 161, 161, 161, 1x8 plus 177, 95,190, 471, 1X the same pattern holds. PG underscore text search is fastest on short queries and the systems converge at longer lengths. Weighted by the MS Marco v1 query length distribution, the overall P50 is 40. 6 milliseconds for PG underscore text search versus 94. 4 milliseconds for parade DB, a 2.3x advantage, concurrent throughput. We ran PG bench with 16 parallel clients for 60 seconds, after a 5-second
19:33 warmup. Each client repeatedly executes a query drawn atrandom from a weighted pool of 1,000 queries. metric pg underscore text search parade db transactions sec one hundred ninety eight seven hundred twenty two eight average latency eighty one millise second seven o one ms total transactions sixties eleven nine million six hundred ninety one thousand three hundred eighty seven pg underscore text search sustains eight seven x higher throughput under concurrent load results ms mark o v one eight eight 8M passages on the smaller dataset, GitHub Actions Runner, 7 gigabytes RAM, Postgres 17. The advantages are more pronounced. 26x speed up for single token queries. 14x for 2 token, 7.3x for 4 token. Total sequential execution time for all 800 queries. 6. 5 seconds for PG underscore text
20:29 search versus 25. 2 seconds for parade db. Full results in methodology are available at the Benchmarks page. Discussion. Latency versus query length the speed up correlates strongly with query length. 11. 7x for single token queries on version 2, narrowing to 1. 1x at 8 plus tokens. This is the expected behavior of dynamic pruning algorithms like BMW and WAND. Grand et all. 7. Observe the same pattern in Lucene's BMW implementation. The practical significance depends on the workloads query length distribution. 6% of MS-Marco queries have 2 to 4 L-exemes, the range where PG- underscore text search shows its largest advantage, 6.5x to 2.4x on version 2. weighted by this distribution, the overall speed-up is 2.
21:21 3x on V2 and 3. 9x on version 1. Concurrent throughput the concurrent throughput advantage, 8.7x substantially exceeds the single client advantage, 2.3x weighted P-50. G underscore text search queries execute a C code operating on Postgres buffer pages, with all memory management handled by Postgres' buffer cache. ParadeDB routes queries through Rust, CFFI into Tantavi, which manages its own memory and I.O outside the buffer pool. We have not profiled ParaditiB's internals, so we cannot attribute the concurrency gap to specific causes, but the architectural difference shared buffer cache versus separate memory management as a plausible contributor. ParaditiB's concurrent performance may also improve in future versions, where P-A-R-A-D-B is faster
22:12 index build time. Per ADB builds indexes 1-6-2x faster across both datasets. Tantavis indexer is highly optimized Rust code with its own I-O management, not constrained by Postgres' page-based storage. Build time is a one-time cost per index, or per re-index, it does not affect query performance. long queries, at 7 plus L-Elexemes, the two systems converge. On version 2, the 8 plus Lexime P 50 is 178 milliseconds for PG underscore text search versus 190 milliseconds for parade db. These long queries represent approximately 3, 7% of the MS Marco distribution. Index size caveat. PG underscore text search indexes are 19 to 26% smaller, but this comparison is not apples to apples
23:02 PG underscore text search does not store term positions, while ParadeDB stores positions to support phrase queries. Benchmark limitations all measurements are warm cache on datasets that fit in memory. The 100 query sample per bucket provides directional results but limited statistical power foretoil latencies. Parade DBV-0-21.6 was current at time of testing. Future versions may improve. We compare against Parade DBB because it is the primary Postgres native BM25 alternative, standalone engines like Elasticsearcharche in a different deployment model. We have not benchmarked right heavy workloads with concurrent queries. Limitations, we want to be clear about what PG underscore text search does not support in 1.0. No phrase queries.
23:50 The index stores term frequencies but not term positions, SWA cannot natively evaluate queries like database system as a phrase. Phrase matching can be done with a post filter, OR-only query semantics. All query terms are implicitly ord. A query for database system matches documents containing either term. We plan to add an OR-N-O-T operators via a dedicated Boolean query syntax in a post-1. Zero release. No highlighting or snippet generation.
24:20 Use Postgres is on the result set for highlighting. expression indexing. Each BM25 index covers a single text column. Workaround. Create a generated column concatenating multiple fields. Partition local statistics. Each partition maintains its own IDF and average document length. Cross-partition queries return scores computed independent LIPR partition. No background compaction. Segment compaction runs synchronously during memtable spill. Right heavy workloads may observe compaction latency. Background compaction is planned. Place, PGSQL requires explicit index names. The implicit text syntax relies on planner hooks that do not fire inside place, PGSQL, do blocks, or stored procedures. Use explicitly. This is a practical limitation many developers will hit. Shared underscore preload underscore libraries required. PG underscore text search must be listed in shared underscore preload underscore libraries, requiring a server restart to install. On Tiger Cloud, this is a handled automatically. No fuzzy matching or typo tolerance. P.G underscore text search uses Postgres'
25:30 standard text search configurations for tokenization and stemming but does not provide built in fuzzy matching. Typotolerant search requires a separate approach. E.G. PG underscore TRGM. What's next? Planned work for post 1. Zero releases. Boolean query operators and OR, not via a dedicated query syntax. Background D-Couple Compaction from the Right Path. Expression Index Support. Index computed expressions, not just bare columns. Dictionary Compression. Front coding for terms, reducing dictionary size.
26:06 Improved right concurrency. Better throughput for sustained insert heavy workloads. Try it. PG underscore text search requires Postgres 17 or 18. The fastest way to try it is on Tiger Cloud, where it is already installed and configured. No setup, no shared underscore preload underscore libraries. Create a service and run the example below. For self-hosted installations,
26:29 pre-built binaries for Linux and MacOS, AMD 64, arm 64, are available on the GitHub releases page. Added to shared underscore preload underscore libraries and restart, source code and full documentation, GitHub.com, timescale, PG underscore text search part two of this series covers getting started with PG underscore text search, hybrid search with P.E. Vector Scale and Production Patterns. References. 1. Robertson et al.
26:59 Ocopy at TREC 3, 1994. See also Robertson, Zaragoza, the Probabilistic Relevance Framework, BM25 and Beyond. Foundations and Trends in IR, 3, 4, 33 to 389, 2009. 2.
27:17 Ding, Sewell. Faster Top K document retrieval using Block Max Indexes. Cigier, 2011, P.P. 993.102. 3. Broder at all. Efficient query evaluation using a two level retrieval process. Chicham 2003, P.P. 4.O.256 to 4. O'Neill at all. The log-structured merged tree, LSM tree. ACTA Informatica, 33, 4. 351 to 385, 1996. Facebook, RoxDB, a persistent key value store for fast storage environments. H T-T-TPS-C-O-Roxd-B. Org, 6.
28:03 Small-Fload Encoding. Apache Lucene Small Float. Java. Tantavi uses an equivalent implementation, 7. Grand et all, from M-A-X-S-C-O-R-E to block Max WAND, the story of how Lucene significantly improved query evaluation performance. ECIR 2020. 8. Nguyen et al. M.S. Marco. A human-generated machine reading comprehension data set.
28:28 2016. 9. Statista. Distribution of online search queries in the U.S. February 2020 by number of search terms. 10. Dean. We analyzed 306M keywords. Backlinko, 2024. Thank you for listening to this Hackernoon story, read by artificial intelligence. Visit hackernoon.com to read, write, learn and publish.