Jackie-Jiang commented on code in PR #19587: URL: https://github.com/apache/pinot/pull/19587#discussion_r4174966277
########## pinot-common/src/main/java/org/apache/pinot/common/utils/RoaringBitmapUnion.java: ########## @@ -0,0 +1,229 @@ +/** + * 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.pinot.common.utils; + +import java.io.IOException; +import java.nio.ByteBuffer; +import java.util.Objects; +import org.roaringbitmap.ContainerPointer; +import org.roaringbitmap.RoaringBitmap; + + +/// Interim stand-in for `org.roaringbitmap.RoaringBitmapUnion`, which is proposed to RoaringBitmap for +/// apache/pinot#19587 and not released yet. It has the same name and the same methods, so that once a RoaringBitmap +/// release ships the class the swap is mechanical: +/// +/// - change the import at the call sites to `org.roaringbitmap.RoaringBitmapUnion`, +/// - make [RoaringBitmapUtils#deserializeToUnion] call `RoaringBitmapUnion.takeOwnership(deserialize(bytes))`, +/// - delete this class, [MutableRoaringBitmapUnion] and their two tests (the library tests its own classes). +/// +/// `RoaringBitmapUnionTest` fails as soon as the library class is on the classpath, as a reminder. This class is +/// internal to Pinot and goes away with the swap; code outside this repository should not depend on it. +/// +/// An incremental union accumulator: it folds bitmaps that arrive over time into one bitmap with RoaringBitmap's lazy +/// union, which skips cardinality maintenance and keeps overlapping containers in a form that makes further unions +/// cheap, and it repairs the result only when it is read. Callers only ever observe valid bitmaps: +/// +/// - [#add(RoaringBitmap)] never modifies or retains its argument. +/// - [#get()] returns the accumulated bitmap without copying. The union never modifies that instance again: its next +/// mutating call first copies it, so the returned bitmap stays valid. Callers must treat it as read-only while they +/// still intend to use the union. +/// - [#take()] transfers ownership of the accumulated bitmap and leaves the union empty. +/// +/// Callers should code against the library contract, which is stricter than this class in two places: a bitmap +/// passed to [#takeOwnership(RoaringBitmap)] is relinquished for good, and it must be a plain [RoaringBitmap], not an +/// instance of a subclass. +/// +/// Differences from the library class: +/// +/// - The lazy primitives of [RoaringBitmap] are `protected`, so the accumulated state is a private subclass that +/// reaches them through inheritance. The bitmaps handed out by [#get()] and [#take()] are instances of that +/// subclass; it adds no state and overrides nothing. +/// - [#takeOwnership(RoaringBitmap)] adopts without copying only a bitmap that a union handed out; any other bitmap +/// is copied. Pinot never needs more: bitmaps are deserialized straight into a union with +/// [RoaringBitmapUtils#deserializeToUnion], and copies are made by adding to an empty union. +/// - [#add(int)] repairs pending lazy state before inserting, because inserting into a lazy container needs the +/// library's internals, and it does not re-encode a run container that received the value. A given accumulator +/// receives either bitmaps or single values in Pinot, never both. +/// - The released lazy union only pays off once containers are dense: while they are small arrays it allocates a new +/// container per union where the eager union merges in place, and it inserts container keys that are new to the +/// accumulator one at a time, which is quadratic when an input brings many of them. So an input is unioned eagerly +/// while the accumulator holds few values per container (hashed values spread over many containers stay there for +/// good) or when the input would insert many new keys, and lazily otherwise. The library class does not need +/// this: its lazy union merges small arrays in place and new keys in one pass. +/// +/// Instances are not thread-safe. +public final class RoaringBitmapUnion { + // The lazy union starts to pay off when containers hold more values than the library's lazy array bound: past it + // they are kept as bitmaps whose unions skip cardinality maintenance, below it they are arrays that the lazy union + // copies on every union + private static final int MIN_VALUES_PER_CONTAINER_FOR_LAZY_UNION = 1024; + // An input that would insert more new keys than this between existing ones is unioned eagerly. Each insert shifts + // the accumulator's key and container arrays, and the eager union's single merge pass costs about as much as a + // few of those shifts. + private static final int MAX_NEW_KEYS_FOR_LAZY_UNION = 4; + + // The accumulated bitmap. Never null. + private LazyBitmap _bitmap; + // Whether the bitmap holds lazy state that must be repaired before it is read + private boolean _dirty; + // Whether an alias returned by get() is outstanding and must not be mutated + private boolean _published; + // Number of values added so far, counting duplicates: an upper bound of the cardinality that is known without + // repairing, used to estimate how dense the containers are + private long _numValuesAdded; + + /// Creates an empty union. + public RoaringBitmapUnion() { + _bitmap = new LazyBitmap(); + } + + private RoaringBitmapUnion(LazyBitmap adopted) { + _bitmap = adopted; + // Adopted state is normalized on the first read, like the library class does + _dirty = true; + _numValuesAdded = adopted.getLongCardinality(); + } + + /// Creates a union whose initial state is the given bitmap. The caller relinquishes the instance: it must not be + /// used again except through the union. + public static RoaringBitmapUnion takeOwnership(RoaringBitmap bitmap) { + Objects.requireNonNull(bitmap, "bitmap"); + if (bitmap instanceof LazyBitmap) { + return new RoaringBitmapUnion((LazyBitmap) bitmap); + } + LazyBitmap copy = new LazyBitmap(); + copy.lazyOr(bitmap); + return new RoaringBitmapUnion(copy); + } + + /// Deserializes a bitmap straight into a union that owns it. Not part of the library class: callers go through + /// [RoaringBitmapUtils#deserializeToUnion]. + static RoaringBitmapUnion deserialize(ByteBuffer byteBuffer) { + LazyBitmap bitmap = new LazyBitmap(); + try { + bitmap.deserialize(byteBuffer); + } catch (IOException e) { + throw new RuntimeException("Caught exception while deserializing RoaringBitmap", e); + } + return new RoaringBitmapUnion(bitmap); + } + + /// Unions the input into the accumulated state. The input is neither modified nor retained, so it may be reused or + /// mutated afterwards. Adding this union's own [#get()] result, or an empty bitmap, is a no-op. + public void add(RoaringBitmap input) { + Objects.requireNonNull(input, "input"); + if (input == _bitmap || input.isEmpty()) { + return; + } + beforeMutation(); + boolean dense = _numValuesAdded >= (long) MIN_VALUES_PER_CONTAINER_FOR_LAZY_UNION * _bitmap.getContainerCount(); + _numValuesAdded += input.getLongCardinality(); + if (dense && !insertsManyNewKeys(input)) { + _dirty = true; + _bitmap.lazyOr(input); Review Comment: Non-blocking: please check actual density before enabling lazy unions. `_numValuesAdded` counts duplicates, so repeated sparse inputs eventually trigger lazy union even though the result remains sparse. For example, folding 10,000 copies of a 500-value hashed bitmap spread across 499 containers switches to the lazy path after about 1,022 inputs, while the result still contains only 500 values. This is reachable when serialized `DISTINCT_COUNT_BITMAP` rows or star-tree groups contain highly overlapping hash values. With the exact PR sources on Java 25 and RoaringBitmap 1.6.23, an isolated fold allocated 215,526,208 bytes versus 54,032 bytes with eager union and took roughly twice as long. The library's sparse `lazyIOR` allocates a new array container and backing array on each overlap, whereas eager `ior` reuses capacity. These are union-only measurements, not whole-query timings. The same condition exists in `MutableRoaringBitmapUnion` at lines 94–98. When the estimate reaches the threshold, consider checking actual cardinality/density and resetting the estimate if the accumulator remains sparse. A benchmark with many repeated sparse inputs would cover this case. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [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]
