Repository: maxnowack/signaldb
Pull request #384 (2023-11-28 12:55:22)

feat: allow creation of simple field indices for collections

codecov[bot]: ## [Codecov](https://app.codecov.io/gh/maxnowack/signaldb/pull/384?src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Max+Nowack) Report
Attention: `2 lines` in your changes are missing coverage. Please review.
> Comparison is base [(`97117ef`)](https://app.codecov.io/gh/maxnowack/signaldb/commit/97117ef561baac30070133699f496ba41bb4ad11?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Max+Nowack) 100.00% compared to head [(`c55e213`)](https://app.codecov.io/gh/maxnowack/signaldb/pull/384?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Max+Nowack) 99.59%.
> Report is 1 commits behind head on main.

| [Files](https://app.codecov.io/gh/maxnowack/signaldb/pull/384?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Max+Nowack) | Patch % | Lines |
|---|---|---|
| [src/Collection/createIndex.ts](https://app.codecov.io/gh/maxnowack/signaldb/pull/384?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Max+Nowack#diff-c3JjL0NvbGxlY3Rpb24vY3JlYXRlSW5kZXgudHM=) | 95.34% | [1 Missing and 1 partial :warning: ](https://app.codecov.io/gh/maxnowack/signaldb/pull/384?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Max+Nowack) |

<details><summary>Additional details and impacted files</summary>


```diff
@@             Coverage Diff             @@
##              main     #384      +/-   ##
===========================================
- Coverage   100.00%   99.59%   -0.41%     
===========================================
  Files           23       24       +1     
  Lines          473      489      +16     
  Branches       128      136       +8     
===========================================
+ Hits           473      487      +14     
- Misses           0        1       +1     
- Partials         0        1       +1     
```



</details>

[:umbrella: View full report in Codecov by Sentry](https://app.codecov.io/gh/maxnowack/signaldb/pull/384?src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Max+Nowack).   
:loudspeaker: Have feedback on the report? [Share it here](https://about.codecov.io/codecov-pr-comment-feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Max+Nowack).


Patch:
diff --git a/docs/collections/index.md b/docs/collections/index.md
index 95f607d..4a3b98d 100644
--- a/docs/collections/index.md
+++ b/docs/collections/index.md
@@ -79,7 +79,7 @@ Behaves the same like `.removeMany()` but only removes the first found document.
 ## IndexProvider
 
 An IndexProvider is an object that specifies how to create an index on a collection. It can be created with the `createIndexProvider()` function.
-Take a look at the [`createIdIndex`](https://github.com/maxnowack/signaldb/blob/main/src/Collection/createIdIndex.ts) function for an example.
+Take a look at the [`createIndex`](https://github.com/maxnowack/signaldb/blob/main/src/Collection/createIndex.ts) function for an example.
 
 ```js
 import { createIndexProvider } from 'signaldb'
@@ -94,3 +94,25 @@ const indexProvider = createIndexProvider({
   },
 })
 ```
+
+## createIndex
+
+The `createIndex()` function can be used to create a single field index on a collection. It takes a field name as a parameter and returns an IndexProvider object which can be passed directly to the `indices` option of the Collection constructor.
+
+```js
+
+import { createIndex, Collection } from 'signaldb'
+
+interface User {
+  id: string
+  name: string
+  age: number
+}
+
+const users = new Collection<User>({
+  indices: [
+    createIndex('name'),
+    createIndex('age'),
+  ],
+})
+```
diff --git a/src/Collection/createIdIndex.spec.ts b/src/Collection/createIdIndex.spec.ts
deleted file mode 100644
index d58f133..0000000
--- a/src/Collection/createIdIndex.spec.ts
+++ /dev/null
@@ -1,51 +0,0 @@
-import { describe, it, expect } from 'vitest'
-import { getMatchingIds } from './createIdIndex'
-
-describe('getMatchingIds', () => {
-  it('should return null if selector.id is a RegExp', () => {
-    const selector = { id: /test/ }
-    const result = getMatchingIds(selector)
-    expect(result).toBeNull()
-  })
-
-  it("should return an array with selector.id if it's not null and not a field expression", () => {
-    const selector = { id: 'test' }
-    const result = getMatchingIds(selector)
-    expect(result).toEqual(['test'])
-  })
-
-  it("should return an array with selector.id.$in if it's a field expression with $in", () => {
-    const selector = { id: { $in: ['test1', 'test2'] } }
-    const result = getMatchingIds(selector)
-    expect(result).toEqual(['test1', 'test2'])
-  })
-
-  it("should return an array with selector.id if it's a field expression without $in", () => {
-    const selector = { id: { $ne: 'test' } }
-    const result = getMatchingIds(selector)
-    expect(result).toBeNull()
-  })
-
-  it('should return null if selector.$and is an empty array', () => {
-    const selector = { $and: [] }
-    const result = getMatchingIds(selector)
-    expect(result).toBeNull()
-  })
-
-  it('should return the intersection of sub-arrays if selector.$and is an array of selectors', () => {
-    expect(getMatchingIds({
-      $and: [
-        { id: 'test1' },
-        { name: 'John' },
-      ],
-    })).toEqual(['test1'])
-
-    expect(getMatchingIds({
-      $and: [
-        { id: 'test1' },
-        { id: { $in: ['test1', 'test2'] } },
-        { id: { $ne: 'test2' } },
-      ],
-    })).toEqual(['test1'])
-  })
-})
diff --git a/src/Collection/createIdIndex.ts b/src/Collection/createIdIndex.ts
index ad30c4f..47b301e 100644
--- a/src/Collection/createIdIndex.ts
+++ b/src/Collection/createIdIndex.ts
@@ -1,51 +1,6 @@
-import createIndexProvider from '../createIndexProvider'
-import type Selector from '../types/Selector'
-import compact from '../utils/compact'
-import intersection from '../utils/intersection'
-import isFieldExpression from '../utils/isFieldExpression'
+import createIndex from './createIndex'
 import type { BaseItem } from './types'
 
-export function getMatchingIds<
-  T extends BaseItem<I> = BaseItem, I = any
->(selector: Selector<T>): I[] | null {
-  if (selector.id instanceof RegExp) return null
-  if (selector.id != null) {
-    if (isFieldExpression(selector.id)) {
-      const is$in = isFieldExpression(selector.id)
-        && Array.isArray(selector.id.$in)
-        && selector.id.$in.length
-      if (is$in) return selector.id.$in as I[]
-      return null
-    }
-    return [selector.id] as I[]
-  }
-
-  if (Array.isArray(selector.$and)) {
-    const subIdArrays = selector.$and.map(sel => getMatchingIds(sel))
-    const subIds = compact(subIdArrays)
-    if (subIds.length === 0) return null
-    return intersection(...subIds)
-  }
-
-  return null
-}
-
 export default function createIdIndex<T extends BaseItem<I> = BaseItem, I = any>() {
-  const index = new Map<I, number>()
-
-  return createIndexProvider<T, I>({
-    getItemPositions(selector) {
-      const matchingIds = getMatchingIds<T, I>(selector)
-      if (matchingIds == null) return null
-      const resolvedPositions = matchingIds.map(id => index.get(id))
-        .filter(pos => pos != null)
-      return resolvedPositions as number[]
-    },
-    rebuild(items) {
-      index.clear()
-      items.forEach((item, i) => {
-        index.set(item.id, i)
-      })
-    },
-  })
+  return createIndex<T, I>('id')
 }
diff --git a/src/Collection/createIndex.spec.ts b/src/Collection/createIndex.spec.ts
new file mode 100644
index 0000000..0ea1849
--- /dev/null
+++ b/src/Collection/createIndex.spec.ts
@@ -0,0 +1,107 @@
+import { describe, it, expect } from 'vitest'
+import { getMatchingKeys, serializeValue } from './createIndex'
+
+describe('serializeValue', () => {
+  it('should serialize a string value correctly', () => {
+    expect(serializeValue('hello')).toBe('hello')
+  })
+
+  it('should serialize a number value correctly', () => {
+    expect(serializeValue(42)).toBe('42')
+  })
+
+  it('should serialize a boolean value correctly', () => {
+    expect(serializeValue(true)).toBe('true')
+  })
+
+  it('should serialize a Date value correctly', () => {
+    expect(serializeValue(new Date('2022-01-01T00:00:00Z'))).toBe('2022-01-01T00:00:00.000Z')
+  })
+
+  it('should serialize an object value correctly', () => {
+    expect(serializeValue({ name: 'John', age: 30 })).toBe('{"name":"John","age":30}')
+  })
+})
+
+describe('getMatchingKeys', () => {
+  it('should return null if the selector field is an instance of RegExp', () => {
+    const field = 'name'
+    const selector = { name: /John/ }
+
+    const result = getMatchingKeys(field, selector)
+
+    expect(result).toBeNull()
+  })
+
+  it('should return null if the selector field is null or undefined', () => {
+    const field = 'name'
+    const selector1 = { name: null }
+    const selector2 = { name: undefined }
+
+    const result1 = getMatchingKeys(field, selector1)
+    const result2 = getMatchingKeys(field, selector2)
+
+    expect(result1).toBeNull()
+    expect(result2).toBeNull()
+  })
+
+  it('should return an array of matching keys if the selector field is a single value', () => {
+    const field = 'name'
+    const selector = { name: 'John' }
+
+    const result = getMatchingKeys(field, selector)
+
+    expect(result).toEqual(['John'])
+  })
+
+  it('should return an array of matching keys if the selector field is an $in expression', () => {
+    const field = 'name'
+    const selector = { name: { $in: ['John', 'Jane'] } }
+
+    const result = getMatchingKeys(field, selector)
+
+    expect(result).toEqual(['John', 'Jane'])
+  })
+
+  it('should return an array of matching keys if the selector field is nested within $and expression', () => {
+    const field = 'name'
+    const selector = {
+      $and: [
+        { name: 'John' },
+        { name: 'Jane' },
+      ],
+    }
+
+    const result = getMatchingKeys(field, selector)
+
+    expect(result).toEqual([])
+  })
+
+  it('should return an array of matching keys if the selector field is nested within $or expression', () => {
+    const field = 'name'
+    const selector = {
+      $or: [
+        { name: 'John' },
+        { name: 'Jane' },
+      ],
+    }
+
+    const result = getMatchingKeys(field, selector)
+
+    expect(result).toEqual(['John', 'Jane'])
+  })
+
+  it('should return matching keys in nested expressions', () => {
+    const field = 'name'
+    const selector = {
+      $and: [
+        { name: 'John' },
+        { age: 30 },
+      ],
+    }
+
+    const result = getMatchingKeys(field, selector)
+
+    expect(result).toEqual(['John'])
+  })
+})
diff --git a/src/Collection/createIndex.ts b/src/Collection/createIndex.ts
new file mode 100644
index 0000000..efeeae4
--- /dev/null
+++ b/src/Collection/createIndex.ts
@@ -0,0 +1,70 @@
+import createIndexProvider from '../createIndexProvider'
+import type Selector from '../types/Selector'
+import compact from '../utils/compact'
+import get from '../utils/get'
+import intersection from '../utils/intersection'
+import isFieldExpression from '../utils/isFieldExpression'
+import type { BaseItem } from './types'
+
+export function serializeValue(value: any) {
+  if (typeof value === 'string') return value
+  if (typeof value === 'number') return value.toString()
+  if (typeof value === 'boolean') return value.toString()
+  if (value instanceof Date) return value.toISOString()
+  return JSON.stringify(value)
+}
+
+export function getMatchingKeys<
+  T extends BaseItem<I> = BaseItem, I = any
+>(field: string, selector: Selector<T>): string[] | null {
+  if (selector[field] instanceof RegExp) return null
+  if (selector[field] != null) {
+    if (isFieldExpression(selector[field])) {
+      const is$in = isFieldExpression(selector[field])
+        && Array.isArray(selector[field].$in)
+        && selector[field].$in.length
+      if (is$in) return selector[field].$in as string[]
+      return null
+    }
+    return [serializeValue(selector[field])]
+  }
+
+  if (Array.isArray(selector.$and)) {
+    const subArrays = selector.$and.map(sel => getMatchingKeys(field, sel))
+    const subKeys = compact(subArrays)
+    if (subKeys.length === 0) return null
+    return intersection(...subKeys)
+  }
+
+  if (Array.isArray(selector.$or)) {
+    const subArrays = selector.$or.map(sel => getMatchingKeys(field, sel))
+    const subKeys = compact(subArrays)
+    if (subKeys.length === 0) return null
+    return subKeys.reduce<string[]>((memo, keys) => [...memo, ...keys], [])
+  }
+
+  return null
+}
+
+export default function createIndex<T extends BaseItem<I> = BaseItem, I = any>(field: string) {
+  const index = new Map<string, Set<number>>()
+
+  return createIndexProvider<T, I>({
+    getItemPositions(selector) {
+      const matchingKeys = getMatchingKeys<T, I>(field, selector)
+      if (matchingKeys == null) return null
+      const itemPositions = matchingKeys
+        .reduce<number[]>((memo, key) => [...memo, ...index.get(key) || []], [])
+      return itemPositions
+    },
+    rebuild(items) {
+      index.clear()
+      items.forEach((item, i) => {
+        const value = serializeValue(get(item, field))
+        const current = index.get(value) || new Set<number>()
+        current.add(i)
+        index.set(value, current)
+      })
+    },
+  })
+}
diff --git a/src/Collection/index.ts b/src/Collection/index.ts
index 105e9da..c9ed4e3 100644
--- a/src/Collection/index.ts
+++ b/src/Collection/index.ts
@@ -18,6 +18,7 @@ import type { BaseItem, FindOptions, Transform } from './types'
 export type { BaseItem, Transform, SortSpecifier, FieldSpecifier, FindOptions } from './types'
 export type { CursorOptions } from './Cursor'
 export type { ObserveCallbacks } from './Observer'
+export { default as createIndex } from './createIndex'
 
 export interface CollectionOptions<T extends BaseItem<I>, I, U = T> {
   memory?: MemoryAdapter,
diff --git a/src/index.ts b/src/index.ts
index dea187f..146db32 100644
--- a/src/index.ts
+++ b/src/index.ts
@@ -10,7 +10,7 @@ export type {
   FindOptions,
 } from './Collection'
 
-export { default as Collection } from './Collection'
+export { default as Collection, createIndex } from './Collection'
 export { default as PersistentCollection } from './PersistentCollection'
 export { default as createLocalStorageAdapter } from './persistence/createLocalStorageAdapter'
 export { default as createFilesystemAdapter } from './persistence/createFilesystemAdapter'


Test patch:
diff --git a/__tests__/Collection.spec.ts b/__tests__/Collection.spec.ts
index ebc76f6..135468a 100644
--- a/__tests__/Collection.spec.ts
+++ b/__tests__/Collection.spec.ts
@@ -1,5 +1,5 @@
 import { vi, beforeEach, describe, it, expect } from 'vitest'
-import { Collection, createMemoryAdapter } from '../src/index'
+import { Collection, createMemoryAdapter, createIndex } from '../src/index'
 
 describe('Collection', () => {
   let collection: Collection<{ id: string, name: string }>
@@ -316,6 +316,12 @@ describe('Collection', () => {
   })
 
   describe('performance', () => {
+    const measureTime = (fn: () => void) => {
+      const start = performance.now()
+      fn()
+      return performance.now() - start
+    }
+
     it('should be faster with id only queries', () => {
       const col = new Collection<{ id: string, name: string, num: number }>()
 
@@ -324,12 +330,6 @@ describe('Collection', () => {
         col.insert({ id: i.toString(), name: 'John', num: i })
       }
 
-      const measureTime = (fn: () => void) => {
-        const start = performance.now()
-        fn()
-        return performance.now() - start
-      }
-
       const idQueryTime = measureTime(() => {
         const item = col.findOne({ id: '999' })
         expect(item).toEqual({ id: '999', name: 'John', num: 999 })
@@ -340,10 +340,34 @@ describe('Collection', () => {
         expect(item).toEqual({ id: '999', name: 'John', num: 999 })
       })
 
-      expect(idQueryTime).toBeLessThan(nonIdQueryTime)
-
       // id query should use less than 10% of the time of a non-id query
-      expect((100 / nonIdQueryTime) * idQueryTime).toBeLessThan(10)
+      expect(Math.round((100 / nonIdQueryTime) * idQueryTime)).toBeLessThan(10)
+    })
+
+    it('should be faster with field indices', () => {
+      const col1 = new Collection<{ id: string, name: string, num: number }>({
+        indices: [createIndex('num')],
+      })
+      const col2 = new Collection<{ id: string, name: string, num: number }>()
+
+      // create items
+      for (let i = 0; i < 1000; i += 1) {
+        col1.insert({ id: i.toString(), name: 'John', num: i })
+        col2.insert({ id: i.toString(), name: 'John', num: i })
+      }
+
+      const indexQueryTime = measureTime(() => {
+        const item = col1.findOne({ num: 999 })
+        expect(item).toEqual({ id: '999', name: 'John', num: 999 })
+      })
+
+      const nonIndexQueryTime = measureTime(() => {
+        const item = col2.findOne({ num: 999 })
+        expect(item).toEqual({ id: '999', name: 'John', num: 999 })
+      })
+
+      // index query should use less than 10% of the time of a non-index query
+      expect(Math.round((100 / nonIndexQueryTime) * indexQueryTime)).toBeLessThan(10)
     })
   })
 })