You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by gu...@apache.org on 2023/09/22 05:33:08 UTC

[lucene] branch main updated: Use radix sort to speed up the sorting of deleted terms (#12573)

This is an automated email from the ASF dual-hosted git repository.

guofeng pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/lucene.git


The following commit(s) were added to refs/heads/main by this push:
     new 8b84f6c0965 Use radix sort to speed up the sorting of deleted terms (#12573)
8b84f6c0965 is described below

commit 8b84f6c0965dda01514c196126ed10e57cb6d01a
Author: gf2121 <52...@users.noreply.github.com>
AuthorDate: Fri Sep 22 00:33:01 2023 -0500

    Use radix sort to speed up the sorting of deleted terms (#12573)
---
 lucene/CHANGES.txt                                 |   2 +
 .../org/apache/lucene/index/BufferedUpdates.java   | 202 ++++++++++++++++++---
 .../apache/lucene/index/FreqProxTermsWriter.java   |  41 ++---
 .../apache/lucene/index/FrozenBufferedUpdates.java |   8 +-
 .../apache/lucene/index/TestBufferedUpdates.java   |  49 ++++-
 .../index/TestDocumentsWriterDeleteQueue.java      |   3 +-
 .../apache/lucene/index/TestIndexWriterDelete.java |   2 +-
 7 files changed, 246 insertions(+), 61 deletions(-)

diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index fc1ef72507e..f09161a19d6 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -150,6 +150,8 @@ Optimizations
 ---------------------
 * GITHUB#12183: Make TermStates#build concurrent. (Shubham Chaudhary)
 
+* GITHUB#12573: Use radix sort to speed up the sorting of deleted terms. (Guo Feng)
+
 Changes in runtime behavior
 ---------------------
 
diff --git a/lucene/core/src/java/org/apache/lucene/index/BufferedUpdates.java b/lucene/core/src/java/org/apache/lucene/index/BufferedUpdates.java
index 1c1eddf89d1..f6a30e3e733 100644
--- a/lucene/core/src/java/org/apache/lucene/index/BufferedUpdates.java
+++ b/lucene/core/src/java/org/apache/lucene/index/BufferedUpdates.java
@@ -16,13 +16,22 @@
  */
 package org.apache.lucene.index;
 
+import java.util.ArrayList;
 import java.util.HashMap;
+import java.util.HashSet;
+import java.util.List;
 import java.util.Map;
+import java.util.Set;
 import java.util.concurrent.atomic.AtomicInteger;
+import java.util.stream.Collectors;
 import org.apache.lucene.index.DocValuesUpdate.BinaryDocValuesUpdate;
 import org.apache.lucene.index.DocValuesUpdate.NumericDocValuesUpdate;
 import org.apache.lucene.search.Query;
 import org.apache.lucene.util.Accountable;
+import org.apache.lucene.util.ArrayUtil;
+import org.apache.lucene.util.ByteBlockPool;
+import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.BytesRefHash;
 import org.apache.lucene.util.Counter;
 import org.apache.lucene.util.RamUsageEstimator;
 
@@ -39,21 +48,6 @@ import org.apache.lucene.util.RamUsageEstimator;
 
 class BufferedUpdates implements Accountable {
 
-  /* Rough logic: HashMap has an array[Entry] w/ varying
-  load factor (say 2 * POINTER).  Entry is object w/ Term
-  key, Integer val, int hash, Entry next
-  (OBJ_HEADER + 3*POINTER + INT).  Term is object w/
-  String field and String text (OBJ_HEADER + 2*POINTER).
-  Term's field is String (OBJ_HEADER + 4*INT + POINTER +
-  OBJ_HEADER + string.length*CHAR).
-  Term's text is String (OBJ_HEADER + 4*INT + POINTER +
-  OBJ_HEADER + string.length*CHAR).  Integer is
-  OBJ_HEADER + INT. */
-  static final int BYTES_PER_DEL_TERM =
-      9 * RamUsageEstimator.NUM_BYTES_OBJECT_REF
-          + 7 * RamUsageEstimator.NUM_BYTES_OBJECT_HEADER
-          + 10 * Integer.BYTES;
-
   /* Rough logic: HashMap has an array[Entry] w/ varying
   load factor (say 2 * POINTER).  Entry is object w/
   Query key, Integer val, int hash, Entry next
@@ -67,8 +61,7 @@ class BufferedUpdates implements Accountable {
   final AtomicInteger numTermDeletes = new AtomicInteger();
   final AtomicInteger numFieldUpdates = new AtomicInteger();
 
-  final Map<Term, Integer> deleteTerms =
-      new HashMap<>(); // TODO cut this over to FieldUpdatesBuffer
+  final DeletedTerms deleteTerms = new DeletedTerms();
   final Map<Query, Integer> deleteQueries = new HashMap<>();
 
   final Map<String, FieldUpdatesBuffer> fieldUpdates = new HashMap<>();
@@ -77,7 +70,6 @@ class BufferedUpdates implements Accountable {
 
   private final Counter bytesUsed = Counter.newCounter(true);
   final Counter fieldUpdatesBytesUsed = Counter.newCounter(true);
-  private final Counter termsBytesUsed = Counter.newCounter(true);
 
   private static final boolean VERBOSE_DELETES = false;
 
@@ -127,8 +119,8 @@ class BufferedUpdates implements Accountable {
   }
 
   public void addTerm(Term term, int docIDUpto) {
-    Integer current = deleteTerms.get(term);
-    if (current != null && docIDUpto < current) {
+    int current = deleteTerms.get(term);
+    if (current != -1 && docIDUpto < current) {
       // Only record the new number if it's greater than the
       // current one.  This is important because if multiple
       // threads are replacing the same doc at nearly the
@@ -139,15 +131,11 @@ class BufferedUpdates implements Accountable {
       return;
     }
 
-    deleteTerms.put(term, Integer.valueOf(docIDUpto));
-    // note that if current != null then it means there's already a buffered
+    deleteTerms.put(term, docIDUpto);
+    // note that if current != -1 then it means there's already a buffered
     // delete on that term, therefore we seem to over-count. this over-counting
     // is done to respect IndexWriterConfig.setMaxBufferedDeleteTerms.
     numTermDeletes.incrementAndGet();
-    if (current == null) {
-      termsBytesUsed.addAndGet(
-          BYTES_PER_DEL_TERM + term.bytes.length + (Character.BYTES * term.field().length()));
-    }
   }
 
   void addNumericUpdate(NumericDocValuesUpdate update, int docIDUpto) {
@@ -176,7 +164,6 @@ class BufferedUpdates implements Accountable {
 
   void clearDeleteTerms() {
     numTermDeletes.set(0);
-    termsBytesUsed.addAndGet(-termsBytesUsed.get());
     deleteTerms.clear();
   }
 
@@ -188,7 +175,6 @@ class BufferedUpdates implements Accountable {
     fieldUpdates.clear();
     bytesUsed.addAndGet(-bytesUsed.get());
     fieldUpdatesBytesUsed.addAndGet(-fieldUpdatesBytesUsed.get());
-    termsBytesUsed.addAndGet(-termsBytesUsed.get());
   }
 
   boolean any() {
@@ -197,6 +183,164 @@ class BufferedUpdates implements Accountable {
 
   @Override
   public long ramBytesUsed() {
-    return bytesUsed.get() + fieldUpdatesBytesUsed.get() + termsBytesUsed.get();
+    return bytesUsed.get() + fieldUpdatesBytesUsed.get() + deleteTerms.ramBytesUsed();
+  }
+
+  static class DeletedTerms implements Accountable {
+
+    private final Counter bytesUsed = Counter.newCounter();
+    private final ByteBlockPool pool =
+        new ByteBlockPool(new ByteBlockPool.DirectTrackingAllocator(bytesUsed));
+    private final Map<String, BytesRefIntMap> deleteTerms = new HashMap<>();
+    private int termsSize = 0;
+
+    DeletedTerms() {}
+
+    /**
+     * Get the newest doc id of the deleted term.
+     *
+     * @param term The deleted term.
+     * @return The newest doc id of this deleted term.
+     */
+    int get(Term term) {
+      BytesRefIntMap hash = deleteTerms.get(term.field);
+      if (hash == null) {
+        return -1;
+      }
+      return hash.get(term.bytes);
+    }
+
+    /**
+     * Put the newest doc id of the deleted term.
+     *
+     * @param term The deleted term.
+     * @param value The newest doc id of the deleted term.
+     */
+    void put(Term term, int value) {
+      BytesRefIntMap hash =
+          deleteTerms.computeIfAbsent(
+              term.field,
+              k -> {
+                bytesUsed.addAndGet(RamUsageEstimator.sizeOf(term.field));
+                return new BytesRefIntMap(pool, bytesUsed);
+              });
+      if (hash.put(term.bytes, value)) {
+        termsSize++;
+      }
+    }
+
+    void clear() {
+      bytesUsed.addAndGet(-bytesUsed.get());
+      deleteTerms.clear();
+      termsSize = 0;
+    }
+
+    int size() {
+      return termsSize;
+    }
+
+    boolean isEmpty() {
+      return termsSize == 0;
+    }
+
+    /** Just for test, not efficient. */
+    Set<Term> keySet() {
+      return deleteTerms.entrySet().stream()
+          .flatMap(
+              entry -> entry.getValue().keySet().stream().map(b -> new Term(entry.getKey(), b)))
+          .collect(Collectors.toSet());
+    }
+
+    interface DeletedTermConsumer<E extends Exception> {
+      void accept(Term term, int docId) throws E;
+    }
+
+    /**
+     * Consume all terms in a sorted order.
+     *
+     * <p>Note: This is a destructive operation as it calls {@link BytesRefHash#sort()}.
+     *
+     * @see BytesRefHash#sort
+     */
+    <E extends Exception> void forEachOrdered(DeletedTermConsumer<E> consumer) throws E {
+      List<Map.Entry<String, BytesRefIntMap>> deleteFields =
+          new ArrayList<>(deleteTerms.entrySet());
+      deleteFields.sort(Map.Entry.comparingByKey());
+      Term scratch = new Term("", new BytesRef());
+      for (Map.Entry<String, BufferedUpdates.BytesRefIntMap> deleteFieldEntry : deleteFields) {
+        scratch.field = deleteFieldEntry.getKey();
+        BufferedUpdates.BytesRefIntMap terms = deleteFieldEntry.getValue();
+        int[] indices = terms.bytesRefHash.sort();
+        for (int index : indices) {
+          if (index != -1) {
+            terms.bytesRefHash.get(index, scratch.bytes);
+            consumer.accept(scratch, terms.values[index]);
+          }
+        }
+      }
+    }
+
+    @Override
+    public long ramBytesUsed() {
+      return bytesUsed.get();
+    }
+  }
+
+  private static class BytesRefIntMap {
+
+    private static final long INIT_RAM_BYTES =
+        RamUsageEstimator.shallowSizeOf(BytesRefIntMap.class)
+            + RamUsageEstimator.shallowSizeOf(BytesRefHash.class)
+            + RamUsageEstimator.sizeOf(new int[BytesRefHash.DEFAULT_CAPACITY]);
+
+    private final Counter counter;
+    private final BytesRefHash bytesRefHash;
+    private int[] values;
+
+    private BytesRefIntMap(ByteBlockPool pool, Counter counter) {
+      this.counter = counter;
+      this.bytesRefHash =
+          new BytesRefHash(
+              pool,
+              BytesRefHash.DEFAULT_CAPACITY,
+              new BytesRefHash.DirectBytesStartArray(BytesRefHash.DEFAULT_CAPACITY, counter));
+      this.values = new int[BytesRefHash.DEFAULT_CAPACITY];
+      counter.addAndGet(INIT_RAM_BYTES);
+    }
+
+    private Set<BytesRef> keySet() {
+      BytesRef scratch = new BytesRef();
+      Set<BytesRef> set = new HashSet<>();
+      for (int i = 0; i < bytesRefHash.size(); i++) {
+        bytesRefHash.get(i, scratch);
+        set.add(BytesRef.deepCopyOf(scratch));
+      }
+      return set;
+    }
+
+    private boolean put(BytesRef key, int value) {
+      assert value >= 0;
+      int e = bytesRefHash.add(key);
+      if (e < 0) {
+        values[-e - 1] = value;
+        return false;
+      } else {
+        if (e >= values.length) {
+          int originLength = values.length;
+          values = ArrayUtil.grow(values, e + 1);
+          counter.addAndGet((long) (values.length - originLength) * Integer.BYTES);
+        }
+        values[e] = value;
+        return true;
+      }
+    }
+
+    private int get(BytesRef key) {
+      int e = bytesRefHash.find(key);
+      if (e == -1) {
+        return -1;
+      }
+      return values[e];
+    }
   }
 }
diff --git a/lucene/core/src/java/org/apache/lucene/index/FreqProxTermsWriter.java b/lucene/core/src/java/org/apache/lucene/index/FreqProxTermsWriter.java
index c178b5aa63b..f04096c78cf 100644
--- a/lucene/core/src/java/org/apache/lucene/index/FreqProxTermsWriter.java
+++ b/lucene/core/src/java/org/apache/lucene/index/FreqProxTermsWriter.java
@@ -18,7 +18,6 @@ package org.apache.lucene.index;
 
 import java.io.IOException;
 import java.util.ArrayList;
-import java.util.Collections;
 import java.util.List;
 import java.util.Map;
 import org.apache.lucene.codecs.FieldsConsumer;
@@ -55,29 +54,29 @@ final class FreqProxTermsWriter extends TermsHash {
     // Process any pending Term deletes for this newly
     // flushed segment:
     if (state.segUpdates != null && state.segUpdates.deleteTerms.size() > 0) {
-      Map<Term, Integer> segDeletes = state.segUpdates.deleteTerms;
-      List<Term> deleteTerms = new ArrayList<>(segDeletes.keySet());
-      Collections.sort(deleteTerms);
+
+      BufferedUpdates.DeletedTerms segDeletes = state.segUpdates.deleteTerms;
       FrozenBufferedUpdates.TermDocsIterator iterator =
           new FrozenBufferedUpdates.TermDocsIterator(fields, true);
-      for (Term deleteTerm : deleteTerms) {
-        DocIdSetIterator postings = iterator.nextTerm(deleteTerm.field(), deleteTerm.bytes());
-        if (postings != null) {
-          int delDocLimit = segDeletes.get(deleteTerm);
-          assert delDocLimit < PostingsEnum.NO_MORE_DOCS;
-          int doc;
-          while ((doc = postings.nextDoc()) < delDocLimit) {
-            if (state.liveDocs == null) {
-              state.liveDocs = new FixedBitSet(state.segmentInfo.maxDoc());
-              state.liveDocs.set(0, state.segmentInfo.maxDoc());
-            }
-            if (state.liveDocs.get(doc)) {
-              state.delCountOnFlush++;
-              state.liveDocs.clear(doc);
+
+      segDeletes.forEachOrdered(
+          (term, docId) -> {
+            DocIdSetIterator postings = iterator.nextTerm(term.field(), term.bytes());
+            if (postings != null) {
+              assert docId < PostingsEnum.NO_MORE_DOCS;
+              int doc;
+              while ((doc = postings.nextDoc()) < docId) {
+                if (state.liveDocs == null) {
+                  state.liveDocs = new FixedBitSet(state.segmentInfo.maxDoc());
+                  state.liveDocs.set(0, state.segmentInfo.maxDoc());
+                }
+                if (state.liveDocs.get(doc)) {
+                  state.delCountOnFlush++;
+                  state.liveDocs.clear(doc);
+                }
+              }
             }
-          }
-        }
-      }
+          });
     }
   }
 
diff --git a/lucene/core/src/java/org/apache/lucene/index/FrozenBufferedUpdates.java b/lucene/core/src/java/org/apache/lucene/index/FrozenBufferedUpdates.java
index dbeaf98e83c..363b2e17df7 100644
--- a/lucene/core/src/java/org/apache/lucene/index/FrozenBufferedUpdates.java
+++ b/lucene/core/src/java/org/apache/lucene/index/FrozenBufferedUpdates.java
@@ -31,7 +31,6 @@ import org.apache.lucene.search.Query;
 import org.apache.lucene.search.ScoreMode;
 import org.apache.lucene.search.Scorer;
 import org.apache.lucene.search.Weight;
-import org.apache.lucene.util.ArrayUtil;
 import org.apache.lucene.util.Bits;
 import org.apache.lucene.util.BytesRef;
 import org.apache.lucene.util.InfoStream;
@@ -86,12 +85,9 @@ final class FrozenBufferedUpdates {
     this.privateSegment = privateSegment;
     assert privateSegment == null || updates.deleteTerms.isEmpty()
         : "segment private packet should only have del queries";
-    Term[] termsArray = updates.deleteTerms.keySet().toArray(new Term[updates.deleteTerms.size()]);
-    ArrayUtil.timSort(termsArray);
+
     PrefixCodedTerms.Builder builder = new PrefixCodedTerms.Builder();
-    for (Term term : termsArray) {
-      builder.add(term);
-    }
+    updates.deleteTerms.forEachOrdered((term, doc) -> builder.add(term));
     deleteTerms = builder.finish();
 
     deleteQueries = new Query[updates.deleteQueries.size()];
diff --git a/lucene/core/src/test/org/apache/lucene/index/TestBufferedUpdates.java b/lucene/core/src/test/org/apache/lucene/index/TestBufferedUpdates.java
index 8fb59602981..af24088e4aa 100644
--- a/lucene/core/src/test/org/apache/lucene/index/TestBufferedUpdates.java
+++ b/lucene/core/src/test/org/apache/lucene/index/TestBufferedUpdates.java
@@ -16,8 +16,13 @@
  */
 package org.apache.lucene.index;
 
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.List;
+import java.util.Map;
 import org.apache.lucene.search.TermQuery;
 import org.apache.lucene.tests.util.LuceneTestCase;
+import org.apache.lucene.util.BytesRef;
 
 /** Unit test for {@link BufferedUpdates} */
 public class TestBufferedUpdates extends LuceneTestCase {
@@ -28,14 +33,14 @@ public class TestBufferedUpdates extends LuceneTestCase {
     assertFalse(bu.any());
     int queries = atLeast(1);
     for (int i = 0; i < queries; i++) {
-      final int docIDUpto = random().nextBoolean() ? Integer.MAX_VALUE : random().nextInt();
+      final int docIDUpto = random().nextBoolean() ? Integer.MAX_VALUE : random().nextInt(100000);
       final Term term = new Term("id", Integer.toString(random().nextInt(100)));
       bu.addQuery(new TermQuery(term), docIDUpto);
     }
 
     int terms = atLeast(1);
     for (int i = 0; i < terms; i++) {
-      final int docIDUpto = random().nextBoolean() ? Integer.MAX_VALUE : random().nextInt();
+      final int docIDUpto = random().nextBoolean() ? Integer.MAX_VALUE : random().nextInt(100000);
       final Term term = new Term("id", Integer.toString(random().nextInt(100)));
       bu.addTerm(term, docIDUpto);
     }
@@ -52,4 +57,44 @@ public class TestBufferedUpdates extends LuceneTestCase {
     assertFalse(bu.any());
     assertEquals(bu.ramBytesUsed(), 0L);
   }
+
+  public void testDeletedTerms() {
+    int iters = atLeast(10);
+    String[] fields = new String[] {"a", "b", "c"};
+    for (int iter = 0; iter < iters; iter++) {
+
+      Map<Term, Integer> expected = new HashMap<>();
+      BufferedUpdates.DeletedTerms actual = new BufferedUpdates.DeletedTerms();
+      assertTrue(actual.isEmpty());
+
+      int termCount = atLeast(5000);
+      int maxBytesNum = random().nextInt(3) + 1;
+      for (int i = 0; i < termCount; i++) {
+        int byteNum = random().nextInt(maxBytesNum) + 1;
+        byte[] bytes = new byte[byteNum];
+        random().nextBytes(bytes);
+        Term term = new Term(fields[random().nextInt(fields.length)], new BytesRef(bytes));
+        int value = random().nextInt(10000000);
+        expected.put(term, value);
+        actual.put(term, value);
+      }
+
+      assertEquals(expected.size(), actual.size());
+
+      for (Map.Entry<Term, Integer> entry : expected.entrySet()) {
+        assertEquals(entry.getValue(), Integer.valueOf(actual.get(entry.getKey())));
+      }
+
+      List<Map.Entry<Term, Integer>> expectedSorted =
+          expected.entrySet().stream().sorted(Map.Entry.comparingByKey()).toList();
+      List<Map.Entry<Term, Integer>> actualSorted = new ArrayList<>();
+      actual.forEachOrdered(
+          ((term, docId) -> {
+            Term copy = new Term(term.field, BytesRef.deepCopyOf(term.bytes));
+            actualSorted.add(Map.entry(copy, docId));
+          }));
+
+      assertEquals(expectedSorted, actualSorted);
+    }
+  }
 }
diff --git a/lucene/core/src/test/org/apache/lucene/index/TestDocumentsWriterDeleteQueue.java b/lucene/core/src/test/org/apache/lucene/index/TestDocumentsWriterDeleteQueue.java
index 828792784b8..95368c5c6ad 100644
--- a/lucene/core/src/test/org/apache/lucene/index/TestDocumentsWriterDeleteQueue.java
+++ b/lucene/core/src/test/org/apache/lucene/index/TestDocumentsWriterDeleteQueue.java
@@ -84,8 +84,7 @@ public class TestDocumentsWriterDeleteQueue extends LuceneTestCase {
 
   private void assertAllBetween(int start, int end, BufferedUpdates deletes, Integer[] ids) {
     for (int i = start; i <= end; i++) {
-      assertEquals(
-          Integer.valueOf(end), deletes.deleteTerms.get(new Term("id", ids[i].toString())));
+      assertEquals(end, deletes.deleteTerms.get(new Term("id", ids[i].toString())));
     }
   }
 
diff --git a/lucene/core/src/test/org/apache/lucene/index/TestIndexWriterDelete.java b/lucene/core/src/test/org/apache/lucene/index/TestIndexWriterDelete.java
index 1fe44c7271e..4e9d96a49c8 100644
--- a/lucene/core/src/test/org/apache/lucene/index/TestIndexWriterDelete.java
+++ b/lucene/core/src/test/org/apache/lucene/index/TestIndexWriterDelete.java
@@ -1158,7 +1158,7 @@ public class TestIndexWriterDelete extends LuceneTestCase {
         new IndexWriter(
             dir,
             newIndexWriterConfig(new MockAnalyzer(random()))
-                .setRAMBufferSizeMB(0.1f)
+                .setRAMBufferSizeMB(0.5f)
                 .setMaxBufferedDocs(1000)
                 .setMergePolicy(NoMergePolicy.INSTANCE)
                 .setReaderPooling(false));