indices

Documentation

Overview

Package indices contains index definitions for Limestone.

Limestone keeps entities in a memory database indexed for efficient access. An index can be based on one or more properties of an entity. To define an entity kind with indices, first make some index definitions:

var (
    IndexProjectID = limestone.FieldIndex("ProjectID")
    IndexProjectIDName = limestone.UniqueIndex(
        limestone.ConditionalIndexWhereFalse("Deleted",
            limestone.CompoundIndex(
                IndexProjectID,
                limestone.FieldIndex("Name", limestone.IgnoreCase),
            )
        )
    )
)

IndexProjectID defines a simple index on the ProjectID property.

IndexProjectIDName is a more complex example: it is a unique compound index on the (ProjectID, Name) pair, where name is sorted and matched case-insensitively, conditional on the Deleted property being false. Entites where Deleted is true are excluded from the index, cannot be found in it using snapshot.Search or enumerated with snapshot.All, and the uniqueness requirement imposed by limestone.UniqueIndex does not apply to them.

See the documentation for the individual *Index* functions in this package for what kinds of indices they can define.

When defining a kind, list the desired index definitions after the first argument to KindOf:

var KindCluster = limestone.KindOf(cluster{}, IndexProjectID, IndexProjectIDName)

Index definitions like IndexProjectID are immutable and can be shared among many kinds, given that they all contain the properties required by the index. This produces independent indices for each kind.

Each kind has an implicit unique index on the identity field. You don't have to define this index.

When querying a snapshot for entities, the Search method expects an index definition to choose the desired index. This is why they are assigned to variables in the snippet above.

iter := snapshot.Search(KindCluster, IndexProjectIDName, project.ID, name)

Every index expects a certain number of arguments of certain types passed to Search. For a compound index like IndexProjectIDName, they are the types of the participating properties. The types must match exactly. For example, if the ProjectID property is of a string-based project.ID type, the corresponding argument to Search must be of that type, and cannot be a plain string.

One can pass fewer arguments to Search than the index expects:

iter := snapshot.Search(KindCluster, IndexProjectIDName, project.ID)

This finds all clusters with the specified project ID where Deleted is false (because entities where Deleted is true are excluded from the index as specified by ConditionalIndexWhereFalse).

Finally, one can call Search with just two arguments to enumerate all indexed entities:

iter := snapshot.All(KindCluster, IndexProjectIDName)

(This iterator will still skip entities where Deleted is true.)

Search always enumerates entities in the order given by the index. For example, the last snippet above will enumerate them in ascending order of ProjectID, then among those with the same ProjectID, in ascending order of Name.

Indexable types

All integer types, strings, booleans, and all named types based on them are considered indexable. Fields of such types and pointers to those are supported by limestone.FieldIndex and expected by Search. These types are also the ones supported as return values of custom index functions passed to CustomIndex.

Any other type can be made indexable by implementing a method

IndexKey() ([]byte, bool)

The method should be a pure function that serializes the value as a byte sequence which later participates in lexicographical ordering. It may be concatenated with other such byte sequences if the index is compound.

The second return value should be true if the value is nonempty (this is taken into account by FieldIndex with the SkipZeros option).

Index

• Variables
• type Definition
  • func CompoundIndex(defs ...Definition) Definition
  • func CustomIndex(name string, fn any) Definition
  • func FieldIndex(name string, options ...fieldIndexOption) Definition
  • func IdentityIndex() Definition
  • func Index(def string) Definition
  • func IndexIf(desc string, filter any, def Definition) Definition
  • func IndexIfNonzero(fieldName string, def Definition) Definition
  • func IndexIfZero(fieldName string, def Definition) Definition
  • func UniqueIndex(def string) Definition
  • func UniquifyIndex(def Definition) Definition
• type IndexKey

Variables

var IgnoreCase ignoreCase

IgnoreCase is an option to FieldIndex that makes the index case-insensitive (per Unicode spec). The field must be a string, a named type based on a string, or a pointer to one of those. Values that only differ in case are considered equal by a case-insensitive index. In a UniqueIndex, they conflict. Lookup is case-insensitive.

var SkipZeros skipZeros

SkipZeros is an option to FieldIndex that makes the index exclude entities with zero values of the field. If the field is a pointer, zero values of the pointed-to type are excluded.

Types

type Definition

type Definition interface {
	Name() string                         // stable unique name
	Args() int                            // number of expected Search arguments
	Index(meta.Struct) *memdb.IndexSchema // create the indexer
}

Definition is a blueprint for creating a memdb indexer. This intermediate step is needed because such blueprints are created before the Kind they are intended for.

func CompoundIndex

func CompoundIndex(defs ...Definition) Definition

CompoundIndex specifies a compound index built from several simpler indices. Only produces values for entities for which all constituent indices produce values.

Example:

var indexFleetIDGroup = limestone.CompoundIndex(
    limestone.FieldIndex("FleetID"),
    limestone.FieldIndex("Group"),
)
var kindInstance = limestone.KindOf(instance{}, indexFleetIDGroup)

To find instances with the particular FleetID and Group:

iter := snapshot.Search(kindInstance, indexFleetIDGroup, fleet.ID, groupName)

To find instances with the particular FleetID, sorted by Group:

iter := snapshot.Search(kindInstance, indexFleetIDGroup, fleet.ID)

To enumerate all instances, sorted first by FleetID, then by Group:

iter := snapshot.Search(kindInstance, indexFleetIDGroup)

func CustomIndex

func CustomIndex(name string, fn any) Definition

CustomIndex specifies an index implemented by a custom function. The function takes the entity by value as its only argument, and returns zero or more typed values, plus a bool value (must be last). The bool value indicates whether or not the entity must be present in the index. It will be possible to search for the entities by passing values of the same types (except the last bool one) in the same order to snapshot.Search.

The name argument to CustomIndex is to identify this index uniquely. Give different names to indices using different functions.

Example:

// indexDeficit includes only clusters that are over budget,
// sorted by how much over budget they are.
var indexDeficit = CustomIndex("deficit",
    func(c cluster) (units.NanoUSDPerHour, bool) {
        if c.Budget == nil {
            return 0, false
        }
        // the difference will be negative, sorted in ascending order
        return c.Budget - c.SpendingRate, c.SpendingRate > c.Budget
    })
var kindCluster = KindOf(cluster{}, indexDeficit)

To enumerate all clusters that are over budget, from biggest deficit to smallest:

iter := snapshot.Search(kindCluster, indexDeficit)

To find the clusters with a particular deficit value:

iter := snapshot.Search(kindCluster, indexDeficit, units.NanoUSDPerHour(-1000))

func FieldIndex

func FieldIndex(name string, options ...fieldIndexOption) Definition

FieldIndex specifies an index on a single field. The field must be of an indexable type, or a pointer to such type. Possible options are SkipZeros and IgnoreCase.

func IdentityIndex

func IdentityIndex() Definition

IdentityIndex specifies a unique index on the identity field

func Index

func Index(def string) Definition

Index is a shorthand for specifying common kinds of indices. An index is described by a string containing space-separated words of two kinds:

Fields, in forms "Field" and "Field!".

Filters, in the forms "-Field" and "+Field".

Resulting index will contain all fields in order of their appearance in the description. For fields of form "Field!" only entities with non-zero values of this field will be included in the index.

A filter of form "-Field" causes all entities where the specified field has a nonzero value of its type to be excluded from the index. A filter of the form "+Field" has the reverse effect: it excludes those entities where the specified field has the zero value of its type. In particular, when the field is boolean, "-Field" means "only entities where Field is false", and "+Field" means "only entities where Field is true".

Fields and filters can be freely mixed in the description.

Examples:

Index("Test") => FieldIndex("Test") Index("Test1 Test2") => CompoundIndex(FieldIndex("Test1"), FieldIndex("Test2")) Index("Number! Price -Deleted") => IndexIfZero("Deleted", CompoundIndex(

FieldIndex("Number", SkipZeros), FieldIndex("Price")))

Index("Value! +Parent") => IndexIfNonzero("Parent",

FieldIndex("Value", SkipZeros))

func IndexIf

func IndexIf(desc string, filter any, def Definition) Definition

IndexIf filters another index on the condition given by a filtering function. The function must take the entity structure by value as its only argument, and return bool. Entities for which the function returns false are excluded from the index.

func IndexIfNonzero

func IndexIfNonzero(fieldName string, def Definition) Definition

IndexIfNonzero filters another index on the given field of the entity. Entities where the field has the zero value of its type are excluded from the index.

func IndexIfZero

func IndexIfZero(fieldName string, def Definition) Definition

IndexIfZero filters another index on the given field of the entity. Entities where the field has a nonzero value of its type are excluded from the index.

func UniqueIndex

func UniqueIndex(def string) Definition

UniqueIndex is the same as Index, but the produced index is unique.

func UniquifyIndex

func UniquifyIndex(def Definition) Definition

UniquifyIndex makes an index unique

type IndexKey

type IndexKey interface {
	IndexKey() ([]byte, bool)
}

IndexKey is an interface that can be implemented to make any type indexable