You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@lucene.apache.org by "jpountz (via GitHub)" <gi...@apache.org> on 2024/02/21 10:07:33 UTC

[PR] Change BP reordering logic to help support document blocks later on. [lucene]

jpountz opened a new pull request, #13123:
URL: https://github.com/apache/lucene/pull/13123

   The current logic for reordering splits a slice of doc IDs into a left side and a right side, and for each document it computes the expected gain of moving to the other side. Then it swaps documents from both sides as long as the sum of the gain of moving the left doc to the right and the right doc to the left is positive.
   
   This works well, but I would like to extend BP reordering to also work with blocks, and the swapping logic is challenging to modify as two parent documents may have different numbers of children.
   
   One of the follow-up papers on BP suggested to use a different logic, where one would compute a bias for all documents that is negative when a document is attracted to the left and positive otherwise. Then we only have to partition doc IDs around the mid point, e.g. with quickselect.
   
   A benefit of this change is that it will make it easier to generalize BP reordering to indexes that have blocks, e.g. by using a stable sort on biases.


-- 
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-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Change BP reordering logic to help support document blocks later on. [lucene]

Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz merged PR #13123:
URL: https://github.com/apache/lucene/pull/13123


-- 
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-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Change BP reordering logic to help support document blocks later on. [lucene]

Posted by "rishabhmaurya (via GitHub)" <gi...@apache.org>.
rishabhmaurya commented on code in PR #13123:
URL: https://github.com/apache/lucene/pull/13123#discussion_r1513889998


##########
lucene/misc/src/java/org/apache/lucene/misc/index/BPIndexReorderer.java:
##########
@@ -341,116 +344,94 @@ protected void compute() {
      */
     private boolean shuffle(
         ForwardIndex forwardIndex,
-        IntsRef left,
-        IntsRef right,
+        IntsRef docIDs,
+        int midPoint,
         int[] leftDocFreqs,
         int[] rightDocFreqs,
-        float[] gains,
+        float[] biases,
         int iter)
         throws IOException {
-      assert left.ints == right.ints;
-      assert left.offset + left.length == right.offset;
 
-      // Computing gains is typically a bottleneck, because each iteration needs to iterate over all
-      // postings to recompute gains, and the total number of postings is usually one order of
+      // Computing biases is typically a bottleneck, because each iteration needs to iterate over
+      // all postings to recompute biases, and the total number of postings is usually one order of
       // magnitude or more larger than the number of docs. So we try to parallelize it.
-      ComputeGainsTask leftGainsTask =
-          new ComputeGainsTask(
-              left.ints,
-              gains,
-              left.offset,
-              left.offset + left.length,
+      new ComputeBiasTask(
+              docIDs.ints,
+              biases,
+              docIDs.offset,
+              docIDs.offset + docIDs.length,
               leftDocFreqs,
               rightDocFreqs,
               threadLocal,
-              depth);
-      ComputeGainsTask rightGainsTask =
-          new ComputeGainsTask(
-              right.ints,
-              gains,
-              right.offset,
-              right.offset + right.length,
-              rightDocFreqs,
-              leftDocFreqs,
-              threadLocal,
-              depth);
-      if (shouldFork(docIDs.length, docIDs.ints.length)) {
-        invokeAll(leftGainsTask, rightGainsTask);
-      } else {
-        leftGainsTask.compute();
-        rightGainsTask.compute();
+              depth)
+          .compute();
+
+      float maxLeftBias = Float.NEGATIVE_INFINITY;
+      for (int i = docIDs.offset; i < midPoint; ++i) {
+        maxLeftBias = Math.max(maxLeftBias, biases[i]);
+      }
+      float minRightBias = Float.POSITIVE_INFINITY;
+      for (int i = midPoint, end = docIDs.offset + docIDs.length; i < end; ++i) {
+        minRightBias = Math.min(minRightBias, biases[i]);
+      }
+      float gain = maxLeftBias - minRightBias;
+      // This uses the simulated annealing proposed by Mackenzie et al in "Tradeoff Options for
+      // Bipartite Graph Partitioning" by comparing the gain of swapping the doc from the left side
+      // that is most attracted to the right and the doc from the right side that is most attracted
+      // to the left against `iter` rather than zero.
+      if (gain <= iter) {
+        return false;
       }
 
-      class ByDescendingGainSorter extends IntroSorter {
+      new IntroSelector() {
 
         int pivotDoc;
-        float pivotGain;
+        float pivotBias;
 
         @Override
         protected void setPivot(int i) {
-          pivotDoc = left.ints[i];
-          pivotGain = gains[i];
+          pivotDoc = docIDs.ints[i];
+          pivotBias = biases[i];
         }
 
         @Override
         protected int comparePivot(int j) {
-          // Compare in reverse order to get a descending sort
-          int cmp = Float.compare(gains[j], pivotGain);
+          int cmp = Float.compare(pivotBias, biases[j]);

Review Comment:
   @jpountz To be precise, this is what I tried to avoid swaps as per the paper - 
   ```java
       int cmp = Float.compare(pivotBias-iter, biases[j]);
       if (cmp > 0) {
         return cmp;
       }
       cmp = Float.compare(pivotBias, biases[j]);
       if (cmp >= 0) {
         // Tie break on the doc ID to preserve doc ID ordering as much as possible
         cmp = pivotDoc - docIDs.ints[j];
       }
       return cmp;
   ```
   It won't be a precise kth largest but will be close to it with tolerance factor governed by `iter`. 
   
   I used [http_logs](https://github.com/opensearch-project/opensearch-benchmark-workloads/blob/main/http_logs) workload and I see similar results as described in the paper with respect to time taken to perform reordering.
   
   For benchmark setup, I setup just a single shard and try to force merge into one segment after indexing and the corpus used is `logs-231998`. 
   
   Here is the result - 
   
   ### With this change
   ```shell
   Final index size: 686.3mb
   curl localhost:9200/_cat/indices
   green open logs-231998 T-HpeIWARuSZFGa74PWOig 1 0 11961342 0 686.3mb 686.3mb
   ```
   Some additional metrics I'm publishing [here](https://github.com/rishabhmaurya/lucene/commit/fda8f19ac691af832e4bd7b4722324a4f14971bf#diff-43ddf233a75c4de53d99ec83e5b52a5eff0c39e8d601ae6816db49c7c14f785aR1154), you can see **number of swaps to number of docs ratio is 8**
   ```
   Reorder stats
   totalDocs: 11961342; numTerms: 964; totalPostings: 88726436; totalSwapsPerformed: 96188516; postingsDocRatio: 7; swapsDocsRatio: 8
   12816206 9489609 12087839 12496439 9235544 9035264 8148933 6569703 5403994 3803447 2775037 1757719 1117468 668304 374775 216838 120914 70483 0 0 0 0 0 0 0
   ```
   |                                                         Metric |                     Task |       Value |   Unit |
   |---------------------------------------------------------------:|-------------------------:|------------:|-------:|
   |                        Cumulative merge time of primary shards |                          |     9.23488 |    min |
   |                       Cumulative merge count of primary shards |                          |          20 |        |
   
   ### Without this change
   ```shell
   Final index size: 840.2mb
   curl localhost:9200/_cat/indices
   green open logs-231998 wZ8LNHeDQaCiLgOkJTjKxg 1 0 11961342 0 840.2mb 840.2mb
   ```
   **number of swaps to number of docs ratio is 47**
   ```
   Reorder stats
   totalDocs: 11961342; numTerms: 964; totalPostings: 88726436; totalSwapsPerformed: 571132294; postingsDocRatio: 7; swapsDocsRatio: 47
   47254463 55941681 48415352 38245831 39694052 36558063 37907697 33234795 32316838 30361191 27886028 26467715 24669276 22745648 21136997 17510104 16757532 14029031 0 0 0 0 0 0 0
   ```
   | Metric | Task | Value | Unit |
   | ---: | ---: | ---: | ---: |
   | Cumulative merge time of primary shards |  | 15.5215 | min |
   | Cumulative merge count of primary shards |  | 20 |  |
   
   So overall time to perform merge reduced from 15.5 mins to 9.23 mins. Also, number of swaps performed to docs ratio reduced significantly here. 
   
   ### Without reordering
   
   ```
   Final index size: 923.8mb
   curl localhost:9200/_cat/indices
   green open logs-231998 O0bppXZUREadOqVz80qJBw 1 0 11961342 0 923.8mb 
   ```
   
   | Metric | Task | Value | Unit |
   | ---: | ---: | ---: | ---: |
   | Cumulative merge time of primary shards |  | 1.13032 | min |
   | Cumulative merge count of primary shards |  | 21 |  |



-- 
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-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Change BP reordering logic to help support document blocks later on. [lucene]

Posted by "rishabhmaurya (via GitHub)" <gi...@apache.org>.
rishabhmaurya commented on code in PR #13123:
URL: https://github.com/apache/lucene/pull/13123#discussion_r1511781873


##########
lucene/misc/src/java/org/apache/lucene/misc/index/BPIndexReorderer.java:
##########
@@ -341,116 +344,94 @@ protected void compute() {
      */
     private boolean shuffle(
         ForwardIndex forwardIndex,
-        IntsRef left,
-        IntsRef right,
+        IntsRef docIDs,
+        int midPoint,
         int[] leftDocFreqs,
         int[] rightDocFreqs,
-        float[] gains,
+        float[] biases,
         int iter)
         throws IOException {
-      assert left.ints == right.ints;
-      assert left.offset + left.length == right.offset;
 
-      // Computing gains is typically a bottleneck, because each iteration needs to iterate over all
-      // postings to recompute gains, and the total number of postings is usually one order of
+      // Computing biases is typically a bottleneck, because each iteration needs to iterate over
+      // all postings to recompute biases, and the total number of postings is usually one order of
       // magnitude or more larger than the number of docs. So we try to parallelize it.
-      ComputeGainsTask leftGainsTask =
-          new ComputeGainsTask(
-              left.ints,
-              gains,
-              left.offset,
-              left.offset + left.length,
+      new ComputeBiasTask(
+              docIDs.ints,
+              biases,
+              docIDs.offset,
+              docIDs.offset + docIDs.length,
               leftDocFreqs,
               rightDocFreqs,
               threadLocal,
-              depth);
-      ComputeGainsTask rightGainsTask =
-          new ComputeGainsTask(
-              right.ints,
-              gains,
-              right.offset,
-              right.offset + right.length,
-              rightDocFreqs,
-              leftDocFreqs,
-              threadLocal,
-              depth);
-      if (shouldFork(docIDs.length, docIDs.ints.length)) {
-        invokeAll(leftGainsTask, rightGainsTask);
-      } else {
-        leftGainsTask.compute();
-        rightGainsTask.compute();
+              depth)
+          .compute();
+
+      float maxLeftBias = Float.NEGATIVE_INFINITY;
+      for (int i = docIDs.offset; i < midPoint; ++i) {
+        maxLeftBias = Math.max(maxLeftBias, biases[i]);
+      }
+      float minRightBias = Float.POSITIVE_INFINITY;
+      for (int i = midPoint, end = docIDs.offset + docIDs.length; i < end; ++i) {
+        minRightBias = Math.min(minRightBias, biases[i]);
+      }
+      float gain = maxLeftBias - minRightBias;
+      // This uses the simulated annealing proposed by Mackenzie et al in "Tradeoff Options for
+      // Bipartite Graph Partitioning" by comparing the gain of swapping the doc from the left side
+      // that is most attracted to the right and the doc from the right side that is most attracted
+      // to the left against `iter` rather than zero.
+      if (gain <= iter) {
+        return false;
       }
 
-      class ByDescendingGainSorter extends IntroSorter {
+      new IntroSelector() {
 
         int pivotDoc;
-        float pivotGain;
+        float pivotBias;
 
         @Override
         protected void setPivot(int i) {
-          pivotDoc = left.ints[i];
-          pivotGain = gains[i];
+          pivotDoc = docIDs.ints[i];
+          pivotBias = biases[i];
         }
 
         @Override
         protected int comparePivot(int j) {
-          // Compare in reverse order to get a descending sort
-          int cmp = Float.compare(gains[j], pivotGain);
+          int cmp = Float.compare(pivotBias, biases[j]);

Review Comment:
   I see that you are terminating early before shuffling by checking ` if (gain <= iter)`; 
   Should we also include `iter` into the equation here `compare(pivotBias - iter, biases[j])`? 
   
   



-- 
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-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Change BP reordering logic to help support document blocks later on. [lucene]

Posted by "rishabhmaurya (via GitHub)" <gi...@apache.org>.
rishabhmaurya commented on code in PR #13123:
URL: https://github.com/apache/lucene/pull/13123#discussion_r1525325740


##########
lucene/misc/src/java/org/apache/lucene/misc/index/BPIndexReorderer.java:
##########
@@ -341,116 +344,94 @@ protected void compute() {
      */
     private boolean shuffle(
         ForwardIndex forwardIndex,
-        IntsRef left,
-        IntsRef right,
+        IntsRef docIDs,
+        int midPoint,
         int[] leftDocFreqs,
         int[] rightDocFreqs,
-        float[] gains,
+        float[] biases,
         int iter)
         throws IOException {
-      assert left.ints == right.ints;
-      assert left.offset + left.length == right.offset;
 
-      // Computing gains is typically a bottleneck, because each iteration needs to iterate over all
-      // postings to recompute gains, and the total number of postings is usually one order of
+      // Computing biases is typically a bottleneck, because each iteration needs to iterate over
+      // all postings to recompute biases, and the total number of postings is usually one order of
       // magnitude or more larger than the number of docs. So we try to parallelize it.
-      ComputeGainsTask leftGainsTask =
-          new ComputeGainsTask(
-              left.ints,
-              gains,
-              left.offset,
-              left.offset + left.length,
+      new ComputeBiasTask(
+              docIDs.ints,
+              biases,
+              docIDs.offset,
+              docIDs.offset + docIDs.length,
               leftDocFreqs,
               rightDocFreqs,
               threadLocal,
-              depth);
-      ComputeGainsTask rightGainsTask =
-          new ComputeGainsTask(
-              right.ints,
-              gains,
-              right.offset,
-              right.offset + right.length,
-              rightDocFreqs,
-              leftDocFreqs,
-              threadLocal,
-              depth);
-      if (shouldFork(docIDs.length, docIDs.ints.length)) {
-        invokeAll(leftGainsTask, rightGainsTask);
-      } else {
-        leftGainsTask.compute();
-        rightGainsTask.compute();
+              depth)
+          .compute();
+
+      float maxLeftBias = Float.NEGATIVE_INFINITY;
+      for (int i = docIDs.offset; i < midPoint; ++i) {
+        maxLeftBias = Math.max(maxLeftBias, biases[i]);
+      }
+      float minRightBias = Float.POSITIVE_INFINITY;
+      for (int i = midPoint, end = docIDs.offset + docIDs.length; i < end; ++i) {
+        minRightBias = Math.min(minRightBias, biases[i]);
+      }
+      float gain = maxLeftBias - minRightBias;
+      // This uses the simulated annealing proposed by Mackenzie et al in "Tradeoff Options for
+      // Bipartite Graph Partitioning" by comparing the gain of swapping the doc from the left side
+      // that is most attracted to the right and the doc from the right side that is most attracted
+      // to the left against `iter` rather than zero.
+      if (gain <= iter) {
+        return false;
       }
 
-      class ByDescendingGainSorter extends IntroSorter {
+      new IntroSelector() {
 
         int pivotDoc;
-        float pivotGain;
+        float pivotBias;
 
         @Override
         protected void setPivot(int i) {
-          pivotDoc = left.ints[i];
-          pivotGain = gains[i];
+          pivotDoc = docIDs.ints[i];
+          pivotBias = biases[i];
         }
 
         @Override
         protected int comparePivot(int j) {
-          // Compare in reverse order to get a descending sort
-          int cmp = Float.compare(gains[j], pivotGain);
+          int cmp = Float.compare(pivotBias, biases[j]);

Review Comment:
   @jpountz done https://github.com/apache/lucene/pull/13186. I wasn't sure if its worthy a PR, thus started discussion here. 



-- 
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-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Change BP reordering logic to help support document blocks later on. [lucene]

Posted by "jpountz (via GitHub)" <gi...@apache.org>.
jpountz commented on code in PR #13123:
URL: https://github.com/apache/lucene/pull/13123#discussion_r1525040811


##########
lucene/misc/src/java/org/apache/lucene/misc/index/BPIndexReorderer.java:
##########
@@ -341,116 +344,94 @@ protected void compute() {
      */
     private boolean shuffle(
         ForwardIndex forwardIndex,
-        IntsRef left,
-        IntsRef right,
+        IntsRef docIDs,
+        int midPoint,
         int[] leftDocFreqs,
         int[] rightDocFreqs,
-        float[] gains,
+        float[] biases,
         int iter)
         throws IOException {
-      assert left.ints == right.ints;
-      assert left.offset + left.length == right.offset;
 
-      // Computing gains is typically a bottleneck, because each iteration needs to iterate over all
-      // postings to recompute gains, and the total number of postings is usually one order of
+      // Computing biases is typically a bottleneck, because each iteration needs to iterate over
+      // all postings to recompute biases, and the total number of postings is usually one order of
       // magnitude or more larger than the number of docs. So we try to parallelize it.
-      ComputeGainsTask leftGainsTask =
-          new ComputeGainsTask(
-              left.ints,
-              gains,
-              left.offset,
-              left.offset + left.length,
+      new ComputeBiasTask(
+              docIDs.ints,
+              biases,
+              docIDs.offset,
+              docIDs.offset + docIDs.length,
               leftDocFreqs,
               rightDocFreqs,
               threadLocal,
-              depth);
-      ComputeGainsTask rightGainsTask =
-          new ComputeGainsTask(
-              right.ints,
-              gains,
-              right.offset,
-              right.offset + right.length,
-              rightDocFreqs,
-              leftDocFreqs,
-              threadLocal,
-              depth);
-      if (shouldFork(docIDs.length, docIDs.ints.length)) {
-        invokeAll(leftGainsTask, rightGainsTask);
-      } else {
-        leftGainsTask.compute();
-        rightGainsTask.compute();
+              depth)
+          .compute();
+
+      float maxLeftBias = Float.NEGATIVE_INFINITY;
+      for (int i = docIDs.offset; i < midPoint; ++i) {
+        maxLeftBias = Math.max(maxLeftBias, biases[i]);
+      }
+      float minRightBias = Float.POSITIVE_INFINITY;
+      for (int i = midPoint, end = docIDs.offset + docIDs.length; i < end; ++i) {
+        minRightBias = Math.min(minRightBias, biases[i]);
+      }
+      float gain = maxLeftBias - minRightBias;
+      // This uses the simulated annealing proposed by Mackenzie et al in "Tradeoff Options for
+      // Bipartite Graph Partitioning" by comparing the gain of swapping the doc from the left side
+      // that is most attracted to the right and the doc from the right side that is most attracted
+      // to the left against `iter` rather than zero.
+      if (gain <= iter) {
+        return false;
       }
 
-      class ByDescendingGainSorter extends IntroSorter {
+      new IntroSelector() {
 
         int pivotDoc;
-        float pivotGain;
+        float pivotBias;
 
         @Override
         protected void setPivot(int i) {
-          pivotDoc = left.ints[i];
-          pivotGain = gains[i];
+          pivotDoc = docIDs.ints[i];
+          pivotBias = biases[i];
         }
 
         @Override
         protected int comparePivot(int j) {
-          // Compare in reverse order to get a descending sort
-          int cmp = Float.compare(gains[j], pivotGain);
+          int cmp = Float.compare(pivotBias, biases[j]);

Review Comment:
   @rishabhmaurya Yes! Please feel free to open a PR and let's discuss there!



-- 
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-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org


Re: [PR] Change BP reordering logic to help support document blocks later on. [lucene]

Posted by "rishabhmaurya (via GitHub)" <gi...@apache.org>.
rishabhmaurya commented on code in PR #13123:
URL: https://github.com/apache/lucene/pull/13123#discussion_r1523704731


##########
lucene/misc/src/java/org/apache/lucene/misc/index/BPIndexReorderer.java:
##########
@@ -341,116 +344,94 @@ protected void compute() {
      */
     private boolean shuffle(
         ForwardIndex forwardIndex,
-        IntsRef left,
-        IntsRef right,
+        IntsRef docIDs,
+        int midPoint,
         int[] leftDocFreqs,
         int[] rightDocFreqs,
-        float[] gains,
+        float[] biases,
         int iter)
         throws IOException {
-      assert left.ints == right.ints;
-      assert left.offset + left.length == right.offset;
 
-      // Computing gains is typically a bottleneck, because each iteration needs to iterate over all
-      // postings to recompute gains, and the total number of postings is usually one order of
+      // Computing biases is typically a bottleneck, because each iteration needs to iterate over
+      // all postings to recompute biases, and the total number of postings is usually one order of
       // magnitude or more larger than the number of docs. So we try to parallelize it.
-      ComputeGainsTask leftGainsTask =
-          new ComputeGainsTask(
-              left.ints,
-              gains,
-              left.offset,
-              left.offset + left.length,
+      new ComputeBiasTask(
+              docIDs.ints,
+              biases,
+              docIDs.offset,
+              docIDs.offset + docIDs.length,
               leftDocFreqs,
               rightDocFreqs,
               threadLocal,
-              depth);
-      ComputeGainsTask rightGainsTask =
-          new ComputeGainsTask(
-              right.ints,
-              gains,
-              right.offset,
-              right.offset + right.length,
-              rightDocFreqs,
-              leftDocFreqs,
-              threadLocal,
-              depth);
-      if (shouldFork(docIDs.length, docIDs.ints.length)) {
-        invokeAll(leftGainsTask, rightGainsTask);
-      } else {
-        leftGainsTask.compute();
-        rightGainsTask.compute();
+              depth)
+          .compute();
+
+      float maxLeftBias = Float.NEGATIVE_INFINITY;
+      for (int i = docIDs.offset; i < midPoint; ++i) {
+        maxLeftBias = Math.max(maxLeftBias, biases[i]);
+      }
+      float minRightBias = Float.POSITIVE_INFINITY;
+      for (int i = midPoint, end = docIDs.offset + docIDs.length; i < end; ++i) {
+        minRightBias = Math.min(minRightBias, biases[i]);
+      }
+      float gain = maxLeftBias - minRightBias;
+      // This uses the simulated annealing proposed by Mackenzie et al in "Tradeoff Options for
+      // Bipartite Graph Partitioning" by comparing the gain of swapping the doc from the left side
+      // that is most attracted to the right and the doc from the right side that is most attracted
+      // to the left against `iter` rather than zero.
+      if (gain <= iter) {
+        return false;
       }
 
-      class ByDescendingGainSorter extends IntroSorter {
+      new IntroSelector() {
 
         int pivotDoc;
-        float pivotGain;
+        float pivotBias;
 
         @Override
         protected void setPivot(int i) {
-          pivotDoc = left.ints[i];
-          pivotGain = gains[i];
+          pivotDoc = docIDs.ints[i];
+          pivotBias = biases[i];
         }
 
         @Override
         protected int comparePivot(int j) {
-          // Compare in reverse order to get a descending sort
-          int cmp = Float.compare(gains[j], pivotGain);
+          int cmp = Float.compare(pivotBias, biases[j]);

Review Comment:
   @jpountz let me know your thoughts on it, happy to contribute and improve it further. Thanks



-- 
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-unsubscribe@lucene.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscribe@lucene.apache.org
For additional commands, e-mail: issues-help@lucene.apache.org