DuckDB Extension
Marisa
Build compact MARISA tries from strings in DuckDB. Store a trie as a BLOB, then check membership or retrieve names with a shared prefix.
On this page
Sample data for the examples
Each browser example starts with these sample tables; sample files are shared across examples on this page. Run this setup first when trying the examples in your own DuckDB session.
-- Fixtures for marisa example snippets. Idempotent: uses CREATE OR REPLACE.
-- Source: cookbook.mdx "Build a trie"
CREATE OR REPLACE TABLE employees(name TEXT);
INSERT INTO employees VALUES
('Alice'),('Bob'),('Charlie'),('David'),('Eve'),('Frank'),
('Mallory'),('Megan'),('Oscar'),('Melissa');
-- Trie built from employees, referenced by lookup/predictive examples.
CREATE OR REPLACE TABLE employees_trie AS
SELECT marisa_trie(name) AS trie FROM employees;
-- Source: cookbook.mdx "Longest-prefix match"
CREATE OR REPLACE TABLE country_codes(code TEXT);
INSERT INTO country_codes VALUES ('U'), ('US'), ('USA');
CREATE OR REPLACE TABLE country_codes_trie AS
SELECT marisa_trie(code) AS trie FROM country_codes;
-- Stand-in for the /usr/share/dict/words wordlist used by the
-- "Big static dictionary" cookbook section. Small, deterministic
-- set with shared "duck" prefixes so marisa_predictive(..., 'duck', ...)
-- still returns plausible completions.
CREATE OR REPLACE TABLE words(word TEXT);
INSERT INTO words VALUES
('duck'), ('duckbill'), ('duckboard'), ('ducker'), ('ducking'),
('duckling'), ('ducks'), ('ducky'),
('rouge'), ('rough'), ('round'), ('route'), ('routine'),
('apple'), ('banana'), ('cherry');
CREATE OR REPLACE TABLE words_trie AS
SELECT marisa_trie(word) AS trie FROM words;
-- "dictionary" alias used by technical-details.mdx "What you can do with one query".
CREATE OR REPLACE TABLE dictionary(word TEXT);
INSERT INTO dictionary SELECT word FROM words;
-- Source: cookbook.mdx "One trie per partition / tenant"
CREATE OR REPLACE TABLE signups(day DATE, name TEXT);
INSERT INTO signups VALUES
(DATE '2024-01-01', 'Alice'),
(DATE '2024-01-01', 'Megan'),
(DATE '2024-01-02', 'Bob'),
(DATE '2024-01-02', 'Melissa'),
(DATE '2024-01-03', 'Charlie');
CREATE OR REPLACE TABLE name_tries AS
SELECT day,
marisa_trie(name) AS trie
FROM signups
GROUP BY day;
Build a compact dictionary with prefix lookups
A trie organizes strings by their shared prefixes. Marisa builds one from a DuckDB column and stores the dictionary as a BLOB. Queries can check membership, find strings beginning with a prefix, or find a prefix that matches a longer input.
Use it for a reusable vocabulary, a lookup dictionary, or autocomplete suggestions over a known list. The built dictionary is static: create a new trie when its contents change. For approximate spelling matches, use RapidFuzz.
Example
Find names with a common prefix
Build a trie from four names and request up to ten completions for Me.
Tested with DuckDB 1.5.6. Browser examples use Haybarn-Wasm 2.0.0-rc12.
SET allow_extension_repositories = 'allowed';
CREATE EXTENSION REPOSITORY IF NOT EXISTS query_farm
WITH PREFIX 'https://duckdb-extensions.query.farm';
INSTALL marisa FROM query_farm;
LOAD marisa FROM query_farm;
WITH names(name) AS (
VALUES ('Alice'), ('Bob'), ('Megan'), ('Melissa')
), dictionary AS (
SELECT marisa_trie(name) AS trie FROM names
)
SELECT marisa_predictive(trie, 'Me', 10) AS suggestions
FROM dictionary;
SET allow_extension_repositories = 'allowed';
CREATE EXTENSION REPOSITORY IF NOT EXISTS query_farm
WITH PREFIX 'https://haybarn-extensions.query.farm';
INSTALL marisa FROM query_farm;
LOAD marisa FROM query_farm;
WITH names(name) AS (
VALUES ('Alice'), ('Bob'), ('Megan'), ('Melissa')
), dictionary AS (
SELECT marisa_trie(name) AS trie FROM names
)
SELECT marisa_predictive(trie, 'Me', 10) AS suggestions
FROM dictionary;
INSTALL marisa FROM community;
LOAD marisa;
WITH names(name) AS (
VALUES ('Alice'), ('Bob'), ('Megan'), ('Melissa')
), dictionary AS (
SELECT marisa_trie(name) AS trie FROM names
)
SELECT marisa_predictive(trie, 'Me', 10) AS suggestions
FROM dictionary;
Expected result
| suggestions |
|---|
| ["Megan","Melissa"] |
A MARISA trie is static. Rebuild it when the source set changes. Prefix lookup is different from fuzzy matching: it does not correct spelling mistakes.
Common tasks
Deep Dive
Technical Details
What you can do with one query
Pack a column of strings into a single, self-contained BLOB — then run membership, predictive, and longest-prefix-match lookups against it forever:
-- Build once at ingest timeCREATE OR REPLACE TABLE words_trie AS SELECT marisa_trie(word) AS trie FROM dictionary;
-- Three lookups against the same BLOBSELECT marisa_lookup(trie, 'duckdb') AS exact, -- BOOLEAN marisa_predictive(trie, 'duck', 10) AS completions, -- VARCHAR[] marisa_common_prefix(trie, 'duckdbtools', 10) AS prefixes_of -- VARCHAR[]FROM words_trie;marisa_trie is the only constructor — an aggregate that emits a single BLOB. The three query primitives (marisa_lookup, marisa_predictive, marisa_common_prefix) read the BLOB directly. No decode step, no warm-up; the first query is as fast as the millionth.
A MARISA trie is built once and queried many times. There is no marisa_insert or marisa_delete — to add or remove keys, rebuild the trie from the updated source set. For a 470K-entry English wordlist that’s milliseconds; for billions of keys, plan an offline rebuild step.
The static design is what makes the structure succinct: keys are packed near the information-theoretic minimum, the BLOB is mmap-ready on load, and lookups don’t pay any synchronization cost. If your set churns continuously, a hash set or a bitfilters Quotient filter is a better fit.
What is MARISA?
MARISA — Matching Algorithm with Recursively Implemented StorAge — is a static, succinct Patricia / radix trie. The reference C++ implementation is s-yata/marisa-trie, maintained for over a decade. This extension is a thin DuckDB wrapper around that library.
A trie is the right data structure when:
- The strings have shared prefixes — URLs, paths, names, dictionary words. Prefix-rich data compresses dramatically.
- You need prefix queries — autocomplete, longest-prefix match, IP-CIDR routing — that hash sets and Bloom filters can’t answer at all.
- You want bounded lookup time — O(|key|), independent of dictionary size.
For random unrelated strings without prefix structure, a hash set or a Bloom / XOR / Binary Fuse filter from bitfilters will be smaller and faster.
Storage
Each marisa_trie call produces one BLOB. The BLOB is self-contained and portable — write it to a column, persist in Parquet, ship to another DuckDB instance. Loading is essentially a pointer-walk; there is no parsing or decompression step at query time.
A typical English-word trie of ~470K entries weighs in around 800 KB — roughly a fifth the size of the same words as a flat sorted list, before any column compression.
Lookup operations
| Operation | Function | Returns |
|---|---|---|
| Exact membership | marisa_lookup |
BOOLEAN |
| Predictive (autocomplete) | marisa_predictive |
VARCHAR[] |
| Longest-prefix-match | marisa_common_prefix |
VARCHAR[] |
All three run against the BLOB directly. The first query is as fast as the millionth.
MARISA vs bitfilters
Both extensions answer set-membership questions; they sit in the same Indexing sub-bucket on the catalog page for that reason. The mechanics are different in ways that matter:
marisa |
bitfilters |
|
|---|---|---|
| Stores the strings? | Yes — keys are recoverable | No — only a probabilistic fingerprint |
| False positives | None — answers are exact | Bounded (e.g. ~0.4% for xor8) |
| Prefix / predictive queries | Yes (marisa_predictive, marisa_common_prefix) |
No |
| Best when | Prefix-rich strings, autocomplete | Random keys, smallest possible memory |
| Mutation | Static — rebuild to update | Static (XOR / Fuse / Bloom) or dynamic (Quotient) |
Use MARISA when you need the strings back or you need prefix queries. Use bitfilters when you only need a yes/no on uncorrelated keys and memory is the binding constraint.
Pairings
- Build at ingest, query at runtime. Materialize one trie per user / partition / day at write time, then query at read time. The static design is a feature here — the trie won’t change underneath you.
- Pair with
fuzzycompleteorrapidfuzzfor fuzzy + prefix lookup pipelines: exact prefix via MARISA, fuzzy fallback via the others. - Use as the dictionary side of a join — much smaller wire size than transferring the underlying string list.
Limitations
- Static — no incremental insert or delete. Rebuild the trie from the updated source set.
- String-only. No numeric or composite keys.
- Lexicographic order only. If you need a different ordering at query time, build separate tries.
Reference
Extension Contents
Quick reference to all available functions and settings organized by category.
| Name | Type | Description |
|---|---|---|
|
Build
The aggregate that turns a column of strings into a single MARISA trie BLOB. Build once at ingest time, store the BLOB in any column type, query repeatedly. Updates require a rebuild — there is no incremental insert. |
||
| marisa_trie() | Object type: Aggregate function | Aggregate that builds a MARISA trie from a column of strings. |
|
Query
Membership tests, autocomplete (predictive prefix), and longest-prefix-match against an existing trie BLOB. All three primitives run in O(|key|) — lookup work is independent of dictionary size. |
||
| marisa_common_prefix() | Object type: Scalar function |
Returns VARCHAR[] — every string in the trie that is a prefix of the search string, capped at max_results.
|
| marisa_lookup() | Object type: Scalar function |
Returns BOOLEAN — true iff the search string is in the trie.
|
| marisa_predictive() | Object type: Scalar function |
Returns VARCHAR[] — every string in the trie that starts with the given prefix, capped at max_results.
|
No extension contents match that search.
API Reference
Function Reference
Practical Examples
Cookbook
Real-world recipes and patterns for common use cases.
Build a trie
marisa_trie is an aggregate — feed it a column of strings, get one BLOB back. Build at ingest time, store the BLOB, query forever.
CREATE OR REPLACE TABLE employees(name TEXT);INSERT INTO employees VALUES ('Alice'),('Bob'),('Charlie'),('David'),('Eve'),('Frank'), ('Mallory'),('Megan'),('Oscar'),('Melissa');
CREATE OR REPLACE TABLE employees_trie AS SELECT marisa_trie(name) AS trie FROM employees;
SELECT octet_length(trie) AS bytes FROM employees_trie;Trie size scales with shared-prefix density rather than raw input bytes; the more prefix structure your strings share, the bigger the win versus a flat sorted list.
Membership lookup (spell-check, dictionary)
marisa_lookup returns BOOLEAN — does this exact string exist in the trie?
SELECT marisa_lookup(trie, 'Alice') FROM employees_trie; -- TRUESELECT marisa_lookup(trie, 'Unknown') FROM employees_trie; -- FALSEThis is the spell-check / “is this term in our dictionary?” primitive. It also stands in for a hash set anywhere you’d otherwise pre-load one for IN (...)-style filtering.
Autocomplete (type-ahead UI)
marisa_predictive(trie, prefix, max_results) returns every entry in the trie whose prefix matches:
-- Names starting with 'Me'SELECT marisa_predictive(trie, 'Me', 10) AS suggestionsFROM employees_trie;-- ['Megan', 'Melissa']Drop this into the backend of a type-ahead search box: one row, one BLOB, microsecond lookups. The max_results cap is a hard cutoff so a short prefix against a million-entry dictionary doesn’t return the whole table.
Longest-prefix match (routing tables)
marisa_common_prefix is the inverse of predictive — every string in the trie that is itself a prefix of the search input:
CREATE OR REPLACE TABLE country_codes(code TEXT);INSERT INTO country_codes VALUES ('U'), ('US'), ('USA');
CREATE OR REPLACE TABLE country_codes_trie AS SELECT marisa_trie(code) AS trie FROM country_codes;
SELECT marisa_common_prefix(trie, 'USA', 10) AS matchesFROM country_codes_trie;-- ['U', 'US', 'USA']Useful for routing tables, IP-prefix labels, feature-flag rule lookups, and any “find every rule that matches this input” pattern.
Big static dictionary: English words
The classic MARISA workload — load a wordlist into a trie once, ship the BLOB inside a Parquet file:
-- Create a small wordlist; replace this file with your own for larger inputs.COPY (SELECT * FROM (VALUES ('duck'), ('duckdb'), ('query'), ('farm')) AS words(word))TO 'words.txt' (HEADER false);CREATE OR REPLACE TABLE words AS SELECT trim(column0) AS word FROM read_csv('words.txt', columns := {'column0': 'VARCHAR'});
CREATE OR REPLACE TABLE words_trie AS SELECT marisa_trie(word) AS trie FROM words;
-- Spell-checkSELECT marisa_lookup(trie, 'duckdb') FROM words_trie; -- TRUESELECT marisa_lookup(trie, 'qwxzy') FROM words_trie; -- FALSE
-- AutocompleteSELECT marisa_predictive(trie, 'duck', 8) FROM words_trie;-- ['duck','duckdb']For ~470K English words the resulting BLOB lands around 800 KB — about a fifth the size of the source list, queryable directly with no decode step.
Persist a trie to Parquet
The trie is just a BLOB — Parquet handles it natively. Build once, write, ship anywhere a DuckDB lives:
COPY (SELECT trie FROM words_trie) TO 'words_trie.parquet' (FORMAT 'parquet');
-- On the other sideCREATE OR REPLACE TABLE words_trie AS SELECT * FROM 'words_trie.parquet';
SELECT marisa_predictive(trie, 'rou', 5) FROM words_trie;Loading is a pointer-walk — no parsing, no decompression. Useful for shipping a fixed dictionary alongside an application without standing up a separate index service.
One trie per partition / tenant
Materialize one trie per logical partition (day, tenant, region) at write time. The set of tries is tiny compared to the source data and serves all three lookup operations at query time:
CREATE OR REPLACE TABLE name_tries ASSELECT day, marisa_trie(name) AS trieFROM signupsGROUP BY day;
-- Did a given name show up on a specific day?SELECT dayFROM name_triesWHERE marisa_lookup(trie, 'Megan');
-- All names that started with 'Me' on each daySELECT day, marisa_predictive(trie, 'Me', 20) AS matchesFROM name_triesORDER BY day;Updating a trie
There is no marisa_insert — to update, rebuild from the new source set:
-- Source set changed; rebuild the trieCREATE OR REPLACE TABLE words_trie AS SELECT marisa_trie(word) AS trie FROM words;For a dictionary that changes daily this is a millisecond-scale CTAS. For a billion-key set, schedule the rebuild offline and treat the trie as a build artifact.
When a trie vs a HashSet vs bitfilters
- Trie — wins when the data has shared prefixes (URLs, names, dictionary words) or you need prefix / predictive queries. Memory: roughly 30–60% of the equivalent flat string list. Lookup: O(|key|), independent of dictionary size.
- HashSet (DuckDB’s built-in
IN) — wins for small, random, unrelated string sets where simplicity dominates. bitfilters— wins for very large random key sets where you only need a yes/no answer and memory is the binding constraint. Doesn’t store the strings; can’t do prefix queries.
If you’re building autocomplete or have prefix-rich data, MARISA is the right structure. For pure membership tests on uncorrelated random strings, a Bloom / XOR / Binary Fuse filter is smaller. For evolving sets that need insert and delete, neither MARISA nor the static bitfilters variants apply — use a Quotient filter or a real index.
Platform Support
Compatibility
Extension availability may vary by platform and DuckDB version. Check below to ensure this extension supports your environment before installation.
Quick Facts
Platforms
DuckDB 2.0.0
- Linux x86_64aarch64
- Linux (musl) Not available
- macOS Apple Silicon
- Windows x86_64x86_64 (MinGW)
- WASM Not available
Compiled binary sizes
| Platform | Architecture | Size |
|---|---|---|
| Linux | x86_64 | 4.03 MB |
| Linux | aarch64 | 3.39 MB |
| macOS | Apple Silicon | 2.85 MB |
| Windows | x86_64 | 10.24 MB |
| Windows | x86_64 (MinGW) | 17.86 MB |
Compressed download sizes for the release shown above.
DuckDB & Haybarn
Release calendar- DuckDB v2.0.0 Query.Farm repository Supported
- Haybarn v1.5.6 Built-in community repository Supported
Browser examples use Haybarn-Wasm 2.0.0-rc12.
Checked .