emkornfield commented on code in PR #11238: URL: https://github.com/apache/iceberg/pull/11238#discussion_r1796430758
########## format/puffin-spec.md: ########## @@ -123,6 +123,54 @@ The blob metadata for this blob may include following properties: - `ndv`: estimate of number of distinct values, derived from the sketch. +#### `delete-vector-v1` blob type + +A serialized delete vector (bitmap) that represents the positions of rows in a +file that are deleted. A set bit at position P indicates that the row at +position P is deleted. + +The vector supports positive 64-bit positions (the most significant bit must be +0), but is optimized for cases where most positions fit in 32 bits by using a +collection of 32-bit Roaring bitmaps. 64-bit positions are divided into a +32-bit "key" using the most significant 4 bytes and a 32-bit sub-position using +the least significant 4 bytes. For each key in the set of positions, a 32-bit +Roaring bitmap is maintained to store a set of 32-bit sub-positions for that +key. + +To test whether a certain position is set, its most significant 4 bytes (the +key) are used to find a 32-bit bitmap and the least significant 4 bytes (the +sub-position) are tested for inclusion in the bitmap. If a bitmap is not found +for the key, then it is not set. + +The serialized blob contains: +* The length of the vector and magic bytes stored as 4 bytes, big-endian +* A 4-byte magic sequence, `D1 D3 39 64` +* The vector, serialized as described below +* A CRC-32 checksum of the serialized vector as 4 bytes, big-endian + +The position vector is serialized using the Roaring bitmap +["portable" format][roaring-bitmap-portable-serialization]. This representation +consists of: + +* The number of 32-bit Roaring bitmaps, serialized as 8 bytes, little-endian +* For each 32-bit Roaring bitmap, ordered by unsigned comparison of the 32-bit keys: + - The key stored as 4 bytes, little-endian + - A [32-bit Roaring bitmap][roaring-bitmap-general-layout] Review Comment: I might be misunderstanding the layout, and it is enough of the edge case for this use-case that it doesn't matter but suppose I have 3 bitmaps (e.g. prefix keys 0x00, 0x01, 0x02, which implies at least an 8 row Billion data row file?), it appears one couldn't skip to a 0x01 bitmap without first reading the 0x00 (i.e. don't quite get how this could be random access without loading the entire data-structure)? If a the layout was instead `<number of prefixes><list of (prefix, bitmap start offset)><bitmap data>` one could randomly seek to the bitmap of interest without parsing preceding ones. Again given the edge case of having > 4B data files I think this point is mostly theoretical. I guess the alternative again which is worth discussing is putting an upper bound of `UINT32_MAX` rows on data files which would allow one just use the 32-bit roaring bitmap. Maybe famous last words but a 4 Billion row iceberg data file should be enough for anyone :) -- 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-unsubscr...@iceberg.apache.org For queries about this service, please contact Infrastructure at: us...@infra.apache.org --------------------------------------------------------------------- To unsubscribe, e-mail: issues-unsubscr...@iceberg.apache.org For additional commands, e-mail: issues-h...@iceberg.apache.org
