roaring

Documentation

Index

• Constants
• func ClearBits(foundSet, target *roaring.Bitmap)
• type BSI
  • func NewBSI(maxValue int64, minValue int64) *BSI
  • func NewDefaultBSI() *BSI
  • func (b *BSI) Add(other *BSI)
  • func (b *BSI) BatchEqual(parallelism int, values []int64) *roaring.Bitmap
  • func (b *BSI) BitCount() int
  • func (b *BSI) ClearValues(foundSet *roaring.Bitmap)
  • func (b *BSI) Clone() *BSI
  • func (b *BSI) CompareValue(parallelism int, op Operation, valueOrStart, end int64, ...) *roaring.Bitmap
  • func (b *BSI) GetCardinality() uint64
  • func (b *BSI) GetExistenceBitmap() *roaring.Bitmap
  • func (b *BSI) GetValue(columnID uint64) (int64, bool)
  • func (b *BSI) HasRunCompression() bool
  • func (b *BSI) Increment(foundSet *roaring.Bitmap)
  • func (b *BSI) IncrementAll()
  • func (b *BSI) IntersectAndTranspose(parallelism int, foundSet *roaring.Bitmap) *roaring.Bitmap
  • func (b *BSI) MarshalBinary() ([][]byte, error)
  • func (b *BSI) MinMax(parallelism int, op Operation, foundSet *roaring.Bitmap) int64
  • func (b *BSI) NewBSIRetainSet(foundSet *roaring.Bitmap) *BSI
  • func (b *BSI) ParOr(parallelism int, bsis ...*BSI)
  • func (b *BSI) RunOptimize()
  • func (b *BSI) SetValue(columnID uint64, value int64)
  • func (b *BSI) Sum(foundSet *roaring.Bitmap) (sum int64, count uint64)
  • func (b *BSI) Transpose() *roaring.Bitmap
  • func (b *BSI) TransposeWithCounts(parallelism int, foundSet *roaring.Bitmap) *BSI
  • func (b *BSI) UnmarshalBinary(bitData [][]byte) error
  • func (b *BSI) ValueExists(columnID uint64) bool
• type Operation

Constants

const (
	// Min64BitSigned - Minimum 64 bit value
	Min64BitSigned = -9223372036854775808
	// Max64BitSigned - Maximum 64 bit value
	Max64BitSigned = 9223372036854775807
)

Functions

func ClearBits

func ClearBits(foundSet, target *roaring.Bitmap)

ClearBits cleared the bits that exist in the target if they are also in the found set.

Types

type BSI

type BSI struct {
	MaxValue int64
	MinValue int64
	// contains filtered or unexported fields
}

BSI is at its simplest is an array of bitmaps that represent an encoded binary value. The advantage of a BSI is that comparisons can be made across ranges of values whereas a bitmap can only represent the existence of a single value for a given column ID. Another usage scenario involves storage of high cardinality values.

It depends upon the bitmap libraries. It is not thread safe, so upstream concurrency guards must be provided.

func NewBSI

func NewBSI(maxValue int64, minValue int64) *BSI

NewBSI constructs a new BSI. Note that it is your responsibility to ensure that the min/max values are set correctly. Queries CompareValue, MinMax, etc. will not work correctly if the min/max values are not set correctly.

func NewDefaultBSI

func NewDefaultBSI() *BSI

NewDefaultBSI constructs an auto-sized BSI

func (*BSI) Add

func (b *BSI) Add(other *BSI)

Add - In-place sum the contents of another BSI with this BSI, column wise.

func (*BSI) BatchEqual

func (b *BSI) BatchEqual(parallelism int, values []int64) *roaring.Bitmap

BatchEqual returns a bitmap containing the column IDs where the values are contained within the list of values provided.

func (*BSI) BitCount

func (b *BSI) BitCount() int

BitCount returns the number of bits needed to represent values.

func (*BSI) ClearValues

func (b *BSI) ClearValues(foundSet *roaring.Bitmap)

ClearValues removes the values found in foundSet

func (*BSI) Clone

func (b *BSI) Clone() *BSI

Clone performs a deep copy of BSI contents.

func (*BSI) CompareValue

func (b *BSI) CompareValue(parallelism int, op Operation, valueOrStart, end int64,
	foundSet *roaring.Bitmap) *roaring.Bitmap

CompareValue compares value. Values should be in the range of the BSI (max, min). If the value is outside the range, the result might erroneous. The operation parameter indicates the type of comparison to be made. For all operations with the exception of RANGE, the value to be compared is specified by valueOrStart. For the RANGE parameter the comparison criteria is >= valueOrStart and <= end. The parallelism parameter indicates the number of CPU threads to be applied for processing. A value of zero indicates that all available CPU resources will be potentially utilized.

func (*BSI) GetCardinality

func (b *BSI) GetCardinality() uint64

GetCardinality returns a count of unique column IDs for which a value has been set.

func (*BSI) GetExistenceBitmap

func (b *BSI) GetExistenceBitmap() *roaring.Bitmap

GetExistenceBitmap returns a pointer to the underlying existence bitmap of the BSI

func (*BSI) GetValue

func (b *BSI) GetValue(columnID uint64) (int64, bool)

GetValue gets the value at the column ID. Second param will be false for non-existent values.

func (*BSI) HasRunCompression

func (b *BSI) HasRunCompression() bool

HasRunCompression returns true if the bitmap benefits from run compression

func (*BSI) Increment

func (b *BSI) Increment(foundSet *roaring.Bitmap)

Increment - In-place increment of values in a BSI. Found set select columns for incrementing.

func (*BSI) IncrementAll

func (b *BSI) IncrementAll()

IncrementAll - In-place increment of all values in a BSI.

func (*BSI) IntersectAndTranspose

func (b *BSI) IntersectAndTranspose(parallelism int, foundSet *roaring.Bitmap) *roaring.Bitmap

IntersectAndTranspose is a matrix transpose function. Return a bitmap such that the values are represented as column IDs in the returned bitmap. This is accomplished by iterating over the foundSet and only including the column IDs in the source (foundSet) as compared with this BSI. This can be useful for vectoring one set of integers to another.

func (*BSI) MarshalBinary

func (b *BSI) MarshalBinary() ([][]byte, error)

MarshalBinary serializes a BSI

func (*BSI) MinMax

func (b *BSI) MinMax(parallelism int, op Operation, foundSet *roaring.Bitmap) int64

MinMax - Find minimum or maximum value.

func (*BSI) NewBSIRetainSet

func (b *BSI) NewBSIRetainSet(foundSet *roaring.Bitmap) *BSI

NewBSIRetainSet - Construct a new BSI from a clone of existing BSI, retain only values contained in foundSet

func (*BSI) ParOr

func (b *BSI) ParOr(parallelism int, bsis ...*BSI)

ParOr is intended primarily to be a concatenation function to be used during bulk load operations. Care should be taken to make sure that columnIDs do not overlap (unless overlapping values are identical).

func (*BSI) RunOptimize

func (b *BSI) RunOptimize()

RunOptimize attempts to further compress the runs of consecutive values found in the bitmap

func (*BSI) SetValue

func (b *BSI) SetValue(columnID uint64, value int64)

SetValue sets a value for a given columnID.

func (*BSI) Sum

func (b *BSI) Sum(foundSet *roaring.Bitmap) (sum int64, count uint64)

Sum all values contained within the foundSet. As a convenience, the cardinality of the foundSet is also returned (for calculating the average).

func (*BSI) Transpose

func (b *BSI) Transpose() *roaring.Bitmap

Transpose calls b.IntersectAndTranspose(0, b.eBM)

func (*BSI) TransposeWithCounts

func (b *BSI) TransposeWithCounts(parallelism int, foundSet *roaring.Bitmap) *BSI

TransposeWithCounts is a matrix transpose function that returns a BSI that has a columnID system defined by the values contained within the input BSI. Given that for BSIs, different columnIDs can have the same value. TransposeWithCounts is useful for situations where there is a one-to-many relationship between the vectored integer sets. The resulting BSI contains the number of times a particular value appeared in the input BSI as an integer count.

func (*BSI) UnmarshalBinary

func (b *BSI) UnmarshalBinary(bitData [][]byte) error

UnmarshalBinary de-serialize a BSI. The value at bitData[0] is the EBM. Other indices are in least to most significance order starting at bitData[1] (bit position 0).

func (*BSI) ValueExists

func (b *BSI) ValueExists(columnID uint64) bool

ValueExists tests whether the value exists.

type Operation

type Operation int

Operation identifier

const (
	// LT less than
	LT Operation = 1 + iota
	// LE less than or equal
	LE
	// EQ equal
	EQ
	// GE greater than or equal
	GE
	// GT greater than
	GT
	// RANGE range
	RANGE
	// MIN find minimum
	MIN
	// MAX find maximum
	MAX
)