You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@iceberg.apache.org by "rdblue (via GitHub)" <gi...@apache.org> on 2026/06/09 22:31:02 UTC
[PR] Core: Add a read-only Mumbling bitmap implementation [iceberg]
rdblue opened a new pull request, #16747:
URL: https://github.com/apache/iceberg/pull/16747
This is a simple implementation of Mumbling bitmap that has been proposed for embedded bitmaps in v4 metadata.
This implementation includes 3 main classes:
* `BitPacking`: bit packing and unpacking implementations for specific widths (1-7) used for descriptor encoding
* `PFOREncoding`: [patched frame-of-reference](https://github.com/apache/iceberg/blob/main/format/mumbling-spec.md#pfor-encoding) encoding and decoding for descriptor bytes
* `MumblingBitmap: a read-only implementation of Mumbling bitmap
Support for creating and modifying bitmaps will be added in later PRs, similar to the approach for variant where `SerializedValue` implementations were added first as a building block for mutable implementations.
This also includes a benchmark to compare the PFOR implementation to JavaFastPFOR. This is not a fair comparison because JavaFastPFOR is intended for large arrays and vectorization, but the use cases tested are very small arrays that don't benefit from vectorization and have high overhead. The reason for the benchmark is to show that it doesn't make sense to delegate to JavaFastPFOR for a small descriptor array. This benchmark probably won't be committed as it is now in the final version, but I wanted to make it available for reviewers.
Co-Authored-By: Claude Code (Opus 4.7, 1M context) <no...@anthropic.com>
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] Core: Add a read-only Mumbling bitmap implementation [iceberg]
Posted by "Fokko (via GitHub)" <gi...@apache.org>.
Fokko commented on code in PR #16747:
URL: https://github.com/apache/iceberg/pull/16747#discussion_r4025214669
##########
core/src/main/java/org/apache/iceberg/mumbling/PFOREncoding.java:
##########
@@ -0,0 +1,405 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.iceberg.mumbling;
+
+import java.nio.ByteBuffer;
+import org.apache.iceberg.relocated.com.google.common.base.Preconditions;
+import org.apache.iceberg.util.ByteBuffers;
+import org.apache.iceberg.util.Pair;
+
+/**
+ * Patched Frame of Reference (PFOR) encoding for arrays of unsigned byte values.
+ *
+ * <p>Implements the encoding described in Appendix A of the Mumbling bitmap specification. The
+ * input array is split into 256-value chunks (the last chunk may be shorter). Each chunk is
+ * independently encoded using 4 configuration values:
+ *
+ * <ul>
+ * <li>{@code b1}: number of bits stored in the primary array for every normalized value
+ * <li>{@code b2}: number of bits stored per exception value (normalized value of > b1 bits)
+ * <li>{@code e}: number of exceptions with more than b1 bits
+ * <li>{@code m}: chunk-local minimum value, subtracted from all values to normalize
+ * </ul>
+ *
+ * <p>Each chunk is stored as:
+ *
+ * <ul>
+ * <li>3-byte header: {@code b1|b2} primary and exception bit widths (byte 0), {@code e} exception
+ * count (byte 1), {@code m} normalization base value (byte 2)
+ * <li>Primary array: the low {@code b1} bits of every normalized value, packed MSB-first ({@code
+ * b1 * n} bits, padded to a byte)
+ * <li>Exception offsets: chunk-relative positions of exception values ({@code e} bytes)
+ * <li>Exception values: the high {@code b2} bits of every exception value, packed MSB-first
+ * ({@code e * b2} bits, padded to a byte.
+ * </ul>
+ */
+class PFOREncoding {
+ private static final int CHUNK_SIZE = 256;
+
+ private PFOREncoding() {}
+
+ /**
+ * Encodes {@code count} values from an array of unsigned byte values.
+ *
+ * @param values unsigned byte values to encode
+ * @param count number of values to encode
+ * @return a {@link ByteBuffer} of the encoded values with position and limit set for reading
+ */
+ static ByteBuffer encode(int[] values, int count) {
+ ByteBuffer out = ByteBuffer.allocate(estimateEncodedSize(count));
+ int bytesWritten = encode(values, 0, out, 0, count);
+ return out.slice(0, bytesWritten);
+ }
+
+ /**
+ * Encode {@code count} unsigned byte values from {@code values} into a buffer.
+ *
+ * <p>The buffer's position and limit are not modified.
+ *
+ * @param values unsigned byte values to encode
+ * @param valueOffset starting offset of values to encode
+ * @param out buffer to write encoded values to
+ * @param outOffset starting offset in the output buffer
+ * @param count number of values to encode
+ * @return the number of bytes written to the buffer
+ */
+ static int encode(int[] values, int valueOffset, ByteBuffer out, int outOffset, int count) {
+ // outOffset is relative to the buffer's position; check the encoded data fits
+ Preconditions.checkArgument(outOffset >= 0, "Cannot encode at negative offset: %s", outOffset);
+ Preconditions.checkArgument(
+ estimateEncodedSize(count) <= out.remaining() - outOffset,
+ "Cannot encode %s values to buffer with %s remaining space",
+ count,
+ out.remaining() - outOffset);
+
+ int bytesWritten = 0;
+ int valuesEncoded = 0;
+
+ while (valuesEncoded < count) {
+ int chunkLength = Math.min(CHUNK_SIZE, count - valuesEncoded);
+ bytesWritten +=
+ encodeChunk(
+ values, valueOffset + valuesEncoded, out, outOffset + bytesWritten, chunkLength);
+ valuesEncoded += chunkLength;
+ }
+
+ return bytesWritten;
+ }
+
+ /**
+ * Decode to produce unsigned byte values.
+ *
+ * <p>Decodes starting at {@code encoded.position()} and does not modify the input buffer.
+ *
+ * @param encoded PFOR-encoded ByteBuffer produced by {@link #encode}
+ * @param count total number of values to decode
+ * @return decoded unsigned byte values
+ */
+ static int[] decode(ByteBuffer encoded, int count) {
+ int[] out = new int[count];
+ decode(encoded, 0, out, 0, count);
+ return out;
+ }
+
+ /**
+ * Decode {@code count} unsigned bytes from a buffer into {@code out}.
+ *
+ * <p>This does not modify the input buffer.
+ *
+ * @param encoded a buffer containing encoded data
+ * @param offset starting offset of encoded values
+ * @param out an output value array
+ * @param outOffset starting offset in the output array
+ * @param count number of values to decode
+ * @return the number of bytes read from the encoded buffer
+ */
+ static int decode(ByteBuffer encoded, int offset, int[] out, int outOffset, int count) {
+ Preconditions.checkArgument(offset >= 0, "Cannot decode at negative offset: %s", offset);
+
+ int bytesRead = 0;
+ int valuesRead = 0;
+
+ while (valuesRead < count) {
+ int chunkSize = Math.min(CHUNK_SIZE, count - valuesRead);
+ bytesRead += decodeChunk(encoded, offset + bytesRead, out, outOffset + valuesRead, chunkSize);
+ valuesRead += chunkSize;
+ }
+
+ return bytesRead;
+ }
+
+ /**
+ * Encode one chunk into {@code out} starting at absolute position {@code outPos}.
+ *
+ * @param values array containing source values to encode
+ * @param valueOffset starting index of values to encode
+ * @param out an output {@link ByteBuffer}
+ * @param outOffset starting index for output in the out buffer
+ * @param count number of values to encode
+ * @return the number of bytes written to the output buffer
+ */
+ private static int encodeChunk(
+ int[] values, int valueOffset, ByteBuffer out, int outOffset, int count) {
+ Preconditions.checkArgument(count >= 0, "Invalid value count to encode: %s", count);
+ Preconditions.checkArgument(
+ valueOffset + count <= values.length,
+ "Cannot encode %s values starting at %s from int[%s]: not enough values",
+ count,
+ valueOffset,
+ values.length);
+
+ // find base=min(values) for normalization
+ int base = min(values, valueOffset, count);
+
+ // normalize by subtracting base
+ int[] normalized = new int[count];
+ int setBits = 0;
+ int normalizedSetBits = 0;
+ for (int i = 0; i < count; i += 1) {
+ setBits |= values[valueOffset + i];
+ normalized[i] = values[valueOffset + i] - base;
+ normalizedSetBits |= normalized[i];
+ }
+
+ Preconditions.checkArgument(
+ width(setBits) <= 8,
+ "Cannot encode values wider than 8 bits: %s bits needed",
+ width(setBits));
+
+ // Choose b1 to minimize total encoded data size (excluding 3-byte header)
+ int maxWidth = width(normalizedSetBits);
+ Pair<Integer, Integer> widthAndExcCount = chooseBitWidth(normalized, count, maxWidth);
+ int b1 = widthAndExcCount.first();
+ int b2 = maxWidth - b1;
+ int excCount = widthAndExcCount.second();
+
+ // check that there is enough space in the buffer for the encoded data
+ int requiredSize = encodedSize(count, b1, b2, excCount);
+ Preconditions.checkArgument(
+ outOffset + requiredSize <= out.remaining(),
+ "Cannot encode %s values (%s bytes) into buffer with %s remaining bytes",
+ count,
+ requiredSize,
+ out.remaining() - outOffset);
+
+ // Special case: b1=8 means store original values as raw bytes with b2, e, and m set to 0.
+ if (b1 == 8) {
+ writeHeader(out, outOffset, b1, 0 /* b2 */, 0 /* excCount */, 0 /* m */);
+ return 3 + BitPacking.packBits(8, values, valueOffset, out, outOffset + 3, count);
+ }
+
+ int bytesWritten = writeHeader(out, outOffset, b1, b2, excCount, base);
+
+ // Primary array: low b1 bits of every value
+ bytesWritten += BitPacking.packBits(b1, normalized, 0, out, outOffset + bytesWritten, count);
+
+ // b2 is the bit width of exception values: (maxWidth - b1) bits of each exception
+ if (excCount > 0) {
+ int[] excOffsets = new int[excCount];
+ int[] excValues = new int[excCount];
+
+ // Collect exceptions (values that do not fit in b1 bits)
+ int excIndex = 0;
+ int threshold = 1 << b1;
+ for (int i = 0; i < count; i += 1) {
+ if (normalized[i] >= threshold) {
+ excOffsets[excIndex] = i;
+ excValues[excIndex] = normalized[i] >>> b1;
+ excIndex += 1;
+ }
+ }
+
+ // Exception offsets (one byte per exception)
+ bytesWritten +=
+ BitPacking.packBits(8, excOffsets, 0, out, outOffset + bytesWritten, excCount);
+
+ // Exception values: remaining high b2 bits of each exception
+ bytesWritten +=
+ BitPacking.packBits(b2, excValues, 0, out, outOffset + bytesWritten, excCount);
+ }
+
+ return bytesWritten;
+ }
+
+ /**
+ * Decode one chunk of encoded data, writing decoded values into an output array.
+ *
+ * @param data buffer containing source data to decode
+ * @param dataOffset starting index in the buffer to decode
+ * @param out an output {@link ByteBuffer}
+ * @param outOffset starting index for output in the out buffer
+ * @param count number of values to decode
+ * @return the number of bytes read from {@code data}
+ */
+ private static int decodeChunk(
+ ByteBuffer data, int dataOffset, int[] out, int outOffset, int count) {
+ Preconditions.checkArgument(count >= 0, "Invalid value count to decode: %s", count);
+ Preconditions.checkArgument(
+ outOffset + count <= out.length,
+ "Cannot decode %s values starting at %s into int[%s]: not enough space",
+ count,
+ outOffset,
+ out.length);
+
+ int b1 = ByteBuffers.readByte(data, dataOffset) & 0x0F;
+ int b2 = (ByteBuffers.readByte(data, dataOffset) >>> 4) & 0x0F;
+ int excCount = ByteBuffers.readByte(data, dataOffset + 1);
+ int base = ByteBuffers.readByte(data, dataOffset + 2);
+ int bytesRead = 3;
+
+ // after reading the header, check that the full chunk is present
+ int expectedSize = encodedSize(count, b1, b2, excCount);
+ Preconditions.checkArgument(
+ dataOffset + expectedSize <= data.remaining(),
+ "Cannot decode %s values (%s bytes) from buffer with %s remaining bytes",
+ count,
+ expectedSize,
+ data.remaining() - dataOffset);
+
+ // Read primary array: low b1 bits of each value
+ bytesRead += BitPacking.unpackBits(b1, data, dataOffset + bytesRead, out, outOffset, count);
+
+ // Read exceptions and update output values
+ if (excCount > 0) {
+ int[] excOffsets = new int[excCount];
+ int[] excValues = new int[excCount];
+ int excListOffset = dataOffset + bytesRead;
+ int excDataOffset = dataOffset + bytesRead + excCount;
+
+ // Read exception indexes
+ bytesRead += BitPacking.unpackBits(8, data, excListOffset, excOffsets, 0, excCount);
+
+ // Read exception values and patch the primary values
+ bytesRead += BitPacking.unpackBits(b2, data, excDataOffset, excValues, 0, excCount);
+
+ // Update output values
+ for (int i = 0; i < excCount; i += 1) {
+ out[outOffset + excOffsets[i]] |= excValues[i] << b1;
+ }
+ }
+
+ // Add back the chunk minimum
+ for (int i = 0; i < count; i += 1) {
+ out[outOffset + i] += base;
+ }
+
+ return bytesRead;
+ }
+
+ private static int writeHeader(
+ ByteBuffer out, int outOffset, int b1, int b2, int excCount, int base) {
+ // Header: b1 in low nibble, b2 in high nibble, then e, then m
+ ByteBuffers.writeByte(out, (b2 << 4) | (b1 & 0b1111), outOffset);
+ ByteBuffers.writeByte(out, excCount, outOffset + 1);
+ ByteBuffers.writeByte(out, base, outOffset + 2);
+
+ return 3;
+ }
+
+ /**
+ * Choose the primary bit width {@code b1} that minimizes total encoded chunk size.
+ *
+ * <p>This produces the width that results in the smallest total size and the number of exceptions
+ * for that width.
+ *
+ * <p>Larger width is preferred on ties to reduce the number of exceptions.
+ *
+ * @param normalized value array to encode, after normalization
+ * @param length number of values in the array to encode
+ * @param maxWidth the largest bit width of normalized values
+ * @return a {@link Pair} of the chosen width and number of exceptions for that width
+ */
+ private static Pair<Integer, Integer> chooseBitWidth(int[] normalized, int length, int maxWidth) {
+ int bestWidth = 0;
+ int bestSize = Integer.MAX_VALUE;
+ int bestExcCount = 0;
+
+ for (int candidateWidth = 0; candidateWidth <= maxWidth; candidateWidth += 1) {
+ int excCount = 0;
+ if (candidateWidth < 8) {
+ int threshold = 1 << candidateWidth;
+ for (int i = 0; i < length; i += 1) {
+ if (normalized[i] >= threshold) {
+ excCount += 1;
+ }
+ }
+ }
+
+ int b2 = maxWidth - candidateWidth;
+ int size = byteWidth(length * candidateWidth) + excCount + byteWidth(excCount * b2);
+
+ if (size <= bestSize) {
+ bestSize = size;
+ bestWidth = candidateWidth;
+ bestExcCount = excCount;
+ }
+ }
+
+ return Pair.of(bestWidth, bestExcCount);
+ }
+
+ /**
+ * Return the lowest byte value from the array slice [start, start + length).
+ *
+ * <p>If length is < 1, the result will be larger than Byte.MAX_VALUE.
+ *
+ * @param values array of values
+ * @param start starting index
+ * @param length number of values to check
+ * @return the min of the values in the array slice
+ */
+ private static int min(int[] values, int start, int length) {
+ // Use min > Byte.MAX_VALUE to signal no min (length < 1)
+ int min = 256;
Review Comment:
Just wondering. Any reason to use 256, and not `Byte.MAX_VALUE + 1` (which equals 128)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] Core: Add a read-only Mumbling bitmap implementation [iceberg]
Posted by "nssalian (via GitHub)" <gi...@apache.org>.
nssalian commented on code in PR #16747:
URL: https://github.com/apache/iceberg/pull/16747#discussion_r4018337386
##########
core/src/main/java/org/apache/iceberg/mumbling/PFOREncoding.java:
##########
@@ -0,0 +1,402 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.iceberg.mumbling;
+
+import java.nio.ByteBuffer;
+import org.apache.iceberg.relocated.com.google.common.base.Preconditions;
+import org.apache.iceberg.util.ByteBuffers;
+import org.apache.iceberg.util.Pair;
+
+/**
+ * Patched Frame of Reference (PFOR) encoding for arrays of unsigned byte values.
+ *
+ * <p>Implements the encoding described in Appendix A of the Mumbling bitmap specification. The
+ * input array is split into 256-value chunks (the last chunk may be shorter). Each chunk is
+ * independently encoded using 4 configuration values:
+ *
+ * <ul>
+ * <li>{@code b1}: number of bits stored in the primary array for every normalized value
+ * <li>{@code b2}: number of bits stored per exception value (normalized value of > b1 bits)
+ * <li>{@code e}: number of exceptions with more than b1 bits
+ * <li>{@code m}: chunk-local minimum value, subtracted from all values to normalize
+ * </ul>
+ *
+ * <p>Each chunk is stored as:
+ *
+ * <ul>
+ * <li>3-byte header: {@code b1|b2} primary and exception bit widths (byte 0), {@code e} exception
+ * count (byte 1), {@code m} normalization base value (byte 2)
+ * <li>Primary array: the low {@code b1} bits of every normalized value, packed MSB-first ({@code
+ * b1 * n} bits, padded to a byte)
+ * <li>Exception offsets: chunk-relative positions of exception values ({@code e} bytes)
+ * <li>Exception values: the high {@code b2} bits of every exception value, packed MSB-first
+ * ({@code e * b2} bits, padded to a byte.
+ * </ul>
+ */
+class PFOREncoding {
+ private static final int CHUNK_SIZE = 256;
+
+ private PFOREncoding() {}
+
+ /**
+ * Encodes {@code count} values from an array of unsigned byte values.
+ *
+ * @param values unsigned byte values to encode
+ * @param count number of values to encode
+ * @return a {@link ByteBuffer} of the encoded values with position and limit set for reading
+ */
+ static ByteBuffer encode(int[] values, int count) {
+ ByteBuffer out = ByteBuffer.allocate(estimateEncodedSize(count));
+ int bytesWritten = encode(values, 0, out, 0, count);
+ return out.slice(0, bytesWritten);
+ }
+
+ /**
+ * Encode {@code count} unsigned byte values from {@code values} into a buffer.
+ *
+ * <p>The buffer's position and limit are not modified.
+ *
+ * @param values unsigned byte values to encode
+ * @param valueOffset starting offset of values to encode
+ * @param out buffer to write encoded values to
+ * @param outOffset starting offset in the output buffer
+ * @param count number of values to encode
+ * @return the number of bytes written to the buffer
+ */
+ static int encode(int[] values, int valueOffset, ByteBuffer out, int outOffset, int count) {
+ // outOffset is relative to the buffer's position; check the encoded data fits
+ Preconditions.checkArgument(outOffset >= 0, "Cannot encode at negative offset: %s", outOffset);
+ Preconditions.checkArgument(
+ estimateEncodedSize(count) <= out.remaining() - outOffset,
+ "Cannot encode %s values to buffer with %s remaining space",
+ count,
+ out.remaining() - outOffset);
+
+ int bytesWritten = 0;
+ int valuesEncoded = 0;
+
+ while (valuesEncoded < count) {
+ int chunkLength = Math.min(CHUNK_SIZE, count - valuesEncoded);
+ bytesWritten +=
+ encodeChunk(
+ values, valueOffset + valuesEncoded, out, outOffset + bytesWritten, chunkLength);
+ valuesEncoded += chunkLength;
+ }
+
+ return bytesWritten;
+ }
+
+ /**
+ * Decode to produce unsigned byte values.
+ *
+ * <p>Decodes starting at {@code encoded.position()} and does not modify the input buffer.
+ *
+ * @param encoded PFOR-encoded ByteBuffer produced by {@link #encode}
+ * @param count total number of values to decode
+ * @return decoded unsigned byte values
+ */
+ static int[] decode(ByteBuffer encoded, int count) {
+ int[] out = new int[count];
+ decode(encoded, 0, out, 0, count);
+ return out;
+ }
+
+ /**
+ * Decode {@code count} unsigned bytes from a buffer into {@code out}.
+ *
+ * <p>This does not modify the input buffer.
+ *
+ * @param encoded a buffer containing encoded data
+ * @param offset starting offset of encoded values
+ * @param out an output value array
+ * @param outOffset starting offset in the output array
+ * @param count number of values to decode
+ * @return the number of bytes read from the encoded buffer
+ */
+ static int decode(ByteBuffer encoded, int offset, int[] out, int outOffset, int count) {
+ Preconditions.checkArgument(offset >= 0, "Cannot decode at negative offset: %s", offset);
+
+ int bytesRead = 0;
+ int valuesRead = 0;
+
+ while (valuesRead < count) {
+ int chunkSize = Math.min(CHUNK_SIZE, count - valuesRead);
+ bytesRead += decodeChunk(encoded, offset + bytesRead, out, outOffset + valuesRead, chunkSize);
+ valuesRead += chunkSize;
+ }
+
+ return bytesRead;
+ }
+
+ /**
+ * Encode one chunk into {@code out} starting at absolute position {@code outPos}.
+ *
+ * @param values array containing source values to encode
+ * @param valueOffset starting index of values to encode
+ * @param out an output {@link ByteBuffer}
+ * @param outOffset starting index for output in the out buffer
+ * @param count number of values to encode
+ * @return the number of bytes written to the output buffer
+ */
+ private static int encodeChunk(
+ int[] values, int valueOffset, ByteBuffer out, int outOffset, int count) {
+ Preconditions.checkArgument(count >= 0, "Invalid value count to encode: %s", count);
+ Preconditions.checkArgument(
+ valueOffset + count <= values.length,
+ "Cannot encode %s values starting at %s from int[%s]: not enough values",
+ count,
+ valueOffset,
+ values.length);
+
+ // find base=min(values) for normalization
+ int base = min(values, valueOffset, count);
+
+ // normalize by subtracting base
+ int[] normalized = new int[count];
+ int setBits = 0;
+ int normalizedSetBits = 0;
+ for (int i = 0; i < count; i += 1) {
+ setBits |= values[valueOffset + i];
+ normalized[i] = values[valueOffset + i] - base;
+ normalizedSetBits |= normalized[i];
+ }
+
+ Preconditions.checkArgument(
+ width(setBits) <= 8,
+ "Cannot encode values wider than 8 bits: %s bits needed",
+ width(setBits));
+
+ // Choose b1 to minimize total encoded data size (excluding 3-byte header)
+ int maxWidth = width(normalizedSetBits);
+ Pair<Integer, Integer> widthAndExcCount = chooseBitWidth(normalized, count, maxWidth);
+ int b1 = widthAndExcCount.first();
+ int b2 = maxWidth - b1;
+ int excCount = widthAndExcCount.second();
+
+ // check that there is enough space in the buffer for the encoded data
+ int requiredSize = encodedSize(count, b1, b2, excCount);
+ Preconditions.checkArgument(
+ outOffset + requiredSize <= out.remaining(),
+ "Cannot encode %s values (%s bytes) into buffer with %s remaining bytes",
+ requiredSize,
+ out.remaining() - outOffset);
+
+ // Special case: b1=8 means store original values as raw bytes with b2, e, and m set to 0.
+ if (b1 == 8) {
+ writeHeader(out, outOffset, b1, 0 /* b2 */, 0 /* excCount */, 0 /* m */);
+ return 3 + BitPacking.packBits(8, values, valueOffset, out, outOffset + 3, count);
+ }
+
+ int bytesWritten = writeHeader(out, outOffset, b1, b2, excCount, base);
+
+ // Primary array: low b1 bits of every value
+ bytesWritten += BitPacking.packBits(b1, normalized, 0, out, outOffset + bytesWritten, count);
+
+ // b2 is the bit width of exception values: (maxWidth - b1) bits of each exception
+ if (excCount > 0) {
+ int[] excOffsets = new int[excCount];
+ int[] excValues = new int[excCount];
+
+ // Collect exceptions (values that do not fit in b1 bits)
+ int excIndex = 0;
+ int threshold = 1 << b1;
+ for (int i = 0; i < count; i += 1) {
+ if (normalized[i] >= threshold) {
+ excOffsets[excIndex] = i;
+ excValues[excIndex] = normalized[i] >>> b1;
+ excIndex += 1;
+ }
+ }
+
+ // Exception offsets (one byte per exception)
+ bytesWritten +=
+ BitPacking.packBits(8, excOffsets, 0, out, outOffset + bytesWritten, excCount);
+
+ // Exception values: remaining high b2 bits of each exception
+ bytesWritten +=
+ BitPacking.packBits(b2, excValues, 0, out, outOffset + bytesWritten, excCount);
+ }
+
+ return bytesWritten;
+ }
+
+ /**
+ * Decode one chunk of encoded data, writing decoded values into an output array.
+ *
+ * @param data buffer containing source data to decode
+ * @param dataOffset starting index in the buffer to decode
+ * @param out an output {@link ByteBuffer}
+ * @param outOffset starting index for output in the out buffer
+ * @param count number of values to decode
+ * @return the number of bytes read from {@code data}
+ */
+ private static int decodeChunk(
+ ByteBuffer data, int dataOffset, int[] out, int outOffset, int count) {
+ Preconditions.checkArgument(count >= 0, "Invalid value count to decode: %s", count);
+ Preconditions.checkArgument(
+ outOffset + count <= out.length,
+ "Cannot decode %s values starting at %s into int[%s]: not enough space",
+ count,
+ outOffset,
+ out.length);
+
+ int b1 = ByteBuffers.readByte(data, dataOffset) & 0x0F;
Review Comment:
Sounds good. The `IndexOutOfBoundsException` already points at the failing read. My only thought was consistency, the check below throws IllegalArgumentException for a short body, so a truncated header failing differently is a bit odd, but it's minor on a read-only reader, so your call. Won't block on this.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] Core: Add a read-only Mumbling bitmap implementation [iceberg]
Posted by "anoopj (via GitHub)" <gi...@apache.org>.
anoopj commented on code in PR #16747:
URL: https://github.com/apache/iceberg/pull/16747#discussion_r3754502044
##########
core/src/main/java/org/apache/iceberg/mumbling/BitPacking.java:
##########
@@ -0,0 +1,769 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.iceberg.mumbling;
+
+import java.nio.ByteBuffer;
+import org.apache.iceberg.util.ByteBuffers;
+
+/**
+ * Bit packing and unpacking for values of 1–7 bits.
+ *
+ * <p>The least-significant bits of each value are packed with the first value occupying the most
+ * significant bits of the output. Output is padded to the nearest byte with 0s. For example,
+ * packing values [0b11, 0b10, 0b01] with width 2 produces 0b11100100.
+ */
+class BitPacking {
+
+ private BitPacking() {}
+
+ /**
+ * Packs {@code width} least-significant bits of {@code count} values into a data buffer.
+ *
+ * <p>Output is padded to the nearest byte with 0s.
+ *
+ * <p>Values are written to the buffer's underlying storage, but the buffer's position and limit
+ * are not modified.
+ *
+ * @param width number of bits of each value to pack
+ * @param values array containing source values to pack
+ * @param valueOffset starting index of values to pack
+ * @param data an output {@link ByteBuffer}
+ * @param dataOffset starting index for output in the data buffer
+ * @param count the number of values to pack
+ * @return the number of bytes written to the data buffer
+ */
+ static int packBits(
Review Comment:
@rdblue
The bitpacking unroll code here is very complex (~700+ lines of dense code and hard to review). I have a couple of questions:
1. Does this have any impact on disk or memory footprint? Or is it purely about improving decoding speed?
2. If it's the latter, how much of a CPU impact does it make, given that our descriptor arrays tend to be small (hundreds of bytes)? I can see it will make a difference on larger arrays, which is not our use case for manifest DVs.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] Core: Add a read-only Mumbling bitmap implementation [iceberg]
Posted by "anoopj (via GitHub)" <gi...@apache.org>.
anoopj commented on code in PR #16747:
URL: https://github.com/apache/iceberg/pull/16747#discussion_r3754510708
##########
core/src/main/java/org/apache/iceberg/mumbling/BitPacking.java:
##########
@@ -0,0 +1,769 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.iceberg.mumbling;
+
+import java.nio.ByteBuffer;
+import org.apache.iceberg.util.ByteBuffers;
+
+/**
+ * Bit packing and unpacking for values of 1–7 bits.
+ *
+ * <p>The least-significant bits of each value are packed with the first value occupying the most
+ * significant bits of the output. Output is padded to the nearest byte with 0s. For example,
+ * packing values [0b11, 0b10, 0b01] with width 2 produces 0b11100100.
+ */
+class BitPacking {
+
+ private BitPacking() {}
+
+ /**
+ * Packs {@code width} least-significant bits of {@code count} values into a data buffer.
+ *
+ * <p>Output is padded to the nearest byte with 0s.
+ *
+ * <p>Values are written to the buffer's underlying storage, but the buffer's position and limit
+ * are not modified.
+ *
+ * @param width number of bits of each value to pack
+ * @param values array containing source values to pack
+ * @param valueOffset starting index of values to pack
+ * @param data an output {@link ByteBuffer}
+ * @param dataOffset starting index for output in the data buffer
+ * @param count the number of values to pack
+ * @return the number of bytes written to the data buffer
+ */
+ static int packBits(
Review Comment:
My understanding from a cursory code reading is that it should not affect the footprint - only the width selection in PFOREncoding class will affect it.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] Core: Add a read-only Mumbling bitmap implementation [iceberg]
Posted by "nssalian (via GitHub)" <gi...@apache.org>.
nssalian commented on code in PR #16747:
URL: https://github.com/apache/iceberg/pull/16747#discussion_r3746565474
##########
core/src/main/java/org/apache/iceberg/mumbling/MumblingBitmap.java:
##########
@@ -0,0 +1,168 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.iceberg.mumbling;
+
+import java.nio.ByteBuffer;
+import org.apache.iceberg.relocated.com.google.common.base.Preconditions;
+
+/**
+ * Read-only view of a Mumbling compressed bitmap stored in a {@link ByteBuffer}.
+ *
+ * <p>The bitmap is lazy: no decoding is done at construction time. On the first call to {@link
+ * #isSet}, the PFOR-encoded descriptor array is decoded and used to build an offsets array that
+ * maps each container index to its absolute byte position in the buffer. This offsets array is the
+ * only derived state kept by this class.
+ *
+ * <p>Format (all integers unsigned, little-endian):
+ *
+ * <ul>
+ * <li>Header (6 bytes): version (1), cardinality (3), container count (2)
+ * <li>Descriptor array: PFOR-encoded, one byte per container
+ * <li>Containers: concatenated sparse (0–31 bytes) or dense (32 bytes) containers
+ * </ul>
+ */
+class MumblingBitmap {
+ private static final int VERSION = 1;
+ private static final int HEADER_SIZE = 6;
+ private static final int DENSE_CONTAINER_BIT = 0b0010_0000;
+
+ private final ByteBuffer data;
+ private final int cardinality;
+ private final int containerCount;
+ private int[] descriptors = null;
+ private int[] offsets = null;
+
+ MumblingBitmap(ByteBuffer data) {
+ int version = data.get(data.position()) & 0xFF;
+ if (version != VERSION) {
+ throw new UnsupportedOperationException("Unsupported Mumbling bitmap version: " + version);
+ }
+
+ this.data = data;
+ this.cardinality =
+ (data.get(data.position() + 1) & 0xFF)
+ | ((data.get(data.position() + 2) & 0xFF) << 8)
+ | ((data.get(data.position() + 3) & 0xFF) << 16);
+ this.containerCount =
Review Comment:
The test builder already enforces the mumbling spec caps (container count <= 8192, cardinality <= 2,097,152).
Should we add a couple of Preconditions.checkArgument calls in the constructor here too?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] Core: Add a read-only Mumbling bitmap implementation [iceberg]
Posted by "rdblue (via GitHub)" <gi...@apache.org>.
rdblue commented on code in PR #16747:
URL: https://github.com/apache/iceberg/pull/16747#discussion_r4010470095
##########
core/src/main/java/org/apache/iceberg/mumbling/MumblingBitmap.java:
##########
@@ -0,0 +1,168 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.iceberg.mumbling;
+
+import java.nio.ByteBuffer;
+import org.apache.iceberg.relocated.com.google.common.base.Preconditions;
+
+/**
+ * Read-only view of a Mumbling compressed bitmap stored in a {@link ByteBuffer}.
+ *
+ * <p>The bitmap is lazy: no decoding is done at construction time. On the first call to {@link
+ * #isSet}, the PFOR-encoded descriptor array is decoded and used to build an offsets array that
+ * maps each container index to its absolute byte position in the buffer. This offsets array is the
+ * only derived state kept by this class.
+ *
+ * <p>Format (all integers unsigned, little-endian):
+ *
+ * <ul>
+ * <li>Header (6 bytes): version (1), cardinality (3), container count (2)
+ * <li>Descriptor array: PFOR-encoded, one byte per container
+ * <li>Containers: concatenated sparse (0–31 bytes) or dense (32 bytes) containers
+ * </ul>
+ */
+class MumblingBitmap {
+ private static final int VERSION = 1;
+ private static final int HEADER_SIZE = 6;
+ private static final int DENSE_CONTAINER_BIT = 0b0010_0000;
+
+ private final ByteBuffer data;
+ private final int cardinality;
+ private final int containerCount;
+ private int[] descriptors = null;
+ private int[] offsets = null;
+
+ MumblingBitmap(ByteBuffer data) {
+ int version = data.get(data.position()) & 0xFF;
+ if (version != VERSION) {
+ throw new UnsupportedOperationException("Unsupported Mumbling bitmap version: " + version);
+ }
+
+ this.data = data;
+ this.cardinality =
+ (data.get(data.position() + 1) & 0xFF)
+ | ((data.get(data.position() + 2) & 0xFF) << 8)
+ | ((data.get(data.position() + 3) & 0xFF) << 16);
+ this.containerCount =
Review Comment:
It's a good idea to verify these, at least in the reference implementation.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] Core: Add a read-only Mumbling bitmap implementation [iceberg]
Posted by "rdblue (via GitHub)" <gi...@apache.org>.
rdblue commented on code in PR #16747:
URL: https://github.com/apache/iceberg/pull/16747#discussion_r4010738989
##########
core/src/main/java/org/apache/iceberg/mumbling/MumblingBitmap.java:
##########
@@ -0,0 +1,168 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.iceberg.mumbling;
+
+import java.nio.ByteBuffer;
+import org.apache.iceberg.relocated.com.google.common.base.Preconditions;
+
+/**
+ * Read-only view of a Mumbling compressed bitmap stored in a {@link ByteBuffer}.
+ *
+ * <p>The bitmap is lazy: no decoding is done at construction time. On the first call to {@link
+ * #isSet}, the PFOR-encoded descriptor array is decoded and used to build an offsets array that
+ * maps each container index to its absolute byte position in the buffer. This offsets array is the
+ * only derived state kept by this class.
+ *
+ * <p>Format (all integers unsigned, little-endian):
+ *
+ * <ul>
+ * <li>Header (6 bytes): version (1), cardinality (3), container count (2)
+ * <li>Descriptor array: PFOR-encoded, one byte per container
+ * <li>Containers: concatenated sparse (0–31 bytes) or dense (32 bytes) containers
+ * </ul>
+ */
+class MumblingBitmap {
+ private static final int VERSION = 1;
+ private static final int HEADER_SIZE = 6;
+ private static final int DENSE_CONTAINER_BIT = 0b0010_0000;
+
+ private final ByteBuffer data;
+ private final int cardinality;
+ private final int containerCount;
+ private int[] descriptors = null;
+ private int[] offsets = null;
Review Comment:
It seems like overkill to me to make these thread safe. I'm trying to decide whether this is a good idea or if we would just introduce locking and `volatile` when it is never used across threads.
Maybe we should at least update these arrays at once, after they are initialized? That seems reasonable?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] Core: Add a read-only Mumbling bitmap implementation [iceberg]
Posted by "rdblue (via GitHub)" <gi...@apache.org>.
rdblue commented on PR #16747:
URL: https://github.com/apache/iceberg/pull/16747#issuecomment-5689911897
Removed the benchmark that isn't intended to be part of the codebase. When tests are passing, I'll merge.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] Core: Add a read-only Mumbling bitmap implementation [iceberg]
Posted by "rdblue (via GitHub)" <gi...@apache.org>.
rdblue commented on PR #16747:
URL: https://github.com/apache/iceberg/pull/16747#issuecomment-5689867652
Thanks for the reviews, everyone! I'm going to get this in so we can wire it up the V4ManifestReader.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] Core: Add a read-only Mumbling bitmap implementation [iceberg]
Posted by "nssalian (via GitHub)" <gi...@apache.org>.
nssalian commented on PR #16747:
URL: https://github.com/apache/iceberg/pull/16747#issuecomment-5236254544
Ran `PFOREncodingBenchmark` that was added here, on an Apple M4 Max (throughput, 5 iterations). At the small descriptor-array sizes Mumbling uses, the Iceberg PFOR codec is much faster than JavaFastPFOR - decode ~126-191x, encode ~10-17x:
| benchmark | Iceberg PFOR | JavaFastPFOR |
|---|---|---|
| decode descriptor | 12.55M ops/s | 100k ops/s |
| decode uniform | 18.91M ops/s | 99k ops/s |
| encode descriptor | 949k ops/s | 96k ops/s |
| encode uniform | 1.66M ops/s | 97k ops/s |
I also ported the codec to iceberg-go and it decodes the same fixtures.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] Core: Add a read-only Mumbling bitmap implementation [iceberg]
Posted by "rdblue (via GitHub)" <gi...@apache.org>.
rdblue commented on code in PR #16747:
URL: https://github.com/apache/iceberg/pull/16747#discussion_r4010600018
##########
core/src/main/java/org/apache/iceberg/mumbling/BitPacking.java:
##########
@@ -0,0 +1,769 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.iceberg.mumbling;
+
+import java.nio.ByteBuffer;
+import org.apache.iceberg.util.ByteBuffers;
+
+/**
+ * Bit packing and unpacking for values of 1–7 bits.
+ *
+ * <p>The least-significant bits of each value are packed with the first value occupying the most
+ * significant bits of the output. Output is padded to the nearest byte with 0s. For example,
+ * packing values [0b11, 0b10, 0b01] with width 2 produces 0b11100100.
+ */
+class BitPacking {
+
+ private BitPacking() {}
+
+ /**
+ * Packs {@code width} least-significant bits of {@code count} values into a data buffer.
+ *
+ * <p>Output is padded to the nearest byte with 0s.
+ *
+ * <p>Values are written to the buffer's underlying storage, but the buffer's position and limit
+ * are not modified.
+ *
+ * @param width number of bits of each value to pack
+ * @param values array containing source values to pack
+ * @param valueOffset starting index of values to pack
+ * @param data an output {@link ByteBuffer}
+ * @param dataOffset starting index for output in the data buffer
+ * @param count the number of values to pack
+ * @return the number of bytes written to the data buffer
+ */
+ static int packBits(
Review Comment:
I did it this way because I think it's easier to read and verify, and we only need to do that once.
For example, we can break down the 3-bit pack method, starting with `packWord3`:
```
private static int packWord3(int a, int b, int c, int d, int e, int f, int g, int h) {
return ((a & 0b111) << 21)
| ((b & 0b111) << 18)
| ((c & 0b111) << 15)
| ((d & 0b111) << 12)
| ((e & 0b111) << 9)
| ((f & 0b111) << 6)
| ((g & 0b111) << 3)
| (h & 0b111);
}
```
This method packs the least-significant 3 bits of 8 values into 3 bytes. It's easy to see the order of values and the offset each one uses. I think that's easier to read than a loop that keeps adding 3 and uses variables like `mask = (0b1 << width) - 1`.
Then for the array pack method:
```
int fullGroups = count / 8;
int remaining = count % 8;
```
This is common to each pack method and breaks the values into groups of 8 for use with the `packWord` method.
```
for (int group = 0; group < fullGroups; group += 1) {
int groupOffset = valueOffset + 8 * group;
int outputOffset = dataOffset + 3 * group;
int word = packWord3(values[groupOffset], ..., values[groupOffset + 7]);
ByteBuffers.writeByte(data, word >>> 16, outputOffset);
ByteBuffers.writeByte(data, word >>> 8, outputOffset + 1);
ByteBuffers.writeByte(data, word, outputOffset + 2);
}
```
This packs all of the full groups of 8 values. The hardest thing is the offset tracking, which skips by 8 values for each group and 3 bytes for each group's output in the data buffer. The values are all passed to `packWord3` that produces an `int` with the 3 packed bytes.
This then writes the packed bytes into the data buffer. I think this makes it easy to see the bits that are used from the int.
```
if (remaining > 0) {
int groupOffset = valueOffset + 8 * fullGroups;
int outputOffset = dataOffset + 3 * fullGroups;
int word =
packWord3(
values[groupOffset],
remaining > 1 ? values[groupOffset + 1] : 0,
remaining > 2 ? values[groupOffset + 2] : 0,
remaining > 3 ? values[groupOffset + 3] : 0,
remaining > 4 ? values[groupOffset + 4] : 0,
remaining > 5 ? values[groupOffset + 5] : 0,
remaining > 6 ? values[groupOffset + 6] : 0,
0);
int byteCount = byteWidth(3 * remaining);
for (int k = 0; k < byteCount; k += 1) {
ByteBuffers.writeByte(data, word >>> (16 - 8 * k), outputOffset + k);
}
}
```
This handles the remaining values of the last partial group. Each value is replaced with 0 when packing to a word, if it is not present in the data.
After packing, the bytes of the value are written to the data buffer. This is a little tricky because it uses a loop to write the first 1 or 2 bytes if the third byte isn't used. However, since it mirrors the `writeByte` calls above, I think it's more understandable. `(16 - 8 * k)` is the shift; first 16, then 8, then 0 just like the first section.
```
return byteWidth(3 * count);
```
Finally, this returns the actual bytes written.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] Core: Add a read-only Mumbling bitmap implementation [iceberg]
Posted by "rdblue (via GitHub)" <gi...@apache.org>.
rdblue commented on code in PR #16747:
URL: https://github.com/apache/iceberg/pull/16747#discussion_r4010700571
##########
core/src/test/java/org/apache/iceberg/mumbling/TestMumblingBitmap.java:
##########
@@ -0,0 +1,352 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.iceberg.mumbling;
+
+import static org.assertj.core.api.Assertions.assertThat;
+import static org.assertj.core.api.Assertions.assertThatThrownBy;
+
+import java.nio.ByteBuffer;
+import java.util.Arrays;
+import org.apache.iceberg.relocated.com.google.common.base.Preconditions;
+import org.junit.jupiter.api.Test;
+
+class TestMumblingBitmap {
+
+ @Test
+ void testEmptyBitmap() {
+ MumblingBitmap bitmap = bitmap();
+ assertThat(bitmap.cardinality()).isEqualTo(0);
+
+ // all positions beyond the bitmap range are false
+ assertThat(bitmap.isSet(0)).isFalse();
+ assertThat(bitmap.isSet(255)).isFalse();
+ assertThat(bitmap.isSet(256)).isFalse();
+ }
+
+ @Test
+ void testInvalidPosition() {
+ MumblingBitmap bitmap = bitmap();
+ assertThat(bitmap.cardinality()).isEqualTo(0);
+ assertThat(bitmap.isSet(0)).isFalse();
+ assertThatThrownBy(() -> bitmap.isSet(-1))
+ .isInstanceOf(IllegalArgumentException.class)
+ .hasMessage("Invalid bit position: -1 < 0");
+ }
+
+ @Test
+ void testEmptySparseContainer() {
+ MumblingBitmap bitmap = bitmap(sparse());
+ assertThat(bitmap.cardinality()).isEqualTo(0);
+ assertThat(bitmap.isSet(0)).isFalse();
+ assertThat(bitmap.isSet(100)).isFalse();
+ assertThat(bitmap.isSet(255)).isFalse();
+ }
+
+ @Test
+ void testSparseContainerSetPositions() {
+ MumblingBitmap bitmap = bitmap(sparse(0, 5, 100, 255));
+ assertThat(bitmap.cardinality()).isEqualTo(4);
+
+ assertThat(bitmap.isSet(0)).isTrue();
+ assertThat(bitmap.isSet(5)).isTrue();
+ assertThat(bitmap.isSet(100)).isTrue();
+ assertThat(bitmap.isSet(255)).isTrue();
+
+ assertThat(bitmap.isSet(1)).isFalse();
+ assertThat(bitmap.isSet(4)).isFalse();
+ assertThat(bitmap.isSet(6)).isFalse();
+ assertThat(bitmap.isSet(99)).isFalse();
+ assertThat(bitmap.isSet(101)).isFalse();
+ assertThat(bitmap.isSet(254)).isFalse();
+ assertThat(bitmap.isSet(256)).isFalse();
+ }
+
+ @Test
+ void testFullSparseContainer() {
+ int[] positions = new int[31];
+ for (int i = 0; i < 31; i += 1) {
+ positions[i] = i * 8; // 0, 8, 16, ..., 240
+ }
+
+ MumblingBitmap bitmap = bitmap(sparse(positions));
+ assertThat(bitmap.cardinality()).isEqualTo(31);
+
+ for (int p : positions) {
+ assertThat(bitmap.isSet(p)).isTrue();
+ }
+
+ assertThat(bitmap.isSet(1)).isFalse();
+ assertThat(bitmap.isSet(7)).isFalse();
+ assertThat(bitmap.isSet(255)).isFalse();
+ }
+
+ @Test
+ void testFullDenseContainer() {
+ byte[] container = new byte[32];
+ Arrays.fill(container, (byte) 0xFF);
+
+ MumblingBitmap bitmap = bitmap(dense(container));
+ assertThat(bitmap.cardinality()).isEqualTo(256);
+
+ for (int i = 0; i < 256; i += 1) {
+ assertThat(bitmap.isSet(i)).isTrue();
+ }
+
+ assertThat(bitmap.isSet(256)).isFalse();
+ }
+
+ // Example 1: positions 0-31: `FF FF FF FF 00 ... 00`
+ @Test
+ void testDenseSpecExample1() {
+ byte[] container = new byte[32];
+ container[0] = (byte) 0xFF;
+ container[1] = (byte) 0xFF;
+ container[2] = (byte) 0xFF;
+ container[3] = (byte) 0xFF;
+ MumblingBitmap bitmap = bitmap(dense(container));
+ assertThat(bitmap.cardinality()).isEqualTo(32);
+
+ for (int i = 0; i <= 31; i += 1) {
+ assertThat(bitmap.isSet(i)).isTrue();
+ }
+
+ assertThat(bitmap.isSet(32)).isFalse();
+ assertThat(bitmap.isSet(255)).isFalse();
+ }
+
+ // Example 2: positions 0-32: `FF FF FF FF 80 00 ... 00`
+ @Test
+ void testDenseSpecExample2() {
+ byte[] container = new byte[32];
+ container[0] = (byte) 0xFF;
+ container[1] = (byte) 0xFF;
+ container[2] = (byte) 0xFF;
+ container[3] = (byte) 0xFF;
+ container[4] = (byte) 0x80;
+
+ MumblingBitmap bitmap = bitmap(dense(container));
+ assertThat(bitmap.cardinality()).isEqualTo(33);
+
+ for (int i = 0; i <= 32; i += 1) {
+ assertThat(bitmap.isSet(i)).isTrue();
+ }
+
+ assertThat(bitmap.isSet(33)).isFalse();
+ assertThat(bitmap.isSet(255)).isFalse();
+ }
+
+ // Example 3: positions 0-15 and 240-255: `FF FF 00 ... 00 FF FF`
+ @Test
+ void testDenseSpecExample3() {
+ byte[] container = new byte[32];
+ container[0] = (byte) 0xFF;
+ container[1] = (byte) 0xFF;
+ container[30] = (byte) 0xFF;
+ container[31] = (byte) 0xFF;
+
+ MumblingBitmap bitmap = bitmap(dense(container));
+ assertThat(bitmap.cardinality()).isEqualTo(32);
+
+ for (int i = 0; i <= 15; i += 1) {
+ assertThat(bitmap.isSet(i)).isTrue();
+ }
+ for (int i = 240; i <= 255; i += 1) {
+ assertThat(bitmap.isSet(i)).isTrue();
+ }
+ assertThat(bitmap.isSet(16)).isFalse();
+ assertThat(bitmap.isSet(239)).isFalse();
+ assertThat(bitmap.isSet(256)).isFalse();
+ }
+
+ // Example 4: even positions 0, 2, 4, ...: `AA AA ... AA AA`
+ @Test
+ void testDenseSpecExample4() {
+ byte[] container = new byte[32];
+ Arrays.fill(container, (byte) 0xAA);
+
+ MumblingBitmap bitmap = bitmap(dense(container));
+ assertThat(bitmap.cardinality()).isEqualTo(128);
+
+ for (int i = 0; i < 256; i += 1) {
+ assertThat(bitmap.isSet(i)).isEqualTo(i % 2 == 0);
+ }
+
+ assertThat(bitmap.isSet(256)).isFalse();
+ }
+
+ @Test
+ void testMultipleContainers() {
+ MumblingBitmap bitmap = bitmap(sparse(5), sparse(), sparse(10));
+ assertThat(bitmap.cardinality()).isEqualTo(2);
+
+ assertThat(bitmap.isSet(5)).isTrue(); // container 0, pos 5
+ assertThat(bitmap.isSet(256)).isFalse(); // container 1
+ assertThat(bitmap.isSet(522)).isTrue(); // container 2, pos 10
+
+ assertThat(bitmap.isSet(512)).isFalse();
+ assertThat(bitmap.isSet(4)).isFalse();
+ assertThat(bitmap.isSet(265)).isFalse();
+ assertThat(bitmap.isSet(267)).isFalse();
+ }
+
+ @Test
+ void testMixedSparseAndDense() {
Review Comment:
Added.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] Core: Add a read-only Mumbling bitmap implementation [iceberg]
Posted by "amogh-jahagirdar (via GitHub)" <gi...@apache.org>.
amogh-jahagirdar commented on PR #16747:
URL: https://github.com/apache/iceberg/pull/16747#issuecomment-5665744398
Thanks @rdblue logically I think this correctly implements the spec, just had some questions around test coverage and avoiding a possible concurrency issue.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] Core: Add a read-only Mumbling bitmap implementation [iceberg]
Posted by "rdblue (via GitHub)" <gi...@apache.org>.
rdblue commented on code in PR #16747:
URL: https://github.com/apache/iceberg/pull/16747#discussion_r4010724310
##########
core/src/test/java/org/apache/iceberg/mumbling/TestMumblingBitmap.java:
##########
@@ -0,0 +1,352 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.iceberg.mumbling;
+
+import static org.assertj.core.api.Assertions.assertThat;
+import static org.assertj.core.api.Assertions.assertThatThrownBy;
+
+import java.nio.ByteBuffer;
+import java.util.Arrays;
+import org.apache.iceberg.relocated.com.google.common.base.Preconditions;
+import org.junit.jupiter.api.Test;
+
+class TestMumblingBitmap {
+
+ @Test
+ void testEmptyBitmap() {
+ MumblingBitmap bitmap = bitmap();
+ assertThat(bitmap.cardinality()).isEqualTo(0);
+
+ // all positions beyond the bitmap range are false
+ assertThat(bitmap.isSet(0)).isFalse();
+ assertThat(bitmap.isSet(255)).isFalse();
+ assertThat(bitmap.isSet(256)).isFalse();
+ }
+
+ @Test
+ void testInvalidPosition() {
+ MumblingBitmap bitmap = bitmap();
+ assertThat(bitmap.cardinality()).isEqualTo(0);
+ assertThat(bitmap.isSet(0)).isFalse();
+ assertThatThrownBy(() -> bitmap.isSet(-1))
+ .isInstanceOf(IllegalArgumentException.class)
+ .hasMessage("Invalid bit position: -1 < 0");
+ }
+
+ @Test
+ void testEmptySparseContainer() {
+ MumblingBitmap bitmap = bitmap(sparse());
+ assertThat(bitmap.cardinality()).isEqualTo(0);
+ assertThat(bitmap.isSet(0)).isFalse();
+ assertThat(bitmap.isSet(100)).isFalse();
+ assertThat(bitmap.isSet(255)).isFalse();
+ }
+
+ @Test
+ void testSparseContainerSetPositions() {
+ MumblingBitmap bitmap = bitmap(sparse(0, 5, 100, 255));
+ assertThat(bitmap.cardinality()).isEqualTo(4);
+
+ assertThat(bitmap.isSet(0)).isTrue();
+ assertThat(bitmap.isSet(5)).isTrue();
+ assertThat(bitmap.isSet(100)).isTrue();
+ assertThat(bitmap.isSet(255)).isTrue();
+
+ assertThat(bitmap.isSet(1)).isFalse();
+ assertThat(bitmap.isSet(4)).isFalse();
+ assertThat(bitmap.isSet(6)).isFalse();
+ assertThat(bitmap.isSet(99)).isFalse();
+ assertThat(bitmap.isSet(101)).isFalse();
+ assertThat(bitmap.isSet(254)).isFalse();
+ assertThat(bitmap.isSet(256)).isFalse();
+ }
+
+ @Test
+ void testFullSparseContainer() {
+ int[] positions = new int[31];
+ for (int i = 0; i < 31; i += 1) {
+ positions[i] = i * 8; // 0, 8, 16, ..., 240
+ }
+
+ MumblingBitmap bitmap = bitmap(sparse(positions));
+ assertThat(bitmap.cardinality()).isEqualTo(31);
+
+ for (int p : positions) {
+ assertThat(bitmap.isSet(p)).isTrue();
+ }
+
+ assertThat(bitmap.isSet(1)).isFalse();
+ assertThat(bitmap.isSet(7)).isFalse();
+ assertThat(bitmap.isSet(255)).isFalse();
+ }
+
+ @Test
+ void testFullDenseContainer() {
+ byte[] container = new byte[32];
+ Arrays.fill(container, (byte) 0xFF);
+
+ MumblingBitmap bitmap = bitmap(dense(container));
+ assertThat(bitmap.cardinality()).isEqualTo(256);
+
+ for (int i = 0; i < 256; i += 1) {
+ assertThat(bitmap.isSet(i)).isTrue();
+ }
+
+ assertThat(bitmap.isSet(256)).isFalse();
+ }
+
+ // Example 1: positions 0-31: `FF FF FF FF 00 ... 00`
+ @Test
+ void testDenseSpecExample1() {
+ byte[] container = new byte[32];
+ container[0] = (byte) 0xFF;
+ container[1] = (byte) 0xFF;
+ container[2] = (byte) 0xFF;
+ container[3] = (byte) 0xFF;
+ MumblingBitmap bitmap = bitmap(dense(container));
+ assertThat(bitmap.cardinality()).isEqualTo(32);
+
+ for (int i = 0; i <= 31; i += 1) {
+ assertThat(bitmap.isSet(i)).isTrue();
+ }
+
+ assertThat(bitmap.isSet(32)).isFalse();
+ assertThat(bitmap.isSet(255)).isFalse();
+ }
+
+ // Example 2: positions 0-32: `FF FF FF FF 80 00 ... 00`
+ @Test
+ void testDenseSpecExample2() {
+ byte[] container = new byte[32];
+ container[0] = (byte) 0xFF;
+ container[1] = (byte) 0xFF;
+ container[2] = (byte) 0xFF;
+ container[3] = (byte) 0xFF;
+ container[4] = (byte) 0x80;
+
+ MumblingBitmap bitmap = bitmap(dense(container));
+ assertThat(bitmap.cardinality()).isEqualTo(33);
+
+ for (int i = 0; i <= 32; i += 1) {
+ assertThat(bitmap.isSet(i)).isTrue();
+ }
+
+ assertThat(bitmap.isSet(33)).isFalse();
+ assertThat(bitmap.isSet(255)).isFalse();
+ }
+
+ // Example 3: positions 0-15 and 240-255: `FF FF 00 ... 00 FF FF`
+ @Test
+ void testDenseSpecExample3() {
+ byte[] container = new byte[32];
+ container[0] = (byte) 0xFF;
+ container[1] = (byte) 0xFF;
+ container[30] = (byte) 0xFF;
+ container[31] = (byte) 0xFF;
+
+ MumblingBitmap bitmap = bitmap(dense(container));
+ assertThat(bitmap.cardinality()).isEqualTo(32);
+
+ for (int i = 0; i <= 15; i += 1) {
+ assertThat(bitmap.isSet(i)).isTrue();
+ }
+ for (int i = 240; i <= 255; i += 1) {
+ assertThat(bitmap.isSet(i)).isTrue();
+ }
+ assertThat(bitmap.isSet(16)).isFalse();
+ assertThat(bitmap.isSet(239)).isFalse();
+ assertThat(bitmap.isSet(256)).isFalse();
+ }
+
+ // Example 4: even positions 0, 2, 4, ...: `AA AA ... AA AA`
+ @Test
+ void testDenseSpecExample4() {
+ byte[] container = new byte[32];
+ Arrays.fill(container, (byte) 0xAA);
+
+ MumblingBitmap bitmap = bitmap(dense(container));
+ assertThat(bitmap.cardinality()).isEqualTo(128);
+
+ for (int i = 0; i < 256; i += 1) {
+ assertThat(bitmap.isSet(i)).isEqualTo(i % 2 == 0);
+ }
+
+ assertThat(bitmap.isSet(256)).isFalse();
+ }
+
+ @Test
+ void testMultipleContainers() {
+ MumblingBitmap bitmap = bitmap(sparse(5), sparse(), sparse(10));
+ assertThat(bitmap.cardinality()).isEqualTo(2);
+
+ assertThat(bitmap.isSet(5)).isTrue(); // container 0, pos 5
+ assertThat(bitmap.isSet(256)).isFalse(); // container 1
+ assertThat(bitmap.isSet(522)).isTrue(); // container 2, pos 10
+
+ assertThat(bitmap.isSet(512)).isFalse();
+ assertThat(bitmap.isSet(4)).isFalse();
+ assertThat(bitmap.isSet(265)).isFalse();
+ assertThat(bitmap.isSet(267)).isFalse();
+ }
+
+ @Test
+ void testMixedSparseAndDense() {
+ byte[] denseContainer = new byte[32];
+ denseContainer[0] = (byte) 0xFF;
+ denseContainer[1] = (byte) 0xFF;
+ denseContainer[2] = (byte) 0xFF;
+ denseContainer[3] = (byte) 0xFF;
+
+ MumblingBitmap bitmap = bitmap(dense(denseContainer), sparse(1));
+ assertThat(bitmap.cardinality()).isEqualTo(33);
+
+ for (int i = 0; i < 32; i += 1) {
+ assertThat(bitmap.isSet(i)).isTrue();
+ }
+ assertThat(bitmap.isSet(32)).isFalse();
+
+ assertThat(bitmap.isSet(256)).isFalse();
+ assertThat(bitmap.isSet(257)).isTrue(); // container 1, pos 1
+ assertThat(bitmap.isSet(258)).isFalse();
+ }
+
+ @Test
+ void testBufferWithOffset() {
+ // Prepend 4 bytes of garbage before the actual bitmap data
+ ByteBuffer buffer = build(sparse(42));
+ byte[] rawBytes = new byte[buffer.remaining()];
+ buffer.get(rawBytes);
+
+ ByteBuffer padded = ByteBuffer.allocate(4 + rawBytes.length);
+ padded.position(4);
+ padded.put(rawBytes);
+ padded.position(4); // position the buffer at the start of bitmap data
+
+ MumblingBitmap bitmap = new MumblingBitmap(padded);
+ assertThat(bitmap.cardinality()).isEqualTo(1);
+
+ assertThat(bitmap.isSet(41)).isFalse();
+ assertThat(bitmap.isSet(42)).isTrue();
+ assertThat(bitmap.isSet(43)).isFalse();
+ }
+
+ private static Container sparse(int... positions) {
+ byte[] bytes = new byte[positions.length];
+ for (int i = 0; i < positions.length; i += 1) {
+ if (i > 0) {
+ Preconditions.checkArgument(
+ positions[i] < 256, "Invalid position in container: %s", positions[i]);
+ Preconditions.checkArgument(
+ positions[i] > positions[i - 1],
+ "Invalid sparse container: pos %s=%s >= pos %s=%s",
+ i - 1,
+ positions[i - 1],
+ i,
+ positions[i]);
+ }
+
+ bytes[i] = (byte) positions[i];
+ }
+
+ return new Container(bytes);
+ }
+
+ /** Descriptor + bytes for a dense container. */
+ private static Container dense(byte[] container) {
+ Preconditions.checkArgument(container.length == 32, "Dense container must be 32 bytes");
+ return new Container(container);
+ }
+
+ private static class Container {
+ private final byte[] bytes;
+ private final int descriptor;
+ private final int cardinality;
+
+ Container(byte[] bytes) {
+ this.bytes = bytes;
+ this.descriptor = bytes.length;
Review Comment:
I just updated the logic based on @nssalian's comment that the container is either sparse (< 32) or dense (= 0x20). I think this is a good idea so that we don't accept invalid descriptors.
As for the spec wording here, I think maybe we should just remove it. We may want to use those bits for a dense container later, but that would require a version bump. It also says that those bits must be 0. Implementations should probably make the decision about whether to ignore them or not, but the reference implementation should check that they are 0s.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] Core: Add a read-only Mumbling bitmap implementation [iceberg]
Posted by "rdblue (via GitHub)" <gi...@apache.org>.
rdblue commented on code in PR #16747:
URL: https://github.com/apache/iceberg/pull/16747#discussion_r4018167245
##########
core/src/main/java/org/apache/iceberg/mumbling/MumblingBitmap.java:
##########
@@ -0,0 +1,168 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.iceberg.mumbling;
+
+import java.nio.ByteBuffer;
+import org.apache.iceberg.relocated.com.google.common.base.Preconditions;
+
+/**
+ * Read-only view of a Mumbling compressed bitmap stored in a {@link ByteBuffer}.
+ *
+ * <p>The bitmap is lazy: no decoding is done at construction time. On the first call to {@link
+ * #isSet}, the PFOR-encoded descriptor array is decoded and used to build an offsets array that
+ * maps each container index to its absolute byte position in the buffer. This offsets array is the
+ * only derived state kept by this class.
+ *
+ * <p>Format (all integers unsigned, little-endian):
+ *
+ * <ul>
+ * <li>Header (6 bytes): version (1), cardinality (3), container count (2)
+ * <li>Descriptor array: PFOR-encoded, one byte per container
+ * <li>Containers: concatenated sparse (0–31 bytes) or dense (32 bytes) containers
+ * </ul>
+ */
+class MumblingBitmap {
+ private static final int VERSION = 1;
+ private static final int HEADER_SIZE = 6;
+ private static final int DENSE_CONTAINER_BIT = 0b0010_0000;
+
+ private final ByteBuffer data;
+ private final int cardinality;
+ private final int containerCount;
+ private int[] descriptors = null;
+ private int[] offsets = null;
Review Comment:
For concurrency, we've been using manifests as a unit of work. I doubt that we would change that.
For now, I've marked the fields `volatile` and updated to initialize a local variable and then set the field references. I think that's reasonable. We can always come back and make the `decodeDescriptors` method `synchronized` if needed.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] Core: Add a read-only Mumbling bitmap implementation [iceberg]
Posted by "amogh-jahagirdar (via GitHub)" <gi...@apache.org>.
amogh-jahagirdar commented on code in PR #16747:
URL: https://github.com/apache/iceberg/pull/16747#discussion_r4017807417
##########
core/src/main/java/org/apache/iceberg/mumbling/MumblingBitmap.java:
##########
@@ -0,0 +1,168 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.iceberg.mumbling;
+
+import java.nio.ByteBuffer;
+import org.apache.iceberg.relocated.com.google.common.base.Preconditions;
+
+/**
+ * Read-only view of a Mumbling compressed bitmap stored in a {@link ByteBuffer}.
+ *
+ * <p>The bitmap is lazy: no decoding is done at construction time. On the first call to {@link
+ * #isSet}, the PFOR-encoded descriptor array is decoded and used to build an offsets array that
+ * maps each container index to its absolute byte position in the buffer. This offsets array is the
+ * only derived state kept by this class.
+ *
+ * <p>Format (all integers unsigned, little-endian):
+ *
+ * <ul>
+ * <li>Header (6 bytes): version (1), cardinality (3), container count (2)
+ * <li>Descriptor array: PFOR-encoded, one byte per container
+ * <li>Containers: concatenated sparse (0–31 bytes) or dense (32 bytes) containers
+ * </ul>
+ */
+class MumblingBitmap {
+ private static final int VERSION = 1;
+ private static final int HEADER_SIZE = 6;
+ private static final int DENSE_CONTAINER_BIT = 0b0010_0000;
+
+ private final ByteBuffer data;
+ private final int cardinality;
+ private final int containerCount;
+ private int[] descriptors = null;
+ private int[] offsets = null;
Review Comment:
Yeah, I think locking is probably overkill.
>Maybe we should at least update these arrays at once, after they are initialized? That seems reasonable?
This seems better yeah.
Though with non-volatile fields, assigning them together doesn't quite guarantee another thread sees the expected contents, it could see the reference set but the array values stale.
One possible case is if we ever decide to scan a single manifest's entries in parallel, we would know that every worker thread would have the same reference conetents of the DV (or any other kinds of cases around caching or prefetching inline DV contents from the root).
So I'm mostly thinking that if it's easy to have these guarantees without relying on the 1 thread reading a manifest assumption, it's a bit more robust. It's most likely a non-issue as we probably would only have 1 thread per manifest like we do today, so not a blocker from my side just wanted to think through it.
##########
core/src/main/java/org/apache/iceberg/mumbling/MumblingBitmap.java:
##########
@@ -0,0 +1,168 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.iceberg.mumbling;
+
+import java.nio.ByteBuffer;
+import org.apache.iceberg.relocated.com.google.common.base.Preconditions;
+
+/**
+ * Read-only view of a Mumbling compressed bitmap stored in a {@link ByteBuffer}.
+ *
+ * <p>The bitmap is lazy: no decoding is done at construction time. On the first call to {@link
+ * #isSet}, the PFOR-encoded descriptor array is decoded and used to build an offsets array that
+ * maps each container index to its absolute byte position in the buffer. This offsets array is the
+ * only derived state kept by this class.
+ *
+ * <p>Format (all integers unsigned, little-endian):
+ *
+ * <ul>
+ * <li>Header (6 bytes): version (1), cardinality (3), container count (2)
+ * <li>Descriptor array: PFOR-encoded, one byte per container
+ * <li>Containers: concatenated sparse (0–31 bytes) or dense (32 bytes) containers
+ * </ul>
+ */
+class MumblingBitmap {
+ private static final int VERSION = 1;
+ private static final int HEADER_SIZE = 6;
+ private static final int DENSE_CONTAINER_BIT = 0b0010_0000;
+
+ private final ByteBuffer data;
+ private final int cardinality;
+ private final int containerCount;
+ private int[] descriptors = null;
+ private int[] offsets = null;
Review Comment:
Yeah, I think locking is probably overkill.
>Maybe we should at least update these arrays at once, after they are initialized? That seems reasonable?
This seems better yeah.
Though with non-volatile fields, assigning them together doesn't quite guarantee another thread sees the expected contents, it could see the reference set but the array values stale.
One possible case is if we ever decide to scan a single manifest's entries in parallel, we would know that every worker thread would have the same reference conetents of the DV (or any other kinds of cases around caching or prefetching inline DV contents from the root).
So I'm mostly thinking that if it's easy to have these guarantees without relying on the 1 thread reading a manifest assumption, it's a bit more robust. It's most likely a non-issue as we probably would only have 1 thread per manifest like we do today, so not a blocker from my side just wanted to think through it.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] Core: Add a read-only Mumbling bitmap implementation [iceberg]
Posted by "amogh-jahagirdar (via GitHub)" <gi...@apache.org>.
amogh-jahagirdar commented on code in PR #16747:
URL: https://github.com/apache/iceberg/pull/16747#discussion_r4017807417
##########
core/src/main/java/org/apache/iceberg/mumbling/MumblingBitmap.java:
##########
@@ -0,0 +1,168 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.iceberg.mumbling;
+
+import java.nio.ByteBuffer;
+import org.apache.iceberg.relocated.com.google.common.base.Preconditions;
+
+/**
+ * Read-only view of a Mumbling compressed bitmap stored in a {@link ByteBuffer}.
+ *
+ * <p>The bitmap is lazy: no decoding is done at construction time. On the first call to {@link
+ * #isSet}, the PFOR-encoded descriptor array is decoded and used to build an offsets array that
+ * maps each container index to its absolute byte position in the buffer. This offsets array is the
+ * only derived state kept by this class.
+ *
+ * <p>Format (all integers unsigned, little-endian):
+ *
+ * <ul>
+ * <li>Header (6 bytes): version (1), cardinality (3), container count (2)
+ * <li>Descriptor array: PFOR-encoded, one byte per container
+ * <li>Containers: concatenated sparse (0–31 bytes) or dense (32 bytes) containers
+ * </ul>
+ */
+class MumblingBitmap {
+ private static final int VERSION = 1;
+ private static final int HEADER_SIZE = 6;
+ private static final int DENSE_CONTAINER_BIT = 0b0010_0000;
+
+ private final ByteBuffer data;
+ private final int cardinality;
+ private final int containerCount;
+ private int[] descriptors = null;
+ private int[] offsets = null;
Review Comment:
Yeah, I think locking is probably overkill.
>Maybe we should at least update these arrays at once, after they are initialized? That seems reasonable?
This seems better yeah.
Though with non-volatile fields, assigning them together doesn't quite guarantee another thread sees the expected contents, it could see the reference set but the array values stale.
One possible case is if we ever decide to scan a single manifest's entries in parallel, we would know that every worker thread would have the same reference conetents of the DV (or any other kinds of cases around caching or prefetching inline DV contents from the root). Though we'd need to have some really huge leaves for paralellism to be useful honestly so maybe it's not a valid case.
So I'm mostly thinking that if it's easy to have these guarantees without relying on the 1 thread reading a manifest assumption, it's a bit more robust. It's most likely a non-issue as we probably would only have 1 thread per manifest like we do today, so not a blocker from my side just wanted to think through it.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] Core: Add a read-only Mumbling bitmap implementation [iceberg]
Posted by "rdblue (via GitHub)" <gi...@apache.org>.
rdblue commented on code in PR #16747:
URL: https://github.com/apache/iceberg/pull/16747#discussion_r4010432960
##########
core/src/main/java/org/apache/iceberg/mumbling/MumblingBitmap.java:
##########
@@ -0,0 +1,168 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.iceberg.mumbling;
+
+import java.nio.ByteBuffer;
+import org.apache.iceberg.relocated.com.google.common.base.Preconditions;
+
+/**
+ * Read-only view of a Mumbling compressed bitmap stored in a {@link ByteBuffer}.
+ *
+ * <p>The bitmap is lazy: no decoding is done at construction time. On the first call to {@link
+ * #isSet}, the PFOR-encoded descriptor array is decoded and used to build an offsets array that
+ * maps each container index to its absolute byte position in the buffer. This offsets array is the
+ * only derived state kept by this class.
+ *
+ * <p>Format (all integers unsigned, little-endian):
+ *
+ * <ul>
+ * <li>Header (6 bytes): version (1), cardinality (3), container count (2)
+ * <li>Descriptor array: PFOR-encoded, one byte per container
+ * <li>Containers: concatenated sparse (0–31 bytes) or dense (32 bytes) containers
+ * </ul>
+ */
+class MumblingBitmap {
+ private static final int VERSION = 1;
+ private static final int HEADER_SIZE = 6;
+ private static final int DENSE_CONTAINER_BIT = 0b0010_0000;
+
+ private final ByteBuffer data;
+ private final int cardinality;
+ private final int containerCount;
+ private int[] descriptors = null;
+ private int[] offsets = null;
+
+ MumblingBitmap(ByteBuffer data) {
+ int version = data.get(data.position()) & 0xFF;
+ if (version != VERSION) {
+ throw new UnsupportedOperationException("Unsupported Mumbling bitmap version: " + version);
+ }
+
+ this.data = data;
+ this.cardinality =
+ (data.get(data.position() + 1) & 0xFF)
+ | ((data.get(data.position() + 2) & 0xFF) << 8)
+ | ((data.get(data.position() + 3) & 0xFF) << 16);
+ this.containerCount =
+ (data.get(data.position() + 4) & 0xFF) | ((data.get(data.position() + 5) & 0xFF) << 8);
+ }
+
+ /** Returns the number of bits set in the bitmap. */
+ public int cardinality() {
+ return cardinality;
+ }
+
+ /**
+ * Returns {@code true} if the bit at {@code pos} is set in the bitmap.
+ *
+ * <p>Positions beyond the range of any container are always unset.
+ */
+ public boolean isSet(int pos) {
+ Preconditions.checkArgument(pos >= 0, "Invalid bit position: %s < 0", pos);
+ int containerIndex = pos >>> 8;
+ int posInContainer = pos & 0xFF;
+
+ if (containerIndex >= containerCount) {
+ return false;
+ }
+
+ int containerStart = offset(containerIndex);
+ int descriptor = descriptor(containerIndex);
+
+ if (isDense(descriptor)) {
+ // Dense: 32-byte bitset, MSB of byte 0 is position 0
+ int byteIndex = posInContainer >>> 3;
+ int bitShift = 7 - (posInContainer & 0b111);
+ return ((data.get(containerStart + byteIndex) >>> bitShift) & 0b1) == 0b1;
+
+ } else {
+ // Sparse: sorted list of set positions; scan until found or exceeded
+ for (int i = 0; i < descriptor; i += 1) {
+ int stored = data.get(containerStart + i) & 0xFF;
+ if (stored == posInContainer) {
+ return true;
+ }
+
+ if (stored > posInContainer) {
+ return false;
+ }
+ }
+
+ return false;
+ }
+ }
+
+ private int descriptor(int containerIndex) {
+ if (null == descriptors) {
+ decodeDescriptors();
+ }
+
+ return descriptors[containerIndex];
+ }
+
+ private int offset(int containerIndex) {
+ if (null == offsets) {
+ decodeDescriptors();
+ }
+
+ return offsets[containerIndex];
+ }
+
+ /**
+ * Decode the descriptor array and produce an array of absolute container offsets in the buffer.
+ */
+ private void decodeDescriptors() {
+ this.descriptors = new int[containerCount];
+ int bytesRead = PFOREncoding.decode(data, HEADER_SIZE, descriptors, 0, containerCount);
+
+ this.offsets = new int[containerCount + 1];
+ int firstContainerOffset = data.position() + HEADER_SIZE + bytesRead;
+ descriptorsToOffsets(firstContainerOffset, descriptors, offsets);
+ }
+
+ private static boolean isDense(int descriptor) {
Review Comment:
I think it's a good call to reject bad descriptors. I've added this to the `descriptorsToOffsets` method since that is already looping over descriptors. That should reject any invalid descriptor now.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] Core: Add a read-only Mumbling bitmap implementation [iceberg]
Posted by "amogh-jahagirdar (via GitHub)" <gi...@apache.org>.
amogh-jahagirdar commented on code in PR #16747:
URL: https://github.com/apache/iceberg/pull/16747#discussion_r4017838522
##########
core/src/main/java/org/apache/iceberg/mumbling/MumblingBitmap.java:
##########
@@ -0,0 +1,168 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.iceberg.mumbling;
+
+import java.nio.ByteBuffer;
+import org.apache.iceberg.relocated.com.google.common.base.Preconditions;
+
+/**
+ * Read-only view of a Mumbling compressed bitmap stored in a {@link ByteBuffer}.
+ *
+ * <p>The bitmap is lazy: no decoding is done at construction time. On the first call to {@link
+ * #isSet}, the PFOR-encoded descriptor array is decoded and used to build an offsets array that
+ * maps each container index to its absolute byte position in the buffer. This offsets array is the
+ * only derived state kept by this class.
+ *
+ * <p>Format (all integers unsigned, little-endian):
+ *
+ * <ul>
+ * <li>Header (6 bytes): version (1), cardinality (3), container count (2)
+ * <li>Descriptor array: PFOR-encoded, one byte per container
+ * <li>Containers: concatenated sparse (0–31 bytes) or dense (32 bytes) containers
+ * </ul>
+ */
+class MumblingBitmap {
+ private static final int VERSION = 1;
+ private static final int HEADER_SIZE = 6;
+ private static final int DENSE_CONTAINER_BIT = 0b0010_0000;
+
+ private final ByteBuffer data;
+ private final int cardinality;
+ private final int containerCount;
+ private int[] descriptors = null;
+ private int[] offsets = null;
Review Comment:
Another case is for columnar updates, if we update a leaf manifest via column update, I _think_ we'd need to share the inline DV for both base leaf manifest + column update. And those may be across different threads? But that's a later problem.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] Core: Add a read-only Mumbling bitmap implementation [iceberg]
Posted by "rdblue (via GitHub)" <gi...@apache.org>.
rdblue commented on code in PR #16747:
URL: https://github.com/apache/iceberg/pull/16747#discussion_r3384250775
##########
gradle/libs.versions.toml:
##########
@@ -154,6 +155,7 @@ hive2-service = { module = "org.apache.hive:hive-service", version.ref = "hive2"
httpcomponents-httpclient5 = { module = "org.apache.httpcomponents.client5:httpclient5", version.ref = "httpcomponents-httpclient5" }
immutables-value = { module = "org.immutables:value", version.ref = "immutables-value" }
jackson-bom = { module = "com.fasterxml.jackson:jackson-bom", version.ref = "jackson-bom" }
+javafastpfor = { module = "me.lemire.integercompression:JavaFastPFOR", version.ref = "javafastpfor" }
Review Comment:
This is for the benchmark and doesn't need to be included in the committed version.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] Core: Add a read-only Mumbling bitmap implementation [iceberg]
Posted by "nssalian (via GitHub)" <gi...@apache.org>.
nssalian commented on code in PR #16747:
URL: https://github.com/apache/iceberg/pull/16747#discussion_r3746564691
##########
core/src/main/java/org/apache/iceberg/mumbling/PFOREncoding.java:
##########
@@ -0,0 +1,402 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.iceberg.mumbling;
+
+import java.nio.ByteBuffer;
+import org.apache.iceberg.relocated.com.google.common.base.Preconditions;
+import org.apache.iceberg.util.ByteBuffers;
+import org.apache.iceberg.util.Pair;
+
+/**
+ * Patched Frame of Reference (PFOR) encoding for arrays of unsigned byte values.
+ *
+ * <p>Implements the encoding described in Appendix A of the Mumbling bitmap specification. The
+ * input array is split into 256-value chunks (the last chunk may be shorter). Each chunk is
+ * independently encoded using 4 configuration values:
+ *
+ * <ul>
+ * <li>{@code b1}: number of bits stored in the primary array for every normalized value
+ * <li>{@code b2}: number of bits stored per exception value (normalized value of > b1 bits)
+ * <li>{@code e}: number of exceptions with more than b1 bits
+ * <li>{@code m}: chunk-local minimum value, subtracted from all values to normalize
+ * </ul>
+ *
+ * <p>Each chunk is stored as:
+ *
+ * <ul>
+ * <li>3-byte header: {@code b1|b2} primary and exception bit widths (byte 0), {@code e} exception
+ * count (byte 1), {@code m} normalization base value (byte 2)
+ * <li>Primary array: the low {@code b1} bits of every normalized value, packed MSB-first ({@code
+ * b1 * n} bits, padded to a byte)
+ * <li>Exception offsets: chunk-relative positions of exception values ({@code e} bytes)
+ * <li>Exception values: the high {@code b2} bits of every exception value, packed MSB-first
+ * ({@code e * b2} bits, padded to a byte.
+ * </ul>
+ */
+class PFOREncoding {
+ private static final int CHUNK_SIZE = 256;
+
+ private PFOREncoding() {}
+
+ /**
+ * Encodes {@code count} values from an array of unsigned byte values.
+ *
+ * @param values unsigned byte values to encode
+ * @param count number of values to encode
+ * @return a {@link ByteBuffer} of the encoded values with position and limit set for reading
+ */
+ static ByteBuffer encode(int[] values, int count) {
+ ByteBuffer out = ByteBuffer.allocate(estimateEncodedSize(count));
+ int bytesWritten = encode(values, 0, out, 0, count);
+ return out.slice(0, bytesWritten);
+ }
+
+ /**
+ * Encode {@code count} unsigned byte values from {@code values} into a buffer.
+ *
+ * <p>The buffer's position and limit are not modified.
+ *
+ * @param values unsigned byte values to encode
+ * @param valueOffset starting offset of values to encode
+ * @param out buffer to write encoded values to
+ * @param outOffset starting offset in the output buffer
+ * @param count number of values to encode
+ * @return the number of bytes written to the buffer
+ */
+ static int encode(int[] values, int valueOffset, ByteBuffer out, int outOffset, int count) {
+ // outOffset is relative to the buffer's position; check the encoded data fits
+ Preconditions.checkArgument(outOffset >= 0, "Cannot encode at negative offset: %s", outOffset);
+ Preconditions.checkArgument(
+ estimateEncodedSize(count) <= out.remaining() - outOffset,
+ "Cannot encode %s values to buffer with %s remaining space",
+ count,
+ out.remaining() - outOffset);
+
+ int bytesWritten = 0;
+ int valuesEncoded = 0;
+
+ while (valuesEncoded < count) {
+ int chunkLength = Math.min(CHUNK_SIZE, count - valuesEncoded);
+ bytesWritten +=
+ encodeChunk(
+ values, valueOffset + valuesEncoded, out, outOffset + bytesWritten, chunkLength);
+ valuesEncoded += chunkLength;
+ }
+
+ return bytesWritten;
+ }
+
+ /**
+ * Decode to produce unsigned byte values.
+ *
+ * <p>Decodes starting at {@code encoded.position()} and does not modify the input buffer.
+ *
+ * @param encoded PFOR-encoded ByteBuffer produced by {@link #encode}
+ * @param count total number of values to decode
+ * @return decoded unsigned byte values
+ */
+ static int[] decode(ByteBuffer encoded, int count) {
+ int[] out = new int[count];
+ decode(encoded, 0, out, 0, count);
+ return out;
+ }
+
+ /**
+ * Decode {@code count} unsigned bytes from a buffer into {@code out}.
+ *
+ * <p>This does not modify the input buffer.
+ *
+ * @param encoded a buffer containing encoded data
+ * @param offset starting offset of encoded values
+ * @param out an output value array
+ * @param outOffset starting offset in the output array
+ * @param count number of values to decode
+ * @return the number of bytes read from the encoded buffer
+ */
+ static int decode(ByteBuffer encoded, int offset, int[] out, int outOffset, int count) {
+ Preconditions.checkArgument(offset >= 0, "Cannot decode at negative offset: %s", offset);
+
+ int bytesRead = 0;
+ int valuesRead = 0;
+
+ while (valuesRead < count) {
+ int chunkSize = Math.min(CHUNK_SIZE, count - valuesRead);
+ bytesRead += decodeChunk(encoded, offset + bytesRead, out, outOffset + valuesRead, chunkSize);
+ valuesRead += chunkSize;
+ }
+
+ return bytesRead;
+ }
+
+ /**
+ * Encode one chunk into {@code out} starting at absolute position {@code outPos}.
+ *
+ * @param values array containing source values to encode
+ * @param valueOffset starting index of values to encode
+ * @param out an output {@link ByteBuffer}
+ * @param outOffset starting index for output in the out buffer
+ * @param count number of values to encode
+ * @return the number of bytes written to the output buffer
+ */
+ private static int encodeChunk(
+ int[] values, int valueOffset, ByteBuffer out, int outOffset, int count) {
+ Preconditions.checkArgument(count >= 0, "Invalid value count to encode: %s", count);
+ Preconditions.checkArgument(
+ valueOffset + count <= values.length,
+ "Cannot encode %s values starting at %s from int[%s]: not enough values",
+ count,
+ valueOffset,
+ values.length);
+
+ // find base=min(values) for normalization
+ int base = min(values, valueOffset, count);
+
+ // normalize by subtracting base
+ int[] normalized = new int[count];
+ int setBits = 0;
+ int normalizedSetBits = 0;
+ for (int i = 0; i < count; i += 1) {
+ setBits |= values[valueOffset + i];
+ normalized[i] = values[valueOffset + i] - base;
+ normalizedSetBits |= normalized[i];
+ }
+
+ Preconditions.checkArgument(
+ width(setBits) <= 8,
+ "Cannot encode values wider than 8 bits: %s bits needed",
+ width(setBits));
+
+ // Choose b1 to minimize total encoded data size (excluding 3-byte header)
+ int maxWidth = width(normalizedSetBits);
+ Pair<Integer, Integer> widthAndExcCount = chooseBitWidth(normalized, count, maxWidth);
+ int b1 = widthAndExcCount.first();
+ int b2 = maxWidth - b1;
+ int excCount = widthAndExcCount.second();
+
+ // check that there is enough space in the buffer for the encoded data
+ int requiredSize = encodedSize(count, b1, b2, excCount);
+ Preconditions.checkArgument(
+ outOffset + requiredSize <= out.remaining(),
+ "Cannot encode %s values (%s bytes) into buffer with %s remaining bytes",
+ requiredSize,
+ out.remaining() - outOffset);
+
+ // Special case: b1=8 means store original values as raw bytes with b2, e, and m set to 0.
+ if (b1 == 8) {
+ writeHeader(out, outOffset, b1, 0 /* b2 */, 0 /* excCount */, 0 /* m */);
+ return 3 + BitPacking.packBits(8, values, valueOffset, out, outOffset + 3, count);
+ }
+
+ int bytesWritten = writeHeader(out, outOffset, b1, b2, excCount, base);
+
+ // Primary array: low b1 bits of every value
+ bytesWritten += BitPacking.packBits(b1, normalized, 0, out, outOffset + bytesWritten, count);
+
+ // b2 is the bit width of exception values: (maxWidth - b1) bits of each exception
+ if (excCount > 0) {
+ int[] excOffsets = new int[excCount];
+ int[] excValues = new int[excCount];
+
+ // Collect exceptions (values that do not fit in b1 bits)
+ int excIndex = 0;
+ int threshold = 1 << b1;
+ for (int i = 0; i < count; i += 1) {
+ if (normalized[i] >= threshold) {
+ excOffsets[excIndex] = i;
+ excValues[excIndex] = normalized[i] >>> b1;
+ excIndex += 1;
+ }
+ }
+
+ // Exception offsets (one byte per exception)
+ bytesWritten +=
+ BitPacking.packBits(8, excOffsets, 0, out, outOffset + bytesWritten, excCount);
+
+ // Exception values: remaining high b2 bits of each exception
+ bytesWritten +=
+ BitPacking.packBits(b2, excValues, 0, out, outOffset + bytesWritten, excCount);
+ }
+
+ return bytesWritten;
+ }
+
+ /**
+ * Decode one chunk of encoded data, writing decoded values into an output array.
+ *
+ * @param data buffer containing source data to decode
+ * @param dataOffset starting index in the buffer to decode
+ * @param out an output {@link ByteBuffer}
+ * @param outOffset starting index for output in the out buffer
+ * @param count number of values to decode
+ * @return the number of bytes read from {@code data}
+ */
+ private static int decodeChunk(
+ ByteBuffer data, int dataOffset, int[] out, int outOffset, int count) {
+ Preconditions.checkArgument(count >= 0, "Invalid value count to decode: %s", count);
+ Preconditions.checkArgument(
+ outOffset + count <= out.length,
+ "Cannot decode %s values starting at %s into int[%s]: not enough space",
+ count,
+ outOffset,
+ out.length);
+
+ int b1 = ByteBuffers.readByte(data, dataOffset) & 0x0F;
Review Comment:
Since this decodes embedded, possibly-corrupt metadata, could we check dataOffset + 3 <= data.remaining() before reading the header so a truncated chunk fails with a clean typed error?
##########
core/src/main/java/org/apache/iceberg/mumbling/PFOREncoding.java:
##########
@@ -0,0 +1,402 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.iceberg.mumbling;
+
+import java.nio.ByteBuffer;
+import org.apache.iceberg.relocated.com.google.common.base.Preconditions;
+import org.apache.iceberg.util.ByteBuffers;
+import org.apache.iceberg.util.Pair;
+
+/**
+ * Patched Frame of Reference (PFOR) encoding for arrays of unsigned byte values.
+ *
+ * <p>Implements the encoding described in Appendix A of the Mumbling bitmap specification. The
+ * input array is split into 256-value chunks (the last chunk may be shorter). Each chunk is
+ * independently encoded using 4 configuration values:
+ *
+ * <ul>
+ * <li>{@code b1}: number of bits stored in the primary array for every normalized value
+ * <li>{@code b2}: number of bits stored per exception value (normalized value of > b1 bits)
+ * <li>{@code e}: number of exceptions with more than b1 bits
+ * <li>{@code m}: chunk-local minimum value, subtracted from all values to normalize
+ * </ul>
+ *
+ * <p>Each chunk is stored as:
+ *
+ * <ul>
+ * <li>3-byte header: {@code b1|b2} primary and exception bit widths (byte 0), {@code e} exception
+ * count (byte 1), {@code m} normalization base value (byte 2)
+ * <li>Primary array: the low {@code b1} bits of every normalized value, packed MSB-first ({@code
+ * b1 * n} bits, padded to a byte)
+ * <li>Exception offsets: chunk-relative positions of exception values ({@code e} bytes)
+ * <li>Exception values: the high {@code b2} bits of every exception value, packed MSB-first
+ * ({@code e * b2} bits, padded to a byte.
+ * </ul>
+ */
+class PFOREncoding {
+ private static final int CHUNK_SIZE = 256;
+
+ private PFOREncoding() {}
+
+ /**
+ * Encodes {@code count} values from an array of unsigned byte values.
+ *
+ * @param values unsigned byte values to encode
+ * @param count number of values to encode
+ * @return a {@link ByteBuffer} of the encoded values with position and limit set for reading
+ */
+ static ByteBuffer encode(int[] values, int count) {
+ ByteBuffer out = ByteBuffer.allocate(estimateEncodedSize(count));
+ int bytesWritten = encode(values, 0, out, 0, count);
+ return out.slice(0, bytesWritten);
+ }
+
+ /**
+ * Encode {@code count} unsigned byte values from {@code values} into a buffer.
+ *
+ * <p>The buffer's position and limit are not modified.
+ *
+ * @param values unsigned byte values to encode
+ * @param valueOffset starting offset of values to encode
+ * @param out buffer to write encoded values to
+ * @param outOffset starting offset in the output buffer
+ * @param count number of values to encode
+ * @return the number of bytes written to the buffer
+ */
+ static int encode(int[] values, int valueOffset, ByteBuffer out, int outOffset, int count) {
+ // outOffset is relative to the buffer's position; check the encoded data fits
+ Preconditions.checkArgument(outOffset >= 0, "Cannot encode at negative offset: %s", outOffset);
+ Preconditions.checkArgument(
+ estimateEncodedSize(count) <= out.remaining() - outOffset,
+ "Cannot encode %s values to buffer with %s remaining space",
+ count,
+ out.remaining() - outOffset);
+
+ int bytesWritten = 0;
+ int valuesEncoded = 0;
+
+ while (valuesEncoded < count) {
+ int chunkLength = Math.min(CHUNK_SIZE, count - valuesEncoded);
+ bytesWritten +=
+ encodeChunk(
+ values, valueOffset + valuesEncoded, out, outOffset + bytesWritten, chunkLength);
+ valuesEncoded += chunkLength;
+ }
+
+ return bytesWritten;
+ }
+
+ /**
+ * Decode to produce unsigned byte values.
+ *
+ * <p>Decodes starting at {@code encoded.position()} and does not modify the input buffer.
+ *
+ * @param encoded PFOR-encoded ByteBuffer produced by {@link #encode}
+ * @param count total number of values to decode
+ * @return decoded unsigned byte values
+ */
+ static int[] decode(ByteBuffer encoded, int count) {
+ int[] out = new int[count];
+ decode(encoded, 0, out, 0, count);
+ return out;
+ }
+
+ /**
+ * Decode {@code count} unsigned bytes from a buffer into {@code out}.
+ *
+ * <p>This does not modify the input buffer.
+ *
+ * @param encoded a buffer containing encoded data
+ * @param offset starting offset of encoded values
+ * @param out an output value array
+ * @param outOffset starting offset in the output array
+ * @param count number of values to decode
+ * @return the number of bytes read from the encoded buffer
+ */
+ static int decode(ByteBuffer encoded, int offset, int[] out, int outOffset, int count) {
+ Preconditions.checkArgument(offset >= 0, "Cannot decode at negative offset: %s", offset);
+
+ int bytesRead = 0;
+ int valuesRead = 0;
+
+ while (valuesRead < count) {
+ int chunkSize = Math.min(CHUNK_SIZE, count - valuesRead);
+ bytesRead += decodeChunk(encoded, offset + bytesRead, out, outOffset + valuesRead, chunkSize);
+ valuesRead += chunkSize;
+ }
+
+ return bytesRead;
+ }
+
+ /**
+ * Encode one chunk into {@code out} starting at absolute position {@code outPos}.
+ *
+ * @param values array containing source values to encode
+ * @param valueOffset starting index of values to encode
+ * @param out an output {@link ByteBuffer}
+ * @param outOffset starting index for output in the out buffer
+ * @param count number of values to encode
+ * @return the number of bytes written to the output buffer
+ */
+ private static int encodeChunk(
+ int[] values, int valueOffset, ByteBuffer out, int outOffset, int count) {
+ Preconditions.checkArgument(count >= 0, "Invalid value count to encode: %s", count);
+ Preconditions.checkArgument(
+ valueOffset + count <= values.length,
+ "Cannot encode %s values starting at %s from int[%s]: not enough values",
+ count,
+ valueOffset,
+ values.length);
+
+ // find base=min(values) for normalization
+ int base = min(values, valueOffset, count);
+
+ // normalize by subtracting base
+ int[] normalized = new int[count];
+ int setBits = 0;
+ int normalizedSetBits = 0;
+ for (int i = 0; i < count; i += 1) {
+ setBits |= values[valueOffset + i];
+ normalized[i] = values[valueOffset + i] - base;
+ normalizedSetBits |= normalized[i];
+ }
+
+ Preconditions.checkArgument(
+ width(setBits) <= 8,
+ "Cannot encode values wider than 8 bits: %s bits needed",
+ width(setBits));
+
+ // Choose b1 to minimize total encoded data size (excluding 3-byte header)
+ int maxWidth = width(normalizedSetBits);
+ Pair<Integer, Integer> widthAndExcCount = chooseBitWidth(normalized, count, maxWidth);
+ int b1 = widthAndExcCount.first();
+ int b2 = maxWidth - b1;
+ int excCount = widthAndExcCount.second();
+
+ // check that there is enough space in the buffer for the encoded data
+ int requiredSize = encodedSize(count, b1, b2, excCount);
+ Preconditions.checkArgument(
+ outOffset + requiredSize <= out.remaining(),
+ "Cannot encode %s values (%s bytes) into buffer with %s remaining bytes",
Review Comment:
this message has three %s but only two args (requiredSize and out.remaining() - outOffset), so the leading value count never gets filled in.
##########
core/src/main/java/org/apache/iceberg/mumbling/MumblingBitmap.java:
##########
@@ -0,0 +1,168 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.iceberg.mumbling;
+
+import java.nio.ByteBuffer;
+import org.apache.iceberg.relocated.com.google.common.base.Preconditions;
+
+/**
+ * Read-only view of a Mumbling compressed bitmap stored in a {@link ByteBuffer}.
+ *
+ * <p>The bitmap is lazy: no decoding is done at construction time. On the first call to {@link
+ * #isSet}, the PFOR-encoded descriptor array is decoded and used to build an offsets array that
+ * maps each container index to its absolute byte position in the buffer. This offsets array is the
+ * only derived state kept by this class.
+ *
+ * <p>Format (all integers unsigned, little-endian):
+ *
+ * <ul>
+ * <li>Header (6 bytes): version (1), cardinality (3), container count (2)
+ * <li>Descriptor array: PFOR-encoded, one byte per container
+ * <li>Containers: concatenated sparse (0–31 bytes) or dense (32 bytes) containers
+ * </ul>
+ */
+class MumblingBitmap {
+ private static final int VERSION = 1;
+ private static final int HEADER_SIZE = 6;
+ private static final int DENSE_CONTAINER_BIT = 0b0010_0000;
+
+ private final ByteBuffer data;
+ private final int cardinality;
+ private final int containerCount;
+ private int[] descriptors = null;
+ private int[] offsets = null;
+
+ MumblingBitmap(ByteBuffer data) {
+ int version = data.get(data.position()) & 0xFF;
+ if (version != VERSION) {
+ throw new UnsupportedOperationException("Unsupported Mumbling bitmap version: " + version);
+ }
+
+ this.data = data;
+ this.cardinality =
+ (data.get(data.position() + 1) & 0xFF)
+ | ((data.get(data.position() + 2) & 0xFF) << 8)
+ | ((data.get(data.position() + 3) & 0xFF) << 16);
+ this.containerCount =
+ (data.get(data.position() + 4) & 0xFF) | ((data.get(data.position() + 5) & 0xFF) << 8);
+ }
+
+ /** Returns the number of bits set in the bitmap. */
+ public int cardinality() {
+ return cardinality;
+ }
+
+ /**
+ * Returns {@code true} if the bit at {@code pos} is set in the bitmap.
+ *
+ * <p>Positions beyond the range of any container are always unset.
+ */
+ public boolean isSet(int pos) {
+ Preconditions.checkArgument(pos >= 0, "Invalid bit position: %s < 0", pos);
+ int containerIndex = pos >>> 8;
+ int posInContainer = pos & 0xFF;
+
+ if (containerIndex >= containerCount) {
+ return false;
+ }
+
+ int containerStart = offset(containerIndex);
+ int descriptor = descriptor(containerIndex);
+
+ if (isDense(descriptor)) {
+ // Dense: 32-byte bitset, MSB of byte 0 is position 0
+ int byteIndex = posInContainer >>> 3;
+ int bitShift = 7 - (posInContainer & 0b111);
+ return ((data.get(containerStart + byteIndex) >>> bitShift) & 0b1) == 0b1;
+
+ } else {
+ // Sparse: sorted list of set positions; scan until found or exceeded
+ for (int i = 0; i < descriptor; i += 1) {
+ int stored = data.get(containerStart + i) & 0xFF;
+ if (stored == posInContainer) {
+ return true;
+ }
+
+ if (stored > posInContainer) {
+ return false;
+ }
+ }
+
+ return false;
+ }
+ }
+
+ private int descriptor(int containerIndex) {
+ if (null == descriptors) {
+ decodeDescriptors();
+ }
+
+ return descriptors[containerIndex];
+ }
+
+ private int offset(int containerIndex) {
+ if (null == offsets) {
+ decodeDescriptors();
+ }
+
+ return offsets[containerIndex];
+ }
+
+ /**
+ * Decode the descriptor array and produce an array of absolute container offsets in the buffer.
+ */
+ private void decodeDescriptors() {
+ this.descriptors = new int[containerCount];
+ int bytesRead = PFOREncoding.decode(data, HEADER_SIZE, descriptors, 0, containerCount);
+
+ this.offsets = new int[containerCount + 1];
+ int firstContainerOffset = data.position() + HEADER_SIZE + bytesRead;
+ descriptorsToOffsets(firstContainerOffset, descriptors, offsets);
+ }
+
+ private static boolean isDense(int descriptor) {
+ return (descriptor & DENSE_CONTAINER_BIT) == DENSE_CONTAINER_BIT;
+ }
+
+ /**
+ * Convert an array of lengths into an array of offsets starting at 0.
+ *
+ * <p>For example, descriptorsToOffsets([1, 1, 2]) produces [0, 1, 2, 4].
+ *
+ * @param baseOffset initial offset of the first container
+ * @param descriptors an array of descriptor bytes
+ * @param offsets output array of offsets
+ */
+ private static void descriptorsToOffsets(int baseOffset, int[] descriptors, int[] offsets) {
+ Preconditions.checkArgument(
+ offsets.length > descriptors.length,
+ "Cannot decode %s lengths into %s offsets (not enough space)",
+ descriptors.length,
+ offsets.length);
+
+ offsets[0] = baseOffset;
+ for (int i = 0; i < descriptors.length; i += 1) {
+ if (isDense(descriptors[i])) {
+ offsets[i + 1] = offsets[i] + 32;
Review Comment:
Nit: this 32 is the dense-container byte size (256 bits / 8) and it also shows up in the two comments above. Since the class already has DENSE_CONTAINER_BIT, possibly adding a DENSE_CONTAINER_BYTES = 32 would make the intent obvious here.
##########
core/src/main/java/org/apache/iceberg/mumbling/MumblingBitmap.java:
##########
@@ -0,0 +1,168 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.iceberg.mumbling;
+
+import java.nio.ByteBuffer;
+import org.apache.iceberg.relocated.com.google.common.base.Preconditions;
+
+/**
+ * Read-only view of a Mumbling compressed bitmap stored in a {@link ByteBuffer}.
+ *
+ * <p>The bitmap is lazy: no decoding is done at construction time. On the first call to {@link
+ * #isSet}, the PFOR-encoded descriptor array is decoded and used to build an offsets array that
+ * maps each container index to its absolute byte position in the buffer. This offsets array is the
+ * only derived state kept by this class.
+ *
+ * <p>Format (all integers unsigned, little-endian):
+ *
+ * <ul>
+ * <li>Header (6 bytes): version (1), cardinality (3), container count (2)
+ * <li>Descriptor array: PFOR-encoded, one byte per container
+ * <li>Containers: concatenated sparse (0–31 bytes) or dense (32 bytes) containers
+ * </ul>
+ */
+class MumblingBitmap {
+ private static final int VERSION = 1;
+ private static final int HEADER_SIZE = 6;
+ private static final int DENSE_CONTAINER_BIT = 0b0010_0000;
+
+ private final ByteBuffer data;
+ private final int cardinality;
+ private final int containerCount;
+ private int[] descriptors = null;
+ private int[] offsets = null;
+
+ MumblingBitmap(ByteBuffer data) {
+ int version = data.get(data.position()) & 0xFF;
+ if (version != VERSION) {
+ throw new UnsupportedOperationException("Unsupported Mumbling bitmap version: " + version);
+ }
+
+ this.data = data;
+ this.cardinality =
+ (data.get(data.position() + 1) & 0xFF)
+ | ((data.get(data.position() + 2) & 0xFF) << 8)
+ | ((data.get(data.position() + 3) & 0xFF) << 16);
+ this.containerCount =
+ (data.get(data.position() + 4) & 0xFF) | ((data.get(data.position() + 5) & 0xFF) << 8);
+ }
+
+ /** Returns the number of bits set in the bitmap. */
+ public int cardinality() {
+ return cardinality;
+ }
+
+ /**
+ * Returns {@code true} if the bit at {@code pos} is set in the bitmap.
+ *
+ * <p>Positions beyond the range of any container are always unset.
+ */
+ public boolean isSet(int pos) {
+ Preconditions.checkArgument(pos >= 0, "Invalid bit position: %s < 0", pos);
+ int containerIndex = pos >>> 8;
+ int posInContainer = pos & 0xFF;
+
+ if (containerIndex >= containerCount) {
+ return false;
+ }
+
+ int containerStart = offset(containerIndex);
+ int descriptor = descriptor(containerIndex);
+
+ if (isDense(descriptor)) {
+ // Dense: 32-byte bitset, MSB of byte 0 is position 0
+ int byteIndex = posInContainer >>> 3;
+ int bitShift = 7 - (posInContainer & 0b111);
+ return ((data.get(containerStart + byteIndex) >>> bitShift) & 0b1) == 0b1;
+
+ } else {
+ // Sparse: sorted list of set positions; scan until found or exceeded
+ for (int i = 0; i < descriptor; i += 1) {
+ int stored = data.get(containerStart + i) & 0xFF;
+ if (stored == posInContainer) {
+ return true;
+ }
+
+ if (stored > posInContainer) {
+ return false;
+ }
+ }
+
+ return false;
+ }
+ }
+
+ private int descriptor(int containerIndex) {
+ if (null == descriptors) {
+ decodeDescriptors();
+ }
+
+ return descriptors[containerIndex];
+ }
+
+ private int offset(int containerIndex) {
+ if (null == offsets) {
+ decodeDescriptors();
+ }
+
+ return offsets[containerIndex];
+ }
+
+ /**
+ * Decode the descriptor array and produce an array of absolute container offsets in the buffer.
+ */
+ private void decodeDescriptors() {
+ this.descriptors = new int[containerCount];
+ int bytesRead = PFOREncoding.decode(data, HEADER_SIZE, descriptors, 0, containerCount);
+
+ this.offsets = new int[containerCount + 1];
+ int firstContainerOffset = data.position() + HEADER_SIZE + bytesRead;
+ descriptorsToOffsets(firstContainerOffset, descriptors, offsets);
+ }
+
+ private static boolean isDense(int descriptor) {
Review Comment:
More of a question as I was reading this, isDense keys only on the 0x20 bit, so a descriptor that's neither valid sparse (0-31) nor exactly dense (say 0x40 with the dense bit clear) is read as a sparse container of length 64-255. It's not reachable from the encoder, only from crafted or corrupt input, and the spec reserves the top bits. Do you want the reader to reject unknown descriptor patterns, or is that out of scope for the read-only version?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] Core: Add a read-only Mumbling bitmap implementation [iceberg]
Posted by "amogh-jahagirdar (via GitHub)" <gi...@apache.org>.
amogh-jahagirdar commented on code in PR #16747:
URL: https://github.com/apache/iceberg/pull/16747#discussion_r4006181988
##########
core/src/test/java/org/apache/iceberg/mumbling/TestMumblingBitmap.java:
##########
@@ -0,0 +1,352 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.iceberg.mumbling;
+
+import static org.assertj.core.api.Assertions.assertThat;
+import static org.assertj.core.api.Assertions.assertThatThrownBy;
+
+import java.nio.ByteBuffer;
+import java.util.Arrays;
+import org.apache.iceberg.relocated.com.google.common.base.Preconditions;
+import org.junit.jupiter.api.Test;
+
+class TestMumblingBitmap {
+
+ @Test
+ void testEmptyBitmap() {
+ MumblingBitmap bitmap = bitmap();
+ assertThat(bitmap.cardinality()).isEqualTo(0);
+
+ // all positions beyond the bitmap range are false
+ assertThat(bitmap.isSet(0)).isFalse();
+ assertThat(bitmap.isSet(255)).isFalse();
+ assertThat(bitmap.isSet(256)).isFalse();
+ }
+
+ @Test
+ void testInvalidPosition() {
+ MumblingBitmap bitmap = bitmap();
+ assertThat(bitmap.cardinality()).isEqualTo(0);
+ assertThat(bitmap.isSet(0)).isFalse();
+ assertThatThrownBy(() -> bitmap.isSet(-1))
+ .isInstanceOf(IllegalArgumentException.class)
+ .hasMessage("Invalid bit position: -1 < 0");
+ }
+
+ @Test
+ void testEmptySparseContainer() {
+ MumblingBitmap bitmap = bitmap(sparse());
+ assertThat(bitmap.cardinality()).isEqualTo(0);
+ assertThat(bitmap.isSet(0)).isFalse();
+ assertThat(bitmap.isSet(100)).isFalse();
+ assertThat(bitmap.isSet(255)).isFalse();
+ }
+
+ @Test
+ void testSparseContainerSetPositions() {
+ MumblingBitmap bitmap = bitmap(sparse(0, 5, 100, 255));
+ assertThat(bitmap.cardinality()).isEqualTo(4);
+
+ assertThat(bitmap.isSet(0)).isTrue();
+ assertThat(bitmap.isSet(5)).isTrue();
+ assertThat(bitmap.isSet(100)).isTrue();
+ assertThat(bitmap.isSet(255)).isTrue();
+
+ assertThat(bitmap.isSet(1)).isFalse();
+ assertThat(bitmap.isSet(4)).isFalse();
+ assertThat(bitmap.isSet(6)).isFalse();
+ assertThat(bitmap.isSet(99)).isFalse();
+ assertThat(bitmap.isSet(101)).isFalse();
+ assertThat(bitmap.isSet(254)).isFalse();
+ assertThat(bitmap.isSet(256)).isFalse();
+ }
+
+ @Test
+ void testFullSparseContainer() {
+ int[] positions = new int[31];
+ for (int i = 0; i < 31; i += 1) {
+ positions[i] = i * 8; // 0, 8, 16, ..., 240
+ }
+
+ MumblingBitmap bitmap = bitmap(sparse(positions));
+ assertThat(bitmap.cardinality()).isEqualTo(31);
+
+ for (int p : positions) {
+ assertThat(bitmap.isSet(p)).isTrue();
+ }
+
+ assertThat(bitmap.isSet(1)).isFalse();
+ assertThat(bitmap.isSet(7)).isFalse();
+ assertThat(bitmap.isSet(255)).isFalse();
+ }
+
+ @Test
+ void testFullDenseContainer() {
+ byte[] container = new byte[32];
+ Arrays.fill(container, (byte) 0xFF);
+
+ MumblingBitmap bitmap = bitmap(dense(container));
+ assertThat(bitmap.cardinality()).isEqualTo(256);
+
+ for (int i = 0; i < 256; i += 1) {
+ assertThat(bitmap.isSet(i)).isTrue();
+ }
+
+ assertThat(bitmap.isSet(256)).isFalse();
+ }
+
+ // Example 1: positions 0-31: `FF FF FF FF 00 ... 00`
+ @Test
+ void testDenseSpecExample1() {
+ byte[] container = new byte[32];
+ container[0] = (byte) 0xFF;
+ container[1] = (byte) 0xFF;
+ container[2] = (byte) 0xFF;
+ container[3] = (byte) 0xFF;
+ MumblingBitmap bitmap = bitmap(dense(container));
+ assertThat(bitmap.cardinality()).isEqualTo(32);
+
+ for (int i = 0; i <= 31; i += 1) {
+ assertThat(bitmap.isSet(i)).isTrue();
+ }
+
+ assertThat(bitmap.isSet(32)).isFalse();
+ assertThat(bitmap.isSet(255)).isFalse();
+ }
+
+ // Example 2: positions 0-32: `FF FF FF FF 80 00 ... 00`
+ @Test
+ void testDenseSpecExample2() {
+ byte[] container = new byte[32];
+ container[0] = (byte) 0xFF;
+ container[1] = (byte) 0xFF;
+ container[2] = (byte) 0xFF;
+ container[3] = (byte) 0xFF;
+ container[4] = (byte) 0x80;
+
+ MumblingBitmap bitmap = bitmap(dense(container));
+ assertThat(bitmap.cardinality()).isEqualTo(33);
+
+ for (int i = 0; i <= 32; i += 1) {
+ assertThat(bitmap.isSet(i)).isTrue();
+ }
+
+ assertThat(bitmap.isSet(33)).isFalse();
+ assertThat(bitmap.isSet(255)).isFalse();
+ }
+
+ // Example 3: positions 0-15 and 240-255: `FF FF 00 ... 00 FF FF`
+ @Test
+ void testDenseSpecExample3() {
+ byte[] container = new byte[32];
+ container[0] = (byte) 0xFF;
+ container[1] = (byte) 0xFF;
+ container[30] = (byte) 0xFF;
+ container[31] = (byte) 0xFF;
+
+ MumblingBitmap bitmap = bitmap(dense(container));
+ assertThat(bitmap.cardinality()).isEqualTo(32);
+
+ for (int i = 0; i <= 15; i += 1) {
+ assertThat(bitmap.isSet(i)).isTrue();
+ }
+ for (int i = 240; i <= 255; i += 1) {
+ assertThat(bitmap.isSet(i)).isTrue();
+ }
+ assertThat(bitmap.isSet(16)).isFalse();
+ assertThat(bitmap.isSet(239)).isFalse();
+ assertThat(bitmap.isSet(256)).isFalse();
+ }
+
+ // Example 4: even positions 0, 2, 4, ...: `AA AA ... AA AA`
+ @Test
+ void testDenseSpecExample4() {
+ byte[] container = new byte[32];
+ Arrays.fill(container, (byte) 0xAA);
+
+ MumblingBitmap bitmap = bitmap(dense(container));
+ assertThat(bitmap.cardinality()).isEqualTo(128);
+
+ for (int i = 0; i < 256; i += 1) {
+ assertThat(bitmap.isSet(i)).isEqualTo(i % 2 == 0);
+ }
+
+ assertThat(bitmap.isSet(256)).isFalse();
+ }
+
+ @Test
+ void testMultipleContainers() {
+ MumblingBitmap bitmap = bitmap(sparse(5), sparse(), sparse(10));
+ assertThat(bitmap.cardinality()).isEqualTo(2);
+
+ assertThat(bitmap.isSet(5)).isTrue(); // container 0, pos 5
+ assertThat(bitmap.isSet(256)).isFalse(); // container 1
+ assertThat(bitmap.isSet(522)).isTrue(); // container 2, pos 10
+
+ assertThat(bitmap.isSet(512)).isFalse();
+ assertThat(bitmap.isSet(4)).isFalse();
+ assertThat(bitmap.isSet(265)).isFalse();
+ assertThat(bitmap.isSet(267)).isFalse();
+ }
+
+ @Test
+ void testMixedSparseAndDense() {
Review Comment:
`testMixedSparseAndDense` doesn't seem to hit any PFOR exception cases. Could we add one, e.g. descriptors like `[1, 1, ..., 1, 32]` where the `32` becomes an exception? Or if it's not apppropriate for this unit test, a separate one. I see the PFOR encoding tests already cover exception cases, but adding one here would catch any issues around decoding the descriptor array at a non-zero offset.
##########
core/src/test/java/org/apache/iceberg/mumbling/TestMumblingBitmap.java:
##########
@@ -0,0 +1,352 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.iceberg.mumbling;
+
+import static org.assertj.core.api.Assertions.assertThat;
+import static org.assertj.core.api.Assertions.assertThatThrownBy;
+
+import java.nio.ByteBuffer;
+import java.util.Arrays;
+import org.apache.iceberg.relocated.com.google.common.base.Preconditions;
+import org.junit.jupiter.api.Test;
+
+class TestMumblingBitmap {
+
+ @Test
+ void testEmptyBitmap() {
+ MumblingBitmap bitmap = bitmap();
+ assertThat(bitmap.cardinality()).isEqualTo(0);
+
+ // all positions beyond the bitmap range are false
+ assertThat(bitmap.isSet(0)).isFalse();
+ assertThat(bitmap.isSet(255)).isFalse();
+ assertThat(bitmap.isSet(256)).isFalse();
+ }
+
+ @Test
+ void testInvalidPosition() {
+ MumblingBitmap bitmap = bitmap();
+ assertThat(bitmap.cardinality()).isEqualTo(0);
+ assertThat(bitmap.isSet(0)).isFalse();
+ assertThatThrownBy(() -> bitmap.isSet(-1))
+ .isInstanceOf(IllegalArgumentException.class)
+ .hasMessage("Invalid bit position: -1 < 0");
+ }
+
+ @Test
+ void testEmptySparseContainer() {
+ MumblingBitmap bitmap = bitmap(sparse());
+ assertThat(bitmap.cardinality()).isEqualTo(0);
+ assertThat(bitmap.isSet(0)).isFalse();
+ assertThat(bitmap.isSet(100)).isFalse();
+ assertThat(bitmap.isSet(255)).isFalse();
+ }
+
+ @Test
+ void testSparseContainerSetPositions() {
+ MumblingBitmap bitmap = bitmap(sparse(0, 5, 100, 255));
+ assertThat(bitmap.cardinality()).isEqualTo(4);
+
+ assertThat(bitmap.isSet(0)).isTrue();
+ assertThat(bitmap.isSet(5)).isTrue();
+ assertThat(bitmap.isSet(100)).isTrue();
+ assertThat(bitmap.isSet(255)).isTrue();
+
+ assertThat(bitmap.isSet(1)).isFalse();
+ assertThat(bitmap.isSet(4)).isFalse();
+ assertThat(bitmap.isSet(6)).isFalse();
+ assertThat(bitmap.isSet(99)).isFalse();
+ assertThat(bitmap.isSet(101)).isFalse();
+ assertThat(bitmap.isSet(254)).isFalse();
+ assertThat(bitmap.isSet(256)).isFalse();
+ }
+
+ @Test
+ void testFullSparseContainer() {
+ int[] positions = new int[31];
+ for (int i = 0; i < 31; i += 1) {
+ positions[i] = i * 8; // 0, 8, 16, ..., 240
+ }
+
+ MumblingBitmap bitmap = bitmap(sparse(positions));
+ assertThat(bitmap.cardinality()).isEqualTo(31);
+
+ for (int p : positions) {
+ assertThat(bitmap.isSet(p)).isTrue();
+ }
+
+ assertThat(bitmap.isSet(1)).isFalse();
+ assertThat(bitmap.isSet(7)).isFalse();
+ assertThat(bitmap.isSet(255)).isFalse();
+ }
+
+ @Test
+ void testFullDenseContainer() {
+ byte[] container = new byte[32];
+ Arrays.fill(container, (byte) 0xFF);
+
+ MumblingBitmap bitmap = bitmap(dense(container));
+ assertThat(bitmap.cardinality()).isEqualTo(256);
+
+ for (int i = 0; i < 256; i += 1) {
+ assertThat(bitmap.isSet(i)).isTrue();
+ }
+
+ assertThat(bitmap.isSet(256)).isFalse();
+ }
+
+ // Example 1: positions 0-31: `FF FF FF FF 00 ... 00`
+ @Test
+ void testDenseSpecExample1() {
+ byte[] container = new byte[32];
+ container[0] = (byte) 0xFF;
+ container[1] = (byte) 0xFF;
+ container[2] = (byte) 0xFF;
+ container[3] = (byte) 0xFF;
+ MumblingBitmap bitmap = bitmap(dense(container));
+ assertThat(bitmap.cardinality()).isEqualTo(32);
+
+ for (int i = 0; i <= 31; i += 1) {
+ assertThat(bitmap.isSet(i)).isTrue();
+ }
+
+ assertThat(bitmap.isSet(32)).isFalse();
+ assertThat(bitmap.isSet(255)).isFalse();
+ }
+
+ // Example 2: positions 0-32: `FF FF FF FF 80 00 ... 00`
+ @Test
+ void testDenseSpecExample2() {
+ byte[] container = new byte[32];
+ container[0] = (byte) 0xFF;
+ container[1] = (byte) 0xFF;
+ container[2] = (byte) 0xFF;
+ container[3] = (byte) 0xFF;
+ container[4] = (byte) 0x80;
+
+ MumblingBitmap bitmap = bitmap(dense(container));
+ assertThat(bitmap.cardinality()).isEqualTo(33);
+
+ for (int i = 0; i <= 32; i += 1) {
+ assertThat(bitmap.isSet(i)).isTrue();
+ }
+
+ assertThat(bitmap.isSet(33)).isFalse();
+ assertThat(bitmap.isSet(255)).isFalse();
+ }
+
+ // Example 3: positions 0-15 and 240-255: `FF FF 00 ... 00 FF FF`
+ @Test
+ void testDenseSpecExample3() {
+ byte[] container = new byte[32];
+ container[0] = (byte) 0xFF;
+ container[1] = (byte) 0xFF;
+ container[30] = (byte) 0xFF;
+ container[31] = (byte) 0xFF;
+
+ MumblingBitmap bitmap = bitmap(dense(container));
+ assertThat(bitmap.cardinality()).isEqualTo(32);
+
+ for (int i = 0; i <= 15; i += 1) {
+ assertThat(bitmap.isSet(i)).isTrue();
+ }
+ for (int i = 240; i <= 255; i += 1) {
+ assertThat(bitmap.isSet(i)).isTrue();
+ }
+ assertThat(bitmap.isSet(16)).isFalse();
+ assertThat(bitmap.isSet(239)).isFalse();
+ assertThat(bitmap.isSet(256)).isFalse();
+ }
+
+ // Example 4: even positions 0, 2, 4, ...: `AA AA ... AA AA`
+ @Test
+ void testDenseSpecExample4() {
+ byte[] container = new byte[32];
+ Arrays.fill(container, (byte) 0xAA);
+
+ MumblingBitmap bitmap = bitmap(dense(container));
+ assertThat(bitmap.cardinality()).isEqualTo(128);
+
+ for (int i = 0; i < 256; i += 1) {
+ assertThat(bitmap.isSet(i)).isEqualTo(i % 2 == 0);
+ }
+
+ assertThat(bitmap.isSet(256)).isFalse();
+ }
+
+ @Test
+ void testMultipleContainers() {
+ MumblingBitmap bitmap = bitmap(sparse(5), sparse(), sparse(10));
+ assertThat(bitmap.cardinality()).isEqualTo(2);
+
+ assertThat(bitmap.isSet(5)).isTrue(); // container 0, pos 5
+ assertThat(bitmap.isSet(256)).isFalse(); // container 1
+ assertThat(bitmap.isSet(522)).isTrue(); // container 2, pos 10
+
+ assertThat(bitmap.isSet(512)).isFalse();
+ assertThat(bitmap.isSet(4)).isFalse();
+ assertThat(bitmap.isSet(265)).isFalse();
+ assertThat(bitmap.isSet(267)).isFalse();
+ }
+
+ @Test
+ void testMixedSparseAndDense() {
+ byte[] denseContainer = new byte[32];
+ denseContainer[0] = (byte) 0xFF;
+ denseContainer[1] = (byte) 0xFF;
+ denseContainer[2] = (byte) 0xFF;
+ denseContainer[3] = (byte) 0xFF;
+
+ MumblingBitmap bitmap = bitmap(dense(denseContainer), sparse(1));
+ assertThat(bitmap.cardinality()).isEqualTo(33);
+
+ for (int i = 0; i < 32; i += 1) {
+ assertThat(bitmap.isSet(i)).isTrue();
+ }
+ assertThat(bitmap.isSet(32)).isFalse();
+
+ assertThat(bitmap.isSet(256)).isFalse();
+ assertThat(bitmap.isSet(257)).isTrue(); // container 1, pos 1
+ assertThat(bitmap.isSet(258)).isFalse();
+ }
+
+ @Test
+ void testBufferWithOffset() {
+ // Prepend 4 bytes of garbage before the actual bitmap data
+ ByteBuffer buffer = build(sparse(42));
+ byte[] rawBytes = new byte[buffer.remaining()];
+ buffer.get(rawBytes);
+
+ ByteBuffer padded = ByteBuffer.allocate(4 + rawBytes.length);
+ padded.position(4);
+ padded.put(rawBytes);
+ padded.position(4); // position the buffer at the start of bitmap data
+
+ MumblingBitmap bitmap = new MumblingBitmap(padded);
+ assertThat(bitmap.cardinality()).isEqualTo(1);
+
+ assertThat(bitmap.isSet(41)).isFalse();
+ assertThat(bitmap.isSet(42)).isTrue();
+ assertThat(bitmap.isSet(43)).isFalse();
+ }
+
+ private static Container sparse(int... positions) {
+ byte[] bytes = new byte[positions.length];
+ for (int i = 0; i < positions.length; i += 1) {
+ if (i > 0) {
+ Preconditions.checkArgument(
+ positions[i] < 256, "Invalid position in container: %s", positions[i]);
+ Preconditions.checkArgument(
+ positions[i] > positions[i - 1],
+ "Invalid sparse container: pos %s=%s >= pos %s=%s",
+ i - 1,
+ positions[i - 1],
+ i,
+ positions[i]);
+ }
+
+ bytes[i] = (byte) positions[i];
+ }
+
+ return new Container(bytes);
+ }
+
+ /** Descriptor + bytes for a dense container. */
+ private static Container dense(byte[] container) {
+ Preconditions.checkArgument(container.length == 32, "Dense container must be 32 bytes");
+ return new Container(container);
+ }
+
+ private static class Container {
+ private final byte[] bytes;
+ private final int descriptor;
+ private final int cardinality;
+
+ Container(byte[] bytes) {
+ this.bytes = bytes;
+ this.descriptor = bytes.length;
Review Comment:
If I follow right, this is always hardcoded to 0x20. If that's right, I don't think the tests cover a case where we have dense descriptor and with the low bits set. The spec says "The two most significant bits are reserved for future use and implementations must ignore the least-significant bits for a dense container if they are set." . Should we add a case, something like 0x2F and make sure the container is just read like a normal dense bitmap?
##########
core/src/main/java/org/apache/iceberg/mumbling/MumblingBitmap.java:
##########
@@ -0,0 +1,168 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.iceberg.mumbling;
+
+import java.nio.ByteBuffer;
+import org.apache.iceberg.relocated.com.google.common.base.Preconditions;
+
+/**
+ * Read-only view of a Mumbling compressed bitmap stored in a {@link ByteBuffer}.
+ *
+ * <p>The bitmap is lazy: no decoding is done at construction time. On the first call to {@link
+ * #isSet}, the PFOR-encoded descriptor array is decoded and used to build an offsets array that
+ * maps each container index to its absolute byte position in the buffer. This offsets array is the
+ * only derived state kept by this class.
+ *
+ * <p>Format (all integers unsigned, little-endian):
+ *
+ * <ul>
+ * <li>Header (6 bytes): version (1), cardinality (3), container count (2)
+ * <li>Descriptor array: PFOR-encoded, one byte per container
+ * <li>Containers: concatenated sparse (0–31 bytes) or dense (32 bytes) containers
+ * </ul>
+ */
+class MumblingBitmap {
+ private static final int VERSION = 1;
+ private static final int HEADER_SIZE = 6;
+ private static final int DENSE_CONTAINER_BIT = 0b0010_0000;
+
+ private final ByteBuffer data;
+ private final int cardinality;
+ private final int containerCount;
+ private int[] descriptors = null;
+ private int[] offsets = null;
Review Comment:
Just to harden this path a bit, should these be made as `volatile` and these fields are only set after they are actually populated. I think that avoids any subtle concurrency bugs in case for whatever reason a single bitmap reference is decoded and acceessed across different threads. While I wouldn't expect there to be more 1 thread reading a given bitmap, seems like we can avoid those cases in a simple manner and allow for flexible consumption patterns to callers.
##########
core/src/main/java/org/apache/iceberg/mumbling/PFOREncoding.java:
##########
@@ -0,0 +1,402 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.iceberg.mumbling;
+
+import java.nio.ByteBuffer;
+import org.apache.iceberg.relocated.com.google.common.base.Preconditions;
+import org.apache.iceberg.util.ByteBuffers;
+import org.apache.iceberg.util.Pair;
+
+/**
+ * Patched Frame of Reference (PFOR) encoding for arrays of unsigned byte values.
+ *
+ * <p>Implements the encoding described in Appendix A of the Mumbling bitmap specification. The
+ * input array is split into 256-value chunks (the last chunk may be shorter). Each chunk is
+ * independently encoded using 4 configuration values:
+ *
+ * <ul>
+ * <li>{@code b1}: number of bits stored in the primary array for every normalized value
+ * <li>{@code b2}: number of bits stored per exception value (normalized value of > b1 bits)
+ * <li>{@code e}: number of exceptions with more than b1 bits
+ * <li>{@code m}: chunk-local minimum value, subtracted from all values to normalize
+ * </ul>
+ *
+ * <p>Each chunk is stored as:
+ *
+ * <ul>
+ * <li>3-byte header: {@code b1|b2} primary and exception bit widths (byte 0), {@code e} exception
+ * count (byte 1), {@code m} normalization base value (byte 2)
+ * <li>Primary array: the low {@code b1} bits of every normalized value, packed MSB-first ({@code
+ * b1 * n} bits, padded to a byte)
+ * <li>Exception offsets: chunk-relative positions of exception values ({@code e} bytes)
+ * <li>Exception values: the high {@code b2} bits of every exception value, packed MSB-first
+ * ({@code e * b2} bits, padded to a byte.
+ * </ul>
+ */
+class PFOREncoding {
+ private static final int CHUNK_SIZE = 256;
+
+ private PFOREncoding() {}
+
+ /**
+ * Encodes {@code count} values from an array of unsigned byte values.
+ *
+ * @param values unsigned byte values to encode
+ * @param count number of values to encode
+ * @return a {@link ByteBuffer} of the encoded values with position and limit set for reading
+ */
+ static ByteBuffer encode(int[] values, int count) {
+ ByteBuffer out = ByteBuffer.allocate(estimateEncodedSize(count));
+ int bytesWritten = encode(values, 0, out, 0, count);
+ return out.slice(0, bytesWritten);
+ }
+
+ /**
+ * Encode {@code count} unsigned byte values from {@code values} into a buffer.
+ *
+ * <p>The buffer's position and limit are not modified.
+ *
+ * @param values unsigned byte values to encode
+ * @param valueOffset starting offset of values to encode
+ * @param out buffer to write encoded values to
+ * @param outOffset starting offset in the output buffer
+ * @param count number of values to encode
+ * @return the number of bytes written to the buffer
+ */
+ static int encode(int[] values, int valueOffset, ByteBuffer out, int outOffset, int count) {
+ // outOffset is relative to the buffer's position; check the encoded data fits
+ Preconditions.checkArgument(outOffset >= 0, "Cannot encode at negative offset: %s", outOffset);
+ Preconditions.checkArgument(
+ estimateEncodedSize(count) <= out.remaining() - outOffset,
+ "Cannot encode %s values to buffer with %s remaining space",
+ count,
+ out.remaining() - outOffset);
+
+ int bytesWritten = 0;
+ int valuesEncoded = 0;
+
+ while (valuesEncoded < count) {
+ int chunkLength = Math.min(CHUNK_SIZE, count - valuesEncoded);
+ bytesWritten +=
+ encodeChunk(
+ values, valueOffset + valuesEncoded, out, outOffset + bytesWritten, chunkLength);
+ valuesEncoded += chunkLength;
+ }
+
+ return bytesWritten;
+ }
+
+ /**
+ * Decode to produce unsigned byte values.
+ *
+ * <p>Decodes starting at {@code encoded.position()} and does not modify the input buffer.
+ *
+ * @param encoded PFOR-encoded ByteBuffer produced by {@link #encode}
+ * @param count total number of values to decode
+ * @return decoded unsigned byte values
+ */
+ static int[] decode(ByteBuffer encoded, int count) {
+ int[] out = new int[count];
+ decode(encoded, 0, out, 0, count);
+ return out;
+ }
+
+ /**
+ * Decode {@code count} unsigned bytes from a buffer into {@code out}.
+ *
+ * <p>This does not modify the input buffer.
+ *
+ * @param encoded a buffer containing encoded data
+ * @param offset starting offset of encoded values
+ * @param out an output value array
+ * @param outOffset starting offset in the output array
+ * @param count number of values to decode
+ * @return the number of bytes read from the encoded buffer
+ */
+ static int decode(ByteBuffer encoded, int offset, int[] out, int outOffset, int count) {
+ Preconditions.checkArgument(offset >= 0, "Cannot decode at negative offset: %s", offset);
+
+ int bytesRead = 0;
+ int valuesRead = 0;
+
+ while (valuesRead < count) {
+ int chunkSize = Math.min(CHUNK_SIZE, count - valuesRead);
+ bytesRead += decodeChunk(encoded, offset + bytesRead, out, outOffset + valuesRead, chunkSize);
+ valuesRead += chunkSize;
+ }
+
+ return bytesRead;
+ }
+
+ /**
+ * Encode one chunk into {@code out} starting at absolute position {@code outPos}.
+ *
+ * @param values array containing source values to encode
+ * @param valueOffset starting index of values to encode
+ * @param out an output {@link ByteBuffer}
+ * @param outOffset starting index for output in the out buffer
+ * @param count number of values to encode
+ * @return the number of bytes written to the output buffer
+ */
+ private static int encodeChunk(
+ int[] values, int valueOffset, ByteBuffer out, int outOffset, int count) {
+ Preconditions.checkArgument(count >= 0, "Invalid value count to encode: %s", count);
+ Preconditions.checkArgument(
+ valueOffset + count <= values.length,
+ "Cannot encode %s values starting at %s from int[%s]: not enough values",
+ count,
+ valueOffset,
+ values.length);
+
+ // find base=min(values) for normalization
+ int base = min(values, valueOffset, count);
+
+ // normalize by subtracting base
+ int[] normalized = new int[count];
+ int setBits = 0;
+ int normalizedSetBits = 0;
+ for (int i = 0; i < count; i += 1) {
+ setBits |= values[valueOffset + i];
+ normalized[i] = values[valueOffset + i] - base;
+ normalizedSetBits |= normalized[i];
+ }
+
+ Preconditions.checkArgument(
+ width(setBits) <= 8,
+ "Cannot encode values wider than 8 bits: %s bits needed",
+ width(setBits));
+
+ // Choose b1 to minimize total encoded data size (excluding 3-byte header)
+ int maxWidth = width(normalizedSetBits);
+ Pair<Integer, Integer> widthAndExcCount = chooseBitWidth(normalized, count, maxWidth);
+ int b1 = widthAndExcCount.first();
+ int b2 = maxWidth - b1;
+ int excCount = widthAndExcCount.second();
+
+ // check that there is enough space in the buffer for the encoded data
+ int requiredSize = encodedSize(count, b1, b2, excCount);
+ Preconditions.checkArgument(
+ outOffset + requiredSize <= out.remaining(),
+ "Cannot encode %s values (%s bytes) into buffer with %s remaining bytes",
+ requiredSize,
+ out.remaining() - outOffset);
+
+ // Special case: b1=8 means store original values as raw bytes with b2, e, and m set to 0.
+ if (b1 == 8) {
+ writeHeader(out, outOffset, b1, 0 /* b2 */, 0 /* excCount */, 0 /* m */);
+ return 3 + BitPacking.packBits(8, values, valueOffset, out, outOffset + 3, count);
+ }
+
+ int bytesWritten = writeHeader(out, outOffset, b1, b2, excCount, base);
+
+ // Primary array: low b1 bits of every value
+ bytesWritten += BitPacking.packBits(b1, normalized, 0, out, outOffset + bytesWritten, count);
+
+ // b2 is the bit width of exception values: (maxWidth - b1) bits of each exception
+ if (excCount > 0) {
+ int[] excOffsets = new int[excCount];
+ int[] excValues = new int[excCount];
+
+ // Collect exceptions (values that do not fit in b1 bits)
+ int excIndex = 0;
+ int threshold = 1 << b1;
+ for (int i = 0; i < count; i += 1) {
+ if (normalized[i] >= threshold) {
+ excOffsets[excIndex] = i;
+ excValues[excIndex] = normalized[i] >>> b1;
+ excIndex += 1;
+ }
+ }
+
+ // Exception offsets (one byte per exception)
+ bytesWritten +=
+ BitPacking.packBits(8, excOffsets, 0, out, outOffset + bytesWritten, excCount);
+
+ // Exception values: remaining high b2 bits of each exception
+ bytesWritten +=
+ BitPacking.packBits(b2, excValues, 0, out, outOffset + bytesWritten, excCount);
+ }
+
+ return bytesWritten;
+ }
+
+ /**
+ * Decode one chunk of encoded data, writing decoded values into an output array.
+ *
+ * @param data buffer containing source data to decode
+ * @param dataOffset starting index in the buffer to decode
+ * @param out an output {@link ByteBuffer}
+ * @param outOffset starting index for output in the out buffer
+ * @param count number of values to decode
+ * @return the number of bytes read from {@code data}
+ */
+ private static int decodeChunk(
+ ByteBuffer data, int dataOffset, int[] out, int outOffset, int count) {
+ Preconditions.checkArgument(count >= 0, "Invalid value count to decode: %s", count);
+ Preconditions.checkArgument(
+ outOffset + count <= out.length,
+ "Cannot decode %s values starting at %s into int[%s]: not enough space",
+ count,
+ outOffset,
+ out.length);
+
+ int b1 = ByteBuffers.readByte(data, dataOffset) & 0x0F;
+ int b2 = (ByteBuffers.readByte(data, dataOffset) >>> 4) & 0x0F;
+ int excCount = ByteBuffers.readByte(data, dataOffset + 1);
+ int base = ByteBuffers.readByte(data, dataOffset + 2);
+ int bytesRead = 3;
+
+ // after reading the header, check that the full chunk is present
+ int expectedSize = encodedSize(count, b1, b2, excCount);
+ Preconditions.checkArgument(
+ dataOffset + expectedSize <= data.remaining(),
+ "Cannot decode %s values from buffer with %s remaining bytes",
+ expectedSize,
+ data.remaining() - dataOffset);
+
+ // Read primary array: low b1 bits of each value
+ bytesRead += BitPacking.unpackBits(b1, data, dataOffset + bytesRead, out, outOffset, count);
+
+ // Read exceptions and update output values
+ if (excCount > 0) {
+ int[] excOffsets = new int[excCount];
+ int[] excValues = new int[excCount];
+ int excListOffset = dataOffset + bytesRead;
+ int excDataOffset = dataOffset + bytesRead + excCount;
+
+ // Read exception indexes
+ bytesRead += BitPacking.unpackBits(8, data, excListOffset, excOffsets, 0, excCount);
+
+ // Read exception values and patch the primary values
+ bytesRead += BitPacking.unpackBits(b2, data, excDataOffset, excValues, 0, excCount);
+
+ // Update output values
+ for (int i = 0; i < excCount; i += 1) {
+ out[outOffset + excOffsets[i]] |= excValues[i] << b1;
+ }
+ }
+
+ // Add back the chunk minimum
+ for (int i = 0; i < count; i += 1) {
+ out[outOffset + i] += base;
+ }
+
+ return bytesRead;
+ }
+
+ private static int writeHeader(
+ ByteBuffer out, int outOffset, int b1, int b2, int excCount, int base) {
+ // Header: b1 in low nibble, b2 in high nibble, then e, then m
+ ByteBuffers.writeByte(out, (b2 << 4) | (b1 & 0b1111), outOffset);
+ ByteBuffers.writeByte(out, excCount, outOffset + 1);
+ ByteBuffers.writeByte(out, base, outOffset + 2);
+
+ return 3;
+ }
+
+ /**
+ * Choose the primary bit width {@code b1} that minimizes total encoded chunk size.
+ *
+ * <p>This produces the width that results in the smallest total size and the number of exceptions
Review Comment:
The spec example encodes `[6, 34, 8, 7]` as `b1=2` with one exception, but this function picks `b1=5` with no exceptions. Both come out to the same size and both decode correctly, so this is a valid choice, just different from the example bytes in the spec.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] Core: Add a read-only Mumbling bitmap implementation [iceberg]
Posted by "amogh-jahagirdar (via GitHub)" <gi...@apache.org>.
amogh-jahagirdar merged PR #16747:
URL: https://github.com/apache/iceberg/pull/16747
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] Core: Add a read-only Mumbling bitmap implementation [iceberg]
Posted by "pvary (via GitHub)" <gi...@apache.org>.
pvary commented on PR #16747:
URL: https://github.com/apache/iceberg/pull/16747#issuecomment-4671995456
What pattern should I test?
This is what I tried, and what I have found:
```
pattern set positions Mumbling Roaring Roaring + RLE Parquet v2
last 50k only 50000 6491 16408 25 631
random 1% + last 50k 53495 10472 22980 7509 4628
random 10% 40000 40636 50552 50552 27227
random 20% 80000 50111 51862 51862 42340
random 5% 20000 20871 40064 40064 16634
```
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] Core: Add a read-only Mumbling bitmap implementation [iceberg]
Posted by "rdblue (via GitHub)" <gi...@apache.org>.
rdblue commented on code in PR #16747:
URL: https://github.com/apache/iceberg/pull/16747#discussion_r4010600018
##########
core/src/main/java/org/apache/iceberg/mumbling/BitPacking.java:
##########
@@ -0,0 +1,769 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.iceberg.mumbling;
+
+import java.nio.ByteBuffer;
+import org.apache.iceberg.util.ByteBuffers;
+
+/**
+ * Bit packing and unpacking for values of 1–7 bits.
+ *
+ * <p>The least-significant bits of each value are packed with the first value occupying the most
+ * significant bits of the output. Output is padded to the nearest byte with 0s. For example,
+ * packing values [0b11, 0b10, 0b01] with width 2 produces 0b11100100.
+ */
+class BitPacking {
+
+ private BitPacking() {}
+
+ /**
+ * Packs {@code width} least-significant bits of {@code count} values into a data buffer.
+ *
+ * <p>Output is padded to the nearest byte with 0s.
+ *
+ * <p>Values are written to the buffer's underlying storage, but the buffer's position and limit
+ * are not modified.
+ *
+ * @param width number of bits of each value to pack
+ * @param values array containing source values to pack
+ * @param valueOffset starting index of values to pack
+ * @param data an output {@link ByteBuffer}
+ * @param dataOffset starting index for output in the data buffer
+ * @param count the number of values to pack
+ * @return the number of bytes written to the data buffer
+ */
+ static int packBits(
Review Comment:
I did it this way because I think it's easier to read and verify, and we only need to do that once.
For example, we can break down the 3-bit pack method, starting with `packWord3`:
```java
private static int packWord3(int a, int b, int c, int d, int e, int f, int g, int h) {
return ((a & 0b111) << 21)
| ((b & 0b111) << 18)
| ((c & 0b111) << 15)
| ((d & 0b111) << 12)
| ((e & 0b111) << 9)
| ((f & 0b111) << 6)
| ((g & 0b111) << 3)
| (h & 0b111);
}
```
This method packs the least-significant 3 bits of 8 values into 3 bytes. It's easy to see the order of values and the offset each one uses. I think that's easier to read than a loop that keeps adding 3 and uses variables like `mask = (0b1 << width) - 1`.
Then for the array pack method:
```java
int fullGroups = count / 8;
// . . .
int remaining = count % 8;
```
This is common to each pack method and breaks the values into groups of 8 for use with the `packWord` method.
```java
for (int group = 0; group < fullGroups; group += 1) {
int groupOffset = valueOffset + 8 * group;
int outputOffset = dataOffset + 3 * group;
int word = packWord3(values[groupOffset], ..., values[groupOffset + 7]);
ByteBuffers.writeByte(data, word >>> 16, outputOffset);
ByteBuffers.writeByte(data, word >>> 8, outputOffset + 1);
ByteBuffers.writeByte(data, word, outputOffset + 2);
}
```
This packs all of the full groups of 8 values. The hardest thing is the offset tracking, which skips by 8 values for each group and 3 bytes for each group's output in the data buffer. The values are all passed to `packWord3` that produces an `int` with the 3 packed bytes.
This then writes the packed bytes into the data buffer. I think this makes it easy to see the bits that are used from the int.
```java
if (remaining > 0) {
int groupOffset = valueOffset + 8 * fullGroups;
int outputOffset = dataOffset + 3 * fullGroups;
int word =
packWord3(
values[groupOffset],
remaining > 1 ? values[groupOffset + 1] : 0,
remaining > 2 ? values[groupOffset + 2] : 0,
remaining > 3 ? values[groupOffset + 3] : 0,
remaining > 4 ? values[groupOffset + 4] : 0,
remaining > 5 ? values[groupOffset + 5] : 0,
remaining > 6 ? values[groupOffset + 6] : 0,
0);
int byteCount = byteWidth(3 * remaining);
for (int k = 0; k < byteCount; k += 1) {
ByteBuffers.writeByte(data, word >>> (16 - 8 * k), outputOffset + k);
}
}
```
This handles the remaining values of the last partial group. Each value is replaced with 0 when packing to a word, if it is not present in the data.
After packing, the bytes of the value are written to the data buffer. This is a little tricky because it uses a loop to write the first 1 or 2 bytes if the third byte isn't used. However, since it mirrors the `writeByte` calls above, I think it's more understandable. `(16 - 8 * k)` is the shift; first 16, then 8, then 0 just like the first section.
```java
return byteWidth(3 * count);
```
Finally, this returns the actual bytes written.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] Core: Add a read-only Mumbling bitmap implementation [iceberg]
Posted by "Fokko (via GitHub)" <gi...@apache.org>.
Fokko commented on code in PR #16747:
URL: https://github.com/apache/iceberg/pull/16747#discussion_r4025214669
##########
core/src/main/java/org/apache/iceberg/mumbling/PFOREncoding.java:
##########
@@ -0,0 +1,405 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.iceberg.mumbling;
+
+import java.nio.ByteBuffer;
+import org.apache.iceberg.relocated.com.google.common.base.Preconditions;
+import org.apache.iceberg.util.ByteBuffers;
+import org.apache.iceberg.util.Pair;
+
+/**
+ * Patched Frame of Reference (PFOR) encoding for arrays of unsigned byte values.
+ *
+ * <p>Implements the encoding described in Appendix A of the Mumbling bitmap specification. The
+ * input array is split into 256-value chunks (the last chunk may be shorter). Each chunk is
+ * independently encoded using 4 configuration values:
+ *
+ * <ul>
+ * <li>{@code b1}: number of bits stored in the primary array for every normalized value
+ * <li>{@code b2}: number of bits stored per exception value (normalized value of > b1 bits)
+ * <li>{@code e}: number of exceptions with more than b1 bits
+ * <li>{@code m}: chunk-local minimum value, subtracted from all values to normalize
+ * </ul>
+ *
+ * <p>Each chunk is stored as:
+ *
+ * <ul>
+ * <li>3-byte header: {@code b1|b2} primary and exception bit widths (byte 0), {@code e} exception
+ * count (byte 1), {@code m} normalization base value (byte 2)
+ * <li>Primary array: the low {@code b1} bits of every normalized value, packed MSB-first ({@code
+ * b1 * n} bits, padded to a byte)
+ * <li>Exception offsets: chunk-relative positions of exception values ({@code e} bytes)
+ * <li>Exception values: the high {@code b2} bits of every exception value, packed MSB-first
+ * ({@code e * b2} bits, padded to a byte.
+ * </ul>
+ */
+class PFOREncoding {
+ private static final int CHUNK_SIZE = 256;
+
+ private PFOREncoding() {}
+
+ /**
+ * Encodes {@code count} values from an array of unsigned byte values.
+ *
+ * @param values unsigned byte values to encode
+ * @param count number of values to encode
+ * @return a {@link ByteBuffer} of the encoded values with position and limit set for reading
+ */
+ static ByteBuffer encode(int[] values, int count) {
+ ByteBuffer out = ByteBuffer.allocate(estimateEncodedSize(count));
+ int bytesWritten = encode(values, 0, out, 0, count);
+ return out.slice(0, bytesWritten);
+ }
+
+ /**
+ * Encode {@code count} unsigned byte values from {@code values} into a buffer.
+ *
+ * <p>The buffer's position and limit are not modified.
+ *
+ * @param values unsigned byte values to encode
+ * @param valueOffset starting offset of values to encode
+ * @param out buffer to write encoded values to
+ * @param outOffset starting offset in the output buffer
+ * @param count number of values to encode
+ * @return the number of bytes written to the buffer
+ */
+ static int encode(int[] values, int valueOffset, ByteBuffer out, int outOffset, int count) {
+ // outOffset is relative to the buffer's position; check the encoded data fits
+ Preconditions.checkArgument(outOffset >= 0, "Cannot encode at negative offset: %s", outOffset);
+ Preconditions.checkArgument(
+ estimateEncodedSize(count) <= out.remaining() - outOffset,
+ "Cannot encode %s values to buffer with %s remaining space",
+ count,
+ out.remaining() - outOffset);
+
+ int bytesWritten = 0;
+ int valuesEncoded = 0;
+
+ while (valuesEncoded < count) {
+ int chunkLength = Math.min(CHUNK_SIZE, count - valuesEncoded);
+ bytesWritten +=
+ encodeChunk(
+ values, valueOffset + valuesEncoded, out, outOffset + bytesWritten, chunkLength);
+ valuesEncoded += chunkLength;
+ }
+
+ return bytesWritten;
+ }
+
+ /**
+ * Decode to produce unsigned byte values.
+ *
+ * <p>Decodes starting at {@code encoded.position()} and does not modify the input buffer.
+ *
+ * @param encoded PFOR-encoded ByteBuffer produced by {@link #encode}
+ * @param count total number of values to decode
+ * @return decoded unsigned byte values
+ */
+ static int[] decode(ByteBuffer encoded, int count) {
+ int[] out = new int[count];
+ decode(encoded, 0, out, 0, count);
+ return out;
+ }
+
+ /**
+ * Decode {@code count} unsigned bytes from a buffer into {@code out}.
+ *
+ * <p>This does not modify the input buffer.
+ *
+ * @param encoded a buffer containing encoded data
+ * @param offset starting offset of encoded values
+ * @param out an output value array
+ * @param outOffset starting offset in the output array
+ * @param count number of values to decode
+ * @return the number of bytes read from the encoded buffer
+ */
+ static int decode(ByteBuffer encoded, int offset, int[] out, int outOffset, int count) {
+ Preconditions.checkArgument(offset >= 0, "Cannot decode at negative offset: %s", offset);
+
+ int bytesRead = 0;
+ int valuesRead = 0;
+
+ while (valuesRead < count) {
+ int chunkSize = Math.min(CHUNK_SIZE, count - valuesRead);
+ bytesRead += decodeChunk(encoded, offset + bytesRead, out, outOffset + valuesRead, chunkSize);
+ valuesRead += chunkSize;
+ }
+
+ return bytesRead;
+ }
+
+ /**
+ * Encode one chunk into {@code out} starting at absolute position {@code outPos}.
+ *
+ * @param values array containing source values to encode
+ * @param valueOffset starting index of values to encode
+ * @param out an output {@link ByteBuffer}
+ * @param outOffset starting index for output in the out buffer
+ * @param count number of values to encode
+ * @return the number of bytes written to the output buffer
+ */
+ private static int encodeChunk(
+ int[] values, int valueOffset, ByteBuffer out, int outOffset, int count) {
+ Preconditions.checkArgument(count >= 0, "Invalid value count to encode: %s", count);
+ Preconditions.checkArgument(
+ valueOffset + count <= values.length,
+ "Cannot encode %s values starting at %s from int[%s]: not enough values",
+ count,
+ valueOffset,
+ values.length);
+
+ // find base=min(values) for normalization
+ int base = min(values, valueOffset, count);
+
+ // normalize by subtracting base
+ int[] normalized = new int[count];
+ int setBits = 0;
+ int normalizedSetBits = 0;
+ for (int i = 0; i < count; i += 1) {
+ setBits |= values[valueOffset + i];
+ normalized[i] = values[valueOffset + i] - base;
+ normalizedSetBits |= normalized[i];
+ }
+
+ Preconditions.checkArgument(
+ width(setBits) <= 8,
+ "Cannot encode values wider than 8 bits: %s bits needed",
+ width(setBits));
+
+ // Choose b1 to minimize total encoded data size (excluding 3-byte header)
+ int maxWidth = width(normalizedSetBits);
+ Pair<Integer, Integer> widthAndExcCount = chooseBitWidth(normalized, count, maxWidth);
+ int b1 = widthAndExcCount.first();
+ int b2 = maxWidth - b1;
+ int excCount = widthAndExcCount.second();
+
+ // check that there is enough space in the buffer for the encoded data
+ int requiredSize = encodedSize(count, b1, b2, excCount);
+ Preconditions.checkArgument(
+ outOffset + requiredSize <= out.remaining(),
+ "Cannot encode %s values (%s bytes) into buffer with %s remaining bytes",
+ count,
+ requiredSize,
+ out.remaining() - outOffset);
+
+ // Special case: b1=8 means store original values as raw bytes with b2, e, and m set to 0.
+ if (b1 == 8) {
+ writeHeader(out, outOffset, b1, 0 /* b2 */, 0 /* excCount */, 0 /* m */);
+ return 3 + BitPacking.packBits(8, values, valueOffset, out, outOffset + 3, count);
+ }
+
+ int bytesWritten = writeHeader(out, outOffset, b1, b2, excCount, base);
+
+ // Primary array: low b1 bits of every value
+ bytesWritten += BitPacking.packBits(b1, normalized, 0, out, outOffset + bytesWritten, count);
+
+ // b2 is the bit width of exception values: (maxWidth - b1) bits of each exception
+ if (excCount > 0) {
+ int[] excOffsets = new int[excCount];
+ int[] excValues = new int[excCount];
+
+ // Collect exceptions (values that do not fit in b1 bits)
+ int excIndex = 0;
+ int threshold = 1 << b1;
+ for (int i = 0; i < count; i += 1) {
+ if (normalized[i] >= threshold) {
+ excOffsets[excIndex] = i;
+ excValues[excIndex] = normalized[i] >>> b1;
+ excIndex += 1;
+ }
+ }
+
+ // Exception offsets (one byte per exception)
+ bytesWritten +=
+ BitPacking.packBits(8, excOffsets, 0, out, outOffset + bytesWritten, excCount);
+
+ // Exception values: remaining high b2 bits of each exception
+ bytesWritten +=
+ BitPacking.packBits(b2, excValues, 0, out, outOffset + bytesWritten, excCount);
+ }
+
+ return bytesWritten;
+ }
+
+ /**
+ * Decode one chunk of encoded data, writing decoded values into an output array.
+ *
+ * @param data buffer containing source data to decode
+ * @param dataOffset starting index in the buffer to decode
+ * @param out an output {@link ByteBuffer}
+ * @param outOffset starting index for output in the out buffer
+ * @param count number of values to decode
+ * @return the number of bytes read from {@code data}
+ */
+ private static int decodeChunk(
+ ByteBuffer data, int dataOffset, int[] out, int outOffset, int count) {
+ Preconditions.checkArgument(count >= 0, "Invalid value count to decode: %s", count);
+ Preconditions.checkArgument(
+ outOffset + count <= out.length,
+ "Cannot decode %s values starting at %s into int[%s]: not enough space",
+ count,
+ outOffset,
+ out.length);
+
+ int b1 = ByteBuffers.readByte(data, dataOffset) & 0x0F;
+ int b2 = (ByteBuffers.readByte(data, dataOffset) >>> 4) & 0x0F;
+ int excCount = ByteBuffers.readByte(data, dataOffset + 1);
+ int base = ByteBuffers.readByte(data, dataOffset + 2);
+ int bytesRead = 3;
+
+ // after reading the header, check that the full chunk is present
+ int expectedSize = encodedSize(count, b1, b2, excCount);
+ Preconditions.checkArgument(
+ dataOffset + expectedSize <= data.remaining(),
+ "Cannot decode %s values (%s bytes) from buffer with %s remaining bytes",
+ count,
+ expectedSize,
+ data.remaining() - dataOffset);
+
+ // Read primary array: low b1 bits of each value
+ bytesRead += BitPacking.unpackBits(b1, data, dataOffset + bytesRead, out, outOffset, count);
+
+ // Read exceptions and update output values
+ if (excCount > 0) {
+ int[] excOffsets = new int[excCount];
+ int[] excValues = new int[excCount];
+ int excListOffset = dataOffset + bytesRead;
+ int excDataOffset = dataOffset + bytesRead + excCount;
+
+ // Read exception indexes
+ bytesRead += BitPacking.unpackBits(8, data, excListOffset, excOffsets, 0, excCount);
+
+ // Read exception values and patch the primary values
+ bytesRead += BitPacking.unpackBits(b2, data, excDataOffset, excValues, 0, excCount);
+
+ // Update output values
+ for (int i = 0; i < excCount; i += 1) {
+ out[outOffset + excOffsets[i]] |= excValues[i] << b1;
+ }
+ }
+
+ // Add back the chunk minimum
+ for (int i = 0; i < count; i += 1) {
+ out[outOffset + i] += base;
+ }
+
+ return bytesRead;
+ }
+
+ private static int writeHeader(
+ ByteBuffer out, int outOffset, int b1, int b2, int excCount, int base) {
+ // Header: b1 in low nibble, b2 in high nibble, then e, then m
+ ByteBuffers.writeByte(out, (b2 << 4) | (b1 & 0b1111), outOffset);
+ ByteBuffers.writeByte(out, excCount, outOffset + 1);
+ ByteBuffers.writeByte(out, base, outOffset + 2);
+
+ return 3;
+ }
+
+ /**
+ * Choose the primary bit width {@code b1} that minimizes total encoded chunk size.
+ *
+ * <p>This produces the width that results in the smallest total size and the number of exceptions
+ * for that width.
+ *
+ * <p>Larger width is preferred on ties to reduce the number of exceptions.
+ *
+ * @param normalized value array to encode, after normalization
+ * @param length number of values in the array to encode
+ * @param maxWidth the largest bit width of normalized values
+ * @return a {@link Pair} of the chosen width and number of exceptions for that width
+ */
+ private static Pair<Integer, Integer> chooseBitWidth(int[] normalized, int length, int maxWidth) {
+ int bestWidth = 0;
+ int bestSize = Integer.MAX_VALUE;
+ int bestExcCount = 0;
+
+ for (int candidateWidth = 0; candidateWidth <= maxWidth; candidateWidth += 1) {
+ int excCount = 0;
+ if (candidateWidth < 8) {
+ int threshold = 1 << candidateWidth;
+ for (int i = 0; i < length; i += 1) {
+ if (normalized[i] >= threshold) {
+ excCount += 1;
+ }
+ }
+ }
+
+ int b2 = maxWidth - candidateWidth;
+ int size = byteWidth(length * candidateWidth) + excCount + byteWidth(excCount * b2);
+
+ if (size <= bestSize) {
+ bestSize = size;
+ bestWidth = candidateWidth;
+ bestExcCount = excCount;
+ }
+ }
+
+ return Pair.of(bestWidth, bestExcCount);
+ }
+
+ /**
+ * Return the lowest byte value from the array slice [start, start + length).
+ *
+ * <p>If length is < 1, the result will be larger than Byte.MAX_VALUE.
+ *
+ * @param values array of values
+ * @param start starting index
+ * @param length number of values to check
+ * @return the min of the values in the array slice
+ */
+ private static int min(int[] values, int start, int length) {
+ // Use min > Byte.MAX_VALUE to signal no min (length < 1)
+ int min = 256;
Review Comment:
Any reason to use 256, and not `Byte.MAX_VALUE + 1` (which equals 128)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] Core: Add a read-only Mumbling bitmap implementation [iceberg]
Posted by "amogh-jahagirdar (via GitHub)" <gi...@apache.org>.
amogh-jahagirdar commented on PR #16747:
URL: https://github.com/apache/iceberg/pull/16747#issuecomment-5699143060
I'll go ahead and merge this, I think the remaining comments can be done in a follow up. Thank you @rdblue and thank you @pvary @anoopj @nssalian @Fokko for reviewing.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] Core: Add a read-only Mumbling bitmap implementation [iceberg]
Posted by "amogh-jahagirdar (via GitHub)" <gi...@apache.org>.
amogh-jahagirdar commented on code in PR #16747:
URL: https://github.com/apache/iceberg/pull/16747#discussion_r4017838522
##########
core/src/main/java/org/apache/iceberg/mumbling/MumblingBitmap.java:
##########
@@ -0,0 +1,168 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.iceberg.mumbling;
+
+import java.nio.ByteBuffer;
+import org.apache.iceberg.relocated.com.google.common.base.Preconditions;
+
+/**
+ * Read-only view of a Mumbling compressed bitmap stored in a {@link ByteBuffer}.
+ *
+ * <p>The bitmap is lazy: no decoding is done at construction time. On the first call to {@link
+ * #isSet}, the PFOR-encoded descriptor array is decoded and used to build an offsets array that
+ * maps each container index to its absolute byte position in the buffer. This offsets array is the
+ * only derived state kept by this class.
+ *
+ * <p>Format (all integers unsigned, little-endian):
+ *
+ * <ul>
+ * <li>Header (6 bytes): version (1), cardinality (3), container count (2)
+ * <li>Descriptor array: PFOR-encoded, one byte per container
+ * <li>Containers: concatenated sparse (0–31 bytes) or dense (32 bytes) containers
+ * </ul>
+ */
+class MumblingBitmap {
+ private static final int VERSION = 1;
+ private static final int HEADER_SIZE = 6;
+ private static final int DENSE_CONTAINER_BIT = 0b0010_0000;
+
+ private final ByteBuffer data;
+ private final int cardinality;
+ private final int containerCount;
+ private int[] descriptors = null;
+ private int[] offsets = null;
Review Comment:
Another case is for columnar updates, if we update a leaf manifest via column update, I _think_ we'd need to share the inline DV for both base leaf manifest + column update. But that's a later problem.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] Core: Add a read-only Mumbling bitmap implementation [iceberg]
Posted by "rdblue (via GitHub)" <gi...@apache.org>.
rdblue commented on code in PR #16747:
URL: https://github.com/apache/iceberg/pull/16747#discussion_r3384392634
##########
core/src/main/java/org/apache/iceberg/mumbling/MumblingBitmap.java:
##########
@@ -0,0 +1,169 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.iceberg.mumbling;
+
+import java.nio.ByteBuffer;
+import org.apache.curator.shaded.com.google.common.base.Preconditions;
+
+/**
+ * Read-only view of a Mumbling compressed bitmap stored in a {@link ByteBuffer}.
+ *
+ * <p>The bitmap is lazy: no decoding is done at construction time. On the first call to {@link
+ * #isSet}, the PFOR-encoded descriptor array is decoded and used to build an offsets array that
+ * maps each container index to its absolute byte position in the buffer. This offsets array is the
+ * only derived state kept by this class.
+ *
+ * <p>Format (all integers unsigned, little-endian):
+ *
+ * <ul>
+ * <li>Header (6 bytes): version (1), cardinality (3), container count (2)
+ * <li>Descriptor array: PFOR-encoded, one byte per container
+ * <li>Containers: concatenated sparse (0–31 bytes) or dense (32 bytes) containers
+ * </ul>
+ */
+class MumblingBitmap {
+ private static final int VERSION = 1;
+ private static final int HEADER_SIZE = 6;
+ private static final int DENSE_CONTAINER_BIT = 0b0010_0000;
+
+ private final ByteBuffer data;
+ private final int cardinality;
+ private final int containerCount;
+ private int[] descriptors = null;
+ private int[] offsets = null;
+
+ MumblingBitmap(ByteBuffer data) {
+ int version = data.get(data.position()) & 0xFF;
+ if (version != VERSION) {
+ throw new UnsupportedOperationException("Unsupported Mumbling bitmap version: " + version);
+ }
+
+ this.data = data;
+ this.cardinality =
+ (data.get(data.position() + 1) & 0xFF)
+ | ((data.get(data.position() + 2) & 0xFF) << 8)
+ | ((data.get(data.position() + 3) & 0xFF) << 16);
Review Comment:
This and other direct reads will be refactored to use utils in `ByteBuffers` after #16748 moves them out of `VariantUtil`.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] Core: Add a read-only Mumbling bitmap implementation [iceberg]
Posted by "pvary (via GitHub)" <gi...@apache.org>.
pvary commented on code in PR #16747:
URL: https://github.com/apache/iceberg/pull/16747#discussion_r3389658120
##########
core/src/jmh/java/org/apache/iceberg/mumbling/PFOREncodingBenchmark.java:
##########
@@ -0,0 +1,212 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.iceberg.mumbling;
+
+import java.nio.ByteBuffer;
+import java.util.Random;
+import java.util.concurrent.TimeUnit;
+import me.lemire.integercompression.FastPFOR128;
+import me.lemire.integercompression.IntWrapper;
+import org.openjdk.jmh.annotations.Benchmark;
+import org.openjdk.jmh.annotations.BenchmarkMode;
+import org.openjdk.jmh.annotations.Fork;
+import org.openjdk.jmh.annotations.Measurement;
+import org.openjdk.jmh.annotations.Mode;
+import org.openjdk.jmh.annotations.Scope;
+import org.openjdk.jmh.annotations.Setup;
+import org.openjdk.jmh.annotations.State;
+import org.openjdk.jmh.annotations.Threads;
+import org.openjdk.jmh.annotations.Timeout;
+import org.openjdk.jmh.annotations.Warmup;
+import org.openjdk.jmh.infra.Blackhole;
+
+/**
+ * A benchmark that evaluates the performance of {@link PFOREncoding} and compares it with
+ * JavaFastPFOR.
+ *
+ * <p>Two data shapes are exercised:
+ *
+ * <ul>
+ * <li><b>Descriptor</b>: 256 values in {@code [0, 31]} with 5% full-range outliers, typical for
+ * Mumbling bitmap descriptor arrays.
+ * <li><b>Uniform byte</b>: 256 values drawn uniformly from {@code [0, 255]}, the worst case for
+ * PFOR (no compression benefit; exercises the fallback path).
+ * </ul>
+ *
+ * <p>To run this benchmark: <code>
+ * ./gradlew :iceberg-core:jmh
+ * -PjmhIncludeRegex=PFOREncodingBenchmark
+ * -PjmhOutputPath=benchmark/pfor-encoding-benchmark.txt
+ * </code>
+ */
+@Fork(1)
+@State(Scope.Benchmark)
+@Warmup(iterations = 3)
+@Measurement(iterations = 5)
+@BenchmarkMode(Mode.Throughput)
+@Timeout(time = 5, timeUnit = TimeUnit.MINUTES)
+public class PFOREncodingBenchmark {
+
+ // Iceberg PFOR input arrays
+ private int[] descriptorValues;
+ private int[] uniformValues;
+
+ // Pre-encoded buffers for decode benchmarks
+ private ByteBuffer descriptorEncoded;
+ private ByteBuffer uniformEncoded;
+
+ // Reusable encode buffer (avoids allocation in the encode hot path)
+ private ByteBuffer encodeBuffer;
+
+ // Reusable decode output (avoids allocation in the decode hot path)
+ private int[] decodeOutput;
+
+ // JavaFastPFOR compressed arrays (pre-encoded for decode benchmarks)
+ private int[] descriptorFastPFOREncoded;
+ private int[] uniformFastPFOREncoded;
+
+ // Reusable output buffers for JavaFastPFOR (avoids allocation in hot path)
+ private int[] fastPFOROutputBuffer;
+
+ @Setup
+ public void setupBenchmark() {
+ Random random = new Random(1938745);
+
+ // 256-value descriptor-like data: mostly [0,31] with ~5% [0,255] outliers
+ descriptorValues = PFORRandomData.exceptions(random, 256, 0.5f);
Review Comment:
0.05?
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] Core: Add a read-only Mumbling bitmap implementation [iceberg]
Posted by "rdblue (via GitHub)" <gi...@apache.org>.
rdblue commented on code in PR #16747:
URL: https://github.com/apache/iceberg/pull/16747#discussion_r4010286825
##########
core/src/main/java/org/apache/iceberg/mumbling/PFOREncoding.java:
##########
@@ -0,0 +1,402 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.iceberg.mumbling;
+
+import java.nio.ByteBuffer;
+import org.apache.iceberg.relocated.com.google.common.base.Preconditions;
+import org.apache.iceberg.util.ByteBuffers;
+import org.apache.iceberg.util.Pair;
+
+/**
+ * Patched Frame of Reference (PFOR) encoding for arrays of unsigned byte values.
+ *
+ * <p>Implements the encoding described in Appendix A of the Mumbling bitmap specification. The
+ * input array is split into 256-value chunks (the last chunk may be shorter). Each chunk is
+ * independently encoded using 4 configuration values:
+ *
+ * <ul>
+ * <li>{@code b1}: number of bits stored in the primary array for every normalized value
+ * <li>{@code b2}: number of bits stored per exception value (normalized value of > b1 bits)
+ * <li>{@code e}: number of exceptions with more than b1 bits
+ * <li>{@code m}: chunk-local minimum value, subtracted from all values to normalize
+ * </ul>
+ *
+ * <p>Each chunk is stored as:
+ *
+ * <ul>
+ * <li>3-byte header: {@code b1|b2} primary and exception bit widths (byte 0), {@code e} exception
+ * count (byte 1), {@code m} normalization base value (byte 2)
+ * <li>Primary array: the low {@code b1} bits of every normalized value, packed MSB-first ({@code
+ * b1 * n} bits, padded to a byte)
+ * <li>Exception offsets: chunk-relative positions of exception values ({@code e} bytes)
+ * <li>Exception values: the high {@code b2} bits of every exception value, packed MSB-first
+ * ({@code e * b2} bits, padded to a byte.
+ * </ul>
+ */
+class PFOREncoding {
+ private static final int CHUNK_SIZE = 256;
+
+ private PFOREncoding() {}
+
+ /**
+ * Encodes {@code count} values from an array of unsigned byte values.
+ *
+ * @param values unsigned byte values to encode
+ * @param count number of values to encode
+ * @return a {@link ByteBuffer} of the encoded values with position and limit set for reading
+ */
+ static ByteBuffer encode(int[] values, int count) {
+ ByteBuffer out = ByteBuffer.allocate(estimateEncodedSize(count));
+ int bytesWritten = encode(values, 0, out, 0, count);
+ return out.slice(0, bytesWritten);
+ }
+
+ /**
+ * Encode {@code count} unsigned byte values from {@code values} into a buffer.
+ *
+ * <p>The buffer's position and limit are not modified.
+ *
+ * @param values unsigned byte values to encode
+ * @param valueOffset starting offset of values to encode
+ * @param out buffer to write encoded values to
+ * @param outOffset starting offset in the output buffer
+ * @param count number of values to encode
+ * @return the number of bytes written to the buffer
+ */
+ static int encode(int[] values, int valueOffset, ByteBuffer out, int outOffset, int count) {
+ // outOffset is relative to the buffer's position; check the encoded data fits
+ Preconditions.checkArgument(outOffset >= 0, "Cannot encode at negative offset: %s", outOffset);
+ Preconditions.checkArgument(
+ estimateEncodedSize(count) <= out.remaining() - outOffset,
+ "Cannot encode %s values to buffer with %s remaining space",
+ count,
+ out.remaining() - outOffset);
+
+ int bytesWritten = 0;
+ int valuesEncoded = 0;
+
+ while (valuesEncoded < count) {
+ int chunkLength = Math.min(CHUNK_SIZE, count - valuesEncoded);
+ bytesWritten +=
+ encodeChunk(
+ values, valueOffset + valuesEncoded, out, outOffset + bytesWritten, chunkLength);
+ valuesEncoded += chunkLength;
+ }
+
+ return bytesWritten;
+ }
+
+ /**
+ * Decode to produce unsigned byte values.
+ *
+ * <p>Decodes starting at {@code encoded.position()} and does not modify the input buffer.
+ *
+ * @param encoded PFOR-encoded ByteBuffer produced by {@link #encode}
+ * @param count total number of values to decode
+ * @return decoded unsigned byte values
+ */
+ static int[] decode(ByteBuffer encoded, int count) {
+ int[] out = new int[count];
+ decode(encoded, 0, out, 0, count);
+ return out;
+ }
+
+ /**
+ * Decode {@code count} unsigned bytes from a buffer into {@code out}.
+ *
+ * <p>This does not modify the input buffer.
+ *
+ * @param encoded a buffer containing encoded data
+ * @param offset starting offset of encoded values
+ * @param out an output value array
+ * @param outOffset starting offset in the output array
+ * @param count number of values to decode
+ * @return the number of bytes read from the encoded buffer
+ */
+ static int decode(ByteBuffer encoded, int offset, int[] out, int outOffset, int count) {
+ Preconditions.checkArgument(offset >= 0, "Cannot decode at negative offset: %s", offset);
+
+ int bytesRead = 0;
+ int valuesRead = 0;
+
+ while (valuesRead < count) {
+ int chunkSize = Math.min(CHUNK_SIZE, count - valuesRead);
+ bytesRead += decodeChunk(encoded, offset + bytesRead, out, outOffset + valuesRead, chunkSize);
+ valuesRead += chunkSize;
+ }
+
+ return bytesRead;
+ }
+
+ /**
+ * Encode one chunk into {@code out} starting at absolute position {@code outPos}.
+ *
+ * @param values array containing source values to encode
+ * @param valueOffset starting index of values to encode
+ * @param out an output {@link ByteBuffer}
+ * @param outOffset starting index for output in the out buffer
+ * @param count number of values to encode
+ * @return the number of bytes written to the output buffer
+ */
+ private static int encodeChunk(
+ int[] values, int valueOffset, ByteBuffer out, int outOffset, int count) {
+ Preconditions.checkArgument(count >= 0, "Invalid value count to encode: %s", count);
+ Preconditions.checkArgument(
+ valueOffset + count <= values.length,
+ "Cannot encode %s values starting at %s from int[%s]: not enough values",
+ count,
+ valueOffset,
+ values.length);
+
+ // find base=min(values) for normalization
+ int base = min(values, valueOffset, count);
+
+ // normalize by subtracting base
+ int[] normalized = new int[count];
+ int setBits = 0;
+ int normalizedSetBits = 0;
+ for (int i = 0; i < count; i += 1) {
+ setBits |= values[valueOffset + i];
+ normalized[i] = values[valueOffset + i] - base;
+ normalizedSetBits |= normalized[i];
+ }
+
+ Preconditions.checkArgument(
+ width(setBits) <= 8,
+ "Cannot encode values wider than 8 bits: %s bits needed",
+ width(setBits));
+
+ // Choose b1 to minimize total encoded data size (excluding 3-byte header)
+ int maxWidth = width(normalizedSetBits);
+ Pair<Integer, Integer> widthAndExcCount = chooseBitWidth(normalized, count, maxWidth);
+ int b1 = widthAndExcCount.first();
+ int b2 = maxWidth - b1;
+ int excCount = widthAndExcCount.second();
+
+ // check that there is enough space in the buffer for the encoded data
+ int requiredSize = encodedSize(count, b1, b2, excCount);
+ Preconditions.checkArgument(
+ outOffset + requiredSize <= out.remaining(),
+ "Cannot encode %s values (%s bytes) into buffer with %s remaining bytes",
+ requiredSize,
+ out.remaining() - outOffset);
+
+ // Special case: b1=8 means store original values as raw bytes with b2, e, and m set to 0.
+ if (b1 == 8) {
+ writeHeader(out, outOffset, b1, 0 /* b2 */, 0 /* excCount */, 0 /* m */);
+ return 3 + BitPacking.packBits(8, values, valueOffset, out, outOffset + 3, count);
+ }
+
+ int bytesWritten = writeHeader(out, outOffset, b1, b2, excCount, base);
+
+ // Primary array: low b1 bits of every value
+ bytesWritten += BitPacking.packBits(b1, normalized, 0, out, outOffset + bytesWritten, count);
+
+ // b2 is the bit width of exception values: (maxWidth - b1) bits of each exception
+ if (excCount > 0) {
+ int[] excOffsets = new int[excCount];
+ int[] excValues = new int[excCount];
+
+ // Collect exceptions (values that do not fit in b1 bits)
+ int excIndex = 0;
+ int threshold = 1 << b1;
+ for (int i = 0; i < count; i += 1) {
+ if (normalized[i] >= threshold) {
+ excOffsets[excIndex] = i;
+ excValues[excIndex] = normalized[i] >>> b1;
+ excIndex += 1;
+ }
+ }
+
+ // Exception offsets (one byte per exception)
+ bytesWritten +=
+ BitPacking.packBits(8, excOffsets, 0, out, outOffset + bytesWritten, excCount);
+
+ // Exception values: remaining high b2 bits of each exception
+ bytesWritten +=
+ BitPacking.packBits(b2, excValues, 0, out, outOffset + bytesWritten, excCount);
+ }
+
+ return bytesWritten;
+ }
+
+ /**
+ * Decode one chunk of encoded data, writing decoded values into an output array.
+ *
+ * @param data buffer containing source data to decode
+ * @param dataOffset starting index in the buffer to decode
+ * @param out an output {@link ByteBuffer}
+ * @param outOffset starting index for output in the out buffer
+ * @param count number of values to decode
+ * @return the number of bytes read from {@code data}
+ */
+ private static int decodeChunk(
+ ByteBuffer data, int dataOffset, int[] out, int outOffset, int count) {
+ Preconditions.checkArgument(count >= 0, "Invalid value count to decode: %s", count);
+ Preconditions.checkArgument(
+ outOffset + count <= out.length,
+ "Cannot decode %s values starting at %s into int[%s]: not enough space",
+ count,
+ outOffset,
+ out.length);
+
+ int b1 = ByteBuffers.readByte(data, dataOffset) & 0x0F;
Review Comment:
This would fail with an `IndexOutOfBoundsException` if the last index passed to `readByte` is beyond the limit of the buffer. I think that's a good exception because it would target the read that failed (`base = ByteBuffers.readByte(data, dataOffset + 2)`) and it would be clear that the data is truncated.
What would we want to change about that exception? All this code knows is that the byte buffer it was passed is not long enough. It can't tell why that is the case.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] Core: Add a read-only Mumbling bitmap implementation [iceberg]
Posted by "rdblue (via GitHub)" <gi...@apache.org>.
rdblue commented on code in PR #16747:
URL: https://github.com/apache/iceberg/pull/16747#discussion_r4010388325
##########
core/src/main/java/org/apache/iceberg/mumbling/MumblingBitmap.java:
##########
@@ -0,0 +1,168 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.iceberg.mumbling;
+
+import java.nio.ByteBuffer;
+import org.apache.iceberg.relocated.com.google.common.base.Preconditions;
+
+/**
+ * Read-only view of a Mumbling compressed bitmap stored in a {@link ByteBuffer}.
+ *
+ * <p>The bitmap is lazy: no decoding is done at construction time. On the first call to {@link
+ * #isSet}, the PFOR-encoded descriptor array is decoded and used to build an offsets array that
+ * maps each container index to its absolute byte position in the buffer. This offsets array is the
+ * only derived state kept by this class.
+ *
+ * <p>Format (all integers unsigned, little-endian):
+ *
+ * <ul>
+ * <li>Header (6 bytes): version (1), cardinality (3), container count (2)
+ * <li>Descriptor array: PFOR-encoded, one byte per container
+ * <li>Containers: concatenated sparse (0–31 bytes) or dense (32 bytes) containers
+ * </ul>
+ */
+class MumblingBitmap {
+ private static final int VERSION = 1;
+ private static final int HEADER_SIZE = 6;
+ private static final int DENSE_CONTAINER_BIT = 0b0010_0000;
+
+ private final ByteBuffer data;
+ private final int cardinality;
+ private final int containerCount;
+ private int[] descriptors = null;
+ private int[] offsets = null;
+
+ MumblingBitmap(ByteBuffer data) {
+ int version = data.get(data.position()) & 0xFF;
+ if (version != VERSION) {
+ throw new UnsupportedOperationException("Unsupported Mumbling bitmap version: " + version);
+ }
+
+ this.data = data;
+ this.cardinality =
+ (data.get(data.position() + 1) & 0xFF)
+ | ((data.get(data.position() + 2) & 0xFF) << 8)
+ | ((data.get(data.position() + 3) & 0xFF) << 16);
+ this.containerCount =
+ (data.get(data.position() + 4) & 0xFF) | ((data.get(data.position() + 5) & 0xFF) << 8);
+ }
+
+ /** Returns the number of bits set in the bitmap. */
+ public int cardinality() {
+ return cardinality;
+ }
+
+ /**
+ * Returns {@code true} if the bit at {@code pos} is set in the bitmap.
+ *
+ * <p>Positions beyond the range of any container are always unset.
+ */
+ public boolean isSet(int pos) {
+ Preconditions.checkArgument(pos >= 0, "Invalid bit position: %s < 0", pos);
+ int containerIndex = pos >>> 8;
+ int posInContainer = pos & 0xFF;
+
+ if (containerIndex >= containerCount) {
+ return false;
+ }
+
+ int containerStart = offset(containerIndex);
+ int descriptor = descriptor(containerIndex);
+
+ if (isDense(descriptor)) {
+ // Dense: 32-byte bitset, MSB of byte 0 is position 0
+ int byteIndex = posInContainer >>> 3;
+ int bitShift = 7 - (posInContainer & 0b111);
+ return ((data.get(containerStart + byteIndex) >>> bitShift) & 0b1) == 0b1;
+
+ } else {
+ // Sparse: sorted list of set positions; scan until found or exceeded
+ for (int i = 0; i < descriptor; i += 1) {
+ int stored = data.get(containerStart + i) & 0xFF;
+ if (stored == posInContainer) {
+ return true;
+ }
+
+ if (stored > posInContainer) {
+ return false;
+ }
+ }
+
+ return false;
+ }
+ }
+
+ private int descriptor(int containerIndex) {
+ if (null == descriptors) {
+ decodeDescriptors();
+ }
+
+ return descriptors[containerIndex];
+ }
+
+ private int offset(int containerIndex) {
+ if (null == offsets) {
+ decodeDescriptors();
+ }
+
+ return offsets[containerIndex];
+ }
+
+ /**
+ * Decode the descriptor array and produce an array of absolute container offsets in the buffer.
+ */
+ private void decodeDescriptors() {
+ this.descriptors = new int[containerCount];
+ int bytesRead = PFOREncoding.decode(data, HEADER_SIZE, descriptors, 0, containerCount);
+
+ this.offsets = new int[containerCount + 1];
+ int firstContainerOffset = data.position() + HEADER_SIZE + bytesRead;
+ descriptorsToOffsets(firstContainerOffset, descriptors, offsets);
+ }
+
+ private static boolean isDense(int descriptor) {
+ return (descriptor & DENSE_CONTAINER_BIT) == DENSE_CONTAINER_BIT;
+ }
+
+ /**
+ * Convert an array of lengths into an array of offsets starting at 0.
+ *
+ * <p>For example, descriptorsToOffsets([1, 1, 2]) produces [0, 1, 2, 4].
+ *
+ * @param baseOffset initial offset of the first container
+ * @param descriptors an array of descriptor bytes
+ * @param offsets output array of offsets
+ */
+ private static void descriptorsToOffsets(int baseOffset, int[] descriptors, int[] offsets) {
+ Preconditions.checkArgument(
+ offsets.length > descriptors.length,
+ "Cannot decode %s lengths into %s offsets (not enough space)",
+ descriptors.length,
+ offsets.length);
+
+ offsets[0] = baseOffset;
+ for (int i = 0; i < descriptors.length; i += 1) {
+ if (isDense(descriptors[i])) {
+ offsets[i + 1] = offsets[i] + 32;
Review Comment:
Fixed.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] Core: Add a read-only Mumbling bitmap implementation [iceberg]
Posted by "rdblue (via GitHub)" <gi...@apache.org>.
rdblue commented on code in PR #16747:
URL: https://github.com/apache/iceberg/pull/16747#discussion_r4010733185
##########
core/src/main/java/org/apache/iceberg/mumbling/PFOREncoding.java:
##########
@@ -0,0 +1,402 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements. See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership. The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied. See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+package org.apache.iceberg.mumbling;
+
+import java.nio.ByteBuffer;
+import org.apache.iceberg.relocated.com.google.common.base.Preconditions;
+import org.apache.iceberg.util.ByteBuffers;
+import org.apache.iceberg.util.Pair;
+
+/**
+ * Patched Frame of Reference (PFOR) encoding for arrays of unsigned byte values.
+ *
+ * <p>Implements the encoding described in Appendix A of the Mumbling bitmap specification. The
+ * input array is split into 256-value chunks (the last chunk may be shorter). Each chunk is
+ * independently encoded using 4 configuration values:
+ *
+ * <ul>
+ * <li>{@code b1}: number of bits stored in the primary array for every normalized value
+ * <li>{@code b2}: number of bits stored per exception value (normalized value of > b1 bits)
+ * <li>{@code e}: number of exceptions with more than b1 bits
+ * <li>{@code m}: chunk-local minimum value, subtracted from all values to normalize
+ * </ul>
+ *
+ * <p>Each chunk is stored as:
+ *
+ * <ul>
+ * <li>3-byte header: {@code b1|b2} primary and exception bit widths (byte 0), {@code e} exception
+ * count (byte 1), {@code m} normalization base value (byte 2)
+ * <li>Primary array: the low {@code b1} bits of every normalized value, packed MSB-first ({@code
+ * b1 * n} bits, padded to a byte)
+ * <li>Exception offsets: chunk-relative positions of exception values ({@code e} bytes)
+ * <li>Exception values: the high {@code b2} bits of every exception value, packed MSB-first
+ * ({@code e * b2} bits, padded to a byte.
+ * </ul>
+ */
+class PFOREncoding {
+ private static final int CHUNK_SIZE = 256;
+
+ private PFOREncoding() {}
+
+ /**
+ * Encodes {@code count} values from an array of unsigned byte values.
+ *
+ * @param values unsigned byte values to encode
+ * @param count number of values to encode
+ * @return a {@link ByteBuffer} of the encoded values with position and limit set for reading
+ */
+ static ByteBuffer encode(int[] values, int count) {
+ ByteBuffer out = ByteBuffer.allocate(estimateEncodedSize(count));
+ int bytesWritten = encode(values, 0, out, 0, count);
+ return out.slice(0, bytesWritten);
+ }
+
+ /**
+ * Encode {@code count} unsigned byte values from {@code values} into a buffer.
+ *
+ * <p>The buffer's position and limit are not modified.
+ *
+ * @param values unsigned byte values to encode
+ * @param valueOffset starting offset of values to encode
+ * @param out buffer to write encoded values to
+ * @param outOffset starting offset in the output buffer
+ * @param count number of values to encode
+ * @return the number of bytes written to the buffer
+ */
+ static int encode(int[] values, int valueOffset, ByteBuffer out, int outOffset, int count) {
+ // outOffset is relative to the buffer's position; check the encoded data fits
+ Preconditions.checkArgument(outOffset >= 0, "Cannot encode at negative offset: %s", outOffset);
+ Preconditions.checkArgument(
+ estimateEncodedSize(count) <= out.remaining() - outOffset,
+ "Cannot encode %s values to buffer with %s remaining space",
+ count,
+ out.remaining() - outOffset);
+
+ int bytesWritten = 0;
+ int valuesEncoded = 0;
+
+ while (valuesEncoded < count) {
+ int chunkLength = Math.min(CHUNK_SIZE, count - valuesEncoded);
+ bytesWritten +=
+ encodeChunk(
+ values, valueOffset + valuesEncoded, out, outOffset + bytesWritten, chunkLength);
+ valuesEncoded += chunkLength;
+ }
+
+ return bytesWritten;
+ }
+
+ /**
+ * Decode to produce unsigned byte values.
+ *
+ * <p>Decodes starting at {@code encoded.position()} and does not modify the input buffer.
+ *
+ * @param encoded PFOR-encoded ByteBuffer produced by {@link #encode}
+ * @param count total number of values to decode
+ * @return decoded unsigned byte values
+ */
+ static int[] decode(ByteBuffer encoded, int count) {
+ int[] out = new int[count];
+ decode(encoded, 0, out, 0, count);
+ return out;
+ }
+
+ /**
+ * Decode {@code count} unsigned bytes from a buffer into {@code out}.
+ *
+ * <p>This does not modify the input buffer.
+ *
+ * @param encoded a buffer containing encoded data
+ * @param offset starting offset of encoded values
+ * @param out an output value array
+ * @param outOffset starting offset in the output array
+ * @param count number of values to decode
+ * @return the number of bytes read from the encoded buffer
+ */
+ static int decode(ByteBuffer encoded, int offset, int[] out, int outOffset, int count) {
+ Preconditions.checkArgument(offset >= 0, "Cannot decode at negative offset: %s", offset);
+
+ int bytesRead = 0;
+ int valuesRead = 0;
+
+ while (valuesRead < count) {
+ int chunkSize = Math.min(CHUNK_SIZE, count - valuesRead);
+ bytesRead += decodeChunk(encoded, offset + bytesRead, out, outOffset + valuesRead, chunkSize);
+ valuesRead += chunkSize;
+ }
+
+ return bytesRead;
+ }
+
+ /**
+ * Encode one chunk into {@code out} starting at absolute position {@code outPos}.
+ *
+ * @param values array containing source values to encode
+ * @param valueOffset starting index of values to encode
+ * @param out an output {@link ByteBuffer}
+ * @param outOffset starting index for output in the out buffer
+ * @param count number of values to encode
+ * @return the number of bytes written to the output buffer
+ */
+ private static int encodeChunk(
+ int[] values, int valueOffset, ByteBuffer out, int outOffset, int count) {
+ Preconditions.checkArgument(count >= 0, "Invalid value count to encode: %s", count);
+ Preconditions.checkArgument(
+ valueOffset + count <= values.length,
+ "Cannot encode %s values starting at %s from int[%s]: not enough values",
+ count,
+ valueOffset,
+ values.length);
+
+ // find base=min(values) for normalization
+ int base = min(values, valueOffset, count);
+
+ // normalize by subtracting base
+ int[] normalized = new int[count];
+ int setBits = 0;
+ int normalizedSetBits = 0;
+ for (int i = 0; i < count; i += 1) {
+ setBits |= values[valueOffset + i];
+ normalized[i] = values[valueOffset + i] - base;
+ normalizedSetBits |= normalized[i];
+ }
+
+ Preconditions.checkArgument(
+ width(setBits) <= 8,
+ "Cannot encode values wider than 8 bits: %s bits needed",
+ width(setBits));
+
+ // Choose b1 to minimize total encoded data size (excluding 3-byte header)
+ int maxWidth = width(normalizedSetBits);
+ Pair<Integer, Integer> widthAndExcCount = chooseBitWidth(normalized, count, maxWidth);
+ int b1 = widthAndExcCount.first();
+ int b2 = maxWidth - b1;
+ int excCount = widthAndExcCount.second();
+
+ // check that there is enough space in the buffer for the encoded data
+ int requiredSize = encodedSize(count, b1, b2, excCount);
+ Preconditions.checkArgument(
+ outOffset + requiredSize <= out.remaining(),
+ "Cannot encode %s values (%s bytes) into buffer with %s remaining bytes",
+ requiredSize,
+ out.remaining() - outOffset);
+
+ // Special case: b1=8 means store original values as raw bytes with b2, e, and m set to 0.
+ if (b1 == 8) {
+ writeHeader(out, outOffset, b1, 0 /* b2 */, 0 /* excCount */, 0 /* m */);
+ return 3 + BitPacking.packBits(8, values, valueOffset, out, outOffset + 3, count);
+ }
+
+ int bytesWritten = writeHeader(out, outOffset, b1, b2, excCount, base);
+
+ // Primary array: low b1 bits of every value
+ bytesWritten += BitPacking.packBits(b1, normalized, 0, out, outOffset + bytesWritten, count);
+
+ // b2 is the bit width of exception values: (maxWidth - b1) bits of each exception
+ if (excCount > 0) {
+ int[] excOffsets = new int[excCount];
+ int[] excValues = new int[excCount];
+
+ // Collect exceptions (values that do not fit in b1 bits)
+ int excIndex = 0;
+ int threshold = 1 << b1;
+ for (int i = 0; i < count; i += 1) {
+ if (normalized[i] >= threshold) {
+ excOffsets[excIndex] = i;
+ excValues[excIndex] = normalized[i] >>> b1;
+ excIndex += 1;
+ }
+ }
+
+ // Exception offsets (one byte per exception)
+ bytesWritten +=
+ BitPacking.packBits(8, excOffsets, 0, out, outOffset + bytesWritten, excCount);
+
+ // Exception values: remaining high b2 bits of each exception
+ bytesWritten +=
+ BitPacking.packBits(b2, excValues, 0, out, outOffset + bytesWritten, excCount);
+ }
+
+ return bytesWritten;
+ }
+
+ /**
+ * Decode one chunk of encoded data, writing decoded values into an output array.
+ *
+ * @param data buffer containing source data to decode
+ * @param dataOffset starting index in the buffer to decode
+ * @param out an output {@link ByteBuffer}
+ * @param outOffset starting index for output in the out buffer
+ * @param count number of values to decode
+ * @return the number of bytes read from {@code data}
+ */
+ private static int decodeChunk(
+ ByteBuffer data, int dataOffset, int[] out, int outOffset, int count) {
+ Preconditions.checkArgument(count >= 0, "Invalid value count to decode: %s", count);
+ Preconditions.checkArgument(
+ outOffset + count <= out.length,
+ "Cannot decode %s values starting at %s into int[%s]: not enough space",
+ count,
+ outOffset,
+ out.length);
+
+ int b1 = ByteBuffers.readByte(data, dataOffset) & 0x0F;
+ int b2 = (ByteBuffers.readByte(data, dataOffset) >>> 4) & 0x0F;
+ int excCount = ByteBuffers.readByte(data, dataOffset + 1);
+ int base = ByteBuffers.readByte(data, dataOffset + 2);
+ int bytesRead = 3;
+
+ // after reading the header, check that the full chunk is present
+ int expectedSize = encodedSize(count, b1, b2, excCount);
+ Preconditions.checkArgument(
+ dataOffset + expectedSize <= data.remaining(),
+ "Cannot decode %s values from buffer with %s remaining bytes",
+ expectedSize,
+ data.remaining() - dataOffset);
+
+ // Read primary array: low b1 bits of each value
+ bytesRead += BitPacking.unpackBits(b1, data, dataOffset + bytesRead, out, outOffset, count);
+
+ // Read exceptions and update output values
+ if (excCount > 0) {
+ int[] excOffsets = new int[excCount];
+ int[] excValues = new int[excCount];
+ int excListOffset = dataOffset + bytesRead;
+ int excDataOffset = dataOffset + bytesRead + excCount;
+
+ // Read exception indexes
+ bytesRead += BitPacking.unpackBits(8, data, excListOffset, excOffsets, 0, excCount);
+
+ // Read exception values and patch the primary values
+ bytesRead += BitPacking.unpackBits(b2, data, excDataOffset, excValues, 0, excCount);
+
+ // Update output values
+ for (int i = 0; i < excCount; i += 1) {
+ out[outOffset + excOffsets[i]] |= excValues[i] << b1;
+ }
+ }
+
+ // Add back the chunk minimum
+ for (int i = 0; i < count; i += 1) {
+ out[outOffset + i] += base;
+ }
+
+ return bytesRead;
+ }
+
+ private static int writeHeader(
+ ByteBuffer out, int outOffset, int b1, int b2, int excCount, int base) {
+ // Header: b1 in low nibble, b2 in high nibble, then e, then m
+ ByteBuffers.writeByte(out, (b2 << 4) | (b1 & 0b1111), outOffset);
+ ByteBuffers.writeByte(out, excCount, outOffset + 1);
+ ByteBuffers.writeByte(out, base, outOffset + 2);
+
+ return 3;
+ }
+
+ /**
+ * Choose the primary bit width {@code b1} that minimizes total encoded chunk size.
+ *
+ * <p>This produces the width that results in the smallest total size and the number of exceptions
Review Comment:
Yeah, both representations are tested in the case for 6, 34, 8, 7. The reason for this is that there's a tie in the final size. Both are valid, but the implementation chooses not to have exceptions to make decoding easier.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org
Re: [PR] Core: Add a read-only Mumbling bitmap implementation [iceberg]
Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #16747:
URL: https://github.com/apache/iceberg/pull/16747#issuecomment-5627459917
This pull request has been marked as stale due to 30 days of inactivity. It will be closed in 1 week if no further activity occurs. If you think that’s incorrect or this pull request requires a review, please simply write any comment. If closed, you can revive the PR at any time and @mention a reviewer or discuss it on the dev@iceberg.apache.org list. Thank you for your contributions.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@iceberg.apache.org
For additional commands, e-mail: issues-help@iceberg.apache.org