dolt icon indicating copy to clipboard operation
dolt copied to clipboard

Add initial implementation of Proximity Map

Open nicktobey opened this issue 4 months ago • 7 comments

This adds a new message/node type: Vector Index, and a corresponding prolly-tree-based map structure: the Proximity Map

The Vector Index message currently has a subset of the Prolly Map message. A different message type was chosen to prevent them from being accidentally confused: while a Vector Index has the same fields as a Prolly Map, and has similar computed properties, their invariants and iteration order are completely different, and algorithms written for Prolly Map nodes should not accidentally operate on Vector Index nodes instead. Old versions of Dolt that do not support vector indexes should not attempt to manipulate Vector Index nodes as if they were Prolly Map nodes.

Proximity Maps resemble other Prolly Maps, but have the following invariants:

  • Each key must be convertible to a vector. Typically, the key is a val.Tuple, and the vector is the first value in that tuple.
  • The keys are arranged in the tree such that, for each of a key's parent keys (the keys that appear on the path from the root to the key), the key is closer to that parent key than any of the parent key's siblings.
  • The keys in a node are sorted...
  • ...except for the first key which matches its direct parent. (This may prove to be unnecessary and could potentially be relaxed.)

Notably, while the keys of an individual node are sorted, walking all of a vector indexes keys in standard iteration order will not be sorted.

This is a useful construct because it allows for efficient proximity-based lookup, which are instrumental for quickly running "approximate nearest neighbor" algorithms.

Currently, chunk boundaries are computed completely deterministically. No rolling hash or weibull distribution is used to control chunk sizes. This was chosen because it has the simplest guarentees about chunk boundaries, which makes it easier to reason about the cost of fixup operations, and makes cascading chunk boundary changes impossible: for example, a key that marks a chunk boundary on the first two levels will always mark a chunk boundary on the first two levels even if it gets moved when fixing up the tree.

This has its downsides: the chunk sizes follow a geometric distribution with no maximum or minimum size. This may change in the future, but is acceptable as a first pass.

nicktobey avatar Oct 01 '24 21:10 nicktobey