docfilter

Documentation

Overview

Package docfilter provides an exact, integer-PK doc_id membership filter used to prune the fulltext / IVF index scan to the candidate documents that pass a surrounding relational predicate.

For an integer PK it builds an exact bitset — a dense cbitmap for a bounded id range (cbitmap.go), else the compact C CRoaring bitset (croaring.go, via pkg cgo). Both are cheaper to build than a bloom filter (no hashing) and exact (no false positives, so no re-verification is needed). For non-integer PKs the caller falls back to a CBloomFilter. Build produces a tagged payload and New reconstructs the right structure from the tag; callers hold the result behind the MembershipFilter interface and never see the concrete structure.

WARNING — transport endianness: the cbitmap payload (TagCbitmap) is serialized in HOST byte order (a raw memcpy of [base][nbits][bitmap words]) for speed, so it is only valid when exchanged between MO nodes of the SAME endianness. The CRoaring (TagCRoaring) and CBloomFilter (TagBloom) payloads use portable serialization and are endianness-independent. All current MO targets are little-endian and a big-endian build fails to compile (see the static guard in cgo/cbitmap.c). Before deploying MO on a big-endian or mixed-endian cluster, switch cbitmap (de)serialization to an explicit little-endian format.

Index

• Constants
• Variables
• func Build(v *vector.Vector) ([]byte, error)
• func BuildCRoaringBytes(v *vector.Vector) ([]byte, error)
• func BuildCbitmapBytes(v *vector.Vector) (data []byte, ok bool, err error)
• func BuildIntegerFilter(v *vector.Vector) (byte, []byte, error)
• func CbitmapFeasible(maxVal uint64) bool
• func SupportsBitset(t types.Type) bool
• type CFilter
• type CRoaringFilter
  • func NewCRoaringFilter(data []byte) (*CRoaringFilter, error)
  • func (f *CRoaringFilter) CHandle() unsafe.Pointer
  • func (f *CRoaringFilter) CKind() byte
  • func (f *CRoaringFilter) Exact() bool
  • func (f *CRoaringFilter) Free()
  • func (f *CRoaringFilter) Share() MembershipFilter
  • func (f *CRoaringFilter) SharePointer() *CRoaringFilter
  • func (f *CRoaringFilter) Test(data []byte) bool
  • func (f *CRoaringFilter) TestVector(v *vector.Vector, cb func(bool, bool, int)) []uint8
  • func (f *CRoaringFilter) Valid() bool
• type CbitmapFilter
  • func NewCbitmapFilter(data []byte) (*CbitmapFilter, error)
  • func (f *CbitmapFilter) CHandle() unsafe.Pointer
  • func (f *CbitmapFilter) CKind() byte
  • func (f *CbitmapFilter) Exact() bool
  • func (f *CbitmapFilter) Free()
  • func (f *CbitmapFilter) Share() MembershipFilter
  • func (f *CbitmapFilter) SharePointer() *CbitmapFilter
  • func (f *CbitmapFilter) Test(data []byte) bool
  • func (f *CbitmapFilter) TestVector(v *vector.Vector, cb func(bool, bool, int)) []uint8
  • func (f *CbitmapFilter) Valid() bool
• type MembershipFilter
  • func New(data []byte) (MembershipFilter, error)

Constants

const MaxCbitmapBits = uint64(1) << 23

MaxCbitmapBits caps the dense bitset size. A dense bitmap is indexed by the doc_id value, so its size is O(max value), not O(count) — only viable when the max id is bounded. Above this the caller falls back to CRoaring.

2^23 bits = 1 MB, sized to stay within a typical per-core L2 cache so the random per-row membership probe hits L2 rather than L3/DRAM, and to bound per-query memory under concurrency (N concurrent queries * up to 1 MB). Covers dense integer PKs up to ~8.4M; sparser/larger id ranges fall back to the compact CRoaring bitset.

const TagBloom byte = 0

TagBloom marks a payload serialized by the CBloomFilter fallback (non-integer PKs). It shares the reader-side transport channel (defines.FulltextMembershipFilter -> FilterHint.MembershipFilterBytes) with TagCRoaring (croaring.go) and TagCbitmap (cbitmap.go); New dispatches on the tag.

const TagCRoaring byte = 2

TagCRoaring marks a payload serialized by the CRoaring (C, roaring64) filter, alongside docfilter.TagBitset (Go roaring) and TagBloom in the shared reader-side transport. CRoaring is the C-backed, compact, exact integer-PK filter (build/probe in C, one cgo call per vector).

const TagCbitmap byte = 3

TagCbitmap marks a payload serialized by the dense cbitmap filter, alongside TagBloom / TagBitset / TagCRoaring in the shared reader-side transport.

Variables

var CbitmapUseOffset = true

CbitmapUseOffset, when true, bases the dense bitset at min(values) so its size is the value SPAN (max-min) rather than the max value. This lets high-but- narrow id sets — recent rows of a large table, BETWEEN ranges, or signed/negative PKs (which zero-extend to huge uint64) — stay within MaxCbitmapBits instead of falling back to CRoaring. On by default: it strictly shrinks the bitset (size = span, never larger than the value-indexed layout) at no probe cost (BenchmarkTestVectorOffset: identical probe time), so a bounded-span set uses the fast dense path even when its absolute ids are large. The base is carried in the serialized payload, so the reader is agnostic to this flag (a payload built with it on is probed correctly either way).

Functions

func Build

func Build(v *vector.Vector) ([]byte, error)

Build serializes the best doc_id filter for the whole vector and returns the tagged bytes: an exact bitset (cbitmap for a bounded integer-id range, else CRoaring) for integer PKs, or a CBloomFilter for non-integer PKs. Build and probe read the column buffer directly in C (one cgo call). Callers just transport the bytes; New reconstructs the right filter from the tag.

func BuildCRoaringBytes

func BuildCRoaringBytes(v *vector.Vector) ([]byte, error)

BuildCRoaringBytes builds a roaring64 bitset from an integer doc_id vector (read directly in C) and returns its portable serialization (no tag prefix).

func BuildCbitmapBytes

func BuildCbitmapBytes(v *vector.Vector) (data []byte, ok bool, err error)

BuildCbitmapBytes builds a dense bitset from an integer doc_id vector (read directly in C) and returns its serialization (no tag). ok=false means the id range is too large for a dense bitmap (caller should use CRoaring instead).

func BuildIntegerFilter

func BuildIntegerFilter(v *vector.Vector) (byte, []byte, error)

BuildIntegerFilter builds the best exact filter for an integer doc_id vector and returns the tag byte to prepend + the serialized payload: a dense cbitmap when the id range is bounded (fastest), else a compact CRoaring bitset (sparse-safe). The reader picks the structure from the tag.

func CbitmapFeasible

func CbitmapFeasible(maxVal uint64) bool

CbitmapFeasible reports whether a max doc_id value is small enough that a dense cbitmap is worthwhile (vs the compact CRoaring filter). This is the value-indexed (offset-off) bound; with CbitmapUseOffset the actual build gates on the value SPAN (max-min), which is never larger.

func SupportsBitset

func SupportsBitset(t types.Type) bool

SupportsBitset reports whether a doc_id column type can be filtered with an exact integer bitset (cbitmap / CRoaring), i.e. it is a fixed-width integer type. Non-integer PKs (varchar/uuid/decimal/composite) use the CBloomFilter fallback.

Types

type CFilter

type CFilter interface {
	MembershipFilter
	// CHandle returns the underlying C handle (mo_cbitmap_t* / roaring64 /
	// bloomfilter_t*).
	CHandle() unsafe.Pointer
	// CKind reports the structure tag (TagBloom / TagCRoaring / TagCbitmap),
	// telling the bridge which C membership test to dispatch.
	CKind() byte
}

CFilter is the C-backed ADAPTER contract: a MembershipFilter that can also expose its underlying C handle + structure tag for the cgo vector-index filtered-search bridge (pkg/vectorindex/usearchex), whose C predicate tests each candidate key against the structure directly. The bridge type-asserts a MembershipFilter to CFilter, so general filters that cannot back a C search are not forced to expose unsafe.Pointer details.

type CRoaringFilter

type CRoaringFilter struct {
	// contains filtered or unexported fields
}

CRoaringFilter wraps a C roaring64_bitmap_t (via cgo/croaring) and implements engine.MembershipFilter. It uses CBloomFilter-style refcounting so the same C bitmap can be shared across parallel readers and freed exactly once.

func NewCRoaringFilter

func NewCRoaringFilter(data []byte) (*CRoaringFilter, error)

NewCRoaringFilter deserializes a portable roaring64 payload (no tag prefix).

func (*CRoaringFilter) CHandle

func (f *CRoaringFilter) CHandle() unsafe.Pointer

CHandle returns the underlying C roaring64 handle for the cgo search bridge.

func (*CRoaringFilter) CKind

func (f *CRoaringFilter) CKind() byte

CKind reports the roaring64 structure tag.

func (*CRoaringFilter) Exact

func (f *CRoaringFilter) Exact() bool

Exact is true: a roaring bitset is an exact membership test (no false positives).

func (*CRoaringFilter) Free

func (f *CRoaringFilter) Free()

Free drops one reference; the C bitmap is released when the last is freed.

func (*CRoaringFilter) Share

func (f *CRoaringFilter) Share() MembershipFilter

Share implements MembershipFilter (refcounted; returns the same C bitmap).

func (*CRoaringFilter) SharePointer

func (f *CRoaringFilter) SharePointer() *CRoaringFilter

SharePointer increments the refcount and returns the same filter, so each parallel reader holds a share and the C bitmap is freed exactly once.

func (*CRoaringFilter) Test

func (f *CRoaringFilter) Test(data []byte) bool

Test reports whether the raw fixed bytes of a single doc_id are present.

func (*CRoaringFilter) TestVector

func (f *CRoaringFilter) TestVector(v *vector.Vector, cb func(bool, bool, int)) []uint8

TestVector tests every row of an integer doc_id vector in one cgo call.

func (*CRoaringFilter) Valid

func (f *CRoaringFilter) Valid() bool

Valid reports whether the filter is usable.

type CbitmapFilter

type CbitmapFilter struct {
	// contains filtered or unexported fields
}

CbitmapFilter wraps a C dense bitset (cgo/cbitmap) and implements engine.MembershipFilter. Build and probe run entirely in C over the raw column buffer (one cgo call per vector), and it uses CRoaring-style refcounting so the same C bitset can be shared across parallel readers and freed once. It is the fastest exact filter for dense, bounded integer doc_ids.

func NewCbitmapFilter

func NewCbitmapFilter(data []byte) (*CbitmapFilter, error)

NewCbitmapFilter deserializes a dense bitset payload (no tag prefix).

func (*CbitmapFilter) CHandle

func (f *CbitmapFilter) CHandle() unsafe.Pointer

CHandle returns the underlying C dense-bitset handle for the cgo search bridge.

func (*CbitmapFilter) CKind

func (f *CbitmapFilter) CKind() byte

CKind reports the dense-bitset structure tag.

func (*CbitmapFilter) Exact

func (f *CbitmapFilter) Exact() bool

Exact is true: a dense bitset is an exact membership test (no false positives).

func (*CbitmapFilter) Free

func (f *CbitmapFilter) Free()

Free drops one reference; the C bitset is released when the last is freed.

func (*CbitmapFilter) Share

func (f *CbitmapFilter) Share() MembershipFilter

Share implements MembershipFilter (refcounted; returns the same C bitset).

func (*CbitmapFilter) SharePointer

func (f *CbitmapFilter) SharePointer() *CbitmapFilter

SharePointer increments the refcount and returns the same filter, so each parallel reader holds a share and the C bitset is freed exactly once.

func (*CbitmapFilter) Test

func (f *CbitmapFilter) Test(data []byte) bool

Test reports whether the raw fixed bytes of a single doc_id are present.

func (*CbitmapFilter) TestVector

func (f *CbitmapFilter) TestVector(v *vector.Vector, cb func(bool, bool, int)) []uint8

TestVector tests every row of an integer doc_id vector in one cgo call.

func (*CbitmapFilter) Valid

func (f *CbitmapFilter) Valid() bool

Valid reports whether the filter is usable.

type MembershipFilter

type MembershipFilter interface {
	// Test reports whether the raw fixed bytes of a single key may be present.
	Test(data []byte) bool
	// TestVector tests every row of a key vector, invoking cb(exist, isnull, row).
	TestVector(v *vector.Vector, cb func(bool, bool, int)) []uint8
	// Valid reports whether the filter is usable.
	Valid() bool
	// Exact reports whether membership is exact (a bitset, no false positives)
	// rather than approximate (a bloom filter).
	Exact() bool
	// Free releases resources / drops one share.
	Free()
	// Share returns a filter for one parallel reader (refcount or per-reader wrapper).
	Share() MembershipFilter
}

MembershipFilter is the primary-key membership PROBE contract (fulltext calls the PK doc_id). Its method set is the consumer interface engine.MembershipFilter (Test/TestVector/Valid/Exact/Free) plus Share — so a value can be stored directly in engine.FilterHint.BF without this package importing engine (a pkg/common -> pkg/vm/engine layering inversion). The consumer half is kept compatible with engine.MembershipFilter by a compile-time assertion in package disttae; that shared method set's single source of truth lives in engine.

This is intentionally free of any cgo/unsafe detail: a general (non-C-backed) filter implementation only needs to probe. The C-bridge methods live on the separate CFilter contract below, which the cgo search bridge type-asserts.

Callers obtain one via New (from tagged bytes produced by Build) and never need to know which concrete structure (cbitmap / CRoaring / bloom) backs it.

func New

func New(data []byte) (MembershipFilter, error)

New reconstructs a MembershipFilter from the tagged bytes produced by Build.