Indexes: equality, spatial, full-text, vector

Indexes

A query walks the Document and tests every Element. That scan is the right default: it needs no setup, it sees the live Document, and for most reads it is fast enough. When one field is read over and over, an index trades a build step for a faster answer.

An index is a second structure laid beside the Document. Four kinds share one shape:

FieldIndex answers "which Elements equal this value".
SpatialIndex answers "which Elements are near this point".
TextIndex answers "which Elements contain these words".
VectorIndex answers "which Elements are closest to this vector".

They share a seam. You construct each one over a Document, query it faster than a scan, and rebuild it after an edit. Three rules follow from that seam.

Build once. Construction reads the whole Document in one pass and keeps the structure it needs. The cost is paid at build time, the queries are cheap.

Query a snapshot. An index borrows the Document's Elements and captures the field values at build time. It does not track later edits. This fits the model: a Document is a value you hold, and an index over an unchanging value stays correct as long as you hold it.

Rebuild after an edit. Change the Document and the index goes stale. Build a fresh one. An index is an opt-in accelerator, off the Document mutation path, so editing stays simple and the index stays a thing you reach for when a read is hot.

All four index types are available in both C++ and Python, with the same methods (Python uses snake_case names and reads back element Handles). Each example below shows both.

Queries borrow Elements from the Document. An index does too. Do not use an index past the lifetime of the Document it was built over, and do not edit that Document while you hold the index.

Equality: FieldIndex

FieldIndex indexes one field for equality. Where a query scans every Element to find a match, the index goes straight to the bucket. equals returns every Element whose field equals the value, in time proportional to the number of matches rather than the size of the Document.

#include "kinogaki/Query.h"

FieldIndex byStatus(doc, "status");

for (const Element* e : byStatus.equals(Value("open")))
    /* every issue whose status is "open" */;

bool anyDone = byStatus.contains(Value("done"));   // true if at least one match
std::size_t distinct = byStatus.keyCount();        // number of distinct status values

by_status = FieldIndex(doc, "status")

for e in by_status.equals("open"):
    pass   # every issue whose status is "open" (e is a Handle)

any_done = by_status.contains("done")    # True if at least one match
distinct = by_status.key_count           # number of distinct status values

Values match by query-layer equality. Numbers compare by widened value, so equals(Float(3)) finds an Element stored as the integer 3; strings compare as text. An Element missing the field, or holding a non-scalar there, is not indexed.

This is the indexed form of doc.query().where(field("status") == "open"). Reach for the index when that lookup runs many times over an unchanging Document. Reach for the query for a one-off read, or any read that filters on more than the one field.

Spatial: SpatialIndex

SpatialIndex is the metric sibling of FieldIndex. It indexes a point3f field and answers nearness: radius, k-nearest, and box. It buckets Elements into a uniform grid, so a query examines only the cells its ball or box touches, not every Element.

#include "kinogaki/Spatial.h"

SpatialIndex stars(doc, "position", /*cell*/ 10.0);

// every star within 10 units of the origin, nearest first
for (const Element* e : stars.within(Vec3{0, 0, 0}, 10.0))
    /* ... */;

std::size_t near = stars.countWithin(Vec3{0, 0, 0}, 10.0);

// the 5 nearest stars to a point, nearest first
auto closest = stars.nearest(Vec3{3, 0, 1}, 5);
const Element* one = stars.nearest(Vec3{3, 0, 1});   // the single nearest, or nullptr if empty

// every star inside an axis-aligned box
for (const Element* e : stars.inBox(Vec3{-5, -5, -5}, Vec3{5, 5, 5}))
    /* ... */;

stars = SpatialIndex(doc, "position", cell=10.0)

for e in stars.within((0, 0, 0), 10.0):  # nearest first
    pass

near = stars.count_within((0, 0, 0), 10.0)

closest = stars.nearest((3, 0, 1), 5)     # the 5 nearest, nearest first
one = stars.nearest_one((3, 0, 1))        # the single nearest, or None if empty

for e in stars.in_box((-5, -5, -5), (5, 5, 5)):
    pass

The cell size is the one tuning knob. Pick it near your typical query radius: a radius query examines about eight cells when the radius is no larger than a cell. Inserts are O(1), which suits data that grows in place, such as point clouds and scene graphs. See spatial concepts for the grid in depth.

Full text: TextIndex

TextIndex is an inverted index over a string field. It maps each token to the list of Elements that hold it, and ranks results by tf-idf, so a term that is rare across the corpus and frequent in an Element scores that Element high.

#include "kinogaki/Search.h"

TextIndex notes(doc, "body");

// Elements whose body contains "render", best first (case-insensitive)
for (const Element* e : notes.search("render"))
    /* ... */;

// Elements containing ALL of these terms, ranked by summed tf-idf
auto hits = notes.searchAll("render cache invalidation");

std::size_t vocab = notes.terms();      // distinct tokens indexed
std::size_t n     = notes.documents();  // Elements indexed

notes = TextIndex(doc, "body")

for e in notes.search("render"):          # best first, case-insensitive
    pass

hits = notes.search_all("render cache invalidation")   # AND over the terms

vocab = notes.terms          # distinct tokens indexed
n = notes.documents          # Elements indexed

search takes one term. searchAll splits a query on whitespace and returns the Elements that contain every term, an AND over the postings. Both return best-first.

Vector: VectorIndex

VectorIndex finds nearest neighbours over a float-array field, the kind of field an embedding lives in. Choose the metric at build time: Cosine, Dot, or L2.

#include "kinogaki/Search.h"

VectorIndex embeddings(doc, "embedding", VectorIndex::Metric::Cosine);

std::vector<float> query = /* an embedding of the search text */;
for (const Element* e : embeddings.nearest(query, 10))   // the 10 nearest, best first
    /* ... */;

std::size_t n   = embeddings.size();   // vectors indexed
std::size_t dim = embeddings.dim();    // their dimension

embeddings = VectorIndex(doc, "embedding", Metric.COSINE)

query = [...]   # an embedding of the search text
for e in embeddings.nearest(query, 10):   # the 10 nearest, best first
    pass

n = embeddings.size          # vectors indexed
dim = embeddings.dim         # their dimension

nearest is exact today. It compares the query against every indexed vector and returns the best k. That is brute force, correct and simple, and fast enough for thousands of vectors. The scaling upgrade is an HNSW navigable-graph backend, built on Core's graph primitive, behind the same nearest call.

Pick the index that matches the question: equal, near, contains, closest. For the scan they accelerate, see query; for storing a field as a contiguous column, see columnar. Build once, query fast, rebuild after an edit.

‹ Querying Columnar tables ›