overlap

type Checker ¶

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

Checker is used to check for data overlap between tables in the LSM and a user key region of interest.

func MakeChecker(cmp base.Compare, iteratorFactory IteratorFactory) Checker

func (c *Checker) EmptyRegion(
	ctx context.Context, region base.UserKeyBounds, m *manifest.TableMetadata,
) (bool, error)

func (c *Checker) LSMOverlap(
	ctx context.Context, region base.UserKeyBounds, v *manifest.Version,
) (WithLSM, error)

func (c *Checker) LevelOverlap(
	ctx context.Context, region base.UserKeyBounds, ls manifest.LevelSlice,
) (WithLevel, error)

type IteratorFactory ¶

type IteratorFactory interface {
	Points(ctx context.Context, m *manifest.TableMetadata) (base.InternalIterator, error)
	RangeDels(ctx context.Context, m *manifest.TableMetadata) (keyspan.FragmentIterator, error)
	RangeKeys(ctx context.Context, m *manifest.TableMetadata) (keyspan.FragmentIterator, error)
}

IteratorFactory is an interface that is used by the Checker to create iterators for a given table. All methods can return nil as an empty iterator.

type Kind ¶

type Kind uint8

Kind indicates the kind of overlap detected between a key range and a level. We check two types of overlap:

• file boundary overlap: whether the key range overlaps any of the level's user key boundaries;

• data overlap: whether the key range overlaps any keys or ranges in the level. Data overlap implies file boundary overlap.

const (
	// None indicates that the key range of interest doesn't overlap any tables on
	// the level.
	None Kind = iota + 1
	// OnlyBoundary indicates that there is boundary overlap but no data overlap.
	OnlyBoundary
	// Data indicates that at least a key or range in the level overlaps with the
	// key range of interest. Note that the data overlap check is best-effort and
	// there could be false positives.
	Data
)

type WithLSM ¶

type WithLSM [manifest.NumLevels]WithLevel

WithLSM stores the result of checking for boundary and data overlap between a region of key space and the LSM levels, starting from the top (L0) and stopping at the highest level with data overlap.

type WithLevel ¶

type WithLevel struct {
	Result Kind
	// SplitFile can be set only when result is OnlyBoundary. If it is set, this
	// file can be split to free up the range of interest.
	SplitFile *manifest.TableMetadata
}

WithLevel is the result of checking overlap against an LSM level.