Skip to content

Commit 5f43d5f

Browse files
kevin-dpkevin-dp
authored
Reverse index (#627)
* Reverse index if direction doesn't match. * Changeset
1 parent 56b870b commit 5f43d5f

7 files changed

Lines changed: 284 additions & 24 deletions

File tree

‎.changeset/lemon-poems-raise.md‎

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,5 @@
1+
---
2+
"@tanstack/db": patch
3+
---
4+
5+
Optimization: reverse the index when the direction does not match.

‎packages/db/src/collection/subscription.ts‎

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -5,7 +5,7 @@ import {
55
createFilteredCallback,
66
} from "./change-events.js"
77
import type { BasicExpression } from "../query/ir.js"
8-
import type { BaseIndex } from "../indexes/base-index.js"
8+
import type { IndexInterface } from "../indexes/base-index.js"
99
import type { ChangeMessage } from "../types.js"
1010
import type { CollectionImpl } from "./index.js"
1111

@@ -38,7 +38,7 @@ export class CollectionSubscription {
3838

3939
private filteredCallback: (changes: Array<ChangeMessage<any, any>>) => void
4040

41-
private orderByIndex: BaseIndex<string | number> | undefined
41+
private orderByIndex: IndexInterface<string | number> | undefined
4242

4343
constructor(
4444
private collection: CollectionImpl<any, any, any, any, any>,
@@ -65,7 +65,7 @@ export class CollectionSubscription {
6565
: this.callback
6666
}
6767

68-
setOrderByIndex(index: BaseIndex<any>) {
68+
setOrderByIndex(index: IndexInterface<any>) {
6969
this.orderByIndex = index
7070
}
7171

‎packages/db/src/indexes/base-index.ts‎

Lines changed: 87 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -1,8 +1,9 @@
11
import { compileSingleRowExpression } from "../query/compiler/evaluators.js"
22
import { comparisonFunctions } from "../query/builder/functions.js"
33
import { DEFAULT_COMPARE_OPTIONS, deepEquals } from "../utils.js"
4+
import type { RangeQueryOptions } from "./btree-index.js"
45
import type { CompareOptions } from "../query/builder/types.js"
5-
import type { BasicExpression } from "../query/ir.js"
6+
import type { BasicExpression, OrderByDirection } from "../query/ir.js"
67

78
/**
89
* Operations that indexes can support, imported from available comparison functions
@@ -24,12 +25,57 @@ export interface IndexStats {
2425
readonly lastUpdated: Date
2526
}
2627

28+
export interface IndexInterface<
29+
TKey extends string | number = string | number,
30+
> {
31+
add: (key: TKey, item: any) => void
32+
remove: (key: TKey, item: any) => void
33+
update: (key: TKey, oldItem: any, newItem: any) => void
34+
35+
build: (entries: Iterable<[TKey, any]>) => void
36+
clear: () => void
37+
38+
lookup: (operation: IndexOperation, value: any) => Set<TKey>
39+
40+
equalityLookup: (value: any) => Set<TKey>
41+
inArrayLookup: (values: Array<any>) => Set<TKey>
42+
43+
rangeQuery: (options: RangeQueryOptions) => Set<TKey>
44+
rangeQueryReversed: (options: RangeQueryOptions) => Set<TKey>
45+
46+
take: (
47+
n: number,
48+
from?: TKey,
49+
filterFn?: (key: TKey) => boolean
50+
) => Array<TKey>
51+
takeReversed: (
52+
n: number,
53+
from?: TKey,
54+
filterFn?: (key: TKey) => boolean
55+
) => Array<TKey>
56+
57+
get keyCount(): number
58+
get orderedEntriesArray(): Array<[any, Set<TKey>]>
59+
get orderedEntriesArrayReversed(): Array<[any, Set<TKey>]>
60+
61+
get indexedKeysSet(): Set<TKey>
62+
get valueMapData(): Map<any, Set<TKey>>
63+
64+
supports: (operation: IndexOperation) => boolean
65+
66+
matchesField: (fieldPath: Array<string>) => boolean
67+
matchesCompareOptions: (compareOptions: CompareOptions) => boolean
68+
matchesDirection: (direction: OrderByDirection) => boolean
69+
70+
getStats: () => IndexStats
71+
}
72+
2773
/**
2874
* Base abstract class that all index types extend
2975
*/
30-
export abstract class BaseIndex<
31-
TKey extends string | number = string | number,
32-
> {
76+
export abstract class BaseIndex<TKey extends string | number = string | number>
77+
implements IndexInterface<TKey>
78+
{
3379
public readonly id: number
3480
public readonly name?: string
3581
public readonly expression: BasicExpression
@@ -65,7 +111,20 @@ export abstract class BaseIndex<
65111
from?: TKey,
66112
filterFn?: (key: TKey) => boolean
67113
): Array<TKey>
114+
abstract takeReversed(
115+
n: number,
116+
from?: TKey,
117+
filterFn?: (key: TKey) => boolean
118+
): Array<TKey>
68119
abstract get keyCount(): number
120+
abstract equalityLookup(value: any): Set<TKey>
121+
abstract inArrayLookup(values: Array<any>): Set<TKey>
122+
abstract rangeQuery(options: RangeQueryOptions): Set<TKey>
123+
abstract rangeQueryReversed(options: RangeQueryOptions): Set<TKey>
124+
abstract get orderedEntriesArray(): Array<[any, Set<TKey>]>
125+
abstract get orderedEntriesArrayReversed(): Array<[any, Set<TKey>]>
126+
abstract get indexedKeysSet(): Set<TKey>
127+
abstract get valueMapData(): Map<any, Set<TKey>>
69128

70129
// Common methods
71130
supports(operation: IndexOperation): boolean {
@@ -80,8 +139,31 @@ export abstract class BaseIndex<
80139
)
81140
}
82141

142+
/**
143+
* Checks if the compare options match the index's compare options.
144+
* The direction is ignored because the index can be reversed if the direction is different.
145+
*/
83146
matchesCompareOptions(compareOptions: CompareOptions): boolean {
84-
return deepEquals(this.compareOptions, compareOptions)
147+
const thisCompareOptionsWithoutDirection = {
148+
...this.compareOptions,
149+
direction: undefined,
150+
}
151+
const compareOptionsWithoutDirection = {
152+
...compareOptions,
153+
direction: undefined,
154+
}
155+
156+
return deepEquals(
157+
thisCompareOptionsWithoutDirection,
158+
compareOptionsWithoutDirection
159+
)
160+
}
161+
162+
/**
163+
* Checks if the index matches the provided direction.
164+
*/
165+
matchesDirection(direction: OrderByDirection): boolean {
166+
return this.compareOptions.direction === direction
85167
}
86168

87169
getStats(): IndexStats {

‎packages/db/src/indexes/btree-index.ts‎

Lines changed: 50 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -245,15 +245,26 @@ export class BTreeIndex<
245245
}
246246

247247
/**
248-
* Returns the next n items after the provided item or the first n items if no from item is provided.
249-
* @param n - The number of items to return
250-
* @param from - The item to start from (exclusive). Starts from the smallest item (inclusive) if not provided.
251-
* @returns The next n items after the provided key. Returns the first n items if no from item is provided.
248+
* Performs a reversed range query
252249
*/
253-
take(n: number, from?: any, filterFn?: (key: TKey) => boolean): Array<TKey> {
250+
rangeQueryReversed(options: RangeQueryOptions = {}): Set<TKey> {
251+
const { from, to, fromInclusive = true, toInclusive = true } = options
252+
return this.rangeQuery({
253+
from: to ?? this.orderedEntries.maxKey(),
254+
to: from ?? this.orderedEntries.minKey(),
255+
fromInclusive: toInclusive,
256+
toInclusive: fromInclusive,
257+
})
258+
}
259+
260+
private takeInternal(
261+
n: number,
262+
nextPair: (k?: any) => [any, any] | undefined,
263+
from?: any,
264+
filterFn?: (key: TKey) => boolean
265+
): Array<TKey> {
254266
const keysInResult: Set<TKey> = new Set()
255267
const result: Array<TKey> = []
256-
const nextPair = (k?: any) => this.orderedEntries.nextHigherPair(k)
257268
let pair: [any, any] | undefined
258269
let key = normalizeValue(from)
259270

@@ -275,6 +286,32 @@ export class BTreeIndex<
275286
return result
276287
}
277288

289+
/**
290+
* Returns the next n items after the provided item or the first n items if no from item is provided.
291+
* @param n - The number of items to return
292+
* @param from - The item to start from (exclusive). Starts from the smallest item (inclusive) if not provided.
293+
* @returns The next n items after the provided key. Returns the first n items if no from item is provided.
294+
*/
295+
take(n: number, from?: any, filterFn?: (key: TKey) => boolean): Array<TKey> {
296+
const nextPair = (k?: any) => this.orderedEntries.nextHigherPair(k)
297+
return this.takeInternal(n, nextPair, from, filterFn)
298+
}
299+
300+
/**
301+
* Returns the next n items **before** the provided item (in descending order) or the last n items if no from item is provided.
302+
* @param n - The number of items to return
303+
* @param from - The item to start from (exclusive). Starts from the largest item (inclusive) if not provided.
304+
* @returns The next n items **before** the provided key. Returns the last n items if no from item is provided.
305+
*/
306+
takeReversed(
307+
n: number,
308+
from?: any,
309+
filterFn?: (key: TKey) => boolean
310+
): Array<TKey> {
311+
const nextPair = (k?: any) => this.orderedEntries.nextLowerPair(k)
312+
return this.takeInternal(n, nextPair, from, filterFn)
313+
}
314+
278315
/**
279316
* Performs an IN array lookup
280317
*/
@@ -303,6 +340,13 @@ export class BTreeIndex<
303340
.map((key) => [key, this.valueMap.get(key) ?? new Set()])
304341
}
305342

343+
get orderedEntriesArrayReversed(): Array<[any, Set<TKey>]> {
344+
return this.takeReversed(this.orderedEntries.size).map((key) => [
345+
key,
346+
this.valueMap.get(key) ?? new Set(),
347+
])
348+
}
349+
306350
get valueMapData(): Map<any, Set<TKey>> {
307351
return this.valueMap
308352
}

‎packages/db/src/indexes/reverse-index.ts‎

Lines changed: 120 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,120 @@
1+
import type { CompareOptions } from "../query/builder/types"
2+
import type { OrderByDirection } from "../query/ir"
3+
import type { IndexInterface, IndexOperation, IndexStats } from "./base-index"
4+
import type { RangeQueryOptions } from "./btree-index"
5+
6+
export class ReverseIndex<TKey extends string | number>
7+
implements IndexInterface<TKey>
8+
{
9+
private originalIndex: IndexInterface<TKey>
10+
11+
constructor(index: IndexInterface<TKey>) {
12+
this.originalIndex = index
13+
}
14+
15+
// Define the reversed operations
16+
17+
lookup(operation: IndexOperation, value: any): Set<TKey> {
18+
const reverseOperation =
19+
operation === `gt`
20+
? `lt`
21+
: operation === `gte`
22+
? `lte`
23+
: operation === `lt`
24+
? `gt`
25+
: operation === `lte`
26+
? `gte`
27+
: operation
28+
return this.originalIndex.lookup(reverseOperation, value)
29+
}
30+
31+
rangeQuery(options: RangeQueryOptions = {}): Set<TKey> {
32+
return this.originalIndex.rangeQueryReversed(options)
33+
}
34+
35+
rangeQueryReversed(options: RangeQueryOptions = {}): Set<TKey> {
36+
return this.originalIndex.rangeQuery(options)
37+
}
38+
39+
take(n: number, from?: any, filterFn?: (key: TKey) => boolean): Array<TKey> {
40+
return this.originalIndex.takeReversed(n, from, filterFn)
41+
}
42+
43+
takeReversed(
44+
n: number,
45+
from?: any,
46+
filterFn?: (key: TKey) => boolean
47+
): Array<TKey> {
48+
return this.originalIndex.take(n, from, filterFn)
49+
}
50+
51+
get orderedEntriesArray(): Array<[any, Set<TKey>]> {
52+
return this.originalIndex.orderedEntriesArrayReversed
53+
}
54+
55+
get orderedEntriesArrayReversed(): Array<[any, Set<TKey>]> {
56+
return this.originalIndex.orderedEntriesArray
57+
}
58+
59+
// All operations below delegate to the original index
60+
61+
supports(operation: IndexOperation): boolean {
62+
return this.originalIndex.supports(operation)
63+
}
64+
65+
matchesField(fieldPath: Array<string>): boolean {
66+
return this.originalIndex.matchesField(fieldPath)
67+
}
68+
69+
matchesCompareOptions(compareOptions: CompareOptions): boolean {
70+
return this.originalIndex.matchesCompareOptions(compareOptions)
71+
}
72+
73+
matchesDirection(direction: OrderByDirection): boolean {
74+
return this.originalIndex.matchesDirection(direction)
75+
}
76+
77+
getStats(): IndexStats {
78+
return this.originalIndex.getStats()
79+
}
80+
81+
add(key: TKey, item: any): void {
82+
this.originalIndex.add(key, item)
83+
}
84+
85+
remove(key: TKey, item: any): void {
86+
this.originalIndex.remove(key, item)
87+
}
88+
89+
update(key: TKey, oldItem: any, newItem: any): void {
90+
this.originalIndex.update(key, oldItem, newItem)
91+
}
92+
93+
build(entries: Iterable<[TKey, any]>): void {
94+
this.originalIndex.build(entries)
95+
}
96+
97+
clear(): void {
98+
this.originalIndex.clear()
99+
}
100+
101+
get keyCount(): number {
102+
return this.originalIndex.keyCount
103+
}
104+
105+
equalityLookup(value: any): Set<TKey> {
106+
return this.originalIndex.equalityLookup(value)
107+
}
108+
109+
inArrayLookup(values: Array<any>): Set<TKey> {
110+
return this.originalIndex.inArrayLookup(values)
111+
}
112+
113+
get indexedKeysSet(): Set<TKey> {
114+
return this.originalIndex.indexedKeysSet
115+
}
116+
117+
get valueMapData(): Map<any, Set<TKey>> {
118+
return this.originalIndex.valueMapData
119+
}
120+
}

‎packages/db/src/query/compiler/order-by.ts‎

Lines changed: 8 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -9,7 +9,7 @@ import type { CompiledSingleRowExpression } from "./evaluators.js"
99
import type { OrderByClause, QueryIR, Select } from "../ir.js"
1010
import type { NamespacedAndKeyedStream, NamespacedRow } from "../../types.js"
1111
import type { IStreamBuilder, KeyValue } from "@tanstack/db-ivm"
12-
import type { BaseIndex } from "../../indexes/base-index.js"
12+
import type { IndexInterface } from "../../indexes/base-index.js"
1313
import type { Collection } from "../../collection/index.js"
1414

1515
export type OrderByOptimizationInfo = {
@@ -20,7 +20,7 @@ export type OrderByOptimizationInfo = {
2020
b: Record<string, unknown> | null | undefined
2121
) => number
2222
valueExtractorForRawRow: (row: Record<string, unknown>) => any
23-
index: BaseIndex<string | number>
23+
index: IndexInterface<string | number>
2424
dataNeeded?: () => number
2525
}
2626

@@ -151,11 +151,12 @@ export function processOrderBy(
151151
return compare(extractedA, extractedB)
152152
}
153153

154-
const index: BaseIndex<string | number> | undefined = findIndexForField(
155-
followRefCollection.indexes,
156-
followRefResult.path,
157-
clause.compareOptions
158-
)
154+
const index: IndexInterface<string | number> | undefined =
155+
findIndexForField(
156+
followRefCollection.indexes,
157+
followRefResult.path,
158+
clause.compareOptions
159+
)
159160

160161
if (index && index.supports(`gt`)) {
161162
// We found an index that we can use to lazily load ordered data

0 commit comments

Comments
 (0)