Full Text Search with IndexedDB

Author: singpolyma@singpolyma.net Date: 2026-098 Tags: javascript, database, tech, borogove Source: https://blog.jmp.chat/b/2026-full-text-search-indexeddb

Overview

The article discusses implementing full-text search for locally-stored chat message history in Borogove, a web-based application using IndexedDB as its storage engine. The author explores practical approaches to overcome IndexedDB's lack of built-in full-text search capabilities.

Key Concept

Full-text search, as defined here, means finding messages containing all words the user typed, regardless of order.

Table Scan Approach

The foundational solution involves iterating through all stored messages. While simple, this works well for datasets under 10,000 documents.

Helper Function

The implementation begins with a utility to convert IndexedDB requests into promises:

function promisifyRequest(request) {
	return new Promise((resolve, reject) => {
	  request.oncomplete = request.onsuccess = () => resolve(request.result);
	  request.onabort = request.onerror = () => reject(request.error);
	});
}

Tokenization

Text is processed into searchable components:

const stopwords = ["and", "if", "but"];
function tokenize(s) {
	return s.toLowerCase().split(/\s*\b/)
		.filter(w => w.length > 1 && w.match(/\w/) && !stopwords.includes(w));
}

This function converts text to lowercase, splits on word boundaries, removes single characters, filters non-word content, and excludes common "stopwords" that don't aid searching.

Stemming (Optional)

The author mentions stemming as an optional enhancement, allowing searches for "flying" to match documents containing "fly." Porter2 stemmer is referenced as an external option.

Basic Search Implementation

async function search(q) {
	const qTerms = new Set(tokenize(q).map(stemmer));
	const tx = db.transaction(["messages"], "readonly");
	const store = tx.objectStore("messages");
	const cursor = store.openCursor();

	const result = [];
	while (true) {
        const cresult = await promisifyRequest(cursor);
        if (!cresult?.value) break;

		if (new Set(tokenize(cresult.value.text).map(stemmer)).isSupersetOf(qTerms) {
			result.push(cresult.value);
		}
		cresult.continue();
	}

	return result;
}

Index-Based Approach

For larger datasets (one million+ messages), indexing dramatically improves performance. This method uses "an ordered index, usually built on a B-Tree."

Creating the Index

In the database upgrade handler:

tx.objectStore("messages").createIndex("terms", "terms", { multiEntry: true });

The multiEntry flag creates separate index entries for each term in an array, rather than treating the array as a single value.

Storing Messages with Terms

Messages should include pre-tokenized terms:

tx.objectStore("messages").put({ text, terms: [...new Set(tokenize(text).map(stemmer))] });

Optimized Search with Index

The enhanced search identifies which query term matches the fewest messages, then scans only that smaller subset:

async function search(q) {
	const qTerms = new Set(tokenize(q).map(stemmer));
	const tx = db.transaction(["messages"], "readonly");
	const store = tx.objectStore("messages");
	const index = store.index("terms");
	
	// Find the term with smallest match count
	let probeTerm = null;
	let probeScore = null;
	for (const term of qTerms) {
		const score = await promisifyRequest(index.count(IDBKeyRange.only(term)));
		if (!probeTerm || score < probeScore) {
			probeTerm = term;
			probeScore = score;
		}
	}
	
	// Scan only messages matching the rarest term
	const result = [];
	const cursor = index.openCursor(IDBKeyRange.only(probeTerm));
	while (true) {
		const cresult = await promisifyRequest(cursor);
		if (!cresult?.value) break;
		if (new Set(cresult.value.terms).isSupersetOf(qTerms)) {
			result.push(cresult.value);
		}
		cresult.continue();
	}

	// Manual sorting by timestamp
	return result.sort((a, b) => a.timestamp < b.timestamp ? -1 : (a.timestamp > b.timestamp ? 1 : 0));
}

Performance Results

Testing with one million messages demonstrated that "the simple index was enough to take the performance from unusable grinding to almost instant responses" because the rarest search term typically matches fewer than 10,000 documents.

License

This work is shared under Creative Commons Attribution ShareAlike 4.0.