Repository: cockroachdb/pebble
Pull request #3819 (2024-08-01 16:13:01)

colblk: add data block builder, iterator
Introduce facilities for reading and writing data blocks using user-specified columns for user keys. The full data block schema is not yet complete (eg, the 'is obsolete' bit, etc has not yet been integrated).

cockroach-teamcity: 

<!-- Reviewable:start -->
This change is [<img src="https://reviewable.io/review_button.svg" height="34" align="absmiddle" alt="Reviewable"/>](https://reviewable.io/reviews/cockroachdb/pebble/3819)
<!-- Reviewable:end -->


Patch:
diff --git a/sstable/colblk/block.go b/sstable/colblk/block.go
index 9ae95c53..4fa056d7 100644
--- a/sstable/colblk/block.go
+++ b/sstable/colblk/block.go
@@ -321,6 +321,11 @@ func (r *BlockReader) Init(data []byte, customHeaderSize uint32) {
 	}
 }
 
+// Rows returns the number of rows in the block, as indicated by the block header.
+func (r *BlockReader) Rows() int {
+	return int(r.header.Rows)
+}
+
 // DataType returns the data type of the col'th column. Every column's data type
 // is encoded within the block header.
 func (r *BlockReader) DataType(col int) DataType {
@@ -413,21 +418,14 @@ func (r *BlockReader) headerToBinFormatter(f *binfmt.Formatter) {
 	}
 }
 
-func (r *BlockReader) columnToBinFormatter(f *binfmt.Formatter, col, rows int) {
+func (r *BlockReader) formatColumn(
+	f *binfmt.Formatter, col int, fn func(*binfmt.Formatter, DataType),
+) {
 	f.CommentLine("data for column %d", col)
 	dataType := r.DataType(col)
 	colSize := r.pageStart(col+1) - r.pageStart(col)
 	endOff := f.Offset() + int(colSize)
-	switch dataType {
-	case DataTypeBool:
-		bitmapToBinFormatter(f, rows)
-	case DataTypeUint8, DataTypeUint16, DataTypeUint32, DataTypeUint64:
-		uintsToBinFormatter(f, rows, dataType, nil)
-	case DataTypeBytes:
-		rawBytesToBinFormatter(f, rows, nil)
-	default:
-		panic("unimplemented")
-	}
+	fn(f, dataType)
 
 	// We expect formatting the column data to have consumed all the bytes
 	// between the column's pageOffset and the next column's pageOffset.
@@ -439,3 +437,21 @@ func (r *BlockReader) columnToBinFormatter(f *binfmt.Formatter, col, rows int) {
 		panic(fmt.Sprintf("expected f.Offset() = %d, but found %d; did column %s format too many bytes?", endOff, f.Offset(), dataType))
 	}
 }
+
+func (r *BlockReader) columnToBinFormatter(f *binfmt.Formatter, col, rows int) {
+	r.formatColumn(f, col, func(f *binfmt.Formatter, dataType DataType) {
+		switch dataType {
+		case DataTypeBool:
+			bitmapToBinFormatter(f, rows)
+		case DataTypeUint8, DataTypeUint16, DataTypeUint32, DataTypeUint64:
+			uintsToBinFormatter(f, rows, dataType, nil)
+		case DataTypePrefixBytes:
+			prefixBytesToBinFormatter(f, rows, nil)
+		case DataTypeBytes:
+			rawBytesToBinFormatter(f, rows, nil)
+		default:
+			panic("unimplemented")
+		}
+	})
+
+}
diff --git a/sstable/colblk/data_block.go b/sstable/colblk/data_block.go
new file mode 100644
index 00000000..882fcb7a
--- /dev/null
+++ b/sstable/colblk/data_block.go
@@ -0,0 +1,756 @@
+// Copyright 2024 The LevelDB-Go and Pebble Authors. All rights reserved. Use
+// of this source code is governed by a BSD-style license that can be found in
+// the LICENSE file.
+
+package colblk
+
+import (
+	"bytes"
+	"cmp"
+	"context"
+	"encoding/binary"
+	"fmt"
+	"io"
+	"math"
+	"sync"
+	"unsafe"
+
+	"github.com/cockroachdb/errors"
+	"github.com/cockroachdb/pebble/internal/base"
+	"github.com/cockroachdb/pebble/internal/binfmt"
+	"github.com/cockroachdb/pebble/internal/invariants"
+	"github.com/cockroachdb/pebble/internal/treeprinter"
+	"github.com/cockroachdb/pebble/sstable/block"
+)
+
+// KeySchema defines the schema of a user key, as defined by the user's
+// application.
+//
+// TODO(jackson): Consider making this KVSchema. It feels like there's an
+// opportunity to generalize the ShortAttribute so that when a value is stored
+// out-of-band, the DataBlockWriter calls user-provided code to store the short
+// attributes inlined within the data block. For inlined-values, the
+// user-defined value columns would be implicitly null.
+type KeySchema struct {
+	ColumnTypes  []DataType
+	NewKeyWriter func() KeyWriter
+	NewKeySeeker func() KeySeeker
+}
+
+// A KeyWriter maintains ColumnWriters for a data block for writing user keys
+// into the database-specific key schema. Users may define their own key schema
+// and implement KeyWriter to encode keys into custom columns that are aware of
+// the structure of user keys.
+type KeyWriter interface {
+	ColumnWriter
+	// ComparePrev compares the provided user to the previously-written user
+	// key. The returned KeyComparison's UserKeyComparison field is equivalent
+	// to Compare(key, prevKey) where prevKey is the last key passed to
+	// WriteKey.
+	ComparePrev(key []byte) KeyComparison
+	// WriteKey writes a user key into the KeyWriter's columns. The
+	// keyPrefixLenSharedWithPrev parameter takes the number of bytes prefixing
+	// the key's logical prefix (as defined by (base.Comparer).Split) that the
+	// previously-written key's prefix shares.
+	//
+	// WriteKey is guaranteed to be called sequentially with increasing row
+	// indexes, beginning at zero.
+	WriteKey(row int, key []byte, keyPrefixLen, keyPrefixLenSharedWithPrev int32)
+}
+
+// KeyComparison holds information about a key and its comparison to another a
+// key.
+type KeyComparison struct {
+	// PrefixLen is the length of the prefix of the key. It's the outcome of
+	// calling base.Split on the key.
+	PrefixLen int32
+	// CommonPrefixLen is the length of the physical (byte-wise) prefix of the
+	// logical prefix that is shared with the other key. For example, for
+	// "apple@1" and "applied@3" the value is 4 (the length of "appl"). For
+	// "apple@1" and "apple@10" the value is 5 (the length of "apple"), because
+	// the shared bytes within the suffix are not included.
+	CommonPrefixLen int32
+	// UserKeyComparison is the comparison of the user keys of the two keys.
+	// Should be equivalent to
+	//
+	//   Compare(key, otherKey)
+	UserKeyComparison int32
+}
+
+// PrefixEqual returns true if the key comparison determined that the keys have
+// equal prefixes.
+func (kcmp KeyComparison) PrefixEqual() bool { return kcmp.PrefixLen == kcmp.CommonPrefixLen }
+
+// KeySeeker iterates over the keys in a columnar data block.
+//
+// Users of Pebble who define their own key schema must implement KeySeeker to
+// seek over their decomposed keys.
+//
+// KeySeeker implementations must be safe for concurrent use by multiple
+// goroutines. In practice, multiple DataBlockIterators may use the same
+// KeySeeker.
+type KeySeeker interface {
+	// Init initializes the iterator to read from the provided DataBlockReader.
+	Init(b *DataBlockReader) error
+	// SeekGE returns the index of the first row with a key greater than or
+	// equal to [key].
+	//
+	// If the caller externally knows a bound on where the key is located, it
+	// may indicate it through [boundRow] and [searchDir]. A [searchDir] value
+	// of -1 indicates that the sought row must be at an index ≤ [boundRow]. A
+	// [searchDir] value of +1 indicates that the sought row must be at an index
+	// ≥ [boundRow]. Implementations may use this information to constrain the
+	// search. See (base.SeekGEFlags).TrySeekUsingNext for context on when this
+	// may be set in practice.
+	SeekGE(key []byte, boundRow int, searchDir int8) (row int)
+	// MaterializeUserKey materializes the user key of the specified row,
+	// returning a slice of the materialized user key.  The caller may use the
+	// provided keyIter and its buffer to avoid allocations and reduce work. The
+	// prevRow parameter is the row MaterializeUserKey was last invoked with.
+	// Implementations may take advantage of that knowledge to reduce work.
+	MaterializeUserKey(keyIter *PrefixBytesIter, prevRow, row int) []byte
+	// Release releases the KeySeeker. It's called when the seeker is no longer
+	// in use. Implementations may pool KeySeeker objects.
+	Release()
+}
+
+const (
+	defaultKeySchemaColumnPrefix int = iota
+	defaultKeySchemaColumnSuffix
+)
+
+var defaultSchemaColumnTypes = []DataType{
+	defaultKeySchemaColumnPrefix: DataTypePrefixBytes,
+	defaultKeySchemaColumnSuffix: DataTypeBytes,
+}
+
+var defaultKeySeekerPool = sync.Pool{
+	New: func() interface{} {
+		return &defaultKeySeeker{}
+	},
+}
+
+// DefaultKeySchema returns the default key schema that decomposes a user key
+// into its prefix and suffix. Prefixes are sorted in lexicographical order.
+func DefaultKeySchema(comparer *base.Comparer, prefixBundleSize int) KeySchema {
+	return KeySchema{
+		ColumnTypes: defaultSchemaColumnTypes,
+		NewKeyWriter: func() KeyWriter {
+			kw := &defaultKeyWriter{comparer: comparer}
+			kw.prefixes.Init(prefixBundleSize)
+			kw.suffixes.Init()
+			return kw
+		},
+		NewKeySeeker: func() KeySeeker {
+			ks := defaultKeySeekerPool.Get().(*defaultKeySeeker)
+			ks.comparer = comparer
+			return ks
+		},
+	}
+}
+
+// Assert that *defaultKeyWriter implements the KeyWriter interface.
+var _ KeyWriter = (*defaultKeyWriter)(nil)
+
+type defaultKeyWriter struct {
+	comparer *base.Comparer
+	prefixes PrefixBytesBuilder
+	suffixes RawBytesBuilder
+}
+
+func (w *defaultKeyWriter) ComparePrev(key []byte) KeyComparison {
+	lp := w.prefixes.LastKey()
+
+	var cmpv KeyComparison
+	cmpv.PrefixLen = int32(w.comparer.Split(key))
+	cmpv.CommonPrefixLen = int32(bytesSharedPrefix(lp, key[:cmpv.PrefixLen]))
+	if len(lp) == 0 {
+		// The first key has no previous key to compare to.
+		return cmpv
+	}
+
+	if invariants.Enabled && bytes.Compare(lp, key[:cmpv.PrefixLen]) > 0 {
+		panic(errors.AssertionFailedf("keys are not in order: %q > %q", lp, key[:cmpv.PrefixLen]))
+	}
+	// Keys are written in order and prefixes must be sorted lexicograpgically,
+	// so CommonPrefixLen == PrefixLen implies that the keys share the same
+	// logical prefix. (If the previous key had a prefix longer than
+	// CommonPrefixLen, it would sort after [key].)
+	if cmpv.CommonPrefixLen == cmpv.PrefixLen {
+		// The keys share the same MVCC prefix. Compare the suffixes.
+		cmpv.UserKeyComparison = int32(w.comparer.CompareSuffixes(key[cmpv.PrefixLen:], w.suffixes.LastSlice()))
+		if invariants.Enabled {
+			if !w.comparer.Equal(lp, key[:cmpv.PrefixLen]) {
+				panic(errors.AssertionFailedf("keys have different logical prefixes: %q != %q", lp, key[:cmpv.PrefixLen]))
+			}
+		}
+		return cmpv
+	}
+
+	// The keys have different MVCC prefixes. We haven't determined which is
+	// greater, but we know the index at which they diverge. The base.Comparer
+	// contract dictates that prefixes must be lexicographically ordered.
+	if len(lp) == int(cmpv.CommonPrefixLen) {
+		// cmpv.PrefixLen > cmpv.PrefixLenShared; key is greater.
+		cmpv.UserKeyComparison = +1
+	} else {
+		// Both keys have at least 1 additional byte at which they diverge.
+		// Compare the diverging byte.
+		cmpv.UserKeyComparison = int32(cmp.Compare(key[cmpv.CommonPrefixLen], lp[cmpv.CommonPrefixLen]))
+	}
+	if invariants.Enabled {
+		// In this case we've determined that the keys have different prefixes,
+		// so the UserKeyComparison should be equal to the result of comparing
+		// the prefixes and nonzero.
+		if cmpv.UserKeyComparison == 0 {
+			panic(errors.AssertionFailedf("user keys should not be equal: %q+%q, %q", lp, w.suffixes.LastSlice(), key))
+		}
+		if v := w.comparer.Compare(key, lp); v != int(cmpv.UserKeyComparison) {
+			panic(errors.AssertionFailedf("user key comparison mismatch: Compare(%q, %q) = %d ≠ %d",
+				key, lp, v, cmpv.UserKeyComparison))
+		}
+	}
+	return cmpv
+}
+
+func (w *defaultKeyWriter) WriteKey(
+	row int, key []byte, keyPrefixLen, keyPrefixLenSharedWithPrev int32,
+) {
+	w.prefixes.Put(key[:keyPrefixLen], int(keyPrefixLenSharedWithPrev))
+	w.suffixes.Put(key[keyPrefixLen:])
+}
+
+func (w *defaultKeyWriter) NumColumns() int {
+	return 2
+}
+
+func (w *defaultKeyWriter) DataType(col int) DataType {
+	return defaultSchemaColumnTypes[col]
+}
+
+func (w *defaultKeyWriter) Reset() {
+	w.prefixes.Reset()
+	w.suffixes.Reset()
+}
+
+func (w *defaultKeyWriter) WriteDebug(dst io.Writer, rows int) {
+	fmt.Fprint(dst, "0: prefixes:       ")
+	w.prefixes.WriteDebug(dst, rows)
+	fmt.Fprintln(dst)
+	fmt.Fprint(dst, "1: suffixes:       ")
+	w.suffixes.WriteDebug(dst, rows)
+	fmt.Fprintln(dst)
+}
+
+func (w *defaultKeyWriter) Size(rows int, offset uint32) uint32 {
+	offset = w.prefixes.Size(rows, offset)
+	offset = w.suffixes.Size(rows, offset)
+	return offset
+}
+
+func (w *defaultKeyWriter) Finish(col, rows int, offset uint32, buf []byte) (nextOffset uint32) {
+	switch col {
+	case defaultKeySchemaColumnPrefix:
+		return w.prefixes.Finish(0, rows, offset, buf)
+	case defaultKeySchemaColumnSuffix:
+		return w.suffixes.Finish(0, rows, offset, buf)
+	default:
+		panic(fmt.Sprintf("unknown default key column: %d", col))
+	}
+}
+
+// Assert that *defaultKeySeeker implements KeySeeker.
+var _ KeySeeker = (*defaultKeySeeker)(nil)
+
+type defaultKeySeeker struct {
+	comparer     *base.Comparer
+	reader       *DataBlockReader
+	prefixes     PrefixBytes
+	suffixes     RawBytes
+	sharedPrefix []byte
+}
+
+func (ks *defaultKeySeeker) Init(r *DataBlockReader) error {
+	ks.reader = r
+	ks.prefixes = r.r.PrefixBytes(defaultKeySchemaColumnPrefix)
+	ks.suffixes = r.r.RawBytes(defaultKeySchemaColumnSuffix)
+	ks.sharedPrefix = ks.prefixes.SharedPrefix()
+	return nil
+}
+
+func (ks *defaultKeySeeker) SeekGE(key []byte, currRow int, dir int8) (row int) {
+	si := ks.comparer.Split(key)
+	row, eq := ks.prefixes.Search(key[:si])
+	if eq {
+		return ks.seekGEOnSuffix(row, key[si:])
+	}
+	return row
+}
+
+// seekGEOnSuffix is a helper function for SeekGE when a seek key's prefix
+// exactly matches a row. seekGEOnSuffix finds the first row at index or later
+// with the same prefix as index and a suffix greater than or equal to [suffix],
+// or if no such row exists, the next row with a different prefix.
+func (ks *defaultKeySeeker) seekGEOnSuffix(index int, suffix []byte) (row int) {
+	// The search key's prefix exactly matches the prefix of the row at index.
+	// If the row at index has a suffix >= [suffix], then return the row.
+	if ks.comparer.CompareSuffixes(ks.suffixes.At(index), suffix) >= 0 {
+		return index
+	}
+	// Otherwise, the row at [index] sorts before the search key and we need to
+	// search forward. Binary search between [index+1, prefixChanged.Successor(index+1)].
+	//
+	// Define f(l-1) == false and f(u) == true.
+	// Invariant: f(l-1) == false, f(u) == true.
+	l := index + 1
+	u := ks.reader.prefixChanged.Successor(index + 1)
+	for l < u {
+		h := int(uint(l+u) >> 1) // avoid overflow when computing h
+		// l ≤ h < u
+		if ks.comparer.CompareSuffixes(ks.suffixes.At(h), suffix) >= 0 {
+			u = h // preserves f(u) == true
+		} else {
+			l = h + 1 // preserves f(l-1) == false
+		}
+	}
+	return l
+}
+
+func (ks *defaultKeySeeker) MaterializeUserKey(keyIter *PrefixBytesIter, prevRow, row int) []byte {
+	if row == prevRow+1 && prevRow >= 0 {
+		ks.prefixes.SetNext(keyIter)
+	} else {
+		ks.prefixes.SetAt(keyIter, row)
+	}
+	suffix := ks.suffixes.At(row)
+	memmove(unsafe.Pointer(uintptr(keyIter.ptr)+uintptr(keyIter.len)), unsafe.Pointer(unsafe.SliceData(suffix)), uintptr(len(suffix)))
+	return unsafe.Slice((*byte)(keyIter.ptr), keyIter.len+len(suffix))
+}
+
+func (ks *defaultKeySeeker) Release() {
+	*ks = defaultKeySeeker{}
+	defaultKeySeekerPool.Put(ks)
+}
+
+// DataBlockWriter writes columnar data blocks, encoding keys using a
+// user-defined schema.
+type DataBlockWriter struct {
+	Schema    KeySchema
+	KeyWriter KeyWriter
+	// trailers is the column writer for InternalKey uint64 trailers.
+	trailers UintBuilder[uint64]
+	// prefixSame is the column writer for the prefix-changed bitmap that
+	// indicates when a new key prefix begins. During block building, the bitmap
+	// represents when the prefix stays the same, which is expected to be a
+	// rarer case. Before Finish-ing the column, we invert the bitmap.
+	prefixSame BitmapBuilder
+	// values is the column writer for values. Iff the isValueExternal bitmap
+	// indicates a value is external, the value is prefixed with a ValuePrefix
+	// byte.
+	values RawBytesBuilder
+	// isValueExternal is the column writer for the is-value-external bitmap
+	// that indicates when a value is stored out-of-band in a value block.
+	isValueExternal BitmapBuilder
+
+	enc              blockEncoder
+	rows             int
+	maximumKeyLength int
+	valuePrefixTmp   [1]byte
+}
+
+// TODO(jackson): Add an isObsolete bitmap column.
+
+const (
+	dataBlockColumnTrailer = iota
+	dataBlockColumnPrefixChanged
+	dataBlockColumnValue
+	dataBlockColumnIsValueExternal
+	dataBlockColumnMax
+)
+
+// The data block header is a 4-byte uint32 encoding the maximum length of a key
+// contained within the block. This is used by iterators to avoid the need to
+// grow key buffers while iterating over the block, ensuring that the key buffer
+// is always sufficiently large.
+const dataBlockCustomHeaderSize = 4
+
+// Init initializes the data block writer.
+func (w *DataBlockWriter) Init(schema KeySchema) {
+	w.Schema = schema
+	w.KeyWriter = schema.NewKeyWriter()
+	w.trailers.Init()
+	w.prefixSame.Reset()
+	w.values.Init()
+	w.isValueExternal.Reset()
+	w.rows = 0
+	w.maximumKeyLength = 0
+}
+
+// Reset resets the data block writer to its initial state, retaining buffers.
+func (w *DataBlockWriter) Reset() {
+	w.KeyWriter.Reset()
+	w.trailers.Reset()
+	w.prefixSame.Reset()
+	w.values.Reset()
+	w.isValueExternal.Reset()
+	w.rows = 0
+	w.maximumKeyLength = 0
+	w.enc.reset()
+}
+
+// String outputs a human-readable summary of internal DataBlockWriter state.
+func (w *DataBlockWriter) String() string {
+	var buf bytes.Buffer
+	size := uint32(w.Size())
+	fmt.Fprintf(&buf, "size=%d:\n", size)
+	w.KeyWriter.WriteDebug(&buf, w.rows)
+
+	fmt.Fprintf(&buf, "%d: trailers:       ", len(w.Schema.ColumnTypes)+dataBlockColumnTrailer)
+	w.trailers.WriteDebug(&buf, w.rows)
+	fmt.Fprintln(&buf)
+
+	fmt.Fprintf(&buf, "%d: prefix changed: ", len(w.Schema.ColumnTypes)+dataBlockColumnPrefixChanged)
+	w.prefixSame.WriteDebug(&buf, w.rows)
+	fmt.Fprintln(&buf)
+
+	fmt.Fprintf(&buf, "%d: values:         ", len(w.Schema.ColumnTypes)+dataBlockColumnValue)
+	w.values.WriteDebug(&buf, w.rows)
+	fmt.Fprintln(&buf)
+
+	fmt.Fprintf(&buf, "%d: is-value-ext:   ", len(w.Schema.ColumnTypes)+dataBlockColumnIsValueExternal)
+	w.isValueExternal.WriteDebug(&buf, w.rows)
+	fmt.Fprintln(&buf)
+
+	return buf.String()
+}
+
+// Add adds the provided key to the data block. Keys must be added in order. The
+// caller must supply a KeyComparison containing the comparison of the key to
+// the previously-added key, obtainable through
+//
+//	KeyWriter.ComparePrev(ikey.UserKey)
+//
+// The caller is required to pass this in because in expected use cases, the
+// caller will also require the same information.
+func (w *DataBlockWriter) Add(
+	ikey base.InternalKey, value []byte, valuePrefix block.ValuePrefix, kcmp KeyComparison,
+) {
+	w.KeyWriter.WriteKey(w.rows, ikey.UserKey, kcmp.PrefixLen, kcmp.CommonPrefixLen)
+	if kcmp.PrefixEqual() {
+		w.prefixSame.Set(w.rows, true)
+	}
+	w.trailers.Set(w.rows, uint64(ikey.Trailer))
+	if valuePrefix.IsValueHandle() {
+		w.isValueExternal.Set(w.rows, true)
+		// Write the value with the value prefix byte preceding the value.
+		w.valuePrefixTmp[0] = byte(valuePrefix)
+		w.values.PutConcat(w.valuePrefixTmp[:], value)
+	} else {
+		// Elide the value prefix. Readers will examine the isValueExternal
+		// bitmap and know there is no value prefix byte if !isValueExternal.
+		w.values.Put(value)
+	}
+	if len(ikey.UserKey) > int(w.maximumKeyLength) {
+		w.maximumKeyLength = len(ikey.UserKey)
+	}
+	w.rows++
+}
+
+// Rows returns the number of rows in the current pending data block.
+func (w *DataBlockWriter) Rows() int {
+	return w.rows
+}
+
+// Size returns the size of the current pending data block.
+func (w *DataBlockWriter) Size() int {
+	off := blockHeaderSize(len(w.Schema.ColumnTypes)+dataBlockColumnMax, dataBlockCustomHeaderSize)
+	off = w.KeyWriter.Size(w.rows, off)
+	off = w.trailers.Size(w.rows, off)
+	off = w.prefixSame.Size(w.rows, off)
+	off = w.values.Size(w.rows, off)
+	off = w.isValueExternal.Size(w.rows, off)
+	off++ // trailer padding byte
+	return int(off)
+}
+
+// Finish serializes the pending data block.
+func (w *DataBlockWriter) Finish() []byte {
+	cols := len(w.Schema.ColumnTypes) + dataBlockColumnMax
+	h := Header{
+		Version: Version1,
+		Columns: uint16(cols),
+		Rows:    uint32(w.rows),
+	}
+	w.enc.init(w.Size(), h, dataBlockCustomHeaderSize)
+
+	// Write the max key length in the custom header.
+	binary.LittleEndian.PutUint32(w.enc.data()[:dataBlockCustomHeaderSize], uint32(w.maximumKeyLength))
+
+	// Write the user-defined key columns.
+	w.enc.encode(w.rows, w.KeyWriter)
+
+	// Write the internal key trailers.
+	w.enc.encode(w.rows, &w.trailers)
+
+	// Invert the prefix-same bitmap before writing it out, because we want it
+	// to represent when the prefix changes.
+	w.prefixSame.Invert(w.rows)
+	w.enc.encode(w.rows, &w.prefixSame)
+
+	// Write the value columns.
+	w.enc.encode(w.rows, &w.values)
+	w.enc.encode(w.rows, &w.isValueExternal)
+	return w.enc.finish()
+}
+
+// DataBlockReaderSize is the size of a DataBlockReader struct. If allocating
+// memory for a data block, the caller may want to additionally allocate memory
+// for the corresponding DataBlockReader.
+const DataBlockReaderSize = unsafe.Sizeof(DataBlockReader{})
+
+// A DataBlockReader holds state for reading a columnar data block. It may be
+// shared among multiple DataBlockIters.
+type DataBlockReader struct {
+	r BlockReader
+	// trailers holds an array of the InternalKey trailers, encoding the key
+	// kind and sequence number of each key.
+	trailers UnsafeUint64s
+	// prefixChanged is a bitmap indicating when the prefix (as defined by
+	// Split) of a key changes, relative to the preceding key. This is used to
+	// bound seeks within a prefix, and to optimize NextPrefix.
+	prefixChanged Bitmap
+	// values is the column reader for values. If the isValueExternal bitmap
+	// indicates a value is external, the value is prefixed with a ValuePrefix
+	// byte.
+	values RawBytes
+	// isValueExternal is the column reader for the is-value-external bitmap
+	// that indicates whether a value is stored out-of-band in a value block. If
+	// true, the value contains a ValuePrefix byte followed by an encoded value
+	// handle indicating the value's location within the value block(s).
+	isValueExternal Bitmap
+	// maximumKeyLength is the maximum length of a user key in the block.
+	// Iterators may use it to allocate a sufficiently large buffer up front,
+	// and elide size checks during iteration.
+	maximumKeyLength uint32
+}
+
+// BlockReader returns a pointer to the underlying BlockReader.
+func (r *DataBlockReader) BlockReader() *BlockReader {
+	return &r.r
+}
+
+// Init initializes the data block reader with the given serialized data block.
+func (r *DataBlockReader) Init(schema KeySchema, data []byte) {
+	r.r.Init(data, dataBlockCustomHeaderSize)
+	r.trailers = r.r.Uint64s(len(schema.ColumnTypes) + dataBlockColumnTrailer)
+	r.prefixChanged = r.r.Bitmap(len(schema.ColumnTypes) + dataBlockColumnPrefixChanged)
+	r.values = r.r.RawBytes(len(schema.ColumnTypes) + dataBlockColumnValue)
+	r.isValueExternal = r.r.Bitmap(len(schema.ColumnTypes) + dataBlockColumnIsValueExternal)
+	r.maximumKeyLength = binary.LittleEndian.Uint32(data[:dataBlockCustomHeaderSize])
+}
+
+func (r *DataBlockReader) toFormatter(f *binfmt.Formatter) {
+	f.CommentLine("data block header")
+	f.HexBytesln(4, "maximum key length: %d", r.maximumKeyLength)
+	r.r.headerToBinFormatter(f)
+	for i := 0; i < int(r.r.header.Columns); i++ {
+		r.r.columnToBinFormatter(f, i, int(r.r.header.Rows))
+	}
+}
+
+// DataBlockIter iterates over a columnar data block.
+type DataBlockIter struct {
+	// configuration
+	r            *DataBlockReader
+	maxRow       int
+	keySeeker    KeySeeker
+	getLazyValue func([]byte) base.LazyValue
+
+	// state
+	keyIter PrefixBytesIter
+	row     int
+	kv      base.InternalKV
+	kvRow   int // the row currently held in kv
+}
+
+var _ base.InternalIterator = (*DataBlockIter)(nil)
+
+// Init initializes the data block iterator, configuring it to read from the
+// provided reader.
+func (i *DataBlockIter) Init(
+	r *DataBlockReader, keyIterator KeySeeker, getLazyValue func([]byte) base.LazyValue,
+) error {
+	*i = DataBlockIter{
+		r:            r,
+		maxRow:       int(r.r.header.Rows) - 1,
+		keySeeker:    keyIterator,
+		getLazyValue: getLazyValue,
+		row:          -1,
+		kvRow:        math.MinInt,
+		kv:           base.InternalKV{},
+		keyIter:      PrefixBytesIter{},
+	}
+	// Allocate a keyIter buffer that's large enough to hold the largest user
+	// key in the block.
+	i.keyIter.Alloc(int(r.maximumKeyLength))
+	return i.keySeeker.Init(r)
+}
+
+// SeekGE implements the base.InternalIterator interface.
+func (i *DataBlockIter) SeekGE(key []byte, flags base.SeekGEFlags) *base.InternalKV {
+	searchDir := int8(0)
+	if flags.TrySeekUsingNext() {
+		searchDir = +1
+	}
+	return i.decodeRow(i.keySeeker.SeekGE(key, i.row, searchDir))
+}
+
+// SeekPrefixGE implements the base.InternalIterator interface.
+func (i *DataBlockIter) SeekPrefixGE(prefix, key []byte, flags base.SeekGEFlags) *base.InternalKV {
+	// This should never be called as prefix iteration is handled by
+	// sstable.Iterator.
+
+	// TODO(jackson): We can implement this and avoid propagating keys without
+	// the prefix up to the merging iterator. It will avoid unnecessary key
+	// comparisons fixing up the merging iterator heap. We can also short
+	// circuit the search if the prefix isn't found within the prefix column.
+	// There's some subtlety around ensuring we continue to benefit from the
+	// TrySeekUsingNext optimization.
+	panic("pebble: SeekPrefixGE unimplemented")
+}
+
+// SeekLT implements the base.InternalIterator interface.
+func (i *DataBlockIter) SeekLT(key []byte, _ base.SeekLTFlags) *base.InternalKV {
+	row := i.keySeeker.SeekGE(key, i.row, 0 /* searchDir */)
+	return i.decodeRow(row - 1)
+}
+
+// First implements the base.InternalIterator interface.
+func (i *DataBlockIter) First() *base.InternalKV {
+	return i.decodeRow(0)
+}
+
+// Last implements the base.InternalIterator interface.
+func (i *DataBlockIter) Last() *base.InternalKV {
+	return i.decodeRow(i.r.BlockReader().Rows() - 1)
+}
+
+// Next advances to the next KV pair in the block.
+func (i *DataBlockIter) Next() *base.InternalKV {
+	// Inline decodeRow, but avoiding unnecessary checks against i.row.
+	if i.row >= i.maxRow {
+		i.row = i.maxRow + 1
+		return nil
+	}
+	i.row++
+	i.kv.K = base.InternalKey{
+		UserKey: i.keySeeker.MaterializeUserKey(&i.keyIter, i.kvRow, i.row),
+		Trailer: base.InternalKeyTrailer(i.r.trailers.At(i.row)),
+	}
+	// Inline i.r.values.At(row).
+	startOffset := i.r.values.offsets.At(i.row)
+	v := unsafe.Slice((*byte)(i.r.values.ptr(startOffset)), i.r.values.offsets.At(i.row+1)-startOffset)
+	if i.r.isValueExternal.At(i.row) {
+		i.kv.V = i.getLazyValue(v)
+	} else {
+		i.kv.V = base.MakeInPlaceValue(v)
+	}
+	i.kvRow = i.row
+	return &i.kv
+}
+
+// NextPrefix moves the iterator to the next row with a different prefix than
+// the key at the current iterator position.
+//
+// The columnar block implementation uses a newPrefix bitmap to identify the
+// next row with a differing prefix from the current row's key. If newPrefix[i]
+// is set then row's i key prefix is different that row i-1. The bitmap is
+// organized as a slice of 64-bit words. If a 64-bit word in the bitmap is zero
+// then all of the rows corresponding to the bits in that word have the same
+// prefix and we can skip ahead. If a row is non-zero a small bit of bit
+// shifting and masking combined with bits.TrailingZeros64 can identify the the
+// next bit that is set after the current row. The bitmap uses 1 bit/row (0.125
+// bytes/row). A 32KB block containing 1300 rows (25 bytes/row) would need a
+// bitmap of 21 64-bit words. Even in the worst case where every word is 0 this
+// bitmap can be scanned in ~20 ns (1 ns/word) leading to a total NextPrefix
+// time of ~30 ns if a row is found and decodeRow are called. In more normal
+// cases, NextPrefix takes ~15% longer that a single Next call.
+//
+// For comparision, the rowblk nextPrefixV3 optimizations work by setting a bit
+// in the value prefix byte that indicates that the current key has the same
+// prefix as the previous key. Additionally, a bit is stolen from the restart
+// table entries indicating whether a restart table entry has the same key
+// prefix as the previous entry. Checking the value prefix byte bit requires
+// locating that byte which requires decoding 3 varints per key/value pair.
+func (i *DataBlockIter) NextPrefix(_ []byte) *base.InternalKV {
+	return i.decodeRow(i.r.prefixChanged.Successor(i.row + 1))
+}
+
+// Prev moves the iterator to the previous KV pair in the block.
+func (i *DataBlockIter) Prev() *base.InternalKV {
+	return i.decodeRow(i.row - 1)
+}
+
+// Error implements the base.InternalIterator interface. A DataBlockIter is
+// infallible and always returns a nil error.
+func (i *DataBlockIter) Error() error {
+	return nil // infallible
+}
+
+// Close implements the base.InternalIterator interface.
+func (i *DataBlockIter) Close() error {
+	*i = DataBlockIter{}
+	return nil
+}
+
+// SetBounds implements the base.InternalIterator interface.
+func (i *DataBlockIter) SetBounds(lower, upper []byte) {
+	// This should never be called as bounds are handled by sstable.Iterator.
+	panic("pebble: SetBounds unimplemented")
+}
+
+// SetContext implements the base.InternalIterator interface.
+func (i *DataBlockIter) SetContext(_ context.Context) {}
+
+var dataBlockTypeString string = fmt.Sprintf("%T", (*DataBlockIter)(nil))
+
+// String implements the base.InternalIterator interface.
+func (i *DataBlockIter) String() string {
+	return dataBlockTypeString
+}
+
+// DebugTree is part of the InternalIterator interface.
+func (i *DataBlockIter) DebugTree(tp treeprinter.Node) {
+	tp.Childf("%T(%p)", i, i)
+}
+
+func (i *DataBlockIter) decodeRow(row int) *base.InternalKV {
+	switch {
+	case row < 0:
+		i.row = -1
+		return nil
+	case row >= i.r.BlockReader().Rows():
+		i.row = i.r.BlockReader().Rows()
+		return nil
+	case i.kvRow == row:
+		i.row = row
+		// Already synthesized the kv at row.
+		return &i.kv
+	default:
+		i.kv.K = base.InternalKey{
+			UserKey: i.keySeeker.MaterializeUserKey(&i.keyIter, i.kvRow, row),
+			Trailer: base.InternalKeyTrailer(i.r.trailers.At(row)),
+		}
+		// Inline i.r.values.At(row).
+		startOffset := i.r.values.offsets.At(row)
+		v := unsafe.Slice((*byte)(i.r.values.ptr(startOffset)), i.r.values.offsets.At(row+1)-startOffset)
+		if i.r.isValueExternal.At(row) {
+			i.kv.V = i.getLazyValue(v)
+		} else {
+			i.kv.V = base.MakeInPlaceValue(v)
+		}
+		i.row = row
+		i.kvRow = row
+		return &i.kv
+	}
+}
diff --git a/sstable/colblk/prefix_bytes.go b/sstable/colblk/prefix_bytes.go
index 47126979..e9bc4447 100644
--- a/sstable/colblk/prefix_bytes.go
+++ b/sstable/colblk/prefix_bytes.go
@@ -250,7 +250,9 @@ type PrefixBytesIter struct {
 }
 
 // SetAt updates the provided PrefixBytesIter to hold the i'th []byte slice in
-// the PrefixBytes.
+// the PrefixBytes. The PrefixBytesIter's buffer must be sufficiently large to
+// hold the i'th []byte slice, and the caller is required to statically ensure
+// this.
 func (b *PrefixBytes) SetAt(it *PrefixBytesIter, i int) {
 	// Determine the offset and length of the bundle prefix.
 	bundleOffsetIndex := b.bundleOffsetIndexForRow(i)
@@ -268,8 +270,7 @@ func (b *PrefixBytes) SetAt(it *PrefixBytesIter, i int) {
 	// Grow the size of the iterator's buffer if necessary.
 	it.len = b.sharedPrefixLen + int(it.bundlePrefixLen) + int(rowSuffixEnd-rowSuffixStart)
 	if it.len > it.cap {
-		it.cap = it.len << 1
-		it.ptr = mallocgc(uintptr(it.cap), nil, false)
+		panic(errors.AssertionFailedf("buffer too small: %d > %d", it.len, it.cap))
 	}
 
 	// Copy the shared key prefix.
@@ -291,7 +292,9 @@ func (b *PrefixBytes) SetAt(it *PrefixBytesIter, i int) {
 
 // SetNext updates the provided PrefixBytesIter to hold the next []byte slice in
 // the PrefixBytes. SetNext requires the provided iter to currently hold a slice
-// and for a subsequent slice to exist within the PrefixBytes.
+// and for a subsequent slice to exist within the PrefixBytes.  The
+// PrefixBytesIter's buffer must be sufficiently large to hold the next []byte
+// slice, and the caller is required to statically ensure this.
 func (b *PrefixBytes) SetNext(it *PrefixBytesIter) {
 	it.offsetIndex++
 	// If the next row is in the same bundle, we can take a fast path of only
@@ -308,10 +311,7 @@ func (b *PrefixBytes) SetNext(it *PrefixBytesIter) {
 		// Grow the buffer if necessary.
 		it.len = b.sharedPrefixLen + int(it.bundlePrefixLen) + int(rowSuffixEnd-rowSuffixStart)
 		if it.len > it.cap {
-			it.cap = it.len << 1
-			prevPtr := it.ptr
-			it.ptr = mallocgc(uintptr(it.cap), nil, false)
-			memmove(it.ptr, prevPtr, uintptr(b.sharedPrefixLen)+uintptr(it.bundlePrefixLen))
+			panic(errors.AssertionFailedf("buffer too small: %d > %d", it.len, it.cap))
 		}
 		// Copy in the per-row suffix.
 		memmove(
@@ -337,9 +337,7 @@ func (b *PrefixBytes) SetNext(it *PrefixBytesIter) {
 	// Grow the buffer if necessary.
 	it.len = b.sharedPrefixLen + int(it.bundlePrefixLen) + int(rowSuffixEnd-rowSuffixStart)
 	if it.len > it.cap {
-		it.cap = it.len << 1
-		it.ptr = mallocgc(uintptr(it.cap), nil, false)
-		memmove(it.ptr, b.rawBytes.data, uintptr(b.sharedPrefixLen))
+		panic(errors.AssertionFailedf("buffer too small: %d > %d", it.len, it.cap))
 	}
 	// Copy in the new bundle suffix.
 	memmove(
diff --git a/sstable/colblk/raw_bytes.go b/sstable/colblk/raw_bytes.go
index 43c9d474..a7c9e197 100644
--- a/sstable/colblk/raw_bytes.go
+++ b/sstable/colblk/raw_bytes.go
@@ -5,6 +5,7 @@
 package colblk
 
 import (
+	"bytes"
 	"fmt"
 	"io"
 	"unsafe"
@@ -72,6 +73,9 @@ func DecodeRawBytes(b []byte, offset uint32, count int) (rawBytes RawBytes, endO
 var _ DecodeFunc[RawBytes] = DecodeRawBytes
 
 func defaultSliceFormatter(x []byte) string {
+	if bytes.ContainsFunc(x, func(r rune) bool { return r < 32 || r > 126 }) {
+		return fmt.Sprintf("%q", x)
+	}
 	return string(x)
 }
 
@@ -160,6 +164,15 @@ func (b *RawBytesBuilder) PutConcat(s1, s2 []byte) {
 	b.offsets.Set(b.rows, uint32(len(b.data)))
 }
 
+// LastSlice returns the last slice added to the builder. The returned slice is
+// owned by the builder and must not be mutated.
+func (b *RawBytesBuilder) LastSlice() []byte {
+	if b.rows == 0 {
+		return nil
+	}
+	return b.data[b.offsets.array.elems.At(b.rows-1):b.offsets.array.elems.At(b.rows)]
+}
+
 // Finish writes the serialized byte slices to buf starting at offset. The buf
 // slice must be sufficiently large to store the serialized output. The caller
 // should use [Size] to size buf appropriately before calling Finish.
diff --git a/sstable/colblk/unsafe_slice.go b/sstable/colblk/unsafe_slice.go
index 74729bfd..a4a6f2f9 100644
--- a/sstable/colblk/unsafe_slice.go
+++ b/sstable/colblk/unsafe_slice.go
@@ -143,6 +143,13 @@ type UnsafeBuf struct {
 	cap int
 }
 
+// Alloc allocates a buffer of size n, without zeroing its contents or copying
+// previous buffer contents.
+func (b *UnsafeBuf) Alloc(n int) {
+	b.ptr = mallocgc(uintptr(n), nil, false)
+	b.cap = n
+}
+
 // UnsafeSlice returns the current contents of the buf.
 func (b *UnsafeBuf) UnsafeSlice() []byte {
 	return unsafe.Slice((*byte)(b.ptr), b.len)


Test patch:
diff --git a/internal/crdbtest/crdbtest.go b/internal/crdbtest/crdbtest.go
index df037310..2f1c77c8 100644
--- a/internal/crdbtest/crdbtest.go
+++ b/internal/crdbtest/crdbtest.go
@@ -132,14 +132,14 @@ func EncodeTimestamp(key []byte, walltime uint64, logical uint32) []byte {
 // DecodeTimestamp decodes a MVCC timestamp from a serialized MVCC key.
 func DecodeTimestamp(mvccKey []byte) ([]byte, []byte, uint64, uint32) {
 	tsLen := int(mvccKey[len(mvccKey)-1])
-	keyPartEnd := len(mvccKey) - 1 - tsLen
+	keyPartEnd := len(mvccKey) - tsLen
 	if keyPartEnd < 0 {
 		return nil, nil, 0, 0
 	}
 
 	key := mvccKey[:keyPartEnd]
 	if tsLen > 0 {
-		ts := mvccKey[keyPartEnd+1 : len(mvccKey)-1]
+		ts := mvccKey[keyPartEnd : len(mvccKey)-1]
 		switch len(ts) {
 		case 8:
 			return key, nil, binary.BigEndian.Uint64(ts[:8]), 0
diff --git a/sstable/colblk/cockroach_test.go b/sstable/colblk/cockroach_test.go
new file mode 100644
index 00000000..b0bfb7b5
--- /dev/null
+++ b/sstable/colblk/cockroach_test.go
@@ -0,0 +1,467 @@
+// Copyright 2024 The LevelDB-Go and Pebble Authors. All rights reserved. Use
+// of this source code is governed by a BSD-style license that can be found in
+// the LICENSE file.
+
+package colblk
+
+import (
+	"bytes"
+	"cmp"
+	"encoding/binary"
+	"fmt"
+	"io"
+	"sync"
+	"testing"
+	"time"
+	"unsafe"
+
+	"github.com/cockroachdb/pebble/internal/base"
+	"github.com/cockroachdb/pebble/internal/crdbtest"
+	"github.com/cockroachdb/pebble/sstable/block"
+	"github.com/stretchr/testify/require"
+	"golang.org/x/exp/rand"
+)
+
+const (
+	cockroachColPrefix int = iota
+	cockroachColMVCCWallTime
+	cockroachColMVCCLogical
+	cockroachColUntypedSuffix
+	cockroachColCount
+)
+
+var cockroachKeySchema = KeySchema{
+	ColumnTypes: []DataType{
+		cockroachColPrefix:        DataTypePrefixBytes,
+		cockroachColMVCCWallTime:  DataTypeUint64,
+		cockroachColMVCCLogical:   DataTypeUint32,
+		cockroachColUntypedSuffix: DataTypeBytes,
+	},
+	NewKeyWriter: func() KeyWriter {
+		kw := &cockroachKeyWriter{}
+		kw.prefixes.Init(16)
+		kw.wallTimes.Init()
+		kw.logicalTimes.InitWithDefault()
+		kw.untypedSuffixes.Init()
+		return kw
+	},
+	NewKeySeeker: func() KeySeeker {
+		return &cockroachKeySeeker{}
+	},
+}
+
+type cockroachKeyWriter struct {
+	prefixes        PrefixBytesBuilder
+	wallTimes       UintBuilder[uint64]
+	logicalTimes    UintBuilder[uint32]
+	untypedSuffixes RawBytesBuilder
+	prevSuffix      []byte
+}
+
+func (kw *cockroachKeyWriter) ComparePrev(key []byte) KeyComparison {
+	lp := kw.prefixes.LastKey()
+	var cmpv KeyComparison
+	cmpv.PrefixLen = int32(crdbtest.Split(key)) // TODO(jackson): Inline
+	cmpv.CommonPrefixLen = int32(bytesSharedPrefix(lp, key[:cmpv.PrefixLen]))
+	if cmpv.CommonPrefixLen == cmpv.PrefixLen {
+		cmpv.UserKeyComparison = int32(crdbtest.CompareSuffixes(key[cmpv.PrefixLen:], kw.prevSuffix))
+		return cmpv
+	}
+	// The keys have different MVCC prefixes. We haven't determined which is
+	// greater, but we know the index at which they diverge. The base.Comparer
+	// contract dictates that prefixes must be lexicograrphically ordered.
+	if len(lp) == int(cmpv.CommonPrefixLen) {
+		// cmpv.PrefixLen > cmpv.PrefixLenShared; key is greater.
+		cmpv.UserKeyComparison = +1
+	} else {
+		// Both keys have at least 1 additional byte at which they diverge.
+		// Compare the diverging byte.
+		cmpv.UserKeyComparison = int32(cmp.Compare(key[cmpv.CommonPrefixLen], lp[cmpv.CommonPrefixLen]))
+	}
+	return cmpv
+}
+
+func (kw *cockroachKeyWriter) WriteKey(
+	row int, key []byte, keyPrefixLen, keyPrefixLenSharedWithPrev int32,
+) {
+	// TODO(jackson): Avoid copying the previous suffix.
+	// TODO(jackson): Use keyPrefixLen to speed up decoding.
+	prefix, untypedSuffix, wallTime, logicalTime := crdbtest.DecodeTimestamp(key)
+	kw.prevSuffix = append(kw.prevSuffix[:0], key[keyPrefixLen:]...)
+	kw.prefixes.Put(prefix, int(keyPrefixLenSharedWithPrev))
+	kw.wallTimes.Set(row, wallTime)
+	// The w.logicalTimes builder was initialized with InitWithDefault, so if we
+	// don't set a value, the column value is implicitly zero. We only need to
+	// Set anything for non-zero values.
+	if logicalTime > 0 {
+		kw.logicalTimes.Set(row, logicalTime)
+	}
+	kw.untypedSuffixes.Put(untypedSuffix)
+}
+
+func (kw *cockroachKeyWriter) Reset() {
+	kw.prefixes.Reset()
+	kw.wallTimes.Reset()
+	kw.logicalTimes.Reset()
+	kw.untypedSuffixes.Reset()
+}
+
+func (kw *cockroachKeyWriter) WriteDebug(dst io.Writer, rows int) {
+	fmt.Fprint(dst, "prefixes: ")
+	kw.prefixes.WriteDebug(dst, rows)
+	fmt.Fprintln(dst)
+	fmt.Fprint(dst, "wall times: ")
+	kw.wallTimes.WriteDebug(dst, rows)
+	fmt.Fprintln(dst)
+	fmt.Fprint(dst, "logical times: ")
+	kw.logicalTimes.WriteDebug(dst, rows)
+	fmt.Fprintln(dst)
+	fmt.Fprint(dst, "untyped suffixes: ")
+	kw.untypedSuffixes.WriteDebug(dst, rows)
+	fmt.Fprintln(dst)
+}
+
+func (kw *cockroachKeyWriter) NumColumns() int {
+	return cockroachColCount
+}
+
+func (kw *cockroachKeyWriter) DataType(col int) DataType {
+	return cockroachKeySchema.ColumnTypes[col]
+}
+
+func (kw *cockroachKeyWriter) Size(rows int, offset uint32) uint32 {
+	offset = kw.prefixes.Size(rows, offset)
+	offset = kw.wallTimes.Size(rows, offset)
+	offset = kw.logicalTimes.Size(rows, offset)
+	offset = kw.untypedSuffixes.Size(rows, offset)
+	return offset
+}
+
+func (kw *cockroachKeyWriter) Finish(
+	col int, rows int, offset uint32, buf []byte,
+) (endOffset uint32) {
+	switch col {
+	case cockroachColPrefix:
+		return kw.prefixes.Finish(0, rows, offset, buf)
+	case cockroachColMVCCWallTime:
+		return kw.wallTimes.Finish(0, rows, offset, buf)
+	case cockroachColMVCCLogical:
+		return kw.logicalTimes.Finish(0, rows, offset, buf)
+	case cockroachColUntypedSuffix:
+		return kw.untypedSuffixes.Finish(0, rows, offset, buf)
+	default:
+		panic(fmt.Sprintf("unknown default key column: %d", col))
+	}
+}
+
+var cockroachKeySeekerPool = sync.Pool{
+	New: func() interface{} { return &cockroachKeySeeker{} },
+}
+
+type cockroachKeySeeker struct {
+	reader          *DataBlockReader
+	prefixes        PrefixBytes
+	mvccWallTimes   UnsafeUint64s
+	mvccLogical     UnsafeUint32s
+	untypedSuffixes RawBytes
+	sharedPrefix    []byte
+}
+
+func (ks *cockroachKeySeeker) Init(r *DataBlockReader) error {
+	ks.reader = r
+	ks.prefixes = r.r.PrefixBytes(cockroachColPrefix)
+	ks.mvccWallTimes = r.r.Uint64s(cockroachColMVCCWallTime)
+	ks.mvccLogical = r.r.Uint32s(cockroachColMVCCLogical)
+	ks.untypedSuffixes = r.r.RawBytes(cockroachColUntypedSuffix)
+	ks.sharedPrefix = ks.prefixes.SharedPrefix()
+	return nil
+}
+
+func (ks *cockroachKeySeeker) SeekGE(key []byte, currRow int, dir int8) (row int) {
+	// TODO(jackson): Inline crdbtest.Split.
+	si := crdbtest.Split(key)
+	row, eq := ks.prefixes.Search(key[:si-1])
+	if eq {
+		return ks.seekGEOnSuffix(row, key[si:])
+	}
+	return row
+}
+
+// seekGEOnSuffix is a helper function for SeekGE when a seek key's prefix
+// exactly matches a row. seekGEOnSuffix finds the first row at index or later
+// with the same prefix as index and a suffix greater than or equal to [suffix],
+// or if no such row exists, the next row with a different prefix.
+func (ks *cockroachKeySeeker) seekGEOnSuffix(index int, seekSuffix []byte) (row int) {
+	// The search key's prefix exactly matches the prefix of the row at index.
+	const withWall = 9
+	const withLogical = withWall + 4
+	const withSynthetic = withLogical + 1
+	var seekWallTime uint64
+	var seekLogicalTime uint32
+	switch len(seekSuffix) {
+	case 0:
+		// The search key has no suffix, so it's the smallest possible key with
+		// its prefix. Return the row. This is a common case where the user is
+		// seeking to the most-recent row and just wants the smallest key with
+		// the prefix.
+		return index
+	case withLogical, withSynthetic:
+		seekWallTime = binary.LittleEndian.Uint64(seekSuffix)
+		seekLogicalTime = binary.LittleEndian.Uint32(seekSuffix[8:])
+	case withWall:
+		seekWallTime = binary.LittleEndian.Uint64(seekSuffix)
+	default:
+		// The suffix is untyped. Compare the untyped suffixes.
+		// Binary search between [index, prefixChanged.Successor(index)].
+		//
+		// Define f(l-1) == false and f(u) == true.
+		// Invariant: f(l-1) == false, f(u) == true.
+		l := index
+		u := ks.reader.prefixChanged.Successor(index)
+		for l < u {
+			h := int(uint(l+u) >> 1) // avoid overflow when computing h
+			// l ≤ h < u
+			if bytes.Compare(ks.untypedSuffixes.At(h), seekSuffix) >= 0 {
+				u = h // preserves f(u) == true
+			} else {
+				l = h + 1 // preserves f(l-1) == false
+			}
+		}
+		return l
+	}
+	// Seeking among MVCC versions using a MVCC timestamp.
+
+	// TODO(jackson): What if the row has an untyped suffix?
+
+	// Binary search between [index, prefixChanged.Successor(index)].
+	//
+	// Define f(l-1) == false and f(u) == true.
+	// Invariant: f(l-1) == false, f(u) == true.
+	l := index
+	u := ks.reader.prefixChanged.Successor(index)
+	for l < u {
+		h := int(uint(l+u) >> 1) // avoid overflow when computing h
+		// l ≤ h < u
+		switch cmp.Compare(ks.mvccWallTimes.At(h), seekWallTime) {
+		case -1:
+			l = h + 1 // preserves f(l-1) == false
+		case +1:
+			u = h // preserves f(u) == true
+		}
+		if cmp.Compare(ks.mvccLogical.At(h), seekLogicalTime) >= 0 {
+			u = h // preserves f(u) == true
+		} else {
+			l = h + 1 // preserves f(l-1) == false
+		}
+	}
+	return l
+}
+
+func (ks *cockroachKeySeeker) MaterializeUserKey(ki *PrefixBytesIter, prevRow, row int) []byte {
+	if prevRow+1 == row && prevRow >= 0 {
+		ks.prefixes.SetNext(ki)
+	} else {
+		ks.prefixes.SetAt(ki, row)
+	}
+
+	mvccWall := ks.mvccWallTimes.At(row)
+	mvccLogical := ks.mvccLogical.At(row)
+	if mvccWall == 0 && mvccLogical == 0 {
+		// This is not an MVCC key. Use the untyped suffix.
+		untypedSuffixed := ks.untypedSuffixes.At(row)
+		memmove(unsafe.Pointer(uintptr(ki.ptr)+uintptr(ki.len)), unsafe.Pointer(unsafe.SliceData(untypedSuffixed)), uintptr(len(untypedSuffixed)))
+		return unsafe.Slice((*byte)(ki.ptr), ki.len+len(untypedSuffixed))
+	}
+
+	// This is an MVCC key.
+	if mvccLogical == 0 {
+		binary.BigEndian.PutUint64(unsafe.Slice((*byte)(unsafe.Pointer(uintptr(ki.ptr)+uintptr(ki.len))), 8), mvccWall)
+		*(*byte)(unsafe.Pointer(uintptr(ki.ptr) + uintptr(ki.len) + 8)) = 9
+		return unsafe.Slice((*byte)(ki.ptr), ki.len+9)
+	}
+	binary.BigEndian.PutUint64(unsafe.Slice((*byte)(unsafe.Pointer(uintptr(ki.ptr)+uintptr(ki.len))), 8), mvccWall)
+	binary.BigEndian.PutUint32(unsafe.Slice((*byte)(unsafe.Pointer(uintptr(ki.ptr)+uintptr(ki.len+8))), 4), mvccLogical)
+	*(*byte)(unsafe.Pointer(uintptr(ki.ptr) + uintptr(ki.len) + 12)) = 13
+	return unsafe.Slice((*byte)(ki.ptr), ki.len+13)
+}
+
+func (ks *cockroachKeySeeker) Release() {
+	*ks = cockroachKeySeeker{}
+	cockroachKeySeekerPool.Put(ks)
+}
+
+func TestCockroachDataBlock(t *testing.T) {
+	const targetBlockSize = 32 << 10
+	seed := uint64(time.Now().UnixNano())
+	t.Logf("seed: %d", seed)
+	rng := rand.New(rand.NewSource(seed))
+	keys, values := crdbtest.RandomKVs(rng, targetBlockSize/100, crdbtest.KeyConfig{
+		PrefixAlphabetLen: 26,
+		PrefixLen:         12,
+		BaseWallTime:      seed,
+	}, 100)
+
+	var w DataBlockWriter
+	w.Init(cockroachKeySchema)
+	var count int
+	for w.Size() < targetBlockSize {
+		ik := base.MakeInternalKey(keys[count], base.SeqNum(rng.Uint64n(uint64(base.SeqNumMax))), base.InternalKeyKindSet)
+		kcmp := w.KeyWriter.ComparePrev(ik.UserKey)
+		w.Add(ik, values[count], block.InPlaceValuePrefix(kcmp.PrefixEqual()), kcmp)
+		count++
+	}
+	serializedBlock := w.Finish()
+	var reader DataBlockReader
+	var it DataBlockIter
+	reader.Init(cockroachKeySchema, serializedBlock)
+	it.Init(&reader, cockroachKeySchema.NewKeySeeker(), func([]byte) base.LazyValue {
+		return base.LazyValue{ValueOrHandle: []byte("mock external value")}
+	})
+
+	t.Run("Next", func(t *testing.T) {
+		// Scan the block using Next and ensure that all the keys values match.
+		i := 0
+		for kv := it.First(); kv != nil; i, kv = i+1, it.Next() {
+			if !bytes.Equal(kv.K.UserKey, keys[i]) {
+				t.Fatalf("expected %q, but found %q", keys[i], kv.K.UserKey)
+			}
+			if !bytes.Equal(kv.V.InPlaceValue(), values[i]) {
+				t.Fatalf("expected %x, but found %x", values[i], kv.V.InPlaceValue())
+			}
+		}
+		require.Equal(t, count, i)
+	})
+	t.Run("SeekGE", func(t *testing.T) {
+		rng := rand.New(rand.NewSource(seed))
+		for _, i := range rng.Perm(count) {
+			kv := it.SeekGE(keys[i], base.SeekGEFlagsNone)
+			if kv == nil {
+				t.Fatalf("%q not found", keys[i])
+			}
+			if !bytes.Equal(kv.V.InPlaceValue(), values[i]) {
+				t.Fatalf("expected %x, but found %x", values[i], kv.V.InPlaceValue())
+			}
+		}
+	})
+}
+
+func BenchmarkCockroachDataBlockWriter(b *testing.B) {
+	for _, alphaLen := range []int{4, 8, 26} {
+		for _, lenSharedPct := range []float64{0.25, 0.5} {
+			for _, prefixLen := range []int{8, 32, 128} {
+				lenShared := int(float64(prefixLen) * lenSharedPct)
+				for _, valueLen := range []int{8, 128, 1024} {
+					keyConfig := crdbtest.KeyConfig{
+						PrefixAlphabetLen: alphaLen,
+						PrefixLen:         prefixLen,
+						PrefixLenShared:   lenShared,
+						Logical:           0,
+						BaseWallTime:      uint64(time.Now().UnixNano()),
+					}
+					b.Run(fmt.Sprintf("%s,valueLen=%d", keyConfig, valueLen), func(b *testing.B) {
+						benchmarkCockroachDataBlockWriter(b, keyConfig, valueLen)
+					})
+				}
+			}
+		}
+	}
+}
+
+func benchmarkCockroachDataBlockWriter(b *testing.B, keyConfig crdbtest.KeyConfig, valueLen int) {
+	const targetBlockSize = 32 << 10
+	seed := uint64(time.Now().UnixNano())
+	rng := rand.New(rand.NewSource(seed))
+	keys, values := crdbtest.RandomKVs(rng, targetBlockSize/valueLen, keyConfig, valueLen)
+
+	var w DataBlockWriter
+	w.Init(cockroachKeySchema)
+
+	b.ResetTimer()
+	for i := 0; i < b.N; i++ {
+		w.Reset()
+		var count int
+		for w.Size() < targetBlockSize {
+			ik := base.MakeInternalKey(keys[count], base.SeqNum(rng.Uint64n(uint64(base.SeqNumMax))), base.InternalKeyKindSet)
+			kcmp := w.KeyWriter.ComparePrev(ik.UserKey)
+			w.Add(ik, values[count], block.InPlaceValuePrefix(kcmp.PrefixEqual()), kcmp)
+			count++
+		}
+		_ = w.Finish()
+	}
+}
+
+func BenchmarkCockroachDataBlockIter(b *testing.B) {
+	for _, alphaLen := range []int{4, 8, 26} {
+		for _, lenSharedPct := range []float64{0.25, 0.5} {
+			for _, prefixLen := range []int{8, 32, 128} {
+				lenShared := int(float64(prefixLen) * lenSharedPct)
+				for _, logical := range []uint32{0, 1} {
+					for _, valueLen := range []int{8, 128, 1024} {
+						keyConfig := crdbtest.KeyConfig{
+							PrefixAlphabetLen: alphaLen,
+							PrefixLen:         prefixLen,
+							PrefixLenShared:   lenShared,
+							Logical:           logical,
+							BaseWallTime:      uint64(time.Now().UnixNano()),
+						}
+						b.Run(fmt.Sprintf("%s,value=%d", keyConfig, valueLen),
+							func(b *testing.B) {
+								benchmarkCockroachDataBlockIter(b, keyConfig, valueLen)
+							})
+					}
+				}
+			}
+		}
+	}
+}
+
+func benchmarkCockroachDataBlockIter(b *testing.B, keyConfig crdbtest.KeyConfig, valueLen int) {
+	const targetBlockSize = 32 << 10
+	seed := uint64(time.Now().UnixNano())
+	rng := rand.New(rand.NewSource(seed))
+	keys, values := crdbtest.RandomKVs(rng, targetBlockSize/valueLen, keyConfig, valueLen)
+
+	var w DataBlockWriter
+	w.Init(cockroachKeySchema)
+	var count int
+	for w.Size() < targetBlockSize {
+		ik := base.MakeInternalKey(keys[count], base.SeqNum(rng.Uint64n(uint64(base.SeqNumMax))), base.InternalKeyKindSet)
+		kcmp := w.KeyWriter.ComparePrev(ik.UserKey)
+		w.Add(ik, values[count], block.InPlaceValuePrefix(kcmp.PrefixEqual()), kcmp)
+		count++
+	}
+	serializedBlock := w.Finish()
+	var reader DataBlockReader
+	var it DataBlockIter
+	reader.Init(cockroachKeySchema, serializedBlock)
+	it.Init(&reader, cockroachKeySchema.NewKeySeeker(), func([]byte) base.LazyValue {
+		return base.LazyValue{ValueOrHandle: []byte("mock external value")}
+	})
+	avgRowSize := float64(len(serializedBlock)) / float64(count)
+
+	b.Run("Next", func(b *testing.B) {
+		kv := it.First()
+		b.ResetTimer()
+		for i := 0; i < b.N; i++ {
+			if kv == nil {
+				kv = it.First()
+			} else {
+				kv = it.Next()
+			}
+		}
+		b.StopTimer()
+		b.ReportMetric(avgRowSize, "bytes/row")
+	})
+	b.Run("SeekGE", func(b *testing.B) {
+		rng := rand.New(rand.NewSource(seed))
+		b.ResetTimer()
+		for i := 0; i < b.N; i++ {
+			k := keys[rng.Intn(count)]
+			if kv := it.SeekGE(k, base.SeekGEFlagsNone); kv == nil {
+				b.Fatalf("%q not found", k)
+			}
+		}
+		b.StopTimer()
+		b.ReportMetric(avgRowSize, "bytes/row")
+	})
+}
diff --git a/sstable/colblk/data_block_test.go b/sstable/colblk/data_block_test.go
new file mode 100644
index 00000000..ec3e1b06
--- /dev/null
+++ b/sstable/colblk/data_block_test.go
@@ -0,0 +1,136 @@
+// Copyright 2024 The LevelDB-Go and Pebble Authors. All rights reserved. Use
+// of this source code is governed by a BSD-style license that can be found in
+// the LICENSE file.
+
+package colblk
+
+import (
+	"bytes"
+	"fmt"
+	"slices"
+	"strings"
+	"testing"
+	"time"
+
+	"github.com/cockroachdb/datadriven"
+	"github.com/cockroachdb/pebble/internal/base"
+	"github.com/cockroachdb/pebble/internal/binfmt"
+	"github.com/cockroachdb/pebble/internal/itertest"
+	"github.com/cockroachdb/pebble/internal/testkeys"
+	"github.com/cockroachdb/pebble/sstable/block"
+	"golang.org/x/exp/rand"
+)
+
+var testKeysSchema = DefaultKeySchema(testkeys.Comparer, 16)
+
+func TestDataBlock(t *testing.T) {
+	var buf bytes.Buffer
+	var w DataBlockWriter
+	var r DataBlockReader
+	var it DataBlockIter
+	datadriven.Walk(t, "testdata/data_block", func(t *testing.T, path string) {
+		datadriven.RunTest(t, path, func(t *testing.T, td *datadriven.TestData) string {
+			buf.Reset()
+			switch td.Cmd {
+			case "init":
+				var bundleSize int
+				if td.MaybeScanArgs(t, "bundle-size", &bundleSize) {
+					w.Init(DefaultKeySchema(testkeys.Comparer, bundleSize))
+				} else {
+					w.Init(testKeysSchema)
+				}
+				fmt.Fprint(&buf, &w)
+				return buf.String()
+			case "write":
+				for _, line := range strings.Split(td.Input, "\n") {
+					j := strings.IndexRune(line, ':')
+					ik := base.ParsePrettyInternalKey(line[:j])
+
+					kcmp := w.KeyWriter.ComparePrev(ik.UserKey)
+					valueString := line[j+1:]
+					vp := block.InPlaceValuePrefix(kcmp.PrefixEqual())
+					if strings.HasPrefix(valueString, "valueHandle") {
+						vp = block.ValueHandlePrefix(kcmp.PrefixEqual(), 0)
+					}
+					v := []byte(line[j+1:])
+					w.Add(ik, v, vp, kcmp)
+				}
+				fmt.Fprint(&buf, &w)
+				return buf.String()
+			case "finish":
+				block := w.Finish()
+				r.Init(testKeysSchema, block)
+				f := binfmt.New(r.r.data).LineWidth(20)
+				r.toFormatter(f)
+
+				return f.String()
+			case "iter":
+				it.Init(&r, testKeysSchema.NewKeySeeker(), func([]byte) base.LazyValue {
+					return base.LazyValue{ValueOrHandle: []byte("mock external value")}
+				})
+				return itertest.RunInternalIterCmd(t, td, &it)
+			default:
+				return fmt.Sprintf("unknown command: %s", td.Cmd)
+			}
+		})
+	})
+}
+
+func BenchmarkDataBlockWriter(b *testing.B) {
+	for _, prefixSize := range []int{8, 32, 128} {
+		for _, valueSize := range []int{8, 128, 1024} {
+			b.Run(fmt.Sprintf("prefix=%d,value=%d", prefixSize, valueSize), func(b *testing.B) {
+				benchmarkDataBlockWriter(b, prefixSize, valueSize)
+			})
+		}
+	}
+}
+
+func benchmarkDataBlockWriter(b *testing.B, prefixSize, valueSize int) {
+	const targetBlockSize = 32 << 10
+	seed := uint64(time.Now().UnixNano())
+	rng := rand.New(rand.NewSource(seed))
+	keys, values := makeTestKeyRandomKVs(rng, prefixSize, valueSize, targetBlockSize)
+
+	var w DataBlockWriter
+	w.Init(testKeysSchema)
+	b.ResetTimer()
+
+	for i := 0; i < b.N; i++ {
+		w.Reset()
+		var j int
+		for w.Size() < targetBlockSize {
+			ik := base.MakeInternalKey(keys[j], base.SeqNum(rng.Uint64n(uint64(base.SeqNumMax))), base.InternalKeyKindSet)
+			kcmp := w.KeyWriter.ComparePrev(ik.UserKey)
+			vp := block.InPlaceValuePrefix(kcmp.PrefixEqual())
+			w.Add(ik, values[j], vp, kcmp)
+			j++
+		}
+		w.Finish()
+	}
+}
+
+func makeTestKeyRandomKVs(
+	rng *rand.Rand, prefixSize, valueSize int, aggregateSize int,
+) (keys, vals [][]byte) {
+	keys = make([][]byte, aggregateSize/valueSize+1)
+	vals = make([][]byte, len(keys))
+	for i := range keys {
+		keys[i] = randTestKey(rng, make([]byte, prefixSize+testkeys.MaxSuffixLen), prefixSize)
+		vals[i] = make([]byte, valueSize)
+		rng.Read(vals[i])
+	}
+	slices.SortFunc(keys, bytes.Compare)
+	return keys, vals
+}
+
+func randTestKey(rng *rand.Rand, buf []byte, prefixLen int) []byte {
+	suffix := rng.Int63n(100)
+	sl := testkeys.SuffixLen(suffix)
+	buf = buf[0 : prefixLen+sl]
+	for i := 0; i < prefixLen; i++ {
+		buf[i] = byte(rng.Intn(26) + 'a')
+	}
+	testkeys.WriteSuffix(buf[prefixLen:], suffix)
+	return buf
+}
diff --git a/sstable/colblk/prefix_bytes_test.go b/sstable/colblk/prefix_bytes_test.go
index adae5b79..d2cfefb9 100644
--- a/sstable/colblk/prefix_bytes_test.go
+++ b/sstable/colblk/prefix_bytes_test.go
@@ -275,6 +275,7 @@ func BenchmarkPrefixBytes(b *testing.B) {
 			pb, _ := DecodePrefixBytes(buf, 0, n)
 			b.ResetTimer()
 			var pbi PrefixBytesIter
+			pbi.Alloc(maxLen)
 			for i := 0; i < b.N; i++ {
 				j := i % n
 				if j == 0 {
diff --git a/sstable/colblk/testdata/data_block/bundle_search b/sstable/colblk/testdata/data_block/bundle_search
new file mode 100644
index 00000000..addcdaa6
--- /dev/null
+++ b/sstable/colblk/testdata/data_block/bundle_search
@@ -0,0 +1,543 @@
+# Build a test block with words beginning with "ba". Some of the bundle prefixes
+# are the same, so it's a good data set for testing prefix seeking behavior.
+#
+# It also includes an instance where the bundle prefix is "ck" for a few
+# bundles, then extends to "ckhand" for a bundle, and then returns to "ck".
+# There's subtlety in implementing binary search among the bundle prefixes; A
+# search for "backache" must consider all the bundles before the "ckhand"
+# bundle. A search for "backslide" must consider all the bundles after the
+# "ckhand".
+
+init bundle-size=4
+----
+size=1:
+0: prefixes:       prefixbytes(4): 0 keys
+1: suffixes:       bytes: 0 rows set; 0 bytes in data
+2: trailers:       uint64: 0 rows
+3: prefix changed: bitmap
+4: values:         bytes: 0 rows set; 0 bytes in data
+5: is-value-ext:   bitmap
+
+write
+baba#1,SET:v
+babble#1,SET:v
+babblement#1,SET:v
+babbler#1,SET:v
+babblesome#1,SET:v
+babbling#1,SET:v
+babblingly#1,SET:v
+babblish#1,SET:v
+babblishly#1,SET:v
+babbly#1,SET:v
+babe#1,SET:v
+baboon#1,SET:v
+baboonery#1,SET:v
+baboonish#1,SET:v
+babushka#1,SET:v
+baby#1,SET:v
+babydom#1,SET:v
+babyhood#1,SET:v
+babyhouse#1,SET:v
+babyish#1,SET:v
+babyishly#1,SET:v
+babyishness#1,SET:v
+babyism#1,SET:v
+babylike#1,SET:v
+bacchanal#1,SET:v
+bacchanalian#1,SET:v
+bacchanalianism#1,SET:v
+bacchanalianly#1,SET:v
+bacchanalism#1,SET:v
+bacchanalization#1,SET:v
+bacchanalize#1,SET:v
+back#1,SET:v
+backache#1,SET:v
+backbone#1,SET:v
+backboned#1,SET:v
+backbreaking#1,SET:v
+backcourt#1,SET:v
+backcross#1,SET:v
+backdoor#1,SET:v
+backdown#1,SET:v
+backdrop#1,SET:v
+backed#1,SET:v
+backfield#1,SET:v
+backfill#1,SET:v
+backfire#1,SET:v
+backfiring#1,SET:v
+backgammon#1,SET:v
+background#1,SET:v
+backhand#1,SET:v
+backhanded#1,SET:v
+backhandedly#1,SET:v
+backhandedness#1,SET:v
+backpedal#1,SET:v
+backslap#1,SET:v
+backslide#1,SET:v
+backspace#1,SET:v
+backstage#1,SET:v
+backstop#1,SET:v
+backstroke#1,SET:v
+backtrack#1,SET:v
+backup#1,SET:v
+backward#1,SET:v
+backwards#1,SET:v
+backwash#1,SET:v
+backwoods#1,SET:v
+bacteria#1,SET:v
+----
+size=761:
+0: prefixes:       prefixbytes(4): 66 keys
+1: suffixes:       bytes: 66 rows set; 0 bytes in data
+2: trailers:       uint64: 66 rows
+3: prefix changed: bitmap
+4: values:         bytes: 66 rows set; 66 bytes in data
+5: is-value-ext:   bitmap
+
+finish
+----
+# data block header
+000-004: x 10000000                                                         # maximum key length: 16
+# columnar block header
+004-005: x 01                                                               # version 1
+005-007: x 0600                                                             # 6 columns
+007-011: x 42000000                                                         # 66 rows
+# column 0
+011-012: b 00000111                                                         # prefixbytes
+012-016: x 29000000                                                         # page start 41
+# column 1
+016-017: b 00000110                                                         # bytes
+017-021: x 29020000                                                         # page start 553
+# column 2
+021-022: b 00000101                                                         # uint64
+022-026: x 2e020000                                                         # page start 558
+# column 3
+026-027: b 00000001                                                         # bool
+027-031: x 37020000                                                         # page start 567
+# column 4
+031-032: b 00000110                                                         # bytes
+032-036: x 50020000                                                         # page start 592
+# column 5
+036-037: b 00000001                                                         # bool
+037-041: x da020000                                                         # page start 730
+# data for column 0
+# PrefixBytes
+041-042: x 02                                                               # bundleSize: 4
+# Offsets table
+042-043: x 03                                                               # delta encoding: delta16
+043-047: x 00000000                                                         # 32-bit constant: 0
+# padding
+047-048: x 00                                                               # aligning to 16-bit boundary
+048-050: x 0200                                                             # data[0] = 2 [218 overall]
+050-052: x 0300                                                             # data[1] = 3 [219 overall]
+052-054: x 0400                                                             # data[2] = 4 [220 overall]
+054-056: x 0700                                                             # data[3] = 7 [223 overall]
+056-058: x 0e00                                                             # data[4] = 14 [230 overall]
+058-060: x 1200                                                             # data[5] = 18 [234 overall]
+060-062: x 1500                                                             # data[6] = 21 [237 overall]
+062-064: x 1a00                                                             # data[7] = 26 [242 overall]
+064-066: x 1d00                                                             # data[8] = 29 [245 overall]
+066-068: x 2200                                                             # data[9] = 34 [250 overall]
+068-070: x 2500                                                             # data[10] = 37 [253 overall]
+070-072: x 2600                                                             # data[11] = 38 [254 overall]
+072-074: x 2d00                                                             # data[12] = 45 [261 overall]
+074-076: x 3000                                                             # data[13] = 48 [264 overall]
+076-078: x 3100                                                             # data[14] = 49 [265 overall]
+078-080: x 3400                                                             # data[15] = 52 [268 overall]
+080-082: x 3500                                                             # data[16] = 53 [269 overall]
+082-084: x 3b00                                                             # data[17] = 59 [275 overall]
+084-086: x 4100                                                             # data[18] = 65 [281 overall]
+086-088: x 4600                                                             # data[19] = 70 [286 overall]
+088-090: x 4700                                                             # data[20] = 71 [287 overall]
+090-092: x 4900                                                             # data[21] = 73 [289 overall]
+092-094: x 4c00                                                             # data[22] = 76 [292 overall]
+094-096: x 5000                                                             # data[23] = 80 [296 overall]
+096-098: x 5500                                                             # data[24] = 85 [301 overall]
+098-100: x 5800                                                             # data[25] = 88 [304 overall]
+100-102: x 5a00                                                             # data[26] = 90 [306 overall]
+102-104: x 5f00                                                             # data[27] = 95 [311 overall]
+104-106: x 6600                                                             # data[28] = 102 [318 overall]
+106-108: x 6900                                                             # data[29] = 105 [321 overall]
+108-110: x 6d00                                                             # data[30] = 109 [325 overall]
+110-112: x 7400                                                             # data[31] = 116 [332 overall]
+112-114: x 7400                                                             # data[32] = 116 [332 overall]
+114-116: x 7700                                                             # data[33] = 119 [335 overall]
+116-118: x 7d00                                                             # data[34] = 125 [341 overall]
+118-120: x 8200                                                             # data[35] = 130 [346 overall]
+120-122: x 8300                                                             # data[36] = 131 [347 overall]
+122-124: x 8c00                                                             # data[37] = 140 [356 overall]
+124-126: x 9900                                                             # data[38] = 153 [369 overall]
+126-128: x a200                                                             # data[39] = 162 [378 overall]
+128-130: x a300                                                             # data[40] = 163 [379 overall]
+130-132: x a500                                                             # data[41] = 165 [381 overall]
+132-134: x a900                                                             # data[42] = 169 [385 overall]
+134-136: x ad00                                                             # data[43] = 173 [389 overall]
+136-138: x b200                                                             # data[44] = 178 [394 overall]
+138-140: x ba00                                                             # data[45] = 186 [402 overall]
+140-142: x bc00                                                             # data[46] = 188 [404 overall]
+142-144: x c100                                                             # data[47] = 193 [409 overall]
+144-146: x c600                                                             # data[48] = 198 [414 overall]
+146-148: x ca00                                                             # data[49] = 202 [418 overall]
+148-150: x ce00                                                             # data[50] = 206 [422 overall]
+150-152: x d000                                                             # data[51] = 208 [424 overall]
+152-154: x d400                                                             # data[52] = 212 [428 overall]
+154-156: x d600                                                             # data[53] = 214 [430 overall]
+156-158: x db00                                                             # data[54] = 219 [435 overall]
+158-160: x df00                                                             # data[55] = 223 [439 overall]
+160-162: x e100                                                             # data[56] = 225 [441 overall]
+162-164: x e500                                                             # data[57] = 229 [445 overall]
+164-166: x eb00                                                             # data[58] = 235 [451 overall]
+166-168: x f100                                                             # data[59] = 241 [457 overall]
+168-170: x f700                                                             # data[60] = 247 [463 overall]
+170-172: x fd00                                                             # data[61] = 253 [469 overall]
+172-174: x fd00                                                             # data[62] = 253 [469 overall]
+174-176: x ff00                                                             # data[63] = 255 [471 overall]
+176-178: x 0301                                                             # data[64] = 259 [475 overall]
+178-180: x 0901                                                             # data[65] = 265 [481 overall]
+180-182: x 0b01                                                             # data[66] = 267 [483 overall]
+182-184: x 1001                                                             # data[67] = 272 [488 overall]
+184-186: x 1401                                                             # data[68] = 276 [492 overall]
+186-188: x 1901                                                             # data[69] = 281 [497 overall]
+188-190: x 1e01                                                             # data[70] = 286 [502 overall]
+190-192: x 2001                                                             # data[71] = 288 [504 overall]
+192-194: x 2501                                                             # data[72] = 293 [509 overall]
+194-196: x 2901                                                             # data[73] = 297 [513 overall]
+196-198: x 2f01                                                             # data[74] = 303 [519 overall]
+198-200: x 3401                                                             # data[75] = 308 [524 overall]
+200-202: x 3601                                                             # data[76] = 310 [526 overall]
+202-204: x 3801                                                             # data[77] = 312 [528 overall]
+204-206: x 3c01                                                             # data[78] = 316 [532 overall]
+206-208: x 4101                                                             # data[79] = 321 [537 overall]
+208-210: x 4501                                                             # data[80] = 325 [541 overall]
+210-212: x 4601                                                             # data[81] = 326 [542 overall]
+212-214: x 4c01                                                             # data[82] = 332 [548 overall]
+214-216: x 5101                                                             # data[83] = 337 [553 overall]
+# Data
+216-218: x 6261                                                             # data[00]: ba (block prefix)
+218-219: x 62                                                               # data[01]: ..b (bundle prefix)
+219-220: x 61                                                               # data[02]: ...a
+220-223: x 626c65                                                           # data[03]: ...ble
+223-230: x 626c656d656e74                                                   # data[04]: ...blement
+230-234: x 626c6572                                                         # data[05]: ...bler
+234-237: x 62626c                                                           # data[06]: ..bbl (bundle prefix)
+237-242: x 65736f6d65                                                       # data[07]: .....esome
+242-245: x 696e67                                                           # data[08]: .....ing
+245-250: x 696e676c79                                                       # data[09]: .....ingly
+250-253: x 697368                                                           # data[10]: .....ish
+253-254: x 62                                                               # data[11]: ..b (bundle prefix)
+254-261: x 626c6973686c79                                                   # data[12]: ...blishly
+261-264: x 626c79                                                           # data[13]: ...bly
+264-265: x 65                                                               # data[14]: ...e
+265-268: x 6f6f6e                                                           # data[15]: ...oon
+268-269: x 62                                                               # data[16]: ..b (bundle prefix)
+269-275: x 6f6f6e657279                                                     # data[17]: ...oonery
+275-281: x 6f6f6e697368                                                     # data[18]: ...oonish
+281-286: x 7573686b61                                                       # data[19]: ...ushka
+286-287: x 79                                                               # data[20]: ...y
+287-289: x 6279                                                             # data[21]: ..by (bundle prefix)
+289-292: x 646f6d                                                           # data[22]: ....dom
+292-296: x 686f6f64                                                         # data[23]: ....hood
+296-301: x 686f757365                                                       # data[24]: ....house
+301-304: x 697368                                                           # data[25]: ....ish
+304-306: x 6279                                                             # data[26]: ..by (bundle prefix)
+306-311: x 6973686c79                                                       # data[27]: ....ishly
+311-318: x 6973686e657373                                                   # data[28]: ....ishness
+318-321: x 69736d                                                           # data[29]: ....ism
+321-325: x 6c696b65                                                         # data[30]: ....like
+325-332: x 636368616e616c                                                   # data[31]: ..cchanal (bundle prefix)
+332-332: x                                                                  # data[32]: .........
+332-335: x 69616e                                                           # data[33]: .........ian
+335-341: x 69616e69736d                                                     # data[34]: .........ianism
+341-346: x 69616e6c79                                                       # data[35]: .........ianly
+346-347: x 63                                                               # data[36]: ..c (bundle prefix)
+347-356: x 6368616e616c69736d                                               # data[37]: ...chanalism
+356-366: x 6368616e616c697a6174                                             # data[38]: ...chanalization
+366-369: x 696f6e                                                           # (continued...)
+369-378: x 6368616e616c697a65                                               # data[39]: ...chanalize
+378-379: x 6b                                                               # data[40]: ...k
+379-381: x 636b                                                             # data[41]: ..ck (bundle prefix)
+381-385: x 61636865                                                         # data[42]: ....ache
+385-389: x 626f6e65                                                         # data[43]: ....bone
+389-394: x 626f6e6564                                                       # data[44]: ....boned
+394-402: x 627265616b696e67                                                 # data[45]: ....breaking
+402-404: x 636b                                                             # data[46]: ..ck (bundle prefix)
+404-409: x 636f757274                                                       # data[47]: ....court
+409-414: x 63726f7373                                                       # data[48]: ....cross
+414-418: x 646f6f72                                                         # data[49]: ....door
+418-422: x 646f776e                                                         # data[50]: ....down
+422-424: x 636b                                                             # data[51]: ..ck (bundle prefix)
+424-428: x 64726f70                                                         # data[52]: ....drop
+428-430: x 6564                                                             # data[53]: ....ed
+430-435: x 6669656c64                                                       # data[54]: ....field
+435-439: x 66696c6c                                                         # data[55]: ....fill
+439-441: x 636b                                                             # data[56]: ..ck (bundle prefix)
+441-445: x 66697265                                                         # data[57]: ....fire
+445-451: x 666972696e67                                                     # data[58]: ....firing
+451-457: x 67616d6d6f6e                                                     # data[59]: ....gammon
+457-463: x 67726f756e64                                                     # data[60]: ....ground
+463-469: x 636b68616e64                                                     # data[61]: ..ckhand (bundle prefix)
+469-469: x                                                                  # data[62]: ........
+469-471: x 6564                                                             # data[63]: ........ed
+471-475: x 65646c79                                                         # data[64]: ........edly
+475-481: x 65646e657373                                                     # data[65]: ........edness
+481-483: x 636b                                                             # data[66]: ..ck (bundle prefix)
+483-488: x 706564616c                                                       # data[67]: ....pedal
+488-492: x 736c6170                                                         # data[68]: ....slap
+492-497: x 736c696465                                                       # data[69]: ....slide
+497-502: x 7370616365                                                       # data[70]: ....space
+502-504: x 636b                                                             # data[71]: ..ck (bundle prefix)
+504-509: x 7374616765                                                       # data[72]: ....stage
+509-513: x 73746f70                                                         # data[73]: ....stop
+513-519: x 7374726f6b65                                                     # data[74]: ....stroke
+519-524: x 747261636b                                                       # data[75]: ....track
+524-526: x 636b                                                             # data[76]: ..ck (bundle prefix)
+526-528: x 7570                                                             # data[77]: ....up
+528-532: x 77617264                                                         # data[78]: ....ward
+532-537: x 7761726473                                                       # data[79]: ....wards
+537-541: x 77617368                                                         # data[80]: ....wash
+541-542: x 63                                                               # data[81]: ..c (bundle prefix)
+542-548: x 6b776f6f6473                                                     # data[82]: ...kwoods
+548-553: x 7465726961                                                       # data[83]: ...teria
+# data for column 1
+# rawbytes
+# offsets table
+553-554: x 01                                                               # delta encoding: const
+554-558: x 00000000                                                         # 32-bit constant: 0
+# data
+558-558: x                                                                  # data[0]:
+558-558: x                                                                  # data[1]:
+558-558: x                                                                  # data[2]:
+558-558: x                                                                  # data[3]:
+558-558: x                                                                  # data[4]:
+558-558: x                                                                  # data[5]:
+558-558: x                                                                  # data[6]:
+558-558: x                                                                  # data[7]:
+558-558: x                                                                  # data[8]:
+558-558: x                                                                  # data[9]:
+558-558: x                                                                  # data[10]:
+558-558: x                                                                  # data[11]:
+558-558: x                                                                  # data[12]:
+558-558: x                                                                  # data[13]:
+558-558: x                                                                  # data[14]:
+558-558: x                                                                  # data[15]:
+558-558: x                                                                  # data[16]:
+558-558: x                                                                  # data[17]:
+558-558: x                                                                  # data[18]:
+558-558: x                                                                  # data[19]:
+558-558: x                                                                  # data[20]:
+558-558: x                                                                  # data[21]:
+558-558: x                                                                  # data[22]:
+558-558: x                                                                  # data[23]:
+558-558: x                                                                  # data[24]:
+558-558: x                                                                  # data[25]:
+558-558: x                                                                  # data[26]:
+558-558: x                                                                  # data[27]:
+558-558: x                                                                  # data[28]:
+558-558: x                                                                  # data[29]:
+558-558: x                                                                  # data[30]:
+558-558: x                                                                  # data[31]:
+558-558: x                                                                  # data[32]:
+558-558: x                                                                  # data[33]:
+558-558: x                                                                  # data[34]:
+558-558: x                                                                  # data[35]:
+558-558: x                                                                  # data[36]:
+558-558: x                                                                  # data[37]:
+558-558: x                                                                  # data[38]:
+558-558: x                                                                  # data[39]:
+558-558: x                                                                  # data[40]:
+558-558: x                                                                  # data[41]:
+558-558: x                                                                  # data[42]:
+558-558: x                                                                  # data[43]:
+558-558: x                                                                  # data[44]:
+558-558: x                                                                  # data[45]:
+558-558: x                                                                  # data[46]:
+558-558: x                                                                  # data[47]:
+558-558: x                                                                  # data[48]:
+558-558: x                                                                  # data[49]:
+558-558: x                                                                  # data[50]:
+558-558: x                                                                  # data[51]:
+558-558: x                                                                  # data[52]:
+558-558: x                                                                  # data[53]:
+558-558: x                                                                  # data[54]:
+558-558: x                                                                  # data[55]:
+558-558: x                                                                  # data[56]:
+558-558: x                                                                  # data[57]:
+558-558: x                                                                  # data[58]:
+558-558: x                                                                  # data[59]:
+558-558: x                                                                  # data[60]:
+558-558: x                                                                  # data[61]:
+558-558: x                                                                  # data[62]:
+558-558: x                                                                  # data[63]:
+558-558: x                                                                  # data[64]:
+558-558: x                                                                  # data[65]:
+# data for column 2
+558-559: x 01                                                               # delta encoding: const
+559-567: x 0101000000000000                                                 # 64-bit constant: 257
+# data for column 3
+567-568: x 00                                                               # padding to align to 64-bit boundary
+568-576: b 1111111111111111111111111111111111111111111111111111111111111111 # bitmap word 0
+576-584: b 0000001100000000000000000000000000000000000000000000000000000000 # bitmap word 1
+584-592: b 0000001100000000000000000000000000000000000000000000000000000000 # bitmap summary word 0-63
+# data for column 4
+# rawbytes
+# offsets table
+592-593: x 02                                                               # delta encoding: delta8
+593-597: x 00000000                                                         # 32-bit constant: 0
+597-598: x 00                                                               # data[0] = 0 [664 overall]
+598-599: x 01                                                               # data[1] = 1 [665 overall]
+599-600: x 02                                                               # data[2] = 2 [666 overall]
+600-601: x 03                                                               # data[3] = 3 [667 overall]
+601-602: x 04                                                               # data[4] = 4 [668 overall]
+602-603: x 05                                                               # data[5] = 5 [669 overall]
+603-604: x 06                                                               # data[6] = 6 [670 overall]
+604-605: x 07                                                               # data[7] = 7 [671 overall]
+605-606: x 08                                                               # data[8] = 8 [672 overall]
+606-607: x 09                                                               # data[9] = 9 [673 overall]
+607-608: x 0a                                                               # data[10] = 10 [674 overall]
+608-609: x 0b                                                               # data[11] = 11 [675 overall]
+609-610: x 0c                                                               # data[12] = 12 [676 overall]
+610-611: x 0d                                                               # data[13] = 13 [677 overall]
+611-612: x 0e                                                               # data[14] = 14 [678 overall]
+612-613: x 0f                                                               # data[15] = 15 [679 overall]
+613-614: x 10                                                               # data[16] = 16 [680 overall]
+614-615: x 11                                                               # data[17] = 17 [681 overall]
+615-616: x 12                                                               # data[18] = 18 [682 overall]
+616-617: x 13                                                               # data[19] = 19 [683 overall]
+617-618: x 14                                                               # data[20] = 20 [684 overall]
+618-619: x 15                                                               # data[21] = 21 [685 overall]
+619-620: x 16                                                               # data[22] = 22 [686 overall]
+620-621: x 17                                                               # data[23] = 23 [687 overall]
+621-622: x 18                                                               # data[24] = 24 [688 overall]
+622-623: x 19                                                               # data[25] = 25 [689 overall]
+623-624: x 1a                                                               # data[26] = 26 [690 overall]
+624-625: x 1b                                                               # data[27] = 27 [691 overall]
+625-626: x 1c                                                               # data[28] = 28 [692 overall]
+626-627: x 1d                                                               # data[29] = 29 [693 overall]
+627-628: x 1e                                                               # data[30] = 30 [694 overall]
+628-629: x 1f                                                               # data[31] = 31 [695 overall]
+629-630: x 20                                                               # data[32] = 32 [696 overall]
+630-631: x 21                                                               # data[33] = 33 [697 overall]
+631-632: x 22                                                               # data[34] = 34 [698 overall]
+632-633: x 23                                                               # data[35] = 35 [699 overall]
+633-634: x 24                                                               # data[36] = 36 [700 overall]
+634-635: x 25                                                               # data[37] = 37 [701 overall]
+635-636: x 26                                                               # data[38] = 38 [702 overall]
+636-637: x 27                                                               # data[39] = 39 [703 overall]
+637-638: x 28                                                               # data[40] = 40 [704 overall]
+638-639: x 29                                                               # data[41] = 41 [705 overall]
+639-640: x 2a                                                               # data[42] = 42 [706 overall]
+640-641: x 2b                                                               # data[43] = 43 [707 overall]
+641-642: x 2c                                                               # data[44] = 44 [708 overall]
+642-643: x 2d                                                               # data[45] = 45 [709 overall]
+643-644: x 2e                                                               # data[46] = 46 [710 overall]
+644-645: x 2f                                                               # data[47] = 47 [711 overall]
+645-646: x 30                                                               # data[48] = 48 [712 overall]
+646-647: x 31                                                               # data[49] = 49 [713 overall]
+647-648: x 32                                                               # data[50] = 50 [714 overall]
+648-649: x 33                                                               # data[51] = 51 [715 overall]
+649-650: x 34                                                               # data[52] = 52 [716 overall]
+650-651: x 35                                                               # data[53] = 53 [717 overall]
+651-652: x 36                                                               # data[54] = 54 [718 overall]
+652-653: x 37                                                               # data[55] = 55 [719 overall]
+653-654: x 38                                                               # data[56] = 56 [720 overall]
+654-655: x 39                                                               # data[57] = 57 [721 overall]
+655-656: x 3a                                                               # data[58] = 58 [722 overall]
+656-657: x 3b                                                               # data[59] = 59 [723 overall]
+657-658: x 3c                                                               # data[60] = 60 [724 overall]
+658-659: x 3d                                                               # data[61] = 61 [725 overall]
+659-660: x 3e                                                               # data[62] = 62 [726 overall]
+660-661: x 3f                                                               # data[63] = 63 [727 overall]
+661-662: x 40                                                               # data[64] = 64 [728 overall]
+662-663: x 41                                                               # data[65] = 65 [729 overall]
+663-664: x 42                                                               # data[66] = 66 [730 overall]
+# data
+664-665: x 76                                                               # data[0]: v
+665-666: x 76                                                               # data[1]: v
+666-667: x 76                                                               # data[2]: v
+667-668: x 76                                                               # data[3]: v
+668-669: x 76                                                               # data[4]: v
+669-670: x 76                                                               # data[5]: v
+670-671: x 76                                                               # data[6]: v
+671-672: x 76                                                               # data[7]: v
+672-673: x 76                                                               # data[8]: v
+673-674: x 76                                                               # data[9]: v
+674-675: x 76                                                               # data[10]: v
+675-676: x 76                                                               # data[11]: v
+676-677: x 76                                                               # data[12]: v
+677-678: x 76                                                               # data[13]: v
+678-679: x 76                                                               # data[14]: v
+679-680: x 76                                                               # data[15]: v
+680-681: x 76                                                               # data[16]: v
+681-682: x 76                                                               # data[17]: v
+682-683: x 76                                                               # data[18]: v
+683-684: x 76                                                               # data[19]: v
+684-685: x 76                                                               # data[20]: v
+685-686: x 76                                                               # data[21]: v
+686-687: x 76                                                               # data[22]: v
+687-688: x 76                                                               # data[23]: v
+688-689: x 76                                                               # data[24]: v
+689-690: x 76                                                               # data[25]: v
+690-691: x 76                                                               # data[26]: v
+691-692: x 76                                                               # data[27]: v
+692-693: x 76                                                               # data[28]: v
+693-694: x 76                                                               # data[29]: v
+694-695: x 76                                                               # data[30]: v
+695-696: x 76                                                               # data[31]: v
+696-697: x 76                                                               # data[32]: v
+697-698: x 76                                                               # data[33]: v
+698-699: x 76                                                               # data[34]: v
+699-700: x 76                                                               # data[35]: v
+700-701: x 76                                                               # data[36]: v
+701-702: x 76                                                               # data[37]: v
+702-703: x 76                                                               # data[38]: v
+703-704: x 76                                                               # data[39]: v
+704-705: x 76                                                               # data[40]: v
+705-706: x 76                                                               # data[41]: v
+706-707: x 76                                                               # data[42]: v
+707-708: x 76                                                               # data[43]: v
+708-709: x 76                                                               # data[44]: v
+709-710: x 76                                                               # data[45]: v
+710-711: x 76                                                               # data[46]: v
+711-712: x 76                                                               # data[47]: v
+712-713: x 76                                                               # data[48]: v
+713-714: x 76                                                               # data[49]: v
+714-715: x 76                                                               # data[50]: v
+715-716: x 76                                                               # data[51]: v
+716-717: x 76                                                               # data[52]: v
+717-718: x 76                                                               # data[53]: v
+718-719: x 76                                                               # data[54]: v
+719-720: x 76                                                               # data[55]: v
+720-721: x 76                                                               # data[56]: v
+721-722: x 76                                                               # data[57]: v
+722-723: x 76                                                               # data[58]: v
+723-724: x 76                                                               # data[59]: v
+724-725: x 76                                                               # data[60]: v
+725-726: x 76                                                               # data[61]: v
+726-727: x 76                                                               # data[62]: v
+727-728: x 76                                                               # data[63]: v
+728-729: x 76                                                               # data[64]: v
+729-730: x 76                                                               # data[65]: v
+# data for column 5
+730-736: x 000000000000                                                     # padding to align to 64-bit boundary
+736-744: b 0000000000000000000000000000000000000000000000000000000000000000 # bitmap word 0
+744-752: b 0000000000000000000000000000000000000000000000000000000000000000 # bitmap word 1
+752-760: b 0000000000000000000000000000000000000000000000000000000000000000 # bitmap summary word 0-63
+
+iter
+seek-ge backache
+seek-ge backslide
+seek-ge backslid
+seek-ge backhanded
+seek-ge backhande
+seek-ge bac
+seek-ge bacl
+seek-ge bacu
+----
+backache:v
+backslide:v
+backslide:v
+backhanded:v
+backhanded:v
+bacchanal:v
+bacteria:v
+.
diff --git a/sstable/colblk/testdata/data_block/external_value b/sstable/colblk/testdata/data_block/external_value
new file mode 100644
index 00000000..fe9b689e
--- /dev/null
+++ b/sstable/colblk/testdata/data_block/external_value
@@ -0,0 +1,343 @@
+init
+----
+size=1:
+0: prefixes:       prefixbytes(16): 0 keys
+1: suffixes:       bytes: 0 rows set; 0 bytes in data
+2: trailers:       uint64: 0 rows
+3: prefix changed: bitmap
+4: values:         bytes: 0 rows set; 0 bytes in data
+5: is-value-ext:   bitmap
+
+write
+blockprefix_apple@98#0,SET:apple98
+blockprefix_apple@52#0,SET:valueHandle-apple52
+blockprefix_apple@23#0,SET:valueHandle-apple23
+blockprefix_apple@11#0,SETWITHDEL:valueHandle-apple11
+blockprefix_banana@94#245,SETWITHDEL:banana94
+blockprefix_banana@93#244,DEL:
+blockprefix_banana@93#221,SETWITHDEL:valueHandle-banana93
+blockprefix_banana@72#0,SETWITHDEL:valueHandle-banana72
+blockprefix_banana@9#0,SET:valueHandle-banana9
+blockprefix_banana@1#0,SET:valueHandle-banana1
+blockprefix_coconut#0,SET:coconut
+blockprefix_coconut@92#0,SET:valueHandle-coconut92
+blockprefix_coconut@35#0,SET:valueHandle-coconut35
+blockprefix_coconut@22#0,SET:valueHandle-coconut22
+blockprefix_coconut@21#0,SET:valueHandle-coconut21
+blockprefix_coconut@1#0,SET:valueHandle-coconut1
+blockprefix_guava@99#0,SET:valueHandle-guava99
+blockprefix_kiwi@99#0,SET:valueHandle-kiwi99
+blockprefix_kiwi@98#0,SET:valueHandle-kiwi98
+blockprefix_lemon@92#0,DEL:
+----
+size=665:
+0: prefixes:       prefixbytes(16): 20 keys
+1: suffixes:       bytes: 20 rows set; 54 bytes in data
+2: trailers:       uint64: 20 rows
+3: prefix changed: bitmap
+4: values:         bytes: 20 rows set; 331 bytes in data
+5: is-value-ext:   bitmap
+
+finish
+----
+# data block header
+000-004: x 16000000                                                         # maximum key length: 22
+# columnar block header
+004-005: x 01                                                               # version 1
+005-007: x 0600                                                             # 6 columns
+007-011: x 14000000                                                         # 20 rows
+# column 0
+011-012: b 00000111                                                         # prefixbytes
+012-016: x 29000000                                                         # page start 41
+# column 1
+016-017: b 00000110                                                         # bytes
+017-021: x 72000000                                                         # page start 114
+# column 2
+021-022: b 00000101                                                         # uint64
+022-026: x c2000000                                                         # page start 194
+# column 3
+026-027: b 00000001                                                         # bool
+027-031: x f4000000                                                         # page start 244
+# column 4
+031-032: b 00000110                                                         # bytes
+032-036: x 08010000                                                         # page start 264
+# column 5
+036-037: b 00000001                                                         # bool
+037-041: x 83020000                                                         # page start 643
+# data for column 0
+# PrefixBytes
+041-042: x 04                                                               # bundleSize: 16
+# Offsets table
+042-043: x 02                                                               # delta encoding: delta8
+043-047: x 00000000                                                         # 32-bit constant: 0
+047-048: x 0c                                                               # data[0] = 12 [82 overall]
+048-049: x 0c                                                               # data[1] = 12 [82 overall]
+049-050: x 11                                                               # data[2] = 17 [87 overall]
+050-051: x 11                                                               # data[3] = 17 [87 overall]
+051-052: x 11                                                               # data[4] = 17 [87 overall]
+052-053: x 11                                                               # data[5] = 17 [87 overall]
+053-054: x 17                                                               # data[6] = 23 [93 overall]
+054-055: x 17                                                               # data[7] = 23 [93 overall]
+055-056: x 17                                                               # data[8] = 23 [93 overall]
+056-057: x 17                                                               # data[9] = 23 [93 overall]
+057-058: x 17                                                               # data[10] = 23 [93 overall]
+058-059: x 17                                                               # data[11] = 23 [93 overall]
+059-060: x 1e                                                               # data[12] = 30 [100 overall]
+060-061: x 1e                                                               # data[13] = 30 [100 overall]
+061-062: x 1e                                                               # data[14] = 30 [100 overall]
+062-063: x 1e                                                               # data[15] = 30 [100 overall]
+063-064: x 1e                                                               # data[16] = 30 [100 overall]
+064-065: x 1e                                                               # data[17] = 30 [100 overall]
+065-066: x 1e                                                               # data[18] = 30 [100 overall]
+066-067: x 23                                                               # data[19] = 35 [105 overall]
+067-068: x 27                                                               # data[20] = 39 [109 overall]
+068-069: x 27                                                               # data[21] = 39 [109 overall]
+069-070: x 2c                                                               # data[22] = 44 [114 overall]
+# Data
+070-080: x 626c6f636b7072656669                                             # data[00]: blockprefix_ (block prefix)
+080-082: x 785f                                                             # (continued...)
+082-082: x                                                                  # data[01]: ............ (bundle prefix)
+082-087: x 6170706c65                                                       # data[02]: ............apple
+087-087: x                                                                  # data[03]: .................
+087-087: x                                                                  # data[04]: .................
+087-087: x                                                                  # data[05]: .................
+087-093: x 62616e616e61                                                     # data[06]: ............banana
+093-093: x                                                                  # data[07]: ..................
+093-093: x                                                                  # data[08]: ..................
+093-093: x                                                                  # data[09]: ..................
+093-093: x                                                                  # data[10]: ..................
+093-093: x                                                                  # data[11]: ..................
+093-100: x 636f636f6e7574                                                   # data[12]: ............coconut
+100-100: x                                                                  # data[13]: ...................
+100-100: x                                                                  # data[14]: ...................
+100-100: x                                                                  # data[15]: ...................
+100-100: x                                                                  # data[16]: ...................
+100-100: x                                                                  # data[17]: ...................
+100-100: x                                                                  # data[18]: ............ (bundle prefix)
+100-105: x 6775617661                                                       # data[19]: ............guava
+105-109: x 6b697769                                                         # data[20]: ............kiwi
+109-109: x                                                                  # data[21]: ................
+109-114: x 6c656d6f6e                                                       # data[22]: ............lemon
+# data for column 1
+# rawbytes
+# offsets table
+114-115: x 02                                                               # delta encoding: delta8
+115-119: x 00000000                                                         # 32-bit constant: 0
+119-120: x 00                                                               # data[0] = 0 [140 overall]
+120-121: x 03                                                               # data[1] = 3 [143 overall]
+121-122: x 06                                                               # data[2] = 6 [146 overall]
+122-123: x 09                                                               # data[3] = 9 [149 overall]
+123-124: x 0c                                                               # data[4] = 12 [152 overall]
+124-125: x 0f                                                               # data[5] = 15 [155 overall]
+125-126: x 12                                                               # data[6] = 18 [158 overall]
+126-127: x 15                                                               # data[7] = 21 [161 overall]
+127-128: x 18                                                               # data[8] = 24 [164 overall]
+128-129: x 1a                                                               # data[9] = 26 [166 overall]
+129-130: x 1c                                                               # data[10] = 28 [168 overall]
+130-131: x 1c                                                               # data[11] = 28 [168 overall]
+131-132: x 1f                                                               # data[12] = 31 [171 overall]
+132-133: x 22                                                               # data[13] = 34 [174 overall]
+133-134: x 25                                                               # data[14] = 37 [177 overall]
+134-135: x 28                                                               # data[15] = 40 [180 overall]
+135-136: x 2a                                                               # data[16] = 42 [182 overall]
+136-137: x 2d                                                               # data[17] = 45 [185 overall]
+137-138: x 30                                                               # data[18] = 48 [188 overall]
+138-139: x 33                                                               # data[19] = 51 [191 overall]
+139-140: x 36                                                               # data[20] = 54 [194 overall]
+# data
+140-143: x 403938                                                           # data[0]: @98
+143-146: x 403532                                                           # data[1]: @52
+146-149: x 403233                                                           # data[2]: @23
+149-152: x 403131                                                           # data[3]: @11
+152-155: x 403934                                                           # data[4]: @94
+155-158: x 403933                                                           # data[5]: @93
+158-161: x 403933                                                           # data[6]: @93
+161-164: x 403732                                                           # data[7]: @72
+164-166: x 4039                                                             # data[8]: @9
+166-168: x 4031                                                             # data[9]: @1
+168-168: x                                                                  # data[10]:
+168-171: x 403932                                                           # data[11]: @92
+171-174: x 403335                                                           # data[12]: @35
+174-177: x 403232                                                           # data[13]: @22
+177-180: x 403231                                                           # data[14]: @21
+180-182: x 4031                                                             # data[15]: @1
+182-185: x 403939                                                           # data[16]: @99
+185-188: x 403939                                                           # data[17]: @99
+188-191: x 403938                                                           # data[18]: @98
+191-194: x 403932                                                           # data[19]: @92
+# data for column 2
+194-195: x 03                                                               # delta encoding: delta16
+195-203: x 0000000000000000                                                 # 64-bit constant: 0
+# padding
+203-204: x 00                                                               # aligning to 16-bit boundary
+204-206: x 0100                                                             # data[0] = 1
+206-208: x 0100                                                             # data[1] = 1
+208-210: x 0100                                                             # data[2] = 1
+210-212: x 1200                                                             # data[3] = 18
+212-214: x 12f5                                                             # data[4] = 62738
+214-216: x 00f4                                                             # data[5] = 62464
+216-218: x 12dd                                                             # data[6] = 56594
+218-220: x 1200                                                             # data[7] = 18
+220-222: x 0100                                                             # data[8] = 1
+222-224: x 0100                                                             # data[9] = 1
+224-226: x 0100                                                             # data[10] = 1
+226-228: x 0100                                                             # data[11] = 1
+228-230: x 0100                                                             # data[12] = 1
+230-232: x 0100                                                             # data[13] = 1
+232-234: x 0100                                                             # data[14] = 1
+234-236: x 0100                                                             # data[15] = 1
+236-238: x 0100                                                             # data[16] = 1
+238-240: x 0100                                                             # data[17] = 1
+240-242: x 0100                                                             # data[18] = 1
+242-244: x 0000                                                             # data[19] = 0
+# data for column 3
+244-248: x 00000000                                                         # padding to align to 64-bit boundary
+248-256: b 0001000100000100000010110000000000000000000000000000000000000000 # bitmap word 0
+256-264: b 0000000100000000000000000000000000000000000000000000000000000000 # bitmap summary word 0-63
+# data for column 4
+# rawbytes
+# offsets table
+264-265: x 03                                                               # delta encoding: delta16
+265-269: x 00000000                                                         # 32-bit constant: 0
+# padding
+269-270: x 00                                                               # aligning to 16-bit boundary
+270-272: x 0000                                                             # data[0] = 0 [312 overall]
+272-274: x 0700                                                             # data[1] = 7 [319 overall]
+274-276: x 1b00                                                             # data[2] = 27 [339 overall]
+276-278: x 2f00                                                             # data[3] = 47 [359 overall]
+278-280: x 4300                                                             # data[4] = 67 [379 overall]
+280-282: x 4b00                                                             # data[5] = 75 [387 overall]
+282-284: x 4b00                                                             # data[6] = 75 [387 overall]
+284-286: x 6000                                                             # data[7] = 96 [408 overall]
+286-288: x 7500                                                             # data[8] = 117 [429 overall]
+288-290: x 8900                                                             # data[9] = 137 [449 overall]
+290-292: x 9d00                                                             # data[10] = 157 [469 overall]
+292-294: x a400                                                             # data[11] = 164 [476 overall]
+294-296: x ba00                                                             # data[12] = 186 [498 overall]
+296-298: x d000                                                             # data[13] = 208 [520 overall]
+298-300: x e600                                                             # data[14] = 230 [542 overall]
+300-302: x fc00                                                             # data[15] = 252 [564 overall]
+302-304: x 1101                                                             # data[16] = 273 [585 overall]
+304-306: x 2501                                                             # data[17] = 293 [605 overall]
+306-308: x 3801                                                             # data[18] = 312 [624 overall]
+308-310: x 4b01                                                             # data[19] = 331 [643 overall]
+310-312: x 4b01                                                             # data[20] = 331 [643 overall]
+# data
+312-319: x 6170706c653938                                                   # data[0]: apple98
+319-329: x a076616c756548616e64                                             # data[1]: "\xa0valueHandle-apple52"
+329-339: x 6c652d6170706c653532                                             # (continued...)
+339-349: x a076616c756548616e64                                             # data[2]: "\xa0valueHandle-apple23"
+349-359: x 6c652d6170706c653233                                             # (continued...)
+359-369: x a076616c756548616e64                                             # data[3]: "\xa0valueHandle-apple11"
+369-379: x 6c652d6170706c653131                                             # (continued...)
+379-387: x 62616e616e613934                                                 # data[4]: banana94
+387-387: x                                                                  # data[5]:
+387-397: x a076616c756548616e64                                             # data[6]: "\xa0valueHandle-banana93"
+397-407: x 6c652d62616e616e6139                                             # (continued...)
+407-408: x 33                                                               # (continued...)
+408-418: x a076616c756548616e64                                             # data[7]: "\xa0valueHandle-banana72"
+418-428: x 6c652d62616e616e6137                                             # (continued...)
+428-429: x 32                                                               # (continued...)
+429-439: x a076616c756548616e64                                             # data[8]: "\xa0valueHandle-banana9"
+439-449: x 6c652d62616e616e6139                                             # (continued...)
+449-459: x a076616c756548616e64                                             # data[9]: "\xa0valueHandle-banana1"
+459-469: x 6c652d62616e616e6131                                             # (continued...)
+469-476: x 636f636f6e7574                                                   # data[10]: coconut
+476-486: x a076616c756548616e64                                             # data[11]: "\xa0valueHandle-coconut92"
+486-496: x 6c652d636f636f6e7574                                             # (continued...)
+496-498: x 3932                                                             # (continued...)
+498-508: x a076616c756548616e64                                             # data[12]: "\xa0valueHandle-coconut35"
+508-518: x 6c652d636f636f6e7574                                             # (continued...)
+518-520: x 3335                                                             # (continued...)
+520-530: x a076616c756548616e64                                             # data[13]: "\xa0valueHandle-coconut22"
+530-540: x 6c652d636f636f6e7574                                             # (continued...)
+540-542: x 3232                                                             # (continued...)
+542-552: x a076616c756548616e64                                             # data[14]: "\xa0valueHandle-coconut21"
+552-562: x 6c652d636f636f6e7574                                             # (continued...)
+562-564: x 3231                                                             # (continued...)
+564-574: x a076616c756548616e64                                             # data[15]: "\xa0valueHandle-coconut1"
+574-584: x 6c652d636f636f6e7574                                             # (continued...)
+584-585: x 31                                                               # (continued...)
+585-595: x 8076616c756548616e64                                             # data[16]: "\x80valueHandle-guava99"
+595-605: x 6c652d67756176613939                                             # (continued...)
+605-615: x 8076616c756548616e64                                             # data[17]: "\x80valueHandle-kiwi99"
+615-624: x 6c652d6b6977693939                                               # (continued...)
+624-634: x a076616c756548616e64                                             # data[18]: "\xa0valueHandle-kiwi98"
+634-643: x 6c652d6b6977693938                                               # (continued...)
+643-643: x                                                                  # data[19]:
+# data for column 5
+643-648: x 0000000000                                                       # padding to align to 64-bit boundary
+648-656: b 1100111011111011000001110000000000000000000000000000000000000000 # bitmap word 0
+656-664: b 0000000100000000000000000000000000000000000000000000000000000000 # bitmap summary word 0-63
+
+# Scan across the block using next.
+iter
+first
+next
+next
+next
+next
+next
+next
+next
+next
+next
+next
+next
+next
+next
+next
+next
+next
+next
+next
+next
+next
+----
+blockprefix_apple@98:apple98
+blockprefix_apple@52:mock external value
+blockprefix_apple@23:mock external value
+blockprefix_apple@11:mock external value
+blockprefix_banana@94:banana94
+blockprefix_banana@93:
+blockprefix_banana@93:mock external value
+blockprefix_banana@72:mock external value
+blockprefix_banana@9:mock external value
+blockprefix_banana@1:mock external value
+blockprefix_coconut:coconut
+blockprefix_coconut@92:mock external value
+blockprefix_coconut@35:mock external value
+blockprefix_coconut@22:mock external value
+blockprefix_coconut@21:mock external value
+blockprefix_coconut@1:mock external value
+blockprefix_guava@99:mock external value
+blockprefix_kiwi@99:mock external value
+blockprefix_kiwi@98:mock external value
+blockprefix_lemon@92:
+.
+
+# Scan across the block using next prefix.
+
+iter
+first
+next-prefix
+next-prefix
+next-prefix
+next-prefix
+next-prefix
+next-prefix
+----
+blockprefix_apple@98:apple98
+blockprefix_banana@94:banana94
+blockprefix_coconut:coconut
+blockprefix_guava@99:mock external value
+blockprefix_kiwi@99:mock external value
+blockprefix_lemon@92:
+.
+
+iter
+seek-ge blockprefix_banana@73
+next-prefix
+----
+blockprefix_banana@72:mock external value
+blockprefix_coconut:coconut
diff --git a/sstable/colblk/testdata/data_block/next_prefix b/sstable/colblk/testdata/data_block/next_prefix
new file mode 100644
index 00000000..006ebf91
--- /dev/null
+++ b/sstable/colblk/testdata/data_block/next_prefix
@@ -0,0 +1,273 @@
+init
+----
+size=1:
+0: prefixes:       prefixbytes(16): 0 keys
+1: suffixes:       bytes: 0 rows set; 0 bytes in data
+2: trailers:       uint64: 0 rows
+3: prefix changed: bitmap
+4: values:         bytes: 0 rows set; 0 bytes in data
+5: is-value-ext:   bitmap
+
+write
+blockprefix_apple@98#0,SET:apple98
+blockprefix_apple@52#0,SET:apple52
+blockprefix_apple@23#0,SET:apple23
+blockprefix_apple@11#0,SETWITHDEL:apple11
+blockprefix_banana@94#245,SETWITHDEL:banana94
+blockprefix_banana@93#244,DEL:
+blockprefix_banana@93#221,SETWITHDEL:banana93
+blockprefix_banana@72#0,SETWITHDEL:banana72
+blockprefix_banana@9#0,SET:banana9
+blockprefix_banana@1#0,SET:banana1
+blockprefix_coconut#0,SET:coconut
+blockprefix_coconut@92#0,SET:coconut92
+blockprefix_coconut@35#0,SET:coconut35
+blockprefix_coconut@22#0,SET:coconut22
+blockprefix_coconut@21#0,SET:coconut21
+blockprefix_coconut@1#0,SET:coconut1
+blockprefix_guava@99#0,SET:guava99
+blockprefix_kiwi@99#0,SET:kiwi99
+blockprefix_kiwi@98#0,SET:kiwi98
+blockprefix_lemon@92#0,DEL:
+----
+size=449:
+0: prefixes:       prefixbytes(16): 20 keys
+1: suffixes:       bytes: 20 rows set; 54 bytes in data
+2: trailers:       uint64: 20 rows
+3: prefix changed: bitmap
+4: values:         bytes: 20 rows set; 136 bytes in data
+5: is-value-ext:   bitmap
+
+finish
+----
+# data block header
+000-004: x 16000000                                                         # maximum key length: 22
+# columnar block header
+004-005: x 01                                                               # version 1
+005-007: x 0600                                                             # 6 columns
+007-011: x 14000000                                                         # 20 rows
+# column 0
+011-012: b 00000111                                                         # prefixbytes
+012-016: x 29000000                                                         # page start 41
+# column 1
+016-017: b 00000110                                                         # bytes
+017-021: x 72000000                                                         # page start 114
+# column 2
+021-022: b 00000101                                                         # uint64
+022-026: x c2000000                                                         # page start 194
+# column 3
+026-027: b 00000001                                                         # bool
+027-031: x f4000000                                                         # page start 244
+# column 4
+031-032: b 00000110                                                         # bytes
+032-036: x 08010000                                                         # page start 264
+# column 5
+036-037: b 00000001                                                         # bool
+037-041: x aa010000                                                         # page start 426
+# data for column 0
+# PrefixBytes
+041-042: x 04                                                               # bundleSize: 16
+# Offsets table
+042-043: x 02                                                               # delta encoding: delta8
+043-047: x 00000000                                                         # 32-bit constant: 0
+047-048: x 0c                                                               # data[0] = 12 [82 overall]
+048-049: x 0c                                                               # data[1] = 12 [82 overall]
+049-050: x 11                                                               # data[2] = 17 [87 overall]
+050-051: x 11                                                               # data[3] = 17 [87 overall]
+051-052: x 11                                                               # data[4] = 17 [87 overall]
+052-053: x 11                                                               # data[5] = 17 [87 overall]
+053-054: x 17                                                               # data[6] = 23 [93 overall]
+054-055: x 17                                                               # data[7] = 23 [93 overall]
+055-056: x 17                                                               # data[8] = 23 [93 overall]
+056-057: x 17                                                               # data[9] = 23 [93 overall]
+057-058: x 17                                                               # data[10] = 23 [93 overall]
+058-059: x 17                                                               # data[11] = 23 [93 overall]
+059-060: x 1e                                                               # data[12] = 30 [100 overall]
+060-061: x 1e                                                               # data[13] = 30 [100 overall]
+061-062: x 1e                                                               # data[14] = 30 [100 overall]
+062-063: x 1e                                                               # data[15] = 30 [100 overall]
+063-064: x 1e                                                               # data[16] = 30 [100 overall]
+064-065: x 1e                                                               # data[17] = 30 [100 overall]
+065-066: x 1e                                                               # data[18] = 30 [100 overall]
+066-067: x 23                                                               # data[19] = 35 [105 overall]
+067-068: x 27                                                               # data[20] = 39 [109 overall]
+068-069: x 27                                                               # data[21] = 39 [109 overall]
+069-070: x 2c                                                               # data[22] = 44 [114 overall]
+# Data
+070-080: x 626c6f636b7072656669                                             # data[00]: blockprefix_ (block prefix)
+080-082: x 785f                                                             # (continued...)
+082-082: x                                                                  # data[01]: ............ (bundle prefix)
+082-087: x 6170706c65                                                       # data[02]: ............apple
+087-087: x                                                                  # data[03]: .................
+087-087: x                                                                  # data[04]: .................
+087-087: x                                                                  # data[05]: .................
+087-093: x 62616e616e61                                                     # data[06]: ............banana
+093-093: x                                                                  # data[07]: ..................
+093-093: x                                                                  # data[08]: ..................
+093-093: x                                                                  # data[09]: ..................
+093-093: x                                                                  # data[10]: ..................
+093-093: x                                                                  # data[11]: ..................
+093-100: x 636f636f6e7574                                                   # data[12]: ............coconut
+100-100: x                                                                  # data[13]: ...................
+100-100: x                                                                  # data[14]: ...................
+100-100: x                                                                  # data[15]: ...................
+100-100: x                                                                  # data[16]: ...................
+100-100: x                                                                  # data[17]: ...................
+100-100: x                                                                  # data[18]: ............ (bundle prefix)
+100-105: x 6775617661                                                       # data[19]: ............guava
+105-109: x 6b697769                                                         # data[20]: ............kiwi
+109-109: x                                                                  # data[21]: ................
+109-114: x 6c656d6f6e                                                       # data[22]: ............lemon
+# data for column 1
+# rawbytes
+# offsets table
+114-115: x 02                                                               # delta encoding: delta8
+115-119: x 00000000                                                         # 32-bit constant: 0
+119-120: x 00                                                               # data[0] = 0 [140 overall]
+120-121: x 03                                                               # data[1] = 3 [143 overall]
+121-122: x 06                                                               # data[2] = 6 [146 overall]
+122-123: x 09                                                               # data[3] = 9 [149 overall]
+123-124: x 0c                                                               # data[4] = 12 [152 overall]
+124-125: x 0f                                                               # data[5] = 15 [155 overall]
+125-126: x 12                                                               # data[6] = 18 [158 overall]
+126-127: x 15                                                               # data[7] = 21 [161 overall]
+127-128: x 18                                                               # data[8] = 24 [164 overall]
+128-129: x 1a                                                               # data[9] = 26 [166 overall]
+129-130: x 1c                                                               # data[10] = 28 [168 overall]
+130-131: x 1c                                                               # data[11] = 28 [168 overall]
+131-132: x 1f                                                               # data[12] = 31 [171 overall]
+132-133: x 22                                                               # data[13] = 34 [174 overall]
+133-134: x 25                                                               # data[14] = 37 [177 overall]
+134-135: x 28                                                               # data[15] = 40 [180 overall]
+135-136: x 2a                                                               # data[16] = 42 [182 overall]
+136-137: x 2d                                                               # data[17] = 45 [185 overall]
+137-138: x 30                                                               # data[18] = 48 [188 overall]
+138-139: x 33                                                               # data[19] = 51 [191 overall]
+139-140: x 36                                                               # data[20] = 54 [194 overall]
+# data
+140-143: x 403938                                                           # data[0]: @98
+143-146: x 403532                                                           # data[1]: @52
+146-149: x 403233                                                           # data[2]: @23
+149-152: x 403131                                                           # data[3]: @11
+152-155: x 403934                                                           # data[4]: @94
+155-158: x 403933                                                           # data[5]: @93
+158-161: x 403933                                                           # data[6]: @93
+161-164: x 403732                                                           # data[7]: @72
+164-166: x 4039                                                             # data[8]: @9
+166-168: x 4031                                                             # data[9]: @1
+168-168: x                                                                  # data[10]:
+168-171: x 403932                                                           # data[11]: @92
+171-174: x 403335                                                           # data[12]: @35
+174-177: x 403232                                                           # data[13]: @22
+177-180: x 403231                                                           # data[14]: @21
+180-182: x 4031                                                             # data[15]: @1
+182-185: x 403939                                                           # data[16]: @99
+185-188: x 403939                                                           # data[17]: @99
+188-191: x 403938                                                           # data[18]: @98
+191-194: x 403932                                                           # data[19]: @92
+# data for column 2
+194-195: x 03                                                               # delta encoding: delta16
+195-203: x 0000000000000000                                                 # 64-bit constant: 0
+# padding
+203-204: x 00                                                               # aligning to 16-bit boundary
+204-206: x 0100                                                             # data[0] = 1
+206-208: x 0100                                                             # data[1] = 1
+208-210: x 0100                                                             # data[2] = 1
+210-212: x 1200                                                             # data[3] = 18
+212-214: x 12f5                                                             # data[4] = 62738
+214-216: x 00f4                                                             # data[5] = 62464
+216-218: x 12dd                                                             # data[6] = 56594
+218-220: x 1200                                                             # data[7] = 18
+220-222: x 0100                                                             # data[8] = 1
+222-224: x 0100                                                             # data[9] = 1
+224-226: x 0100                                                             # data[10] = 1
+226-228: x 0100                                                             # data[11] = 1
+228-230: x 0100                                                             # data[12] = 1
+230-232: x 0100                                                             # data[13] = 1
+232-234: x 0100                                                             # data[14] = 1
+234-236: x 0100                                                             # data[15] = 1
+236-238: x 0100                                                             # data[16] = 1
+238-240: x 0100                                                             # data[17] = 1
+240-242: x 0100                                                             # data[18] = 1
+242-244: x 0000                                                             # data[19] = 0
+# data for column 3
+244-248: x 00000000                                                         # padding to align to 64-bit boundary
+248-256: b 0001000100000100000010110000000000000000000000000000000000000000 # bitmap word 0
+256-264: b 0000000100000000000000000000000000000000000000000000000000000000 # bitmap summary word 0-63
+# data for column 4
+# rawbytes
+# offsets table
+264-265: x 02                                                               # delta encoding: delta8
+265-269: x 00000000                                                         # 32-bit constant: 0
+269-270: x 00                                                               # data[0] = 0 [290 overall]
+270-271: x 07                                                               # data[1] = 7 [297 overall]
+271-272: x 0e                                                               # data[2] = 14 [304 overall]
+272-273: x 15                                                               # data[3] = 21 [311 overall]
+273-274: x 1c                                                               # data[4] = 28 [318 overall]
+274-275: x 24                                                               # data[5] = 36 [326 overall]
+275-276: x 24                                                               # data[6] = 36 [326 overall]
+276-277: x 2c                                                               # data[7] = 44 [334 overall]
+277-278: x 34                                                               # data[8] = 52 [342 overall]
+278-279: x 3b                                                               # data[9] = 59 [349 overall]
+279-280: x 42                                                               # data[10] = 66 [356 overall]
+280-281: x 49                                                               # data[11] = 73 [363 overall]
+281-282: x 52                                                               # data[12] = 82 [372 overall]
+282-283: x 5b                                                               # data[13] = 91 [381 overall]
+283-284: x 64                                                               # data[14] = 100 [390 overall]
+284-285: x 6d                                                               # data[15] = 109 [399 overall]
+285-286: x 75                                                               # data[16] = 117 [407 overall]
+286-287: x 7c                                                               # data[17] = 124 [414 overall]
+287-288: x 82                                                               # data[18] = 130 [420 overall]
+288-289: x 88                                                               # data[19] = 136 [426 overall]
+289-290: x 88                                                               # data[20] = 136 [426 overall]
+# data
+290-297: x 6170706c653938                                                   # data[0]: apple98
+297-304: x 6170706c653532                                                   # data[1]: apple52
+304-311: x 6170706c653233                                                   # data[2]: apple23
+311-318: x 6170706c653131                                                   # data[3]: apple11
+318-326: x 62616e616e613934                                                 # data[4]: banana94
+326-326: x                                                                  # data[5]:
+326-334: x 62616e616e613933                                                 # data[6]: banana93
+334-342: x 62616e616e613732                                                 # data[7]: banana72
+342-349: x 62616e616e6139                                                   # data[8]: banana9
+349-356: x 62616e616e6131                                                   # data[9]: banana1
+356-363: x 636f636f6e7574                                                   # data[10]: coconut
+363-372: x 636f636f6e75743932                                               # data[11]: coconut92
+372-381: x 636f636f6e75743335                                               # data[12]: coconut35
+381-390: x 636f636f6e75743232                                               # data[13]: coconut22
+390-399: x 636f636f6e75743231                                               # data[14]: coconut21
+399-407: x 636f636f6e757431                                                 # data[15]: coconut1
+407-414: x 67756176613939                                                   # data[16]: guava99
+414-420: x 6b6977693939                                                     # data[17]: kiwi99
+420-426: x 6b6977693938                                                     # data[18]: kiwi98
+426-426: x                                                                  # data[19]:
+# data for column 5
+426-432: x 000000000000                                                     # padding to align to 64-bit boundary
+432-440: b 0000000000000000000000000000000000000000000000000000000000000000 # bitmap word 0
+440-448: b 0000000000000000000000000000000000000000000000000000000000000000 # bitmap summary word 0-63
+
+# Scan across the block using next prefix.
+
+iter
+first
+next-prefix
+next-prefix
+next-prefix
+next-prefix
+next-prefix
+next-prefix
+----
+blockprefix_apple@98:apple98
+blockprefix_banana@94:banana94
+blockprefix_coconut:coconut
+blockprefix_guava@99:guava99
+blockprefix_kiwi@99:kiwi99
+blockprefix_lemon@92:
+.
+
+iter
+seek-ge blockprefix_banana@73
+next-prefix
+----
+blockprefix_banana@72:banana72
+blockprefix_coconut:coconut
diff --git a/sstable/colblk/testdata/data_block/simple b/sstable/colblk/testdata/data_block/simple
new file mode 100644
index 00000000..52e8d71f
--- /dev/null
+++ b/sstable/colblk/testdata/data_block/simple
@@ -0,0 +1,540 @@
+init
+----
+size=1:
+0: prefixes:       prefixbytes(16): 0 keys
+1: suffixes:       bytes: 0 rows set; 0 bytes in data
+2: trailers:       uint64: 0 rows
+3: prefix changed: bitmap
+4: values:         bytes: 0 rows set; 0 bytes in data
+5: is-value-ext:   bitmap
+
+write
+a@10#0,SET:apple
+b@5#0,SET:banana
+b@2#0,SETWITHDEL:blueberry
+c@9#0,SETWITHDEL:coconut
+c@6#0,SET:cantelope
+c@1#0,SET:clementine
+----
+size=201:
+0: prefixes:       prefixbytes(16): 6 keys
+1: suffixes:       bytes: 6 rows set; 13 bytes in data
+2: trailers:       uint64: 6 rows
+3: prefix changed: bitmap
+4: values:         bytes: 6 rows set; 46 bytes in data
+5: is-value-ext:   bitmap
+
+write
+d@11#0,DEL:
+----
+size=209:
+0: prefixes:       prefixbytes(16): 7 keys
+1: suffixes:       bytes: 7 rows set; 16 bytes in data
+2: trailers:       uint64: 7 rows
+3: prefix changed: bitmap
+4: values:         bytes: 7 rows set; 46 bytes in data
+5: is-value-ext:   bitmap
+
+finish
+----
+# data block header
+000-004: x 04000000                                                         # maximum key length: 4
+# columnar block header
+004-005: x 01                                                               # version 1
+005-007: x 0600                                                             # 6 columns
+007-011: x 07000000                                                         # 7 rows
+# column 0
+011-012: b 00000111                                                         # prefixbytes
+012-016: x 29000000                                                         # page start 41
+# column 1
+016-017: b 00000110                                                         # bytes
+017-021: x 3c000000                                                         # page start 60
+# column 2
+021-022: b 00000101                                                         # uint64
+022-026: x 59000000                                                         # page start 89
+# column 3
+026-027: b 00000001                                                         # bool
+027-031: x 69000000                                                         # page start 105
+# column 4
+031-032: b 00000110                                                         # bytes
+032-036: x 80000000                                                         # page start 128
+# column 5
+036-037: b 00000001                                                         # bool
+037-041: x bb000000                                                         # page start 187
+# data for column 0
+# PrefixBytes
+041-042: x 04                                                               # bundleSize: 16
+# Offsets table
+042-043: x 02                                                               # delta encoding: delta8
+043-047: x 00000000                                                         # 32-bit constant: 0
+047-048: x 00                                                               # data[0] = 0 [56 overall]
+048-049: x 00                                                               # data[1] = 0 [56 overall]
+049-050: x 01                                                               # data[2] = 1 [57 overall]
+050-051: x 02                                                               # data[3] = 2 [58 overall]
+051-052: x 02                                                               # data[4] = 2 [58 overall]
+052-053: x 03                                                               # data[5] = 3 [59 overall]
+053-054: x 03                                                               # data[6] = 3 [59 overall]
+054-055: x 03                                                               # data[7] = 3 [59 overall]
+055-056: x 04                                                               # data[8] = 4 [60 overall]
+# Data
+056-056: x                                                                  # data[00]:  (block prefix)
+056-056: x                                                                  # data[01]:  (bundle prefix)
+056-057: x 61                                                               # data[02]: a
+057-058: x 62                                                               # data[03]: b
+058-058: x                                                                  # data[04]: .
+058-059: x 63                                                               # data[05]: c
+059-059: x                                                                  # data[06]: .
+059-059: x                                                                  # data[07]: .
+059-060: x 64                                                               # data[08]: d
+# data for column 1
+# rawbytes
+# offsets table
+060-061: x 02                                                               # delta encoding: delta8
+061-065: x 00000000                                                         # 32-bit constant: 0
+065-066: x 00                                                               # data[0] = 0 [73 overall]
+066-067: x 03                                                               # data[1] = 3 [76 overall]
+067-068: x 05                                                               # data[2] = 5 [78 overall]
+068-069: x 07                                                               # data[3] = 7 [80 overall]
+069-070: x 09                                                               # data[4] = 9 [82 overall]
+070-071: x 0b                                                               # data[5] = 11 [84 overall]
+071-072: x 0d                                                               # data[6] = 13 [86 overall]
+072-073: x 10                                                               # data[7] = 16 [89 overall]
+# data
+073-076: x 403130                                                           # data[0]: @10
+076-078: x 4035                                                             # data[1]: @5
+078-080: x 4032                                                             # data[2]: @2
+080-082: x 4039                                                             # data[3]: @9
+082-084: x 4036                                                             # data[4]: @6
+084-086: x 4031                                                             # data[5]: @1
+086-089: x 403131                                                           # data[6]: @11
+# data for column 2
+089-090: x 02                                                               # delta encoding: delta8
+090-098: x 0000000000000000                                                 # 64-bit constant: 0
+098-099: x 01                                                               # data[0] = 1
+099-100: x 01                                                               # data[1] = 1
+100-101: x 12                                                               # data[2] = 18
+101-102: x 12                                                               # data[3] = 18
+102-103: x 01                                                               # data[4] = 1
+103-104: x 01                                                               # data[5] = 1
+104-105: x 00                                                               # data[6] = 0
+# data for column 3
+105-112: x 00000000000000                                                   # padding to align to 64-bit boundary
+112-120: b 0100101100000000000000000000000000000000000000000000000000000000 # bitmap word 0
+120-128: b 0000000100000000000000000000000000000000000000000000000000000000 # bitmap summary word 0-63
+# data for column 4
+# rawbytes
+# offsets table
+128-129: x 02                                                               # delta encoding: delta8
+129-133: x 00000000                                                         # 32-bit constant: 0
+133-134: x 00                                                               # data[0] = 0 [141 overall]
+134-135: x 05                                                               # data[1] = 5 [146 overall]
+135-136: x 0b                                                               # data[2] = 11 [152 overall]
+136-137: x 14                                                               # data[3] = 20 [161 overall]
+137-138: x 1b                                                               # data[4] = 27 [168 overall]
+138-139: x 24                                                               # data[5] = 36 [177 overall]
+139-140: x 2e                                                               # data[6] = 46 [187 overall]
+140-141: x 2e                                                               # data[7] = 46 [187 overall]
+# data
+141-146: x 6170706c65                                                       # data[0]: apple
+146-152: x 62616e616e61                                                     # data[1]: banana
+152-161: x 626c75656265727279                                               # data[2]: blueberry
+161-168: x 636f636f6e7574                                                   # data[3]: coconut
+168-177: x 63616e74656c6f7065                                               # data[4]: cantelope
+177-187: x 636c656d656e74696e65                                             # data[5]: clementine
+187-187: x                                                                  # data[6]:
+# data for column 5
+187-192: x 0000000000                                                       # padding to align to 64-bit boundary
+192-200: b 0000000000000000000000000000000000000000000000000000000000000000 # bitmap word 0
+200-208: b 0000000000000000000000000000000000000000000000000000000000000000 # bitmap summary word 0-63
+
+iter
+first
+next
+next
+next
+next
+next
+next
+next
+----
+a@10:apple
+b@5:banana
+b@2:blueberry
+c@9:coconut
+c@6:cantelope
+c@1:clementine
+d@11:
+.
+
+iter
+last
+prev
+prev
+prev
+prev
+prev
+prev
+prev
+----
+d@11:
+c@1:clementine
+c@6:cantelope
+c@9:coconut
+b@2:blueberry
+b@5:banana
+a@10:apple
+.
+
+iter
+seek-ge a
+seek-ge a@10
+seek-ge a@3
+seek-ge a@1
+seek-ge b
+seek-ge b@999999
+seek-ge b@5
+seek-ge b@4
+seek-ge b@3
+seek-ge b@2
+seek-ge b@1
+seek-ge c
+----
+a@10:apple
+a@10:apple
+b@5:banana
+b@5:banana
+b@5:banana
+b@5:banana
+b@5:banana
+b@2:blueberry
+b@2:blueberry
+b@2:blueberry
+c@9:coconut
+c@9:coconut
+
+iter
+seek-ge c@10
+seek-ge c@9
+seek-ge c@8
+seek-ge c@7
+seek-ge c@6
+seek-ge c@5
+seek-ge c@4
+seek-ge c@3
+seek-ge c@2
+seek-ge c@1
+seek-ge c@0
+seek-ge d
+seek-ge d@11
+seek-ge d@10
+----
+c@9:coconut
+c@9:coconut
+c@6:cantelope
+c@6:cantelope
+c@6:cantelope
+c@1:clementine
+c@1:clementine
+c@1:clementine
+c@1:clementine
+c@1:clementine
+d@11:
+d@11:
+d@11:
+.
+
+iter
+seek-lt a
+seek-lt a@10
+seek-lt a@3
+seek-lt a@1
+seek-lt b
+seek-lt b@999999
+seek-lt b@5
+seek-lt b@4
+seek-lt b@3
+seek-lt b@2
+seek-lt b@1
+seek-lt c
+----
+.
+.
+a@10:apple
+a@10:apple
+a@10:apple
+a@10:apple
+a@10:apple
+b@5:banana
+b@5:banana
+b@5:banana
+b@2:blueberry
+b@2:blueberry
+
+iter
+seek-lt c@10
+seek-lt c@9
+seek-lt c@8
+seek-lt c@7
+seek-lt c@6
+seek-lt c@5
+seek-lt c@4
+seek-lt c@3
+seek-lt c@2
+seek-lt c@1
+seek-lt c@0
+seek-lt d
+seek-lt d@11
+seek-lt d@10
+----
+b@2:blueberry
+b@2:blueberry
+c@9:coconut
+c@9:coconut
+c@9:coconut
+c@6:cantelope
+c@6:cantelope
+c@6:cantelope
+c@6:cantelope
+c@6:cantelope
+c@1:clementine
+c@1:clementine
+c@1:clementine
+d@11:
+
+init
+----
+size=1:
+0: prefixes:       prefixbytes(16): 0 keys
+1: suffixes:       bytes: 0 rows set; 0 bytes in data
+2: trailers:       uint64: 0 rows
+3: prefix changed: bitmap
+4: values:         bytes: 0 rows set; 0 bytes in data
+5: is-value-ext:   bitmap
+
+write
+aaaaaaaaaaaaaaappalling@10#0,SET:a
+aaaaaaaaaaaaaaapparel@10#0,SET:a
+aaaaaaaaaaaaaaapparition@10#0,SET:a
+aaaaaaaaaaaaaaappearing@10#0,SET:a
+aaaaaaaaaaaaaaappend@10#0,SET:a
+aaaaaaaaaaaaaaappendage@10#0,SET:a
+aaaaaaaaaaaaaaappendix@10#0,SET:a
+aaaaaaaaaaaaaaapplaud@10#0,SET:a
+aaaaaaaaaaaaaaapple@10#0,SET:a
+aaaaaaaaaaaaaaapplication@10#0,SET:a
+aaaaaaaaaaaaaaapplied@10#0,SET:a
+aaaaaaaaaaaaaaapplying@10#0,SET:a
+aaaaaaaaaaaaaaappoint@10#0,SET:a
+aaaaaaaaaaaaaaapposes@10#0,SET:a
+aaaaaaaaaaaaaaapproves@10#0,SET:a
+aaaaaaaaaaaaaaarresting@10#0,SET:a
+aaaaaaaaaaaaaaarrived@10#0,SET:a
+----
+size=361:
+0: prefixes:       prefixbytes(16): 17 keys
+1: suffixes:       bytes: 17 rows set; 51 bytes in data
+2: trailers:       uint64: 17 rows
+3: prefix changed: bitmap
+4: values:         bytes: 17 rows set; 17 bytes in data
+5: is-value-ext:   bitmap
+
+finish
+----
+# data block header
+000-004: x 1c000000                                                         # maximum key length: 28
+# columnar block header
+004-005: x 01                                                               # version 1
+005-007: x 0600                                                             # 6 columns
+007-011: x 11000000                                                         # 17 rows
+# column 0
+011-012: b 00000111                                                         # prefixbytes
+012-016: x 29000000                                                         # page start 41
+# column 1
+016-017: b 00000110                                                         # bytes
+017-021: x c7000000                                                         # page start 199
+# column 2
+021-022: b 00000101                                                         # uint64
+022-026: x 11010000                                                         # page start 273
+# column 3
+026-027: b 00000001                                                         # bool
+027-031: x 1a010000                                                         # page start 282
+# column 4
+031-032: b 00000110                                                         # bytes
+032-036: x 30010000                                                         # page start 304
+# column 5
+036-037: b 00000001                                                         # bool
+037-041: x 58010000                                                         # page start 344
+# data for column 0
+# PrefixBytes
+041-042: x 04                                                               # bundleSize: 16
+# Offsets table
+042-043: x 02                                                               # delta encoding: delta8
+043-047: x 00000000                                                         # 32-bit constant: 0
+047-048: x 0f                                                               # data[0] = 15 [82 overall]
+048-049: x 0f                                                               # data[1] = 15 [82 overall]
+049-050: x 17                                                               # data[2] = 23 [90 overall]
+050-051: x 1d                                                               # data[3] = 29 [96 overall]
+051-052: x 26                                                               # data[4] = 38 [105 overall]
+052-053: x 2e                                                               # data[5] = 46 [113 overall]
+053-054: x 33                                                               # data[6] = 51 [118 overall]
+054-055: x 3b                                                               # data[7] = 59 [126 overall]
+055-056: x 42                                                               # data[8] = 66 [133 overall]
+056-057: x 48                                                               # data[9] = 72 [139 overall]
+057-058: x 4c                                                               # data[10] = 76 [143 overall]
+058-059: x 56                                                               # data[11] = 86 [153 overall]
+059-060: x 5c                                                               # data[12] = 92 [159 overall]
+060-061: x 63                                                               # data[13] = 99 [166 overall]
+061-062: x 69                                                               # data[14] = 105 [172 overall]
+062-063: x 6f                                                               # data[15] = 111 [178 overall]
+063-064: x 76                                                               # data[16] = 118 [185 overall]
+064-065: x 7e                                                               # data[17] = 126 [193 overall]
+065-066: x 84                                                               # data[18] = 132 [199 overall]
+066-067: x 84                                                               # data[19] = 132 [199 overall]
+# Data
+067-077: x 61616161616161616161                                             # data[00]: aaaaaaaaaaaaaaa (block prefix)
+077-082: x 6161616161                                                       # (continued...)
+082-082: x                                                                  # data[01]: ............... (bundle prefix)
+082-090: x 7070616c6c696e67                                                 # data[02]: ...............ppalling
+090-096: x 70706172656c                                                     # data[03]: ...............pparel
+096-105: x 707061726974696f6e                                               # data[04]: ...............pparition
+105-113: x 7070656172696e67                                                 # data[05]: ...............ppearing
+113-118: x 7070656e64                                                       # data[06]: ...............ppend
+118-126: x 7070656e64616765                                                 # data[07]: ...............ppendage
+126-133: x 7070656e646978                                                   # data[08]: ...............ppendix
+133-139: x 70706c617564                                                     # data[09]: ...............pplaud
+139-143: x 70706c65                                                         # data[10]: ...............pple
+143-153: x 70706c69636174696f6e                                             # data[11]: ...............pplication
+153-159: x 70706c696564                                                     # data[12]: ...............pplied
+159-166: x 70706c79696e67                                                   # data[13]: ...............pplying
+166-172: x 70706f696e74                                                     # data[14]: ...............ppoint
+172-178: x 70706f736573                                                     # data[15]: ...............pposes
+178-185: x 7070726f766573                                                   # data[16]: ...............pproves
+185-193: x 7272657374696e67                                                 # data[17]: ...............rresting
+193-199: x 727269766564                                                     # data[18]: ...............rrived (bundle prefix)
+199-199: x                                                                  # data[19]: .....................
+# data for column 1
+# rawbytes
+# offsets table
+199-200: x 02                                                               # delta encoding: delta8
+200-204: x 00000000                                                         # 32-bit constant: 0
+204-205: x 00                                                               # data[0] = 0 [222 overall]
+205-206: x 03                                                               # data[1] = 3 [225 overall]
+206-207: x 06                                                               # data[2] = 6 [228 overall]
+207-208: x 09                                                               # data[3] = 9 [231 overall]
+208-209: x 0c                                                               # data[4] = 12 [234 overall]
+209-210: x 0f                                                               # data[5] = 15 [237 overall]
+210-211: x 12                                                               # data[6] = 18 [240 overall]
+211-212: x 15                                                               # data[7] = 21 [243 overall]
+212-213: x 18                                                               # data[8] = 24 [246 overall]
+213-214: x 1b                                                               # data[9] = 27 [249 overall]
+214-215: x 1e                                                               # data[10] = 30 [252 overall]
+215-216: x 21                                                               # data[11] = 33 [255 overall]
+216-217: x 24                                                               # data[12] = 36 [258 overall]
+217-218: x 27                                                               # data[13] = 39 [261 overall]
+218-219: x 2a                                                               # data[14] = 42 [264 overall]
+219-220: x 2d                                                               # data[15] = 45 [267 overall]
+220-221: x 30                                                               # data[16] = 48 [270 overall]
+221-222: x 33                                                               # data[17] = 51 [273 overall]
+# data
+222-225: x 403130                                                           # data[0]: @10
+225-228: x 403130                                                           # data[1]: @10
+228-231: x 403130                                                           # data[2]: @10
+231-234: x 403130                                                           # data[3]: @10
+234-237: x 403130                                                           # data[4]: @10
+237-240: x 403130                                                           # data[5]: @10
+240-243: x 403130                                                           # data[6]: @10
+243-246: x 403130                                                           # data[7]: @10
+246-249: x 403130                                                           # data[8]: @10
+249-252: x 403130                                                           # data[9]: @10
+252-255: x 403130                                                           # data[10]: @10
+255-258: x 403130                                                           # data[11]: @10
+258-261: x 403130                                                           # data[12]: @10
+261-264: x 403130                                                           # data[13]: @10
+264-267: x 403130                                                           # data[14]: @10
+267-270: x 403130                                                           # data[15]: @10
+270-273: x 403130                                                           # data[16]: @10
+# data for column 2
+273-274: x 01                                                               # delta encoding: const
+274-282: x 0100000000000000                                                 # 64-bit constant: 1
+# data for column 3
+282-288: x 000000000000                                                     # padding to align to 64-bit boundary
+288-296: b 1111111111111111000000010000000000000000000000000000000000000000 # bitmap word 0
+296-304: b 0000000100000000000000000000000000000000000000000000000000000000 # bitmap summary word 0-63
+# data for column 4
+# rawbytes
+# offsets table
+304-305: x 02                                                               # delta encoding: delta8
+305-309: x 00000000                                                         # 32-bit constant: 0
+309-310: x 00                                                               # data[0] = 0 [327 overall]
+310-311: x 01                                                               # data[1] = 1 [328 overall]
+311-312: x 02                                                               # data[2] = 2 [329 overall]
+312-313: x 03                                                               # data[3] = 3 [330 overall]
+313-314: x 04                                                               # data[4] = 4 [331 overall]
+314-315: x 05                                                               # data[5] = 5 [332 overall]
+315-316: x 06                                                               # data[6] = 6 [333 overall]
+316-317: x 07                                                               # data[7] = 7 [334 overall]
+317-318: x 08                                                               # data[8] = 8 [335 overall]
+318-319: x 09                                                               # data[9] = 9 [336 overall]
+319-320: x 0a                                                               # data[10] = 10 [337 overall]
+320-321: x 0b                                                               # data[11] = 11 [338 overall]
+321-322: x 0c                                                               # data[12] = 12 [339 overall]
+322-323: x 0d                                                               # data[13] = 13 [340 overall]
+323-324: x 0e                                                               # data[14] = 14 [341 overall]
+324-325: x 0f                                                               # data[15] = 15 [342 overall]
+325-326: x 10                                                               # data[16] = 16 [343 overall]
+326-327: x 11                                                               # data[17] = 17 [344 overall]
+# data
+327-328: x 61                                                               # data[0]: a
+328-329: x 61                                                               # data[1]: a
+329-330: x 61                                                               # data[2]: a
+330-331: x 61                                                               # data[3]: a
+331-332: x 61                                                               # data[4]: a
+332-333: x 61                                                               # data[5]: a
+333-334: x 61                                                               # data[6]: a
+334-335: x 61                                                               # data[7]: a
+335-336: x 61                                                               # data[8]: a
+336-337: x 61                                                               # data[9]: a
+337-338: x 61                                                               # data[10]: a
+338-339: x 61                                                               # data[11]: a
+339-340: x 61                                                               # data[12]: a
+340-341: x 61                                                               # data[13]: a
+341-342: x 61                                                               # data[14]: a
+342-343: x 61                                                               # data[15]: a
+343-344: x 61                                                               # data[16]: a
+# data for column 5
+344-352: b 0000000000000000000000000000000000000000000000000000000000000000 # bitmap word 0
+352-360: b 0000000000000000000000000000000000000000000000000000000000000000 # bitmap summary word 0-63
+
+iter
+seek-ge aaa
+seek-ge aaaaaaaaa
+seek-ge aaaaaaaaaaaaaaapp
+seek-ge aaaaaaaaaaaaaaapparel@10
+seek-ge aaaaaaaaaaaaaaapparh
+seek-ge aaaaaaaaaaaaaaarresting@10
+seek-ge aaaaaaaaaaaaaaarrived@10
+----
+aaaaaaaaaaaaaaappalling@10:a
+aaaaaaaaaaaaaaappalling@10:a
+aaaaaaaaaaaaaaappalling@10:a
+aaaaaaaaaaaaaaapparel@10:a
+aaaaaaaaaaaaaaapparition@10:a
+aaaaaaaaaaaaaaarresting@10:a
+aaaaaaaaaaaaaaarrived@10:a
+
+iter
+seek-lt aaa
+seek-lt aaaaaaaaa
+seek-lt aaaaaaaaaaaaaaapp
+seek-lt aaaaaaaaaaaaaaapparel@10
+seek-lt aaaaaaaaaaaaaaapparh
+seek-lt aaaaaaaaaaaaaaarresting@10
+seek-lt aaaaaaaaaaaaaaarrived@10
+----
+.
+.
+.
+aaaaaaaaaaaaaaappalling@10:a
+aaaaaaaaaaaaaaapparel@10:a
+aaaaaaaaaaaaaaapproves@10:a
+aaaaaaaaaaaaaaarresting@10:a