A Hitchhiker's Guide to Postgres Text Search

One thing I love about The Hitchhiker’s Guide to the Galaxy is how it plays with the relativity of importance. The same event can be monumental to one person, while being completely forgettable to another. When the Vogons demolish Earth to make way for a hyperspace bypass, it’s the worst day of Arthur Dent’s life. To the Vogons, it’s a routine Thursday doing some construction work.

Platform investments can take a similar shape. From the inside, a project can be huge with months of design, a new data model, a migration nobody wants to get wrong, and lots of looking at metrics. From the outside, the best version of that project shows up as one small thing. In this case, that search is fast now, and it finds what you want. At Cortex, we recently rebuilt one of these under-the-hood systems. It was a big deal for us, and we hope for our customers it’s simply a thing that works better than it used to.

Search at Cortex

The software catalog is a core functionality of our product. Customers may have hundreds to millions of entities depending on their scale and level of granularity, and people ask all kinds of questions of it: “what does this person own?”, “what’s in this AWS project?”, “where’s the billing service?” Search is how they get those answers, and it shows up all over the product, so when search is slow or wrong, customers feel it everywhere.

At Cortex, following the DRIVE framework, we have a weekly operational excellence review where we take stock of our various systems and try to identify any gaps. Our search SLOs kept showing up in that review, along with a steady trickle of bug reports. Talking through the issues, we began to realize that there were problems with our search architecture that became apparent after we hit a larger scale.

The original design served us well for years. What changed was the scale around it. Essentially, our old system was based around Lucene, and it would build search indexes on a cron based schedule then put those search indexes in storage. When we needed those indexes, we would fetch them and deserialize them into application memory where they were cached and the execution of the query takes place. For smaller data sets, that worked well, a cache miss would still be quick, and the impact on application memory wasn’t too bad. But as that data size grew, so did the indexes, up to the point where we could see objects 1Gi large we were trying to fetch. This caused out of memory exceptions since they were resident in memory for some time, as well as caused a long tail latency where cold start queries had to wait some period of time to load those from storage. On top of that, because indexes were only rebuilt on a schedule, search was only ever as fresh as the last run. A newly created service might not show up in search for a while, which explained a lot of those bug reports.

We knew the solution was to push the query into the storage layer rather than loading it in the application, but we also had some hard constraints that we were working with. We needed the capability to deploy in a wide variety of environments with as little as a Postgres database. And in those environments, arbitrary extensions are not always well supported. Extensions like unaccent ship with Postgres contrib and are available on every managed cloud provider. Alternatives like ElasticSearch or extensions like ParadeDB became less attractive due to their operational burden, and because managed Postgres offerings on the major cloud providers, like RDS and Cloud SQL, don’t let you install them. So we set out on our journey to implement search on a minimal Postgres instance!

Query Parsing

Before we get to the fun SQL, we have to start at how queries come into our search engine. It would be great and easy if we could hand the raw string straight to Postgres. Postgres even ships websearch_to_tsquery, which understands quotes, OR, and -. But it has no concept of fields (owner:), presence checks (owner:*), or parentheses. Beyond those gaps, we wanted full control over our query grammar, so we can extend it as the product grows. We support the following syntax and operations:

• <key>:<value>
• <key>:* (the field has any value)
• "quoted phrases"
• prefix*
• AND
• OR
• NOT (-)
• Parentheses

To represent this in code:

sealed interface SearchExpr {
    data class Term(val field: String?, val value: String, val prefix: Boolean = false) : SearchExpr

    data class And(val children: List<SearchExpr>, val explicit: Boolean = false) : SearchExpr

    data class Or(val children: List<SearchExpr>) : SearchExpr

    data class Not(val child: SearchExpr) : SearchExpr

    data class Presence(val field: String) : SearchExpr
}

And.explicit is a nuanced problem because in certain cases we may want to treat “cat dog” as “cat AND dog” whereas other use cases may require “cat OR dog”. This keeps it generic to allow for search surfaces to opt-in to the behavior they want (more on this later).

From this, it flows into a tokenizer, which just converts the raw string into List<Token>. That goes into our parser, which follows a classic textbook shape from computer science class. For example we have:

private fun parseOr(): SearchExpr {
    val first = parseAnd()
    val parts = mutableListOf(first)
    while (peek() is Token.Or) {
        advance()
        parts.add(parseAnd())
    }
    return if (parts.size == 1) parts[0] else SearchExpr.Or(parts)
}

The parser follows the same order of operations as Boolean logic (and SQL): NOT first, then AND, then OR. parseAnd, parseAdjacency, and parseNot follow the same shape, one precedence level each. Every node in this tree eventually becomes part of a SQL WHERE clause, so we also cap how deeply a query can nest and how many terms it can have. That keeps a pathological query from turning into a plan that Postgres spends ages on. With some additional finagling to handle things like special key:value terms, and special cases like https:// we end up with the following outputs from this process end to end:

Query Building

A quick Postgres full-text primer

Postgres full-text search has two sides. On the document side, to_tsvector turns text into a tsvector (apt naming). This means that the text becomes a sorted list of normalized words (lexemes) and their positions.

SELECT to_tsvector('simple_nostop', 'The Heart of Gold');
-- 'gold':4 'heart':2

Stopwords like “the” and “of” are dropped, since they just add noise and consume disk space, and everything is lowercased. On the query side, a tsquery describes what to look for, and @@ checks whether a tsvector matches it. There are a few ways to build one:

A GIN index on the tsvector column maps each lexeme to the rows that contain it, which is what makes @@ fast. We use a config without stemming on purpose: catalog data is full of names, tags, and identifiers, and those shouldn’t be folded.

Putting it together

The read side for catalog search is a denormalized table sourced via CDC from several source tables. We generate one tsvector column that holds all of the following fields with a weight. I will get into that process more later on, but for now imagine the following schema:

CREATE TABLE search_index (
  id            bigint NOT NULL,
  name          text,
  description   text,
  owner_text    text,
  tag_text      text,
  content_hash  text,
  search_vector tsvector NOT NULL
);

We use jOOQ for query building, which generates Kotlin classes from our database schema so we can write SQL as typed code instead of strings. It’s fantastic for composing complex queries, because every WHERE fragment is a Condition that combines with and, or, and not, just like our parsed tree. We can just walk through the tree and do some mapping!

fun build(e: SearchExpr): Condition = when (e) {
    is SearchExpr.Term -> term(e)
    is SearchExpr.Presence -> presence(e.field)
    is SearchExpr.And -> DSL.and(e.children.map(::build))
    is SearchExpr.Or -> DSL.or(e.children.map(::build))
    is SearchExpr.Not -> DSL.not(build(e.child))
}

Well… Not totally that straightforward, so I’ll start with a simple case. When we just have a bare term, we match against search_vector and pick the Postgres function based on the shape of the input:

In the real queries, each value is also wrapped in immutable_unaccent(...) and passed a text search config; we leave those out here for readability.

If I’m searching for something such as name:"Heart of Gold", then we must ensure that “Heart of Gold” appears in the name column of our search index table. Text indexes can get very expensive, so we don’t keep a separate index for every column. Instead, the column’s to_tsvector(...) gets computed at query time. That would be slow on its own, but the search_vector column is an indexed superset of the other columns. So we use its GIN index to find candidate rows first, and then recheck the specific column on only those rows:

WHERE search_vector @@ phraseto_tsquery('heart of gold')      -- GIN index: fast, finds candidates
  AND to_tsvector(name) @@ phraseto_tsquery('heart of gold')  -- recheck: runs only on candidates

We map from key to column using some jOOQ generated column types, which can catch any broken mappings at compile time.

It’s also worth briefly discussing scoring. Consider again the case of a bare term. If I search “auth”, what should be more relevant, “auth”, “auth-service”, or “authorization”? Most likely, an end user wants the exact match first! Postgres’ ts_rank alone can’t tell us that: it scores how often and how closely lexemes appear, not whether the name is the query. So we layer tiers on top:

  CASE WHEN lower(name) = lower(:q)    THEN 20000 ELSE 0 END  -- exact
+ CASE WHEN name ILIKE '%' || :q || '%' THEN 5000 ELSE 0 END  -- substring
+ ts_rank_cd(search_vector, query) * 100                      -- full-text relevance
+ similarity(name, :q) * 10                                   -- trigram closeness

The gaps between the weights are deliberate: any exact match beats any substring match, and ts_rank only breaks ties within a tier. Structured queries like a OR b skip the exact and substring tiers, since “exact” doesn’t mean much there.

To tie it all together, here’s one query end to end through the pipeline:

Search Index Updates

Remember the old cron job that rebuilt our indexes on a schedule? We wanted search to reflect a change within seconds, not whenever the next run happened to kick off. So instead of rebuilding on a timer, we listen for changes as they happen using change data capture (CDC).

The rough shape looks like this:

Debezium tails the Postgres write-ahead log (WAL) and publishes every insert, update, and delete as an event on Kafka. Our search consumer reads those events in batches and figures out which catalog entities they affect. The nice thing about sourcing from the WAL is that we don’t have to remember to update search everywhere we write to the catalog. If it hits the database, search hears about it.

One decision that made life a lot easier is that the consumer never tries to patch a row with the contents of an event. An event only tells us which entity changed, and then we reproject that entity from the current state of the source tables. That sounds wasteful, but it means event order doesn’t matter much, a replayed event is harmless, and there’s exactly one code path that knows how to build a search row. We also dedupe each batch per tenant first, so an entity that got edited ten times in a few seconds only gets rebuilt once.

Writing the row is where the tsvector from earlier finally gets built. Each field gets its own weight, which is what ts_rank_cd uses when it scores matches:

search_vector =
     setweight(to_tsvector(name),        'A')
  || setweight(to_tsvector(tag_text),    'A')
  || setweight(to_tsvector(owner_text),  'B')
  || setweight(to_tsvector(description), 'C')

A match on a name counts for more than a match buried in a description, which is usually what you want. Computing all of those vectors isn’t free though, so every row also stores a hash of its content. If a reprojected entity hashes the same as what’s already there, we skip the write entirely. That turns retries and duplicate events into no-ops, and it keeps a full rebuild over unchanged data from rewriting the whole table (and the GIN index along with it).

Not every change is cheap to fan out. Renaming a group that a few thousand services belong to technically touches every one of those search rows. Rather than stampede the database with those in real time, we leave the big fan-out changes to a nightly full rebuild. This trades a little bit of consistency to avoid major performance hits to typical updates. It also protects us against any failed updates via CDC. It’s essentially a safety net, and thanks to the content hash, a night where nothing changed costs next to nothing.

Search Surfaces

Catalog search wasn’t the only search box in the product. Scorecards, workflows, reports, and plenty of other list pages all have one, and each of them had grown its own way of filtering. Once we had a parser and a query builder we liked, it felt a little silly to keep them to ourselves. So we pulled the reusable pieces out into what we call a SearchSurface.

A surface is everything a feature team needs to write to get search on their table, and nothing more. No tsvectors, no tsquerys, and no GIN indexes to think about:

val SCORECARD_SEARCH = SearchSurface(
    table = SCORECARDS,
    id = SCORECARDS.ID,
    documentColumns = listOf(SCORECARDS.NAME, SCORECARDS.TAG, SCORECARDS.DESCRIPTION),
    boostWeights = mapOf(SCORECARDS.NAME to 10_000, SCORECARDS.TAG to 10_000),
)

Then they call search(surface, tenantId, rawQuery) and get back a ranked list of ids. Every surface runs the same parser as catalog search, so quotes, -, AND, OR, and parentheses work the same way in every search box. The one thing a surface skips is field: operators, since most search surfaces don’t require or support those semantics..

This is also where And.explicit from earlier pays off. In catalog search, deep thought means both words have to match. In a list page search box that’s often too strict, so surfaces default to treating adjacent words as an OR, ranked by how many of them hit. Searching deep thought shows “Deep Thought” first, with “Deep Space Probe” right after it. A typed AND is still a hard requirement, which is exactly why the parser checks whether the user actually typed it.

Unlike the catalog, surfaces don’t get a precomputed search_vector. The tsvector is computed inline for each row at query time, which sounds scary until you remember that most of these tables have hundreds or maybe thousands of rows per tenant. Postgres chews through that without breaking a sweat. If a surface ever outgrows that, we can add an expression GIN index on the same tsvector and the queries pick it up with no code changes.

Results

We compared a month of production search on the old engine with a month after the last tenant moved over.

Internal search (what the Cortex app uses)

Public API search

The pattern is the part I like most. The long tail saw the most drastic improvement. That’s where the old design hurt, with cold starts stuck waiting on an index to load.

Across our search-serving applications, resident heap after GC dropped by about half, and total memory use fell by roughly 40%.

Freshness of the search indexes also improved. The old indexes took at least five minutes to pick up an edit, and some fields didn’t update until the next nightly full build. With CDC, most edits now show up in search within a couple of seconds, and even the slowest 1% typically land within about 10 seconds:

The exceptions are typically short backlogs when large batch jobs write to the database all at once.

Ford Prefect spends fifteen years on Earth researching and writing about the planet for the Guide. After all of his work, his editors compress it into two words: “Mostly harmless.” A whole world, and years of effort, compressed into something a reader skims past in a second.

That’s how I think about this project. Months of planning, development, and rollout, and for most of our customers it compresses down to a couple of words (in the best way possible): “search works.”