---
title: Index Manager Algorithm
summary: Vector index management, memory-mapped file handling, and index rebuild algorithms for local memory search
---

# Index Manager Algorithm

## Overview

The Memory Index Manager provides local SQLite-based memory search with vector embeddings and full-text search (FTS) capabilities. It serves as the fallback backend when QMD is unavailable, or as the primary backend for local-only deployments.

**Location:** `src/memory/manager.ts`

### Key Features

- **Hybrid search** - Vector similarity + BM25 full-text search
- **Memory-mapped vectors** - Efficient storage via sqlite-vec extension
- **Incremental indexing** - Watch-based updates without full rebuilds
- **Embedding cache** - Avoid recomputing embeddings for identical content
- **Atomic operations** - Transaction-safe index updates

---

## Architecture

```
┌─────────────────────────────────────────────────────────┐
│  MemoryIndexManager                                     │
│                                                         │
│  ┌───────────────────────────────────────────────────┐ │
│  │  Embedded Database (SQLite + sqlite-vec)          │ │
│  │                                                   │ │
│  │  ┌──────────────┐  ┌──────────────┐              │ │
│  │  │ chunks_vec   │  │ chunks_fts   │              │ │
│  │  │ (vector)     │  │ (full-text)  │              │ │
│  │  │              │  │              │              │ │
│  │  │ - id         │  │ - rowid      │              │ │
│  │  │ - embedding  │  │ - content    │              │ │
│  │  │ - metadata   │  │ - session    │              │ │
│  │  └──────────────┘  └──────────────┘              │ │
│  │                                                   │ │
│  │  ┌──────────────┐  ┌──────────────┐              │ │
│  │  │ embedding_   │  │ sessions     │              │ │
│  │  │ cache        │  │              │              │ │
│  │  │              │  │              │              │ │
│  │  │ - content    │  │ - id         │              │ │
│  │  │ - embedding  │  │ - messages   │              │ │
│  │  │ - dims       │  │ - metadata   │              │ │
│  │  └──────────────┘  └──────────────┘              │ │
│  └───────────────────────────────────────────────────┘ │
│                                                         │
│  ┌───────────────────────────────────────────────────┐ │
│  │  Embedding Provider Layer                         │ │
│  │  - OpenAI (text-embedding-3-small/large)          │ │
│  │  - Gemini (text-embedding-004)                    │ │
│  │  - Voyage (voyage-3, voyage-code)                 │ │
│  │  - Mistral (mistral-embed)                        │ │
│  │  - Local (ollama, llama.cpp)                      │ │
│  └───────────────────────────────────────────────────┘ │
└─────────────────────────────────────────────────────────┘
```

---

## Database Schema

### Vector Table

```sql
-- Vector storage with sqlite-vec extension
CREATE TABLE IF NOT EXISTS chunks_vec (
  id TEXT PRIMARY KEY,
  chunk_id TEXT NOT NULL,
  session_id TEXT NOT NULL,
  content TEXT NOT NULL,
  embedding BLOB,  -- f32 array stored as BLOB
  dims INTEGER,
  created_at INTEGER NOT NULL,
  metadata TEXT    -- JSON blob
);

-- Vector index for similarity search
CREATE INDEX IF NOT EXISTS idx_chunks_vec_session
  ON chunks_vec(session_id);
```

### Full-Text Search Table

```sql
-- FTS5 for BM25 keyword search
CREATE VIRTUAL TABLE IF NOT EXISTS chunks_fts USING fts5(
  content,
  session_id,
  chunk_id,
  tokenize='porter'
);

-- Populate FTS from vector table
CREATE TRIGGER IF NOT EXISTS chunks_vec_ai AFTER INSERT ON chunks_vec BEGIN
  INSERT INTO chunks_fts(rowid, content, session_id, chunk_id)
  VALUES (NEW.id, NEW.content, NEW.session_id, NEW.chunk_id);
END;
```

### Embedding Cache

```sql
-- Cache to avoid recomputing embeddings
CREATE TABLE IF NOT EXISTS embedding_cache (
  content_hash TEXT PRIMARY KEY,  -- SHA-256 of content
  embedding BLOB NOT NULL,
  dims INTEGER NOT NULL,
  provider TEXT NOT NULL,
  model TEXT NOT NULL,
  created_at INTEGER NOT NULL
);

-- Index for cache lookups
CREATE INDEX IF NOT EXISTS idx_embedding_cache_provider_model
  ON embedding_cache(provider, model);
```

---

## Vector Index Management

### Index Initialization

```typescript
export class MemoryIndexManager extends MemoryManagerEmbeddingOps implements MemorySearchManager {
  protected db: DatabaseSync;
  protected readonly vector: {
    enabled: boolean;
    available: boolean | null;
    extensionPath?: string;
    loadError?: string;
    dims?: number;
  };
  protected readonly fts: {
    enabled: boolean;
    available: boolean;
    loadError?: string;
  };

  constructor(params: { /* ... */ }) {
    // ... initialization ...

    // Load sqlite-vec extension
    this.vector = this.loadVectorExtension();

    // Initialize FTS5
    this.fts = this.initializeFts();
  }

  private loadVectorExtension(): VectorState {
    try {
      const extensionPath = resolveSqliteVecExtension();

      // Enable loading extensions
      this.db.function("load_extension", (path: string) => {
        this.db.exec(`SELECT load_extension('${path}')`);
      });

      this.db.exec(`SELECT load_extension('${extensionPath}')`);

      return {
        enabled: true,
        available: true,
        extensionPath,
      };
    } catch (err) {
      return {
        enabled: false,
        available: false,
        loadError: err instanceof Error ? err.message : String(err),
      };
    }
  }
}
```

### Vector Similarity Search

```typescript
async function searchVector(
  db: DatabaseSync,
  query: string,
  sessionKey: string,
  embedding: number[],
  opts: { maxResults: number; minScore: number },
): Promise<MemorySearchResult[]> {
  // Use sqlite-vec KNN search
  const stmt = db.prepare(`
    SELECT 
      id, chunk_id, session_id, content,
      vec_distance_cosine(embedding, ?1) AS distance
    FROM chunks_vec
    WHERE session_id = ?2
    ORDER BY distance ASC
    LIMIT ?3
  `);

  const results = stmt.all(
    new Float32Array(embedding), // Query embedding as BLOB
    sessionKey,
    opts.maxResults,
  ) as Array<{
    id: string;
    chunk_id: string;
    content: string;
    distance: number;
  }>;

  // Convert distance to similarity score (0-1)
  return results
    .filter((r) => {
      const score = 1 - r.distance;
      return score >= opts.minScore;
    })
    .map((r) => ({
      id: r.id,
      chunkId: r.chunk_id,
      content: r.content,
      score: 1 - r.distance, // Cosine similarity
      sessionId: r.session_id,
    }));
}
```

### Full-Text Search (BM25)

```typescript
async function searchKeyword(
  db: DatabaseSync,
  query: string,
  sessionKey: string,
  opts: { maxResults: number },
): Promise<MemorySearchResult[]> {
  // Extract keywords from query
  const keywords = extractKeywords(query);
  const ftsQuery = buildFtsQuery(keywords);

  // BM25 search with ranking
  const stmt = db.prepare(`
    SELECT 
      chunks_vec.id,
      chunks_vec.chunk_id,
      chunks_vec.session_id,
      chunks_vec.content,
      bm25(chunks_fts) AS bm25_score
    FROM chunks_fts
    JOIN chunks_vec ON chunks_fts.rowid = chunks_vec.rowid
    WHERE chunks_fts MATCH ?1
      AND chunks_vec.session_id = ?2
    ORDER BY bm25_score ASC  -- Lower BM25 = better match
    LIMIT ?3
  `);

  const results = stmt.all(ftsQuery, sessionKey, opts.maxResults) as Array<{
    id: string;
    bm25_score: number;
    content: string;
  }>;

  // Convert BM25 scores to 0-1 range
  return results.map((r) => ({
    id: r.id,
    chunkId: r.chunk_id,
    content: r.content,
    score: bm25RankToScore(r.bm25_score),
    sessionId: r.session_id,
  }));
}

function bm25RankToScore(rank: number): number {
  // BM25 returns negative scores (lower = better)
  // Normalize to 0-1 range where 1 = perfect match
  return Math.max(0, Math.min(1, 1 / (1 + Math.abs(rank))));
}
```

### Hybrid Search (Vector + FTS)

```typescript
function mergeHybridResults(
  vectorResults: MemorySearchResult[],
  ftsResults: MemorySearchResult[],
  opts: { vectorWeight: number; ftsWeight: number },
): MemorySearchResult[] {
  const seen = new Map<string, MemorySearchResult>();

  // Merge vector results
  for (const result of vectorResults) {
    seen.set(result.id, {
      ...result,
      score: result.score * opts.vectorWeight,
    });
  }

  // Merge FTS results with score combination
  for (const result of ftsResults) {
    const existing = seen.get(result.id);
    if (existing) {
      // Combine scores (weighted average)
      existing.score = existing.score + result.score * opts.ftsWeight;
    } else {
      seen.set(result.id, {
        ...result,
        score: result.score * opts.ftsWeight,
      });
    }
  }

  // Sort by combined score
  return Array.from(seen.values()).sort((a, b) => b.score - a.score);
}
```

---

## Memory-Mapped File Handling

### SQLite Memory Mapping

```typescript
// Configure SQLite for memory-mapped I/O
function configureMemoryMapping(db: DatabaseSync): void {
  // Enable WAL mode for better concurrency
  db.exec("PRAGMA journal_mode = WAL");

  // Set memory-mapped I/O size (256 MB)
  db.exec("PRAGMA mmap_size = 268435456"); // 256 MB

  // Cache size (negative = KB, positive = pages)
  db.exec("PRAGMA cache_size = -64000"); // 64 MB

  // Synchronous mode (NORMAL = good balance)
  db.exec("PRAGMA synchronous = NORMAL");

  // Temp store in memory
  db.exec("PRAGMA temp_store = MEMORY");
}
```

### Memory-Mapped Vector Storage

```
┌─────────────────────────────────────────────────────────┐
│  Memory-Mapped Vector Storage                           │
│                                                         │
│  SQLite Database File (memory.db)                      │
│  ┌─────────────────────────────────────────────────┐   │
│  │ Header                                          │   │
│  ├─────────────────────────────────────────────────┤   │
│  │ sqlite-vec extension                            │   │
│  │ ┌─────────────────────────────────────────────┐ │   │
│  │ │ chunks_vec table                            │ │   │
│  │ │ ┌──────┬──────────────┬─────────────────┐  │ │   │
│  │ │ │ id   │ embedding    │ metadata        │  │ │   │
│  │ │ ├──────┼──────────────┼─────────────────┤  │ │   │
│  │ │ │ ...  │ [f32 array]  │ {...}           │  │ │   │
│  │ │ └──────┴──────────────┴─────────────────┘  │ │   │
│  │ └─────────────────────────────────────────────┘ │   │
│  ├─────────────────────────────────────────────────┤   │
│  │ Data Pages (memory-mapped)                      │   │
│  │ ┌─────────────────────────────────────────────┐ │   │
│  │ │ Page 1: [vector embeddings...]              │ │   │
│  │ │ Page 2: [vector embeddings...]              │ │   │
│  │ │ ...                                         │ │   │
│  │ │ Page N: [vector embeddings...]              │ │   │
│  │ └─────────────────────────────────────────────┘ │   │
│  └─────────────────────────────────────────────────┘   │
│                    │                                    │
│                    │ mmap()                             │
│                    ▼                                    │
│  Process Memory (virtual address space)                │
│  ┌─────────────────────────────────────────────────┐   │
│  │ Virtual Memory Mapping                          │   │
│  │ - OS pages in on demand                         │   │
│  │ - Pages evicted under memory pressure           │   │
│  │ - Zero-copy access to vector data               │   │
│  └─────────────────────────────────────────────────┘   │
└─────────────────────────────────────────────────────────┘
```

### Benefits

1. **Zero-copy access** - Vectors read directly from disk to CPU cache
2. **Lazy loading** - Only accessed pages consume RAM
3. **OS-managed caching** - kernel page cache handles eviction
4. **Persistence** - Data survives process restarts

### Configuration

```typescript
function optimizeForLargeIndexes(db: DatabaseSync): void {
  // Increase page size for better sequential access
  db.exec("PRAGMA page_size = 8192"); // 8 KB pages

  // Enable query planner statistics
  db.exec("ANALYZE");

  // Optimize for read-heavy workloads
  db.exec("PRAGMA read_uncommitted = true");

  // Limit memory per connection
  db.exec("PRAGMA soft_heap_limit = 134217728"); // 128 MB
}
```

---

## Index Rebuild Algorithms

### Full Rebuild

```typescript
async function rebuildIndex(params: {
  sessions: SessionFileEntry[];
  embeddingProvider: EmbeddingProvider;
  batchSize: number;
  progress?: (update: MemorySyncProgressUpdate) => void;
}): Promise<void> {
  const { sessions, embeddingProvider, batchSize, progress } = params;

  // Use transaction for atomicity
  db.exec("BEGIN");

  try {
    // Clear existing index
    db.exec("DELETE FROM chunks_vec");
    db.exec("DELETE FROM chunks_fts");
    db.exec("DELETE FROM embedding_cache");

    let processed = 0;
    const total = sessions.reduce((sum, s) => sum + s.messageCount, 0);

    // Process sessions in batches
    for (const session of sessions) {
      const messages = await readSessionMessages(session);

      // Chunk messages
      const chunks = chunkMessages(messages, {
        maxChunkSize: 512, // tokens
        overlap: 50, // tokens
      });

      // Embed chunks in batches
      for (let i = 0; i < chunks.length; i += batchSize) {
        const batch = chunks.slice(i, i + batchSize);

        // Generate embeddings
        const embeddings = await embeddingProvider.embedBatch(batch.map((c) => c.content));

        // Insert into database
        const insertStmt = db.prepare(`
          INSERT OR REPLACE INTO chunks_vec 
          (id, chunk_id, session_id, content, embedding, dims, created_at)
          VALUES (?, ?, ?, ?, ?, ?, ?)
        `);

        for (let j = 0; j < batch.length; j++) {
          const chunk = batch[j];
          const embedding = embeddings[j];

          insertStmt.run(
            generateChunkId(chunk),
            chunk.id,
            session.id,
            chunk.content,
            new Float32Array(embedding.vector),
            embedding.dims,
            Date.now(),
          );
        }

        processed += batch.length;
        progress?.({
          phase: "indexing",
          processed,
          total,
          currentSession: session.id,
        });
      }
    }

    // Commit transaction
    db.exec("COMMIT");

    // Update index metadata
    updateIndexMetadata({
      lastRebuild: Date.now(),
      totalChunks: processed,
      totalSessions: sessions.length,
    });
  } catch (err) {
    // Rollback on error
    db.exec("ROLLBACK");
    throw err;
  }
}
```

### Incremental Rebuild

```typescript
async function incrementalRebuild(params: {
  dirtySessions: Set<string>;
  embeddingProvider: EmbeddingProvider;
}): Promise<void> {
  const { dirtySessions, embeddingProvider } = params;

  db.exec("BEGIN");

  try {
    // Remove old chunks for dirty sessions
    const removeStmt = db.prepare("DELETE FROM chunks_vec WHERE session_id = ?");

    for (const sessionId of dirtySessions) {
      removeStmt.run(sessionId);
    }

    // Re-index only dirty sessions
    for (const sessionId of dirtySessions) {
      const messages = await readSessionMessages(sessionId);
      const chunks = chunkMessages(messages);

      const embeddings = await embeddingProvider.embedBatch(chunks.map((c) => c.content));

      const insertStmt = db.prepare(`
        INSERT OR REPLACE INTO chunks_vec 
        (id, chunk_id, session_id, content, embedding, dims, created_at)
        VALUES (?, ?, ?, ?, ?, ?, ?)
      `);

      for (let i = 0; i < chunks.length; i++) {
        const chunk = chunks[i];
        const embedding = embeddings[i];

        insertStmt.run(
          generateChunkId(chunk),
          chunk.id,
          sessionId,
          chunk.content,
          new Float32Array(embedding.vector),
          embedding.dims,
          Date.now(),
        );
      }
    }

    db.exec("COMMIT");
  } catch (err) {
    db.exec("ROLLBACK");
    throw err;
  }
}
```

### Chunking Algorithm

```typescript
function chunkMessages(
  messages: SessionMessage[],
  opts: { maxChunkSize: number; overlap: number },
): MemoryChunk[] {
  const chunks: MemoryChunk[] = [];
  let currentChunk: string[] = [];
  let currentSize = 0;

  for (const message of messages) {
    const tokens = tokenize(message.content);

    // Check if adding this message exceeds chunk size
    if (currentSize + tokens.length > opts.maxChunkSize) {
      // Finalize current chunk
      if (currentChunk.length > 0) {
        chunks.push({
          id: randomId(),
          content: currentChunk.join("\n"),
          messageCount: currentChunk.length,
        });

        // Keep overlap for continuity
        const overlapSize = Math.min(opts.overlap, currentChunk.length);
        currentChunk = currentChunk.slice(-overlapSize);
        currentSize = currentChunk.reduce((sum, c) => sum + tokenize(c).length, 0);
      }
    }

    currentChunk.push(message.content);
    currentSize += tokens.length;
  }

  // Don't forget last chunk
  if (currentChunk.length > 0) {
    chunks.push({
      id: randomId(),
      content: currentChunk.join("\n"),
      messageCount: currentChunk.length,
    });
  }

  return chunks;
}
```

---

## Embedding Cache

### Cache Lookup

```typescript
async function getOrComputeEmbedding(
  content: string,
  provider: EmbeddingProvider,
): Promise<number[]> {
  const contentHash = hashContent(content);

  // Check cache first
  const cached = db
    .prepare(
      `
    SELECT embedding, dims FROM embedding_cache
    WHERE content_hash = ? AND provider = ? AND model = ?
  `,
    )
    .get(contentHash, provider.provider, provider.model) as
    | { embedding: Buffer; dims: number }
    | undefined;

  if (cached) {
    // Return cached embedding
    return Array.from(new Float32Array(cached.embedding.buffer));
  }

  // Compute new embedding
  const result = await provider.embed(content);

  // Cache result
  db.prepare(
    `
    INSERT OR REPLACE INTO embedding_cache
    (content_hash, embedding, dims, provider, model, created_at)
    VALUES (?, ?, ?, ?, ?, ?)
  `,
  ).run(
    contentHash,
    new Float32Array(result.vector),
    result.dims,
    provider.provider,
    provider.model,
    Date.now(),
  );

  return result.vector;
}
```

### Cache Eviction

```typescript
function evictOldCacheEntries(maxAge: number, maxEntries: number): void {
  const cutoff = Date.now() - maxAge;

  // Remove old entries
  db.prepare(
    `
    DELETE FROM embedding_cache
    WHERE created_at < ?
  `,
  ).run(cutoff);

  // If still over limit, remove least recently used
  const count = db.prepare("SELECT COUNT(*) as count FROM embedding_cache").get() as {
    count: number;
  };

  if (count.count > maxEntries) {
    const toRemove = count.count - maxEntries;
    db.prepare(
      `
      DELETE FROM embedding_cache
      WHERE rowid IN (
        SELECT rowid FROM embedding_cache
        ORDER BY created_at ASC
        LIMIT ?
      )
    `,
    ).run(toRemove);
  }
}
```

---

## Watch-Based Updates

### File System Watcher

```typescript
class MemoryIndexManager {
  private watcher: FSWatcher | null = null;
  private sessionPendingFiles = new Set<string>();
  private sessionWatchTimer: NodeJS.Timeout | null = null;

  startWatching(): void {
    this.watcher = watch(this.workspaceDir, {
      persistent: true,
      ignoreInitial: true,
    });

    this.watcher.on("change", (filePath) => {
      if (isSessionFile(filePath)) {
        this.markSessionDirty(filePath);
      }
    });

    this.watcher.on("add", (filePath) => {
      if (isSessionFile(filePath)) {
        this.markSessionDirty(filePath);
      }
    });

    // Debounced sync
    this.sessionWatchTimer = setInterval(() => {
      if (this.sessionPendingFiles.size > 0) {
        this.syncDirtySessions();
      }
    }, SYNC_INTERVAL_MS);
  }

  private markSessionDirty(filePath: string): void {
    const sessionKey = extractSessionKey(filePath);
    this.sessionPendingFiles.add(filePath);
    this.sessionDirty.add(sessionKey);
  }

  private async syncDirtySessions(): Promise<void> {
    const sessions = Array.from(this.sessionDirty);
    this.sessionDirty.clear();

    await incrementalRebuild({
      dirtySessions: new Set(sessions),
      embeddingProvider: this.provider,
    });
  }
}
```

---

## Testing Strategies

```typescript
describe("MemoryIndexManager", () => {
  it("creates vector and FTS indexes", async () => {
    const manager = await MemoryIndexManager.get(params);

    expect(manager.vector.enabled).toBe(true);
    expect(manager.fts.enabled).toBe(true);
  });

  it("performs hybrid search", async () => {
    const manager = await MemoryIndexManager.get(params);

    // Index test documents
    await manager.sync({ force: true });

    // Search
    const results = await manager.search("test query", {
      maxResults: 10,
      minScore: 0.7,
    });

    expect(results.length).toBeGreaterThan(0);
    expect(results[0].score).toBeGreaterThan(0.7);
  });

  it("caches embeddings", async () => {
    const manager = await MemoryIndexManager.get(params);
    const embedSpy = jest.spyOn(provider, "embed");

    // First call - computes embedding
    await manager.search("test");
    expect(embedSpy).toHaveBeenCalledTimes(1);

    // Second call - uses cache
    await manager.search("test");
    expect(embedSpy).toHaveBeenCalledTimes(1); // Still 1
  });

  it("performs incremental rebuild", async () => {
    const manager = await MemoryIndexManager.get(params);

    await manager.sync({ force: true });
    const initialSize = await manager.getSize();

    // Add new messages
    await addMessages("test-session", ["new message"]);

    // Incremental sync
    await manager.sync({ force: false });

    const newSize = await manager.getSize();
    expect(newSize).toBeGreaterThan(initialSize);
  });
});
```

---

## Related Documentation

- [Fallback Manager](/algorithms/memory-search/fallback-manager)
- [QMD Backend](/algorithms/memory-search/qmd-backend)
- [Memory Configuration](/memory/configuration)
- [SQLite Vec Extension](https://sqlite-vec.org/)