Documentation
¶
Index ¶
- Constants
- func DecodeDocID(pos uint64) uint64
- func DecodeLeafIdx(pos uint64) uint16
- func DecodeRootIdx(pos uint64) uint16
- func Encode(rootIdx, leafIdx uint16, docID uint64) uint64
- func ExistsKey(path string) []byte
- func IdxKey(path string, index int) []byte
- func IdxKeyPrefix(path string) []byte
- func IdxKeyToBuf(path string, index int, buf []byte) []byte
- func OrDocID(positions []uint64, docID uint64) []uint64
- func PathPrefix(path string) []byte
- func ValueKey(path string, analyzedValue []byte) []byte
- type AssignResult
- type BitmapOps
- func (o *BitmapOps) AndAll(raws []*sroar.Bitmap, maxConcurrency int) (raw *sroar.Bitmap, release func())
- func (o *BitmapOps) AndAllMaskLeaf(raws []*sroar.Bitmap, maxConcurrency int) (rootDoc *sroar.Bitmap, release func())
- func (o *BitmapOps) AndNot(base, subtract *sroar.Bitmap, maxConcurrency int) (raw *sroar.Bitmap, release func())
- func (o *BitmapOps) CrossLeafCopresenceAll(raws []*sroar.Bitmap) (raw *sroar.Bitmap, release func())
- func (o *BitmapOps) IntersectsMaskedLeaf(rootDoc, raw *sroar.Bitmap) bool
- func (o *BitmapOps) MaskLeaf(raw *sroar.Bitmap) (rootDoc *sroar.Bitmap, release func())
- func (o *BitmapOps) MaskLeafAnd(rawA, rawB *sroar.Bitmap) (rootDoc *sroar.Bitmap, release func())
- func (o *BitmapOps) MaskRootLeaf(positions *sroar.Bitmap) (doc *sroar.Bitmap, release func())
- func (o *BitmapOps) NewEmpty(minCap int) (result *sroar.Bitmap, release func())
- func (o *BitmapOps) OrAll(raws []*sroar.Bitmap, maxConcurrency int) (raw *sroar.Bitmap, release func())
- type ExistsEntry
- type IdxEntry
- type PositionedValue
Constants ¶
const ( MaxRoots = 1 << rootBits // 16384 MaxLeavesPerRoot = 1 << leafBits // 16384 MaxDocID = (1 << docBits) - 1 // 68719476735; 68.7B )
Position encoding layout (64 bits total):
| root_idx (14 bits) | leaf_idx (14 bits) | docID (36 bits) | | bits 63-50 | bits 49-36 | bits 35-0 |
root_idx: 1-based index into top-level object array. Always 1 for standalone objects (treated as implicit 1-element array).
leaf_idx: 1-based counter assigned depth-first within a root element. Resets per root. Scalar array elements each get their own leaf_idx. Object elements with descendant leaves are intermediate (inherit descendants' positions); those without get their own leaf_idx.
docID: 36-bit internal document identifier.
const (
IdxKeySize = hashSize + 2 // hash12 + BE16(index)
)
Variables ¶
This section is empty.
Functions ¶
func DecodeDocID ¶
DecodeDocID extracts the document ID from an encoded position.
func DecodeLeafIdx ¶
DecodeLeafIdx extracts the leaf index from an encoded position.
func DecodeRootIdx ¶
DecodeRootIdx extracts the root index from an encoded position.
func Encode ¶
Encode packs root index, leaf index, and document ID into a single uint64 position value. Root and leaf indices are 1-based (0 is reserved/invalid). All three fields are masked to their declared widths (rootMask, leafMask, docMask) before packing, so out-of-range inputs are silently clipped.
func ExistsKey ¶
ExistsKey builds the key for an _exists metadata entry: hash12("_exists." + path) for named paths, or hash12("_exists") for root.
func IdxKey ¶
IdxKey builds the key for an _idx metadata entry: hash12("_idx." + path) + BE16(index) for named paths, or hash12("_idx") + BE16(index) for the root (path == ""). Mirrors ExistsKey's empty-path handling.
func IdxKeyPrefix ¶
IdxKeyPrefix returns the hash-only prefix used by IdxKey / IdxKeyToBuf for a path (no BE16 index suffix). Consumers building Seek-then-HasPrefix iterators must use this instead of PathPrefix("_idx."+path) so the empty-path handling stays aligned with the producer — otherwise a root-LCA iteration would compute hash("_idx.") while Seek lands on hash("_idx") and the first HasPrefix check would always fail.
func IdxKeyToBuf ¶
IdxKeyToBuf writes an _idx key into buf and returns the populated slice. buf must be at least IdxKeySize bytes. Use this in loops to avoid per-iteration allocation; declare a [IdxKeySize]byte on the stack and pass a slice of it.
func OrDocID ¶
OrDocID ORs a real docID into position templates that have docID=0. Returns a new slice; does not modify the input.
func PathPrefix ¶
PathPrefix returns the hashSize-byte hash prefix for a dot-notation property path. Used as keyPrefix on RowReaderRoaringSet when reading from a nested bucket.
Types ¶
type AssignResult ¶
type AssignResult struct {
Values []PositionedValue
Idx []IdxEntry
Exists []ExistsEntry
}
AssignResult holds all positioned values and metadata produced by walking a nested property value.
func AssignPositions ¶
func AssignPositions(prop *models.Property, value any) (*AssignResult, error)
AssignPositions walks a nested property value depth-first, assigns leaf positions according to the position assignment rules, and returns positioned values and metadata entries.
The property must be of type object or object[]. For object type, the value is wrapped in a 1-element array with root_idx=1.
All positions have docID=0; the caller ORs in the real docID during write.
type BitmapOps ¶
type BitmapOps struct {
// contains filtered or unexported fields
}
BitmapOps provides pool-backed versions of every bitmap merge operation used by the nested filter executor. Each method returns the result bitmap and a release function; callers must invoke release() when the bitmap is no longer needed so the underlying buffer is returned to the pool.
Using pool-backed allocations on the hot resolution path reduces GC pressure because intermediate bitmaps do not escape to the heap.
func NewBitmapOps ¶
func NewBitmapOps(pool roaringset.BitmapBufPool) *BitmapOps
NewBitmapOps constructs a BitmapOps that allocates result bitmaps from pool. Pass roaringset.NewBitmapBufPoolNoop() in tests or the real pool in production.
func (*BitmapOps) AndAll ¶
func (o *BitmapOps) AndAll(raws []*sroar.Bitmap, maxConcurrency int) (raw *sroar.Bitmap, release func())
AndAll returns the intersection of all raw position bitmaps in a pool buffer. Returns an empty (non-pooled) bitmap when raws is empty. The loop exits early when the running intersection becomes empty — further ANDs cannot change the result.
func (*BitmapOps) AndAllMaskLeaf ¶
func (o *BitmapOps) AndAllMaskLeaf(raws []*sroar.Bitmap, maxConcurrency int) (rootDoc *sroar.Bitmap, release func())
AndAllMaskLeaf zeroes the leaf bits of each raw bitmap, ANDs them all, and returns the rootDoc bitmap in a pool buffer. Returns an empty (non-pooled) bitmap when raws is empty. The loop exits early when the running intersection becomes empty — further ANDs cannot change the result.
func (*BitmapOps) AndNot ¶
func (o *BitmapOps) AndNot(base, subtract *sroar.Bitmap, maxConcurrency int) (raw *sroar.Bitmap, release func())
AndNot clones base into a pool buffer and subtracts subtract in place, returning the resulting bitmap and a release callback. Used to materialize the positive bitmap for NotEqual (universe AND-NOT denylist) without mutating the source universe bitmap.
func (*BitmapOps) CrossLeafCopresenceAll ¶
func (o *BitmapOps) CrossLeafCopresenceAll(raws []*sroar.Bitmap) (raw *sroar.Bitmap, release func())
CrossLeafCopresenceAll returns the union of values from all input bitmaps whose (root, docID) projection appears in every input — leaf differences across inputs are tolerated. Equivalent to sroar.CopresenceByMask with mask=zeroLeafBits. Result is allocated in a pool buffer sized to the largest input. Returns an empty (non-pooled) bitmap when raws is empty.
Use case: cross-disjoint-leaf AND under position-level evaluation. When operands sit at different leaves of the same element (sibling sub-arrays without a Phase 3 scalar bridge), raw AndAll gives ∅ even when the same physical element satisfies every operand. This op keeps the contributing leaf positions while filtering by (root, doc) co-presence, so the result composes raw with further within-root operations.
TODO aliszka:nested_filtering: revisit buffer sizing. max(LenInBytes) is usually adequate since the AND step at the heart of copresence can only shrink contributions, but heavy overlap with disjoint groupings could still grow the result above max. Sum of input sizes is the safe upper bound. Profile to pick the sweet spot.
func (*BitmapOps) IntersectsMaskedLeaf ¶
IntersectsMaskedLeaf reports whether rootDoc and raw share at least one position after zeroing raw's leaf bits. rootDoc must already be leaf-masked. No allocation is performed — use this for cheap element pre-checks before running the full per-element intersection.
func (*BitmapOps) MaskLeaf ¶
MaskLeaf zeroes the leaf bits of raw and returns the rootDoc bitmap in a pool buffer. The caller must invoke release() when the result is no longer needed.
func (*BitmapOps) MaskLeafAnd ¶
MaskLeafAnd intersects rawA and rawB on raw positions, zeroes the leaf bits of the result, and returns the rootDoc bitmap in a pool buffer. Equivalent to MaskLeaf(sroar.And(rawA, rawB)) but uses a single fused operation.
Both inputs must be raw position bitmaps (non-zero leaf bits).
func (*BitmapOps) MaskRootLeaf ¶
MaskRootLeaf zeroes both root and leaf bits of positions, returning only docIDs in a pool buffer. Use as the final step to extract plain document IDs. positions may be raw or rootDoc.
func (*BitmapOps) NewEmpty ¶
NewEmpty returns an empty bitmap backed by a pool buffer sized to minCap bytes. As values are added the bitmap may outgrow the initial buffer and allocate internally, but for typical use (result ⊆ some known upper bound) the hint avoids that reallocation.
func (*BitmapOps) OrAll ¶
func (o *BitmapOps) OrAll(raws []*sroar.Bitmap, maxConcurrency int) (raw *sroar.Bitmap, release func())
OrAll returns the union of all raw position bitmaps in a pool buffer. The largest input is cloned as the accumulator and the rest are folded in — avoiding one OrConc pass and starting from a pre-populated container structure (typically faster than growing an empty buffer through repeated ORs). Returns an empty (non-pooled) bitmap when raws is empty.
TODO aliszka:nested_filtering: revisit buffer sizing. Cloning the largest input still under-sizes the accumulator when the remaining inputs contain disjoint values — internal growth fires. Sum of input sizes is the safe upper bound but wastes pool capacity in the common overlapping case. Profile the nested-filter workload to pick the sweet spot.
TODO aliszka:nested_filtering: consider sorting the remaining inputs in descending order by LenInBytes before folding them in. OR is commutative so correctness is unaffected; the question is whether accumulator-growth cost dominates enough for sort order to matter. Profile before adding the sort cost.
type ExistsEntry ¶
type ExistsEntry struct {
Path string // property path; empty string for root-level exists
Positions []uint64 // positions with docID=0
}
ExistsEntry records which positions have a given property present. Used for IS NULL checks and ALL/NONE filter operators.
type IdxEntry ¶
type IdxEntry struct {
Path string // array path, e.g. "addresses" or "owner.nicknames"
Index int // 0-based element index
Positions []uint64 // positions with docID=0
}
IdxEntry records which positions belong to a specific array element. Used for same-element verification in cross-sibling filter correlation.
type PositionedValue ¶
type PositionedValue struct {
Path string // dot-notation path, e.g. "addresses.city"
PropName string // leaf property name, e.g. "city"
Value any // raw value (caller analyzes based on DataType)
DataType schema.DataType // scalar data type for value analysis
Tokenization string // tokenization strategy (for text types)
TextAnalyzer *models.TextAnalyzerConfig // custom text analyzer config (may be nil)
Positions []uint64 // encoded positions with docID=0
}
PositionedValue represents a leaf value discovered during position assignment. Positions have docID=0; the caller ORs in the real docID.
Source Files