Fokko commented on code in PR #16518: URL: https://github.com/apache/iceberg/pull/16518#discussion_r3286971565
########## format/mumbling-spec.md: ########## @@ -0,0 +1,316 @@ +--- +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, +even for 0-length (empty) containers. And because an empty state is needed, +descriptors cannot encode the container cardinality (up to 256). PFOR encoding +is used to reduce this overhead. + +The second trade-off is that offsets are not directly stored. However, offsets +can be computed from the relatively small descriptor array and finding the +descriptor for a key uses direct array indexing. + +An alternative to the descriptor array is to store the offsets, and use the +difference between offsets to find container length. This approach was not +chosen because array encoding would be worse (values are increasing), and the +remaining descriptor bits cannot be used. + + +## Format + +A Mumbling bitmap consists of 3 sections: + +* Header +* Descriptor array +* Containers + +Throughout the foramt, integers are unsigned and stored as little endian. Review Comment: ```suggestion Throughout the format, integers are unsigned and stored as little endian. ``` -- 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]
