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

Live Queries

Full-Text Search