emkornfield commented on code in PR #16518: URL: https://github.com/apache/iceberg/pull/16518#discussion_r3377044535
########## format/mumbling-spec.md: ########## @@ -0,0 +1,315 @@ +--- +title: "Mumbling Bitmap Spec" +--- +<!-- + - 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. + --> + +# Mumbling Bitmap Spec + +This is a specification for the Mumbling compressed bitmap format designed for +use cases with bounded total size, like a deletion vector. This is based on +[Roaring Bitmap][roaring]. + +This spec is for version 1. + +[roaring]: https://roaringbitmap.org/ + + +## Overview + +Mumbling bitmaps are based on the same idea as Roaring bitmaps: a bitmap is +divided into fixed-size (256 bit) regions, called _containers_. Each container +is either _sparse_ to store offsets (0-255) or _dense_ to store a bit set. The +main difference from Roaring is that Mumbling bitmaps use a smaller scale where +each container is at most 32 bytes, and are limited to at most 2,097,152 +values. + +Containers are tracked by an array of descriptor bytes, one per container. The +position of the descriptor byte in the array encodes the most significant bits +of the positions stored in its corresponding container (the _key_ in Roaring +bitmap). The descriptor encodes the container size for sparse containers (0-31 +values), or that a container is dense (32). Because the format uses a +descriptor array instead of keys and offsets, descriptor bytes are stored +as a PFOR-encoded array. + + +## Design choices + +Unlike Roaring, this format uses a descriptor array instead of storing a key, +cardinality, and offset for each container. + +The Iceberg use case is for small, embedded deletion vectors. These vectors +will be small, likely less than 100,000 entries. But, limiting the +per-container overhead by using a single byte for the key (256 containers) +would be too limiting (only 65,536 total entries). As a result, this would +require 2-byte keys and 2-byte offsets (8192 containers * 32 bytes / +container). + +The descriptor array avoids 4 bytes of overhead for each 32-byte container. The +key is implicit and is the offset into the descriptor array. Descriptors encode +the length of a container instead of its offset, requiring only one byte. + +The first trade-off of this approach is that each descriptor must be present, Review Comment: It might be good to repeat this part in the format, I was originally initially confused about this (i.e. format should describe min/max length of the array. -- 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: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
