You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by ma...@apache.org on 2020/10/06 17:27:09 UTC
[lucene-solr] branch branch_8x updated (e7bf2dc -> 66c49a3)
This is an automated email from the ASF dual-hosted git repository.
mayya pushed a change to branch branch_8x
in repository https://gitbox.apache.org/repos/asf/lucene-solr.git.
from e7bf2dc LUCENE-9555: Advance conjunction Iterator for two phase iteration (#1943)
new 16d25ac LUCENE-9565 Fix competitive iteration (#1952)
new 66c49a3 LUCENE-9541 ConjunctionDISI sub-iterators check (#1937)
The 2 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails. The revisions
listed as "add" were already present in the repository and have only
been added to this reference.
Summary of changes:
.../org/apache/lucene/search/ConjunctionDISI.java | 36 ++++++++++++++
.../src/java/org/apache/lucene/search/Weight.java | 55 ++++++++++++++++++++--
.../lucene/search/comparators/DocComparator.java | 8 ++--
.../search/comparators/NumericComparator.java | 8 ++--
.../apache/lucene/search/TestConjunctionDISI.java | 19 +++++++-
5 files changed, 116 insertions(+), 10 deletions(-)
[lucene-solr] 01/02: LUCENE-9565 Fix competitive iteration (#1952)
Posted by ma...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
mayya pushed a commit to branch branch_8x
in repository https://gitbox.apache.org/repos/asf/lucene-solr.git
commit 16d25ace3f4c273d45284c0e7ebf9915b245995a
Author: Mayya Sharipova <ma...@elastic.co>
AuthorDate: Tue Oct 6 13:22:16 2020 -0400
LUCENE-9565 Fix competitive iteration (#1952)
PR #1351 introduced a sort optimization where documents can be skipped.
But iteration over competitive iterators was not properly organized,
as they were not storing the current docID, and
when competitive iterator was updated the current doc ID was lost.
This patch fixed it.
Relates to #1351
---
.../src/java/org/apache/lucene/search/Weight.java | 55 ++++++++++++++++++++--
.../lucene/search/comparators/DocComparator.java | 8 ++--
.../search/comparators/NumericComparator.java | 8 ++--
3 files changed, 62 insertions(+), 9 deletions(-)
diff --git a/lucene/core/src/java/org/apache/lucene/search/Weight.java b/lucene/core/src/java/org/apache/lucene/search/Weight.java
index d2a0428..75acefe 100644
--- a/lucene/core/src/java/org/apache/lucene/search/Weight.java
+++ b/lucene/core/src/java/org/apache/lucene/search/Weight.java
@@ -217,9 +217,17 @@ public abstract class Weight implements SegmentCacheable {
collector.setScorer(scorer);
DocIdSetIterator scorerIterator = twoPhase == null ? iterator : twoPhase.approximation();
DocIdSetIterator collectorIterator = collector.competitiveIterator();
- // if possible filter scorerIterator to keep only competitive docs as defined by collector
- DocIdSetIterator filteredIterator = collectorIterator == null ? scorerIterator :
- ConjunctionDISI.intersectIterators(Arrays.asList(scorerIterator, collectorIterator));
+ DocIdSetIterator filteredIterator;
+ if (collectorIterator == null) {
+ filteredIterator = scorerIterator;
+ } else {
+ if (scorerIterator.docID() != -1) {
+ // Wrap ScorerIterator to start from -1 for conjunction
+ scorerIterator = new RangeDISIWrapper(scorerIterator, max);
+ }
+ // filter scorerIterator to keep only competitive docs as defined by collector
+ filteredIterator = ConjunctionDISI.intersectIterators(Arrays.asList(scorerIterator, collectorIterator));
+ }
if (filteredIterator.docID() == -1 && min == 0 && max == DocIdSetIterator.NO_MORE_DOCS) {
scoreAll(collector, filteredIterator, twoPhase, acceptDocs);
return DocIdSetIterator.NO_MORE_DOCS;
@@ -279,4 +287,45 @@ public abstract class Weight implements SegmentCacheable {
}
}
+ /**
+ * Wraps an internal docIdSetIterator for it to start with docID = -1
+ */
+ protected static class RangeDISIWrapper extends DocIdSetIterator {
+ private final DocIdSetIterator in;
+ private final int min;
+ private final int max;
+ private int docID = -1;
+
+ public RangeDISIWrapper(DocIdSetIterator in, int max) {
+ this.in = in;
+ this.min = in.docID();
+ this.max = max;
+ }
+
+ @Override
+ public int docID() {
+ return docID;
+ }
+
+ @Override
+ public int nextDoc() throws IOException {
+ return advance(docID + 1);
+ }
+
+ @Override
+ public int advance(int target) throws IOException {
+ target = Math.max(min, target);
+ if (target >= max) {
+ return docID = NO_MORE_DOCS;
+ }
+ return docID = in.advance(target);
+ }
+
+ @Override
+ public long cost() {
+ return Math.min(max - min, in.cost());
+ }
+
+ }
+
}
diff --git a/lucene/core/src/java/org/apache/lucene/search/comparators/DocComparator.java b/lucene/core/src/java/org/apache/lucene/search/comparators/DocComparator.java
index 8974ca6..c0b3e2e 100644
--- a/lucene/core/src/java/org/apache/lucene/search/comparators/DocComparator.java
+++ b/lucene/core/src/java/org/apache/lucene/search/comparators/DocComparator.java
@@ -133,14 +133,16 @@ public class DocComparator extends FieldComparator<Integer> {
return null;
} else {
return new DocIdSetIterator() {
+ private int docID = -1;
+
@Override
public int nextDoc() throws IOException {
- return competitiveIterator.nextDoc();
+ return advance(docID + 1);
}
@Override
public int docID() {
- return competitiveIterator.docID();
+ return docID;
}
@Override
@@ -150,7 +152,7 @@ public class DocComparator extends FieldComparator<Integer> {
@Override
public int advance(int target) throws IOException {
- return competitiveIterator.advance(target);
+ return docID = competitiveIterator.advance(target);
}
};
}
diff --git a/lucene/core/src/java/org/apache/lucene/search/comparators/NumericComparator.java b/lucene/core/src/java/org/apache/lucene/search/comparators/NumericComparator.java
index 7f62f66..7ed7511 100644
--- a/lucene/core/src/java/org/apache/lucene/search/comparators/NumericComparator.java
+++ b/lucene/core/src/java/org/apache/lucene/search/comparators/NumericComparator.java
@@ -228,14 +228,16 @@ public abstract class NumericComparator<T extends Number> extends FieldComparato
public DocIdSetIterator competitiveIterator() {
if (enableSkipping == false) return null;
return new DocIdSetIterator() {
+ private int docID = -1;
+
@Override
public int nextDoc() throws IOException {
- return competitiveIterator.nextDoc();
+ return advance(docID + 1);
}
@Override
public int docID() {
- return competitiveIterator.docID();
+ return docID;
}
@Override
@@ -245,7 +247,7 @@ public abstract class NumericComparator<T extends Number> extends FieldComparato
@Override
public int advance(int target) throws IOException {
- return competitiveIterator.advance(target);
+ return docID = competitiveIterator.advance(target);
}
};
}
[lucene-solr] 02/02: LUCENE-9541 ConjunctionDISI sub-iterators
check (#1937)
Posted by ma...@apache.org.
This is an automated email from the ASF dual-hosted git repository.
mayya pushed a commit to branch branch_8x
in repository https://gitbox.apache.org/repos/asf/lucene-solr.git
commit 66c49a354023a6e77b67839cc59a1e499fcd6536
Author: Mayya Sharipova <ma...@elastic.co>
AuthorDate: Mon Oct 5 09:38:17 2020 -0400
LUCENE-9541 ConjunctionDISI sub-iterators check (#1937)
Ensure sub-iterators of a conjunction iterator are on the same doc.
---
.../org/apache/lucene/search/ConjunctionDISI.java | 36 ++++++++++++++++++++++
.../apache/lucene/search/TestConjunctionDISI.java | 19 +++++++++++-
2 files changed, 54 insertions(+), 1 deletion(-)
diff --git a/lucene/core/src/java/org/apache/lucene/search/ConjunctionDISI.java b/lucene/core/src/java/org/apache/lucene/search/ConjunctionDISI.java
index 780e854..30bdabb 100644
--- a/lucene/core/src/java/org/apache/lucene/search/ConjunctionDISI.java
+++ b/lucene/core/src/java/org/apache/lucene/search/ConjunctionDISI.java
@@ -31,6 +31,7 @@ import org.apache.lucene.util.BitSetIterator;
import org.apache.lucene.util.CollectionUtil;
/** A conjunction of DocIdSetIterators.
+ * Requires that all of its sub-iterators must be on the same document all the time.
* This iterates over the doc ids that are present in each given DocIdSetIterator.
* <br>Public only for use in {@link org.apache.lucene.search.spans}.
* @lucene.internal
@@ -140,6 +141,15 @@ public final class ConjunctionDISI extends DocIdSetIterator {
private static DocIdSetIterator createConjunction(
List<DocIdSetIterator> allIterators,
List<TwoPhaseIterator> twoPhaseIterators) {
+
+ // check that all sub-iterators are on the same doc ID
+ int curDoc = allIterators.size() > 0 ? allIterators.get(0).docID() : twoPhaseIterators.get(0).approximation.docID();
+ boolean iteratorsOnTheSameDoc = allIterators.stream().allMatch(it -> it.docID() == curDoc);
+ iteratorsOnTheSameDoc = iteratorsOnTheSameDoc && twoPhaseIterators.stream().allMatch(it -> it.approximation().docID() == curDoc);
+ if (iteratorsOnTheSameDoc == false) {
+ throw new IllegalArgumentException("Sub-iterators of ConjunctionDISI are not on the same document!");
+ }
+
long minCost = allIterators.stream().mapToLong(DocIdSetIterator::cost).min().getAsLong();
List<BitSetIterator> bitSetIterators = new ArrayList<>();
List<DocIdSetIterator> iterators = new ArrayList<>();
@@ -177,6 +187,7 @@ public final class ConjunctionDISI extends DocIdSetIterator {
private ConjunctionDISI(List<? extends DocIdSetIterator> iterators) {
assert iterators.size() >= 2;
+
// Sort the array the first time to allow the least frequent DocsEnum to
// lead the matching.
CollectionUtil.timSort(iterators, new Comparator<DocIdSetIterator>() {
@@ -227,6 +238,7 @@ public final class ConjunctionDISI extends DocIdSetIterator {
@Override
public int advance(int target) throws IOException {
+ assert assertItersOnSameDoc() : "Sub-iterators of ConjunctionDISI are not one the same document!";
return doNext(lead1.advance(target));
}
@@ -237,6 +249,7 @@ public final class ConjunctionDISI extends DocIdSetIterator {
@Override
public int nextDoc() throws IOException {
+ assert assertItersOnSameDoc() : "Sub-iterators of ConjunctionDISI are not on the same document!";
return doNext(lead1.nextDoc());
}
@@ -245,6 +258,16 @@ public final class ConjunctionDISI extends DocIdSetIterator {
return lead1.cost(); // overestimate
}
+ // Returns {@code true} if all sub-iterators are on the same doc ID, {@code false} otherwise
+ private boolean assertItersOnSameDoc() {
+ int curDoc = lead1.docID();
+ boolean iteratorsOnTheSameDoc = (lead2.docID() == curDoc);
+ for (int i = 0; (i < others.length && iteratorsOnTheSameDoc); i++) {
+ iteratorsOnTheSameDoc = iteratorsOnTheSameDoc && (others[i].docID() == curDoc);
+ }
+ return iteratorsOnTheSameDoc;
+ }
+
/** Conjunction between a {@link DocIdSetIterator} and one or more {@link BitSetIterator}s. */
private static class BitSetConjunctionDISI extends DocIdSetIterator {
@@ -256,6 +279,7 @@ public final class ConjunctionDISI extends DocIdSetIterator {
BitSetConjunctionDISI(DocIdSetIterator lead, Collection<BitSetIterator> bitSetIterators) {
this.lead = lead;
assert bitSetIterators.size() > 0;
+
this.bitSetIterators = bitSetIterators.toArray(new BitSetIterator[0]);
// Put the least costly iterators first so that we exit as soon as possible
ArrayUtil.timSort(this.bitSetIterators, (a, b) -> Long.compare(a.cost(), b.cost()));
@@ -276,11 +300,13 @@ public final class ConjunctionDISI extends DocIdSetIterator {
@Override
public int nextDoc() throws IOException {
+ assert assertItersOnSameDoc() : "Sub-iterators of ConjunctionDISI are not on the same document!";
return doNext(lead.nextDoc());
}
@Override
public int advance(int target) throws IOException {
+ assert assertItersOnSameDoc() : "Sub-iterators of ConjunctionDISI are not on the same document!";
return doNext(lead.advance(target));
}
@@ -306,6 +332,16 @@ public final class ConjunctionDISI extends DocIdSetIterator {
return lead.cost();
}
+ // Returns {@code true} if all sub-iterators are on the same doc ID, {@code false} otherwise
+ private boolean assertItersOnSameDoc() {
+ int curDoc = lead.docID();
+ boolean iteratorsOnTheSameDoc = true;
+ for (int i = 0; (i < bitSetIterators.length && iteratorsOnTheSameDoc); i++) {
+ iteratorsOnTheSameDoc = iteratorsOnTheSameDoc && (bitSetIterators[i].docID() == curDoc);
+ }
+ return iteratorsOnTheSameDoc;
+ }
+
}
/**
diff --git a/lucene/core/src/test/org/apache/lucene/search/TestConjunctionDISI.java b/lucene/core/src/test/org/apache/lucene/search/TestConjunctionDISI.java
index a9fd287..853411e 100644
--- a/lucene/core/src/test/org/apache/lucene/search/TestConjunctionDISI.java
+++ b/lucene/core/src/test/org/apache/lucene/search/TestConjunctionDISI.java
@@ -43,7 +43,7 @@ public class TestConjunctionDISI extends LuceneTestCase {
return new TwoPhaseIterator(approximation) {
@Override
- public boolean matches() throws IOException {
+ public boolean matches() {
return confirmed.get(approximation.docID());
}
@@ -398,4 +398,21 @@ public class TestConjunctionDISI extends LuceneTestCase {
public void testCollapseSubConjunctionScorers() throws IOException {
testCollapseSubConjunctions(true);
}
+
+ public void testIllegalAdvancementOfSubIteratorsTripsAssertion() throws IOException {
+ assumeTrue("Assertions must be enabled for this test!", LuceneTestCase.assertsAreEnabled);
+ int maxDoc = 100;
+ final int numIterators = TestUtil.nextInt(random(), 2, 5);
+ FixedBitSet set = randomSet(maxDoc);
+
+ DocIdSetIterator[] iterators = new DocIdSetIterator[numIterators];
+ for (int i = 0; i < iterators.length; ++i) {
+ iterators[i] = new BitDocIdSet(set).iterator();
+ }
+ final DocIdSetIterator conjunction = ConjunctionDISI.intersectIterators(Arrays.asList(iterators));
+ int idx = TestUtil.nextInt(random() , 0, iterators.length-1);
+ iterators[idx].nextDoc(); // illegally advancing one of the sub-iterators outside of the conjunction iterator
+ AssertionError ex = expectThrows(AssertionError.class, () -> conjunction.nextDoc());
+ assertEquals("Sub-iterators of ConjunctionDISI are not on the same document!", ex.getMessage());
+ }
}