index

package
v0.0.0-debug-20260702 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Jul 2, 2026 License: Apache-2.0 Imports: 21 Imported by: 0

Documentation

Index

Constants

View Source 
const (
	BF = iota
	PBF
	HBF
)
View Source 
const (
	PrefixFnID_Object uint8 = iota
	PrefixFnID_Block
)
View Source 
const FuseFilterErrorMsg = "too many iterations"
View Source 
const (
	ZMSize = 64
)

Variables

View Source 
var (
	ErrNotFound  = moerr.NewInternalErrorNoCtx("tae index: key not found")
	ErrDuplicate = moerr.NewInternalErrorNoCtx("tae index: key duplicate")
	ErrPrefix    = moerr.NewInternalErrorNoCtx("tae index: prefix filter error")
)
View Source 
var (
	ObjectPrefixFn = PrefixFn{Id: PrefixFnID_Object, Fn: func(b []byte) []byte { return b[:types.ObjectBytesSize] }}
	BlockPrefixFn  = PrefixFn{Id: PrefixFnID_Block, Fn: func(b []byte) []byte { return b[:types.BlockidSize] }}
)
View Source 
var MaxBytesValue []byte

Functions

func AnySegmentOverlaps 

func AnySegmentOverlaps(objZM ZM, segments [][]byte) bool

AnySegmentOverlaps reports whether any segment in the sorted, non-overlapping segment list overlaps with objZM.

Each segment is a 64-byte ZoneMap (same encoding as ZM) passed as a raw []byte slice. This avoids forcing the engine package to import the index package — callers store segments as [][]byte in engine.PKFilter and pass them here unchanged.

Segments must satisfy two invariants (guaranteed by the gap-based streaming construction algorithm):

  1. Sorted by min: segments[i].min ≤ segments[i+1].min
  2. Non-overlapping: segments[i].max < segments[i+1].min

Because of these invariants the max values are also monotonically increasing, so a single binary search on max suffices.

Overlap condition for two ranges [a_min, a_max] and [b_min, b_max]: 

a_max ≥ b_min  AND  a_min ≤ b_max

Complexity: O(log N) where N = len(segments).

Returns true when segments is empty (no filter ⇒ match everything).

func BatchUpdateZM added in v0.8.0 

func BatchUpdateZM(zm ZM, vec *vector.Vector) (err error)

func DecodeBloomFilter added in v0.8.0 

func DecodeBloomFilter(sf StaticFilter, buf []byte) error

func EncodeZM added in v0.8.0 

func EncodeZM(zm *ZM) []byte

func MustZMToVector added in v0.8.0 

func MustZMToVector(zm ZM, vec *vector.Vector, m *mpool.MPool) *vector.Vector

func NewSimpleARTMap 

func NewSimpleARTMap() *simpleARTMap

func SetZMSum added in v1.0.0 

func SetZMSum(zm ZM, vec *vector.Vector)

func StrictlyCompareZmMaxAndMin 

func StrictlyCompareZmMaxAndMin(maxBuf, minBuf []byte, t types.T, scale1, scale2 int32) int

StrictlyCompareZmMaxAndMin Consider this scenario:

  1. If not truncated, maxBuf is smaller than minBuf.
  2. If truncated, maxBuf is equal to or larger than minBuf.

For example: 

	maxBuf: 0xa 0xff 0xff 0xff 0xff 0xff 0xff 0xff 0xff ==> 0xb 0x00 0x00 0x00 0x00 0x00 0x00 0x00
	minBuf: 0xb
	maxBuf should be smaller than minBuf, but after truncating, maxBuf is bigger than minBuf.
	this is not accepted in overlap check.

	maxBuf: 0xa 0xff 0xff 0xff 0xff 0xff 0xff 0xff 0xff ==> 0xb 0x00 0x00 0x00 0x00 0x00 0x00 0x00
	minBuf: 0xb 0x00 0x00 0x00 0x00 0x00 0x00 0x00 0xff ==> 0xb 0x00 0x00 0x00 0x00 0x00 0x00 0x00
    maxBuf should be smaller than minBuf, but after truncating, maxBuf is equal to minBuf.

In this case, StrictlyCompareZmMaxAndMin will return -1 even when truncated, indicating a possibly false negative response to the declaration that two ZMs intersect

func UpdateZM added in v0.8.0 

func UpdateZM(zm ZM, v []byte)

func UpdateZMAny added in v0.8.0 

func UpdateZMAny(zm ZM, v any)

it is only used for test

func ZMToVector added in v0.8.0 

func ZMToVector(zm ZM, vec *vector.Vector, m *mpool.MPool) (*vector.Vector, error)

if zm is not initialized, return a const null vector if zm is of type varlen and truncated, the max value is null

Types

type BloomFilter 

type BloomFilter = bloomFilter

type HybridBloomFilter 

type HybridBloomFilter = hybridFilter

type Positions 

type Positions []uint32

type PrefixFn 

type PrefixFn struct {
	Id uint8
	Fn func([]byte) []byte
}

type SecondaryIndex 

type SecondaryIndex interface {
	Insert(key []byte, offset uint32) (err error)
	BatchInsert(keys *vector.Vector, offset, length int, startRow uint32) (err error)
	Delete(key any) (old uint32, err error)
	Search(key []byte) ([]uint32, error)
	String() string
	Size() int
}

type StaticFilter 

type StaticFilter interface {
	MayContainsKey(key []byte) (bool, error)
	MayContainsAnyKeys(keys containers.Vector) (bool, *nulls.Bitmap, error)
	MayContainsAny(keys *vector.Vector, lowerBound int, upperBound int) bool

	PrefixMayContainsKey(key []byte, prefixFnId uint8, level uint8) (bool, error)
	PrefixMayContainsAny(
		keys *vector.Vector, lowerBound int, upperBound int, prefixFnId uint8, level uint8,
	) bool

	Marshal() ([]byte, error)
	// MarshalWithBuffer marshals the filter into an existing, reusable buffer.
	// The caller must copy buf.Bytes() before the next Reset/reuse of buf.
	MarshalWithBuffer(buf *bytes.Buffer) error
	Unmarshal(buf []byte) error
	String() string
	PrefixFnId(level uint8) uint8
	GetType() uint8
	MaxLevel() uint8
}

func NewBloomFilter 

func NewBloomFilter(vec containers.Vector, buf *[]uint64, builder *xorfilter.BinaryFuseBuilder, alloc func(int) []byte) (StaticFilter, error)

NewBloomFilter builds a BinaryFuse8 bloom filter for a single vector. buf is an optional scratch buffer; pass &mySlice to reuse it across calls. builder is an optional BinaryFuseBuilder; pass &myBuilder to reuse internal buffers across filter builds.

func NewBloomFilter2 

func NewBloomFilter2(vectors []containers.Vector, buf *[]uint64, builder *xorfilter.BinaryFuseBuilder, alloc func(int) []byte) (StaticFilter, error)

NewBloomFilter2 builds a BinaryFuse8 bloom filter over multiple vectors. buf is an optional scratch buffer; pass &mySlice to reuse it across calls. builder is an optional BinaryFuseBuilder for reusing internal buffers.

func NewEmptyBloomFilter 

func NewEmptyBloomFilter() StaticFilter

func NewEmptyBloomFilterWithType 

func NewEmptyBloomFilterWithType(t uint8) StaticFilter

func NewHybridBloomFilter 

func NewHybridBloomFilter(
	data containers.Vector,
	level1PrefixFnId uint8,
	level1Prefix func([]byte) []byte,
	level2PrefixFnId uint8,
	level2Prefix func([]byte) []byte,
	buf *[]uint64,
	builder *xorfilter.BinaryFuseBuilder,
	alloc func(int) []byte,
) (StaticFilter, error)

NewHybridBloomFilter builds three BinaryFuse8 filters (full-key, level-1 prefix, level-2 prefix) in a single ForeachWindowBytes pass. buf is an optional scratch buffer; pass &mySlice to reuse it across calls. When provided, the buffer is grown to 3×n capacity and partitioned into three non-overlapping sub-slices — one allocation for all three hash arrays. builder is an optional BinaryFuseBuilder for reusing internal buffers.

func NewPrefixBloomFilter 

func NewPrefixBloomFilter(
	data containers.Vector,
	prefixFnId uint8,
	prefixFn func([]byte) []byte,
	buf *[]uint64,
	builder *xorfilter.BinaryFuseBuilder,
	alloc func(int) []byte,
) (StaticFilter, error)

NewPrefixBloomFilter builds a BinaryFuse8 bloom filter over prefix-transformed values. buf is an optional scratch buffer; pass &mySlice to reuse it across calls. builder is an optional BinaryFuseBuilder for reusing internal buffers.

type ZM added in v0.8.0 

type ZM []byte

func BuildZM added in v0.8.0 

func BuildZM(t types.T, v []byte) ZM

func DecodeZM added in v0.8.0 

func DecodeZM(buf []byte) ZM

func NewZM added in v0.8.0 

func NewZM(t types.T, scale int32) ZM

func SetBool added in v0.8.0 

func SetBool(zm ZM, v bool) ZM

func VectorToZM added in v0.8.0 

func VectorToZM(vec *vector.Vector, zm ZM) ZM

if zm is not of length 2, return not initilized zm

func ZMMinus added in v0.8.0 

func ZMMinus(v1, v2, res ZM) ZM

max = v1.max-v2.min min = v1.min-v2.max

func ZMMulti added in v0.8.0 

func ZMMulti(v1, v2, res ZM) ZM

v1 product v2 => p[r0,r1,r2,r3] min,max = Min(p),Max(p)

func ZMPlus added in v0.8.0 

func ZMPlus(v1, v2, res ZM) ZM

max = v1.max+v2.max min = v1.min+v2.min

func (ZM) And added in v0.8.0 

func (zm ZM) And(o ZM) (res bool, ok bool)

both zm should be of type bool, otherwise, ok is false res is true only when zm.min == true and o.min == true

func (ZM) AnyBetween added in v1.1.1 

func (zm ZM) AnyBetween(lb, ub ZM) (res bool, ok bool)

func (ZM) AnyGE added in v0.8.0 

func (zm ZM) AnyGE(o ZM) (res bool, ok bool)

func (ZM) AnyGEByValue added in v1.2.0 

func (zm ZM) AnyGEByValue(k []byte) bool

zm.max >= k

func (ZM) AnyGT added in v0.8.0 

func (zm ZM) AnyGT(o ZM) (res bool, ok bool)

func (ZM) AnyGTByValue added in v1.2.0 

func (zm ZM) AnyGTByValue(k []byte) bool

zm.max > k

func (ZM) AnyIn added in v0.8.0 

func (zm ZM) AnyIn(vec *vector.Vector) bool

func (ZM) AnyLE added in v0.8.0 

func (zm ZM) AnyLE(o ZM) (res bool, ok bool)

func (ZM) AnyLEByValue added in v1.2.0 

func (zm ZM) AnyLEByValue(k []byte) bool

zm.min <= k

func (ZM) AnyLT added in v0.8.0 

func (zm ZM) AnyLT(o ZM) (res bool, ok bool)

func (ZM) AnyLTByValue added in v1.2.0 

func (zm ZM) AnyLTByValue(k []byte) bool

zm.min < k

func (ZM) Between added in v1.2.0 

func (zm ZM) Between(lb, ub []byte) bool

func (ZM) Clone added in v0.8.0 

func (zm ZM) Clone() ZM

func (ZM) CompareMax added in v1.2.0 

func (zm ZM) CompareMax(o ZM) int

caller need to do compareCheck

func (ZM) CompareMin added in v1.2.0 

func (zm ZM) CompareMin(o ZM) int

func (ZM) Contains added in v0.8.0 

func (zm ZM) Contains(k any) bool

TODO: remove me later

func (ZM) ContainsKey added in v0.8.0 

func (zm ZM) ContainsKey(k []byte) bool

func (ZM) Encode added in v0.8.0 

func (zm ZM) Encode() []byte

func (ZM) FastContainsAny added in v0.8.0 

func (zm ZM) FastContainsAny(keys *vector.Vector) (ok bool)

func (ZM) FastIntersect added in v0.8.0 

func (zm ZM) FastIntersect(o ZM) (res bool)

func (ZM) FastLEValue 

func (zm ZM) FastLEValue(v []byte, scale int32) (res bool)

no init check no type check max <= v

func (ZM) GetBuf added in v0.8.0 

func (zm ZM) GetBuf() []byte

func (ZM) GetMax added in v0.8.0 

func (zm ZM) GetMax() any

func (ZM) GetMaxBuf added in v0.8.0 

func (zm ZM) GetMaxBuf() []byte

func (ZM) GetMin added in v0.8.0 

func (zm ZM) GetMin() any

func (ZM) GetMinBuf added in v0.8.0 

func (zm ZM) GetMinBuf() []byte

func (ZM) GetScale added in v0.8.0 

func (zm ZM) GetScale() int32

func (ZM) GetSum added in v1.0.0 

func (zm ZM) GetSum() any

func (ZM) GetSumBuf added in v1.0.0 

func (zm ZM) GetSumBuf() []byte

func (ZM) GetType added in v0.8.0 

func (zm ZM) GetType() types.T

func (ZM) HasSum added in v1.0.0 

func (zm ZM) HasSum() bool

func (ZM) InRange 

func (zm ZM) InRange(lb, ub []byte, hint uint8) bool

func (ZM) Intersect added in v0.8.0 

func (zm ZM) Intersect(o ZM) (res bool, ok bool)

func (ZM) IsArray added in v1.1.0 

func (zm ZM) IsArray() bool

func (ZM) IsInited added in v0.8.0 

func (zm ZM) IsInited() bool

func (ZM) IsString added in v0.8.0 

func (zm ZM) IsString() bool

func (ZM) Marshal added in v0.8.0 

func (zm ZM) Marshal() ([]byte, error)

func (ZM) MaxTruncated added in v0.8.0 

func (zm ZM) MaxTruncated() bool

func (ZM) Or added in v0.8.0 

func (zm ZM) Or(o ZM) (res bool, ok bool)

both zm should be of type bool, otherwise, ok is false res is false only when zm.max == false and o.max == false

func (ZM) PrefixBetween added in v1.1.1 

func (zm ZM) PrefixBetween(lb, ub []byte) bool

func (ZM) PrefixEq added in v1.1.0 

func (zm ZM) PrefixEq(s []byte) bool

func (ZM) PrefixGT 

func (zm ZM) PrefixGT(s []byte) bool

func (ZM) PrefixIn added in v1.1.0 

func (zm ZM) PrefixIn(vec *vector.Vector) bool

func (ZM) PrefixInRange 

func (zm ZM) PrefixInRange(lb, ub []byte, hint uint8) bool

func (ZM) Reset added in v0.8.0 

func (zm ZM) Reset()

func (ZM) ResetMinMax added in v0.8.0 

func (zm ZM) ResetMinMax()

func (ZM) RowidPrefixEq 

func (zm ZM) RowidPrefixEq(s []byte) bool

func (ZM) RowidPrefixGT 

func (zm ZM) RowidPrefixGT(s []byte) bool

func (ZM) SetMaxTruncated added in v1.2.0 

func (zm ZM) SetMaxTruncated()

func (ZM) SetScale added in v0.8.0 

func (zm ZM) SetScale(scale int32)

func (ZM) SetSum added in v1.0.0 

func (zm ZM) SetSum(v []byte)

func (ZM) SetType added in v0.8.0 

func (zm ZM) SetType(t types.T)

func (ZM) String added in v0.8.0 

func (zm ZM) String() string

func (ZM) StringForCompose added in v1.0.0 

func (zm ZM) StringForCompose() string

func (ZM) StringForHex added in v1.2.0 

func (zm ZM) StringForHex() string

func (ZM) SubVecIn added in v1.2.0 

func (zm ZM) SubVecIn(vec *vector.Vector) (int, int)

anyIn has been called, so there must be a subvector in this zonemap return lower bound and upper bound

func (ZM) Unmarshal added in v0.8.0 

func (zm ZM) Unmarshal(buf []byte) (err error)

func (ZM) Update added in v0.8.0 

func (zm ZM) Update(v any) (err error)

TODO: remove me later

func (ZM) Valid added in v0.8.0 

func (zm ZM) Valid() bool

Source Files

View all Source files

Directories

Path Synopsis

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.