The database contains a customer named Smith, but an operator enters Smyth. The difference is only one character, yet ordinary string comparison treats the two names as completely different.
Situations like this arise constantly. Users mistype product names, employees spell names differently, and imported reference data gradually accumulates nearly identical duplicates.
Fuzzy string matching often uses Levenshtein distance: the minimum number of single-character insertions, deletions, and substitutions needed to turn one string into another. The distance between Smith and Smyth is one; between kitten and sitting, it is three.
The most convenient place to calculate it is where the data already lives:
SELECT levenshtein_fast('kitten', 'sitting');This query really does run in PostgreSQL. But levenshtein_fast is not a built-in server function. The complete source files are collected in the appendix at the end.
It is written in Rust and loaded into a PostgreSQL backend process. It is not a separate service or an application that connects to the database over the network. The planner sees it as an ordinary SQL function, while the executor invokes the Rust code from a SELECT, a WHERE clause, an index expression, or a parallel worker process.
The PostgreSQL planner chooses how to execute an SQL query: which indexes and operations to use and in what order to process the data. The executor runs the selected plan.
At first glance, this should require a large layer of C, hand-written FFI, and PostgreSQL internal structures. In practice, pgrx handles almost the entire boundary.
pgrx is a framework for developing PostgreSQL extensions in Rust. It generates the FFI glue and converts types between Rust and SQL.
Removing boilerplate does not remove the rules. We still have to define the function's behavior for NULL, tell the planner the truth about its purity, return results in memory with the correct lifetime, and prevent a Rust panic from crossing PostgreSQL's C stack.
A panic can arise, for example, from indexing outside an array. It must not cross PostgreSQL's C stack: incompatible stack unwinding can terminate the backend, so pgrx converts the panic into an SQL error at the boundary.
Let us begin with code that knows nothing about the database.
An Ordinary Rust Function
The Levenshtein distance implementation uses dynamic programming.
Imagine a matrix whose rows correspond to the characters of one word and whose columns correspond to the characters of the other. Each cell stores the minimum number of edits needed for the corresponding prefixes.
There is no need to store the entire matrix. Computing the next row requires only the previous one, so a single mutable array is enough.
pub fn levenshtein(a: &str, b: &str) -> usize {
let a: Vec<char> = a.chars().collect();
let b: Vec<char> = b.chars().collect();
let (short, long) = if a.len() <= b.len() {
(&a, &b)
} else {
(&b, &a)
};
let mut row: Vec<usize> = (0..=short.len()).collect();
for (i, long_char) in long.iter().enumerate() {
let mut previous_diagonal = row[0];
row[0] = i + 1;
for (j, short_char) in short.iter().enumerate() {
let substitution = if long_char == short_char {
previous_diagonal
} else {
previous_diagonal + 1
};
previous_diagonal = row[j + 1];
row[j + 1] = substitution
.min(row[j] + 1)
.min(row[j + 1] + 1);
}
}
row[short.len()]
}Both strings are first converted into Vec<char>, so the algorithm compares Unicode characters rather than individual UTF-8 bytes.
The row variable stores distances for the part of the longer string that has already been processed. Computing the next cell considers three possibilities: insert a character, delete it, or substitute it. If the characters match, substitution adds no cost.
The running time is proportional to the product of the string lengths, while the extra memory is proportional to the length of the shorter string.
For now, this is an ordinary library function. It can be tested without PostgreSQL installed:
$ cargo test --release
running 5 tests
test result: ok. 5 passed; 0 failed; 0 ignored; 0 measured; 0 filtered outThe algorithm remains independent of the database. It can be tested, profiled, and used by other Rust programs. PostgreSQL integration will live in a separate, thin layer.
The Bridge Between Rust and PostgreSQL
We will use pgrx to build the extension.
It understands PostgreSQL's internal calling convention, converts SQL types into Rust types, creates the FFI entry points, and generates the SQL that registers the extension in the database.
The tools are installed through Cargo:
$ cargo install cargo-pgrx --locked
$ cargo pgrx init --pg18 downloadThe second command prepares a separate PostgreSQL instance for development. It is isolated from production databases and lets us build, install, and run the extension in its own environment.
One more command creates the project skeleton:
$ cargo pgrx new pg_fuzzyAfter that, the entire bridge from a Rust function to SQL looks like this:
use levenshtein::levenshtein;
use pgrx::prelude::*;
::pgrx::pg_module_magic!(name, version);
#[pg_extern(immutable, parallel_safe, strict)]
fn levenshtein_fast(a: &str, b: &str) -> i32 {
levenshtein(a, b) as i32
}The algorithm is included as an ordinary Rust dependency. It has not been copied into the extension or rewritten for PostgreSQL.
The pg_module_magic! macro adds metadata that the server checks when it loads the library. This lets PostgreSQL verify that the module was built for a compatible extension interface.
The #[pg_extern] attribute exports the function to SQL. pgrx analyzes its signature, generates the required glue, and converts PostgreSQL input values into familiar &str references.
The function body itself does almost nothing:
levenshtein(a, b) as i32But the three parameters inside pg_extern matter more than they may appear to. They describe properties that the planner is then entitled to rely on.
PostgreSQL Handles NULL Itself
An argument of type &str must refer to an existing string. An SQL NULL, by contrast, means that there is no value at all.
The strict attribute tells PostgreSQL that if either argument is NULL, there is no need to call the function. The server immediately returns NULL.
This query therefore never crosses the boundary into Rust:
SELECT levenshtein_fast(NULL, 'anything');Let us verify it:
postgres=# SELECT levenshtein_fast(NULL, 'anything') IS NULL
AS strict_handles_null;
strict_handles_null
---------------------
tThe function does not have to accept Option<&str> and handle a missing argument manually. This behavior is natural for Levenshtein distance: if either string is unknown, the result is unknown as well.
If NULL had a distinct application-level meaning, the signature really would have to change. Here, however, the declaration is more precise than an extra branch inside the algorithm.
What immutable Promises the Planner
Levenshtein distance depends only on the two strings it receives. The same arguments always produce the same result.
That is exactly what immutable means.
The function must not read tables, consult the current time, depend on session state, or change its answer from one call to the next. Given this promise, PostgreSQL may precompute constant expressions and use the function in index expressions.
For example:
SELECT levenshtein_fast('rust', 'trust');may be evaluated while the plan is being prepared because its result is already known and cannot change during execution.
PostgreSQL does not verify that the declaration is true. If a function that reads mutable data or depends on connection settings is marked immutable, the server is allowed to reuse its result after that result has stopped being correct.
The attribute is part of the contract, not an optional hint to the optimizer.
Why the Function Can Run in Parallel
PostgreSQL can divide some queries among several worker processes. A user-defined function may be incompatible with parallel execution, however: it might access state owned by the main backend, modify data, or depend on call order.
parallel_safe states that the function has none of those restrictions.
Our implementation receives two strings, creates temporary arrays, computes a number, and returns it. It uses no shared mutable state and does not depend on which process invokes it.
The planner may therefore place it in a parallel section of the plan.
The short signature describes more than argument conversion. It also defines behavior for NULL, permitted optimizations, and the conditions under which the function may run.
Loading the Function into the Server
Build and install the extension:
$ cargo pgrx install --release \
--pg-config ~/.pgrx/18.4/pgrx-install/bin/pg_config
Discovered 2 SQL entities: 0 schemas (0 unique), 2 functions, …
Writing SQL entities to …/extension/pg_fuzzy--0.0.0.sqlpgrx compiles the dynamic library and generates the SQL definition for the exported functions.
Start PostgreSQL:
$ cargo pgrx start pg18
Starting Postgres v18 on port 28818Installing the files on the server does not automatically enable the extension in every database. Run the usual command for the selected database:
CREATE EXTENSION pg_fuzzy;PostgreSQL reads the generated SQL definition, adds the function to the system catalog, and links it to a symbol inside the dynamic library.
Rust code can now be invoked with an ordinary SELECT:
postgres=# CREATE EXTENSION pg_fuzzy;
CREATE EXTENSION
postgres=# SELECT levenshtein_fast('kitten', 'sitting');
levenshtein_fast
------------------
3Let us check a few more strings:
postgres=# SELECT levenshtein_fast('postgres', 'progress') AS d1,
levenshtein_fast('rust', 'trust') AS d2;
d1 | d2
----+----
4 | 1SQL no longer cares which language implements the function body. The planner sees a registered function with defined types and properties; during execution, control passes into compiled Rust code.
We can now use it where it was needed in the first place:
SELECT name
FROM customers
WHERE levenshtein_fast(name, 'Smyth') <= 1;The data never leaves the server, travels to an external application, or gets collected there for a second filtering pass. The algorithm runs directly inside the query.
When Native Code Is Actually Useful
Levenshtein distance can also be implemented in PL/pgSQL. The algorithm remains the same: two rows of the dynamic-programming matrix, nested loops, and character comparisons.
But this is a demanding workload for an interpreted procedural language. Every small operation inside the nested loop passes through its interpreter.
Let us compare the same query over a table containing twenty thousand short strings.
The PL/pgSQL implementation:
== plpgsql
close_matches
---------------
2
Time: 1535.290 ms (00:01.535)The Rust function:
== rust
close_matches
---------------
2
Time: 13.391 msThe difference is roughly two orders of magnitude.
This does not mean that every piece of logic should move into a native extension. PostgreSQL is good at optimizing operations expressed in ordinary SQL, and hiding a simple condition inside a user-defined function can sometimes conceal useful information from the planner.
A specialized algorithm with nested loops, intensive string processing, or a large number of small computations is a better candidate.
Comparing only against PL/pgSQL would still be incomplete. PostgreSQL ships with the fuzzystrmatch module, which already includes a C implementation of Levenshtein distance.
postgres=# CREATE EXTENSION fuzzystrmatch;
postgres=# SELECT count(*) AS close_matches
FROM words
WHERE levenshtein(w, 'deadbeef') <= 3;
close_matches
---------------
2
Time: 15.927 msThe Rust and C versions fall within the same range. The variation between individual runs is too large to claim that either language is faster.
The more important result is different: an ordinary safe Rust function performs like a native server extension. The algorithm did not have to be written in C or surrounded by manual memory management.
Speed, however, is the simplest part of this integration. The code's behavior during an error is much more interesting.
What Happens During a Panic
The SQL function runs inside the same backend process that serves the connection.
If the extension corrupts memory or crosses the language boundary incorrectly, we can lose not just the current call but the entire process and its session.
Add a function that deliberately panics:
#[pg_extern]
fn rust_panic() -> i32 {
panic!("this is a Rust panic inside a Postgres backend");
}Call it from SQL:
postgres=# SELECT rust_panic();
ERROR: this is a Rust panic inside a Postgres backendFrom the outside, the panic looks like an ordinary PostgreSQL error. Let us check whether the connection survived:
postgres=# SELECT 'still alive' AS backend;
backend
-------------
still aliveThe next query receives an answer from the same backend process. The panic did not cross the FFI boundary directly and did not terminate the server.
Rust and PostgreSQL leave a failed call in different ways. pgrx intercepts both mechanisms at the boundary so that each side can finish according to its own rules.
ereportis a PostgreSQL macro written in C for creating an error message. At theERRORlevel, it eventually callslongjmp, a C library function that transfers execution directly to an error handler without returning through the chain of function calls. If Rust code lies on that path, its destructors will not run, so pgrx intercepts the jump at the boundary.
When Rust code panics, pgrx converts the panic into a PostgreSQL error. The server aborts the current command and returns ERROR to the client, but continues serving the connection.
The reverse direction matters just as much.
A Rust function can call PostgreSQL's internal API, which may execute ereport(ERROR). If longjmp is allowed to jump across active Rust frames, their destructors will not run. Temporary strings, vectors, locks, and other values will not complete their normal lifetimes.
The PostgreSQL error is therefore caught at a controlled boundary and represented inside Rust as a panic. Rust first unwinds its own stack; the error is then returned safely to the server.
The conversion works in both directions:
Rust panic → PostgreSQL ERROR
PostgreSQL ERROR → Rust unwinding → PostgreSQL ERRORTo the user, both cases look like an ordinary SQL error. Internally, each side finishes the call according to its own rules.
PostgreSQL Has Its Own Memory Lifetimes
Ordinary temporary values inside the algorithm belong to Rust.
The Vec<char> values are freed when the function returns or when its stack unwinds after a panic. The usual ownership model applies here.
Values returned to SQL, however, must obey PostgreSQL's lifetimes.
The server groups allocations into memory contexts: memory regions associated with a query, transaction, or another part of the backend.
A memory context is a region of memory with a shared lifetime. PostgreSQL frees the entire region when the query finishes, so pointers to its data must not be retained for later queries.
For an i32 result, this boundary is almost invisible: the number is passed directly.
Strings, arrays, composite values, and sets of rows are more complicated. Their representation must live in memory that remains valid for as long as the server needs the result.
pgrx places returned SQL values in the appropriate context and ties their lifetime to the PostgreSQL operation.
This model also helps during errors. If query execution is aborted, the server destroys its memory context along with every temporary SQL allocation in it.
But a memory context does not make every pointer safe.
If an extension manually stores the address of a string from a query context in a global variable, that memory ceases to exist when the query finishes. The address may still look plausible, but it can no longer be dereferenced.
In ordinary Rust, the borrow checker would often prevent this error. When working with the internal C API and raw pointers, part of the lifetime proof once again becomes the extension author's responsibility.
A Short Function Describes a Large Contract
The entire visible integration still fits in one function:
#[pg_extern(immutable, parallel_safe, strict)]
fn levenshtein_fast(a: &str, b: &str) -> i32 {
levenshtein(a, b) as i32
}The Rust signature defines the argument and result types. strict keeps NULL out of the function. immutable lets the planner treat the result as constant for identical inputs. parallel_safe permits calls from worker processes.
The pg_extern macro creates the SQL entry point and the required FFI glue. pgrx reconciles the two error-handling mechanisms and places returned server values in memory with the appropriate lifetime.
The algorithm itself knows nothing about any of this.
It accepts two strings and returns a number, just as it did before PostgreSQL entered the picture. That keeps it independently testable, reusable, and changeable without starting a database after every edit.
The boundary layer stays small not because the boundary is simple, but because its difficult rules have already been expressed by the library, the types, and the attributes.
The Algorithm Moves to the Data
An ordinary application retrieves strings from the database, transfers them over a connection, and processes them in its own process.
An extension reverses that direction: the code is loaded where the data already lives.
Levenshtein distance then becomes part of SQL:
SELECT id, name
FROM customers
WHERE levenshtein_fast(name, 'Smyth') <= 1;The planner knows the function's properties, the executor invokes it for each row, and its result immediately participates in filtering. There is no intermediate customer list, separate network request, or second processing stage.
The price of being this close to the data is stricter responsibility.
NULL must have defined semantics. Declarations made to the planner must match actual behavior. A panic must not cross the FFI boundary without handling. Returned memory must follow PostgreSQL's lifetime rules.
When those conditions hold, Rust code truly becomes part of the server.
Not a service beside PostgreSQL or a client library layered on top, but an ordinary SQL function that can be called with SELECT.
Appendix: Full Source Files
levenshtein/src/lib.rs — 67 lines
//! Scene 01: the Rust code, before any Postgres.
//!
//! Levenshtein distance with the classic two-row dynamic programming:
//! O(a×b) time, O(min(a,b)) memory, over Unicode scalar values. This
//! exact function goes inside the database in the next scene — the
//! point of the demo is that it does not change on the way in.
/// Edit distance between two strings, in Unicode scalar values.
pub fn levenshtein(a: &str, b: &str) -> usize {
let a: Vec<char> = a.chars().collect();
let b: Vec<char> = b.chars().collect();
// Keep the shorter string in the row to minimize memory.
let (short, long) = if a.len() <= b.len() { (&a, &b) } else { (&b, &a) };
let mut row: Vec<usize> = (0..=short.len()).collect();
for (i, long_char) in long.iter().enumerate() {
let mut previous_diagonal = row[0];
row[0] = i + 1;
for (j, short_char) in short.iter().enumerate() {
let substitution = if long_char == short_char {
previous_diagonal
} else {
previous_diagonal + 1
};
previous_diagonal = row[j + 1];
row[j + 1] = substitution.min(row[j] + 1).min(row[j + 1] + 1);
}
}
row[short.len()]
}
#[cfg(test)]
mod tests {
use super::levenshtein;
use anyhow::{Result, ensure};
#[test]
fn textbook_pair() -> Result<()> {
ensure!(levenshtein("kitten", "sitting") == 3);
Ok(())
}
#[test]
fn identical_strings_cost_nothing() -> Result<()> {
ensure!(levenshtein("postgres", "postgres") == 0);
Ok(())
}
#[test]
fn empty_side_costs_the_other_side() -> Result<()> {
ensure!(levenshtein("", "rust") == 4);
Ok(())
}
#[test]
fn symmetric() -> Result<()> {
ensure!(levenshtein("flaw", "lawn") == levenshtein("lawn", "flaw"));
Ok(())
}
#[test]
fn unicode_counts_scalars_not_bytes() -> Result<()> {
// One substitution in chars, though the byte lengths differ.
ensure!(levenshtein("кот", "кит") == 1);
Ok(())
}
}pg_fuzzy/src/lib.rs — 54 lines
//! Scene 02: the scene-01 function, put inside Postgres.
//!
//! The algorithm arrives as a path dependency on the plain crate from
//! scene 01 — not a copy. What pgrx adds is the boundary: the calling
//! convention, NULL discipline (`strict`), and the memory contract —
//! values this code hands to Postgres live in palloc'd memory contexts
//! owned by the query, not in Rust's global allocator's care.
use levenshtein::levenshtein;
use pgrx::prelude::*;
::pgrx::pg_module_magic!(name, version);
/// Edit distance, callable from SQL. `strict` lets Postgres answer
/// NULL inputs itself — the function never sees them; `immutable` and
/// `parallel_safe` tell the planner the whole truth about purity.
#[pg_extern(immutable, parallel_safe, strict)]
fn levenshtein_fast(a: &str, b: &str) -> i32 {
levenshtein(a, b) as i32
}
/// Scene 04's exhibit: a deliberate Rust panic inside a live backend.
/// pgrx catches the unwind at the FFI boundary and reports it as a
/// regular Postgres ERROR — the backend survives.
#[pg_extern]
fn rust_panic() -> i32 {
panic!("this is a Rust panic inside a Postgres backend");
}
#[cfg(any(test, feature = "pg_test"))]
#[pg_schema]
mod tests {
use pgrx::prelude::*;
#[pg_test]
fn test_levenshtein_fast() {
assert_eq!(3, crate::levenshtein_fast("kitten", "sitting"));
}
}
/// This module is required by `cargo pgrx test` invocations.
/// It must be visible at the root of your extension crate.
#[cfg(test)]
pub mod pg_test {
pub fn setup(_options: Vec<&str>) {
// perform one-off initialization when the pg_test framework starts
}
#[must_use]
pub fn postgresql_conf_options() -> Vec<&'static str> {
// return any postgresql.conf settings that are required for your tests
vec![]
}
}pg_fuzzy/Cargo.toml — 40 lines
[package]
name = "pg_fuzzy"
version = "0.0.0"
edition = "2021"
[lib]
crate-type = ["cdylib"]
[features]
default = ["pg18"]
pg13 = ["pgrx/pg13", "pgrx-tests/pg13" ]
pg14 = ["pgrx/pg14", "pgrx-tests/pg14" ]
pg15 = ["pgrx/pg15", "pgrx-tests/pg15" ]
pg16 = ["pgrx/pg16", "pgrx-tests/pg16" ]
pg17 = ["pgrx/pg17", "pgrx-tests/pg17" ]
pg18 = ["pgrx/pg18", "pgrx-tests/pg18" ]
pg19 = ["pgrx/pg19", "pgrx-tests/pg19" ]
pg_test = []
pg_bench = ["dep:pgrx-bench"]
[dependencies]
levenshtein = { path = "../01-levenshtein" }
pgrx = "=0.19.2"
[dependencies.pgrx-bench]
version = "=0.19.2"
optional = true
[dev-dependencies]
[dev-dependencies.pgrx-tests]
version = "=0.19.2"
[profile.dev]
panic = "unwind"
[profile.release]
panic = "unwind"
opt-level = 3
lto = "fat"
codegen-units = 1