Marisa

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 time
CREATE TABLE words_trie AS
  SELECT marisa_trie(word) AS trie FROM dictionary;

-- Three lookups against the same BLOB
SELECT
  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.

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

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:

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 fuzzycomplete or rapidfuzz for 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.

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 TABLE employees(name TEXT);
INSERT INTO employees VALUES
  ('Alice'),('Bob'),('Charlie'),('David'),('Eve'),('Frank'),
  ('Mallory'),('Megan'),('Oscar'),('Melissa');

CREATE 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;  -- TRUE

SELECT marisa_lookup(trie, 'Unknown') FROM employees_trie;  -- FALSE

This 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 suggestions
FROM 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 TABLE country_codes(code TEXT);
INSERT INTO country_codes VALUES ('U'), ('US'), ('USA');

CREATE TABLE country_codes_trie AS
  SELECT marisa_trie(code) AS trie FROM country_codes;

SELECT marisa_common_prefix(trie, 'USA', 10) AS matches
FROM 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:

-- Load any newline-delimited wordlist (e.g. /usr/share/dict/words on macOS/Linux)
CREATE TABLE words AS
  SELECT trim(column0) AS word
  FROM read_csv('/usr/share/dict/words', columns := {'column0': 'VARCHAR'});

CREATE TABLE words_trie AS
  SELECT marisa_trie(word) AS trie FROM words;

-- Spell-check
SELECT marisa_lookup(trie, 'duckling') FROM words_trie;        -- TRUE
SELECT marisa_lookup(trie, 'qwxzy')    FROM words_trie;        -- FALSE

-- Autocomplete
SELECT marisa_predictive(trie, 'duck', 8) FROM words_trie;
-- ['duck','duckbill','duckboard','ducker',...]

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 side
CREATE 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 TABLE name_tries AS
SELECT day,
       marisa_trie(name) AS trie
FROM signups
GROUP BY day;

-- Did a given name show up on a specific day?
SELECT day
FROM name_tries
WHERE marisa_lookup(trie, 'Megan');

-- All names that started with 'Me' on each day
SELECT day, marisa_predictive(trie, 'Me', 20) AS matches
FROM name_tries
ORDER BY day;

Updating a trie

There is no marisa_insert — to update, rebuild from the new source set:

-- Source set changed; rebuild the trie
CREATE 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.