Planned Feature

This feature is on the roadmap but not yet implemented in the current Rust server. The API shown below represents the planned design.

DocsGuidesIndexing

Indexing

TopGun’s Query Engine provides CQEngine-inspired indexing that accelerates queries from O(N) full scans to O(1) or O(log N) indexed lookups. On a dataset of 1 million records, this means going from ~500ms to less than 1ms per query.

O(1) Equality

HashIndex provides constant-time lookups for equality and IN queries.

O(log N) Ranges

NavigableIndex enables efficient range queries with skip-list based indexing.

Full-Text Search

InvertedIndex supports text search with configurable tokenization.

Quick Start

To use indexes, wrap your LWWMap or ORMap with IndexedLWWMap or IndexedORMap:

Creating an Indexed Map

import { IndexedLWWMap, simpleAttribute, HLC } from '@topgunbuild/core';

// Create an indexed map
const hlc = new HLC('node-1');
const products = new IndexedLWWMap<string, Product>(hlc);

// Define attributes for indexing
const categoryAttr = simpleAttribute<Product, string>('category', p => p.category);
const priceAttr = simpleAttribute<Product, number>('price', p => p.price);

// Add indexes
products.addHashIndex(categoryAttr);      // O(1) equality queries
products.addNavigableIndex(priceAttr);    // O(log N) range queries

// Insert data (indexes update automatically)
products.set('p1', { id: 'p1', name: 'Laptop', category: 'electronics', price: 999 });
products.set('p2', { id: 'p2', name: 'Book', category: 'books', price: 29 });
products.set('p3', { id: 'p3', name: 'Mouse', category: 'electronics', price: 49 });

Now queries automatically use the appropriate index:

Querying with Indexes

// Equality query - uses HashIndex (O(1))
const electronics = products.queryValues({
  type: 'eq',
  attribute: 'category',
  value: 'electronics'
});
// Returns: [{ id: 'p1', ... }, { id: 'p3', ... }]

// Range query - uses NavigableIndex (O(log N))
const affordable = products.queryValues({
  type: 'and',
  children: [
    { type: 'gte', attribute: 'price', value: 20 },
    { type: 'lte', attribute: 'price', value: 100 }
  ]
});
// Returns: [{ id: 'p2', ... }, { id: 'p3', ... }]

Index Types

TopGun provides three index types, each optimized for different query patterns:

Index Types

// 1. HashIndex - O(1) equality lookups
//    Use for: status, category, userId, type
products.addHashIndex(simpleAttribute('status', p => p.status));

// 2. NavigableIndex - O(log N) range queries
//    Use for: price, date, age, score
products.addNavigableIndex(simpleAttribute('createdAt', p => p.createdAt));

// 3. InvertedIndex - O(K) text search
//    Use for: name, description, tags
products.addInvertedIndex(simpleAttribute('name', p => p.name));

Index Type	Time Complexity	Best For
HashIndex	O(1)	Equality (`eq`, `neq`, `in`, `has`)
NavigableIndex	O(log N)	Range queries (`gt`, `gte`, `lt`, `lte`, `between`)
InvertedIndex	O(K)	Text search (`contains`, `containsAll`, `containsAny`)

Where N = total records, K = matching tokens.

Query Optimization

The Query Optimizer automatically selects the best index for each query:

Query Plan Inspection

// Inspect query execution plan
const plan = products.explainQuery({
  type: 'and',
  children: [
    { type: 'eq', attribute: 'category', value: 'electronics' },
    { type: 'between', attribute: 'price', from: 100, to: 500 }
  ]
});

console.log(plan);
// {
//   root: {
//     type: 'intersection',
//     steps: [
//       { type: 'index-scan', index: HashIndex, query: {...} },
//       { type: 'index-scan', index: NavigableIndex, query: {...} }
//     ]
//   },
//   estimatedCost: 32,
//   usesIndexes: true
// }

Cost Model

The optimizer uses a cost model to choose execution strategies:

Index Type	Retrieval Cost	Merge Cost
StandingQueryIndex	10	10
HashIndex	30	30
NavigableIndex	40	40
InvertedIndex	35	35
Full Scan	∞	∞

For compound queries (AND/OR), the optimizer:

Identifies which sub-queries can use indexes
Estimates cardinality for merge cost calculation
Chooses intersection/union strategy based on total cost

Multi-Value Attributes

For array fields (tags, categories), use multiAttribute:

Multi-Value Attributes

import { multiAttribute } from '@topgunbuild/core';

// For arrays (tags, categories, etc.)
const tagsAttr = multiAttribute<Product, string>('tags', p => p.tags);
products.addHashIndex(tagsAttr);

// Now queries can match any tag
const wireless = products.queryValues({
  type: 'eq',
  attribute: 'tags',
  value: 'wireless'
});

Index Statistics

Monitor index usage and performance:

Index Statistics

// Get index statistics
const stats = products.getIndexStats();

for (const [attrName, stat] of stats) {
  console.log(`${attrName}: ${stat.size} entries, type: ${stat.type}`);
}
// category: 3 entries, type: hash
// price: 3 entries, type: navigable

// Get registry stats
const registryStats = products.getIndexRegistryStats();
console.log(`Total indexes: ${registryStats.totalIndexes}`);
console.log(`Indexed attributes: ${registryStats.indexedAttributes.join(', ')}`);

Best Practices

When to Add Indexes

• Add indexes on attributes you query frequently
• Use HashIndex for equality checks (status, type, userId)
• Use NavigableIndex for sortable/range fields (price, date, score)
• Use InvertedIndex for text search (name, description)
• Don’t over-index: each index adds ~20-30% memory overhead

Memory Considerations

Indexes trade memory for query speed:

Scenario	Memory Overhead
1 HashIndex	~10-15%
1 NavigableIndex	~15-20%
1 InvertedIndex	~30-50%
All 3 indexes	~50-80%

For browser environments with limited heap (2-4 GB), index selectively based on query patterns.

CRDT Integration

Indexes are fully integrated with TopGun’s CRDT operations:

Automatic updates: Indexes update on set(), remove(), and merge()
Tombstone-aware: Deleted records are removed from indexes
TTL-aware: Expired records are filtered at query time

CRDT Operations with Indexes

// All CRDT operations automatically update indexes
products.set('p4', { id: 'p4', category: 'electronics', price: 299 });
// → HashIndex and NavigableIndex both updated

products.remove('p4');
// → Removed from all indexes

// Remote merge also updates indexes
products.merge('p5', remoteRecord);
// → Indexes updated if merge succeeds

Live Queries with Indexes

Combine indexes with live queries for reactive, high-performance subscriptions:

Live Query Subscription

// Subscribe to a live query (uses indexes internally)
const unsubscribe = products.subscribeLiveQuery(
  { type: 'eq', attribute: 'category', value: 'electronics' },
  (event) => {
    if (event.type === 'initial') {
      console.log('Initial results:', event.results);
    } else {
      console.log('Delta:', event.added, event.removed, event.updated);
    }
  }
);

// Updates trigger delta notifications
products.set('p5', { id: 'p5', category: 'electronics', price: 199 });
// → Callback receives: { type: 'delta', added: [['p5', {...}]], ... }

Next Steps

Full-Text Search - Deep dive into InvertedIndex and tokenization
Adaptive Indexing - Auto-suggest and auto-create indexes
Performance Tuning - Optimize for your workload

Schema & Type Safety

Full-Text Search