假设您正在使用 Java 进行某种数据分析，也许您正在分析交易（如销售）。Transaction在对对象执行计算之前，您需要评估复杂的过滤器。
public static final class Transaction {
private final int quantity;
private final long price;
private final long timestamp;
public Transaction(int quantity, long price, long timestamp) {
this.quantity = quantity;
this.price = price;
this.timestamp = timestamp;
}
public int getQuantity() {
return quantity;
}
public long getPrice() {
return price;
}
public long getTimestamp() {
return timestamp;
}
}
|
在 Java 程序中进行过滤使用流 API：
transactions.stream()
.filter(transaction -> transaction.quantity >= qty && transaction.price <= price
&& transaction.timestamp >= begin && transaction.timestamp <= end)
.forEach(this::processTransaction);
|
假设交易实际上是按时间排序的，那么时间戳条件应该是可预测的，但并没有首先评估。
这意味着不可预测的价格price 和数量quantity 条件要对每个交易进行评估。
如果重新安排条件的顺序可以使运行时间缩短一半。
RangeBitmap
将范围谓词应用于未排序的数据，由RoaringBitmap库RangeBitmap中的数据结构解决。
数据结构是不可变的，并且受益于对数据集中值范围的了解，但是如果需要评估多个过滤器，则为每个属性建立索引可能是值得的。
long minTimestamp = Long.MAX_VALUE;
long maxTimestamp = Long.MIN_VALUE;
long minPrice = Long.MAX_VALUE;
long maxPrice = Long.MIN_VALUE;
int minQty = Long.MAX_VALUE;
int maxQty = Long.MIN_VALUE;
for (Transaction transaction : transactions) {
minTimestamp = Math.min(minTimestamp, transaction.getTimestamp());
maxTimestamp = Math.max(maxTimestamp, transaction.getTimestamp());
minPrice = Math.min(minPrice, transaction.getPrice());
maxPrice = Math.max(maxPrice, transaction.getPrice());
minQty = Math.min(minQty, transaction.getQuantity());
maxQty = Math.max(maxQty, transaction.getQuantity());
}
var timestampAppender = RangeBitmap.appender(maxTimestamp - minTimestamp);
var priceAppender = RangeBitmap.appender(maxPrice - minPrice);
var qtyAppender = RangeBitmap.appender(maxQty - minQty);
for (Transaction transaction : transactions) {
timestampAppender.add(transaction.getTimestamp() - minTimestamp);
priceAppender.add(transaction.getPrice() - minPrice);
qtyAppender.add(transaction.getQuantity() - minQty);
}
var timestampIndex = timestampAppender.build();
var priceIndex = priceAppender.build();
var qtyIndex = qtyAppender.build();
|
两者是否传递数据或半页代码是否值得取决于您需要执行多少过滤器以及它们需要多快。
RangeBitmap产生一个RoaringBitmap满足谓词的索引，并且可以将RoaringBitmap参数作为输入来跳过已经过滤掉的行。之前使用的 Streams API 代码被翻译成RangeBitmapAPI 调用：
RoaringBitmap inTimeRange = timestampIndex.between(minTimeThreshold - minTime, maxTimeThreshold - minTime);
RoaringBitmap matchesQuantity = qtyIndex.gte(minQtyThreshold - minQty, inTimeRange);
RoaringBitmap matchesPrice = priceIndex.lte(maxPriceThreshold - minPrice, matchesQuantity);
matchesPrice.forEach((IntConsumer) i -> processTransaction(transactions.get(i)));
|
每个属性的最小值锚定有点复杂，但提高了效率（除非最小值无论如何都是零），这将在实际应用程序中通过便利类更好地抽象。对于相同的数据，这比二分搜索方法快约 2 倍.
RangeBitmap旨在为Apache Pinot中的范围索引提供支持，因此被压缩并支持与磁盘的零拷贝映射。RangeBitmap - How range index work in Apache Pinot 中有更多关于它如何深入工作的详细信息。