mirror of
https://github.com/featurebasedb/featurebase.git
synced 2026-08-28 10:54:59 +00:00
59d89dda99
This is a partial solution to a nasty performance problem, which is that a ContainerIterator has to *generate* all the containers. With roaring, this was cheap because they already exist in memory; with transactional backends, it's an allocation per container, *even for the containers we don't use*. This design admits filters which can distinguish between answers they can give just based on keys and times when they actually need containers instantiated, and can also give hints as to future answers -- saying "yes" or "no" to entire rows at a time, or indicating when they're done. This is only part of the solution; we also need a Tx API hook for doing scans like this which doesn't rely on ContainerIterator.
88 lines
2.2 KiB
Go
88 lines
2.2 KiB
Go
// Copyright 2020 Pilosa Corp.
|
|
//
|
|
// Licensed under the Apache License, Version 2.0 (the "License");
|
|
// you may not use this file except in compliance with the License.
|
|
// You may obtain a copy of the License at
|
|
//
|
|
// http://www.apache.org/licenses/LICENSE-2.0
|
|
//
|
|
// Unless required by applicable law or agreed to in writing, software
|
|
// distributed under the License is distributed on an "AS IS" BASIS,
|
|
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
|
|
// See the License for the specific language governing permissions and
|
|
// limitations under the License.
|
|
|
|
package roaring
|
|
|
|
import (
|
|
"fmt"
|
|
"math"
|
|
|
|
"github.com/pilosa/pilosa/v2/shardwidth"
|
|
)
|
|
|
|
func (b *Bitmap) String() (r string) {
|
|
r = "c("
|
|
slc := b.Slice()
|
|
width := 0
|
|
s := ""
|
|
for _, v := range slc {
|
|
if width == 0 {
|
|
s = fmt.Sprintf("%v", v)
|
|
} else {
|
|
s = fmt.Sprintf(", %v", v)
|
|
}
|
|
width += len(s)
|
|
r += s
|
|
if width > 70 {
|
|
r += ",\n"
|
|
width = 0
|
|
}
|
|
}
|
|
if width == 0 && len(r) > 2 {
|
|
r = r[:len(r)-2]
|
|
}
|
|
return r + ")"
|
|
}
|
|
|
|
// AsContainerMatrixString returns a string showing
|
|
// the matrix of rows in a shard, showing the count of hot (1) bits
|
|
// in each container.
|
|
func (b *Bitmap) AsContainerMatrixString() (r string) {
|
|
slc := b.Slice()
|
|
n := len(slc)
|
|
max := slc[n-1]
|
|
const rowWidthInContainerCount = 1 << (shardwidth.Exponent - 16) // - 16 because roaring.Container always holds 2^16 bits.
|
|
|
|
sw := uint64(1 << shardwidth.Exponent)
|
|
//fmt.Printf("sw = %v, shardwidth.Exponent = %v, rowWidthInContainerCount=%v\n", sw, shardwidth.Exponent, rowWidthInContainerCount)
|
|
maxrow := uint64(math.Ceil(float64(max) / float64(sw)))
|
|
if max == 0 {
|
|
maxrow++
|
|
}
|
|
matrix := make([][]uint64, maxrow)
|
|
for i := uint64(0); i < maxrow; i++ {
|
|
matrix[i] = make([]uint64, rowWidthInContainerCount)
|
|
}
|
|
iter, _ := b.Containers.Iterator(0)
|
|
for iter.Next() {
|
|
k, v := iter.Value()
|
|
j := k & keyMask
|
|
i := (k << 16) >> shardwidth.Exponent
|
|
matrix[i][j] = uint64(v.N())
|
|
}
|
|
r = "\n "
|
|
for j := 0; j < rowWidthInContainerCount; j++ {
|
|
r += fmt.Sprintf("%-5v ", j)
|
|
}
|
|
r += "\n"
|
|
for i, row := range matrix {
|
|
r += fmt.Sprintf("[row %05v] ", i)
|
|
for j, col := range row {
|
|
_ = j
|
|
r += fmt.Sprintf("%-5v ", col)
|
|
}
|
|
r += "\n"
|
|
}
|
|
return
|
|
}
|