Repository: cockroachdb/pebble
Pull request #3754 (2024-07-12 17:56:00)

colblk: only align uint deltas
Previously, even when using a delta-encoding, the uint column encoding aligned its output to the width of the logical uint. This was necessary to read the full-width constant using a pointer cast. This commit adapts the encoding to only align to the width of the deltas, using ordinary binary.LittleEndian methods for setting and getting the constant. This get only needs to happen once, while parsing the column. This reduces the amount of alignment padding necessary when delta encoding is effective.

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/3754)
<!-- Reviewable:end -->

jbowens: TFTR!

Patch:
diff --git a/sstable/colblk/column.go b/sstable/colblk/column.go
index c4bbb152..6e4967c7 100644
--- a/sstable/colblk/column.go
+++ b/sstable/colblk/column.go
@@ -192,6 +192,21 @@ func (d DeltaEncoding) String() string {
 	}
 }
 
+func (d DeltaEncoding) width() int {
+	switch d {
+	case DeltaEncodingConstant:
+		return 0
+	case DeltaEncodingUint8:
+		return 1
+	case DeltaEncodingUint16:
+		return 2
+	case DeltaEncodingUint32:
+		return 4
+	default:
+		panic("unreachable")
+	}
+}
+
 // ColumnWriter is an interface implemented by column encoders that accumulate a
 // column's values and then serialize them.
 type ColumnWriter interface {
diff --git a/sstable/colblk/uints.go b/sstable/colblk/uints.go
index 44323ce0..5ff86e14 100644
--- a/sstable/colblk/uints.go
+++ b/sstable/colblk/uints.go
@@ -5,6 +5,7 @@
 package colblk
 
 import (
+	"encoding/binary"
 	"fmt"
 	"io"
 	"unsafe"
@@ -198,15 +199,17 @@ func (b *UintBuilder[T]) Size(rows int, offset uint32) uint32 {
 // sizeof(T), then a delta encoding is assumed.
 func uintColumnSize[T Uint](rows, offset, width uint32) uint32 {
 	logicalWidth := uint32(unsafe.Sizeof(T(0)))
-	// Include alignment bytes necessary to align offset appropriately for
-	// elements of type T.
-	offset = align(offset, logicalWidth)
 	if width != logicalWidth {
 		// A delta encoding will be used. We need to first account for the constant
 		// that encodes the minimum. This constant is the full width of the column's
 		// logical data type.
 		offset += logicalWidth
 	}
+	// Include alignment bytes necessary to align offset appropriately for
+	// elements of the delta width.
+	if width > 0 {
+		offset = align(offset, width)
+	}
 	// Now account for the array of [rows] x w elements encoding the deltas.
 	return offset + rows*width
 }
@@ -242,17 +245,13 @@ func uintColumnFinish[T Uint](
 	minimum T, values []T, width, offset uint32, buf []byte,
 ) (uint32, ColumnEncoding) {
 	enc := EncodingDefault
-	// Align the offset appropriately for elements of type T.
-	offset = alignWithZeroes(buf, offset, uint32(unsafe.Sizeof(T(0))))
 
 	// Compare the computed delta width to see if we're able to use an array of
 	// lower-width deltas to encode the column.
 	if uintptr(width) < unsafe.Sizeof(T(0)) {
 		// Regardless of the width, we encode a constant of size T encoding the
 		// minimum across all the values.
-		dest := makeUnsafeRawSlice[T](unsafe.Pointer(&buf[offset]))
-		dest.set(0, minimum)
-		offset += uint32(unsafe.Sizeof(T(0)))
+		offset += uint32(writeLittleEndianNonaligned(buf, offset, minimum))
 
 		switch width {
 		case 0:
@@ -268,12 +267,16 @@ func uintColumnFinish[T Uint](
 			return offset, enc
 		case align16:
 			enc = enc.WithDelta(DeltaEncodingUint16)
+			// Align the offset appropriately for uint16s.
+			offset = alignWithZeroes(buf, offset, align16)
 			dest := makeUnsafeRawSlice[uint16](unsafe.Pointer(&buf[offset]))
 			reduceUints[T, uint16](minimum, values, dest.Slice(len(values)))
 			offset += uint32(len(values)) * align16
 			return offset, enc
 		case align32:
 			enc = enc.WithDelta(DeltaEncodingUint32)
+			// Align the offset appropriately for uint32s.
+			offset = alignWithZeroes(buf, offset, align32)
 			dest := makeUnsafeRawSlice[uint32](unsafe.Pointer(&buf[offset]))
 			reduceUints[T, uint32](minimum, values, dest.Slice(len(values)))
 			offset += uint32(len(values)) * align32
@@ -287,6 +290,44 @@ func uintColumnFinish[T Uint](
 	return offset, enc
 }
 
+// writeLittleEndianNonaligned writes v to buf at the provided offset in
+// little-endian, without assuming that the offset is aligned to the size of T.
+func writeLittleEndianNonaligned[T Uint](buf []byte, offset uint32, v T) int {
+	sz := unsafe.Sizeof(v)
+	switch sz {
+	case 1:
+		buf[offset] = byte(v)
+	case 2:
+		binary.LittleEndian.PutUint16(buf[offset:], uint16(v))
+	case 4:
+		binary.LittleEndian.PutUint32(buf[offset:], uint32(v))
+	case 8:
+		binary.LittleEndian.PutUint64(buf[offset:], uint64(v))
+	default:
+		panic("unreachable")
+	}
+	return int(sz)
+}
+
+// readLittleEndianNonaligned reads a value of type T from buf at the provided
+// offset in little-endian, without assuming that the offset is aligned to the
+// size of T.
+func readLittleEndianNonaligned[T constraints.Integer](buf []byte, offset uint32) T {
+	sz := unsafe.Sizeof(T(0))
+	switch sz {
+	case 1:
+		return T(buf[offset])
+	case 2:
+		return T(binary.LittleEndian.Uint16(buf[offset:]))
+	case 4:
+		return T(binary.LittleEndian.Uint32(buf[offset:]))
+	case 8:
+		return T(binary.LittleEndian.Uint64(buf[offset:]))
+	default:
+		panic("unreachable")
+	}
+}
+
 // WriteDebug implements Encoder.
 func (b *UintBuilder[T]) WriteDebug(w io.Writer, rows int) {
 	fmt.Fprintf(w, "%s: %d rows", b.dt, rows)
@@ -344,10 +385,7 @@ func uintsToBinFormatter(
 	}
 
 	logicalWidth := desc.DataType.uintWidth()
-	if off := align(f.Offset(), int(logicalWidth)); off != f.Offset() {
-		f.CommentLine("Padding")
-		f.HexBytesln(off-f.Offset(), "aligning to %d-bit boundary", logicalWidth*8)
-	}
+
 	elementWidth := int(logicalWidth)
 	if desc.Encoding.Delta() != DeltaEncodingNone {
 		f.HexBytesln(int(logicalWidth), "%d-bit constant: %d", logicalWidth*8, f.PeekUint(int(logicalWidth)))
@@ -366,6 +404,10 @@ func uintsToBinFormatter(
 			panic("unreachable")
 		}
 	}
+	if off := align(f.Offset(), int(elementWidth)); off != f.Offset() {
+		f.CommentLine("Padding")
+		f.HexBytesln(off-f.Offset(), "aligning to %d-bit boundary", elementWidth*8)
+	}
 	for i := 0; i < rows; i++ {
 		f.HexBytesln(elementWidth, "data[%d] = %s", i, uintFormatter(f.PeekUint(elementWidth)))
 	}
diff --git a/sstable/colblk/unsafe_slice.go b/sstable/colblk/unsafe_slice.go
index 6eae96db..b0eddee5 100644
--- a/sstable/colblk/unsafe_slice.go
+++ b/sstable/colblk/unsafe_slice.go
@@ -70,28 +70,22 @@ type UnsafeIntegerSlice[T constraints.Integer] struct {
 func readUnsafeIntegerSlice[T constraints.Integer](
 	rows int, b []byte, off uint32, delta DeltaEncoding,
 ) (endOffset uint32, slice UnsafeIntegerSlice[T]) {
-	off = align(off, uint32(unsafe.Sizeof(T(0))))
-
-	fullWidthSlice := makeUnsafeIntegerSlice[T](0, unsafe.Pointer(&b[off]), int(unsafe.Sizeof(T(0))))
 	switch delta {
 	case DeltaEncodingNone:
-		slice = fullWidthSlice
+		off = align(off, uint32(unsafe.Sizeof(T(0))))
+		slice = makeUnsafeIntegerSlice[T](0, unsafe.Pointer(&b[off]), int(unsafe.Sizeof(T(0))))
 		off += uint32(unsafe.Sizeof(T(0))) * uint32(rows)
 	case DeltaEncodingConstant:
+		base := readLittleEndianNonaligned[T](b, off)
 		off += uint32(unsafe.Sizeof(T(0)))
-		slice = makeUnsafeIntegerSlice[T](fullWidthSlice.At(0), unsafe.Pointer(&b[off]), 0)
-	case DeltaEncodingUint8:
-		off += uint32(unsafe.Sizeof(T(0)))
-		slice = makeUnsafeIntegerSlice[T](fullWidthSlice.At(0), unsafe.Pointer(&b[off]), 1)
-		off += uint32(rows)
-	case DeltaEncodingUint16:
-		off += uint32(unsafe.Sizeof(T(0)))
-		slice = makeUnsafeIntegerSlice[T](fullWidthSlice.At(0), unsafe.Pointer(&b[off]), align16)
-		off += uint32(rows) * align16
-	case DeltaEncodingUint32:
+		slice = makeUnsafeIntegerSlice[T](base, unsafe.Pointer(&b[off]), 0)
+	case DeltaEncodingUint8, DeltaEncodingUint16, DeltaEncodingUint32:
+		w := delta.width()
+		base := readLittleEndianNonaligned[T](b, off)
 		off += uint32(unsafe.Sizeof(T(0)))
-		slice = makeUnsafeIntegerSlice[T](fullWidthSlice.At(0), unsafe.Pointer(&b[off]), align32)
-		off += uint32(rows) * align32
+		off = align(off, uint32(w))
+		slice = makeUnsafeIntegerSlice[T](base, unsafe.Pointer(&b[off]), w)
+		off += uint32(rows) * uint32(w)
 	default:
 		panic("unreachable")
 	}


Test patch:
diff --git a/sstable/colblk/testdata/raw_bytes b/sstable/colblk/testdata/raw_bytes
index 27c37854..4b59abc3 100644
--- a/sstable/colblk/testdata/raw_bytes
+++ b/sstable/colblk/testdata/raw_bytes
@@ -16,16 +16,14 @@ a
 build offset=1
 a
 ----
-00-01: x 00       # start offset
+0-1: x 00       # start offset
 # RawBytes
 # Offsets table
-# Padding
-01-04: x 000000   # aligning to 32-bit boundary
-04-08: x 00000000 # 32-bit constant: 0
-08-09: x 00       # data[0] = 0 [10 overall]
-09-10: x 01       # data[1] = 1 [11 overall]
+1-5: x 00000000 # 32-bit constant: 0
+5-6: x 00       # data[0] = 0 [7 overall]
+6-7: x 01       # data[1] = 1 [8 overall]
 # Data
-10-11: x 61       # data[0]: a
+7-8: x 61       # data[0]: a
 
 build offset=2
 a
@@ -33,13 +31,11 @@ a
 00-02: x 0000     # start offset
 # RawBytes
 # Offsets table
-# Padding
-02-04: x 0000     # aligning to 32-bit boundary
-04-08: x 00000000 # 32-bit constant: 0
-08-09: x 00       # data[0] = 0 [10 overall]
-09-10: x 01       # data[1] = 1 [11 overall]
+02-06: x 00000000 # 32-bit constant: 0
+06-07: x 00       # data[0] = 0 [8 overall]
+07-08: x 01       # data[1] = 1 [9 overall]
 # Data
-10-11: x 61       # data[0]: a
+08-09: x 61       # data[0]: a
 
 build offset=3
 a
@@ -47,13 +43,11 @@ a
 00-03: x 000000   # start offset
 # RawBytes
 # Offsets table
-# Padding
-03-04: x 00       # aligning to 32-bit boundary
-04-08: x 00000000 # 32-bit constant: 0
-08-09: x 00       # data[0] = 0 [10 overall]
-09-10: x 01       # data[1] = 1 [11 overall]
+03-07: x 00000000 # 32-bit constant: 0
+07-08: x 00       # data[0] = 0 [9 overall]
+08-09: x 01       # data[1] = 1 [10 overall]
 # Data
-10-11: x 61       # data[0]: a
+09-10: x 61       # data[0]: a
 
 build offset=4
 a
diff --git a/sstable/colblk/testdata/uints b/sstable/colblk/testdata/uints
index 3d696ec0..49922f51 100644
--- a/sstable/colblk/testdata/uints
+++ b/sstable/colblk/testdata/uints
@@ -140,6 +140,43 @@ b64:
   64: *colblk.UintBuilder[uint64].Size(9, 0) = 26
   64: *colblk.UintBuilder[uint64].Size(8, 0) = 16
 
+size rows=(9, 8) offset=1
+----
+b16:
+  16: *colblk.UintBuilder[uint16].Size(9, 1) = 20 [19 w/o offset]
+  16: *colblk.UintBuilder[uint16].Size(8, 1) = 11 [10 w/o offset]
+b32:
+  32: *colblk.UintBuilder[uint32].Size(9, 1) = 24 [23 w/o offset]
+  32: *colblk.UintBuilder[uint32].Size(8, 1) = 13 [12 w/o offset]
+b64:
+  64: *colblk.UintBuilder[uint64].Size(9, 1) = 28 [27 w/o offset]
+  64: *colblk.UintBuilder[uint64].Size(8, 1) = 17 [16 w/o offset]
+
+size rows=(9, 8) offset=2
+----
+b16:
+  16: *colblk.UintBuilder[uint16].Size(9, 2) = 20 [18 w/o offset]
+  16: *colblk.UintBuilder[uint16].Size(8, 2) = 12 [10 w/o offset]
+b32:
+  32: *colblk.UintBuilder[uint32].Size(9, 2) = 24 [22 w/o offset]
+  32: *colblk.UintBuilder[uint32].Size(8, 2) = 14 [12 w/o offset]
+b64:
+  64: *colblk.UintBuilder[uint64].Size(9, 2) = 28 [26 w/o offset]
+  64: *colblk.UintBuilder[uint64].Size(8, 2) = 18 [16 w/o offset]
+
+
+size rows=(9, 8) offset=5
+----
+b16:
+  16: *colblk.UintBuilder[uint16].Size(9, 5) = 24 [19 w/o offset]
+  16: *colblk.UintBuilder[uint16].Size(8, 5) = 15 [10 w/o offset]
+b32:
+  32: *colblk.UintBuilder[uint32].Size(9, 5) = 28 [23 w/o offset]
+  32: *colblk.UintBuilder[uint32].Size(8, 5) = 17 [12 w/o offset]
+b64:
+  64: *colblk.UintBuilder[uint64].Size(9, 5) = 32 [27 w/o offset]
+  64: *colblk.UintBuilder[uint64].Size(8, 5) = 21 [16 w/o offset]
+
 # We should be able to write up to 2^16-1 without triggering a 32-bit encoding.
 
 write
@@ -646,15 +683,18 @@ write
 0:1 1:63936 2:2957252
 ----
 
-size rows=(3)
+size rows=(3) offset=1
 ----
 b64:
-  64: *colblk.UintBuilder[uint64].Size(3, 0) = 20
+  64: *colblk.UintBuilder[uint64].Size(3, 1) = 24 [23 w/o offset]
 
-finish widths=(64) rows=3
+finish widths=(64) rows=3 offset=1
 ----
 b64: *colblk.UintBuilder[uint64]:
-00-08: x 0100000000000000 # 64-bit constant: 1
-08-12: x 00000000         # data[0] = 0
-12-16: x bff90000         # data[1] = 63935
-16-20: x c31f2d00         # data[2] = 2957251
+00-01: x 00               # artificial start offset
+01-09: x 0100000000000000 # 64-bit constant: 1
+# Padding
+09-12: x 000000           # aligning to 32-bit boundary
+12-16: x 00000000         # data[0] = 0
+16-20: x bff90000         # data[1] = 63935
+20-24: x c31f2d00         # data[2] = 2957251
diff --git a/sstable/colblk/uints_test.go b/sstable/colblk/uints_test.go
index 30ae0578..4a21d193 100644
--- a/sstable/colblk/uints_test.go
+++ b/sstable/colblk/uints_test.go
@@ -81,20 +81,29 @@ func TestUints(t *testing.T) {
 			}
 			return out.String()
 		case "size":
+			var offset uint32
 			var rowCounts []int
 			td.ScanArgs(t, "rows", &rowCounts)
+			td.MaybeScanArgs(t, "offset", &offset)
 			for wIdx, w := range writers {
 				fmt.Fprintf(&out, "b%d:\n", widths[wIdx])
 				for _, rows := range rowCounts {
-					fmt.Fprintf(&out, "  %d: %T.Size(%d, 0) = %d\n", widths[wIdx], w, rows, w.Size(rows, 0))
+					sz := w.Size(rows, offset)
+					if offset > 0 {
+						fmt.Fprintf(&out, "  %d: %T.Size(%d, %d) = %d [%d w/o offset]\n", widths[wIdx], w, rows, offset, sz, sz-offset)
+					} else {
+						fmt.Fprintf(&out, "  %d: %T.Size(%d, %d) = %d\n", widths[wIdx], w, rows, offset, sz)
+					}
 				}
 			}
 			return out.String()
 		case "finish":
 			var rows int
+			var offset uint32
 			var finishWidths []int
 			td.ScanArgs(t, "rows", &rows)
 			td.ScanArgs(t, "widths", &finishWidths)
+			td.MaybeScanArgs(t, "offset", &offset)
 			var newWriters []ColumnWriter
 			var newWidths []int
 			for wIdx, width := range widths {
@@ -103,11 +112,14 @@ func TestUints(t *testing.T) {
 					shouldFinish = shouldFinish || width == fw
 				}
 				if shouldFinish {
-					sz := writers[wIdx].Size(rows, 0)
+					sz := writers[wIdx].Size(rows, offset)
 					buf := aligned.ByteSlice(int(sz))
-					_, desc := writers[wIdx].Finish(0, rows, 0, buf)
+					_, desc := writers[wIdx].Finish(0, rows, offset, buf)
 					fmt.Fprintf(&out, "b%d: %T:\n", width, writers[wIdx])
 					f := binfmt.New(buf).LineWidth(20)
+					if offset > 0 {
+						f.HexBytesln(int(offset), "artificial start offset")
+					}
 					uintsToBinFormatter(f, rows, desc, nil)
 					fmt.Fprintf(&out, "%s", f.String())
 				} else {