jimczi commented on a change in pull request #1725:
URL: https://github.com/apache/lucene-solr/pull/1725#discussion_r474232065
##########
File path: lucene/core/src/java/org/apache/lucene/search/FieldComparator.java
##########
@@ -136,6 +136,13 @@ public int compareValues(T first, T second) {
}
}
+ /**
+ * Informs the comparator that sorting is done in reverse.
+ * This is necessary only for skipping functionality.
+ */
+ public void setReverse() {
Review comment:
I don't understand why this function is needed ? Can't you just pass the
information when the `DocComparator` is created in the SortField ?
##########
File path:
lucene/core/src/java/org/apache/lucene/search/FilteringLeafFieldComparator.java
##########
@@ -32,8 +33,22 @@
DocIdSetIterator competitiveIterator() throws IOException;
/**
- * Informs this leaf comparator that it is allowed to start updating its
competitive iterator.
- * This method is called from a collector when queue becomes full and
threshold is reached.
+ * Informs this leaf comparator that hits threshold is reached.
+ * This method is called from a collector when hits threshold is reached.
+ * For some filtering comparators (e.g. {@code FilteringDocLeafComparator}
reaching
+ * hits threshold is enough to start updating their iterators, even when
queue is not yet full.
*/
- void setCanUpdateIterator() throws IOException;
+ void setHitsThresholdReached() throws IOException;
+
+ /**
+ * Informs this leaf comparator that queue has become full.
+ * This method is called from a collector when queue becomes full.
+ */
+ void setQueueFull() throws IOException;
Review comment:
That seems redundant. I think we can add a single method:
setHitsThresholdReached(int). We have all the other contexts needed in the
LeafFieldComparator. The complexity is that `setBottom `and
`setHitsThresholdReached(int)` are called on the leaves even though they are
global events. Maybe forcing the hierarchy of the filtering fields to use a
`SimpleFieldComparator` could simplify things ? This way you don't have to
repeat redundant informations (hits threshold and queue full) on each leave.
##########
File path:
lucene/core/src/java/org/apache/lucene/search/comparators/DocComparator.java
##########
@@ -0,0 +1,185 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.lucene.search.comparators;
+
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.search.FieldComparator;
+import org.apache.lucene.search.FilteringLeafFieldComparator;
+import org.apache.lucene.search.LeafFieldComparator;
+import org.apache.lucene.search.Scorable;
+
+import java.io.IOException;
+
+/**
+ * Comparator that sorts by asc _doc
+ */
+public class DocComparator extends FieldComparator<Integer> {
+ private final int[] docIDs;
+ private int topValue;
+ private boolean topValueSet;
+ private boolean reverse = false; // only used to check if skipping
functionality should be enabled
+
+ /** Creates a new comparator based on document ids for {@code numHits} */
+ public DocComparator(int numHits) {
+ docIDs = new int[numHits];
+ }
+
+ @Override
+ public int compare(int slot1, int slot2) {
+ // No overflow risk because docIDs are non-negative
+ return docIDs[slot1] - docIDs[slot2];
+ }
+
+
+ @Override
+ public LeafFieldComparator getLeafComparator(LeafReaderContext context) {
+ // TODO: can we "map" our docIDs to the current
+ // reader? saves having to then subtract on every
+ // compare call
+ return new DocLeafComparator(context);
+ }
+
+ @Override
+ public void setTopValue(Integer value) {
+ topValue = value;
+ topValueSet = true;
+ }
+
+ @Override
+ public Integer value(int slot) {
+ return Integer.valueOf(docIDs[slot]);
+ }
+
+ @Override
+ public void setReverse() {
+ reverse = true;
+ }
+
+
+ /**
+ * DocLeafComparator with skipping functionality.
+ * When sort by _doc asc and "after" document is set,
+ * the comparator provides an iterator that can quickly skip to the
desired "after" document.
+ */
+ private class DocLeafComparator implements FilteringLeafFieldComparator {
+ private final int docBase;
+ private int bottom;
+
+ private final boolean enableSkipping;
+ private final int minDoc;
+ private final int maxDoc;
+ private DocIdSetIterator topValueIterator; // iterator that starts
from topValue
+
+ private boolean iteratorUpdated = false;
+
+ public DocLeafComparator(LeafReaderContext context) {
+ this.docBase = context.docBase;
+ // skipping functionality is enabled if topValue is set and sort
is asc
+ this.enableSkipping = topValueSet && reverse == false ? true:
false;
+ if (enableSkipping) {
+ this.minDoc = topValue + 1;
+ this.maxDoc = context.reader().maxDoc();
+ this.topValueIterator = DocIdSetIterator.all(maxDoc);
+ } else {
+ this.minDoc = -1;
+ this.maxDoc = -1;
+ this.topValueIterator = null;
+ }
+ }
+
+ @Override
+ public void setBottom(int slot) {
+ bottom = docIDs[slot];
Review comment:
We should be able to early terminate here if the total hits threshold
has been reached. If it's not reached yet, we can early terminate later in
`setHitsThresholdReached`.
##########
File path: lucene/core/src/java/org/apache/lucene/search/TopFieldCollector.java
##########
@@ -150,11 +150,15 @@ public void setScorer(Scorable scorer) throws IOException
{
if (minScoreAcc != null) {
updateGlobalMinCompetitiveScore(scorer);
}
- if (filteringLeafComparator != null && queueFull &&
hitsThresholdChecker.isThresholdReached()) {
- // if queue became full and hitsThreshold was reached in previous
segments,
- // notify this segment's leaf comparator that its competitive iterator
can be updated
- filteringLeafComparator.setCanUpdateIterator();
- totalHitsRelation = TotalHits.Relation.GREATER_THAN_OR_EQUAL_TO;
+
+ if (filteringLeafComparator != null &&
hitsThresholdChecker.isThresholdReached()) {
+ // hitsThreshold was reached in previous segments, notify this
segment's leaf comparator about it
+ filteringLeafComparator.setHitsThresholdReached();
+ // if queue became full in previous segments, notify this segment's
leaf comparator about it
+ if (queueFull) filteringLeafComparator.setQueueFull();
+ if (filteringLeafComparator.iteratorUpdated()) {
+ totalHitsRelation = TotalHits.Relation.GREATER_THAN_OR_EQUAL_TO;
+ }
Review comment:
See my previous comment, I think we should call
`setHitsThresholdReached` once, when the threshold is reached.
Same for `setQueueFull` that is already call in `setBottom`. Said
differently, this part could be entirely removed ;).
##########
File path:
lucene/core/src/java/org/apache/lucene/search/FilteringLeafFieldComparator.java
##########
@@ -32,8 +33,22 @@
DocIdSetIterator competitiveIterator() throws IOException;
/**
- * Informs this leaf comparator that it is allowed to start updating its
competitive iterator.
- * This method is called from a collector when queue becomes full and
threshold is reached.
+ * Informs this leaf comparator that hits threshold is reached.
+ * This method is called from a collector when hits threshold is reached.
+ * For some filtering comparators (e.g. {@code FilteringDocLeafComparator}
reaching
+ * hits threshold is enough to start updating their iterators, even when
queue is not yet full.
*/
- void setCanUpdateIterator() throws IOException;
+ void setHitsThresholdReached() throws IOException;
+
+ /**
+ * Informs this leaf comparator that queue has become full.
+ * This method is called from a collector when queue becomes full.
+ */
+ void setQueueFull() throws IOException;
+
+ /**
+ * Returns {@code true} if the competitive iterator is updated.
+ * This tells the calling collector that it can update the {@code
TotalHits.Relation} to {GREATER_THAN_OR_EQUAL_TO}
+ */
+ boolean iteratorUpdated() throws IOException;
Review comment:
Is it really needed ? Maybe we should set `GREATER_THAN_OR_EQUAL_TO`
every time a TOP_SCORES collection reaches the total hits threshold ?
##########
File path:
lucene/core/src/java/org/apache/lucene/search/comparators/DocComparator.java
##########
@@ -0,0 +1,185 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.lucene.search.comparators;
+
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.search.FieldComparator;
+import org.apache.lucene.search.FilteringLeafFieldComparator;
+import org.apache.lucene.search.LeafFieldComparator;
+import org.apache.lucene.search.Scorable;
+
+import java.io.IOException;
+
+/**
+ * Comparator that sorts by asc _doc
+ */
+public class DocComparator extends FieldComparator<Integer> {
+ private final int[] docIDs;
+ private int topValue;
+ private boolean topValueSet;
+ private boolean reverse = false; // only used to check if skipping
functionality should be enabled
+
+ /** Creates a new comparator based on document ids for {@code numHits} */
+ public DocComparator(int numHits) {
+ docIDs = new int[numHits];
+ }
+
+ @Override
+ public int compare(int slot1, int slot2) {
+ // No overflow risk because docIDs are non-negative
+ return docIDs[slot1] - docIDs[slot2];
+ }
+
+
+ @Override
+ public LeafFieldComparator getLeafComparator(LeafReaderContext context) {
+ // TODO: can we "map" our docIDs to the current
+ // reader? saves having to then subtract on every
+ // compare call
+ return new DocLeafComparator(context);
+ }
+
+ @Override
+ public void setTopValue(Integer value) {
+ topValue = value;
+ topValueSet = true;
+ }
+
+ @Override
+ public Integer value(int slot) {
+ return Integer.valueOf(docIDs[slot]);
+ }
+
+ @Override
+ public void setReverse() {
+ reverse = true;
+ }
+
+
+ /**
+ * DocLeafComparator with skipping functionality.
+ * When sort by _doc asc and "after" document is set,
+ * the comparator provides an iterator that can quickly skip to the
desired "after" document.
+ */
+ private class DocLeafComparator implements FilteringLeafFieldComparator {
+ private final int docBase;
+ private int bottom;
+
+ private final boolean enableSkipping;
+ private final int minDoc;
+ private final int maxDoc;
+ private DocIdSetIterator topValueIterator; // iterator that starts
from topValue
+
+ private boolean iteratorUpdated = false;
+
+ public DocLeafComparator(LeafReaderContext context) {
+ this.docBase = context.docBase;
+ // skipping functionality is enabled if topValue is set and sort
is asc
+ this.enableSkipping = topValueSet && reverse == false ? true:
false;
+ if (enableSkipping) {
+ this.minDoc = topValue + 1;
+ this.maxDoc = context.reader().maxDoc();
+ this.topValueIterator = DocIdSetIterator.all(maxDoc);
+ } else {
+ this.minDoc = -1;
+ this.maxDoc = -1;
+ this.topValueIterator = null;
+ }
+ }
+
+ @Override
+ public void setBottom(int slot) {
+ bottom = docIDs[slot];
Review comment:
Any query sorted by doc id can early terminate after N matches. That's
an important aspect of the optimization since it can be handled by the hits
threshold transparently. If there is no `after` value, the threshold should be
an upper bound of the number of document that we will collect in the comparator.
----------------------------------------------------------------
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.
For queries about this service, please contact Infrastructure at:
us...@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscr...@lucene.apache.org
For additional commands, e-mail: issues-h...@lucene.apache.org
