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/10/16 19:45:18 UTC

[PR] Core: Add mutable Mumbling bitmap implementation [iceberg]

rdblue opened a new pull request, #18544:
URL: https://github.com/apache/iceberg/pull/18544

   This adds a `MutableBitmap` interface to expose a `set` method for modifying a bitmap and a mutable implementation of Mumbling.
   
   The mutable bitmap implementation is based on a read-only bitmap. The mutable class keeps a map of "overlay" `Container` objects that track the contents of containers that have been modified, either as a sparse ordered list of local positions or as a dense 32-byte bitmap. When serializing the bitmap, unchanged regions are copied from the original base bitmap and overlay containers are written in between.
   
   This also uses and updates `ByteBuffers` methods. When using the unsigned little-endian methods, I found that they depend on the byte order of the buffer. This assumption works in the Variant package where these were first added, but not in general.
   
   Test plan:
   - Validates pass-through to original bitmap
   - Validate overlay works for set bits
       - set bits override overlay
       - set bits show up in isSet
       - setting bits in reverse order works if the byte representation is negative (i.e. 254)
   - Serialization
       - changing an existing container
       - adding containers past the original bitmap end
       - updating an empty bitmap
       - sparse containers
       - dense containers
   - Correct cardinality with all cases
   - Sparse overlay container
   - Dense overlay container
   - Conversion from sparse to dense
   - Empty mutable bitmap
   - Random test
   
   This also includes but does not run a size test similar to the original Rust implementation's that simulates binary pages of bitmaps to check compression and correctness.
   
   


-- 
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 mutable Mumbling bitmap implementation [iceberg]

Posted by "stevenzwu (via GitHub)" <gi...@apache.org>.
stevenzwu commented on code in PR #18544:
URL: https://github.com/apache/iceberg/pull/18544#discussion_r4353425026


##########
core/src/main/java/org/apache/iceberg/mumbling/MumblingBitmap.java:
##########
@@ -138,6 +160,282 @@ private int offset(int containerIndex) {
     return offsets[containerIndex];
   }
 
+  public MutableBitmap asMutable() {
+    return new Mutable(this);
+  }
+
+  /**
+   * A copy-on-write {@link MutableBitmap} implementation for Mumbling.
+   *
+   * <p>When a new bit position is set, an overlay is created for the position's container.
+   *
+   * <p>The initial buffer is not modified.
+   */
+  private static class Mutable implements MutableBitmap {
+    private final NavigableMap<Integer, Container> overlays = Maps.newTreeMap();
+    private final MumblingBitmap base;
+    private final int baseContainerCount;
+    private int cardinality = 0;
+
+    public Mutable(MumblingBitmap base) {
+      this.base = base;
+      this.baseContainerCount = base.descriptors().length;
+      this.cardinality = base.cardinality();
+    }
+
+    @Override
+    public int cardinality() {
+      return cardinality;
+    }
+
+    @Override
+    public boolean isSet(int pos) {
+      Container overlay = overlays.get(containerIndex(pos));
+      if (overlay != null) {
+        return overlay.isSet(posInContainer(pos));
+      }
+
+      return base.isSet(pos);
+    }
+
+    @Override
+    public boolean set(int pos) {
+      Preconditions.checkArgument(pos >= 0, "Cannot set invalid bit position: %s < 0", pos);
+      Preconditions.checkArgument(
+          pos < MAX_CARDINALITY, "Cannot set invalid bit position: %s (must be < 2,097,152)", pos);
+
+      int containerIndex = containerIndex(pos);
+      Container overlay = overlays.get(containerIndex);
+      if (overlay == null) {
+        if (containerIndex < baseContainerCount) {
+          overlay =
+              new Container(
+                  base.buffer(), base.offset(containerIndex), base.descriptor(containerIndex));
+        } else {
+          overlay = new Container();
+        }
+        overlays.put(containerIndex, overlay);
+      }
+
+      if (overlay.set(posInContainer(pos))) {
+        this.cardinality += 1;
+        return true;
+      }
+
+      return false;
+    }
+
+    @Override
+    public ByteBuffer buffer() {
+      int[] descriptorArray = descriptorArray();
+      int containersSize = sizeOfContainers(descriptorArray, 0, descriptorArray.length);
+      ByteBuffer descBuffer = PFOREncoding.encode(descriptorArray, descriptorArray.length);
+      int descriptorsSize = descBuffer.remaining();
+
+      ByteBuffer buffer = ByteBuffer.allocate(HEADER_SIZE + descriptorsSize + containersSize);
+      int currentPos = writeHeader(buffer, cardinality, descriptorArray.length);
+
+      buffer.put(HEADER_SIZE, descBuffer, descBuffer.position(), descriptorsSize);
+      currentPos += descriptorsSize;
+
+      int nextContainerIndex = 0;
+      for (Map.Entry<Integer, Container> entry : overlays.entrySet()) {
+        int containerIndex = entry.getKey();
+        currentPos +=
+            copyOriginalContainers(
+                descriptorArray, nextContainerIndex, containerIndex, buffer, currentPos);
+        currentPos += entry.getValue().writeTo(buffer, currentPos);
+        nextContainerIndex = containerIndex + 1;
+      }
+
+      copyOriginalContainers(
+          descriptorArray, nextContainerIndex, descriptorArray.length, buffer, currentPos);
+
+      return buffer;
+    }
+
+    private int[] descriptorArray() {
+      int[] baseDescriptors = base.descriptors();
+      int lastOverlayIndex = overlays.isEmpty() ? -1 : overlays.lastKey();
+      int numContainers = Math.max(lastOverlayIndex + 1, baseDescriptors.length);

Review Comment:
   I forgot overlays also contains updated containers.



-- 
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 mutable Mumbling bitmap implementation [iceberg]

Posted by "amogh-jahagirdar (via GitHub)" <gi...@apache.org>.
amogh-jahagirdar commented on code in PR #18544:
URL: https://github.com/apache/iceberg/pull/18544#discussion_r4303459251


##########
core/src/main/java/org/apache/iceberg/mumbling/MumblingBitmap.java:
##########
@@ -138,6 +160,282 @@ private int offset(int containerIndex) {
     return offsets[containerIndex];
   }
 
+  public MutableBitmap asMutable() {
+    return new Mutable(this);
+  }
+
+  /**
+   * A copy-on-write {@link MutableBitmap} implementation for Mumbling.
+   *
+   * <p>When a new bit position is set, an overlay is created for the position's container.
+   *
+   * <p>The initial buffer is not modified.
+   */
+  private static class Mutable implements MutableBitmap {
+    private final NavigableMap<Integer, Container> overlays = Maps.newTreeMap();
+    private final MumblingBitmap base;
+    private final int baseContainerCount;
+    private int cardinality = 0;
+
+    public Mutable(MumblingBitmap base) {
+      this.base = base;
+      this.baseContainerCount = base.descriptors().length;
+      this.cardinality = base.cardinality();
+    }
+
+    @Override
+    public int cardinality() {
+      return cardinality;
+    }
+
+    @Override
+    public boolean isSet(int pos) {
+      Container overlay = overlays.get(containerIndex(pos));
+      if (overlay != null) {
+        return overlay.isSet(posInContainer(pos));
+      }
+
+      return base.isSet(pos);
+    }
+
+    @Override
+    public boolean set(int pos) {
+      Preconditions.checkArgument(pos >= 0, "Cannot set invalid bit position: %s < 0", pos);
+      Preconditions.checkArgument(
+          pos < MAX_CARDINALITY, "Cannot set invalid bit position: %s (must be < 2,097,152)", pos);
+
+      int containerIndex = containerIndex(pos);
+      Container overlay = overlays.get(containerIndex);
+      if (overlay == null) {
+        if (containerIndex < baseContainerCount) {
+          overlay =
+              new Container(
+                  base.buffer(), base.offset(containerIndex), base.descriptor(containerIndex));
+        } else {
+          overlay = new Container();
+        }
+        overlays.put(containerIndex, overlay);
+      }
+
+      if (overlay.set(posInContainer(pos))) {
+        this.cardinality += 1;
+        return true;
+      }
+
+      return false;
+    }
+
+    @Override
+    public ByteBuffer buffer() {
+      int[] descriptorArray = descriptorArray();
+      int containersSize = sizeOfContainers(descriptorArray, 0, descriptorArray.length);
+      ByteBuffer descBuffer = PFOREncoding.encode(descriptorArray, descriptorArray.length);
+      int descriptorsSize = descBuffer.remaining();
+
+      ByteBuffer buffer = ByteBuffer.allocate(HEADER_SIZE + descriptorsSize + containersSize);
+      int currentPos = writeHeader(buffer, cardinality, descriptorArray.length);
+
+      buffer.put(HEADER_SIZE, descBuffer, descBuffer.position(), descriptorsSize);
+      currentPos += descriptorsSize;
+
+      int nextContainerIndex = 0;
+      for (Map.Entry<Integer, Container> entry : overlays.entrySet()) {
+        int containerIndex = entry.getKey();
+        currentPos +=
+            copyOriginalContainers(
+                descriptorArray, nextContainerIndex, containerIndex, buffer, currentPos);
+        currentPos += entry.getValue().writeTo(buffer, currentPos);
+        nextContainerIndex = containerIndex + 1;
+      }
+
+      copyOriginalContainers(
+          descriptorArray, nextContainerIndex, descriptorArray.length, buffer, currentPos);
+
+      return buffer;
+    }
+
+    private int[] descriptorArray() {
+      int[] baseDescriptors = base.descriptors();
+      int lastOverlayIndex = overlays.isEmpty() ? -1 : overlays.lastKey();
+      int numContainers = Math.max(lastOverlayIndex + 1, baseDescriptors.length);
+      int[] descriptors = new int[numContainers]; // filled with 0
+      System.arraycopy(baseDescriptors, 0, descriptors, 0, baseDescriptors.length);
+
+      for (Map.Entry<Integer, Container> entry : overlays.entrySet()) {
+        int containerIndex = entry.getKey();
+        int cardinality = entry.getValue().cardinality();
+        descriptors[containerIndex] = Math.min(cardinality, DENSE_CONTAINER_SIZE);
+      }
+
+      return descriptors;
+    }
+
+    private int sizeOfContainers(int[] descriptorArray, int startIndex, int endIndexExclusive) {
+      int size = 0;
+      for (int i = startIndex; i < endIndexExclusive; i += 1) {
+        size += descriptorArray[i];
+      }
+
+      return size;
+    }
+
+    private static int writeHeader(ByteBuffer buffer, int cardinality, int descriptorCount) {
+      ByteBuffers.writeByte(buffer, VERSION, 0);
+      ByteBuffers.writeLittleEndianUnsigned(buffer, cardinality, 1, 3);
+      ByteBuffers.writeLittleEndianUnsigned(buffer, descriptorCount, 4, 2);
+
+      return HEADER_SIZE;
+    }
+
+    private int copyOriginalContainers(
+        int[] descriptorArray,
+        int startIndex,
+        int endIndexExclusive,
+        ByteBuffer buffer,
+        int currentPos) {
+      if (startIndex < baseContainerCount && startIndex < endIndexExclusive) {
+        int offset = base.offset(startIndex);
+        int sizeToCopy = sizeOfContainers(descriptorArray, startIndex, endIndexExclusive);
+        if (sizeToCopy > 0) {
+          buffer.put(currentPos, base.buffer(), offset, sizeToCopy);
+        }
+
+        return sizeToCopy;
+      }
+
+      return 0;
+    }
+  }
+
+  private static class Container {
+    private byte[] dense = null;
+    private byte[] sparse = null;
+    private int cardinality = 0;
+
+    private Container() {
+      this.sparse = new byte[DENSE_CONTAINER_SIZE];
+    }
+
+    private Container(ByteBuffer buffer, int offset, int length) {
+      byte[] bytes = new byte[DENSE_CONTAINER_SIZE];
+      buffer.get(offset, bytes, 0, length);
+
+      if (isDense(length)) {

Review Comment:
   Minor: Should we just track if the container is dense or sparse from the descriptor rather than looking at the cardinality? Right now the read path uses the descriptor to decide, and this uses the cardinality, which is two separate sources of truth for the same thing.



-- 
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 mutable Mumbling bitmap implementation [iceberg]

Posted by "amogh-jahagirdar (via GitHub)" <gi...@apache.org>.
amogh-jahagirdar commented on PR #18544:
URL: https://github.com/apache/iceberg/pull/18544#issuecomment-6236579984

   Also linking this here since it came up above. With a builder we shouldn't need a public `MutableBitmap` interface. The builder can hold the mutable state and `build()` just returns a `ManifestBitmap`, so the mutable type stays internal to `org.apache.iceberg.mumbling`.
   
   https://github.com/apache/iceberg/pull/18544#pullrequestreview-5558751585


-- 
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 mutable Mumbling bitmap implementation [iceberg]

Posted by "amogh-jahagirdar (via GitHub)" <gi...@apache.org>.
amogh-jahagirdar commented on PR #18544:
URL: https://github.com/apache/iceberg/pull/18544#issuecomment-6386039117

   I will go ahead and merge, thanks @rdblue @stevenzwu 


-- 
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 mutable Mumbling bitmap implementation [iceberg]

Posted by "amogh-jahagirdar (via GitHub)" <gi...@apache.org>.
amogh-jahagirdar merged PR #18544:
URL: https://github.com/apache/iceberg/pull/18544


-- 
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 mutable Mumbling bitmap implementation [iceberg]

Posted by "rdblue (via GitHub)" <gi...@apache.org>.
rdblue commented on code in PR #18544:
URL: https://github.com/apache/iceberg/pull/18544#discussion_r4365109427


##########
core/src/test/java/org/apache/iceberg/mumbling/TestMumblingBitmap.java:
##########
@@ -290,4 +343,439 @@ void testBufferWithOffset() {
     assertThat(bitmap.isSet(42)).isTrue();
     assertThat(bitmap.isSet(43)).isFalse();
   }
+
+  @Test
+  public void testMutableValidatesPositions() {
+    MutableBitmap bitmap = MumblingBitmap.newMutableBitmap();
+
+    assertThat(bitmap.set(0)).isTrue();
+    assertThatThrownBy(() -> bitmap.set(-1))
+        .isInstanceOf(IllegalArgumentException.class)
+        .hasMessage("Cannot set invalid bit position: -1 < 0");
+
+    assertThat(bitmap.set(2_097_151)).isTrue();
+    assertThatThrownBy(() -> bitmap.set(2_097_152))
+        .isInstanceOf(IllegalArgumentException.class)
+        .hasMessage("Cannot set invalid bit position: 2097152 (must be < 2,097,152)");
+  }
+
+  @Test
+  public void testMutableOverlayPassthrough() {
+    MutableBitmap bitmap = MUTABLE_TEST_BASE.asMutable();
+
+    assertThat(bitmap.cardinality()).isEqualTo(34);
+
+    assertThat(bitmap.isSet(0)).isTrue();
+    assertThat(bitmap.isSet(1)).isFalse();
+
+    assertThat(bitmap.isSet(263)).isFalse();
+    assertThat(bitmap.isSet(289)).isFalse();
+    assertThat(bitmap.isSet(305)).isFalse();
+    assertThat(bitmap.isSet(321)).isFalse();
+    for (int i = 0; i < 8; i += 1) {
+      assertThat(bitmap.isSet(264 + i)).isTrue();
+      assertThat(bitmap.isSet(280 + i)).isTrue();
+      assertThat(bitmap.isSet(296 + i)).isTrue();
+      assertThat(bitmap.isSet(312 + i)).isTrue();
+    }
+    assertThat(bitmap.isSet(272)).isFalse();
+    assertThat(bitmap.isSet(288)).isFalse();
+    assertThat(bitmap.isSet(304)).isFalse();
+    assertThat(bitmap.isSet(320)).isFalse();
+
+    assertThat(bitmap.isSet(766)).isFalse();
+    assertThat(bitmap.isSet(767)).isTrue();
+    assertThat(bitmap.isSet(768)).isFalse();
+  }
+
+  @Test
+  public void testMutableOverlaySparseUpdate() {
+    MutableBitmap bitmap = MUTABLE_TEST_BASE.asMutable();
+
+    assertThat(bitmap.cardinality()).isEqualTo(34);
+
+    assertThat(bitmap.set(1)).isTrue();
+    assertThat(bitmap.set(0)).isFalse();
+    assertThat(bitmap.set(1)).isFalse();
+
+    assertThat(bitmap.cardinality()).isEqualTo(35);
+    assertThat(bitmap.isSet(0)).isTrue();
+    assertThat(bitmap.isSet(1)).isTrue();
+    assertThat(bitmap.isSet(2)).isFalse();
+
+    assertThat(bitmap.set(766)).isTrue();
+    assertThat(bitmap.set(767)).isFalse();
+    assertThat(bitmap.set(766)).isFalse();
+
+    assertThat(bitmap.cardinality()).isEqualTo(36);
+    assertThat(bitmap.isSet(765)).isFalse();
+    assertThat(bitmap.isSet(766)).isTrue();
+    assertThat(bitmap.isSet(767)).isTrue();
+    assertThat(bitmap.isSet(768)).isFalse();
+  }
+
+  @Test
+  public void testMutableOverlayDenseUpdate() {
+    MutableBitmap bitmap = MUTABLE_TEST_BASE.asMutable();
+
+    assertThat(bitmap.cardinality()).isEqualTo(34);
+
+    for (int i = 0; i < 8; i += 1) {
+      assertThat(bitmap.set(256 + i)).isTrue();
+      assertThat(bitmap.set(256 + i)).isFalse();
+      assertThat(bitmap.set(264 + i)).isFalse(); // already set
+    }
+
+    assertThat(bitmap.cardinality()).isEqualTo(42);
+
+    assertThat(bitmap.isSet(255)).isFalse();
+    for (int i = 0; i < 16; i += 1) {
+      assertThat(bitmap.isSet(256 + i)).isTrue();
+    }
+    assertThat(bitmap.isSet(272)).isFalse();
+
+    assertThat(bitmap.set(511)).isTrue();
+    assertThat(bitmap.set(511)).isFalse();
+    assertThat(bitmap.isSet(511)).isTrue();
+
+    assertThat(bitmap.cardinality()).isEqualTo(43);
+  }
+
+  @Test
+  public void testMutableOverlaySparseToDenseUpdate() {
+    MutableBitmap bitmap = MUTABLE_TEST_BASE.asMutable();
+
+    assertThat(bitmap.cardinality()).isEqualTo(34);
+
+    for (int i = 1; i < 33; i += 1) {
+      assertThat(bitmap.set(i)).isTrue();
+      assertThat(bitmap.set(i)).isFalse();
+    }
+
+    assertThat(bitmap.cardinality()).isEqualTo(66);
+
+    for (int i = 0; i < 33; i += 1) {
+      assertThat(bitmap.isSet(i)).isTrue();
+    }
+    assertThat(bitmap.isSet(33)).isFalse();
+
+    // set positions backward so the sparse list is rewritten
+    for (int i = 254; i > 222; i -= 1) {
+      assertThat(bitmap.set(i)).isTrue();
+      assertThat(bitmap.set(i)).isFalse();
+    }
+
+    assertThat(bitmap.cardinality()).isEqualTo(98);
+  }
+
+  @Test
+  public void testMutableOverlayNewContainer() {
+    MutableBitmap bitmap = MUTABLE_TEST_BASE.asMutable();
+
+    assertThat(bitmap.set(1024)).isTrue(); // container index 4, position 0
+    assertThat(bitmap.set(1024)).isFalse();
+    assertThat(bitmap.isSet(1024)).isTrue();
+    assertThat(bitmap.cardinality()).isEqualTo(35);
+  }
+
+  @Test
+  public void testMutableEmptySerialization() {
+    MutableBitmap empty = MumblingBitmap.newMutableBitmap();
+
+    assertThat(empty.cardinality()).isEqualTo(0);
+    assertThat(empty.buffer())
+        .isEqualTo(ByteBuffer.wrap(new byte[] {0x01, 0x00, 0x00, 0x00, 0x00, 0x00}));
+  }
+
+  @Test
+  public void testMutableNoopSerialization() {
+    MutableBitmap bitmap = MUTABLE_TEST_BASE.asMutable();
+
+    assertThat(bitmap.buffer())
+        .as("Does not reuse the original buffer")
+        .isNotSameAs(MUTABLE_TEST_BASE.buffer());
+    assertThat(bitmap.buffer()).isEqualTo(MUTABLE_TEST_BASE.buffer());
+  }
+
+  @Test
+  public void testMutableNewContainerSerialization() {
+    MutableBitmap bitmap = MUTABLE_TEST_BASE.asMutable();
+
+    assertThat(bitmap.set(1024)).isTrue(); // container 4, position 0
+    assertThat(bitmap.cardinality()).isEqualTo(35);
+    assertThat(bitmap.set(2048)).isTrue(); // container 8, position 0
+    assertThat(bitmap.cardinality()).isEqualTo(36);
+
+    MumblingBitmap result = new MumblingBitmap(bitmap.buffer());
+    assertThat(result.cardinality()).isEqualTo(36);
+    assertThat(result.descriptors()).containsExactly(1, 32, 1, 0, 1, 0, 0, 0, 1);
+
+    assertThat(result.isSet(0)).isTrue();
+
+    for (int i = 0; i < 8; i += 1) {
+      assertThat(result.isSet(264 + i)).isTrue();
+      assertThat(result.isSet(280 + i)).isTrue();
+      assertThat(result.isSet(296 + i)).isTrue();
+      assertThat(result.isSet(312 + i)).isTrue();
+    }
+
+    assertThat(result.isSet(767)).isTrue();
+
+    assertThat(result.isSet(1024)).isTrue();
+    assertThat(result.isSet(2048)).isTrue();
+  }
+
+  @Test
+  public void testMutableEmptyWithNewContainerSerialization() {
+    MutableBitmap bitmap = MumblingBitmap.newMutableBitmap();
+
+    assertThat(bitmap.set(1024)).isTrue(); // container 4, position 0
+    assertThat(bitmap.set(2048)).isTrue(); // container 8, position 0
+
+    assertThat(bitmap.cardinality()).isEqualTo(2);
+
+    MumblingBitmap result = new MumblingBitmap(bitmap.buffer());
+    assertThat(result.cardinality()).isEqualTo(2);
+    assertThat(result.descriptors()).contains(0, 0, 0, 0, 1, 0, 0, 0, 1);
+
+    assertThat(result.isSet(1024)).isTrue();
+    assertThat(result.isSet(2048)).isTrue();
+  }
+
+  @Test
+  public void testMutableSparseUpdateSerialization() {
+    MutableBitmap bitmap = MUTABLE_TEST_BASE.asMutable();
+
+    assertThat(bitmap.set(1)).isTrue();
+    assertThat(bitmap.set(766)).isTrue(); // container index 2, pos 254
+    assertThat(bitmap.cardinality()).isEqualTo(36);
+
+    ByteBuffer serialized = bitmap.buffer();
+    int[] expectedDescriptors = new int[] {2, 32, 2};
+
+    MumblingBitmap result = new MumblingBitmap(serialized);
+    assertThat(result.cardinality()).isEqualTo(36);
+    assertThat(result.descriptors()).isEqualTo(expectedDescriptors);
+
+    assertThat(bitmap.isSet(1)).isTrue();
+    assertThat(bitmap.isSet(766)).isTrue();
+
+    ByteBuffer descriptors = PFOREncoding.encode(expectedDescriptors, expectedDescriptors.length);
+    int descriptorSize = descriptors.remaining();
+    int containersOffset = HEADER_SIZE + descriptorSize;
+
+    assertThat(serialized.slice(6, descriptorSize)).isEqualTo(descriptors);
+
+    assertThat(serialized.slice(containersOffset, 2)).isEqualTo(sparse(0, 1).buffer());
+    assertThat(serialized.slice(containersOffset + 2, 32))
+        .isEqualTo(dense(DENSE_CONTAINER).buffer());
+    assertThat(serialized.slice(containersOffset + 34, 2)).isEqualTo(sparse(254, 255).buffer());
+  }
+
+  @Test
+  public void testMutableDenseUpdateSerialization() {
+    MutableBitmap bitmap = MUTABLE_TEST_BASE.asMutable();
+
+    for (int i = 0; i < 8; i += 1) {
+      assertThat(bitmap.set(256 + i)).isTrue();
+    }
+    assertThat(bitmap.set(511)).isTrue(); // last bit of the dense container
+
+    assertThat(bitmap.cardinality()).isEqualTo(43);
+
+    ByteBuffer serialized = bitmap.buffer();
+    int[] expectedDescriptors = new int[] {1, 32, 1};
+
+    MumblingBitmap result = new MumblingBitmap(serialized);
+    assertThat(result.cardinality()).isEqualTo(43);
+    assertThat(result.descriptors()).isEqualTo(expectedDescriptors);
+
+    ByteBuffer descriptors = PFOREncoding.encode(expectedDescriptors, expectedDescriptors.length);
+    int descriptorSize = descriptors.remaining();
+    int containersOffset = HEADER_SIZE + descriptorSize;
+
+    assertThat(serialized.slice(6, descriptorSize)).isEqualTo(descriptors);
+
+    assertThat(serialized.slice(containersOffset, 1)).isEqualTo(sparse(0).buffer());
+
+    byte[] denseBytes = Arrays.copyOf(DENSE_CONTAINER, 32);
+    denseBytes[0] = (byte) 0xFF;
+    denseBytes[31] = (byte) 0x01; // last bit
+    assertThat(serialized.slice(containersOffset + 1, 32)).isEqualTo(dense(denseBytes).buffer());
+
+    assertThat(serialized.slice(containersOffset + 33, 1)).isEqualTo(sparse(255).buffer());
+  }
+
+  @Test
+  public void testMutableSparseToDenseUpdateSerialization() {
+    MutableBitmap bitmap = MUTABLE_TEST_BASE.asMutable();
+
+    for (int i = 766; i > 735; i -= 1) {
+      assertThat(bitmap.set(i)).isTrue();
+    }
+    assertThat(bitmap.cardinality()).isEqualTo(65);
+
+    ByteBuffer serialized = bitmap.buffer();
+    int[] expectedDescriptors = new int[] {1, 32, 32};
+
+    MumblingBitmap result = new MumblingBitmap(serialized);
+    assertThat(result.cardinality()).isEqualTo(65);
+    assertThat(result.descriptors()).isEqualTo(expectedDescriptors);
+
+    assertThat(result.isSet(0)).isTrue();
+
+    for (int i = 0; i < 8; i += 1) {
+      assertThat(result.isSet(264 + i)).isTrue();
+      assertThat(result.isSet(280 + i)).isTrue();
+      assertThat(result.isSet(296 + i)).isTrue();
+      assertThat(result.isSet(312 + i)).isTrue();
+    }
+
+    for (int i = 736; i < 767; i += 1) {
+      assertThat(bitmap.isSet(i)).isTrue();
+    }
+
+    assertThat(result.isSet(767)).isTrue();
+
+    ByteBuffer descriptors = PFOREncoding.encode(expectedDescriptors, expectedDescriptors.length);
+    int descriptorSize = descriptors.remaining();
+    int containersOffset = HEADER_SIZE + descriptorSize;
+
+    assertThat(serialized.slice(6, descriptorSize)).isEqualTo(descriptors);
+
+    assertThat(serialized.slice(containersOffset, 1)).isEqualTo(sparse(0).buffer());
+    assertThat(serialized.slice(containersOffset + 1, 32))
+        .isEqualTo(dense(DENSE_CONTAINER).buffer());
+
+    byte[] denseBytes = new byte[32];
+    denseBytes[28] = (byte) 0xFF;
+    denseBytes[29] = (byte) 0xFF;
+    denseBytes[30] = (byte) 0xFF;
+    denseBytes[31] = (byte) 0xFF;
+    assertThat(serialized.slice(containersOffset + 33, 32)).isEqualTo(dense(denseBytes).buffer());
+  }
+
+  @Test
+  public void testMutableRandomPositions() {
+    Random positions = new Random(39826538713L);
+    int count = 0;
+
+    MutableBitmap bitmap = MumblingBitmap.newMutableBitmap();
+
+    for (int i = 0; i < 50_000; i += 1) {
+      if (bitmap.set(positions.nextInt(64_000))) {
+        count += 1;
+      }
+    }
+
+    MumblingBitmap result = new MumblingBitmap(bitmap.buffer());
+
+    assertThat(bitmap.cardinality()).isEqualTo(count);
+    assertThat(result.cardinality()).isEqualTo(count);
+
+    // check that all positions are set
+    Random validation = new Random(39826538713L);
+    for (int i = 0; i < 50_000; i += 1) {
+      int pos = validation.nextInt(64_000);
+      assertThat(bitmap.isSet(pos)).isTrue();
+      assertThat(result.isSet(pos)).isTrue();
+    }
+  }
+
+  @Test
+  public void testRelocatedBuffer() {
+    MumblingBitmap bitmap = new MumblingBitmap(relocate(MUTABLE_TEST_BASE.buffer()));
+
+    assertThat(bitmap.cardinality()).isEqualTo(34);
+    assertThat(bitmap.descriptors()).containsExactly(1, 32, 1);
+
+    assertThat(bitmap.isSet(0)).isTrue();
+    assertThat(bitmap.isSet(1)).isFalse();
+
+    assertThat(bitmap.isSet(263)).isFalse();
+    for (int i = 0; i < 8; i += 1) {
+      assertThat(bitmap.isSet(264 + i)).isTrue();
+      assertThat(bitmap.isSet(280 + i)).isTrue();
+      assertThat(bitmap.isSet(296 + i)).isTrue();
+      assertThat(bitmap.isSet(312 + i)).isTrue();
+    }
+    assertThat(bitmap.isSet(272)).isFalse();
+    assertThat(bitmap.isSet(320)).isFalse();
+
+    assertThat(bitmap.isSet(766)).isFalse();
+    assertThat(bitmap.isSet(767)).isTrue();
+    assertThat(bitmap.isSet(768)).isFalse();
+  }
+
+  @Test
+  public void testRelocatedBufferUpdateSerialization() {
+    MutableBitmap bitmap = new MumblingBitmap(relocate(MUTABLE_TEST_BASE.buffer())).asMutable();

Review Comment:
   That is what `testRelocatedBuffer()` tests. That test validates checking bits in a bitmap read from the middle of a buffer. This one builds on that by testing the regions that are copied.



-- 
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 mutable Mumbling bitmap implementation [iceberg]

Posted by "stevenzwu (via GitHub)" <gi...@apache.org>.
stevenzwu commented on code in PR #18544:
URL: https://github.com/apache/iceberg/pull/18544#discussion_r4299216621


##########
core/src/main/java/org/apache/iceberg/mumbling/MumblingBitmap.java:
##########
@@ -19,8 +19,13 @@
 package org.apache.iceberg.mumbling;
 
 import java.nio.ByteBuffer;
+import java.util.Map;
+import java.util.NavigableMap;
+import org.apache.curator.shaded.com.google.common.collect.Maps;

Review Comment:
   Import `org.apache.iceberg.relocated.com.google.common.collect.Maps` instead of the Curator-shaded class.



##########
core/src/main/java/org/apache/iceberg/mumbling/MumblingBitmap.java:
##########


Review Comment:
   nit: these two lines can use the small helper methods.



##########
core/src/main/java/org/apache/iceberg/mumbling/MumblingBitmap.java:
##########
@@ -138,6 +160,282 @@ private int offset(int containerIndex) {
     return offsets[containerIndex];
   }
 
+  public MutableBitmap asMutable() {
+    return new Mutable(this);
+  }
+
+  /**
+   * A copy-on-write {@link MutableBitmap} implementation for Mumbling.
+   *
+   * <p>When a new bit position is set, an overlay is created for the position's container.
+   *
+   * <p>The initial buffer is not modified.
+   */
+  private static class Mutable implements MutableBitmap {
+    private final NavigableMap<Integer, Container> overlays = Maps.newTreeMap();
+    private final MumblingBitmap base;
+    private final int baseContainerCount;
+    private int cardinality = 0;
+
+    public Mutable(MumblingBitmap base) {
+      this.base = base;
+      this.baseContainerCount = base.descriptors().length;
+      this.cardinality = base.cardinality();
+    }
+
+    @Override
+    public int cardinality() {
+      return cardinality;
+    }
+
+    @Override
+    public boolean isSet(int pos) {
+      Container overlay = overlays.get(containerIndex(pos));
+      if (overlay != null) {
+        return overlay.isSet(posInContainer(pos));
+      }
+
+      return base.isSet(pos);
+    }
+
+    @Override
+    public boolean set(int pos) {
+      Preconditions.checkArgument(pos >= 0, "Cannot set invalid bit position: %s < 0", pos);
+      Preconditions.checkArgument(
+          pos < MAX_CARDINALITY, "Cannot set invalid bit position: %s (must be < 2,097,152)", pos);
+
+      int containerIndex = containerIndex(pos);
+      Container overlay = overlays.get(containerIndex);
+      if (overlay == null) {
+        if (containerIndex < baseContainerCount) {
+          overlay =
+              new Container(
+                  base.buffer(), base.offset(containerIndex), base.descriptor(containerIndex));
+        } else {
+          overlay = new Container();
+        }
+        overlays.put(containerIndex, overlay);
+      }
+
+      if (overlay.set(posInContainer(pos))) {
+        this.cardinality += 1;
+        return true;
+      }
+
+      return false;
+    }
+
+    @Override
+    public ByteBuffer buffer() {
+      int[] descriptorArray = descriptorArray();
+      int containersSize = sizeOfContainers(descriptorArray, 0, descriptorArray.length);
+      ByteBuffer descBuffer = PFOREncoding.encode(descriptorArray, descriptorArray.length);
+      int descriptorsSize = descBuffer.remaining();
+
+      ByteBuffer buffer = ByteBuffer.allocate(HEADER_SIZE + descriptorsSize + containersSize);
+      int currentPos = writeHeader(buffer, cardinality, descriptorArray.length);
+
+      buffer.put(HEADER_SIZE, descBuffer, descBuffer.position(), descriptorsSize);
+      currentPos += descriptorsSize;
+
+      int nextContainerIndex = 0;
+      for (Map.Entry<Integer, Container> entry : overlays.entrySet()) {
+        int containerIndex = entry.getKey();
+        currentPos +=
+            copyOriginalContainers(
+                descriptorArray, nextContainerIndex, containerIndex, buffer, currentPos);
+        currentPos += entry.getValue().writeTo(buffer, currentPos);
+        nextContainerIndex = containerIndex + 1;
+      }
+
+      copyOriginalContainers(
+          descriptorArray, nextContainerIndex, descriptorArray.length, buffer, currentPos);
+
+      return buffer;
+    }
+
+    private int[] descriptorArray() {
+      int[] baseDescriptors = base.descriptors();
+      int lastOverlayIndex = overlays.isEmpty() ? -1 : overlays.lastKey();
+      int numContainers = Math.max(lastOverlayIndex + 1, baseDescriptors.length);
+      int[] descriptors = new int[numContainers]; // filled with 0
+      System.arraycopy(baseDescriptors, 0, descriptors, 0, baseDescriptors.length);
+
+      for (Map.Entry<Integer, Container> entry : overlays.entrySet()) {
+        int containerIndex = entry.getKey();
+        int cardinality = entry.getValue().cardinality();
+        descriptors[containerIndex] = Math.min(cardinality, DENSE_CONTAINER_SIZE);
+      }
+
+      return descriptors;
+    }
+
+    private int sizeOfContainers(int[] descriptorArray, int startIndex, int endIndexExclusive) {
+      int size = 0;
+      for (int i = startIndex; i < endIndexExclusive; i += 1) {
+        size += descriptorArray[i];
+      }
+
+      return size;
+    }
+
+    private static int writeHeader(ByteBuffer buffer, int cardinality, int descriptorCount) {
+      ByteBuffers.writeByte(buffer, VERSION, 0);
+      ByteBuffers.writeLittleEndianUnsigned(buffer, cardinality, 1, 3);
+      ByteBuffers.writeLittleEndianUnsigned(buffer, descriptorCount, 4, 2);
+
+      return HEADER_SIZE;
+    }
+
+    private int copyOriginalContainers(
+        int[] descriptorArray,
+        int startIndex,
+        int endIndexExclusive,
+        ByteBuffer buffer,
+        int currentPos) {
+      if (startIndex < baseContainerCount && startIndex < endIndexExclusive) {
+        int offset = base.offset(startIndex);
+        int sizeToCopy = sizeOfContainers(descriptorArray, startIndex, endIndexExclusive);
+        if (sizeToCopy > 0) {
+          buffer.put(currentPos, base.buffer(), offset, sizeToCopy);
+        }
+
+        return sizeToCopy;
+      }
+
+      return 0;
+    }
+  }
+
+  private static class Container {
+    private byte[] dense = null;
+    private byte[] sparse = null;
+    private int cardinality = 0;
+
+    private Container() {
+      this.sparse = new byte[DENSE_CONTAINER_SIZE];
+    }
+
+    private Container(ByteBuffer buffer, int offset, int length) {
+      byte[] bytes = new byte[DENSE_CONTAINER_SIZE];
+      buffer.get(offset, bytes, 0, length);
+
+      if (isDense(length)) {
+        this.dense = bytes;
+        this.cardinality = denseCardinality(dense);
+      } else {
+        this.sparse = bytes;
+        this.cardinality = length;
+      }
+    }
+
+    int cardinality() {
+      return cardinality;
+    }
+
+    private boolean isSet(int posInContainer) {
+      if (cardinality < 32) {
+        // sparse
+        for (int i = 0; i < cardinality; i += 1) {
+          if ((sparse[i] & 0xFF) == posInContainer) {
+            return true;
+          }
+        }
+
+        return false;
+      } else {
+        // dense
+        int bitShift = denseBitShift(posInContainer);
+        return ((dense[denseByteIndex(posInContainer)] >>> bitShift) & 0b1) == 0b1;
+      }
+    }
+
+    private boolean set(int posInContainer) {
+      if (setInternal(posInContainer)) {
+        this.cardinality += 1;
+        return true;
+      }
+
+      return false;
+    }
+
+    int writeTo(ByteBuffer buffer, int offset) {
+      if (cardinality < DENSE_CONTAINER_SIZE) {
+        buffer.put(offset, sparse, 0, cardinality);
+        return cardinality;
+      } else {
+        buffer.put(offset, dense, 0, dense.length);
+        return dense.length;
+      }
+    }
+
+    private boolean setInternal(int posInContainer) {
+      if (cardinality < 31) {
+        return sparseSet(sparse, cardinality, posInContainer);
+      } else if (cardinality > 31) {
+        return denseSet(dense, posInContainer);
+      } else {
+        // convert to dense, reuse converted buffer if it is present
+        if (dense == null) {
+          this.dense = convertToDense(sparse, cardinality);
+        }
+
+        if (denseSet(dense, posInContainer)) {
+          this.sparse = null;
+          return true;
+        }
+
+        // leave the converted dense array for next set attempt
+        return false;
+      }
+    }
+
+    private static boolean sparseSet(byte[] bytes, int length, int posInContainer) {
+      byte nextInsert = (byte) posInContainer;
+      for (int i = 0; i < length; i += 1) {
+        if (nextInsert == bytes[i]) {
+          return false; // already set
+        } else if ((nextInsert & 0xFF) < (bytes[i] & 0xFF)) {
+          byte replaced = bytes[i];
+          bytes[i] = nextInsert;
+          nextInsert = replaced;
+        }
+      }
+
+      bytes[length] = nextInsert;
+      return true;
+    }
+
+    private static byte[] convertToDense(byte[] sparse, int cardinality) {
+      byte[] dense = new byte[32];
+      for (int i = 0; i < cardinality; i += 1) {
+        denseSet(dense, (sparse[i] & 0xFF));
+      }
+
+      return dense;
+    }
+
+    private static boolean denseSet(byte[] bytes, int posInContainer) {
+      int byteIndex = denseByteIndex(posInContainer);
+      byte bit = (byte) (0b1 << denseBitShift(posInContainer));
+      if ((bytes[byteIndex] & bit) != bit) {
+        bytes[byteIndex] |= bit;
+        return true;
+      }
+
+      return false;
+    }
+
+    private static int denseCardinality(byte[] bytes) {
+      int cardinality = 0;
+      for (int i = 0; i < bytes.length; i += 1) {
+        cardinality += Integer.bitCount(bytes[i]);

Review Comment:
   `Integer.bitCount` takes an `int`, and the `byte` is sign-extended first. A byte `>= 0x80` gains 24 extra one-bits. `0xFF` widens to `0xFFFFFFFF` and counts as 32 instead of 8. We should mask before counting:
   
   ```java
   cardinality += Integer.bitCount(bytes[i] & 0xFF);
   ```
   
   `DENSE_CONTAINER` sets bytes 1, 3, 5, and 7 to `0xFF`, so this container has 32 bits set. This method returns 4 × 32 = 128.
   
   The round-trip tests still pass because 128 is above 32. In `descriptorArray()`, `Math.min(cardinality, DENSE_CONTAINER_SIZE)` still writes descriptor 32, and the `>= 32` branches still read and write the dense bytes. `testMutableOverlayDenseUpdate` and `testMutableDenseUpdateSerialization` check the bitmap's own cardinality counter, the descriptor, and those bytes. They never check this bitcount.
   
   
   
   



##########
core/src/main/java/org/apache/iceberg/mumbling/MumblingBitmap.java:
##########
@@ -138,6 +160,282 @@ private int offset(int containerIndex) {
     return offsets[containerIndex];
   }
 
+  public MutableBitmap asMutable() {
+    return new Mutable(this);
+  }
+
+  /**
+   * A copy-on-write {@link MutableBitmap} implementation for Mumbling.
+   *
+   * <p>When a new bit position is set, an overlay is created for the position's container.
+   *
+   * <p>The initial buffer is not modified.
+   */
+  private static class Mutable implements MutableBitmap {
+    private final NavigableMap<Integer, Container> overlays = Maps.newTreeMap();
+    private final MumblingBitmap base;
+    private final int baseContainerCount;
+    private int cardinality = 0;
+
+    public Mutable(MumblingBitmap base) {
+      this.base = base;
+      this.baseContainerCount = base.descriptors().length;
+      this.cardinality = base.cardinality();
+    }
+
+    @Override
+    public int cardinality() {
+      return cardinality;
+    }
+
+    @Override
+    public boolean isSet(int pos) {
+      Container overlay = overlays.get(containerIndex(pos));
+      if (overlay != null) {
+        return overlay.isSet(posInContainer(pos));
+      }
+
+      return base.isSet(pos);
+    }
+
+    @Override
+    public boolean set(int pos) {
+      Preconditions.checkArgument(pos >= 0, "Cannot set invalid bit position: %s < 0", pos);
+      Preconditions.checkArgument(
+          pos < MAX_CARDINALITY, "Cannot set invalid bit position: %s (must be < 2,097,152)", pos);
+
+      int containerIndex = containerIndex(pos);
+      Container overlay = overlays.get(containerIndex);
+      if (overlay == null) {
+        if (containerIndex < baseContainerCount) {
+          overlay =
+              new Container(
+                  base.buffer(), base.offset(containerIndex), base.descriptor(containerIndex));
+        } else {
+          overlay = new Container();
+        }
+        overlays.put(containerIndex, overlay);
+      }
+
+      if (overlay.set(posInContainer(pos))) {
+        this.cardinality += 1;
+        return true;
+      }
+
+      return false;
+    }
+
+    @Override
+    public ByteBuffer buffer() {
+      int[] descriptorArray = descriptorArray();
+      int containersSize = sizeOfContainers(descriptorArray, 0, descriptorArray.length);
+      ByteBuffer descBuffer = PFOREncoding.encode(descriptorArray, descriptorArray.length);
+      int descriptorsSize = descBuffer.remaining();
+
+      ByteBuffer buffer = ByteBuffer.allocate(HEADER_SIZE + descriptorsSize + containersSize);
+      int currentPos = writeHeader(buffer, cardinality, descriptorArray.length);
+
+      buffer.put(HEADER_SIZE, descBuffer, descBuffer.position(), descriptorsSize);
+      currentPos += descriptorsSize;
+
+      int nextContainerIndex = 0;
+      for (Map.Entry<Integer, Container> entry : overlays.entrySet()) {
+        int containerIndex = entry.getKey();
+        currentPos +=
+            copyOriginalContainers(
+                descriptorArray, nextContainerIndex, containerIndex, buffer, currentPos);
+        currentPos += entry.getValue().writeTo(buffer, currentPos);
+        nextContainerIndex = containerIndex + 1;
+      }
+
+      copyOriginalContainers(
+          descriptorArray, nextContainerIndex, descriptorArray.length, buffer, currentPos);
+
+      return buffer;
+    }
+
+    private int[] descriptorArray() {
+      int[] baseDescriptors = base.descriptors();
+      int lastOverlayIndex = overlays.isEmpty() ? -1 : overlays.lastKey();
+      int numContainers = Math.max(lastOverlayIndex + 1, baseDescriptors.length);

Review Comment:
   do we need to validate firstOverlayIndex equals to baseDescriptors.length?



##########
core/src/main/java/org/apache/iceberg/mumbling/MumblingBitmap.java:
##########
@@ -138,6 +160,282 @@ private int offset(int containerIndex) {
     return offsets[containerIndex];
   }
 
+  public MutableBitmap asMutable() {
+    return new Mutable(this);
+  }
+
+  /**
+   * A copy-on-write {@link MutableBitmap} implementation for Mumbling.
+   *
+   * <p>When a new bit position is set, an overlay is created for the position's container.
+   *
+   * <p>The initial buffer is not modified.
+   */
+  private static class Mutable implements MutableBitmap {
+    private final NavigableMap<Integer, Container> overlays = Maps.newTreeMap();
+    private final MumblingBitmap base;
+    private final int baseContainerCount;
+    private int cardinality = 0;
+
+    public Mutable(MumblingBitmap base) {
+      this.base = base;
+      this.baseContainerCount = base.descriptors().length;
+      this.cardinality = base.cardinality();
+    }
+
+    @Override
+    public int cardinality() {
+      return cardinality;
+    }
+
+    @Override
+    public boolean isSet(int pos) {
+      Container overlay = overlays.get(containerIndex(pos));
+      if (overlay != null) {
+        return overlay.isSet(posInContainer(pos));
+      }
+
+      return base.isSet(pos);
+    }
+
+    @Override
+    public boolean set(int pos) {
+      Preconditions.checkArgument(pos >= 0, "Cannot set invalid bit position: %s < 0", pos);
+      Preconditions.checkArgument(
+          pos < MAX_CARDINALITY, "Cannot set invalid bit position: %s (must be < 2,097,152)", pos);
+
+      int containerIndex = containerIndex(pos);
+      Container overlay = overlays.get(containerIndex);
+      if (overlay == null) {
+        if (containerIndex < baseContainerCount) {
+          overlay =
+              new Container(
+                  base.buffer(), base.offset(containerIndex), base.descriptor(containerIndex));
+        } else {
+          overlay = new Container();
+        }
+        overlays.put(containerIndex, overlay);
+      }
+
+      if (overlay.set(posInContainer(pos))) {
+        this.cardinality += 1;
+        return true;
+      }
+
+      return false;
+    }
+
+    @Override
+    public ByteBuffer buffer() {
+      int[] descriptorArray = descriptorArray();
+      int containersSize = sizeOfContainers(descriptorArray, 0, descriptorArray.length);
+      ByteBuffer descBuffer = PFOREncoding.encode(descriptorArray, descriptorArray.length);
+      int descriptorsSize = descBuffer.remaining();
+
+      ByteBuffer buffer = ByteBuffer.allocate(HEADER_SIZE + descriptorsSize + containersSize);
+      int currentPos = writeHeader(buffer, cardinality, descriptorArray.length);
+
+      buffer.put(HEADER_SIZE, descBuffer, descBuffer.position(), descriptorsSize);
+      currentPos += descriptorsSize;
+
+      int nextContainerIndex = 0;
+      for (Map.Entry<Integer, Container> entry : overlays.entrySet()) {
+        int containerIndex = entry.getKey();
+        currentPos +=
+            copyOriginalContainers(
+                descriptorArray, nextContainerIndex, containerIndex, buffer, currentPos);
+        currentPos += entry.getValue().writeTo(buffer, currentPos);
+        nextContainerIndex = containerIndex + 1;
+      }
+
+      copyOriginalContainers(
+          descriptorArray, nextContainerIndex, descriptorArray.length, buffer, currentPos);
+
+      return buffer;
+    }
+
+    private int[] descriptorArray() {
+      int[] baseDescriptors = base.descriptors();
+      int lastOverlayIndex = overlays.isEmpty() ? -1 : overlays.lastKey();
+      int numContainers = Math.max(lastOverlayIndex + 1, baseDescriptors.length);
+      int[] descriptors = new int[numContainers]; // filled with 0
+      System.arraycopy(baseDescriptors, 0, descriptors, 0, baseDescriptors.length);
+
+      for (Map.Entry<Integer, Container> entry : overlays.entrySet()) {
+        int containerIndex = entry.getKey();
+        int cardinality = entry.getValue().cardinality();
+        descriptors[containerIndex] = Math.min(cardinality, DENSE_CONTAINER_SIZE);
+      }
+
+      return descriptors;
+    }
+
+    private int sizeOfContainers(int[] descriptorArray, int startIndex, int endIndexExclusive) {
+      int size = 0;
+      for (int i = startIndex; i < endIndexExclusive; i += 1) {
+        size += descriptorArray[i];
+      }
+
+      return size;
+    }
+
+    private static int writeHeader(ByteBuffer buffer, int cardinality, int descriptorCount) {
+      ByteBuffers.writeByte(buffer, VERSION, 0);
+      ByteBuffers.writeLittleEndianUnsigned(buffer, cardinality, 1, 3);
+      ByteBuffers.writeLittleEndianUnsigned(buffer, descriptorCount, 4, 2);
+
+      return HEADER_SIZE;
+    }
+
+    private int copyOriginalContainers(
+        int[] descriptorArray,
+        int startIndex,
+        int endIndexExclusive,
+        ByteBuffer buffer,
+        int currentPos) {
+      if (startIndex < baseContainerCount && startIndex < endIndexExclusive) {
+        int offset = base.offset(startIndex);
+        int sizeToCopy = sizeOfContainers(descriptorArray, startIndex, endIndexExclusive);
+        if (sizeToCopy > 0) {
+          buffer.put(currentPos, base.buffer(), offset, sizeToCopy);
+        }
+
+        return sizeToCopy;
+      }
+
+      return 0;
+    }
+  }
+
+  private static class Container {
+    private byte[] dense = null;
+    private byte[] sparse = null;
+    private int cardinality = 0;
+
+    private Container() {
+      this.sparse = new byte[DENSE_CONTAINER_SIZE];
+    }
+
+    private Container(ByteBuffer buffer, int offset, int length) {
+      byte[] bytes = new byte[DENSE_CONTAINER_SIZE];
+      buffer.get(offset, bytes, 0, length);
+
+      if (isDense(length)) {
+        this.dense = bytes;
+        this.cardinality = denseCardinality(dense);
+      } else {
+        this.sparse = bytes;
+        this.cardinality = length;
+      }
+    }
+
+    int cardinality() {
+      return cardinality;
+    }
+
+    private boolean isSet(int posInContainer) {
+      if (cardinality < 32) {
+        // sparse
+        for (int i = 0; i < cardinality; i += 1) {
+          if ((sparse[i] & 0xFF) == posInContainer) {
+            return true;
+          }
+        }
+
+        return false;
+      } else {
+        // dense
+        int bitShift = denseBitShift(posInContainer);
+        return ((dense[denseByteIndex(posInContainer)] >>> bitShift) & 0b1) == 0b1;
+      }
+    }
+
+    private boolean set(int posInContainer) {
+      if (setInternal(posInContainer)) {
+        this.cardinality += 1;
+        return true;
+      }
+
+      return false;
+    }
+
+    int writeTo(ByteBuffer buffer, int offset) {
+      if (cardinality < DENSE_CONTAINER_SIZE) {
+        buffer.put(offset, sparse, 0, cardinality);
+        return cardinality;
+      } else {
+        buffer.put(offset, dense, 0, dense.length);
+        return dense.length;
+      }
+    }
+
+    private boolean setInternal(int posInContainer) {
+      if (cardinality < 31) {

Review Comment:
   the magic number 31 is a bit difficult to get. should we use `DENSE_CONTAINER_SIZE`. like
   
   ```
   if (cardinality < DENSE_CONTAINER_SIZE - 1) {
     // sparse container still have room to grow
     return sparseSet(sparse, cardinality, posInContainer);
   } else if (cardinality >= DENSE_CONTAINER_SIZE) {
     // already a dense container
     return denseSet(dense, posInContainer);
   } else {
     // cardinality == 31: convert to dense, reuse converted buffer if it is present
   }
   ```



##########
core/src/main/java/org/apache/iceberg/mumbling/MumblingBitmap.java:
##########
@@ -51,23 +64,23 @@ class MumblingBitmap implements ManifestBitmap {
   private volatile int[] offsets = null;
 
   MumblingBitmap(ByteBuffer data) {
-    int version = data.get(data.position()) & 0xFF;
+    int version = ByteBuffers.readByte(data, 0);
     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);
+    this.cardinality = ByteBuffers.readLittleEndianUnsigned(data, 1, 3);
+    this.containerCount = ByteBuffers.readLittleEndianUnsigned(data, 4, 2);
 
     Preconditions.checkState(
-        containerCount <= 8192, "Invalid container count: %s > 8,192 (max)", containerCount);
+        containerCount < MAX_CONTAINER_COUNT,

Review Comment:
   This PR changes the existing `<=` checks to `<`. Container count 8,192 and cardinality 2,097,152 are valid. Keep `<=`.



##########
core/src/main/java/org/apache/iceberg/mumbling/MutableBitmap.java:
##########
@@ -0,0 +1,26 @@
+/*
+ * 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 org.apache.iceberg.ManifestBitmap;
+
+/** Mutation methods for ManifestBitmap. */
+public interface MutableBitmap extends ManifestBitmap {

Review Comment:
   I found the naming a bit off. `ManifestBitmap` is a very specific bitmap for manifest DV. The `MutableBitmap` sounds like a generic bitmap interface. How about `MutableManifestBitmap`?



##########
core/src/main/java/org/apache/iceberg/mumbling/MumblingBitmap.java:
##########
@@ -138,6 +160,282 @@ private int offset(int containerIndex) {
     return offsets[containerIndex];
   }
 
+  public MutableBitmap asMutable() {
+    return new Mutable(this);
+  }
+
+  /**
+   * A copy-on-write {@link MutableBitmap} implementation for Mumbling.
+   *
+   * <p>When a new bit position is set, an overlay is created for the position's container.
+   *
+   * <p>The initial buffer is not modified.
+   */
+  private static class Mutable implements MutableBitmap {
+    private final NavigableMap<Integer, Container> overlays = Maps.newTreeMap();
+    private final MumblingBitmap base;
+    private final int baseContainerCount;
+    private int cardinality = 0;
+
+    public Mutable(MumblingBitmap base) {
+      this.base = base;
+      this.baseContainerCount = base.descriptors().length;
+      this.cardinality = base.cardinality();
+    }
+
+    @Override
+    public int cardinality() {
+      return cardinality;
+    }
+
+    @Override
+    public boolean isSet(int pos) {
+      Container overlay = overlays.get(containerIndex(pos));
+      if (overlay != null) {
+        return overlay.isSet(posInContainer(pos));
+      }
+
+      return base.isSet(pos);
+    }
+
+    @Override
+    public boolean set(int pos) {
+      Preconditions.checkArgument(pos >= 0, "Cannot set invalid bit position: %s < 0", pos);
+      Preconditions.checkArgument(
+          pos < MAX_CARDINALITY, "Cannot set invalid bit position: %s (must be < 2,097,152)", pos);
+
+      int containerIndex = containerIndex(pos);
+      Container overlay = overlays.get(containerIndex);
+      if (overlay == null) {
+        if (containerIndex < baseContainerCount) {
+          overlay =
+              new Container(
+                  base.buffer(), base.offset(containerIndex), base.descriptor(containerIndex));
+        } else {
+          overlay = new Container();
+        }
+        overlays.put(containerIndex, overlay);
+      }
+
+      if (overlay.set(posInContainer(pos))) {
+        this.cardinality += 1;
+        return true;
+      }
+
+      return false;
+    }
+
+    @Override
+    public ByteBuffer buffer() {
+      int[] descriptorArray = descriptorArray();
+      int containersSize = sizeOfContainers(descriptorArray, 0, descriptorArray.length);
+      ByteBuffer descBuffer = PFOREncoding.encode(descriptorArray, descriptorArray.length);
+      int descriptorsSize = descBuffer.remaining();
+
+      ByteBuffer buffer = ByteBuffer.allocate(HEADER_SIZE + descriptorsSize + containersSize);
+      int currentPos = writeHeader(buffer, cardinality, descriptorArray.length);
+
+      buffer.put(HEADER_SIZE, descBuffer, descBuffer.position(), descriptorsSize);
+      currentPos += descriptorsSize;
+
+      int nextContainerIndex = 0;
+      for (Map.Entry<Integer, Container> entry : overlays.entrySet()) {
+        int containerIndex = entry.getKey();
+        currentPos +=
+            copyOriginalContainers(
+                descriptorArray, nextContainerIndex, containerIndex, buffer, currentPos);
+        currentPos += entry.getValue().writeTo(buffer, currentPos);
+        nextContainerIndex = containerIndex + 1;
+      }
+
+      copyOriginalContainers(
+          descriptorArray, nextContainerIndex, descriptorArray.length, buffer, currentPos);
+
+      return buffer;
+    }
+
+    private int[] descriptorArray() {
+      int[] baseDescriptors = base.descriptors();
+      int lastOverlayIndex = overlays.isEmpty() ? -1 : overlays.lastKey();
+      int numContainers = Math.max(lastOverlayIndex + 1, baseDescriptors.length);
+      int[] descriptors = new int[numContainers]; // filled with 0
+      System.arraycopy(baseDescriptors, 0, descriptors, 0, baseDescriptors.length);
+
+      for (Map.Entry<Integer, Container> entry : overlays.entrySet()) {
+        int containerIndex = entry.getKey();
+        int cardinality = entry.getValue().cardinality();
+        descriptors[containerIndex] = Math.min(cardinality, DENSE_CONTAINER_SIZE);
+      }
+
+      return descriptors;
+    }
+
+    private int sizeOfContainers(int[] descriptorArray, int startIndex, int endIndexExclusive) {
+      int size = 0;
+      for (int i = startIndex; i < endIndexExclusive; i += 1) {
+        size += descriptorArray[i];
+      }
+
+      return size;
+    }
+
+    private static int writeHeader(ByteBuffer buffer, int cardinality, int descriptorCount) {
+      ByteBuffers.writeByte(buffer, VERSION, 0);
+      ByteBuffers.writeLittleEndianUnsigned(buffer, cardinality, 1, 3);
+      ByteBuffers.writeLittleEndianUnsigned(buffer, descriptorCount, 4, 2);
+
+      return HEADER_SIZE;
+    }
+
+    private int copyOriginalContainers(
+        int[] descriptorArray,
+        int startIndex,
+        int endIndexExclusive,
+        ByteBuffer buffer,
+        int currentPos) {
+      if (startIndex < baseContainerCount && startIndex < endIndexExclusive) {
+        int offset = base.offset(startIndex);
+        int sizeToCopy = sizeOfContainers(descriptorArray, startIndex, endIndexExclusive);
+        if (sizeToCopy > 0) {
+          buffer.put(currentPos, base.buffer(), offset, sizeToCopy);
+        }
+
+        return sizeToCopy;
+      }
+
+      return 0;
+    }
+  }
+
+  private static class Container {
+    private byte[] dense = null;
+    private byte[] sparse = null;
+    private int cardinality = 0;
+
+    private Container() {
+      this.sparse = new byte[DENSE_CONTAINER_SIZE];
+    }
+
+    private Container(ByteBuffer buffer, int offset, int length) {
+      byte[] bytes = new byte[DENSE_CONTAINER_SIZE];
+      buffer.get(offset, bytes, 0, length);

Review Comment:
   This writer emits `0b0010_0000`, but accoording to spec readers must ignore the low five bits of a dense descriptor. Should `isDense` check only the top three bits: `(descriptor & 0b1110_0000) == DENSE_CONTAINER_BIT`?
   
   Dense descriptors may be greater than `DENSE_CONTAINER_SIZE`, but their payload is always 32 bytes. Should this use `isDense(length) ? DENSE_CONTAINER_SIZE : length` as the read size? 
   
   Is `descriptor` a better arg name than `length`? Below is the only the caller code of this constructor.
   ```
   if (containerIndex < baseContainerCount) {
     overlay =
         new Container(
             base.buffer(), base.offset(containerIndex), base.descriptor(containerIndex));
   ```



-- 
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 mutable Mumbling bitmap implementation [iceberg]

Posted by "rdblue (via GitHub)" <gi...@apache.org>.
rdblue commented on code in PR #18544:
URL: https://github.com/apache/iceberg/pull/18544#discussion_r4351845836


##########
core/src/main/java/org/apache/iceberg/mumbling/MumblingBitmap.java:
##########
@@ -51,23 +64,23 @@ class MumblingBitmap implements ManifestBitmap {
   private volatile int[] offsets = null;
 
   MumblingBitmap(ByteBuffer data) {
-    int version = data.get(data.position()) & 0xFF;
+    int version = ByteBuffers.readByte(data, 0);
     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);
+    this.cardinality = ByteBuffers.readLittleEndianUnsigned(data, 1, 3);
+    this.containerCount = ByteBuffers.readLittleEndianUnsigned(data, 4, 2);
 
     Preconditions.checkState(
-        containerCount <= 8192, "Invalid container count: %s > 8,192 (max)", containerCount);
+        containerCount < MAX_CONTAINER_COUNT,

Review Comment:
   Yeah, I think this is right.



-- 
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 mutable Mumbling bitmap implementation [iceberg]

Posted by "stevenzwu (via GitHub)" <gi...@apache.org>.
stevenzwu commented on code in PR #18544:
URL: https://github.com/apache/iceberg/pull/18544#discussion_r4354283177


##########
api/src/test/java/org/apache/iceberg/util/TestByteBuffers.java:
##########
@@ -36,9 +37,85 @@ public void testRead2ByteUnsigned() {
     assertThat(ByteBuffers.readLittleEndianUnsigned(buffer, 0, 2)).isEqualTo(65535);
   }
 
+  @Test
+  public void testRead2ByteLittleEndian() {

Review Comment:
   The new tests lock little-endian reads on a big-endian buffer. `writeLittleEndianUnsigned` has the same change and no coverage here. 



##########
core/src/test/java/org/apache/iceberg/mumbling/TestMumblingBitmap.java:
##########
@@ -290,4 +343,439 @@ void testBufferWithOffset() {
     assertThat(bitmap.isSet(42)).isTrue();
     assertThat(bitmap.isSet(43)).isFalse();
   }
+
+  @Test
+  public void testMutableValidatesPositions() {
+    MutableBitmap bitmap = MumblingBitmap.newMutableBitmap();
+
+    assertThat(bitmap.set(0)).isTrue();
+    assertThatThrownBy(() -> bitmap.set(-1))
+        .isInstanceOf(IllegalArgumentException.class)
+        .hasMessage("Cannot set invalid bit position: -1 < 0");
+
+    assertThat(bitmap.set(2_097_151)).isTrue();
+    assertThatThrownBy(() -> bitmap.set(2_097_152))
+        .isInstanceOf(IllegalArgumentException.class)
+        .hasMessage("Cannot set invalid bit position: 2097152 (must be < 2,097,152)");
+  }
+
+  @Test
+  public void testMutableOverlayPassthrough() {
+    MutableBitmap bitmap = MUTABLE_TEST_BASE.asMutable();
+
+    assertThat(bitmap.cardinality()).isEqualTo(34);
+
+    assertThat(bitmap.isSet(0)).isTrue();
+    assertThat(bitmap.isSet(1)).isFalse();
+
+    assertThat(bitmap.isSet(263)).isFalse();
+    assertThat(bitmap.isSet(289)).isFalse();

Review Comment:
   I believe these 4 lines check the positions right before the dense bytes. similar to line 371, I believe the next 3 positions meant 279, 295, 311. 
   
   line-381-384 covers the positions right after the dense bytes.
   
   please correct me if I misunderstood the intention.



##########
core/src/test/java/org/apache/iceberg/mumbling/TestMumblingBitmap.java:
##########
@@ -290,4 +343,439 @@ void testBufferWithOffset() {
     assertThat(bitmap.isSet(42)).isTrue();
     assertThat(bitmap.isSet(43)).isFalse();
   }
+
+  @Test
+  public void testMutableValidatesPositions() {
+    MutableBitmap bitmap = MumblingBitmap.newMutableBitmap();
+
+    assertThat(bitmap.set(0)).isTrue();
+    assertThatThrownBy(() -> bitmap.set(-1))
+        .isInstanceOf(IllegalArgumentException.class)
+        .hasMessage("Cannot set invalid bit position: -1 < 0");
+
+    assertThat(bitmap.set(2_097_151)).isTrue();
+    assertThatThrownBy(() -> bitmap.set(2_097_152))
+        .isInstanceOf(IllegalArgumentException.class)
+        .hasMessage("Cannot set invalid bit position: 2097152 (must be < 2,097,152)");
+  }
+
+  @Test
+  public void testMutableOverlayPassthrough() {
+    MutableBitmap bitmap = MUTABLE_TEST_BASE.asMutable();
+
+    assertThat(bitmap.cardinality()).isEqualTo(34);
+
+    assertThat(bitmap.isSet(0)).isTrue();
+    assertThat(bitmap.isSet(1)).isFalse();
+
+    assertThat(bitmap.isSet(263)).isFalse();
+    assertThat(bitmap.isSet(289)).isFalse();
+    assertThat(bitmap.isSet(305)).isFalse();
+    assertThat(bitmap.isSet(321)).isFalse();
+    for (int i = 0; i < 8; i += 1) {
+      assertThat(bitmap.isSet(264 + i)).isTrue();
+      assertThat(bitmap.isSet(280 + i)).isTrue();
+      assertThat(bitmap.isSet(296 + i)).isTrue();
+      assertThat(bitmap.isSet(312 + i)).isTrue();
+    }
+    assertThat(bitmap.isSet(272)).isFalse();
+    assertThat(bitmap.isSet(288)).isFalse();
+    assertThat(bitmap.isSet(304)).isFalse();
+    assertThat(bitmap.isSet(320)).isFalse();
+
+    assertThat(bitmap.isSet(766)).isFalse();
+    assertThat(bitmap.isSet(767)).isTrue();
+    assertThat(bitmap.isSet(768)).isFalse();
+  }
+
+  @Test
+  public void testMutableOverlaySparseUpdate() {
+    MutableBitmap bitmap = MUTABLE_TEST_BASE.asMutable();
+
+    assertThat(bitmap.cardinality()).isEqualTo(34);
+
+    assertThat(bitmap.set(1)).isTrue();
+    assertThat(bitmap.set(0)).isFalse();
+    assertThat(bitmap.set(1)).isFalse();
+
+    assertThat(bitmap.cardinality()).isEqualTo(35);
+    assertThat(bitmap.isSet(0)).isTrue();
+    assertThat(bitmap.isSet(1)).isTrue();
+    assertThat(bitmap.isSet(2)).isFalse();
+
+    assertThat(bitmap.set(766)).isTrue();
+    assertThat(bitmap.set(767)).isFalse();
+    assertThat(bitmap.set(766)).isFalse();
+
+    assertThat(bitmap.cardinality()).isEqualTo(36);
+    assertThat(bitmap.isSet(765)).isFalse();
+    assertThat(bitmap.isSet(766)).isTrue();
+    assertThat(bitmap.isSet(767)).isTrue();
+    assertThat(bitmap.isSet(768)).isFalse();
+  }
+
+  @Test
+  public void testMutableOverlayDenseUpdate() {
+    MutableBitmap bitmap = MUTABLE_TEST_BASE.asMutable();
+
+    assertThat(bitmap.cardinality()).isEqualTo(34);
+
+    for (int i = 0; i < 8; i += 1) {
+      assertThat(bitmap.set(256 + i)).isTrue();
+      assertThat(bitmap.set(256 + i)).isFalse();
+      assertThat(bitmap.set(264 + i)).isFalse(); // already set
+    }
+
+    assertThat(bitmap.cardinality()).isEqualTo(42);
+
+    assertThat(bitmap.isSet(255)).isFalse();
+    for (int i = 0; i < 16; i += 1) {
+      assertThat(bitmap.isSet(256 + i)).isTrue();
+    }
+    assertThat(bitmap.isSet(272)).isFalse();
+
+    assertThat(bitmap.set(511)).isTrue();
+    assertThat(bitmap.set(511)).isFalse();
+    assertThat(bitmap.isSet(511)).isTrue();
+
+    assertThat(bitmap.cardinality()).isEqualTo(43);
+  }
+
+  @Test
+  public void testMutableOverlaySparseToDenseUpdate() {
+    MutableBitmap bitmap = MUTABLE_TEST_BASE.asMutable();
+
+    assertThat(bitmap.cardinality()).isEqualTo(34);
+
+    for (int i = 1; i < 33; i += 1) {
+      assertThat(bitmap.set(i)).isTrue();
+      assertThat(bitmap.set(i)).isFalse();
+    }
+
+    assertThat(bitmap.cardinality()).isEqualTo(66);
+
+    for (int i = 0; i < 33; i += 1) {
+      assertThat(bitmap.isSet(i)).isTrue();
+    }
+    assertThat(bitmap.isSet(33)).isFalse();
+
+    // set positions backward so the sparse list is rewritten
+    for (int i = 254; i > 222; i -= 1) {
+      assertThat(bitmap.set(i)).isTrue();
+      assertThat(bitmap.set(i)).isFalse();
+    }
+
+    assertThat(bitmap.cardinality()).isEqualTo(98);
+  }
+
+  @Test
+  public void testMutableOverlayNewContainer() {
+    MutableBitmap bitmap = MUTABLE_TEST_BASE.asMutable();
+
+    assertThat(bitmap.set(1024)).isTrue(); // container index 4, position 0
+    assertThat(bitmap.set(1024)).isFalse();
+    assertThat(bitmap.isSet(1024)).isTrue();
+    assertThat(bitmap.cardinality()).isEqualTo(35);
+  }
+
+  @Test
+  public void testMutableEmptySerialization() {
+    MutableBitmap empty = MumblingBitmap.newMutableBitmap();
+
+    assertThat(empty.cardinality()).isEqualTo(0);
+    assertThat(empty.buffer())
+        .isEqualTo(ByteBuffer.wrap(new byte[] {0x01, 0x00, 0x00, 0x00, 0x00, 0x00}));
+  }
+
+  @Test
+  public void testMutableNoopSerialization() {
+    MutableBitmap bitmap = MUTABLE_TEST_BASE.asMutable();
+
+    assertThat(bitmap.buffer())
+        .as("Does not reuse the original buffer")
+        .isNotSameAs(MUTABLE_TEST_BASE.buffer());
+    assertThat(bitmap.buffer()).isEqualTo(MUTABLE_TEST_BASE.buffer());
+  }
+
+  @Test
+  public void testMutableNewContainerSerialization() {
+    MutableBitmap bitmap = MUTABLE_TEST_BASE.asMutable();
+
+    assertThat(bitmap.set(1024)).isTrue(); // container 4, position 0
+    assertThat(bitmap.cardinality()).isEqualTo(35);
+    assertThat(bitmap.set(2048)).isTrue(); // container 8, position 0
+    assertThat(bitmap.cardinality()).isEqualTo(36);
+
+    MumblingBitmap result = new MumblingBitmap(bitmap.buffer());
+    assertThat(result.cardinality()).isEqualTo(36);
+    assertThat(result.descriptors()).containsExactly(1, 32, 1, 0, 1, 0, 0, 0, 1);
+
+    assertThat(result.isSet(0)).isTrue();
+
+    for (int i = 0; i < 8; i += 1) {
+      assertThat(result.isSet(264 + i)).isTrue();
+      assertThat(result.isSet(280 + i)).isTrue();
+      assertThat(result.isSet(296 + i)).isTrue();
+      assertThat(result.isSet(312 + i)).isTrue();
+    }
+
+    assertThat(result.isSet(767)).isTrue();
+
+    assertThat(result.isSet(1024)).isTrue();
+    assertThat(result.isSet(2048)).isTrue();
+  }
+
+  @Test
+  public void testMutableEmptyWithNewContainerSerialization() {
+    MutableBitmap bitmap = MumblingBitmap.newMutableBitmap();
+
+    assertThat(bitmap.set(1024)).isTrue(); // container 4, position 0
+    assertThat(bitmap.set(2048)).isTrue(); // container 8, position 0
+
+    assertThat(bitmap.cardinality()).isEqualTo(2);
+
+    MumblingBitmap result = new MumblingBitmap(bitmap.buffer());
+    assertThat(result.cardinality()).isEqualTo(2);
+    assertThat(result.descriptors()).contains(0, 0, 0, 0, 1, 0, 0, 0, 1);
+
+    assertThat(result.isSet(1024)).isTrue();
+    assertThat(result.isSet(2048)).isTrue();
+  }
+
+  @Test
+  public void testMutableSparseUpdateSerialization() {
+    MutableBitmap bitmap = MUTABLE_TEST_BASE.asMutable();
+
+    assertThat(bitmap.set(1)).isTrue();
+    assertThat(bitmap.set(766)).isTrue(); // container index 2, pos 254
+    assertThat(bitmap.cardinality()).isEqualTo(36);
+
+    ByteBuffer serialized = bitmap.buffer();
+    int[] expectedDescriptors = new int[] {2, 32, 2};
+
+    MumblingBitmap result = new MumblingBitmap(serialized);
+    assertThat(result.cardinality()).isEqualTo(36);
+    assertThat(result.descriptors()).isEqualTo(expectedDescriptors);
+
+    assertThat(bitmap.isSet(1)).isTrue();
+    assertThat(bitmap.isSet(766)).isTrue();
+
+    ByteBuffer descriptors = PFOREncoding.encode(expectedDescriptors, expectedDescriptors.length);
+    int descriptorSize = descriptors.remaining();
+    int containersOffset = HEADER_SIZE + descriptorSize;
+
+    assertThat(serialized.slice(6, descriptorSize)).isEqualTo(descriptors);
+
+    assertThat(serialized.slice(containersOffset, 2)).isEqualTo(sparse(0, 1).buffer());
+    assertThat(serialized.slice(containersOffset + 2, 32))
+        .isEqualTo(dense(DENSE_CONTAINER).buffer());
+    assertThat(serialized.slice(containersOffset + 34, 2)).isEqualTo(sparse(254, 255).buffer());
+  }
+
+  @Test
+  public void testMutableDenseUpdateSerialization() {
+    MutableBitmap bitmap = MUTABLE_TEST_BASE.asMutable();
+
+    for (int i = 0; i < 8; i += 1) {
+      assertThat(bitmap.set(256 + i)).isTrue();
+    }
+    assertThat(bitmap.set(511)).isTrue(); // last bit of the dense container
+
+    assertThat(bitmap.cardinality()).isEqualTo(43);
+
+    ByteBuffer serialized = bitmap.buffer();
+    int[] expectedDescriptors = new int[] {1, 32, 1};
+
+    MumblingBitmap result = new MumblingBitmap(serialized);
+    assertThat(result.cardinality()).isEqualTo(43);
+    assertThat(result.descriptors()).isEqualTo(expectedDescriptors);
+
+    ByteBuffer descriptors = PFOREncoding.encode(expectedDescriptors, expectedDescriptors.length);
+    int descriptorSize = descriptors.remaining();
+    int containersOffset = HEADER_SIZE + descriptorSize;
+
+    assertThat(serialized.slice(6, descriptorSize)).isEqualTo(descriptors);
+
+    assertThat(serialized.slice(containersOffset, 1)).isEqualTo(sparse(0).buffer());
+
+    byte[] denseBytes = Arrays.copyOf(DENSE_CONTAINER, 32);
+    denseBytes[0] = (byte) 0xFF;
+    denseBytes[31] = (byte) 0x01; // last bit
+    assertThat(serialized.slice(containersOffset + 1, 32)).isEqualTo(dense(denseBytes).buffer());
+
+    assertThat(serialized.slice(containersOffset + 33, 1)).isEqualTo(sparse(255).buffer());
+  }
+
+  @Test
+  public void testMutableSparseToDenseUpdateSerialization() {
+    MutableBitmap bitmap = MUTABLE_TEST_BASE.asMutable();
+
+    for (int i = 766; i > 735; i -= 1) {
+      assertThat(bitmap.set(i)).isTrue();
+    }
+    assertThat(bitmap.cardinality()).isEqualTo(65);
+
+    ByteBuffer serialized = bitmap.buffer();
+    int[] expectedDescriptors = new int[] {1, 32, 32};
+
+    MumblingBitmap result = new MumblingBitmap(serialized);
+    assertThat(result.cardinality()).isEqualTo(65);
+    assertThat(result.descriptors()).isEqualTo(expectedDescriptors);
+
+    assertThat(result.isSet(0)).isTrue();
+
+    for (int i = 0; i < 8; i += 1) {
+      assertThat(result.isSet(264 + i)).isTrue();
+      assertThat(result.isSet(280 + i)).isTrue();
+      assertThat(result.isSet(296 + i)).isTrue();
+      assertThat(result.isSet(312 + i)).isTrue();
+    }
+
+    for (int i = 736; i < 767; i += 1) {
+      assertThat(bitmap.isSet(i)).isTrue();
+    }
+
+    assertThat(result.isSet(767)).isTrue();
+
+    ByteBuffer descriptors = PFOREncoding.encode(expectedDescriptors, expectedDescriptors.length);
+    int descriptorSize = descriptors.remaining();
+    int containersOffset = HEADER_SIZE + descriptorSize;
+
+    assertThat(serialized.slice(6, descriptorSize)).isEqualTo(descriptors);
+
+    assertThat(serialized.slice(containersOffset, 1)).isEqualTo(sparse(0).buffer());
+    assertThat(serialized.slice(containersOffset + 1, 32))
+        .isEqualTo(dense(DENSE_CONTAINER).buffer());
+
+    byte[] denseBytes = new byte[32];
+    denseBytes[28] = (byte) 0xFF;
+    denseBytes[29] = (byte) 0xFF;
+    denseBytes[30] = (byte) 0xFF;
+    denseBytes[31] = (byte) 0xFF;
+    assertThat(serialized.slice(containersOffset + 33, 32)).isEqualTo(dense(denseBytes).buffer());
+  }
+
+  @Test
+  public void testMutableRandomPositions() {
+    Random positions = new Random(39826538713L);
+    int count = 0;
+
+    MutableBitmap bitmap = MumblingBitmap.newMutableBitmap();
+
+    for (int i = 0; i < 50_000; i += 1) {
+      if (bitmap.set(positions.nextInt(64_000))) {
+        count += 1;
+      }
+    }
+
+    MumblingBitmap result = new MumblingBitmap(bitmap.buffer());
+
+    assertThat(bitmap.cardinality()).isEqualTo(count);
+    assertThat(result.cardinality()).isEqualTo(count);
+
+    // check that all positions are set
+    Random validation = new Random(39826538713L);
+    for (int i = 0; i < 50_000; i += 1) {
+      int pos = validation.nextInt(64_000);
+      assertThat(bitmap.isSet(pos)).isTrue();
+      assertThat(result.isSet(pos)).isTrue();
+    }
+  }
+
+  @Test
+  public void testRelocatedBuffer() {
+    MumblingBitmap bitmap = new MumblingBitmap(relocate(MUTABLE_TEST_BASE.buffer()));
+
+    assertThat(bitmap.cardinality()).isEqualTo(34);
+    assertThat(bitmap.descriptors()).containsExactly(1, 32, 1);
+
+    assertThat(bitmap.isSet(0)).isTrue();
+    assertThat(bitmap.isSet(1)).isFalse();
+
+    assertThat(bitmap.isSet(263)).isFalse();
+    for (int i = 0; i < 8; i += 1) {
+      assertThat(bitmap.isSet(264 + i)).isTrue();
+      assertThat(bitmap.isSet(280 + i)).isTrue();
+      assertThat(bitmap.isSet(296 + i)).isTrue();
+      assertThat(bitmap.isSet(312 + i)).isTrue();
+    }
+    assertThat(bitmap.isSet(272)).isFalse();
+    assertThat(bitmap.isSet(320)).isFalse();
+
+    assertThat(bitmap.isSet(766)).isFalse();
+    assertThat(bitmap.isSet(767)).isTrue();
+    assertThat(bitmap.isSet(768)).isFalse();
+  }
+
+  @Test
+  public void testRelocatedBufferUpdateSerialization() {
+    MutableBitmap bitmap = new MumblingBitmap(relocate(MUTABLE_TEST_BASE.buffer())).asMutable();

Review Comment:
   should we assert the bitmap state before any bit mutations to verify that relocated byte buffer doesn't cause any problem?



##########
core/src/test/java/org/apache/iceberg/mumbling/TestMumblingBitmap.java:
##########
@@ -27,9 +27,62 @@
 
 import java.nio.ByteBuffer;
 import java.util.Arrays;
+import java.util.Random;
 import org.junit.jupiter.api.Test;
 
 class TestMumblingBitmap {
+  private static final int HEADER_SIZE = 6;
+  private static final byte[] DENSE_CONTAINER = new byte[32];
+
+  static {
+    DENSE_CONTAINER[1] = (byte) 0xFF;
+    DENSE_CONTAINER[3] = (byte) 0xFF;
+    DENSE_CONTAINER[5] = (byte) 0xFF;
+    DENSE_CONTAINER[7] = (byte) 0xFF;
+  }
+
+  private static final MumblingBitmap MUTABLE_TEST_BASE =
+      bitmap(sparse(0), dense(DENSE_CONTAINER), sparse(255));
+
+  @Test
+  public void testInvalidVersion() {

Review Comment:
   Tests cover an invalid version, container count, and cardinality, but not an invalid descriptor. Fixtures and the writer only emit descriptors 0–32, so these cases never appear:
   
   1. A dense descriptor with the low bits set (33–63). 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.
   
   A dense container is 32 bytes. The reader accepts only 32, so 33 is rejected with "Invalid descriptor, not sparse or dense".
   
   2. A descriptor that is neither sparse nor dense (64 or above). 96 is worth including so a check of only bit 5 does not treat it as dense.
   
   These need hand-built buffers.



-- 
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 mutable Mumbling bitmap implementation [iceberg]

Posted by "rdblue (via GitHub)" <gi...@apache.org>.
rdblue commented on code in PR #18544:
URL: https://github.com/apache/iceberg/pull/18544#discussion_r4352703749


##########
core/src/main/java/org/apache/iceberg/mumbling/MumblingBitmap.java:
##########
@@ -138,6 +160,282 @@ private int offset(int containerIndex) {
     return offsets[containerIndex];
   }
 
+  public MutableBitmap asMutable() {
+    return new Mutable(this);
+  }
+
+  /**
+   * A copy-on-write {@link MutableBitmap} implementation for Mumbling.
+   *
+   * <p>When a new bit position is set, an overlay is created for the position's container.
+   *
+   * <p>The initial buffer is not modified.
+   */
+  private static class Mutable implements MutableBitmap {
+    private final NavigableMap<Integer, Container> overlays = Maps.newTreeMap();
+    private final MumblingBitmap base;
+    private final int baseContainerCount;
+    private int cardinality = 0;
+
+    public Mutable(MumblingBitmap base) {
+      this.base = base;
+      this.baseContainerCount = base.descriptors().length;
+      this.cardinality = base.cardinality();
+    }
+
+    @Override
+    public int cardinality() {
+      return cardinality;
+    }
+
+    @Override
+    public boolean isSet(int pos) {
+      Container overlay = overlays.get(containerIndex(pos));
+      if (overlay != null) {
+        return overlay.isSet(posInContainer(pos));
+      }
+
+      return base.isSet(pos);
+    }
+
+    @Override
+    public boolean set(int pos) {
+      Preconditions.checkArgument(pos >= 0, "Cannot set invalid bit position: %s < 0", pos);
+      Preconditions.checkArgument(
+          pos < MAX_CARDINALITY, "Cannot set invalid bit position: %s (must be < 2,097,152)", pos);
+
+      int containerIndex = containerIndex(pos);
+      Container overlay = overlays.get(containerIndex);
+      if (overlay == null) {
+        if (containerIndex < baseContainerCount) {
+          overlay =
+              new Container(
+                  base.buffer(), base.offset(containerIndex), base.descriptor(containerIndex));
+        } else {
+          overlay = new Container();
+        }
+        overlays.put(containerIndex, overlay);
+      }
+
+      if (overlay.set(posInContainer(pos))) {
+        this.cardinality += 1;
+        return true;
+      }
+
+      return false;
+    }
+
+    @Override
+    public ByteBuffer buffer() {
+      int[] descriptorArray = descriptorArray();
+      int containersSize = sizeOfContainers(descriptorArray, 0, descriptorArray.length);
+      ByteBuffer descBuffer = PFOREncoding.encode(descriptorArray, descriptorArray.length);
+      int descriptorsSize = descBuffer.remaining();
+
+      ByteBuffer buffer = ByteBuffer.allocate(HEADER_SIZE + descriptorsSize + containersSize);
+      int currentPos = writeHeader(buffer, cardinality, descriptorArray.length);
+
+      buffer.put(HEADER_SIZE, descBuffer, descBuffer.position(), descriptorsSize);
+      currentPos += descriptorsSize;
+
+      int nextContainerIndex = 0;
+      for (Map.Entry<Integer, Container> entry : overlays.entrySet()) {
+        int containerIndex = entry.getKey();
+        currentPos +=
+            copyOriginalContainers(
+                descriptorArray, nextContainerIndex, containerIndex, buffer, currentPos);
+        currentPos += entry.getValue().writeTo(buffer, currentPos);
+        nextContainerIndex = containerIndex + 1;
+      }
+
+      copyOriginalContainers(
+          descriptorArray, nextContainerIndex, descriptorArray.length, buffer, currentPos);
+
+      return buffer;
+    }
+
+    private int[] descriptorArray() {
+      int[] baseDescriptors = base.descriptors();
+      int lastOverlayIndex = overlays.isEmpty() ? -1 : overlays.lastKey();
+      int numContainers = Math.max(lastOverlayIndex + 1, baseDescriptors.length);
+      int[] descriptors = new int[numContainers]; // filled with 0
+      System.arraycopy(baseDescriptors, 0, descriptors, 0, baseDescriptors.length);
+
+      for (Map.Entry<Integer, Container> entry : overlays.entrySet()) {
+        int containerIndex = entry.getKey();
+        int cardinality = entry.getValue().cardinality();
+        descriptors[containerIndex] = Math.min(cardinality, DENSE_CONTAINER_SIZE);
+      }
+
+      return descriptors;
+    }
+
+    private int sizeOfContainers(int[] descriptorArray, int startIndex, int endIndexExclusive) {
+      int size = 0;
+      for (int i = startIndex; i < endIndexExclusive; i += 1) {
+        size += descriptorArray[i];
+      }
+
+      return size;
+    }
+
+    private static int writeHeader(ByteBuffer buffer, int cardinality, int descriptorCount) {
+      ByteBuffers.writeByte(buffer, VERSION, 0);
+      ByteBuffers.writeLittleEndianUnsigned(buffer, cardinality, 1, 3);
+      ByteBuffers.writeLittleEndianUnsigned(buffer, descriptorCount, 4, 2);
+
+      return HEADER_SIZE;
+    }
+
+    private int copyOriginalContainers(
+        int[] descriptorArray,
+        int startIndex,
+        int endIndexExclusive,
+        ByteBuffer buffer,
+        int currentPos) {
+      if (startIndex < baseContainerCount && startIndex < endIndexExclusive) {
+        int offset = base.offset(startIndex);
+        int sizeToCopy = sizeOfContainers(descriptorArray, startIndex, endIndexExclusive);
+        if (sizeToCopy > 0) {
+          buffer.put(currentPos, base.buffer(), offset, sizeToCopy);
+        }
+
+        return sizeToCopy;
+      }
+
+      return 0;
+    }
+  }
+
+  private static class Container {
+    private byte[] dense = null;
+    private byte[] sparse = null;
+    private int cardinality = 0;
+
+    private Container() {
+      this.sparse = new byte[DENSE_CONTAINER_SIZE];
+    }
+
+    private Container(ByteBuffer buffer, int offset, int length) {
+      byte[] bytes = new byte[DENSE_CONTAINER_SIZE];
+      buffer.get(offset, bytes, 0, length);
+
+      if (isDense(length)) {
+        this.dense = bytes;
+        this.cardinality = denseCardinality(dense);
+      } else {
+        this.sparse = bytes;
+        this.cardinality = length;
+      }
+    }
+
+    int cardinality() {
+      return cardinality;
+    }
+
+    private boolean isSet(int posInContainer) {
+      if (cardinality < 32) {
+        // sparse
+        for (int i = 0; i < cardinality; i += 1) {
+          if ((sparse[i] & 0xFF) == posInContainer) {
+            return true;
+          }
+        }
+
+        return false;
+      } else {
+        // dense
+        int bitShift = denseBitShift(posInContainer);
+        return ((dense[denseByteIndex(posInContainer)] >>> bitShift) & 0b1) == 0b1;
+      }
+    }
+
+    private boolean set(int posInContainer) {
+      if (setInternal(posInContainer)) {
+        this.cardinality += 1;
+        return true;
+      }
+
+      return false;
+    }
+
+    int writeTo(ByteBuffer buffer, int offset) {
+      if (cardinality < DENSE_CONTAINER_SIZE) {
+        buffer.put(offset, sparse, 0, cardinality);
+        return cardinality;
+      } else {
+        buffer.put(offset, dense, 0, dense.length);
+        return dense.length;
+      }
+    }
+
+    private boolean setInternal(int posInContainer) {
+      if (cardinality < 31) {

Review Comment:
   I'll use `MAX_SPARSE_CARDINALITY` instead.



-- 
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 mutable Mumbling bitmap implementation [iceberg]

Posted by "stevenzwu (via GitHub)" <gi...@apache.org>.
stevenzwu commented on code in PR #18544:
URL: https://github.com/apache/iceberg/pull/18544#discussion_r4300034701


##########
core/src/main/java/org/apache/iceberg/mumbling/MumblingBitmap.java:
##########
@@ -138,6 +160,282 @@ private int offset(int containerIndex) {
     return offsets[containerIndex];
   }
 
+  public MutableBitmap asMutable() {
+    return new Mutable(this);
+  }
+
+  /**
+   * A copy-on-write {@link MutableBitmap} implementation for Mumbling.
+   *
+   * <p>When a new bit position is set, an overlay is created for the position's container.
+   *
+   * <p>The initial buffer is not modified.
+   */
+  private static class Mutable implements MutableBitmap {
+    private final NavigableMap<Integer, Container> overlays = Maps.newTreeMap();
+    private final MumblingBitmap base;
+    private final int baseContainerCount;
+    private int cardinality = 0;
+
+    public Mutable(MumblingBitmap base) {
+      this.base = base;
+      this.baseContainerCount = base.descriptors().length;
+      this.cardinality = base.cardinality();
+    }
+
+    @Override
+    public int cardinality() {
+      return cardinality;
+    }
+
+    @Override
+    public boolean isSet(int pos) {
+      Container overlay = overlays.get(containerIndex(pos));
+      if (overlay != null) {
+        return overlay.isSet(posInContainer(pos));
+      }
+
+      return base.isSet(pos);
+    }
+
+    @Override
+    public boolean set(int pos) {
+      Preconditions.checkArgument(pos >= 0, "Cannot set invalid bit position: %s < 0", pos);
+      Preconditions.checkArgument(
+          pos < MAX_CARDINALITY, "Cannot set invalid bit position: %s (must be < 2,097,152)", pos);
+
+      int containerIndex = containerIndex(pos);
+      Container overlay = overlays.get(containerIndex);
+      if (overlay == null) {
+        if (containerIndex < baseContainerCount) {
+          overlay =
+              new Container(
+                  base.buffer(), base.offset(containerIndex), base.descriptor(containerIndex));
+        } else {
+          overlay = new Container();
+        }
+        overlays.put(containerIndex, overlay);
+      }
+
+      if (overlay.set(posInContainer(pos))) {
+        this.cardinality += 1;
+        return true;
+      }
+
+      return false;
+    }
+
+    @Override
+    public ByteBuffer buffer() {
+      int[] descriptorArray = descriptorArray();
+      int containersSize = sizeOfContainers(descriptorArray, 0, descriptorArray.length);
+      ByteBuffer descBuffer = PFOREncoding.encode(descriptorArray, descriptorArray.length);
+      int descriptorsSize = descBuffer.remaining();
+
+      ByteBuffer buffer = ByteBuffer.allocate(HEADER_SIZE + descriptorsSize + containersSize);
+      int currentPos = writeHeader(buffer, cardinality, descriptorArray.length);
+
+      buffer.put(HEADER_SIZE, descBuffer, descBuffer.position(), descriptorsSize);
+      currentPos += descriptorsSize;
+
+      int nextContainerIndex = 0;
+      for (Map.Entry<Integer, Container> entry : overlays.entrySet()) {
+        int containerIndex = entry.getKey();
+        currentPos +=
+            copyOriginalContainers(
+                descriptorArray, nextContainerIndex, containerIndex, buffer, currentPos);
+        currentPos += entry.getValue().writeTo(buffer, currentPos);
+        nextContainerIndex = containerIndex + 1;
+      }
+
+      copyOriginalContainers(
+          descriptorArray, nextContainerIndex, descriptorArray.length, buffer, currentPos);
+
+      return buffer;
+    }
+
+    private int[] descriptorArray() {
+      int[] baseDescriptors = base.descriptors();
+      int lastOverlayIndex = overlays.isEmpty() ? -1 : overlays.lastKey();
+      int numContainers = Math.max(lastOverlayIndex + 1, baseDescriptors.length);
+      int[] descriptors = new int[numContainers]; // filled with 0
+      System.arraycopy(baseDescriptors, 0, descriptors, 0, baseDescriptors.length);
+
+      for (Map.Entry<Integer, Container> entry : overlays.entrySet()) {
+        int containerIndex = entry.getKey();
+        int cardinality = entry.getValue().cardinality();
+        descriptors[containerIndex] = Math.min(cardinality, DENSE_CONTAINER_SIZE);
+      }
+
+      return descriptors;
+    }
+
+    private int sizeOfContainers(int[] descriptorArray, int startIndex, int endIndexExclusive) {
+      int size = 0;
+      for (int i = startIndex; i < endIndexExclusive; i += 1) {
+        size += descriptorArray[i];
+      }
+
+      return size;
+    }
+
+    private static int writeHeader(ByteBuffer buffer, int cardinality, int descriptorCount) {
+      ByteBuffers.writeByte(buffer, VERSION, 0);
+      ByteBuffers.writeLittleEndianUnsigned(buffer, cardinality, 1, 3);
+      ByteBuffers.writeLittleEndianUnsigned(buffer, descriptorCount, 4, 2);
+
+      return HEADER_SIZE;
+    }
+
+    private int copyOriginalContainers(
+        int[] descriptorArray,
+        int startIndex,
+        int endIndexExclusive,
+        ByteBuffer buffer,
+        int currentPos) {
+      if (startIndex < baseContainerCount && startIndex < endIndexExclusive) {
+        int offset = base.offset(startIndex);
+        int sizeToCopy = sizeOfContainers(descriptorArray, startIndex, endIndexExclusive);
+        if (sizeToCopy > 0) {
+          buffer.put(currentPos, base.buffer(), offset, sizeToCopy);
+        }
+
+        return sizeToCopy;
+      }
+
+      return 0;
+    }
+  }
+
+  private static class Container {
+    private byte[] dense = null;
+    private byte[] sparse = null;
+    private int cardinality = 0;
+
+    private Container() {
+      this.sparse = new byte[DENSE_CONTAINER_SIZE];
+    }
+
+    private Container(ByteBuffer buffer, int offset, int length) {
+      byte[] bytes = new byte[DENSE_CONTAINER_SIZE];
+      buffer.get(offset, bytes, 0, length);
+
+      if (isDense(length)) {
+        this.dense = bytes;
+        this.cardinality = denseCardinality(dense);
+      } else {
+        this.sparse = bytes;
+        this.cardinality = length;
+      }
+    }
+
+    int cardinality() {
+      return cardinality;
+    }
+
+    private boolean isSet(int posInContainer) {
+      if (cardinality < 32) {
+        // sparse
+        for (int i = 0; i < cardinality; i += 1) {
+          if ((sparse[i] & 0xFF) == posInContainer) {
+            return true;
+          }
+        }
+
+        return false;
+      } else {
+        // dense
+        int bitShift = denseBitShift(posInContainer);
+        return ((dense[denseByteIndex(posInContainer)] >>> bitShift) & 0b1) == 0b1;
+      }
+    }
+
+    private boolean set(int posInContainer) {
+      if (setInternal(posInContainer)) {
+        this.cardinality += 1;
+        return true;
+      }
+
+      return false;
+    }
+
+    int writeTo(ByteBuffer buffer, int offset) {
+      if (cardinality < DENSE_CONTAINER_SIZE) {
+        buffer.put(offset, sparse, 0, cardinality);
+        return cardinality;
+      } else {
+        buffer.put(offset, dense, 0, dense.length);
+        return dense.length;
+      }
+    }
+
+    private boolean setInternal(int posInContainer) {
+      if (cardinality < 31) {
+        return sparseSet(sparse, cardinality, posInContainer);
+      } else if (cardinality > 31) {
+        return denseSet(dense, posInContainer);
+      } else {
+        // convert to dense, reuse converted buffer if it is present
+        if (dense == null) {
+          this.dense = convertToDense(sparse, cardinality);
+        }
+
+        if (denseSet(dense, posInContainer)) {
+          this.sparse = null;
+          return true;
+        }
+
+        // leave the converted dense array for next set attempt
+        return false;
+      }
+    }
+
+    private static boolean sparseSet(byte[] bytes, int length, int posInContainer) {
+      byte nextInsert = (byte) posInContainer;
+      for (int i = 0; i < length; i += 1) {
+        if (nextInsert == bytes[i]) {
+          return false; // already set
+        } else if ((nextInsert & 0xFF) < (bytes[i] & 0xFF)) {
+          byte replaced = bytes[i];
+          bytes[i] = nextInsert;
+          nextInsert = replaced;
+        }
+      }
+
+      bytes[length] = nextInsert;
+      return true;
+    }
+
+    private static byte[] convertToDense(byte[] sparse, int cardinality) {
+      byte[] dense = new byte[32];
+      for (int i = 0; i < cardinality; i += 1) {
+        denseSet(dense, (sparse[i] & 0xFF));
+      }
+
+      return dense;
+    }
+
+    private static boolean denseSet(byte[] bytes, int posInContainer) {
+      int byteIndex = denseByteIndex(posInContainer);
+      byte bit = (byte) (0b1 << denseBitShift(posInContainer));
+      if ((bytes[byteIndex] & bit) != bit) {
+        bytes[byteIndex] |= bit;
+        return true;
+      }
+
+      return false;
+    }
+
+    private static int denseCardinality(byte[] bytes) {
+      int cardinality = 0;
+      for (int i = 0; i < bytes.length; i += 1) {
+        cardinality += Integer.bitCount(bytes[i]);

Review Comment:
   `Integer.bitCount` takes an `int`, and the `byte` is sign-extended first. A byte `>= 0x80` gains 24 extra one-bits. `0xFF` widens to `0xFFFFFFFF` and counts as 32 instead of 8. We should mask before counting:
   
   ```java
   cardinality += Integer.bitCount(bytes[i] & 0xFF);
   ```
   
   `DENSE_CONTAINER` sets bytes 1, 3, 5, and 7 to `0xFF`, so this container has 32 bits set. This method returns 4 × 32 = 128.
   
   In `descriptorArray()`, `Math.min(cardinality, DENSE_CONTAINER_SIZE)` still writes descriptor 32, and the `>= 32` branches still read and write the dense bytes. `testMutableOverlayDenseUpdate` and `testMutableDenseUpdateSerialization` check the bitmap's own cardinality counter, the descriptor, and those bytes. They never check this bitcount.
   
   
   
   



-- 
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 mutable Mumbling bitmap implementation [iceberg]

Posted by "rdblue (via GitHub)" <gi...@apache.org>.
rdblue commented on code in PR #18544:
URL: https://github.com/apache/iceberg/pull/18544#discussion_r4351845836


##########
core/src/main/java/org/apache/iceberg/mumbling/MumblingBitmap.java:
##########
@@ -51,23 +64,23 @@ class MumblingBitmap implements ManifestBitmap {
   private volatile int[] offsets = null;
 
   MumblingBitmap(ByteBuffer data) {
-    int version = data.get(data.position()) & 0xFF;
+    int version = ByteBuffers.readByte(data, 0);
     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);
+    this.cardinality = ByteBuffers.readLittleEndianUnsigned(data, 1, 3);
+    this.containerCount = ByteBuffers.readLittleEndianUnsigned(data, 4, 2);
 
     Preconditions.checkState(
-        containerCount <= 8192, "Invalid container count: %s > 8,192 (max)", containerCount);
+        containerCount < MAX_CONTAINER_COUNT,

Review Comment:
   Yeah, I think this is right. The rationale for this change was that 8192 requires one more bit than 8191. And similarly, 2097152 requires one more bit than 2097151. I was thinking that it would be better to use 2^n - 1 rather than 2^n, but it doesn't really matter since we are storing these as 2-byte and 3-byte unsigned integers anyway.



-- 
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 mutable Mumbling bitmap implementation [iceberg]

Posted by "rdblue (via GitHub)" <gi...@apache.org>.
rdblue commented on code in PR #18544:
URL: https://github.com/apache/iceberg/pull/18544#discussion_r4365124082


##########
core/src/test/java/org/apache/iceberg/mumbling/TestMumblingBitmap.java:
##########
@@ -290,4 +343,439 @@ void testBufferWithOffset() {
     assertThat(bitmap.isSet(42)).isTrue();
     assertThat(bitmap.isSet(43)).isFalse();
   }
+
+  @Test
+  public void testMutableValidatesPositions() {
+    MutableBitmap bitmap = MumblingBitmap.newMutableBitmap();
+
+    assertThat(bitmap.set(0)).isTrue();
+    assertThatThrownBy(() -> bitmap.set(-1))
+        .isInstanceOf(IllegalArgumentException.class)
+        .hasMessage("Cannot set invalid bit position: -1 < 0");
+
+    assertThat(bitmap.set(2_097_151)).isTrue();
+    assertThatThrownBy(() -> bitmap.set(2_097_152))
+        .isInstanceOf(IllegalArgumentException.class)
+        .hasMessage("Cannot set invalid bit position: 2097152 (must be < 2,097,152)");
+  }
+
+  @Test
+  public void testMutableOverlayPassthrough() {
+    MutableBitmap bitmap = MUTABLE_TEST_BASE.asMutable();
+
+    assertThat(bitmap.cardinality()).isEqualTo(34);
+
+    assertThat(bitmap.isSet(0)).isTrue();
+    assertThat(bitmap.isSet(1)).isFalse();
+
+    assertThat(bitmap.isSet(263)).isFalse();
+    assertThat(bitmap.isSet(289)).isFalse();

Review Comment:
   Yes, this was meant to check the positions just before the bytes that are set (the pattern is 0x00, 0xFF, 0x00, 0xFF, 0x00, 0xFF, 0x00, 0xFF followed by 0x00 for the rest of the container). I initially had the wrong offsets and fixed them, but accidentally left these unchanged.



##########
core/src/test/java/org/apache/iceberg/mumbling/TestMumblingBitmap.java:
##########
@@ -290,4 +343,439 @@ void testBufferWithOffset() {
     assertThat(bitmap.isSet(42)).isTrue();
     assertThat(bitmap.isSet(43)).isFalse();
   }
+
+  @Test
+  public void testMutableValidatesPositions() {
+    MutableBitmap bitmap = MumblingBitmap.newMutableBitmap();
+
+    assertThat(bitmap.set(0)).isTrue();
+    assertThatThrownBy(() -> bitmap.set(-1))
+        .isInstanceOf(IllegalArgumentException.class)
+        .hasMessage("Cannot set invalid bit position: -1 < 0");
+
+    assertThat(bitmap.set(2_097_151)).isTrue();
+    assertThatThrownBy(() -> bitmap.set(2_097_152))
+        .isInstanceOf(IllegalArgumentException.class)
+        .hasMessage("Cannot set invalid bit position: 2097152 (must be < 2,097,152)");
+  }
+
+  @Test
+  public void testMutableOverlayPassthrough() {
+    MutableBitmap bitmap = MUTABLE_TEST_BASE.asMutable();
+
+    assertThat(bitmap.cardinality()).isEqualTo(34);
+
+    assertThat(bitmap.isSet(0)).isTrue();
+    assertThat(bitmap.isSet(1)).isFalse();
+
+    assertThat(bitmap.isSet(263)).isFalse();
+    assertThat(bitmap.isSet(289)).isFalse();

Review Comment:
   Yes, this was meant to check the positions just before the bytes that are set (the pattern is 0x00, 0xFF, 0x00, 0xFF, 0x00, 0xFF, 0x00, 0xFF followed by 0x00 for the rest of the container). I initially had the wrong offsets and fixed them, but accidentally left these unchanged.
   
   I'll push a fix.



-- 
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 mutable Mumbling bitmap implementation [iceberg]

Posted by "amogh-jahagirdar (via GitHub)" <gi...@apache.org>.
amogh-jahagirdar commented on code in PR #18544:
URL: https://github.com/apache/iceberg/pull/18544#discussion_r4303424859


##########
core/src/main/java/org/apache/iceberg/mumbling/MumblingBitmap.java:
##########
@@ -51,23 +64,23 @@ class MumblingBitmap implements ManifestBitmap {
   private volatile int[] offsets = null;
 
   MumblingBitmap(ByteBuffer data) {
-    int version = data.get(data.position()) & 0xFF;
+    int version = ByteBuffers.readByte(data, 0);
     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);
+    this.cardinality = ByteBuffers.readLittleEndianUnsigned(data, 1, 3);
+    this.containerCount = ByteBuffers.readLittleEndianUnsigned(data, 4, 2);
 
     Preconditions.checkState(
-        containerCount <= 8192, "Invalid container count: %s > 8,192 (max)", containerCount);
+        containerCount < MAX_CONTAINER_COUNT,

Review Comment:
   Yeah maybe worth a test that tests a bitmap with all the containers up to this limit



-- 
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 mutable Mumbling bitmap implementation [iceberg]

Posted by "rdblue (via GitHub)" <gi...@apache.org>.
rdblue commented on code in PR #18544:
URL: https://github.com/apache/iceberg/pull/18544#discussion_r4352591173


##########
core/src/main/java/org/apache/iceberg/mumbling/MumblingBitmap.java:
##########


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 mutable Mumbling bitmap implementation [iceberg]

Posted by "rdblue (via GitHub)" <gi...@apache.org>.
rdblue commented on code in PR #18544:
URL: https://github.com/apache/iceberg/pull/18544#discussion_r4352743062


##########
core/src/main/java/org/apache/iceberg/mumbling/MumblingBitmap.java:
##########
@@ -138,6 +160,282 @@ private int offset(int containerIndex) {
     return offsets[containerIndex];
   }
 
+  public MutableBitmap asMutable() {
+    return new Mutable(this);
+  }
+
+  /**
+   * A copy-on-write {@link MutableBitmap} implementation for Mumbling.
+   *
+   * <p>When a new bit position is set, an overlay is created for the position's container.
+   *
+   * <p>The initial buffer is not modified.
+   */
+  private static class Mutable implements MutableBitmap {
+    private final NavigableMap<Integer, Container> overlays = Maps.newTreeMap();
+    private final MumblingBitmap base;
+    private final int baseContainerCount;
+    private int cardinality = 0;
+
+    public Mutable(MumblingBitmap base) {
+      this.base = base;
+      this.baseContainerCount = base.descriptors().length;
+      this.cardinality = base.cardinality();
+    }
+
+    @Override
+    public int cardinality() {
+      return cardinality;
+    }
+
+    @Override
+    public boolean isSet(int pos) {
+      Container overlay = overlays.get(containerIndex(pos));
+      if (overlay != null) {
+        return overlay.isSet(posInContainer(pos));
+      }
+
+      return base.isSet(pos);
+    }
+
+    @Override
+    public boolean set(int pos) {
+      Preconditions.checkArgument(pos >= 0, "Cannot set invalid bit position: %s < 0", pos);
+      Preconditions.checkArgument(
+          pos < MAX_CARDINALITY, "Cannot set invalid bit position: %s (must be < 2,097,152)", pos);
+
+      int containerIndex = containerIndex(pos);
+      Container overlay = overlays.get(containerIndex);
+      if (overlay == null) {
+        if (containerIndex < baseContainerCount) {
+          overlay =
+              new Container(
+                  base.buffer(), base.offset(containerIndex), base.descriptor(containerIndex));
+        } else {
+          overlay = new Container();
+        }
+        overlays.put(containerIndex, overlay);
+      }
+
+      if (overlay.set(posInContainer(pos))) {
+        this.cardinality += 1;
+        return true;
+      }
+
+      return false;
+    }
+
+    @Override
+    public ByteBuffer buffer() {
+      int[] descriptorArray = descriptorArray();
+      int containersSize = sizeOfContainers(descriptorArray, 0, descriptorArray.length);
+      ByteBuffer descBuffer = PFOREncoding.encode(descriptorArray, descriptorArray.length);
+      int descriptorsSize = descBuffer.remaining();
+
+      ByteBuffer buffer = ByteBuffer.allocate(HEADER_SIZE + descriptorsSize + containersSize);
+      int currentPos = writeHeader(buffer, cardinality, descriptorArray.length);
+
+      buffer.put(HEADER_SIZE, descBuffer, descBuffer.position(), descriptorsSize);
+      currentPos += descriptorsSize;
+
+      int nextContainerIndex = 0;
+      for (Map.Entry<Integer, Container> entry : overlays.entrySet()) {
+        int containerIndex = entry.getKey();
+        currentPos +=
+            copyOriginalContainers(
+                descriptorArray, nextContainerIndex, containerIndex, buffer, currentPos);
+        currentPos += entry.getValue().writeTo(buffer, currentPos);
+        nextContainerIndex = containerIndex + 1;
+      }
+
+      copyOriginalContainers(
+          descriptorArray, nextContainerIndex, descriptorArray.length, buffer, currentPos);
+
+      return buffer;
+    }
+
+    private int[] descriptorArray() {
+      int[] baseDescriptors = base.descriptors();
+      int lastOverlayIndex = overlays.isEmpty() ? -1 : overlays.lastKey();
+      int numContainers = Math.max(lastOverlayIndex + 1, baseDescriptors.length);
+      int[] descriptors = new int[numContainers]; // filled with 0
+      System.arraycopy(baseDescriptors, 0, descriptors, 0, baseDescriptors.length);
+
+      for (Map.Entry<Integer, Container> entry : overlays.entrySet()) {
+        int containerIndex = entry.getKey();
+        int cardinality = entry.getValue().cardinality();
+        descriptors[containerIndex] = Math.min(cardinality, DENSE_CONTAINER_SIZE);
+      }
+
+      return descriptors;
+    }
+
+    private int sizeOfContainers(int[] descriptorArray, int startIndex, int endIndexExclusive) {
+      int size = 0;
+      for (int i = startIndex; i < endIndexExclusive; i += 1) {
+        size += descriptorArray[i];
+      }
+
+      return size;
+    }
+
+    private static int writeHeader(ByteBuffer buffer, int cardinality, int descriptorCount) {
+      ByteBuffers.writeByte(buffer, VERSION, 0);
+      ByteBuffers.writeLittleEndianUnsigned(buffer, cardinality, 1, 3);
+      ByteBuffers.writeLittleEndianUnsigned(buffer, descriptorCount, 4, 2);
+
+      return HEADER_SIZE;
+    }
+
+    private int copyOriginalContainers(
+        int[] descriptorArray,
+        int startIndex,
+        int endIndexExclusive,
+        ByteBuffer buffer,
+        int currentPos) {
+      if (startIndex < baseContainerCount && startIndex < endIndexExclusive) {
+        int offset = base.offset(startIndex);
+        int sizeToCopy = sizeOfContainers(descriptorArray, startIndex, endIndexExclusive);
+        if (sizeToCopy > 0) {
+          buffer.put(currentPos, base.buffer(), offset, sizeToCopy);
+        }
+
+        return sizeToCopy;
+      }
+
+      return 0;
+    }
+  }
+
+  private static class Container {
+    private byte[] dense = null;
+    private byte[] sparse = null;
+    private int cardinality = 0;
+
+    private Container() {
+      this.sparse = new byte[DENSE_CONTAINER_SIZE];
+    }
+
+    private Container(ByteBuffer buffer, int offset, int length) {
+      byte[] bytes = new byte[DENSE_CONTAINER_SIZE];
+      buffer.get(offset, bytes, 0, length);
+
+      if (isDense(length)) {
+        this.dense = bytes;
+        this.cardinality = denseCardinality(dense);
+      } else {
+        this.sparse = bytes;
+        this.cardinality = length;
+      }
+    }
+
+    int cardinality() {
+      return cardinality;
+    }
+
+    private boolean isSet(int posInContainer) {
+      if (cardinality < 32) {
+        // sparse
+        for (int i = 0; i < cardinality; i += 1) {
+          if ((sparse[i] & 0xFF) == posInContainer) {
+            return true;
+          }
+        }
+
+        return false;
+      } else {
+        // dense
+        int bitShift = denseBitShift(posInContainer);
+        return ((dense[denseByteIndex(posInContainer)] >>> bitShift) & 0b1) == 0b1;
+      }
+    }
+
+    private boolean set(int posInContainer) {
+      if (setInternal(posInContainer)) {
+        this.cardinality += 1;
+        return true;
+      }
+
+      return false;
+    }
+
+    int writeTo(ByteBuffer buffer, int offset) {
+      if (cardinality < DENSE_CONTAINER_SIZE) {
+        buffer.put(offset, sparse, 0, cardinality);
+        return cardinality;
+      } else {
+        buffer.put(offset, dense, 0, dense.length);
+        return dense.length;
+      }
+    }
+
+    private boolean setInternal(int posInContainer) {
+      if (cardinality < 31) {
+        return sparseSet(sparse, cardinality, posInContainer);
+      } else if (cardinality > 31) {
+        return denseSet(dense, posInContainer);
+      } else {
+        // convert to dense, reuse converted buffer if it is present
+        if (dense == null) {
+          this.dense = convertToDense(sparse, cardinality);
+        }
+
+        if (denseSet(dense, posInContainer)) {
+          this.sparse = null;
+          return true;
+        }
+
+        // leave the converted dense array for next set attempt
+        return false;
+      }
+    }
+
+    private static boolean sparseSet(byte[] bytes, int length, int posInContainer) {
+      byte nextInsert = (byte) posInContainer;
+      for (int i = 0; i < length; i += 1) {
+        if (nextInsert == bytes[i]) {
+          return false; // already set
+        } else if ((nextInsert & 0xFF) < (bytes[i] & 0xFF)) {
+          byte replaced = bytes[i];
+          bytes[i] = nextInsert;
+          nextInsert = replaced;
+        }
+      }
+
+      bytes[length] = nextInsert;
+      return true;
+    }
+
+    private static byte[] convertToDense(byte[] sparse, int cardinality) {
+      byte[] dense = new byte[32];
+      for (int i = 0; i < cardinality; i += 1) {
+        denseSet(dense, (sparse[i] & 0xFF));
+      }
+
+      return dense;
+    }
+
+    private static boolean denseSet(byte[] bytes, int posInContainer) {
+      int byteIndex = denseByteIndex(posInContainer);
+      byte bit = (byte) (0b1 << denseBitShift(posInContainer));
+      if ((bytes[byteIndex] & bit) != bit) {
+        bytes[byteIndex] |= bit;
+        return true;
+      }
+
+      return false;
+    }
+
+    private static int denseCardinality(byte[] bytes) {
+      int cardinality = 0;
+      for (int i = 0; i < bytes.length; i += 1) {
+        cardinality += Integer.bitCount(bytes[i]);

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 mutable Mumbling bitmap implementation [iceberg]

Posted by "rdblue (via GitHub)" <gi...@apache.org>.
rdblue commented on code in PR #18544:
URL: https://github.com/apache/iceberg/pull/18544#discussion_r4365103936


##########
api/src/test/java/org/apache/iceberg/util/TestByteBuffers.java:
##########
@@ -36,9 +37,85 @@ public void testRead2ByteUnsigned() {
     assertThat(ByteBuffers.readLittleEndianUnsigned(buffer, 0, 2)).isEqualTo(65535);
   }
 
+  @Test
+  public void testRead2ByteLittleEndian() {

Review Comment:
   Good catch. Adding tests.



-- 
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 mutable Mumbling bitmap implementation [iceberg]

Posted by "rdblue (via GitHub)" <gi...@apache.org>.
rdblue commented on code in PR #18544:
URL: https://github.com/apache/iceberg/pull/18544#discussion_r4352690283


##########
core/src/main/java/org/apache/iceberg/mumbling/MumblingBitmap.java:
##########
@@ -138,6 +160,282 @@ private int offset(int containerIndex) {
     return offsets[containerIndex];
   }
 
+  public MutableBitmap asMutable() {
+    return new Mutable(this);
+  }
+
+  /**
+   * A copy-on-write {@link MutableBitmap} implementation for Mumbling.
+   *
+   * <p>When a new bit position is set, an overlay is created for the position's container.
+   *
+   * <p>The initial buffer is not modified.
+   */
+  private static class Mutable implements MutableBitmap {
+    private final NavigableMap<Integer, Container> overlays = Maps.newTreeMap();
+    private final MumblingBitmap base;
+    private final int baseContainerCount;
+    private int cardinality = 0;
+
+    public Mutable(MumblingBitmap base) {
+      this.base = base;
+      this.baseContainerCount = base.descriptors().length;
+      this.cardinality = base.cardinality();
+    }
+
+    @Override
+    public int cardinality() {
+      return cardinality;
+    }
+
+    @Override
+    public boolean isSet(int pos) {
+      Container overlay = overlays.get(containerIndex(pos));
+      if (overlay != null) {
+        return overlay.isSet(posInContainer(pos));
+      }
+
+      return base.isSet(pos);
+    }
+
+    @Override
+    public boolean set(int pos) {
+      Preconditions.checkArgument(pos >= 0, "Cannot set invalid bit position: %s < 0", pos);
+      Preconditions.checkArgument(
+          pos < MAX_CARDINALITY, "Cannot set invalid bit position: %s (must be < 2,097,152)", pos);
+
+      int containerIndex = containerIndex(pos);
+      Container overlay = overlays.get(containerIndex);
+      if (overlay == null) {
+        if (containerIndex < baseContainerCount) {
+          overlay =
+              new Container(
+                  base.buffer(), base.offset(containerIndex), base.descriptor(containerIndex));
+        } else {
+          overlay = new Container();
+        }
+        overlays.put(containerIndex, overlay);
+      }
+
+      if (overlay.set(posInContainer(pos))) {
+        this.cardinality += 1;
+        return true;
+      }
+
+      return false;
+    }
+
+    @Override
+    public ByteBuffer buffer() {
+      int[] descriptorArray = descriptorArray();
+      int containersSize = sizeOfContainers(descriptorArray, 0, descriptorArray.length);
+      ByteBuffer descBuffer = PFOREncoding.encode(descriptorArray, descriptorArray.length);
+      int descriptorsSize = descBuffer.remaining();
+
+      ByteBuffer buffer = ByteBuffer.allocate(HEADER_SIZE + descriptorsSize + containersSize);
+      int currentPos = writeHeader(buffer, cardinality, descriptorArray.length);
+
+      buffer.put(HEADER_SIZE, descBuffer, descBuffer.position(), descriptorsSize);
+      currentPos += descriptorsSize;
+
+      int nextContainerIndex = 0;
+      for (Map.Entry<Integer, Container> entry : overlays.entrySet()) {
+        int containerIndex = entry.getKey();
+        currentPos +=
+            copyOriginalContainers(
+                descriptorArray, nextContainerIndex, containerIndex, buffer, currentPos);
+        currentPos += entry.getValue().writeTo(buffer, currentPos);
+        nextContainerIndex = containerIndex + 1;
+      }
+
+      copyOriginalContainers(
+          descriptorArray, nextContainerIndex, descriptorArray.length, buffer, currentPos);
+
+      return buffer;
+    }
+
+    private int[] descriptorArray() {
+      int[] baseDescriptors = base.descriptors();
+      int lastOverlayIndex = overlays.isEmpty() ? -1 : overlays.lastKey();
+      int numContainers = Math.max(lastOverlayIndex + 1, baseDescriptors.length);
+      int[] descriptors = new int[numContainers]; // filled with 0
+      System.arraycopy(baseDescriptors, 0, descriptors, 0, baseDescriptors.length);
+
+      for (Map.Entry<Integer, Container> entry : overlays.entrySet()) {
+        int containerIndex = entry.getKey();
+        int cardinality = entry.getValue().cardinality();
+        descriptors[containerIndex] = Math.min(cardinality, DENSE_CONTAINER_SIZE);
+      }
+
+      return descriptors;
+    }
+
+    private int sizeOfContainers(int[] descriptorArray, int startIndex, int endIndexExclusive) {
+      int size = 0;
+      for (int i = startIndex; i < endIndexExclusive; i += 1) {
+        size += descriptorArray[i];
+      }
+
+      return size;
+    }
+
+    private static int writeHeader(ByteBuffer buffer, int cardinality, int descriptorCount) {
+      ByteBuffers.writeByte(buffer, VERSION, 0);
+      ByteBuffers.writeLittleEndianUnsigned(buffer, cardinality, 1, 3);
+      ByteBuffers.writeLittleEndianUnsigned(buffer, descriptorCount, 4, 2);
+
+      return HEADER_SIZE;
+    }
+
+    private int copyOriginalContainers(
+        int[] descriptorArray,
+        int startIndex,
+        int endIndexExclusive,
+        ByteBuffer buffer,
+        int currentPos) {
+      if (startIndex < baseContainerCount && startIndex < endIndexExclusive) {
+        int offset = base.offset(startIndex);
+        int sizeToCopy = sizeOfContainers(descriptorArray, startIndex, endIndexExclusive);
+        if (sizeToCopy > 0) {
+          buffer.put(currentPos, base.buffer(), offset, sizeToCopy);
+        }
+
+        return sizeToCopy;
+      }
+
+      return 0;
+    }
+  }
+
+  private static class Container {
+    private byte[] dense = null;
+    private byte[] sparse = null;
+    private int cardinality = 0;
+
+    private Container() {
+      this.sparse = new byte[DENSE_CONTAINER_SIZE];
+    }
+
+    private Container(ByteBuffer buffer, int offset, int length) {
+      byte[] bytes = new byte[DENSE_CONTAINER_SIZE];
+      buffer.get(offset, bytes, 0, length);

Review Comment:
   `0b0010_0000` is correct for a dense descriptor. It is always 32, the length of the dense container. Dense descriptors may not be greater than `DENSE_CONTAINER_SIZE`. The descriptor is always the length of the container.
   
   I think that `length` is better than `descriptor` here because it is used to copy `N` bytes directly. It makes more sense to copy `N=length` bytes and then check if that length indicates a dense container, than to copy `N=descriptor` bytes and then check if the descriptor indicates a dense container.



-- 
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 mutable Mumbling bitmap implementation [iceberg]

Posted by "rdblue (via GitHub)" <gi...@apache.org>.
rdblue commented on code in PR #18544:
URL: https://github.com/apache/iceberg/pull/18544#discussion_r4352617941


##########
core/src/main/java/org/apache/iceberg/mumbling/MumblingBitmap.java:
##########
@@ -138,6 +160,282 @@ private int offset(int containerIndex) {
     return offsets[containerIndex];
   }
 
+  public MutableBitmap asMutable() {
+    return new Mutable(this);
+  }
+
+  /**
+   * A copy-on-write {@link MutableBitmap} implementation for Mumbling.
+   *
+   * <p>When a new bit position is set, an overlay is created for the position's container.
+   *
+   * <p>The initial buffer is not modified.
+   */
+  private static class Mutable implements MutableBitmap {
+    private final NavigableMap<Integer, Container> overlays = Maps.newTreeMap();
+    private final MumblingBitmap base;
+    private final int baseContainerCount;
+    private int cardinality = 0;
+
+    public Mutable(MumblingBitmap base) {
+      this.base = base;
+      this.baseContainerCount = base.descriptors().length;
+      this.cardinality = base.cardinality();
+    }
+
+    @Override
+    public int cardinality() {
+      return cardinality;
+    }
+
+    @Override
+    public boolean isSet(int pos) {
+      Container overlay = overlays.get(containerIndex(pos));
+      if (overlay != null) {
+        return overlay.isSet(posInContainer(pos));
+      }
+
+      return base.isSet(pos);
+    }
+
+    @Override
+    public boolean set(int pos) {
+      Preconditions.checkArgument(pos >= 0, "Cannot set invalid bit position: %s < 0", pos);
+      Preconditions.checkArgument(
+          pos < MAX_CARDINALITY, "Cannot set invalid bit position: %s (must be < 2,097,152)", pos);
+
+      int containerIndex = containerIndex(pos);
+      Container overlay = overlays.get(containerIndex);
+      if (overlay == null) {
+        if (containerIndex < baseContainerCount) {
+          overlay =
+              new Container(
+                  base.buffer(), base.offset(containerIndex), base.descriptor(containerIndex));
+        } else {
+          overlay = new Container();
+        }
+        overlays.put(containerIndex, overlay);
+      }
+
+      if (overlay.set(posInContainer(pos))) {
+        this.cardinality += 1;
+        return true;
+      }
+
+      return false;
+    }
+
+    @Override
+    public ByteBuffer buffer() {
+      int[] descriptorArray = descriptorArray();
+      int containersSize = sizeOfContainers(descriptorArray, 0, descriptorArray.length);
+      ByteBuffer descBuffer = PFOREncoding.encode(descriptorArray, descriptorArray.length);
+      int descriptorsSize = descBuffer.remaining();
+
+      ByteBuffer buffer = ByteBuffer.allocate(HEADER_SIZE + descriptorsSize + containersSize);
+      int currentPos = writeHeader(buffer, cardinality, descriptorArray.length);
+
+      buffer.put(HEADER_SIZE, descBuffer, descBuffer.position(), descriptorsSize);
+      currentPos += descriptorsSize;
+
+      int nextContainerIndex = 0;
+      for (Map.Entry<Integer, Container> entry : overlays.entrySet()) {
+        int containerIndex = entry.getKey();
+        currentPos +=
+            copyOriginalContainers(
+                descriptorArray, nextContainerIndex, containerIndex, buffer, currentPos);
+        currentPos += entry.getValue().writeTo(buffer, currentPos);
+        nextContainerIndex = containerIndex + 1;
+      }
+
+      copyOriginalContainers(
+          descriptorArray, nextContainerIndex, descriptorArray.length, buffer, currentPos);
+
+      return buffer;
+    }
+
+    private int[] descriptorArray() {
+      int[] baseDescriptors = base.descriptors();
+      int lastOverlayIndex = overlays.isEmpty() ? -1 : overlays.lastKey();
+      int numContainers = Math.max(lastOverlayIndex + 1, baseDescriptors.length);

Review Comment:
   No, the overlay index could be any index > 0 and <= 8192.



-- 
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 mutable Mumbling bitmap implementation [iceberg]

Posted by "rdblue (via GitHub)" <gi...@apache.org>.
rdblue commented on PR #18544:
URL: https://github.com/apache/iceberg/pull/18544#issuecomment-6350991252

   > The current approach of making the bitmap mutable is fine, though we've used builders in a lot of places in the project and I would've thought we'd do the same here.
   
   I didn't use a builder because I thought that we would want a mutable structure that can also function as a bitmap for reusing this later. As long as the implementation is almost entirely the same, it makes sense to me to use a bitmap API (`set`/`isSet`/`cardinality`) because it can be reused more. With a builder API it would be odd to check a builder if a particular bit is set, and setting a bit should return the builder for chaining instead of whether the bit was set (or was already set).
   
   > CoW is advantageous if we generally expect to modify a few containers and this optimization is well worth it for the general case, since that's when we avoid decoding the untouched ones.
   
   I think this matches our expectation that deletes will generally be sparse. The worst case is random deletes, where you're not targeting files that are clustered together. If you are targeting files that are clustered (say by date partition from writes) then deletes will cluster together and the copy-on-write strategy works better. But even for random deletes, a 1% delete rate means about 1 in 100 files will be affected, which touches about 1 container in 3.
   
   For a 50,000 entry file, there are about 200 containers. If a third of those containers is affected, that is 70 containers or about 2.2k allocated in overlay buffers. The alternative of maintaining a dense bitset is about 49k of memory. Plus you'd have to translate the existing entries by calling `set` a few thousand times. Maybe it isn't a big deal, but this cost adds up with the number of manifests as well. 100 manifests would cost about 5 MB, rather than 220k.


-- 
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 mutable Mumbling bitmap implementation [iceberg]

Posted by "amogh-jahagirdar (via GitHub)" <gi...@apache.org>.
amogh-jahagirdar commented on code in PR #18544:
URL: https://github.com/apache/iceberg/pull/18544#discussion_r4303484296


##########
core/src/main/java/org/apache/iceberg/mumbling/MutableBitmap.java:
##########
@@ -0,0 +1,26 @@
+/*
+ * 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 org.apache.iceberg.ManifestBitmap;
+
+/** Mutation methods for ManifestBitmap. */
+public interface MutableBitmap extends ManifestBitmap {

Review Comment:
   Commented above, with a builder I think we wouldn't need a public MutableBitmap interface. The builder can hold the mutable state and build() just returns a ManifestBitmap, so the mutable type stays internal to org.apache.iceberg.mumbling.
   
   



-- 
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 mutable Mumbling bitmap implementation [iceberg]

Posted by "rdblue (via GitHub)" <gi...@apache.org>.
rdblue commented on code in PR #18544:
URL: https://github.com/apache/iceberg/pull/18544#discussion_r4353083067


##########
core/src/main/java/org/apache/iceberg/mumbling/MutableBitmap.java:
##########
@@ -0,0 +1,26 @@
+/*
+ * 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 org.apache.iceberg.ManifestBitmap;
+
+/** Mutation methods for ManifestBitmap. */
+public interface MutableBitmap extends ManifestBitmap {

Review Comment:
   `MutableManifestBitmap` seems a bit too long. I see wanting to make it mirror the other interface and considered adding it as `ManifestBitmap.Mutable`, but I thought that was long and more awkward. The builder gets around this, but I think we should choose to use a builder or a mutable bitmap independent of the naming decision.



-- 
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 mutable Mumbling bitmap implementation [iceberg]

Posted by "rdblue (via GitHub)" <gi...@apache.org>.
rdblue commented on code in PR #18544:
URL: https://github.com/apache/iceberg/pull/18544#discussion_r4352648412


##########
core/src/main/java/org/apache/iceberg/mumbling/MumblingBitmap.java:
##########
@@ -138,6 +160,282 @@ private int offset(int containerIndex) {
     return offsets[containerIndex];
   }
 
+  public MutableBitmap asMutable() {
+    return new Mutable(this);
+  }
+
+  /**
+   * A copy-on-write {@link MutableBitmap} implementation for Mumbling.
+   *
+   * <p>When a new bit position is set, an overlay is created for the position's container.
+   *
+   * <p>The initial buffer is not modified.
+   */
+  private static class Mutable implements MutableBitmap {
+    private final NavigableMap<Integer, Container> overlays = Maps.newTreeMap();
+    private final MumblingBitmap base;
+    private final int baseContainerCount;
+    private int cardinality = 0;
+
+    public Mutable(MumblingBitmap base) {
+      this.base = base;
+      this.baseContainerCount = base.descriptors().length;
+      this.cardinality = base.cardinality();
+    }
+
+    @Override
+    public int cardinality() {
+      return cardinality;
+    }
+
+    @Override
+    public boolean isSet(int pos) {
+      Container overlay = overlays.get(containerIndex(pos));
+      if (overlay != null) {
+        return overlay.isSet(posInContainer(pos));
+      }
+
+      return base.isSet(pos);
+    }
+
+    @Override
+    public boolean set(int pos) {
+      Preconditions.checkArgument(pos >= 0, "Cannot set invalid bit position: %s < 0", pos);
+      Preconditions.checkArgument(
+          pos < MAX_CARDINALITY, "Cannot set invalid bit position: %s (must be < 2,097,152)", pos);
+
+      int containerIndex = containerIndex(pos);
+      Container overlay = overlays.get(containerIndex);
+      if (overlay == null) {
+        if (containerIndex < baseContainerCount) {
+          overlay =
+              new Container(
+                  base.buffer(), base.offset(containerIndex), base.descriptor(containerIndex));
+        } else {
+          overlay = new Container();
+        }
+        overlays.put(containerIndex, overlay);
+      }
+
+      if (overlay.set(posInContainer(pos))) {
+        this.cardinality += 1;
+        return true;
+      }
+
+      return false;
+    }
+
+    @Override
+    public ByteBuffer buffer() {
+      int[] descriptorArray = descriptorArray();
+      int containersSize = sizeOfContainers(descriptorArray, 0, descriptorArray.length);
+      ByteBuffer descBuffer = PFOREncoding.encode(descriptorArray, descriptorArray.length);
+      int descriptorsSize = descBuffer.remaining();
+
+      ByteBuffer buffer = ByteBuffer.allocate(HEADER_SIZE + descriptorsSize + containersSize);
+      int currentPos = writeHeader(buffer, cardinality, descriptorArray.length);
+
+      buffer.put(HEADER_SIZE, descBuffer, descBuffer.position(), descriptorsSize);
+      currentPos += descriptorsSize;
+
+      int nextContainerIndex = 0;
+      for (Map.Entry<Integer, Container> entry : overlays.entrySet()) {
+        int containerIndex = entry.getKey();
+        currentPos +=
+            copyOriginalContainers(
+                descriptorArray, nextContainerIndex, containerIndex, buffer, currentPos);
+        currentPos += entry.getValue().writeTo(buffer, currentPos);
+        nextContainerIndex = containerIndex + 1;
+      }
+
+      copyOriginalContainers(
+          descriptorArray, nextContainerIndex, descriptorArray.length, buffer, currentPos);
+
+      return buffer;
+    }
+
+    private int[] descriptorArray() {
+      int[] baseDescriptors = base.descriptors();
+      int lastOverlayIndex = overlays.isEmpty() ? -1 : overlays.lastKey();
+      int numContainers = Math.max(lastOverlayIndex + 1, baseDescriptors.length);
+      int[] descriptors = new int[numContainers]; // filled with 0
+      System.arraycopy(baseDescriptors, 0, descriptors, 0, baseDescriptors.length);
+
+      for (Map.Entry<Integer, Container> entry : overlays.entrySet()) {
+        int containerIndex = entry.getKey();
+        int cardinality = entry.getValue().cardinality();
+        descriptors[containerIndex] = Math.min(cardinality, DENSE_CONTAINER_SIZE);
+      }
+
+      return descriptors;
+    }
+
+    private int sizeOfContainers(int[] descriptorArray, int startIndex, int endIndexExclusive) {
+      int size = 0;
+      for (int i = startIndex; i < endIndexExclusive; i += 1) {
+        size += descriptorArray[i];
+      }
+
+      return size;
+    }
+
+    private static int writeHeader(ByteBuffer buffer, int cardinality, int descriptorCount) {
+      ByteBuffers.writeByte(buffer, VERSION, 0);
+      ByteBuffers.writeLittleEndianUnsigned(buffer, cardinality, 1, 3);
+      ByteBuffers.writeLittleEndianUnsigned(buffer, descriptorCount, 4, 2);
+
+      return HEADER_SIZE;
+    }
+
+    private int copyOriginalContainers(
+        int[] descriptorArray,
+        int startIndex,
+        int endIndexExclusive,
+        ByteBuffer buffer,
+        int currentPos) {
+      if (startIndex < baseContainerCount && startIndex < endIndexExclusive) {
+        int offset = base.offset(startIndex);
+        int sizeToCopy = sizeOfContainers(descriptorArray, startIndex, endIndexExclusive);
+        if (sizeToCopy > 0) {
+          buffer.put(currentPos, base.buffer(), offset, sizeToCopy);
+        }
+
+        return sizeToCopy;
+      }
+
+      return 0;
+    }
+  }
+
+  private static class Container {
+    private byte[] dense = null;
+    private byte[] sparse = null;
+    private int cardinality = 0;
+
+    private Container() {
+      this.sparse = new byte[DENSE_CONTAINER_SIZE];
+    }
+
+    private Container(ByteBuffer buffer, int offset, int length) {
+      byte[] bytes = new byte[DENSE_CONTAINER_SIZE];
+      buffer.get(offset, bytes, 0, length);
+
+      if (isDense(length)) {

Review Comment:
   The descriptor is passed as `length`. In the current spec, the descriptor is the length of the container. That's also the cardinality for sparse containers, but dense containers may have a higher cardinality. That's what's happening here: we use length to copy the bytes into a 32-byte buffer (always correct) and if the container is sparse, we set the cardinality from it as well.



-- 
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 mutable Mumbling bitmap implementation [iceberg]

Posted by "rdblue (via GitHub)" <gi...@apache.org>.
rdblue commented on code in PR #18544:
URL: https://github.com/apache/iceberg/pull/18544#discussion_r4365179720


##########
core/src/test/java/org/apache/iceberg/mumbling/TestMumblingBitmap.java:
##########
@@ -27,9 +27,62 @@
 
 import java.nio.ByteBuffer;
 import java.util.Arrays;
+import java.util.Random;
 import org.junit.jupiter.api.Test;
 
 class TestMumblingBitmap {
+  private static final int HEADER_SIZE = 6;
+  private static final byte[] DENSE_CONTAINER = new byte[32];
+
+  static {
+    DENSE_CONTAINER[1] = (byte) 0xFF;
+    DENSE_CONTAINER[3] = (byte) 0xFF;
+    DENSE_CONTAINER[5] = (byte) 0xFF;
+    DENSE_CONTAINER[7] = (byte) 0xFF;
+  }
+
+  private static final MumblingBitmap MUTABLE_TEST_BASE =
+      bitmap(sparse(0), dense(DENSE_CONTAINER), sparse(255));
+
+  @Test
+  public void testInvalidVersion() {

Review Comment:
   Added tests for descriptors 33, 64, and 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