20250205 - Use fuse.js

Context

To implement the Command Palette (triggered via ⌘-K / Ctrl-K), there is a requirement to enable cross-searching of table names and column names within the ER diagram.

Liam ERD currently has both a web version (erd-web) and a CLI version. At least initially, we want them to operate on the same codebase. Therefore, the solution should run on the client side rather than relying on a Node.js runtime.

We considered the following technologies as the primary tools for browser-based search functionality:

fuse.js
Orama

In Pull Request #652, we created a prototype search box using radix-ui (as used in fumadocs) and tested the speed and user experience using a benchmark project (mastodon/mastodon).

While Orama's pre-indexing offers high-speed performance, we observed that fuse.js, despite its O(n) search complexity, delivered comparable search speeds. Please refer to Pull Request #652 for detailed performance metrics.

Decision

We will adopt fuse.js, at least for the initial implementation.

See the positive aspects listed below for the rationale behind this decision.

Proof of Concept (PoC) Summary

In our PoC (Pull Request #652), we compared fuse.js and Orama for client-side search functionality. The key findings are as follows:

fuse.js provides efficient fuzzy search capabilities out-of-the-box, without needing additional configuration for stemming or indexing.

Orama excels in search speed due to pre-built inverted indexes and offers O(1) search performance, while fuse.js operates with O(n) complexity.

Despite the theoretical performance differences, practical benchmarks on a project of Mastodon's scale (99 tables) revealed that both libraries deliver comparable performance, with search times ranging from 0.1ms to 1.0ms.

Orama's pre-indexing time was approximately 30ms-100ms, initiated upon loading the application. fuse.js does not require pre-indexing, leading to simpler integration and faster initial load times.

Both libraries successfully handled partial matches during live typing. However, Orama struggled with exact matches for incorrectly typed queries (e.g., "expire_at" instead of "expires_at").

Based on these observations, fuse.js was chosen for its ease of implementation and sufficient performance, especially for initial deployments where the data scale is moderate.

Consequences

Positive

Simple configuration
Enables easy fuzzy search
- No need for stemming configuration

Negative

Search speed may become an issue when handling larger RDBMS table sizes
Search performance might degrade when dealing with a more diverse set of searchable items