Indexing Reference

ConjureDB provides a rich set of index structures that turn O(n) table scans into O(1) or O(log n) lookups. This page is the comprehensive reference for every index type, its declaration, API, complexity guarantees, query optimizer integration, and practical usage patterns.

Overview

Why Indexes Matter

ConjureDB is an in-memory database for game clients. Even though data lives in RAM, scanning every row in a DbSet<T> for each query wastes CPU budget that should go to rendering and gameplay. Indexes provide sub-linear access paths that the compiled query engine uses to answer queries without full-table scans.

When no suitable index exists, the compiler falls back to a full-table scan and may emit the UM7001 (FullScanOnLargeTable) warning for large tables — it does not hard-error on unindexed access.

Index Categories

ConjureDB organizes indexes into two categories with distinct consistency models:

Category	Consistency	Lifecycle
PrimaryIndex	Immediate (synchronous)	Automatically created for every `DbSet<T>`. Mutations take effect instantly.
SecondaryIndex	Deferred-commit	Declared via `@index` on a field or `@@index` at the table level in `.conjure` schema files. Maintained by the background worker thread after each transaction commit. Secondary index reads always reflect committed data.

Index Types at a Glance

IndexType	Data Structure	Lookup	Insert	Supported Queries	Best For
Primary	Dual-array (sparse + dense)	O(1)	O(1) amort.	Key lookup by `Id`	Every table (automatic)
Lookup	Type-specialized hash map	O(1)	O(1) amort.	Equality (`==`), `IN`	Non-unique key lookups
Unique	`Dictionary<TKey, int>`	O(1)	O(1)	Equality; uniqueness enforced	Unique constraints
SortedSet	`SortedSet<Group>` + cached arrays	O(log n)	O(log n)	Equality, range, ordering	Range scans, ORDER BY
SortedList	Sorted dense array	O(log n)	O(n)	Equality, range, ordering	Small ordered sets
RangeLookup	Sparse min/max arrays	O(1)	O(1)	EXISTS with range predicates	"Does any X exist where Y > Z?"
GroupedSorted	Sparse sorted lists	O(1) group	O(log n) insert	Group + sort pattern	Top-N per group
Aggregation	Per-key stats map	O(1)	O(1)	Grouped Sum, Avg, Count, Min, Max	Per-group metrics (alias of UniversalAggregation)
UniversalAggregation	`Dictionary<TKey, Stats>`	O(1)	O(1)	Grouped Sum, Avg, Count, Min, Max	Per-group metrics
SpatialGrid	Uniform spatial hash grid	O(cells × ents/cell)	O(1)	Radius, bounds, nearest-K	2D/3D proximity queries

Index Types

PrimaryIndex<T>

Every DbSet<T> automatically receives a PrimaryIndex<T> — the authoritative store for all entities, keyed by their integer Id. You never declare it explicitly; it exists the moment you define a table.

Storage

The primary index uses dense, contiguous storage for entities with a separate ID-to-slot mapping. This provides O(1) lookups by ID while keeping iteration dense (no gaps to skip).

API

Method	Complexity	Description
`Contains(objectId)`	O(1)	Returns `true` if the entity exists.
`this[objectId]`	O(1)	Read entity by ID.
`Count`	O(1)	Number of stored entities.
`All`	O(n)	`IEnumerable<T>` over all entities (dense, no gaps).
`AsMemory`	O(1)	`ReadOnlyMemory<T>` zero-copy view.
`Upsert(objectId, item)`	O(1) amort.	Insert or update.
`Remove(objectId)`	O(1)	Swap-and-pop removal — no compaction needed.

Capacity Growth

When storage is exhausted, capacity is doubled. Set an accurate capacity in the table options to avoid resizing in steady state:

table Player(persistence: local, capacity: 10000) {
    // fields...
}

Thread Safety

PrimaryIndex<T> is not thread-safe. All mutations must be serialized by the caller — typically through the DbContext transaction model (BeginTransaction() / Commit()).

When to Use

You don't choose PrimaryIndex — it's always there. Use it for:

Direct entity lookup by Id (the most common access pattern).
Full-table iteration when no filter applies.
As the backing store that all secondary indexes reference.

LookupIndex<TKey>

A hash-based equality index for non-unique keys. The workhorse for filter Column == value queries.

Declaration

// Field-level (.conjure)
table Player {
  guild_id: int @index(name: "PlayersByGuild", kind: lookup)
}

// Composite key, table-level:
table Player {
  guild_id: int
  role: string
  @@index(fields: [guild_id, role], name: "PlayersByGuildAndRole", kind: lookup)
}

Data Structure

LookupIndex is type-specialized to avoid boxing and virtual GetHashCode calls:

Key Type	Backing Structure	Hash Strategy
`int`, `uint`	Integer-optimized hash map	Multiplicative (Fibonacci) hashing
`ulong`	Long-optimized hash map	High-quality integer finalizer
Other	`Dictionary<TKey, List<int>>`	Default `GetHashCode`

Each bucket maps a key value to a list of matching objectId values.

API

Method	Complexity	Description
`Query(key)`	O(1) amort.	Returns `IEnumerable<T>` of all entities with the given key.
`QueryDirect(key)`	O(1) amort.	Zero-allocation struct enumerable (used by generated code).
`QueryDirectByRef(key)`	O(1) amort.	Zero-allocation by-ref enumerable; avoids struct copies.
`ContainsKey(key)`	O(1) amort.	Returns `true` if any entity has this key value.
`Query(from, to)`	O(k)	Range query over sorted key cache (k = number of keys in range).
`All()`	O(n)	All entities in the index.

Null Handling

Entities with null keys are tracked separately, avoiding null-key issues in hash maps. Queries for null keys work transparently.

Partial Index Support

An optional filter predicate can restrict which entities are indexed:

table Player {
  guild_id: int @index(name: "ActivePlayersByGuild", kind: lookup, filter: "static (Player x) => x.IsActive", filter_columns: [IsActive])
}

Only entities passing the predicate are inserted, reducing index size and update cost.

Complexity

Operation	Time	Space per entry
Lookup	O(1) average	4 bytes (objectId in list) + hash map overhead
Insert	O(1) amortized	—
Remove	O(1) (swap in group list)	—
Update (key change)	O(1) remove + O(1) insert	—

When to Use

Equality filters: filter GuildId == 42
IN queries: filter Status in ("Active", "Pending")
Non-unique keys with multiple matches per value
High-frequency lookups where O(1) amortized is critical

Limitations

No ordered iteration guarantee (hash-based).
Not suitable for range queries (use SortedSet instead).
Memory grows with number of distinct key values × entries per key.

UniqueIndex<TKey>

A uniqueness-constrained equality index. Guarantees exactly one entity per key value.

Declaration

table Player {
  username: string @index(name: "PlayerByUsername", kind: unique)
}

Data Structure

Dictionary<TKey, int> — each key maps to exactly one objectId. Pending keys from the current transaction are tracked separately for pre-commit duplicate detection.

API

Method	Complexity	Description
`Query(key)`	O(1)	Returns the single matching entity. Throws `KeyNotFoundException` if absent.
`TryQuery(key, out item)`	O(1)	Returns `false` if absent (no exception).
`TryGetValue(key, out value)`	O(1)	Compatibility alias for dictionary-like API.
`Contains(key)`	O(1)	`true` if the key exists.
`this[key]`	O(1)	Indexer — same as `Query(key)`.
`All()`	O(n)	All entities in the table.

Uniqueness Enforcement

Insert with a duplicate key throws SecondaryIndexValidationException.
Validation happens at two levels:
1. Pre-commit (ValidateAdd): checks both committed keys and pending keys (from the current transaction).
2. Worker sync (AddInternal): final check when the background worker applies changes.
Key changes during updates are handled atomically: the old mapping is removed and the new mapping is inserted in a single operation.

Example

table Player(plural: Players, persistence: local, capacity: 1000) {
  Id: int @id
  Email: string @index(name: "PlayerByEmail", kind: unique)
  Name: string
}

// Usage in query:
// from Players | filter Email == "alice@example.com" | single

When to Use

Natural keys (email, username, external ID) that must be unique.
Foreign key targets where the relationship is 1:1.
Any column where duplicate values represent a data integrity violation.

Limitations

Exactly one entity per key — not suitable for non-unique lookups.
Duplicate detection adds slight overhead to inserts.

SortedSetIndex<TKey>

An ordered index supporting equality lookups, range predicates, and ordered iteration. The most versatile secondary index type.

Declaration

table Player {
  level: int @index(name: "Level_Sorted", kind: sorted_set)
}

// With partial filter
table Player {
  level: int @index(name: "ActivePlayersByLevel", kind: sorted_set, filter: "static (Player x) => x.IsActive", filter_columns: [IsActive])
}

Data Structure

SortedSet<Group> where each Group holds a List<int> of member objectId values sharing the same key. Groups are ordered by key value.

Cached orderings: The index maintains pre-computed ascending and descending orderings, lazily rebuilt after mutations. Ordered iteration is O(1) per element after the first access following a mutation batch.

Group boundaries: For descending access, the index also caches group boundary data, enabling O(log n) slicing for predicates like key > threshold without per-query allocations.

Zero-allocation lookups: Reusable Group objects (_searchGroup, _searchGroupUpper) are mutated in-place for search and range queries. No heap allocation per lookup.

API

Method	Complexity	Description
`Query(key)`	O(log n)	All entities with the exact key.
`QueryDirect(key)`	O(log n)	Zero-allocation struct enumerable.
`QueryDirectByRef(key)`	O(log n)	Zero-allocation by-ref enumerable.
`Query(from, to)`	O(log n + k)	Range query: all entities with keys in `[from, to]` inclusive.
`QueryGreaterThan(key)`	O(log n + k)	All entities with key > threshold.
`QueryGreaterThanOrEqual(key)`	O(log n + k)	All entities with key ≥ threshold.
`QueryLessThan(key)`	O(log n + k)	All entities with key < threshold.
`QueryLessThanOrEqual(key)`	O(log n + k)	All entities with key ≤ threshold.
`QueryGreaterThanReverse(key)`	O(log n + k)	Descending order, key > threshold.
`QueryGreaterThanOrEqualReverse(key)`	O(log n + k)	Descending order, key ≥ threshold.
`QueryLessThanReverse(key)`	O(log n + k)	Descending order, key < threshold.
`QueryLessThanOrEqualReverse(key)`	O(log n + k)	Descending order, key ≤ threshold.
`ContainsKey(key)`	O(log n)	`true` if any entity has this key.
`All()`	O(n)	All entities in ascending key order.
`AllReverse()`	O(n)	All entities in descending key order.
`EnumerateAllReverse()`	O(n)	Zero-allocation descending struct enumerable.
`EnumerateAllReverseByRef()`	O(n)	Zero-allocation descending by-ref enumerable.

(Where n = number of distinct key values, k = number of matching entities.)

Complexity

Operation	Time
Point lookup	O(log n)
Range scan	O(log n + k)
Ordered iteration (cached)	O(1) per element
Insert / Remove	O(log n)
Update (key change)	O(log n) remove + O(log n) insert

Example

table Item(plural: Items, persistence: local, capacity: 50000) {
  Id: int @id
  Name: string
  Price: int @index(name: "ItemsByPrice", kind: sorted_set)
}

// DSL queries that use this index:
// Range: from Items | filter Price >= 100 and Price <= 500
// Top-K: from Items | sort -Price | take 10
// Minimum: from Items | sort Price | take 1

When to Use

Range filters: filter Level >= 10 and Level <= 50
ORDER BY queries: sort -Price
Min/Max queries (via ordered access)
Any query combining equality, range, and ordering on the same column

Limitations

O(log n) per operation vs O(1) for Lookup — use Lookup for pure equality.
Cached snapshot rebuild after mutations is O(n) — acceptable for batch mutations, but consider GroupedSorted for frequently-mutated per-group sorted data.

SortedListIndex<TKey>

Functionally similar to SortedSet, using a dense sorted array instead of a tree. Supports the same query patterns with different performance trade-offs.

Declaration

table Player {
  score: int @index(name: "PlayersByScore", kind: sorted_list)
}

Data Structure

Uses a dense sorted array of object IDs kept in sorted order by key. Range queries use binary search for O(log n) bound location.

API

Supports the same range query methods as SortedSet:

Method	Complexity	Description
`QueryGreaterThan(key)`	O(log n + k)	All entities with key > threshold.
`QueryLessThanOrEqual(key)`	O(log n + k)	All entities with key ≤ threshold.
Range queries	O(log n + k)	All standard range predicates.
Ordered iteration	O(n)	Dense array traversal.

Complexity

Operation	Time
Point lookup	O(log n) via binary search
Range scan	O(log n + k)
Insert	O(n) — requires array shifting
Remove	O(n) — requires array shifting

When to Use

Small collections where insert/remove is infrequent.
Queries that benefit from cache-friendly dense array iteration.
When the compiler maps sorted_list schema declarations.

SortedSet vs SortedList

Property	SortedSet	SortedList
Insert/Remove	O(log n)	O(n)
Range lookup	O(log n + k)	O(log n + k)
Memory layout	Tree nodes (scattered)	Dense array (cache-friendly)
Best for	Large, frequently mutated sets	Small, rarely mutated sets

RangeLookupIndex<TRangeKey>

Answers O(1) EXISTS queries for group-specific range predicates. Designed for patterns like "does any order in group X have quantity > 100?" without scanning.

Declaration

table OrderItem {
  OrderId: int @index(name: "OrderQuantityRange", kind: range_lookup, range: Quantity)
}

Data Structure

Three sparse arrays indexed by int group key, tracking the minimum value, maximum value, and data presence for each group. Initial capacity: 1024 slots. Arrays grow automatically as higher group keys are observed.

API

All query methods are O(1):

Method	Semantics
`ExistsGreaterThan(groupKey, threshold)`	`max > threshold`
`ExistsGreaterThanOrEqual(groupKey, threshold)`	`max >= threshold`
`ExistsLessThan(groupKey, threshold)`	`min < threshold`
`ExistsLessThanOrEqual(groupKey, threshold)`	`min <= threshold`
`ExistsInRange(groupKey, lo, hi)`	`min <= hi && max >= lo` (range overlap)
`ContainsGroup(groupKey)`	`true` if the group has any items
`GetMax(groupKey)`	Maximum range value in the group
`GetMin(groupKey)`	Minimum range value in the group
`EnsureSynchronized()`	Force sync barrier before bulk checks
`EnumerateGroupsGreaterThan(threshold)`	Zero-allocation scan of groups with max > threshold
`EnumerateGroupsGreaterThanOrEqual(threshold)`	Zero-allocation scan of groups with max ≥ threshold

"AssumeSynced" variants (ExistsGreaterThanAssumeSynced, etc.) skip the sync barrier for generated code that has already called EnsureSynchronized() once before a loop.

Incremental Maintenance

Adds update min/max inline — O(1).
Removes that hit a min/max boundary mark the group dirty. Only dirty groups are rebuilt on the next query — not the entire index.

Example

table OrderItem(plural: OrderItems, persistence: local, capacity: 50000) {
  Id: int @id
  OrderId: int @index(name: "OrderQuantityRange", kind: range_lookup, range: Quantity)
  Quantity: int
}

// Query: "Does order #42 have any item with quantity > 100?"
// Compiles to: index.ExistsGreaterThan(42, 100)  → O(1)

When to Use

EXISTS-style range checks within groups (semi-join patterns).
Cross-table filtering: "does the related table have any row matching a range predicate?"
Any pattern where you need a boolean answer about range existence, not the actual rows.

Limitations

Only answers EXISTS questions — does not return matching entities.
Group key must be int (designed for entity ID foreign keys).
Min/max approximation: reports that a range may contain matches (no false negatives, but removing the actual min/max triggers a group rescan).

GroupedSortedIndex<TRangeKey>

Optimized for the common game-client pattern: group by an integer key, then iterate each group in sorted order by a range key (e.g., "top scores per guild", "items by category sorted by price").

Declaration

table Score {
  guild_id: int
  score: int
  @@index(fields: [guild_id], name: "ScoresByGuild", kind: grouped_sorted, range: score)
}

Data Structure

List<Entry>?[] — a sparse array indexed by int group key. Each non-null slot is a sorted list kept in descending order by TRangeKey.

Insertion uses binary search for O(log k) placement within a group of k elements. A parallel tracking array maps each entity to its position for O(1) removal.

API

Method	Complexity	Description
`QueryDirectDescending(groupKey)`	O(1) group access	Zero-allocation descending iteration.
`QueryDirectDescendingByRef(groupKey)`	O(1) group access	By-ref descending (no struct copies).
`QueryDirectAscending(groupKey)`	O(1) group access	Zero-allocation ascending iteration.
`QueryDirectAscendingByRef(groupKey)`	O(1) group access	By-ref ascending.

All enumerables are zero-allocation struct types supporting foreach.

Target Query Pattern

from Scores
| filter GuildId == @guildId
| sort -Score
| take 10

The compiler recognizes this filter + sort + take pattern and routes it to a GroupedSortedIndex. The group is accessed in O(1), and iteration is already in the required descending order — no runtime sort needed.

Example

table Score(plural: Scores, persistence: local, capacity: 100000) {
  Id: int @id
  GuildId: int @index(name: "ScoresByGuild", kind: grouped_sorted, range: Points)
  Points: int
}

// "Top 10 scores in guild #7" → O(1) group access + O(10) iteration
// No sorting at query time — data is pre-sorted.

When to Use

Top-N per group queries (leaderboards, category rankings).
Patterns combining filter GroupKey == X | sort ±RangeKey | take N.
When the group key is a dense integer (entity ID, category enum).

Limitations

Group key must be int (sparse array addressing).
Insertion is O(log k) per group (binary search + list insert with shifting).
Not suitable for groups with very frequent mutations and large group sizes — consider SortedSet in that case.

Aggregation Index (`kind: aggregation`)

Pre-computed per-key (grouped) aggregations over a DbSet — O(1) per metric per group. kind: aggregation is equivalent to kind: universal_aggregation: both compile to the same runtime aggregation-variant class (by default AllStatsAggregationIndex<TKey, TValue>), keyed by the declared index field and aggregating the value: column as entities are added, updated, and removed. The full variant list and API are documented in the Universal Aggregation Index section below.

Declaration

table Player {
  GuildId: int @index(name: "GoldByGuild", kind: aggregation, value: Gold)
}

This keys by GuildId and maintains running Sum, Count, Min, and Max of Gold per guild, exposed through the per-key getters GetSum(key), GetAverage(key), GetCount(key), GetMin(key), and GetMax(key).

No Schema-Declarable Global Aggregation

There is no @index kind: keyword that produces a global (ungrouped, table-wide) aggregation index. A runtime GlobalAggregationIndex<TValue> type does exist — exposing GetGlobalSum(), GetGlobalAverage(), GetGlobalCount(), GetGlobalMin(), GetGlobalMax(), and GetAllGlobalStats() — but it is never emitted by codegen. It is reachable only by manually calling the protected DbSet.CreateGlobalAggregationIndex<TValue> factory from a DbSet subclass. To compute a table-wide aggregate through schema alone, use a per-key aggregation index or accept a full-table scan.

When to Use

Per-group metrics: total gold per guild, average level per region, per-category counts.
Any grouped aggregate that would otherwise require a GROUP BY + aggregation scan.

Limitations

Only supports numeric value types (struct with IComparable<TValue>).
Sum uses long — overflow is possible for very large values.
Value type must be convertible via Convert.ToInt64().

Universal Aggregation Index (`kind: universal_aggregation`)

Pre-computed grouped (per-key) aggregations — O(1) per metric per group. kind: universal_aggregation compiles to one of four runtime aggregation-variant classes (there is no C# type literally named UniversalAggregationIndex); the default is AllStatsAggregationIndex<TKey, TValue>. It is equivalent to kind: aggregation.

ConjureDB provides four aggregation index variants, automatically selected based on the query's aggregation needs:

Variant	Class	Per-Key Footprint	Aggregations
Full stats	`AllStatsAggregationIndex<TKey, TValue>`	~40 bytes	Sum, Avg, Count, Min, Max
Sum + Count	`SumCountAggregationIndex<TKey>`	12 bytes	Sum, Avg, Count
Count only	`CountOnlyAggregationIndex<TKey>`	4 bytes	Count
Distinct count	`DistinctCountAggregationIndex<TKey, TValue>`	Variable (per-group distinct-value set)	Distinct-value count per group

Declaration

table Score {
  GuildId: int @index(name: "TotalScoreByGuild", kind: universal_aggregation, value: Score)
}

Data Structure (AllStatsAggregationIndex)

Dictionary<TKey, AggregationStats> where each stats entry tracks sum, count, min, max, and dirty flags for lazy min/max recomputation.

API

Method	Complexity	Description
`GetSum(key)`	O(1)	Sum for the group.
`GetAverage(key)`	O(1)	`Sum / Count` for the group.
`GetCount(key)`	O(1)	Number of entities in the group.
`GetMin(key)`	O(1) amort.	Minimum value; rescans group if dirty.
`GetMax(key)`	O(1) amort.	Maximum value; rescans group if dirty.
`Keys`	—	`IEnumerable<TKey>` of all group keys.
`EnumerateSums()`	O(n)	Zero-allocation struct enumerable of `(Key, Sum)` pairs.
`EnumerateAllStats()`	O(n)	Zero-allocation struct enumerable of `(Key, Sum, Min, Max, Count)`.
`EnumerateTopSums(limit)`	O(k)	Top-K groups by sum (descending), pre-sorted.
`EnumerateTopAllStats(limit)`	O(k)	Top-K with full stats, pre-sorted.

Lazy Min/Max Recomputation

When an element is removed, the index cannot cheaply determine whether it held the current min or max. Instead, it sets a dirty flag. On the next GetMin or GetMax call, the index rescans the group. Insertions that extend the current extrema clear the flag immediately.

Trade-off: If your workload has frequent deletes and frequent GetMin/GetMax calls, consider a SortedSet index (O(log n) extrema via tree navigation) instead of an aggregation index (O(k) recomputation on dirty min/max, where k = group size).

Ranking Support

When enableRanking is true (default), the index maintains a pre-sorted ranking cache of groups by sum (descending) with ascending key tiebreak. EnumerateTopSums(limit) returns results in O(k) without any sorting at query time.

Example

table Score(plural: Scores, persistence: local, capacity: 100000) {
  Id: int @id
  GuildId: int @index(name: "ScoreStatsByGuild", kind: universal_aggregation, value: Points)
  Points: int
}

// O(1) queries:
// Total points for guild #7:  index.GetSum(7)
// Average points per player:  index.GetAverage(7)
// Top 10 guilds by total:     index.EnumerateTopSums(10)

When to Use

Real-time dashboards: per-guild scores, per-category totals.
Leaderboard aggregates: "which guild has the highest total score?"
Any grouped metric that would otherwise require GROUP BY + aggregation scan.

Limitations

Sum uses long — overflow possible for extremely large values.
Min/Max recomputation after deletes is O(k) per dirty group.
Memory scales with number of distinct groups.

Composite Indexes

Composite indexes use multiple columns as the key. Declared via the fields: list on a table-level @@index:

table Player {
  guild_id: int
  role: string
  @@index(fields: [guild_id, role], name: "PlayerByGuildAndRole", kind: lookup)
}

In schema files, use @@index at the table level:

table Player {
  id: int @id
  guild_id: int
  role: string
  level: int

  @@index(fields: [guild_id, role], name: "PlayerByGuildAndRole", kind: lookup)
  @@index(fields: [level], name: "Level_Sorted", kind: sorted_set)
}

Key Encoding Strategies

For composite keys with low-cardinality string components, packed encodings eliminate heap allocation:

Encoding	Key Layout	Resulting Key Type	Benefit
`Default`	Standard composite key	Tuple / struct	General purpose
`PackedInt32LowCardStringToUInt64`	`int + string` → `ulong`	`ulong`	8-byte key, no string alloc
`PackedUInt8LowCardStringToUInt16`	`byte + string` → `ushort`	`ushort`	2-byte key (≤255 int values, ≤255 strings)
`PackedUInt16LowCardStringToUInt32`	`ushort + string` → `uint`	`uint`	4-byte key (≤65535 int values, ≤65535 strings)

Packed encodings map the string portion to a dense integer via an interning table, then bit-pack it with the integer portion. This enables the composite key to use integer-specialized hash maps for maximum performance.

table Player {
  GuildId: int
  Role: string

  @@index(fields: [GuildId, Role], name: "PlayerByGuildAndRole", kind: lookup,
          encoding: PackedInt32LowCardStringToUInt64)
}

Precondition: The planner must prove that the integer and string values fit within the encoding's range. If selected without satisfying preconditions, runtime will fail fast.

Index Declaration

Indexes are declared in .conjure schema files, either at the field level with @index or at the table level with @@index. Multiple indexes can be declared on the same field by chaining @index(...) annotations:

table Player(plural: Players, persistence: local, capacity: 10000) {
  Id: int @id
  GuildId: int @index(name: "PlayersByGuild", kind: lookup) @index(name: "GuildScoreAgg", kind: universal_aggregation, value: Score)
  Email: string @index(name: "PlayerByEmail", kind: unique)
  Level: int @index(name: "PlayersByLevel", kind: sorted_set)
  Score: int
}

`@index` / `@@index` Option Reference

Option	Applies to	Description
`name:`	both	Required. Unique index name within the table.
`kind:`	both	Index kind: `lookup`, `unique`, `sorted_set`, `sorted_list`, `range_lookup`, `grouped_sorted`, `aggregation`, `universal_aggregation`, `spatial_grid`.
`fields: [...]`	`@@index`	Key columns (composite keys).
`keys: [...]`	both	Additional group/key columns.
`value:`	both	Value column for aggregation indexes (bare identifier).
`range:`	both	Range column for `range_lookup` / `grouped_sorted` (bare identifier).
`included: [...]`	both	Covering columns for index-only scans.
`filter:` / `filter_columns: [...]`	both	Partial index predicate and the columns it references.
`encoding:`	both	Composite key packing strategy.
`dimensions:` / `cell_size:` / `coordinates: [...]`	both	`spatial_grid` layout, cell size, and coordinate columns.

Schema-Based (`.conjure`)

In schema files, indexes can be declared at the field level or table level:

Field-level:

table Player {
  name: string @index(name: "Name_Idx", kind: lookup)
  level: int   @index(name: "Level_Sorted", kind: sorted_set)
}

Table-level (@@index):

table Player {
  id: int @id
  guild_id: int
  level: int

  @@index(fields: [guild_id, level], name: "GuildLevel_Lookup", kind: lookup)
}

Available kind values: lookup, unique, sorted_set, sorted_list, range_lookup, grouped_sorted, aggregation, universal_aggregation, spatial_grid.

Covering Indexes and Index-Only Scans

An included: [...] list duplicates those columns into the secondary index so that a query touching only the index key plus the included columns can be answered from the index without a separate lookup into the primary store.

table Player {
  GuildId: int @index(name: "PlayersByGuild", kind: lookup, included: [Name, Level])
}

// from Players | filter GuildId == 42 | select Name, Level
// Name and Level live in the index, so no separate primary-store lookup is needed.

Unlike a disk-based database, this is not an I/O optimization on ConjureDB. Entities are immutable structs resident in RAM, and the "table dereference" you avoid is an O(1) index into a dense array — not a page fetch — so there is no read I/O to save (the only disk I/O is snapshot/journal writes). The included columns also cost extra memory — they are copied into the index, and memory is the scarce resource for an in-memory database — and the projection still materializes a new row either way. The planner currently costs an index-only scan the same as a full/dense scan (a native covered-row read path is not yet in place), so treat included as a niche memory/shaping tool, not a read-throughput optimization.

Partial (Filtered) Indexes

Partial indexes include only a subset of rows, reducing memory footprint and maintenance cost:

table Player {
  Level: int @index(name: "ActivePlayersByLevel", kind: sorted_set, filter: "static (Player x) => x.IsActive", filter_columns: [IsActive])
}

The optimizer uses filter_columns to determine if a query's WHERE clause implies the index predicate. If the query filters on IsActive == true, the partial index is eligible; otherwise it is not.

Supported on all secondary index types — Lookup, SortedSet, RangeLookup, GroupedSorted, and aggregation indexes all accept filter predicates.

Query Optimizer Integration

The ConjureDB compiler automatically selects the optimal index for each query. Understanding how this works helps you design effective indexes.

Scan Strategy Selection

The ScanStrategyPlanner generates multiple physical alternatives for every table access:

Strategy	Description	When Used
`FullScan`	Iterate all entities in the `PrimaryIndex`	Baseline (always generated)
`PrimaryKeyLookup`	Direct `TryFindById()` via PrimaryIndex	`filter Id == @param`
`SecondaryIndexScan`	Hash lookup via LookupIndex	`filter Column == value`
`SortedSetScan`	Ordered iteration via SortedSetIndex	`sort Column` without filter
`IndexedScan`	Range scan via SortedSetIndex	`filter Column >= X and Column <= Y`
`IndexOnlyScan`	Covering scan over indexed + included columns (currently cost-neutral vs full scan)	Query uses only indexed + included columns

Filter Index Selection

The FilterStrategyPlanner analyzes filter predicates and maps them to index-backed strategies:

Predicate Type	Strategy	Index Type Used
Equality (`==`)	`IndexedLookup`	Lookup or Unique
Range (`>=`, `<=`, `BETWEEN`)	`IndexedRange`	SortedSet
Group + Sort	`GroupedSorted`	GroupedSorted
Primary key	`PrimaryKeyLookup`	PrimaryIndex

The optimizer extracts AND conjuncts from complex predicates and detects range patterns (e.g., X >= lo AND X <= hi → BETWEEN) to select the most efficient index.

Join Optimization

The JoinSecondaryIndexPlanner discovers candidate indexes on the lookup side of joins:

Index Kind	Predicate Type	Join Strategy
Unique	Equality	`UniqueIndexLookup` — always preferred
Lookup	Equality	`SecondaryIndexLookup` — hash probe per row
SortedSet	Range	`SortedSetRange` — range-based probe
SortedSet	Equality	`SecondaryIndexLookup` — hash probe fallback

Cost Model

The optimizer generates all viable alternatives and uses a cost model to select the cheapest plan. Key factors:

Selectivity estimates guide filter strategy ranking.
PGO hints (Profile-Guided Optimization) can override strategy selection based on runtime profiling.
The OptimizationKernelStage performs logical and physical optimization via the Cascades/Volcano framework, exploring alternatives and selecting the cheapest plan.

Foreign Keys and References

Foreign Keys

A @relation annotation declares a foreign-key relationship used by the optimizer for join strategy selection:

table Item {
  Id: int @id
  PlayerId: int @relation(references: Player.Id)
  Name: string
}

The compiler uses relation declarations to:

Infer key bounds for optimization (e.g., DenseHeap strategy).
Select efficient join strategies (index-nested-loop joins via PrimaryIndex).

Injected References

For read-only config tables, declare a @relation to the target; the compiler resolves the reference through the target's PrimaryIndex as an O(1) pointer chase rather than a join:

TemplateId: int @relation(references: ItemTemplate.Id)

This resolves the referenced entity through the target table's PrimaryIndex — an O(1) pointer chase rather than a join. Use for immutable lookup tables (item templates, config data).

SpatialGridIndex

Uniform spatial hash grid for nearby-object queries in 2D or 3D worlds. Space is partitioned into fixed-size cells; entities are assigned to cells based on floor(coord / cellSize). Queries identify candidate cells, iterate their contents, and apply exact Euclidean-distance refinement. Designed for high-frequency proximity lookups typical in game clients — entity detection, area-of-effect, collision pre-filtering.

Declaration

Schema (.conjure):

table GameObject(plural: GameObjects, persistence: local, capacity: 50000) {
  Id: int @id
  PosX: float
  PosY: float
  Name: string

  @@index(fields: [PosX], name: "spatial_pos", kind: spatial_grid,
          coordinates: [PosX, PosY], dimensions: 2, cell_size: 100)
}

Schema (.conjure):

table GameObjects {
  id: int @id
  pos_x: float
  pos_y: float
  pos_z: float
  name: string

  @@index(fields: [pos_x], name: "spatial_pos", kind: spatial_grid,
          coordinates: [pos_x, pos_y], dimensions: 2, cell_size: 100)

  @@index(fields: [pos_x], name: "spatial_pos_3d", kind: spatial_grid,
          coordinates: [pos_x, pos_y, pos_z], dimensions: 3, cell_size: 50)
}

Parameters

Parameter	Type	Default	Description
`dimensions`	int (2 or 3)	`2`	`2` (X, Y) or `3` (X, Y, Z)
`cell_size`	number	`100`	Uniform side length of each grid cell
`coordinates`	column list	—	Coordinate columns; 2 elements for 2D, 3 for 3D

Data Structure

A hash map from integer cell keys (floor(x / cellSize), floor(y / cellSize), …) to lists of dense entity IDs. Only occupied cells consume memory — empty regions of the world have zero cost.

Query Types

Query Kind	Runtime Method	Semantics
Radius	`QueryWithinRadius2D` / `QueryWithinRadius3D`	All entities within Euclidean radius of a center point
Bounds	`QueryWithinBounds2D` / `QueryWithinBounds3D`	All entities inside an axis-aligned bounding box
NearestK	`QueryNearestK2D` / `QueryNearestK3D`	K nearest entities to a center point (exact, deterministic tie-breaking)

All query methods accept a caller-provided Span<int> buffer and return the count of matching entity IDs written into it. Generated code uses stackalloc buffers (default 256 elements) for zero-allocation queries.

DSL Queries

Spatial queries use built-in functions in filter expressions. The compiler detects these patterns and plans a PhysicalSpatialScan instead of a full table scan.

// Find all objects within 50 units of a point
from GameObjects
| filter within_radius(PosX, PosY, @centerX, @centerY, 50.0)
| select Name, PosX, PosY

// Find all objects in a bounding box
from GameObjects
| filter within_bounds(PosX, PosY, @minX, @minY, @maxX, @maxY)
| select Name, PosX, PosY

// 3D radius query
from GameObjects
| filter within_radius(PosX, PosY, PosZ, @cx, @cy, @cz, @radius)
| select Name, PosX, PosY, PosZ

// Combine spatial filter with other predicates
from GameObjects
| filter within_radius(PosX, PosY, @cx, @cy, @radius) and IsActive == true
| select Name, PosX, PosY

When a spatial predicate is combined with non-spatial predicates (e.g., and IsActive == true), the optimizer applies the spatial index for candidate selection and evaluates the remaining predicate as a residual post-filter.

Complexity

Operation	Complexity	Notes
Insert / Remove / Move	O(1)	Hash lookup + list append/remove
Radius / Bounds query	O(cells_in_range × entities_per_cell)	Exact refinement per candidate
NearestK query	O(cells_in_range × entities_per_cell)	Expanding search with exact sort

Cell Size Guidance

Cell size determines the trade-off between query precision and memory/iteration cost:

Cell Size vs. Query Radius	Effect
`cellSize ≈ typical radius`	Optimal — queries touch ~4 cells (2D) or ~8 cells (3D)
`cellSize ≪ radius`	Many cells iterated per query; higher overhead
`cellSize ≫ radius`	Few cells but many false-positive candidates; more refinement work

Rule of thumb: set CellSize close to your most common query radius. For a game with 100-unit interaction range, CellSize = 100 is a good starting point.

When to Use

Proximity queries in 2D/3D game worlds (nearby enemy detection, loot pickup range).
Area-of-effect targeting (splash damage, heal zones).
Collision detection broad phase.
K-nearest-neighbor queries (find closest N allies).
Any workload where entities have spatial coordinates and queries are position-based.

Limitations

Euclidean distance only — no geodesic (spherical) distance, no Manhattan distance.
No toroidal wrap — wrapping worlds are not supported; coordinates are treated as flat Cartesian.
No polygon / arbitrary geometry queries — only axis-aligned bounds and circular/spherical regions.
Coordinate properties must be explicit — auto-detection from composite structs is not supported; list individual float properties.
Static cell size — cell size is set at index declaration and cannot be changed at runtime.
No temporal dimension — moving queries (e.g., trajectory intersection) are not supported.

Custom Collection Types

ConjureDB ships low-level collection types in ConjureDB.Collections. These are the building blocks used internally by every index, and are available for direct use.

High-Performance Hash Maps

General-purpose open-addressing hash tables optimized for different key types.

Property	Value
Load factor	0.75
Collision resolution	Linear probing with displacement tracking

Integer-key variants use power-of-2 capacity with bitwise masking and type-specialized hash functions for optimal performance.

SparseSet<T>

Dual-array data structure: O(1) add, get, remove, contains via swap-and-pop.

Operation	Complexity
Add / Contains / Remove / Get	O(1)
Iteration	O(n) dense, no gaps

OrderStatisticTree

Augmented red-black tree with per-node size field:

Operation	Complexity
Insert / Remove	O(log n)
Select(k)	O(log n) — k-th smallest element
Rank(key)	O(log n) — position of a key

Useful for leaderboard queries with positional lookups.

Pooled Hash Maps

ArrayPool-backed, append-only maps for short-lived aggregation contexts. Rent from the shared pool to avoid GC pressure.

Performance Considerations

Memory Overhead Per Index Type

Index Type	Per-Entity Overhead	Per-Key Overhead	Notes
PrimaryIndex	~12 bytes (dense slot + ID mapping)	—	Always present
Lookup	4 bytes (objectId in list)	Hash bucket overhead	Type-specialized maps reduce overhead
Unique	—	~20 bytes (dictionary entry)	One entry per entity
SortedSet	4 bytes (objectId in group)	~80 bytes (tree node + group)	Plus cached snapshot arrays
RangeLookup	—	~17 bytes (min + max + hasData)	Sparse arrays; empty groups cost nothing
GroupedSorted	~8 bytes (Entry + indexInGroup)	List overhead per group	Sparse array of lists
Aggregation	—	~48 bytes (stats fields)	Per-group stats; equivalent to UniversalAggregation
UniversalAggregation	—	12–40 bytes per group (variant-dependent)	Dictionary + stats struct
SpatialGrid	4 bytes (objectId in cell list)	Hash bucket per occupied cell	Only occupied cells consume memory

Update Cost

Index Type	Insert	Remove	Key Change
Lookup	O(1)	O(1)	O(1) + O(1)
Unique	O(1)	O(1)	O(1) + O(1)
SortedSet	O(log n)	O(log n)	O(log n) + O(log n)
SortedList	O(n)	O(n)	O(n) + O(n)
RangeLookup	O(1)	O(1) amort.	O(1) amort.
GroupedSorted	O(log k)	O(1)	O(log k) + O(1)
Aggregation	O(1)	O(1) amort.	O(1) amort.
UniversalAggregation	O(1)	O(1) amort.	O(1) amort.
SpatialGrid	O(1)	O(1)	O(1) (re-hash to new cell)

When NOT to Index

Very small tables (< 100 rows): Full scan is faster than index maintenance.
Write-heavy, read-light columns: Index update cost outweighs query benefit.
High-cardinality unique columns already covered by PrimaryIndex: Redundant.
Columns never used in filters, sorts, or joins: Dead index overhead.

Index Count Guidelines

1–3 secondary indexes per table is typical for game-client workloads.
Each index adds deferred-commit processing to every transaction.
The optimizer considers all declared indexes — unused indexes only waste memory and update time.
Use PGO recommendations to identify which indexes are actually exercised.

PGO Index Recommendations

Profile-Guided Optimization (PGO) can provide index guidance, but the current repository supports that through two bounded paths, not a single "complete index oracle".

How PGO Suggests Indexes

Profile-side evidence collection
- profiling/export produces canonical AutoIndexCandidates and GroupedIndexProfiles in the PgoProfile.
- these candidates carry normalized descriptors, evidence metadata, what-if deltas, and reason codes.
Compile-time what-if planning
- the planning-owned AutoIndexAdvisor builds hypothetical one-index schema overlays and re-plans the query to estimate marginal benefit.
- candidates are deterministically bucketed into recommended, held-back, and suppressed sets under explicit per-table/global/write/ memory budgets.
- the compiler writes a derived auto-index-report.json and exposes the same advisory summary through PlanExplain.AutoIndexAdvisory.

Today, the strongest supported claim is that PGO helps discover and rank useful indexes for covered shapes in a report-only workflow. The repository does not claim that PGO always discovers the full globally optimal index set for every query or workload.

Covered guidance today

Full table scans that could be avoided with an index.
Missing filter support for covered predicate shapes.
Join predicates without index support for covered join patterns.
Sort / TopN patterns where ordered access would be cheaper.
Grouped-index usage from runtime profile data.

Each recommendation/report includes rationale, evidence quality, status, and what-if metadata in structured output.

Accepting Recommendations

The AutoIndexingMode.ReportOnly advisor mechanism and the auto-index analyze / show / patch / decide CLI review loop are documented canonically in Profile-Guided Optimization. That advisor is report-only: it never auto-creates indexes, mutates schema, or routes candidates into runtime/codegen.

Index-selection-specific note: PGO advisory candidates are accepted through explicit schema ownership — once you decide to take a recommendation, add the chosen @index / @@index declaration to your .conjure schema yourself, then re-compile and re-profile to verify the improvement. See the CLI-first review loop for evidence inspection and patch/decision workflow.

Profile-Driven Index Lifecycle

Profile query workload  →  PGO/runtime advisor surfaces canonical candidates
      ↓
Compile with ReportOnly  →  what-if planning ranks candidates
      ↓
Accept explicitly via @index / @@index schema declarations
      ↓
Re-compile  →  Optimizer uses new indexes
      ↓
Re-profile  →  Verify improvement, remove unused indexes

Best Practices

Choosing the Right Index Type

Query Pattern	Recommended Index	Why
`filter X == value`	Lookup	O(1) hash lookup
`filter X == value` (unique)	Unique	O(1) + integrity guarantee
`filter X >= lo and X <= hi`	SortedSet	O(log n + k) range scan
`sort X` / `sort -X`	SortedSet	Cached ordered arrays
`sort X \| take 1` (min/max)	SortedSet	First/last element of cached array
`filter GroupKey == x \| sort -Y \| take N`	GroupedSorted	Pre-sorted groups, O(1) access
"Does group X have any Y > Z?"	RangeLookup	O(1) EXISTS check
`select sum(X), count(X) group by Y`	UniversalAggregation	Pre-computed O(1) per group
Unique constraint enforcement	Unique	Throws on duplicate
`filter within_radius(X, Y, ...)`	SpatialGrid	Spatial hash grid, O(cells × ents/cell)
`filter within_bounds(X, Y, ...)`	SpatialGrid	Spatial hash grid, AABB candidate selection
Nearest-K entities to a point	SpatialGrid	Exact K-nearest with deterministic tie-breaking

Index Naming Conventions

Use descriptive names: PlayersByGuild, ItemsByPrice, ScoreStatsByGuild.
For composite keys: PlayerByGuildAndRole.
For aggregations: TotalScoreByGuild, GlobalGold.
For partial indexes: ActivePlayersByLevel.

Common Game Patterns

Inventory System

table Item(plural: Items, persistence: local, capacity: 5000) {
  Id: int @id
  PlayerId: int @relation(references: Player.Id) @index(name: "ItemsByPlayer", kind: lookup) @index(name: "ItemsByPlayerSortedByRarity", kind: grouped_sorted, range: Rarity)
  Rarity: int @index(name: "ItemsByRarity", kind: sorted_set)
  Name: string
  Quantity: int
}

// "All items for player #42":             filter PlayerId == 42
// "Player #42's rarest items":            filter PlayerId == 42 | sort -Rarity | take 5
// "All legendary items (rarity >= 90)":   filter Rarity >= 90

Leaderboard

table Score(plural: Scores, persistence: local, capacity: 100000) {
  Id: int @id
  PlayerId: int @index(name: "ScoresByPlayer", kind: lookup)
  Points: long @index(name: "ScoresSorted", kind: sorted_set)
  GuildId: int @index(name: "ScoreStatsByGuild", kind: universal_aggregation, value: Points) @index(name: "TopScoresByGuild", kind: grouped_sorted, range: Points)
}

// Global top 10:                   sort -Points | take 10
// Guild #7 total:                  index.GetSum(7)
// Guild #7 top 10:                 filter GuildId == 7 | sort -Points | take 10
// Top 5 guilds by total score:     index.EnumerateTopSums(5)

Config Lookup

table ItemTemplate(plural: ItemTemplates, persistence: none, capacity: 1000) {
  Id: int @id
  Code: string @index(name: "TemplateByCode", kind: unique)
  Name: string
  BasePrice: int
}

// Unique lookup by code:  filter Code == "SWORD_01" | single
// Never duplicates — UniqueIndex throws on insert conflict.

Getting Started — Setup and basic usage
Query Language — DSL syntax reference
Compiled Queries — How the compiler selects indexes
PGO — Profile-Guided Optimization and index recommendations

Overview​

Why Indexes Matter​

Index Categories​

Index Types at a Glance​

Index Types​

PrimaryIndex<T>​

Storage​

API​

Capacity Growth​

Thread Safety​

When to Use​

LookupIndex<TKey>​

Declaration​

Data Structure​

API​

Null Handling​

Partial Index Support​

Complexity​

When to Use​

Limitations​

UniqueIndex<TKey>​

Declaration​

Data Structure​

API​

Uniqueness Enforcement​

Example​

When to Use​

Limitations​

SortedSetIndex<TKey>​

Declaration​

Data Structure​

API​

Complexity​

Example​

When to Use​

Limitations​

SortedListIndex<TKey>​

Declaration​

Data Structure​

API​

Complexity​

When to Use​

SortedSet vs SortedList​

RangeLookupIndex<TRangeKey>​

Declaration​

Data Structure​

API​

Incremental Maintenance​

Example​

When to Use​

Limitations​

GroupedSortedIndex<TRangeKey>​

Declaration​

Data Structure​

API​

Target Query Pattern​

Example​

When to Use​

Limitations​

Aggregation Index (kind: aggregation)​

Declaration​

No Schema-Declarable Global Aggregation​

When to Use​

Limitations​

Universal Aggregation Index (kind: universal_aggregation)​

Declaration​

Data Structure (AllStatsAggregationIndex)​

API​

Lazy Min/Max Recomputation​

Ranking Support​

Example​

When to Use​

Limitations​

Composite Indexes​

Key Encoding Strategies​

Index Declaration​

@index / @@index Option Reference​

Schema-Based (.conjure)​

Covering Indexes and Index-Only Scans​

Partial (Filtered) Indexes​

Overview

Why Indexes Matter

Index Categories

Index Types at a Glance

Index Types

PrimaryIndex<T>

Storage

API

Capacity Growth

Thread Safety

When to Use

LookupIndex<TKey>

Declaration

Data Structure

API

Null Handling

Partial Index Support

Complexity

When to Use

Limitations

UniqueIndex<TKey>

Declaration

Data Structure

API

Uniqueness Enforcement

Example

When to Use

Limitations

SortedSetIndex<TKey>

Declaration

Data Structure

API

Complexity

Example

When to Use

Limitations

SortedListIndex<TKey>

Declaration

Data Structure

API

Complexity

When to Use

SortedSet vs SortedList

RangeLookupIndex<TRangeKey>

Declaration

Data Structure

API

Incremental Maintenance

Example

When to Use

Limitations

GroupedSortedIndex<TRangeKey>

Declaration

Data Structure

API

Target Query Pattern

Example

When to Use

Limitations

Aggregation Index (`kind: aggregation`)

Declaration

No Schema-Declarable Global Aggregation

When to Use

Limitations

Universal Aggregation Index (`kind: universal_aggregation`)

Declaration

Data Structure (AllStatsAggregationIndex)

API

Lazy Min/Max Recomputation

Ranking Support

Example

When to Use

Limitations

Composite Indexes

Key Encoding Strategies

Index Declaration

`@index` / `@@index` Option Reference

Schema-Based (`.conjure`)

Covering Indexes and Index-Only Scans

Partial (Filtered) Indexes