Indexes
Setup shared by the examples on this page
import { OIMDB, OIMEffectService, OIMReclaimingIndexKeysService, OIMSetBucketContentService, OIMSlotAtUnholdReleasePolicy, createOIMComputedService, createOIMSortedComputedService, createOIMSlotCollectionIndexService, createOIMSlotCollectionSortedArrayIndexService, isOIMSameSlotSequence, type TOIMEntitySlot, createOIMEntityContentService, createOIMSlotCollectionService, OIMSlotTreeStoreService, OIMDefaults, type TOIMBucketSlot, type TOIMBucketSlotsArrayStore, type TOIMStoreKey, OIMScalarKeyTreeWalk } from '@oimdb/core';
type Card = { id: string; deck: string; rank: number };
declare function render(value?: unknown): void;
const db = new OIMDB();
const effectService = OIMEffectService.INSTANCE;
const cardService = createOIMSlotCollectionService({ slotContentService: createOIMEntityContentService<Card>() });
const cards = cardService.createStoreSlot(db);
const cardContentService = cardService.slotContentService;
const byRank = (leftBucketMemberSlot: TOIMEntitySlot<Card>, rightBucketMemberSlot: TOIMEntitySlot<Card>): number =>
(leftBucketMemberSlot.entity?.rank ?? 0) - (rightBucketMemberSlot.entity?.rank ?? 0);
An index is a bucket collection whose buckets are filled from an entity store slot by selectKey: every
write to the source decides which bucket the entity belongs to. Its buckets are the same
buckets a caller fills by hand; why it is shaped this way is on
Why an index looks like this.
How an index files entities
Use an index when the bucket an entity belongs to is a function of the entity
(card.deck, a status, an owner id), so every write can decide it. When the members
come from a response instead, take a manual bucket collection.
Why an index is a pushed bucket plus a pulled order is on its own page:
Why an index looks like this.
writeSlotContentByKey, updateEntity, clearSlotContentselectKey or columns gives each entity its key; a write that moves the key refiles it'todo'the entity slots with that key'done'one bucket per key, minted when the key is first filed or asked forcreateOIMSortedComputedService: one ordered array per bucket, re-sorted only when membership or a sort column movesThe index service is built once per entity collection type; createIndexStoreSlot(entityStoreSlot)
builds one index over one entity store slot, and returns the index's own store slot of buckets.
Setup shared by the examples on this page
const deckIndexService = createOIMSlotCollectionIndexService({
entityService: cardService, // the entity collection it reads
selectKey: (card: Card) => card.deck, // which key an entity belongs to
});
const deckIndex = deckIndexService.createIndexStoreSlot(cards);
const deckBucketReads = deckIndexService.slotContentService;
const red = deckIndexService.holdSlotByKey(deckIndex, 'red'); // the bucket; minted on first hold
cardService.writeSlotContentByKey(cards, 'c1', { id: 'c1', deck: 'red', rank: 1 });
db.flush();
Array.from(deckBucketReads.getBucketMemberSlots(red)); // [c1]
createOIMSlotCollectionIndexService(options) builds the index over a Map store of buckets. Its options:
| Option | Default | What it decides |
|---|---|---|
entityService | required | the source collection service; only its getSlots is used, to fill a new bucket |
columns / selectKey | one of them required | where the key comes from |
slotContentService | new OIMPositionalArrayBucketContentService(), with no recorder | how a bucket holds its slots: pass new OIMSetBucketContentService() for no order, or one built with bucketCommands for a render script |
bucketSlotStoreService | a Map store; required for an array key | where buckets are filed |
slotReleasePolicy | defaults.slotReleasePolicy, then OIMSlotAtEmptyReleasePolicy.INSTANCE | how long a bucket lives |
columnSlotStoreService / columnNames | a shared map-driven store | where bucket column slots live |
The index-keys strategy comes from defaults (new OIMDefaults({ indexKeysService }), see
below). A key of several columns takes
the composite-key door, which sets a tree-driven store.
const unorderedDeckIndexService = createOIMSlotCollectionIndexService({
entityService: cardService,
selectKey: (card: Card) => card.deck,
slotContentService: new OIMSetBucketContentService<TOIMEntitySlot<Card>>(),
});
const unorderedDeckIndex = unorderedDeckIndexService.createIndexStoreSlot(cards);
The default buckets keep arrival order. Only the array-based content services answer by position:
getBucketMemberSlotAt(bucketSlot, index) reads the array at that index, O(1), and
getBucketMemberSlotPosition(bucketSlot, entitySlot) walks the array, O(n), returning
-1 for a slot that is not a member. A set has no positions, so a set-driven index has neither. Take the
set-driven one when you read neither arrival order nor positions: its membership test and removal are a
hash lookup.
OIMSlotCollectionIndexService is a collection service of buckets, so it has every read door of one. Its
slotContentService is the bucket content service narrowed by type to its reads — the index is the only
writer of its buckets. A door that names a key takes the index's store slot first; a door on a bucket takes
only the bucket slot:
| Doors | What for |
|---|---|
getSlotByKey, holdSlotByKey, peekSlotByKey, hasSlotContentByKey, getSlotsByKeys, holdSlotsByKeys, slot.owner.unholdSlot | the bucket of a key |
slotContentService.getBucketMemberSlots, getBucketMemberSlotCount, hasBucketMemberSlot; getEntitiesByKey(indexStoreSlot, key) | what a bucket holds |
slotContentService.getBucketMemberSlotAt, getBucketMemberSlotPosition | positional reads, on an array-based content service only |
getSlots, getSlotCount | which buckets are filed |
getAnyBucketColumnSlotByKey, holdAnyBucketColumnSlotByKey | the bucket's any-column slot |
getBucketColumnSlotByKey, holdBucketColumnSlotByKey, unholdColumnSlot | bucket column slots; unholdColumnSlot also gives back an any-column slot |
disposeIndexStoreSlot | taking one index off its source |
The channel slot of an index store slot is its source store slot's.
Where the key comes from: columns, selectKey, or both
The same pair as the sorter's sortColumns / comparator:
const byColumn = createOIMSlotCollectionIndexService({ entityService: cardService, columns: ['deck'] });
const byFunction = createOIMSlotCollectionIndexService({ entityService: cardService, selectKey: (card: Card) => card.deck });
const byFunctionOfColumns = createOIMSlotCollectionIndexService({
entityService: cardService,
columns: ['deck'],
selectKey: (card: Card) => card.deck.toLowerCase(),
});
columnsalone with ONE column: the key is its value, typed byTOIMIndexKeyfrom that column, which must hold a store key. Several columns make a composite key, the array of their values in that order, and take the composite-key door — see A key of several columns.selectKeyalone is any function, and it runs again on every write to the source: a function does not say which columns it reads.- Both: the columns are the ones
selectKeyreads.
With columns, a patch or put whose changed columns include none of them keeps the
entity's key and calls nothing. A write of the whole value — a fill, a clear,
markEntityChanged(slot) with no names — always reads the key again.
A slot with no entity is filed under no bucket, and neither is an entity whose
selectKey returns undefined. createOIMSlotCollectionIndexService constrains the key to TOIMStoreKey unless it is handed
a bucketSlotStoreService, createOIMSlotCollectionIndexService to an array of TOIMStoreKey, and a key
type handed to them by hand must be assignable to the one TOIMIndexKey computes from columns.
A key of several columns
An array key needs a bucket store that compares arrays part by part: pass bucketSlotStoreService, an
OIMSlotTreeStoreService over OIMScalarKeyTreeWalk.INSTANCE. Name two or more columns and the key
is the array of their values, in that order:
type PlayingCard = { id: string; deck: string; suit: string };
const playingCardService = createOIMSlotCollectionService({ slotContentService: createOIMEntityContentService<PlayingCard>() });
const playingCards = playingCardService.createStoreSlot(db);
type TDeckAndSuitBucket = TOIMBucketSlot<TOIMBucketSlotsArrayStore<TOIMEntitySlot<PlayingCard>>, readonly [string, string]>;
const byDeckAndSuitService = createOIMSlotCollectionIndexService({
entityService: playingCardService,
columns: ['deck', 'suit'],
selectKey: (card: PlayingCard): readonly [string, string] => [card.deck, card.suit],
bucketSlotStoreService: new OIMSlotTreeStoreService<TOIMStoreKey, TDeckAndSuitBucket>(OIMScalarKeyTreeWalk.INSTANCE),
});
const byDeckAndSuit = byDeckAndSuitService.createIndexStoreSlot(playingCards);
byDeckAndSuitService.getEntitiesByKey(byDeckAndSuit, ['red', 'hearts']);
- The key type comes from the columns (
TOIMIndexKey<TEntity, TColumns>): one column is that column's value withoutundefined, several are a tuple of their values, so['deck', 'suit']above is keyed byreadonly [string, string]and a one-column index refuses an array. Columns must be written inline oras const: astring[]variable carries no length, so its key could be either a value or an array, and both doors refuse it. - The index's bucket store is that
OIMSlotTreeStoreService. To tell whether an entity's key moved, the index asks its bucket storeisSameKey. - A
selectKeyreturning an array ofTOIMStoreKeytakescreateOIMSlotCollectionIndexServicewith a tree store passed asbucketSlotStoreService. - Each write that reads the key builds one array; a fresh array with the same parts is the same key, so it moves nothing and wakes nothing.
getSlotsByKeys/holdSlotsByKeysfill every new bucket either way, but only a scalar key gets the ONE pass over the source: array keys are filled one pass per key, the cost of callinggetSlotByKeyfor each.
No bucket exists for a key until it is minted. A bucket minted through any door
(getSlotByKey, holdSlotByKey, getSlotsByKeys, holdSlotsByKeys, getEntitiesByKey) is filled with the
source entities written before it, without a flush, so minting inside an effect body does not throw.
getSlotsByKeys / holdSlotsByKeys fill all new buckets in ONE pass over the source
— take them when you mint many keys at once, such as every column of a board.
The usual way to consume one is an effect on the bucket:
const red = deckIndexService.holdSlotByKey(deckIndex, 'red');
effectService.createAndRunEffect(db, () => render(Array.from(deckBucketReads.getBucketMemberSlots(red))), [red]);
The bucket wakes on membership only — an entity joining or leaving it. A write to an entity that stays in the bucket does not wake it; each entity is subscribed to through its own slot.
What a write costs, and how long a bucket lives
- A key with no bucket is not maintained at all. No slots, no service calls — an entity arriving under such a key costs one key read, one comparison and, when its key changed, one write of its index-key cell. What decides it is whether the bucket exists, not whether anyone holds it: while a bucket stands it is maintained, held or not, and a key whose bucket was released goes back to costing nothing.
- Entities are filed on write, using the index's key, through the source store slot's content-change hook.
- A bucket's lifetime is the
slotReleasePolicy, not the index's. Name nothing (here or on the db) and you getOIMSlotAtEmptyReleasePolicy.INSTANCE: an unheld bucket stays, and goes on being maintained, while it has members, and goes once it is empty. PassOIMSlotNeverReleasePolicy.INSTANCEand a bucket stands for good;new OIMSlotAfterIdleReleasePolicy({ keepAfterIdleMs })and it cools on the queue;OIMSlotAtUnholdReleasePolicy.INSTANCEand it ends at the last give-back, and the next hold builds a fresh one with one scan of the source. The policies themselves: Releasing an identity on a clock. - Order is not the bucket's business. A sorted list is
createOIMSortedComputedServiceover the index service (Ordering). Compose a second computed over the bucket for filtering or any other order.
const deckIndexOnlyWhileHeldService = createOIMSlotCollectionIndexService({
entityService: cardService,
selectKey: (card: Card) => card.deck,
slotReleasePolicy: OIMSlotAtUnholdReleasePolicy.INSTANCE,
});
const deckIndexOnlyWhileHeld = deckIndexOnlyWhileHeldService.createIndexStoreSlot(cards);
Use OIMSlotAtUnholdReleasePolicy when keys are many and each is looked at briefly (a details panel
per user); keep the default when a few keys are read over and over.
An order of your own is a derivation over the bucket:
const rankedInDeckService = createOIMComputedService<string, readonly TOIMEntitySlot<Card>[]>({
createSources: ({ key }) => ({
sourceSlots: [deckIndexService.getSlotByKey(deckIndex, key)],
}),
derive: (computedSlot) => Array.from(
deckBucketReads.getBucketMemberSlots(deckIndexService.getSlotByKey(deckIndex, computedSlot.key)),
).sort(byRank),
sameValueGuard: isOIMSameSlotSequence,
initialValue: [],
});
const rankedInDeck = rankedInDeckService.createStoreSlot(db);
The bucket is named in sourceSlots, so the computed holds it for
as long as the composed order is filed.
Disposing an index
createIndexStoreSlot(entityStoreSlot) is the whole wiring of one index: it registers a
content-change listener on that store slot (OIMSlotContentChangeListenerService.INSTANCE), and the entity
collection knows nothing about indexes. disposeIndexStoreSlot(indexStoreSlot) unsubscribes that index
from its source, empties its buckets and gives back every entity slot it held. The minting doors on that
index store slot (getSlotByKey, holdSlotByKey, getSlotsByKeys, holdSlotsByKeys, getEntitiesByKey,
the bucket column doors) throw after it, because the index no longer hears its source; the give-backs
(slot.owner.unholdSlot, unholdColumnSlot) still work, so a consumer tearing down after the index
does not have to know the order. The index service and its other store slots are untouched.
const temporaryIndex = deckIndexService.createIndexStoreSlot(cards);
deckIndexService.disposeIndexStoreSlot(temporaryIndex);
The bucket's any-column slot
For a reader that needs the whole list every time a member's content changes, the
index hands out a bucket's any-column slot: getAnyBucketColumnSlotByKey(indexStoreSlot, key) and
holdAnyBucketColumnSlotByKey(indexStoreSlot, key), given back with unholdColumnSlot. It is a
TOIMColumnSlot on the bucket slot, and it wakes when any column of any member of
that bucket changes and when a member joins or leaves, because its value lists the members'
entities. The bucket slot (getSlotByKey / holdSlotByKey) wakes on membership alone.
const redBucket = deckIndexService.holdSlotByKey(deckIndex, 'red');
const redAnyColumn = deckIndexService.holdAnyBucketColumnSlotByKey(deckIndex, 'red');
const redEffect = effectService.createEffect(db, () => {
render(deckIndexService.getEntitiesByKey(deckIndex, 'red'));
}, [redBucket, redAnyColumn]);
effectService.disposeEffect(redEffect);
redAnyColumn.unholdSlot();
redBucket.unholdSlot();
Do not use it to render a list. One edit of one entity wakes the whole list, so a view bound to it re-renders every item for a one-field change. Subscribe the list to the bucket and each entity to its own slot. The any-column slot is for an export, an aggregate over the entities, or a log.
It costs nothing until asked for: an entity write is checked against it only after the
first getAnyBucketColumnSlotByKey / holdAnyBucketColumnSlotByKey. A
getAnyBucketColumnSlotByKey nobody kept is gone at the next flush().
The content-change hook and indexKeys
An index is a content-change listener on its source store slot. To push a derivation per
write the way an index does, add your own with
OIMSlotContentChangeListenerService.INSTANCE.addContentChangeListener(storeSlot, listener, readColumnNames)
and remove it with removeContentChangeListener(storeSlot, listener). An IOIMSlotContentChangeListener
has onContentChanged(slot, patch, changedColumns) and onManyContentsChanged(...), which a batch
write calls once. readColumnNames undefined means every column. addContentChangeListener returns the
listener's TOIMSlotContentChangeListenerReadColumns (declaredColumnNames, addedColumnNames, isAnyColumnAdded);
addListenerReadColumn(storeSlot, listener, columnName) and addListenerReadAnyColumn(storeSlot, listener) add reads
to it later, and the util isOIMAnyAddedColumnRead(listenerReadColumns, changedColumns) tells whether a write hit one of them. Listeners on one store slot share
one column filter, so a listener still checks changedColumns itself. Anything that can be pulled
belongs in a computed instead.
Each entity slot remembers, per index, the key it is filed under, so a moved entity leaves its old
bucket in O(1). How that memory is kept is chosen by the defaults an index is built with,
new OIMDefaults({ indexKeysService }):
| strategy | on disposeIndexStoreSlot | cost |
|---|---|---|
OIMAppendingIndexKeysService (default) | the index's position is not reused | each index ever created on a source leaves one entry on the slots it filed |
OIMReclaimingIndexKeysService | the position is wiped on every slot of the source and reused | O(N) per dispose |
const shortLivedIndexDefaults = new OIMDefaults({ indexKeysService: new OIMReclaimingIndexKeysService() });
const byRankService = createOIMSlotCollectionIndexService({ defaults: shortLivedIndexDefaults, entityService: cardService, selectKey: (card: Card) => card.rank });
Switch to OIMReclaimingIndexKeysService only if you create indexes dynamically and often. That is
expensive, so avoid it.
Ordering
A bucket never sorts, except the bucket of a createOIMSlotCollectionSortedArrayIndexService index. Its order is
what the caller or the arrivals put in: addBucketMemberSlots appends, insertBucketMemberSlotAt inserts, a
move moves, writeSlotContent takes the sequence given. A sorted list is a computed over an index —
createOIMSortedComputedService({ indexService, sortColumns?, comparator? }), then
createSortedStoreSlot(indexStoreSlot) for each index — or the
index sorts its own buckets, see Sorted at write.
Take it when the order is a function of the entities' columns; take
positions when the user decides it.
const cardsInDeckService = createOIMSlotCollectionIndexService({
entityService: cardService,
selectKey: (card: Card) => card.deck,
});
const cardsInDeck = cardsInDeckService.createIndexStoreSlot(cards);
const cardsByRankService = createOIMSortedComputedService({
indexService: cardsInDeckService,
sortColumns: [{ columnName: 'rank', direction: 'asc' }],
});
const cardsByRank = cardsByRankService.createSortedStoreSlot(cardsInDeck);
const red = cardsByRankService.holdSlotByKey(cardsByRank, 'red');
effectService.createAndRunEffect(db, () => { render(red.value); }, [], [red]);
red.unholdSlot();
-
indexServiceis theOIMSlotCollectionIndexServicewhose buckets the sorted list reads, and the index store slot handed tocreateSortedStoreSlotis the index it reads them from. The sorted service takes no db: its store slots run on the index store slot's channel slot. -
sortColumns—TOIMSortColumn<TEntity>[], each{ columnName, direction: 'asc' | 'desc' },columnaTOIMSortableColumnName<TEntity>(string, number or bigint values) — decide which writes re-sort. -
comparator: (left: TEntity, right: TEntity) => numberdecides the order. Without it the order iscreateOIMColumnsComparator(sortColumns): the columns in turn, an undefined or null value last in either direction. An entity slot whose entity is gone sorts last. -
Only
comparator→ any write to a member re-sorts. Neither → a member keeps the place it first took and an arrival is appended. -
Both → the two split the job:
comparatororders, andsortColumnsis the list of columns whose change wakes the sort. List every column the comparator reads. A change to a column it reads butsortColumnsomits does not re-sort — the list keeps its old order until something listed changes. Reach for this when the order needs a rulecreateOIMColumnsComparatorcannot express (a locale compare, a computed key, a tie-break) and you still want the sort to wake only for the columns that rule reads, instead of for every write to a member as withcomparatoralone:type TitledCard = { id: string; deck: string; title: string; rank: number; note: string };const titledCardService = createOIMSlotCollectionService({ slotContentService: createOIMEntityContentService<TitledCard>() });const titledCards = titledCardService.createStoreSlot(db);const titledCardsInDeckService = createOIMSlotCollectionIndexService({entityService: titledCardService,selectKey: (card: TitledCard) => card.deck,});const titledCardsInDeck = titledCardsInDeckService.createIndexStoreSlot(titledCards);const byTitleInGermanService = createOIMSortedComputedService({indexService: titledCardsInDeckService,sortColumns: [{ columnName: 'title', direction: 'asc' }, { columnName: 'rank', direction: 'asc' }],comparator: (left, right) => left.title.localeCompare(right.title, 'de') || left.rank - right.rank,});const byTitleInGerman = byTitleInGermanService.createSortedStoreSlot(titledCardsInDeck);// a write to `title` or `rank` re-sorts; a write to any other column does not
It re-sorts only when the bucket's membership changed or a write changed one of its
columns on a member: its sources are the bucket slot of the key plus the
bucket column slot of each column (or the bucket's any-column slot when only a
comparator is given). Its slots are computed slots: pulled, re-derived on the read that
asks, subscribed to in the sourceComputeds list of createEffect. Read the value through
slot.value, which settles the order before answering. A
re-sort that yields the same sequence keeps the previous array, so a consumer
memoising on identity needs no comparison of its own. The sorted array names each
member slot once, even over a bucket that names one twice. Why this is a pull and
membership is a push: Why an index looks like this.
Bucket column slots. An index hands out one column slot per bucket and column —
getBucketColumnSlotByKey(indexStoreSlot, key, columnName), holdBucketColumnSlotByKey(indexStoreSlot, key, columnName),
unholdColumnSlot(columnSlot). It is a TOIMColumnSlot whose carrierSlot is the
bucket slot, written when a write changes that column on any member of the bucket and when a
member joins or leaves (its value is that column across the members).
Subscribe to one when you need "some member's rank moved" without "some member's
title moved":
const rankInRed = deckIndexService.holdBucketColumnSlotByKey(deckIndex, 'red', 'rank');
const onRankInRed = effectService.createEffect(db, () => { render(); }, [rankInRed]);
effectService.disposeEffect(onRankInRed);
rankInRed.unholdSlot();
An index marks bucket column slots only once somebody has asked for one, so an index nobody sorts pays nothing for them.
A comparator that throws is thrown at the reader that asked — out of the sorted
computed's getValueForSlot. The derive is not stamped as run, so the next read runs the
comparator again; the bucket under it is untouched.
Sorted at write
The sorted computed above sorts at read, over any index. The other arm keeps the index's
own buckets in order, so a read needs no computed. You pick one at construction:
createOIMSlotCollectionSortedArrayIndexService({ entityService, columns? | selectKey?, sortColumns, bucketCommands?, bucketSlotStoreService?, slotReleasePolicy?, columnSlotStoreService? | columnNames? })
returns an OIMSlotCollectionSortedArrayIndexService. sortColumns is the same TOIMSortColumn<TEntity>[]
that createOIMSortedComputedService takes, and it is required.
const cardsByDeckService = createOIMSlotCollectionSortedArrayIndexService({
entityService: cardService,
columns: ['deck'],
sortColumns: [{ columnName: 'rank', direction: 'asc' }, { columnName: 'id', direction: 'desc' }],
});
const cardsByDeck = cardsByDeckService.createIndexStoreSlot(cards);
const spades = cardsByDeckService.holdSlotByKey(cardsByDeck, 'spades');
Array.from(spades.getBucketMemberSlots());
cardsByDeckService.slotContentService.getBucketMemberSlotAt(spades, 0);
- Reads come back in order.
getBucketMemberSlots,getBucketMemberSlotAtandgetBucketMemberSlotPositionanswer insortColumnsorder. - Sorted on the first read. A write appends the arrival to an unsorted tail, and the first read settles it. A bucket nobody reads is not sorted.
- A member is re-filed when one of its sort columns changes, and only then. A write to a column that is neither the key nor a sort column neither reorders the bucket nor wakes it.
- There are no positional writes on this bucket. The order belongs to the comparator,
so
insertBucketMemberSlotAtand the other position writes stay onOIMPositionalArrayBucketContentService. - The render script is the whole list. Given
bucketCommands, the bucket records every change asisWholeListRecordedand no commands, because the next settle could move any position a command would name. A view over it rebuilds fromgetBucketMemberSlots()in the frame the bucket changed; withoutbucketCommandsnothing is recorded.
Which arm to take: sort-at-write suits point updates, where a rank change re-files one member. Sort-at-read suits bulk loads. Both ship; neither is the default.