# @coda/search

Search engine primitives for building hybrid (keyword + vector) search systems. All algorithms run in-process with no external dependencies — suitable for embedding in any service.

## Installation

```jsonc
// package.json
{ "dependencies": { "@coda/search": "workspace:*" } }
```

## Why Hybrid Search?

Keyword search ([BM25](docs/concepts.md#bm25-keyword-scoring)) is fast and precise for exact terms but misses synonyms.
Vector search captures semantic similarity but requires embeddings and is slower.
[Glossary boosting](docs/concepts.md#glossary-matching) injects domain knowledge to override both when curated terms match.

[RRF fusion](docs/concepts.md#rrf-score-fusion) combines all three without training data or labeled relevance judgments —
each signal produces a ranked list, and RRF merges them by reciprocal rank.

### Why does this matter? (measured)

Each signal layer improves retrieval quality. Ablation study on 15 labeled schema queries:

| Configuration        | NDCG@10 | MRR   | Delta             |
| -------------------- | ------- | ----- | ----------------- |
| BM25 keyword only    | 0.866   | 0.867 | —                 |
| + glossary expansion | 0.929   | 0.967 | +0.063            |
| + graph signals      | 0.851   | 0.856 | -0.079 (see note) |

Glossary expansion adds +0.063 NDCG by mapping domain terms ("royalties", "advance") to schema identifiers that BM25 alone misses. Graph signals (degree, adamic-adar, betweenness, column-density) help at scale — on the full 82-table corpus with 189 golden queries, the production system achieves **NDCG=0.887, MRR=0.943, Recall@10=0.994**. On small corpora (<20 tables), keyword+glossary is already precise enough that graph signals can dilute rankings.

**Why RRF over linear combination?** RRF is rank-based: it rewards documents that appear near the top of multiple signals without requiring score calibration. A BM25 score of 12.3 and a cosine similarity of 0.87 are incomparable — RRF doesn't care, it only uses ranks. Linear combination (used by Orama, txtai's default) requires manual weight tuning or Bayesian calibration (txtai's BB25) to normalize scores across signals. RRF works out of the box with any number of heterogeneous signals.

### When to use @coda/search

| Use case                                    | Best tool                                                                                                                           |
| ------------------------------------------- | ----------------------------------------------------------------------------------------------------------------------------------- |
| Schema/metadata discovery for AI agents     | **@coda/search** — purpose-built with graph signals, glossary expansion, and in-process operation                                   |
| General-purpose full-text search (<2KB)     | [MiniSearch](https://github.com/lucaong/minisearch) or [Orama](https://github.com/oramasearch/orama) — simpler API, browser support |
| Document QA with knowledge graphs           | [LightRAG](https://github.com/hkuds/lightrag) — LLM-powered entity extraction and graph construction                                |
| Search infrastructure at scale (100K+ docs) | Elasticsearch, Meilisearch, or Typesense — external servers with horizontal scaling                                                 |
| Python ecosystem with BM25+vector+graph     | [txtai](https://github.com/neuml/txtai) — broadest Python search framework                                                          |

**BM25 performance vs MiniSearch** (16-doc schema corpus, same tokenizer):

| Metric         | @coda/search | MiniSearch            |
| -------------- | ------------ | --------------------- |
| Indexing speed | 0.072ms      | 0.109ms (1.5x slower) |
| Search latency | 1.1us        | 4.0us (3.7x slower)   |
| NDCG@10        | 0.944        | 0.952                 |
| MRR            | 1.000        | 1.000                 |

BM25 quality is comparable; our advantage comes from the additional 9 signals (glossary, graph, fuzzy, vector) that MiniSearch cannot provide.

## Documentation

- **[Getting Started](docs/getting-started.md)** — build a working search engine in ~60 lines
- **[Examples](examples/)** — progressive standalone scripts (keyword → glossary → custom signal → lifecycle)
- [Concepts](docs/concepts.md) — hybrid search theory, BM25, HNSW, RRF explained
- [Pipeline Architecture](docs/pipeline.md) — expanders, stages, signals, fusion
- [Tuning Guide](docs/tuning.md) — parameter guidance for production use
- [Engine Lifecycle](docs/engine.md) — init, refresh, search, destroy
- [Extending](docs/extending.md) — custom stages, signals, expanders, scorers
- [Cookbook](docs/cookbook.md) — recipes: new data source, custom signal, glossary, graph, filters, events

## Overview

This package provides three categories of search, plus tools for combining them:

| Category     | Key exports                                      | Algorithm                                                       |
| ------------ | ------------------------------------------------ | --------------------------------------------------------------- |
| **Keyword**  | `Bm25Scorer`, `TfidfScorer`, `InvertedIndex`     | [BM25](docs/concepts.md#bm25-keyword-scoring), TF-IDF           |
| **Vector**   | `HnswIndex`, `QuantizedHnswIndex`, `VectorIndex` | [HNSW](docs/concepts.md#hnsw-vector-search), brute-force ANN    |
| **Glossary** | `matchGlossary`, `buildGlossaryContextMap`       | [Exact/fuzzy term matching](docs/concepts.md#glossary-matching) |
| **Hybrid**   | `HybridSearch`                                   | Combines all three via [RRF](docs/concepts.md#rrf-score-fusion) |

## Dependencies

This package depends on `@coda/data-structures` which provides the data structures used internally — heaps, sorted arrays, and graph types (`ReadonlyGraph`). These power the [HNSW](docs/concepts.md#hnsw-vector-search) neighbor selection, top-K result extraction, and [graph-based ranking signals](docs/concepts.md#graph-signals). The only external dependency is `lru-cache` for [query embedding caching](docs/concepts.md#query-embedding-cache-and-in-flight-dedup).

## Keyword Search

```ts
import { Bm25Scorer, InvertedIndex, tokenize } from "@coda/search";

// Build an inverted index from documents
const index = new InvertedIndex<string>();
const docs = [
  { id: "d1", text: "music royalties and contracts" },
  { id: "d2", text: "artist revenue reporting" },
  { id: "d3", text: "contract terms and royalty rates" },
];
for (const doc of docs) {
  index.add(doc.id, tokenize(doc.text));
}

// Score a query using BM25
const scorer = new Bm25Scorer({ k1: 1.5, b: 0.75 });
const results = scorer.score(tokenize("royalty contract"), index, docs.length);
// results: [{ id: "d3", score: ... }, { id: "d1", score: ... }]
```

| Export          | Description                                                                                                                  |
| --------------- | ---------------------------------------------------------------------------------------------------------------------------- |
| `Bm25Scorer<T>` | [BM25](docs/concepts.md#bm25-keyword-scoring) ranking with configurable [`k1`, `b`](docs/tuning.md#parameters), delta params |
| `bm25`          | Stateless BM25 scoring function                                                                                              |
| `TfidfScorer`   | TF-IDF scoring                                                                                                               |
| `tfidf`         | Stateless TF-IDF function                                                                                                    |
| `InvertedIndex` | Token-to-document inverted index                                                                                             |
| `Bm25Config`    | Configuration: `k1`, `b`, `delta`                                                                                            |
| `KeywordScorer` | Interface for [pluggable keyword scorers](docs/extending.md#custom-keywordscorer)                                            |

## Vector Search

```ts
import { HnswIndex } from "@coda/search";

// Create an HNSW index for 384-dimensional embeddings
const index = new HnswIndex<string>({
  dimensions: 384,
  m: 16,
  efConstruction: 200,
});

// Add documents (embeddings from your model)
index.add("doc1", new Float32Array(384).fill(0.1));
index.add("doc2", new Float32Array(384).fill(0.2));

// Search for nearest neighbors
const results = index.search(new Float32Array(384).fill(0.15), 10);
// results: [{ id: "doc2", score: ... }, { id: "doc1", score: ... }]
```

| Export                  | Description                                                                                        |
| ----------------------- | -------------------------------------------------------------------------------------------------- |
| `HnswIndex<K>`          | [HNSW](docs/concepts.md#hnsw-vector-search) approximate nearest neighbor index                     |
| `QuantizedHnswIndex<K>` | HNSW with [scalar quantization](docs/concepts.md#uint8-quantization) (lower memory)                |
| `VectorIndex<K>`        | Brute-force exact nearest neighbor index                                                           |
| `quantize`              | Scalar quantize a float vector                                                                     |
| `quantizedDot`          | Dot product on quantized vectors                                                                   |
| `HnswConfig`            | HNSW params: `dimensions`, [`m`, `efConstruction`](docs/tuning.md#efsearch-hnsw-recall-vs-latency) |
| `EmbeddingProvider`     | Interface for [async embedding generation](docs/extending.md#custom-embeddingprovider)             |
| `VectorSearch`          | Interface for vector search implementations                                                        |

## Hybrid Search

```ts
import { HybridSearch, type HybridSearchConfig } from "@coda/search";

interface MyDoc {
  id: string;
  name: string;
  description: string;
}

const config: HybridSearchConfig<MyDoc> = {
  getId: (doc) => doc.id,
  buildDocument: (doc) => `${doc.name} ${doc.description}`,
  getKeywords: (doc) => [{ tokens: [doc.name.toLowerCase()] }],
  embeddingProvider: null, // keyword-only mode (pass a real provider for vector search)
  onError: console.error,
};

const hybrid = HybridSearch.create(config);

// Index some documents
hybrid.add({ id: "t1", name: "Artist", description: "music artist entity" });
hybrid.add({
  id: "t2",
  name: "Contract",
  description: "royalty contract terms",
});

// Search returns items ranked by fused scores
const results = await hybrid.search("artist", { limit: 10 });
// results: [{ item: { id: "t1", ... }, score: ... }]
```

| Export               | Description                                     |
| -------------------- | ----------------------------------------------- |
| `HybridSearch<T>`    | Orchestrates keyword + vector + glossary search |
| `HybridSearchConfig` | Full configuration for the hybrid pipeline      |

## Score Fusion

Combine ranked results from multiple signals:

| Export              | Description                                                                                               |
| ------------------- | --------------------------------------------------------------------------------------------------------- |
| `RrfFusion`         | [Reciprocal Rank Fusion](docs/concepts.md#rrf-score-fusion) — rank-based, parameter-free                  |
| `WeightedSumFusion` | [Weighted sum](docs/concepts.md#alternative-weightedsumfusion) of normalized scores                       |
| `ScoreFusion`       | Interface for custom fusion strategies                                                                    |
| `RankedEntry<K>`    | Entry with key + fused score                                                                              |
| `NamedSignal`       | [Named list of ranked entries](docs/concepts.md#namedsignal----extensible-not-hardcoded) for fusion input |

## Text Processing

| Export            | Description                                                                                               |
| ----------------- | --------------------------------------------------------------------------------------------------------- |
| `tokenize`        | Tokenize text into normalized terms (see [tokenization pipeline](docs/concepts.md#tokenization-pipeline)) |
| `generateBigrams` | Generate [bigram](docs/tuning.md#bigrams) tokens from a term list                                         |
| `porterStem`      | [Porter stemming](docs/concepts.md#tokenization-pipeline) algorithm                                       |
| `TokenizeFn`      | Interface for custom tokenizers                                                                           |

## Data Structures

| Export        | Description                                    |
| ------------- | ---------------------------------------------- |
| `Trie<V>`     | Generic trie with typed values                 |
| `StringTrie`  | String-specialized trie                        |
| `fuzzySearch` | Fuzzy search over a trie (Levenshtein-bounded) |
| `TrieOptions` | Configuration for trie construction            |

## Glossary

| Export                    | Description                                                                             |
| ------------------------- | --------------------------------------------------------------------------------------- |
| `matchGlossary`           | Match query against a [domain glossary](docs/concepts.md#glossary-matching)             |
| `buildGlossaryContextMap` | Build a context map for glossary-enriched search                                        |
| `GlossaryEntry`           | Single glossary term with aliases (see [format](docs/concepts.md#glossaryentry-format)) |
| `GlossaryMatch`           | Match result with confidence score                                                      |

## Pipeline Stages

Composable stages for building multi-step search pipelines:

| Export               | Description                                                                           |
| -------------------- | ------------------------------------------------------------------------------------- |
| `GlossaryMatchStage` | Stage that matches against a [domain glossary](docs/concepts.md#expansion-vs-ranking) |
| `VectorStage`        | Stage that performs [vector similarity search](docs/concepts.md#hnsw-vector-search)   |
| `KeywordStage`       | Stage that performs keyword ([BM25](docs/concepts.md#bm25-keyword-scoring)) search    |
| `FuzzyStage`         | Stage that catches typos via edit-distance matching over a trie                       |

## Evaluation Metrics

| Export             | Description                             |
| ------------------ | --------------------------------------- |
| `ndcg`             | Normalized Discounted Cumulative Gain   |
| `mrr`              | Mean Reciprocal Rank                    |
| `precisionAtK`     | Precision at K                          |
| `recallAtK`        | Recall at K                             |
| `aggregateMetrics` | Aggregate metrics over multiple queries |
| `RelevanceMap`     | Ground truth relevance judgments        |

## Ranking Signals

Compute ranking signals for RRF fusion (used by the search service):

| Export                       | Description                                                                                                                      |
| ---------------------------- | -------------------------------------------------------------------------------------------------------------------------------- |
| `computeDegreeSignal`        | Node importance by in/out degree (see [DegreeSignal](docs/concepts.md#degreesignal-static))                                      |
| `computeProximitySignal`     | Node proximity to a query node (see [ProximitySignal](docs/concepts.md#proximitysignal-query-time))                              |
| `computeAdamicAdarSignal`    | Neighbor specificity — nodes with rare neighbors rank higher (see [AdamicAdarSignal](docs/concepts.md#adamicadarsignal-static))  |
| `computeBetweennessSignal`   | Bridge detection — nodes on many shortest paths rank higher (see [BetweennessSignal](docs/concepts.md#betweennesssignal-static)) |
| `computeColumnDensitySignal` | Field count density — documents with more keyword fields rank higher (no graph required)                                         |
| `computeJoinPaths`           | Detect join paths between schema tables                                                                                          |

## Search Engine

`SearchEngine` orchestrates the full index lifecycle — initialization, incremental refresh, search, and teardown:

```ts
import { SearchEngine, InMemoryEventBus } from "@coda/search";

const engine = new SearchEngine({
  fetcher: myFetcher,
  transformer: myTransformer,
  embeddingProvider: myEmbedder,
  snapshotStore: mySnapshotStore,
  eventBus: new InMemoryEventBus(),
});

await engine.init(); // Cold start
await engine.refresh(); // Incremental update
const results = await engine.search("revenue", { limit: 10 });
await engine.destroy(); // Permanent teardown
```

The engine does not own scheduling — the caller decides when to call `refresh()` (timer, webhook, cron, manual). See [Engine Lifecycle](docs/engine.md) for details.

## Pipeline Architecture

A search query flows through four phases:

### 1. [Query Expansion](docs/pipeline.md#phase-1-query-expansion) (optional)

[QueryExpanders](docs/extending.md#custom-queryexpander) rewrite or augment the query before ranking.
Expanders run in order — each receives tokens from prior expanders.

    QueryExpander[] → accumulated expansion tokens

### 2. [Ranking Stages](docs/pipeline.md#phase-2-ranking-stages)

[SearchStages](docs/extending.md#custom-searchstage) score documents concurrently. All stages implement
the same interface and return RankedEntry[].

    SearchStage[] → NamedSignal[] (one per stage)

Built-in: GlossaryMatchStage, KeywordStage, VectorStage.
Add custom stages by implementing [SearchStage](docs/pipeline.md#searchstage-interface) and adding to config.

### 3. [Ranking Signals](docs/pipeline.md#phase-3-ranking-signals)

Signals provide additional scoring dimensions outside the stage pipeline.

- [StaticSignal](docs/pipeline.md#staticsignal): computed once, cached between queries (e.g., [degree centrality](docs/concepts.md#degreesignal-static))
- [QuerySignal](docs/pipeline.md#querysignal): computed per query from candidate results (e.g., [proximity](docs/concepts.md#proximitysignal-query-time))

### 4. [Score Fusion](docs/pipeline.md#phase-4-score-fusion)

All NamedSignals (from stages + signals) are fused into final scores.

    ScoreFusion.fuse(signals) → Map<id, score>

Built-in: [RrfFusion](docs/concepts.md#rrf-score-fusion) (default), [WeightedSumFusion](docs/concepts.md#alternative-weightedsumfusion).

### Full Flow

    Query
      → QueryExpander[] (rewrite)
      → SearchStage[] (rank, concurrent)
      → StaticSignal[] (cached) + QuerySignal[] (per-query)
      → ScoreFusion (fuse all NamedSignals)
      → Paginated results

## Other

| Export           | Description                                    |
| ---------------- | ---------------------------------------------- |
| `allocateBudget` | Distribute a token budget across search stages |
| `RerankProvider` | Interface for async reranking                  |
| `Diff`           | Type representing a diff between two values    |