lucene
lucene copied to clipboard
apache
Use multi-select instead of a full sort for DynamicRange creation
Resolves #13760
Description
This is using a similar approach to how Solr used to compute multiple percentiles at a single time. Basically utilize the quick select method, but instead of following a single path, follow a path for each of the ks that is requested. Multi-quickselect.
That's what I originally made, until I realized that the DynamicRangeUtil is weighted, so I refactored it to choose by weights instead, and also capture the running-value-total and running-weight-total, because that information is used in the DynamicRangeInfo.
My goal was to add this as a generic capability of the Selector (or IntroSelector) class, but because of the limitations above, it is currently a separate class to handle this. If there's any suggestions on how to make this generic enough to be put in the generic class, that would be great. But it might not be worth the effort if it wouldn't be used anywhere else.
As for the original multi-quickSelect algorithm I mentioned, I looked for other multi-select use cases across Lucene, but I only found one instance (ScalarQuantizer does two select calls in succession). If there's more instances we can find, I would be happy to add multiSelect as an option on the Selector class, and implement it in all provided classes.
To-Do
- The code needs to be cleaned up and better documented, this is just a POC
- Benchmarks comparing this to the full-sorting implementation.
Caveat
The implement is slightly different, as it will pick the groups according to "The first value for which the running weight is <= weight-range-boundary". The old logic would start counting again after a weight range was complete, which removes information from the overflow of previous weight-ranges. I'm not sure either approach is right or wrong, but I wanted to explicitly state how the results would be different and why I had to alter a unit test to pass.
This PR has not had activity in the past 2 weeks, labeling it as stale. If the PR is waiting for review, notify the [email protected] list. Thank you for your contribution!
![github-actions[bot] avatar](https://avatars.githubusercontent.com/in/15368?v=4 "Published by a pub.dev verified publisher"){kind=small}
This is a great improvement for Dynamic Ranges @HoustonPutman! After looking into some more test cases, I believe there may be a bug for some unsorted value lists. Consider this unit test:
public void testComputeDynamicNumericRangesWithMisplacedValue() {
List<DynamicRangeUtil.DynamicRangeInfo> expectedRangeInfoList = new ArrayList<>();
long[] values =
new long[] {
1, 2, 11, 101, 102, 103, 104, 105, 106, 107, 108, 109, 110, 12, 111, 112, 113, 114, 115
};
long[] weights =
new long[] {
2, 3, 12, 102, 103, 104, 105, 106, 107, 108, 109, 110, 111, 13, 112, 113, 114, 115, 116
};
expectedRangeInfoList.add(new DynamicRangeUtil.DynamicRangeInfo(8, 444, 1L, 104L, 54.5D));
expectedRangeInfoList.add(new DynamicRangeUtil.DynamicRangeInfo(4, 430, 105L, 108L, 106.5D));
expectedRangeInfoList.add(new DynamicRangeUtil.DynamicRangeInfo(4, 446, 109L, 112L, 110.5D));
expectedRangeInfoList.add(new DynamicRangeUtil.DynamicRangeInfo(3, 345, 113L, 115L, 114.0D));
assertDynamicNumericRangeResults(values, weights, 4, 1646, 1665, expectedRangeInfoList);
}
With the following error (Notice values marked with **):
java.lang.AssertionError: expected:<[DynamicRangeInfo[count=8, weight=444, min=**1**, max=104, centroid=54.5], DynamicRangeInfo[count=4, weight=430, min=105, max=108, centroid=106.5], DynamicRangeInfo[count=4, weight=446, min=109, max=112, centroid=110.5], DynamicRangeInfo[count=3, weight=345, min=113, max=115, centroid=114.0]]> but was:<[DynamicRangeInfo[count=8, weight=444, min=**12**, max=104, centroid=54.5], DynamicRangeInfo[count=4, weight=430, min=105, max=108, centroid=106.5], DynamicRangeInfo[count=4, weight=446, min=109, max=112, centroid=110.5], DynamicRangeInfo[count=3, weight=345, min=113, max=115, centroid=114.0]]>
I have also posted a fix in the review, but there may be better solutions.
Hey @HoustonPutman, I just published GH#14238 which contains all of the unit tests that I've created so far. Note that there was a slight API change between the main branch and this PR, so I included some unit tests that work for this PR below. While some of these tests are not considering the caveat (the change in behavior) you mentioned, I believe there are a few unit tests that capture a few existing issues. For instance:
public void testComputeDynamicNumericRangesWithLargeTopN() {
List<DynamicRangeUtil.DynamicRangeInfo> expectedRangeInfoList = new ArrayList<>();
long[] values = new long[] {487, 439, 794, 277};
long[] weights = new long[] {59, 508, 736, 560};
expectedRangeInfoList.add(new DynamicRangeUtil.DynamicRangeInfo(1, 560L, 277L, 277L, 277D));
expectedRangeInfoList.add(new DynamicRangeUtil.DynamicRangeInfo(1, 508L, 439L, 439L, 439D));
expectedRangeInfoList.add(new DynamicRangeUtil.DynamicRangeInfo(2, 795L, 487L, 794L, 640.5D));
assertDynamicNumericRangeResults(values, weights, 42, 1997L, 1863L, expectedRangeInfoList);
}
Gives the exception:
java.lang.IllegalArgumentException: All kWeights must be < beforeWeight + rangeWeight
at __randomizedtesting.SeedInfo.seed([913AAD1D60B9263B:FFD4EE9EA025DBF]:0)
at [email protected]/org.apache.lucene.util.WeightedSelector.checkArgs(WeightedSelector.java:82)
at [email protected]/org.apache.lucene.util.WeightedSelector.select(WeightedSelector.java:57)
at org.apache.lucene.facet.range.DynamicRangeUtil.computeDynamicNumericRanges(DynamicRangeUtil.java:266)
at org.apache.lucene.facet.range.TestDynamicRangeUtil.testComputeDynamicNumericRangesWithLargeTopN(TestDynamicRangeUtil.java:169)
at java.base/jdk.internal.reflect.DirectMethodHandleAccessor.invoke(DirectMethodHandleAccessor.java:103)
I've tried to track down this bug, and I haven't quite fixed it, but I believe the fix is related to these lines:
--- a/lucene/facet/src/java/org/apache/lucene/facet/range/DynamicRangeUtil.java
+++ b/lucene/facet/src/java/org/apache/lucene/facet/range/DynamicRangeUtil.java
@@ -216,7 +216,7 @@ public final class DynamicRangeUtil {
return dynamicRangeResult;
}
- double rangeWeightTarget = (double) totalWeight / topN;
+ double rangeWeightTarget = (double) totalWeight / Math.min(topN, len);
double[] kWeights = new double[topN];
for (int i = 0; i < topN; i++) {
kWeights[i] = (i == 0 ? 0 : kWeights[i - 1]) + rangeWeightTarget;
--
Additionally:
public void testComputeDynamicNumericRangesWithSameWeights() {
List<DynamicRangeUtil.DynamicRangeInfo> expectedRangeInfoList = new ArrayList<>();
long totalValue = 0;
long[] values = new long[100];
long[] weights = new long[100];
for (int i = 0; i < 100; i++) {
values[i] = i;
weights[i] = 50;
totalValue += i;
}
expectedRangeInfoList.add(new DynamicRangeUtil.DynamicRangeInfo(25, 1250L, 0L, 24L, 12.0D));
expectedRangeInfoList.add(new DynamicRangeUtil.DynamicRangeInfo(25, 1250L, 25L, 49L, 37.0D));
expectedRangeInfoList.add(new DynamicRangeUtil.DynamicRangeInfo(25, 1250L, 50L, 74L, 62.0D));
expectedRangeInfoList.add(new DynamicRangeUtil.DynamicRangeInfo(25, 1250L, 75L, 99L, 87.0D));
assertDynamicNumericRangeResults(values, weights, 4, totalValue, 5000L, expectedRangeInfoList);
}
Gives (Important values marked with **):
java.lang.AssertionError: expected:<[DynamicRangeInfo[count=**25**, weight=1250, min=0, max=24, centroid=12.0], DynamicRangeInfo[count=25, weight=1250, min=25, max=49, centroid=37.0], DynamicRangeInfo[count=25, weight=1250, min=50, max=74, centroid=62.0], DynamicRangeInfo[count=25, weight=1250, min=75, max=99, centroid=87.0]]> but was:<[DynamicRangeInfo[count=**26**, weight=1300, min=0, max=25, centroid=12.5], DynamicRangeInfo[count=25, weight=1250, min=26, max=50, centroid=38.0], DynamicRangeInfo[count=25, weight=1250, min=51, max=75, centroid=63.0], DynamicRangeInfo[count=24, weight=1200, min=76, max=99, centroid=87.5]]>
at __randomizedtesting.SeedInfo.seed([DA6EB4C0C0CA4022:DBA0A4538AB03899]:0)
at [email protected]/org.junit.Assert.fail(Assert.java:89)
at [email protected]/org.junit.Assert.failNotEquals(Assert.java:835)
at [email protected]/org.junit.Assert.assertEquals(Assert.java:120)
at [email protected]/org.junit.Assert.assertEquals(Assert.java:146)
at org.apache.lucene.facet.range.TestDynamicRangeUtil.compareDynamicRangeResult(TestDynamicRangeUtil.java:361)
at org.apache.lucene.facet.range.TestDynamicRangeUtil.assertDynamicNumericRangeResults(TestDynamicRangeUtil.java:351)
at org.apache.lucene.facet.range.TestDynamicRangeUtil.testComputeDynamicNumericRangesWithSameWeights(TestDynamicRangeUtil.java:156)
I know you mentioned there is a change in behavior in the caveat, but I do believe that this example should probably return ranges with equal counts.
I know you mentioned there is a change in behavior in the caveat, but I do believe that this example should probably return ranges with equal counts.
This one was a <= that should have been a <. I've fixed it and the tests pass.
I've tried to track down this bug, and I haven't quite fixed it, but I believe the fix is related to these lines:
Yeah this one was an issue with floating point math. I've set it such that the last quantile will always be the total, no need to do math for that.
The test still returns different results, but at least it fails without an exception.
@HoustonPutman I can confirm that the latest commits fixed the exception in testComputeDynamicNumericRangesWithLargeTopN and the issue in testComputeDynamicNumericRangesWithSameWeights.
Some of the randomized testing included in GH#14238 revealed some more bugs (they also revealed some of my own bugs in GH#14238):
public void testComputeDynamicNumericRangesWithSameWeightsOutOfOrder() {
List<DynamicRangeUtil.DynamicRangeInfo> expectedRangeInfoList = new ArrayList<>();
long[] values =
new long[] {
20, 15, 59, 49, 13, 93, 72, 21, 36, 81, 57, 1, 90, 79, 16, 51, 7, 17, 25, 63, 12, 5, 83,
66, 48, 43, 55, 78, 64, 77, 65, 73, 80, 37, 54, 50, 95, 31, 97, 3, 82, 29, 70, 26, 4, 46,
34, 67, 87, 0, 30, 19, 41, 85, 84, 89, 8, 10, 22, 28, 6, 23, 88, 40, 33, 44, 18, 27, 69,
38, 91, 98, 62, 14, 35, 2, 92, 47, 94, 75, 32, 99, 86, 71, 74, 24, 52, 96, 9, 58, 39, 76,
56, 11, 53, 61, 42, 68, 60, 45
};
long[] weights =
new long[] {
50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50,
50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50,
50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50,
50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50,
50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50
};
// This is testComputeDynamicNumericRangesWithSameWeightsShuffled with seed
// 9AE79D72C8DD56D8
expectedRangeInfoList.add(new DynamicRangeUtil.DynamicRangeInfo(25, 1250L, 0L, 24L, 12.0D));
expectedRangeInfoList.add(new DynamicRangeUtil.DynamicRangeInfo(25, 1250L, 25L, 49L, 37.0D));
expectedRangeInfoList.add(new DynamicRangeUtil.DynamicRangeInfo(25, 1250L, 50L, 74L, 62.0D));
expectedRangeInfoList.add(new DynamicRangeUtil.DynamicRangeInfo(25, 1250L, 75L, 99L, 87.0D));
assertDynamicNumericRangeResults(values, weights, 4, 4950L, 5000L, expectedRangeInfoList);
}
Gives (look at **):
> java.lang.AssertionError: expected:<[DynamicRangeInfo[count=25, weight=1250, min=0, max=24, centroid=12.0], DynamicRangeInfo[count=25, weight=1250, **min=25**, max=49, centroid=37.0], DynamicRangeInfo[count=25, weight=1250, min=50, max=74, centroid=62.0], DynamicRangeInfo[count=25, weight=1250, min=75, max=99, centroid=87.0]]> but was:<[DynamicRangeInfo[count=25, weight=1250, min=0, max=24, centroid=12.0], DynamicRangeInfo[count=25, weight=1250, **min=43**, max=49, centroid=37.0], DynamicRangeInfo[count=25, weight=1250, min=50, max=74, centroid=62.0], DynamicRangeInfo[count=25, weight=1250, min=75, max=99, centroid=87.0]]>
> at __randomizedtesting.SeedInfo.seed([1E722DB63C0BE5AA:F241CBDDDDB3FF8C]:0)
> at [email protected]/org.junit.Assert.fail(Assert.java:89)
> at [email protected]/org.junit.Assert.failNotEquals(Assert.java:835)
> at [email protected]/org.junit.Assert.assertEquals(Assert.java:120)
> at [email protected]/org.junit.Assert.assertEquals(Assert.java:146)
> at org.apache.lucene.facet.range.TestDynamicRangeUtil.assertDynamicNumericRangeResults(TestDynamicRangeUtil.java:389)
> at org.apache.lucene.facet.range.TestDynamicRangeUtil.testComputeDynamicNumericRangesWithSameWeightsOutOfOrder(TestDynamicRangeUtil.java:172)
I believe that this is still related to the minimum in a range bug. Note that this result is with the latest commits you added. Additionally, I think it might be helpful if you run some of these randomized tests overnight to reduce some of the back and forth. I'll post another comment later today with a modification of those randomization tests that you should be able to run.
Here are the promised modified randomized unit tests. These should work with your API change, but you might need to modify them to suit the caveat you mentioned. Of course, add the correct imports:
public void testComputeDynamicNumericRangesWithSameWeightsShuffled() {
List<DynamicRangeUtil.DynamicRangeInfo> expectedRangeInfoList = new ArrayList<>();
long[] values = new long[100];
long[] weights = new long[100];
for (int i = 0; i < 100; i++) {
values[i] = i;
weights[i] = 50;
}
// Shuffling the values and weights should not change the answer between runs
// We expect that returned ranges should come in a strict, deterministic order
// with the same values and weights
shuffleValuesWeights(values, weights);
expectedRangeInfoList.add(new DynamicRangeUtil.DynamicRangeInfo(25, 1250L, 0L, 24L, 12.0D));
expectedRangeInfoList.add(new DynamicRangeUtil.DynamicRangeInfo(25, 1250L, 25L, 49L, 37.0D));
expectedRangeInfoList.add(new DynamicRangeUtil.DynamicRangeInfo(25, 1250L, 50L, 74L, 62.0D));
expectedRangeInfoList.add(new DynamicRangeUtil.DynamicRangeInfo(25, 1250L, 75L, 99L, 87.0D));
assertDynamicNumericRangeResults(values, weights, 4, 4950L, 5000L, expectedRangeInfoList);
}
public void testComputeDynamicNumericRangesWithSameValuesShuffled() {
List<DynamicRangeUtil.DynamicRangeInfo> expectedRangeInfoList = new ArrayList<>();
long totalWeight = 0;
long[] values = new long[100];
long[] weights = new long[100];
for (int i = 0; i < 100; i++) {
values[i] = 50;
weights[i] = i;
totalWeight += i;
}
// Shuffling the values and weights should not change the answer between runs
// We expect that returned ranges should come in a strict, deterministic order
// with the same values and weights
shuffleValuesWeights(values, weights);
expectedRangeInfoList.add(new DynamicRangeUtil.DynamicRangeInfo(51, 1275L, 50L, 50L, 50D));
expectedRangeInfoList.add(new DynamicRangeUtil.DynamicRangeInfo(21, 1281L, 50L, 50L, 50D));
expectedRangeInfoList.add(new DynamicRangeUtil.DynamicRangeInfo(16, 1272L, 50L, 50L, 50D));
expectedRangeInfoList.add(new DynamicRangeUtil.DynamicRangeInfo(12, 1122L, 50L, 50L, 50D));
assertDynamicNumericRangeResults(values, weights, 4, 5000L, totalWeight, expectedRangeInfoList);
}
public void testComputeDynamicNumericRangesWithRandomValues() {
int arraySize = random().nextInt(100);
long[] values = new long[arraySize];
long[] weights = new long[arraySize];
for (int i = 0; i < arraySize; i++) {
values[i] = random().nextLong(1000);
weights[i] = random().nextLong(1000);
}
int topN = random().nextInt(100);
long totalWeight = 0;
long totalValue = 0;
for (int i = 0; i < arraySize; i++) {
totalWeight += weights[i];
totalValue += values[i];
}
assertDynamicNumericRangeValidProperties(values, weights, topN, totalValue, totalWeight);
}
private static void assertDynamicNumericRangeValidProperties(
long[] values, long[] weights, int topN, long totalValue, long totalWeight) {
List<WeightedPair> sortedPairs = new ArrayList<>();
for (int i = 0; i < values.length; i++) {
long value = values[i];
long weight = weights[i];
WeightedPair pair = new WeightedPair(value, weight);
sortedPairs.add(pair);
}
sortedPairs.sort(
Comparator.comparingLong(WeightedPair::value).thenComparingLong(WeightedPair::weight));
int len = values.length;
double rangeWeightTarget = (double) totalWeight / Math.min(topN, len);
List<DynamicRangeUtil.DynamicRangeInfo> mockDynamicRangeResult =
DynamicRangeUtil.computeDynamicNumericRanges(
values, weights, values.length, totalValue, totalWeight, topN);
// Zero requested ranges (TopN) should return a empty list of ranges regardless of inputs
if (topN == 0) {
assertTrue(mockDynamicRangeResult.size() == 0);
return; // Early return; do not check anything else
}
// Adjacent ranges do not overlap - only adjacent max-min can overlap
for (int i = 0; i < mockDynamicRangeResult.size() - 1; i++) {
DynamicRangeUtil.DynamicRangeInfo rangeInfo = mockDynamicRangeResult.get(i);
DynamicRangeUtil.DynamicRangeInfo nextRangeInfo = mockDynamicRangeResult.get(i + 1);
assertTrue(rangeInfo.max() <= nextRangeInfo.min());
}
// The count of every range sums to the number of values
int accuCount = 0;
for (int i = 0; i < mockDynamicRangeResult.size(); i++) {
DynamicRangeUtil.DynamicRangeInfo rangeInfo = mockDynamicRangeResult.get(i);
int count = rangeInfo.count();
accuCount += count;
}
assertTrue(accuCount == len);
// The sum of every range weight equals the total weight
long accuWeight = 0;
for (int i = 0; i < mockDynamicRangeResult.size(); i++) {
DynamicRangeUtil.DynamicRangeInfo rangeInfo = mockDynamicRangeResult.get(i);
long weight = rangeInfo.weight();
accuWeight += weight;
}
assertTrue(accuWeight == totalWeight);
// All values appear in atleast one range
for (int pairOffset = 0, rangeIdx = 0; rangeIdx < mockDynamicRangeResult.size(); rangeIdx++) {
DynamicRangeUtil.DynamicRangeInfo rangeInfo = mockDynamicRangeResult.get(rangeIdx);
int count = rangeInfo.count();
for (int i = pairOffset; i < pairOffset + count; i++) {
WeightedPair pair = sortedPairs.get(i);
long value = pair.value();
assertTrue(rangeInfo.min() <= value && value <= rangeInfo.max());
}
pairOffset += count;
}
// The minimum/maximum of each range is actually the smallest/largest value
for (int pairOffset = 0, rangeIdx = 0; rangeIdx < mockDynamicRangeResult.size(); rangeIdx++) {
DynamicRangeUtil.DynamicRangeInfo rangeInfo = mockDynamicRangeResult.get(rangeIdx);
int count = rangeInfo.count();
WeightedPair minPair = sortedPairs.get(pairOffset);
WeightedPair maxPair = sortedPairs.get(pairOffset + count - 1);
long min = minPair.value();
long max = maxPair.value();
assertTrue(rangeInfo.min() == min);
assertTrue(rangeInfo.max() == max);
pairOffset += count;
}
// Weights of each range is over the rangeWeightTarget - exclude last range
for (int i = 0; i < mockDynamicRangeResult.size() - 1; i++) {
DynamicRangeUtil.DynamicRangeInfo rangeInfo = mockDynamicRangeResult.get(i);
assertTrue(rangeInfo.weight() >= rangeWeightTarget);
}
// Removing the last weight from a range brings it under the rangeWeightTarget - exclude last
// range
for (int pairOffset = 0, rangeIdx = 0;
rangeIdx < mockDynamicRangeResult.size() - 1;
rangeIdx++) {
DynamicRangeUtil.DynamicRangeInfo rangeInfo = mockDynamicRangeResult.get(rangeIdx);
int count = rangeInfo.count();
WeightedPair lastPair = sortedPairs.get(pairOffset + count - 1);
long lastWeight = lastPair.weight();
pairOffset += count;
assertTrue(rangeInfo.weight() - lastWeight < rangeWeightTarget);
}
// Centroids for each range are correct
for (int pairOffset = 0, rangeIdx = 0; rangeIdx < mockDynamicRangeResult.size(); rangeIdx++) {
DynamicRangeUtil.DynamicRangeInfo rangeInfo = mockDynamicRangeResult.get(rangeIdx);
int count = rangeInfo.count();
long accuValue = 0;
for (int i = pairOffset; i < pairOffset + count; i++) {
WeightedPair pair = sortedPairs.get(i);
long value = pair.value();
accuValue += value;
}
pairOffset += count;
assertTrue(rangeInfo.centroid() == ((double) accuValue / count));
}
}
/** Implementation of Durstenfeld's algorithm for shuffling values and weights */
private static void shuffleValuesWeights(long[] values, long[] weights) {
for (int i = values.length - 1; i > 0; i--) {
int rdmIdx = random().nextInt(i + 1);
long tmpValue = values[i];
long tmpWeight = weights[i];
values[i] = values[rdmIdx];
weights[i] = weights[rdmIdx];
values[rdmIdx] = tmpValue;
weights[rdmIdx] = tmpWeight;
}
}
/**
* Holds parameters of a weighted pair.
*
* @param value the value of the pair
* @param weight the weight of the pair
*/
private record WeightedPair(long value, long weight) {}
Additionally, here is a command that you can run from the command line to search for bugs:
First, ./gradlew clean and ./gradlew build
for i in {1..100}; do; echo $i; ./gradlew check; if [ $? -gt 0 ]; then; cat $path_to_test_output >> "../errors.txt"; fi; done;
$path_to_test_output should be a path ending with OUTPUT-org.apache.lucene.facet.range.TestDynamicRangeUtil.txt. This should be the same location that you go whenever you want to view the output from unit tests (which appears when a unit test fails after a build fails).
After the command finishes, all of the found bugs should be in ../error.txt.
This PR has not had activity in the past 2 weeks, labeling it as stale. If the PR is waiting for review, notify the [email protected] list. Thank you for your contribution!
This PR does not have an entry in lucene/CHANGES.txt. Consider adding one. If the PR doesn't need a changelog entry, then add the skip-changelog label to it and you will stop receiving this reminder on future updates to the PR.
This PR has not had activity in the past 2 weeks, labeling it as stale. If the PR is waiting for review, notify the [email protected] list. Thank you for your contribution!
This PR has not had activity in the past 2 weeks, labeling it as stale. If the PR is waiting for review, notify the [email protected] list. Thank you for your contribution!