completype 0.1.0

completype is a serverless autocompletion engine. In the spirit of LanceDB, it is a library, not a service: your application embeds it (Rust, or Python through first-class bindings), and an object-store bucket or a local directory is the database. There is no cluster to deploy, scale, upgrade or keep alive. Every process that serves completions reads the index straight from storage, and writers coordinate through the storage itself.

You give it documents (an id, a text, a popularity weight, and optionally aliases and an embedding), and it completes what your users type: every kind of match an autocomplete box needs, ranked together, and kept fresh while your data changes.

Contents

• Serverless by design
• Features
• What it completes
• Installation
• Quick start
• Guides: documents, filtering, synonyms, layers, semantic and hybrid, databases, asyncio, collections, command line, configuration
• Benchmarks
• Guarantees and testing
• Non-features
• FAQ
• Contributing · License

Serverless by design

flowchart LR
    W["Any process<br/>txn.commit()"] -- "create-only commit" --> M
    W -- "new segments" --> S
    subgraph B["Bucket or directory: the database"]
        M["_versions/ manifests"]
        S["segments/ immutable files"]
    end
    M -- "new versions" --> F1["Your app + completype<br/>engine.complete(...)"]
    S -- "changed segments" --> F1
    M --> F2["Your app + completype"]
    S --> F2
    M --> F3["Your app + completype"]
    S --> F3

• Storage is the only shared component. Manifests and segments are plain objects on S3, GCS, Azure or a file system. Nothing else runs between your processes.
• Commits are create-only writes. Version N + 1 is written with If-None-Match (exclusive create on a file system), so concurrent writers never corrupt each other; a loser retries on the newer version.
• Readers scale with your application. Each engine syncs itself in the background, loads only changed, immutable segments (memory-mapped from local disk or the optional disk cache) and switches versions atomically. Add capacity by adding replicas of your own app.
• Queries never leave the process, so there is no network hop on the hot path.

Features

Matching

• Exact and prefix completion as users type, over whole titles and their words.
• Infix matching: queen finds Dancing Queen – ABBA.
• Abbreviations: RHCP completes Under the Bridge – Red Hot Chili Peppers. Abbreviations match exactly, so short codes do not flood the results.
• Synonyms: alternative names that are prefix-searchable and point back to their document, searched on their own so they never displace a direct match.
• Spelling correction of up to two edits per word, SymSpell-style, verified with rapidfuzz: bohemain rapsody finds Bohemian Rhapsody – Queen.
• Word decomposition: run-together input such as dancingqueen is split into words and completed.
• Semantic completion from embeddings of any model, quantised to 2-4 bits.
• Hybrid completion with reciprocal rank fusion, weighted blending or lexical-first ordering, chosen per request.
• Context filters: restrict any request to documents tagged with a category, tenant or language.
• Your own ids: integers or strings such as UUIDs, returned with every suggestion as given. Documents with the same title stay separate results.

Ranking

• Popularity through a per-document weight, combined with match kind, text length and whole-word bonuses.
• Every suggestion carries its text, match kind and highlight ranges, so your UI renders it directly.
• Deterministic: identical inputs give bit-identical scores and order, with ties broken by id.

Serving

• Fast: p50 around 0.1 ms and p99 under 3 ms for typed queries on 200k documents, on one core.
• Zero-copy segments: an aligned, checksummed binary format read in place through mmap. Opening a segment takes under a millisecond and reads only its headers. Texts are FSST-compressed and decoded one at a time.
• Compact index: titles are found through documents sorted by title, words by binary search over their sorted texts, spelling variants through Elias-Fano coded buckets, and postings are delta coded in blocks, so the 7.2 million English Wikipedia titles index into 338 MB, less than tantivy's 357 MB.
• Streaming builds: documents stream into a SegmentBuilder (completype.Segment.build(rows, path=...) in Python), which keeps them compactly and writes each section to the file as it is produced. Indexing the 124,440 HN titles takes 0.29 s and peaks at 59 MB.
• Bounded indexing memory: a SegmentWriter starts a new segment file whenever building the current one would pass its memory budget (256 MB by default), so any corpus indexes in bounded memory. The segments rank exactly like one, and compaction merges them through their sorted dictionaries, byte for byte as a rebuild would: all of English Wikipedia, 7.2 million titles, is written and compacted into one segment in 25.6 s, and 40 million MusicBrainz recordings in 317 s with a peak of 547 MB.
• Override layers: one catalogue, many views. Tenants, languages, listeners, promotions, takedowns and experiments are small indexes stacked on the shared data, overriding it per document id, without a copy.
• A short-query cache for one- to three-character prefixes, carried across index versions.

Serverless updates

• Immutable segments, as in Lucene and LanceDB: updates land as small delta segments, and tiered compaction merges them.
• Versioned databases on local disk, S3, GCS, Azure or memory, with optimistic, create-only commits and automatic retries.
• Engines that follow the database: an engine from db.engine() loads new versions in a background thread, with no sync loop to write.
• One ingestor, many writers, when you need it: any process submits change sets, and a lease-elected Ingestor commits them in order.
• Credentials like boto3: environment, profiles, SSO, web identity, ECS and IMDS.

Developer experience

• Documents as dicts, completype.Document objects, or pandas, polars and Arrow tables, with int or string ids.
• Indexes, engines, databases and transactions at the top level of completype, an asyncio API, typed stubs and a clear exception hierarchy.
• Collections on top, for named collections that compact themselves.
• A completype command-line tool, and tracing events that also reach Python's logging.

What it completes

Real results from the index behind the demo above (23 short titles with popularity weights):

Installation

pip install completype

cargo add completype --features store                       # databases on local disk and in memory
cargo add completype --features aws-credentials,gcp,azure   # plus S3, GCS and Azure
cargo add tokio --features macros,rt-multi-thread         # the database API is async

The Python wheel includes all features. It is abi3 for CPython 3.11+, and releases the GIL while it searches and builds.

Quick start

Python

import completype
from completype import Index

docs = [   # also completype.Document objects, pandas, polars or Arrow tables
    {"id": "bohemian", "text": "Bohemian Rhapsody – Queen", "popularity": 0.95, "synonyms": ["is this the real life"]},
    {"id": "dancing", "text": "Dancing Queen – ABBA", "popularity": 0.85},
    {"id": "dark", "text": "Dancing in the Dark – Bruce Springsteen", "popularity": 0.7},
    {"id": "bridge", "text": "Under the Bridge – Red Hot Chili Peppers", "popularity": 0.75, "abbreviations": ["RHCP"]},
]
index = Index.from_documents(docs)   # in memory

for query in ["danc", "RHCP", "bohemain rapsody", "queen"]:
    print(query, [(s.text, s.kind, round(s.score, 3)) for s in index.complete(query, limit=3)])

danc [('Dancing Queen – ABBA', MatchKind.PREFIX, 0.547), ('Dancing in the Dark – Bruce Springsteen', MatchKind.PREFIX, 0.462)]
RHCP [('Under the Bridge – Red Hot Chili Peppers', MatchKind.ABBREVIATION, 0.486)]
bohemain rapsody [('Bohemian Rhapsody – Queen', MatchKind.FUZZY, 0.186)]
queen [('Bohemian Rhapsody – Queen', MatchKind.INFIX, 0.356), ('Dancing Queen – ABBA', MatchKind.INFIX, 0.329)]

Each suggestion carries its id (an int or the string you gave), text, score, kind, layer (the index it came from, in a layered search), and highlights: character ranges of the text that matched, ready to render in bold.

top = index.complete("danc")[0]
[top.text[a:b] for a, b in top.highlights]   # ['Danc']

A database keeps named indexes in a directory or bucket. A transaction commits a new version, and an engine from the database serves it, loading newer versions by itself every sync_every seconds (5 by default):

db = completype.connect("./data")   # or "s3://bucket/prefix", "gs://...", "az://...", "memory://"
txn = db.begin()
txn.append("songs", docs)   # upserts; deletes=[...] removes ids
txn.commit()

engine = db.engine()
engine.complete("danc", ["songs"])   # [Suggestion(id='dancing', ...), Suggestion(id='dark', ...)]

Other processes that open the same database and take an engine see the commit within sync_every seconds; engine.sync() loads it at once.

Rust

use std::{sync::Arc, time::Duration};
use completype::{Database, Document, Engine, Index, IndexOptions, Replica};

let docs = || [
    Document::keyed("bohemian", "Bohemian Rhapsody – Queen", 0.95).with_synonym("is this the real life"),
    Document::keyed("dancing", "Dancing Queen – ABBA", 0.85),
    Document::keyed("dark", "Dancing in the Dark – Bruce Springsteen", 0.7),
    Document::keyed("bridge", "Under the Bridge – Red Hot Chili Peppers", 0.75).with_abbreviation("RHCP"),
];
let index = Index::from_documents(docs())?;
for s in index.complete("danc", 10) {
    println!("{} {} {:.3} {:?}", s.text, s.kind.as_str(), s.score, s.highlights);
}

let database = Database::open("./data", Vec::<(String, String)>::new()).await?;
let mut txn = database.begin().await?;
txn.append_documents("songs", docs(), [])?;
txn.commit().await?;

let engine = Arc::new(Engine::new());
let replica = Arc::new(Replica::new(database, IndexOptions::default()));
replica.sync(&engine).await?;
let _follower = replica.follow(&engine, Duration::from_secs(5));   // syncs until dropped
let hits = engine.complete(&["songs"], "danc", 10)?;

Runnable versions: quickstart.rs and quickstart.py.

Guides

Documents

Unknown fields raise InvalidInputError, so a typo never silently drops data.

Filtering by context

Tag documents with contexts and restrict any request to them. Filtering happens while candidates are collected, so a filtered request still returns up to limit results.

index = completype.Index.from_documents([
    {"id": "dancing", "text": "Dancing Queen – ABBA", "popularity": 0.85, "contexts": ["pop", "disco"]},
    {"id": "dark", "text": "Dancing in the Dark – Bruce Springsteen", "popularity": 0.7, "contexts": ["rock"]},
    {"id": "ownown", "text": "Dancing On My Own – Robyn", "popularity": 0.5, "contexts": ["pop"]},
])
[s.text for s in index.complete("danc", contexts=["pop"])]
# ['Dancing Queen – ABBA', 'Dancing On My Own – Robyn']
[s.text for s in index.complete("danc", contexts=["disco", "rock"])]   # any of the contexts
# ['Dancing Queen – ABBA', 'Dancing in the Dark – Bruce Springsteen']

engine.complete(...) and hybrid_search(...) take the same contexts.

Synonyms

Synonyms are searched with complete_aliases, apart from direct matches, so an alternative name never displaces what the user typed. Suggestions carry the document's text:

index.complete_aliases("is this the real")   # [AliasSuggestion(id='bohemian', text='Bohemian Rhapsody – Queen', ...)]

Layers

One catalogue, many views. An engine searches a stack of indexes, and later layers override earlier ones per document id. A tenant, a language, a listener or an experiment gets a small index holding only what differs (edits, deletions, additions, different popularity) on top of the shared catalogue, which is built and held once:

txn = db.begin()
txn.append("radio", [{"id": "bohemian", "text": "Bohemian Rhapsody (Remastered 2011) – Queen", "popularity": 0.95},
                     {"id": "session", "text": "Dancing Queen (Live Session) – ABBA", "popularity": 0.8}],
           deletes=["killer"])   # a station's edits, exclusives and removals
txn.commit()

stack = ["catalog", "catalog-de", "radio", f"user-{user_id}", "takedowns"]
[(s.text, s.layer) for s in engine.complete("queen", stack, ignore_missing_layers=True)]
# [('Bohemian Rhapsody (Remastered 2011) – Queen', 'radio'), ('Dancing Queen – ABBA', 'catalog'),
#  ('Dancing Queen (Live Session) – ABBA', 'radio')]

• Tenants rename, hide and add songs without a copy of the catalogue.
• Locales raise local charts and add local songs, titles and abbreviations.
• Listeners get their own plays ranked first, from a layer that builds in under a millisecond.
• Promotions, takedowns and experiments are layers published atomically, with no rebuild.

Scores from every layer are on the first layer's scale, so an unchanged copy ranks exactly where it did. Five layers over 200,000 titles answer in 0.2 ms at the median. A layer that does not exist raises LayerNotFoundError unless the query passes ignore_missing_layers=True.

Layers stack within a namespace: a set of indexes, such as one locale's catalogue and its tenants' layers, that the engine switches to a new version in one step. engine.namespace("de") holds that version for a request, so every search through it agrees:

with db.namespace("de").begin() as txn:     # commits at the end of the block
    txn.append("catalog", songs_de)
    txn.append("radio", radio_edits_de)

de = engine.namespace("de")                 # Namespace(name='de', version=1, indexes=['catalog', 'radio'])
de.complete("99", ["catalog", "radio"])

See Layers for each pattern with its output.

Semantic and hybrid completion

Documents can carry embeddings from any model. completype quantises them with TurboQuant (4 bits by default, 2 or 3 optional) and searches them with deleted and filtered-out documents masked out.

vectors = embed([d["text"] for d in docs]).astype("float32")   # shape (n, dim)
index = Index.from_documents(docs, vectors=vectors)              # or txn.append(..., vectors=vectors)

index.hybrid_search("dancing q", embed(["dancing q"])[0])                       # fused by reciprocal rank
index.hybrid_search("dancing q", embed(["dancing q"])[0], fusion="weighted")    # or "lexical_first"
index.vector_search(embed(["disco classics"])[0])                               # kind == "semantic"

A hybrid suggestion keeps its lexical match kind when it matched lexically, and is semantic otherwise. It also reports both source scores.

Databases on disk and in buckets

completype.connect(url) opens a versioned database in a directory or bucket, and creates a local one if it does not exist. Commits go straight to storage, durable on return; concurrent writers retry on the newer version. Engines sync themselves in a background thread.

import completype

# Any process that writes:
db = completype.connect("s3://my-bucket/completions")   # or a local path, gs://..., az://...
txn = db.begin()
txn.append("songs", [{"id": f"s{i}", "text": f"song {i}"} for i in range(10_000)], deletes=["s42"])
txn.commit()

# Every serving process: the engine picks up new versions every sync_every seconds.
engine = completype.connect("s3://my-bucket/completions", cache_dir="/var/cache/completype").engine(sync_every=5.0)
engine.complete("danc", ["songs"])

Runnable: live_updates.py.

• Status: engine.version is the version served, and engine.sync_status the last background sync's synced_at and error.
• Compaction: db.compact("songs") merges small segments tier by tier; an ingestor does it for you.
• Cleanup: db.cleanup(keep_versions=10, older_than_seconds=3600) deletes old manifests, and segment files that no retained version references.
• Many writers: db.submit(changes) queues a ChangeSet, and a lease-elected Ingestor commits queued change sets in order.
• Forking servers: open databases and engines in each worker after a pre-forking server forks.
• Credentials: S3 uses the standard AWS chain. Override it with options={"aws_access_key_id": ..., "aws_region": ...}, and pass cache_dir=... to keep downloaded segments on local disk.

asyncio

completype.AsyncDatabase has the same methods as a database, awaited, for FastAPI and other asyncio services. Constructing it does not block; storage opens on the first awaited call. Completions stay synchronous: they take well under a millisecond.

db = completype.AsyncDatabase("s3://my-bucket/completions")
txn = await db.begin()
txn.append("songs", [{"id": "billie", "text": "Billie Jean – Michael Jackson", "popularity": 0.9}])
await db.commit(txn)
engine = await db.engine()
engine.complete("bill", ["songs"])

See the FastAPI example.

Collections

completype.Client is a convenience layer on top: named collections with stored settings, that compact themselves after writes, report stats(), and complete synonyms below direct matches in one call. Each collection is an index of the same name.

client = completype.Client("./data")
songs = client.get_or_create_collection("songs")
songs.add([{"id": "bohemian", "text": "Bohemian Rhapsody – Queen", "popularity": 0.95, "synonyms": ["is this the real life"]}])
songs.complete("is this the real", aliases=True)   # [Suggestion(id='bohemian', ..., kind=MatchKind.SYNONYM)]

It does not expose index options, the choice of fusion, or getting documents by id; client.database returns the database underneath. In Rust, completype::connect returns this client. See Collections.

Command line

The completype tool operates a database from a terminal or a cron job. Every command takes the database URL first (or COMPLETYPE_URL).

cargo install completype-cli

completype s3://my-bucket/completions import songs songs.jsonl   # JSON Lines documents
completype s3://my-bucket/completions complete songs "danc" --contexts pop
completype s3://my-bucket/completions inspect                    # versions, indexes, sizes
completype s3://my-bucket/completions compact songs
completype s3://my-bucket/completions cleanup --keep-versions 10
completype s3://my-bucket/completions ingest --interval 1         # run an ingestor

Engine events are logged to stderr; set COMPLETYPE_LOG=completype=debug for more.

Errors

Every error derives from completype.CompletypeError: ConflictError, CorruptionError, NotFoundError (also a LookupError) with NamespaceNotFoundError and LayerNotFoundError under it, InvalidInputError (also a ValueError) and StorageError (also an OSError). The not-found errors carry the missing name and the names that do exist in available, and suggest a name when the missing one looks like a typo:

LayerNotFoundError: no index 'custmer-a' in namespace 'de-DE' at version 3 (did you mean 'customer-a'?); indexes: customer-a, customer-b, shared; set ignore_missing_layers if it may not exist

Configuration

In Rust, BuildOptions, IndexOptions, SearchOptions, HybridOptions, CompactionPolicy and CleanupPolicy expose the same settings through chainable setters, e.g. SearchOptions::new(5).contexts(["pop"]). The configuration guide lists every setting, including the collections layer's.

Benchmarks

Against other engines. On five corpora, from 124,440 Hacker News titles to all 40 million MusicBrainz recordings, 39.6 million Amazon search terms and 41.7 million Open Library works, typed character by character, completype ranks the wanted title best of tantivy, Typesense and Meilisearch in 19 of 20 comparisons (popular and uniformly drawn targets, typed cleanly and with a typo). On 20,000 prefixes Amazon's users really typed, it has the searched term in its top 10 for 28.5% of them, against 25.2% for Meilisearch and 23.8% for tantivy. In process it answers 40 million MusicBrainz recordings in 1.5 to 3.0 ms at the median, with every p99 below every other engine's, and serves 1,355 queries per second on 8 threads, 14 times tantivy. Its index is the smallest on every corpus above HN (MusicBrainz: 3.1 GB, against 5.9 GB for tantivy and 39.5 GB for Meilisearch). tantivy still indexes the two largest corpora faster. Full tables, a capability comparison, where the bytes go, settings and caveats are in docs/benchmarks.md; the harness is in bench/.

On a synthetic corpus.

A synthetic corpus of 200,000 documents (1 to 4 words from a 30,000-word vocabulary, Zipf-distributed), on one core of an Apple M1 Pro. Reproduce with cargo run --release -p completype --example bench -- 200000 --vectors.

The vector rows come from the same run with --vectors, whose segment is 32.8 MB.

One- and two-character prefixes, which match large parts of the corpus, dominate the tail. The short-query cache serves them, and replicas carry its hottest entries across index versions.

Guarantees and testing

• Determinism: results depend only on the documents and settings, not on how the index was segmented, compacted or queried concurrently. The tests re-run queries sampled under concurrent updates, on the same snapshot and on a freshly built index, and require bit-identical output.
• Concurrency: readers never block. New index versions are published atomically, and a reader keeps the version it started with.
• Integrity: every segment ends with an xxh3 checksum. Segment::open checks a local file's structure only; Segment::verify, Segment::from_bytes and downloads into a store's cache check the checksum and every section. Stable-Rust fuzz tests feed in truncated, bit-flipped and garbage segments, random Unicode queries and corrupted manifests.
• Memory: replicas replace indexes group by group, and release old segments before loading the next group. In a soak test over thousands of versions, serving memory stayed flat.

cargo test --release -p completype --features store          # unit, database, concurrency and fuzz tests
COMPLETYPE_FUZZ_ITERS=1000000 cargo test --release -p completype --features store --test fuzz

Non-features

completype does one job. It deliberately does not include:

• a server or HTTP API; it is serverless by design, so expose it through your own API if you need one;
• full-text search over long documents, filtering or faceting;
• multi-field schemas; each document has one text, plus aliases and an optional embedding;
• built-in embedding models; bring vectors from any model;
• sharding across machines; one index is expected to fit on one machine, memory-mapped.

FAQ

What does "serverless" mean here? The same as for LanceDB: there is no completype server. The engine is a library in your process, and the database is a set of files in a bucket or directory. Your application is still deployed however you like, on containers, VMs or functions; completype adds no extra service to it.

How does completype differ from Elasticsearch, OpenSearch, Typesense or Meilisearch? Those are search servers for documents with many fields, filters and facets: you run and scale a cluster, and every query crosses the network. completype is serverless and does autocompletion only: it runs inside your process, and ranks the match kinds a completion box needs (abbreviations, spelling correction, word decomposition) together with popularity. Many applications use both: a search server for the results page, completype for the box.

How do several writers avoid conflicts without a server? Through the store. Commits create the next manifest create-only, so exactly one writer wins each version and the others rebase and retry. For high write rates, processes can instead submit change sets to an inbox, and a single Ingestor elected by an expiring lease commits them in order. Every commit carries the lease generation as a fencing token, so an ingestor that lost its lease cannot commit.

How does it differ from an FST or trie library? fst and marisa-trie are excellent key dictionaries, and completype uses the same ideas internally. On top of them it adds scoring, typo tolerance, abbreviations, semantic search, updates without rebuilding, and storage.

Which languages does it support? Text is normalised with Unicode lowercasing and split on Unicode whitespace, so any language written with spaces works as it is. For scripts written without spaces, such as Chinese and Japanese, pass text segmented into words to get infix matching.

How large can an index be? A segment is memory-mapped and costs roughly 100 bytes per short title, plus about 136 bytes per 256-d vector at 4 bits. Hundreds of thousands to a few million documents per index fit comfortably on one machine.

Why the name? completype is said "completer": it completes what people type, and the missing vowel is a nod to search-engine names such as Solr. Its wordmark shows the name being completed as you type it.

How it works

A segment stores its documents in zstd-compressed blocks, and its keys in three dictionaries: titles, title words and aliases. SymSpell delete variants for spelling correction are hashed into buckets of word ordinals. Popularity and title length are kept in aligned columns, and postings are bit-packed. Queries run on primitives merged across segments (cursor merges over the sorted dictionaries), so an index of many segments ranks exactly like a single one. See docs/architecture.md for the format, the ranking and the database protocol.

Status

completype is young. The on-disk format is versioned and checked on load, but it and the API may still change before 1.0. Feedback and issues are very welcome.

Contributing

Contributions are welcome. Please read CONTRIBUTING.md and the Code of Conduct. To report a vulnerability, see SECURITY.md.

Acknowledgements

completype builds on excellent work: fst by Andrew Gallant, rapidfuzz, turbovec, object_store, zstd and PyO3. Its trie design is inspired by marisa-trie, its spelling correction and word decomposition by SymSpell, and its database protocol by Lance. The wordmark and demo use outlines of Space Grotesk and Source Sans 3.

License

MIT. Developed and maintained by Saiful Islam.