You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@lucene.apache.org by "mkhludnev (via GitHub)" <gi...@apache.org> on 2024/11/03 19:54:57 UTC
[PR] DRAFT: SortedSet DV Multi Range query [lucene]
mkhludnev opened a new pull request, #13974:
URL: https://github.com/apache/lucene/pull/13974
### Description
Here's a sketch of DV analog of MultiRangeQuery. This draft uses bitset for expanding multiple ranges.
It passes random test, but internals are rough yet.
What do you think about this idea overall?
@atris, may I request your comments as an author of MultiRangeQuery?
--
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] SortedSet DV Multi Range query [lucene]
Posted by "github-actions[bot] (via GitHub)" <gi...@apache.org>.
github-actions[bot] commented on PR #13974:
URL: https://github.com/apache/lucene/pull/13974#issuecomment-2524694965
This PR has not had activity in the past 2 weeks, labeling it as stale. If the PR is waiting for review, notify the dev@lucene.apache.org list. Thank you for your contribution!
--
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] SortedSet DV Multi Range query [lucene]
Posted by "gsmiller (via GitHub)" <gi...@apache.org>.
gsmiller commented on PR #13974:
URL: https://github.com/apache/lucene/pull/13974#issuecomment-2638201802
@mkhludnev took one more look and I think this is in good shape to merge. Would you mind adding a CHANGES entry?
--
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] SortedSet DV Multi Range query [lucene]
Posted by "mkhludnev (via GitHub)" <gi...@apache.org>.
mkhludnev commented on PR #13974:
URL: https://github.com/apache/lucene/pull/13974#issuecomment-2670991159
pardon #14260
--
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] SortedSet DV Multi Range query [lucene]
Posted by "mkhludnev (via GitHub)" <gi...@apache.org>.
mkhludnev commented on PR #13974:
URL: https://github.com/apache/lucene/pull/13974#issuecomment-2640847271
Thanks. I'm happy to hear. Here's what I have to work on:
- @gsmiller what's your feeling about the [proposed API](https://github.com/apache/lucene/blob/c56caeb26a5af4b0afc5f2cb04a4f290ceff6189/lucene/sandbox/src/test/org/apache/lucene/sandbox/search/TestInetAddrSsDvMultiRange.java#L145). For me it seems a little bit cumbersome. I'm thinking about extending it further to other docvalues types and picking range tree algorithm instead of bitset.
- I'll put some more untitests and improve `toString()` somehow.
- I still don't know how to utilize DocValuesSkipper, can you give me a clue how to handle it properly?
--
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] SortedSet DV Multi Range query [lucene]
Posted by "mkhludnev (via GitHub)" <gi...@apache.org>.
mkhludnev commented on code in PR #13974:
URL: https://github.com/apache/lucene/pull/13974#discussion_r1891293118
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/search/SortedSetMultiRangeQuery.java:
##########
@@ -0,0 +1,300 @@
+/*
+ * 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.sandbox.search;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Objects;
+import org.apache.lucene.document.SortedSetDocValuesField;
+import org.apache.lucene.index.DocValues;
+import org.apache.lucene.index.DocValuesSkipper;
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.index.SortedSetDocValues;
+import org.apache.lucene.index.TermsEnum;
+import org.apache.lucene.search.BooleanQuery;
+import org.apache.lucene.search.ConstantScoreScorer;
+import org.apache.lucene.search.ConstantScoreWeight;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.search.DocValuesRangeIterator;
+import org.apache.lucene.search.IndexSearcher;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.search.QueryVisitor;
+import org.apache.lucene.search.ScoreMode;
+import org.apache.lucene.search.Scorer;
+import org.apache.lucene.search.ScorerSupplier;
+import org.apache.lucene.search.TwoPhaseIterator;
+import org.apache.lucene.search.Weight;
+import org.apache.lucene.util.ArrayUtil;
+import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.LongBitSet;
+
+/** A union multiple ranges over SortedSetDocValuesField */
+public class SortedSetMultiRangeQuery extends Query {
Review Comment:
Aghh right. Let me gather my considerations:
- do you mean to rename it to `SortedSetDocValuesMultiRangeQuery` or somehow abbreviate it? I'm totally for it.
- `SortedSetDocValuesRangeQuery` which is a singular analog of `SortedSetMultiRangeQuery`, has no `bytePerDim` constraint. However, I purpose `SortedSetMultiRangeQuery` for fixed width usages like IP, lately for IP ranges. I'm not sure it's possible at all, but do you think it's worth to drop `bytePerDim` constrain to move it forward?
- `sandbox` package is an only option for now, I suppose
- is it worth to copy `MultiRangeQuery.RangeClause` here? I used it only because it's public. Whether we do it now or later, it doesn't leak from public interface. WDYT?
--
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] SortedSet DV Multi Range query [lucene]
Posted by "mkhludnev (via GitHub)" <gi...@apache.org>.
mkhludnev commented on code in PR #13974:
URL: https://github.com/apache/lucene/pull/13974#discussion_r1891251385
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/search/SortedSetMultiRangeQuery.java:
##########
@@ -0,0 +1,300 @@
+/*
+ * 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.sandbox.search;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Objects;
+import org.apache.lucene.document.SortedSetDocValuesField;
+import org.apache.lucene.index.DocValues;
+import org.apache.lucene.index.DocValuesSkipper;
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.index.SortedSetDocValues;
+import org.apache.lucene.index.TermsEnum;
+import org.apache.lucene.search.BooleanQuery;
+import org.apache.lucene.search.ConstantScoreScorer;
+import org.apache.lucene.search.ConstantScoreWeight;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.search.DocValuesRangeIterator;
+import org.apache.lucene.search.IndexSearcher;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.search.QueryVisitor;
+import org.apache.lucene.search.ScoreMode;
+import org.apache.lucene.search.Scorer;
+import org.apache.lucene.search.ScorerSupplier;
+import org.apache.lucene.search.TwoPhaseIterator;
+import org.apache.lucene.search.Weight;
+import org.apache.lucene.util.ArrayUtil;
+import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.LongBitSet;
+
+/** A union multiple ranges over SortedSetDocValuesField */
+public class SortedSetMultiRangeQuery extends Query {
+ private final String field;
+ private final int bytesPerDim;
+ private final ArrayUtil.ByteArrayComparator comparator;
+ List<MultiRangeQuery.RangeClause> rangeClauses;
+
+ SortedSetMultiRangeQuery(
+ String name,
+ List<MultiRangeQuery.RangeClause> clauses,
+ int bytes,
+ ArrayUtil.ByteArrayComparator comparator) {
+ this.field = name;
+ this.rangeClauses = clauses;
+ this.bytesPerDim = bytes;
+ this.comparator = comparator;
+ }
+
+ /** Builder for creating a SortedSetMultiRangeQuery. */
+ public static class Builder {
+ private final String name;
+ protected final List<MultiRangeQuery.RangeClause> clauses = new ArrayList<>();
+ private final int bytes;
+ private final ArrayUtil.ByteArrayComparator comparator;
+
+ public Builder(String name, int bytes) {
+ this.name = Objects.requireNonNull(name);
+ this.bytes = bytes; // TODO assrt positive
+ this.comparator = ArrayUtil.getUnsignedComparator(bytes);
+ }
+
+ public Builder add(BytesRef lowerValue, BytesRef upperValue) {
+ byte[] low = lowerValue.clone().bytes;
+ byte[] up = upperValue.clone().bytes;
+ if (this.comparator.compare(low, 0, up, 0) > 0) {
+ throw new IllegalArgumentException("lowerValue must be <= upperValue");
+ } else {
+ clauses.add(new MultiRangeQuery.RangeClause(low, up));
+ }
+ return this;
+ }
+
+ public Query build() {
+ if (clauses.isEmpty()) {
+ return new BooleanQuery.Builder().build();
+ }
+ if (clauses.size() == 1) {
+ return SortedSetDocValuesField.newSlowRangeQuery(
+ name,
+ new BytesRef(clauses.getFirst().lowerValue),
+ new BytesRef(clauses.getFirst().upperValue),
+ true,
+ true);
+ }
+ return new SortedSetMultiRangeQuery(name, clauses, this.bytes, comparator);
+ }
+ }
+
+ @Override
+ public Query rewrite(IndexSearcher indexSearcher) throws IOException {
+ ArrayList<MultiRangeQuery.RangeClause> sortedClauses = new ArrayList<>(this.rangeClauses);
Review Comment:
ook. let's move it to constructor.
--
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] SortedSet DV Multi Range query [lucene]
Posted by "mkhludnev (via GitHub)" <gi...@apache.org>.
mkhludnev commented on code in PR #13974:
URL: https://github.com/apache/lucene/pull/13974#discussion_r1898414243
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/search/SortedSetMultiRangeQuery.java:
##########
@@ -0,0 +1,300 @@
+/*
+ * 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.sandbox.search;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Objects;
+import org.apache.lucene.document.SortedSetDocValuesField;
+import org.apache.lucene.index.DocValues;
+import org.apache.lucene.index.DocValuesSkipper;
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.index.SortedSetDocValues;
+import org.apache.lucene.index.TermsEnum;
+import org.apache.lucene.search.BooleanQuery;
+import org.apache.lucene.search.ConstantScoreScorer;
+import org.apache.lucene.search.ConstantScoreWeight;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.search.DocValuesRangeIterator;
+import org.apache.lucene.search.IndexSearcher;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.search.QueryVisitor;
+import org.apache.lucene.search.ScoreMode;
+import org.apache.lucene.search.Scorer;
+import org.apache.lucene.search.ScorerSupplier;
+import org.apache.lucene.search.TwoPhaseIterator;
+import org.apache.lucene.search.Weight;
+import org.apache.lucene.util.ArrayUtil;
+import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.LongBitSet;
+
+/** A union multiple ranges over SortedSetDocValuesField */
+public class SortedSetMultiRangeQuery extends Query {
+ private final String field;
+ private final int bytesPerDim;
+ private final ArrayUtil.ByteArrayComparator comparator;
+ List<MultiRangeQuery.RangeClause> rangeClauses;
+
+ SortedSetMultiRangeQuery(
+ String name,
+ List<MultiRangeQuery.RangeClause> clauses,
+ int bytes,
+ ArrayUtil.ByteArrayComparator comparator) {
+ this.field = name;
+ this.rangeClauses = clauses;
+ this.bytesPerDim = bytes;
+ this.comparator = comparator;
+ }
+
+ /** Builder for creating a SortedSetMultiRangeQuery. */
+ public static class Builder {
+ private final String name;
+ protected final List<MultiRangeQuery.RangeClause> clauses = new ArrayList<>();
+ private final int bytes;
+ private final ArrayUtil.ByteArrayComparator comparator;
+
+ public Builder(String name, int bytes) {
+ this.name = Objects.requireNonNull(name);
+ this.bytes = bytes; // TODO assrt positive
+ this.comparator = ArrayUtil.getUnsignedComparator(bytes);
+ }
+
+ public Builder add(BytesRef lowerValue, BytesRef upperValue) {
+ byte[] low = lowerValue.clone().bytes;
+ byte[] up = upperValue.clone().bytes;
+ if (this.comparator.compare(low, 0, up, 0) > 0) {
+ throw new IllegalArgumentException("lowerValue must be <= upperValue");
+ } else {
+ clauses.add(new MultiRangeQuery.RangeClause(low, up));
+ }
+ return this;
+ }
+
+ public Query build() {
+ if (clauses.isEmpty()) {
+ return new BooleanQuery.Builder().build();
+ }
+ if (clauses.size() == 1) {
+ return SortedSetDocValuesField.newSlowRangeQuery(
+ name,
+ new BytesRef(clauses.getFirst().lowerValue),
+ new BytesRef(clauses.getFirst().upperValue),
+ true,
+ true);
+ }
+ return new SortedSetMultiRangeQuery(name, clauses, this.bytes, comparator);
+ }
+ }
+
+ @Override
+ public Query rewrite(IndexSearcher indexSearcher) throws IOException {
+ ArrayList<MultiRangeQuery.RangeClause> sortedClauses = new ArrayList<>(this.rangeClauses);
+ sortedClauses.sort(
+ (o1, o2) -> {
+ // if (result == 0) {
+ // return comparator.compare(o1.upperValue, 0, o2.upperValue, 0);
+ // } else {
+ return comparator.compare(o1.lowerValue, 0, o2.lowerValue, 0);
+ // }
+ });
+ if (!this.rangeClauses.equals(sortedClauses)) {
+ return new SortedSetMultiRangeQuery(
+ this.field, sortedClauses, this.bytesPerDim, this.comparator);
+ } else {
+ return this;
+ }
+ }
+
+ @Override
+ public String toString(String fld) {
+ return "SortedSetMultiRangeQuery{"
+ + "field='"
+ + fld
+ + '\''
+ + ", rangeClauses="
+ + rangeClauses
+ + // TODO better toString
+ '}';
+ }
+
+ // what TODO with reverse ranges ???
+ @Override
+ public Weight createWeight(IndexSearcher searcher, ScoreMode scoreMode, float boost)
+ throws IOException {
+ return new ConstantScoreWeight(this, boost) {
+ @Override
+ public ScorerSupplier scorerSupplier(LeafReaderContext context) throws IOException {
+ if (context.reader().getFieldInfos().fieldInfo(field) == null) {
+ return null;
+ }
+ DocValuesSkipper skipper = context.reader().getDocValuesSkipper(field);
+ SortedSetDocValues values = DocValues.getSortedSet(context.reader(), field);
+ // implement ScorerSupplier, since we do some expensive stuff to make a scorer
+ return new ScorerSupplier() {
+ @Override
+ public Scorer get(long leadCost) throws IOException {
+ if (rangeClauses.isEmpty()) {
+ return empty();
+ }
+ TermsEnum termsEnum = values.termsEnum();
+ LongBitSet matchingOrdsShifted = null;
+ long minOrd = 0, maxOrd = values.getValueCount() - 1;
+ long matchesAbove =
+ values.getValueCount(); // it's last range goes to maxOrd, by default - no match
+ long maxSeenOrd = values.getValueCount();
+ TermsEnum.SeekStatus seekStatus = TermsEnum.SeekStatus.NOT_FOUND;
+ for (int r = 0; r < rangeClauses.size(); r++) {
+ MultiRangeQuery.RangeClause range = rangeClauses.get(r);
+ long startingOrd;
+ seekStatus = termsEnum.seekCeil(new BytesRef(range.lowerValue));
+ if (matchingOrdsShifted == null) { // first iter
+ if (seekStatus == TermsEnum.SeekStatus.END) {
+ return empty(); // no bitset yet, give up
+ }
+ minOrd = termsEnum.ord();
+ if (skipper != null) {
+ minOrd = Math.max(minOrd, skipper.minValue());
+ maxOrd = Math.min(maxOrd, skipper.maxValue());
+ }
+ if (maxOrd < minOrd) {
+ return empty();
+ }
+ startingOrd = minOrd;
+ } else {
+ if (seekStatus == TermsEnum.SeekStatus.END) {
+ break; // ranges - we are done, terms are exhausted
+ } else {
+ startingOrd = termsEnum.ord();
+ }
+ }
+ byte[] upper = range.upperValue; // TODO ignore reverse ranges
+ // looking for overlap
+ for (int overlap = r + 1; overlap < rangeClauses.size(); overlap++, r++) {
+ MultiRangeQuery.RangeClause mayOverlap = rangeClauses.get(overlap);
+ assert comparator.compare(range.lowerValue, 0, mayOverlap.lowerValue, 0) <= 0
+ : "since they are sorted";
+ // TODO it might be contiguous ranges, it's worth to check but I have no idea how
+ if (comparator.compare(mayOverlap.lowerValue, 0, upper, 0) <= 0) {
+ // overlap, expand if needed
+ if (comparator.compare(upper, 0, mayOverlap.upperValue, 0) < 0) {
+ upper = mayOverlap.upperValue;
+ }
+ // continue; // skip overlapping rng
+ } else {
+ break; // no r++
+ }
+ }
+ seekStatus = termsEnum.seekCeil(new BytesRef(upper));
+
+ if (seekStatus == TermsEnum.SeekStatus.END) {
+ maxSeenOrd = maxOrd; // perhaps it's worth to set for skipper
+ matchesAbove = startingOrd;
+ break; // no need to create bitset
+ }
+ maxSeenOrd =
+ seekStatus == TermsEnum.SeekStatus.FOUND
+ ? termsEnum.ord()
+ : termsEnum.ord() - 1; // floor
+
+ if (matchingOrdsShifted == null) {
+ matchingOrdsShifted = new LongBitSet(maxOrd + 1 - minOrd);
+ }
+ matchingOrdsShifted.set(
+ startingOrd - minOrd, maxSeenOrd - minOrd + 1); // up is exclusive
+ }
+ /// ranges are over, there might be no set!!
+ TwoPhaseIterator iterator;
+ long finalMatchesAbove = matchesAbove;
+ LongBitSet finalMatchingOrdsShifted = matchingOrdsShifted;
+ long finalMinOrd = minOrd;
+ iterator =
+ new TwoPhaseIterator(values) {
+ // TODO unwrap singleton?
+ @Override
+ public boolean matches() throws IOException {
+ for (int i = 0; i < values.docValueCount(); i++) {
+ long ord = values.nextOrd();
+ if (ord >= finalMinOrd
+ && ((finalMatchesAbove < values.getValueCount()
+ && ord >= finalMatchesAbove)
+ || finalMatchingOrdsShifted.get(ord - finalMinOrd))) {
Review Comment:
> less memory by keeping track of the range min/max values and not needing the dense representation
I just realized, if we merge overlapping ranges (which turns not so easy, but feasible), for remaining non-overlapping ranges we always have smaller and greater neighbor, that means we can just search ranges by ordinal in `TreeSet`.
Is it worth to explore instead of dense bit set?
--
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] SortedSet DV Multi Range query [lucene]
Posted by "mkhludnev (via GitHub)" <gi...@apache.org>.
mkhludnev commented on code in PR #13974:
URL: https://github.com/apache/lucene/pull/13974#discussion_r1891648727
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/search/SortedSetMultiRangeQuery.java:
##########
@@ -0,0 +1,300 @@
+/*
+ * 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.sandbox.search;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Objects;
+import org.apache.lucene.document.SortedSetDocValuesField;
+import org.apache.lucene.index.DocValues;
+import org.apache.lucene.index.DocValuesSkipper;
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.index.SortedSetDocValues;
+import org.apache.lucene.index.TermsEnum;
+import org.apache.lucene.search.BooleanQuery;
+import org.apache.lucene.search.ConstantScoreScorer;
+import org.apache.lucene.search.ConstantScoreWeight;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.search.DocValuesRangeIterator;
+import org.apache.lucene.search.IndexSearcher;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.search.QueryVisitor;
+import org.apache.lucene.search.ScoreMode;
+import org.apache.lucene.search.Scorer;
+import org.apache.lucene.search.ScorerSupplier;
+import org.apache.lucene.search.TwoPhaseIterator;
+import org.apache.lucene.search.Weight;
+import org.apache.lucene.util.ArrayUtil;
+import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.LongBitSet;
+
+/** A union multiple ranges over SortedSetDocValuesField */
+public class SortedSetMultiRangeQuery extends Query {
+ private final String field;
+ private final int bytesPerDim;
+ private final ArrayUtil.ByteArrayComparator comparator;
+ List<MultiRangeQuery.RangeClause> rangeClauses;
+
+ SortedSetMultiRangeQuery(
+ String name,
+ List<MultiRangeQuery.RangeClause> clauses,
+ int bytes,
+ ArrayUtil.ByteArrayComparator comparator) {
+ this.field = name;
+ this.rangeClauses = clauses;
+ this.bytesPerDim = bytes;
+ this.comparator = comparator;
+ }
+
+ /** Builder for creating a SortedSetMultiRangeQuery. */
+ public static class Builder {
+ private final String name;
+ protected final List<MultiRangeQuery.RangeClause> clauses = new ArrayList<>();
+ private final int bytes;
+ private final ArrayUtil.ByteArrayComparator comparator;
+
+ public Builder(String name, int bytes) {
+ this.name = Objects.requireNonNull(name);
+ this.bytes = bytes; // TODO assrt positive
+ this.comparator = ArrayUtil.getUnsignedComparator(bytes);
+ }
+
+ public Builder add(BytesRef lowerValue, BytesRef upperValue) {
+ byte[] low = lowerValue.clone().bytes;
+ byte[] up = upperValue.clone().bytes;
+ if (this.comparator.compare(low, 0, up, 0) > 0) {
+ throw new IllegalArgumentException("lowerValue must be <= upperValue");
+ } else {
+ clauses.add(new MultiRangeQuery.RangeClause(low, up));
+ }
+ return this;
+ }
+
+ public Query build() {
+ if (clauses.isEmpty()) {
+ return new BooleanQuery.Builder().build();
+ }
+ if (clauses.size() == 1) {
+ return SortedSetDocValuesField.newSlowRangeQuery(
+ name,
+ new BytesRef(clauses.getFirst().lowerValue),
+ new BytesRef(clauses.getFirst().upperValue),
+ true,
+ true);
+ }
+ return new SortedSetMultiRangeQuery(name, clauses, this.bytes, comparator);
+ }
+ }
+
+ @Override
+ public Query rewrite(IndexSearcher indexSearcher) throws IOException {
+ ArrayList<MultiRangeQuery.RangeClause> sortedClauses = new ArrayList<>(this.rangeClauses);
+ sortedClauses.sort(
+ (o1, o2) -> {
+ // if (result == 0) {
+ // return comparator.compare(o1.upperValue, 0, o2.upperValue, 0);
+ // } else {
+ return comparator.compare(o1.lowerValue, 0, o2.lowerValue, 0);
+ // }
+ });
+ if (!this.rangeClauses.equals(sortedClauses)) {
+ return new SortedSetMultiRangeQuery(
+ this.field, sortedClauses, this.bytesPerDim, this.comparator);
+ } else {
+ return this;
+ }
+ }
+
+ @Override
+ public String toString(String fld) {
+ return "SortedSetMultiRangeQuery{"
+ + "field='"
+ + fld
+ + '\''
+ + ", rangeClauses="
+ + rangeClauses
+ + // TODO better toString
+ '}';
+ }
+
+ // what TODO with reverse ranges ???
+ @Override
+ public Weight createWeight(IndexSearcher searcher, ScoreMode scoreMode, float boost)
+ throws IOException {
+ return new ConstantScoreWeight(this, boost) {
+ @Override
+ public ScorerSupplier scorerSupplier(LeafReaderContext context) throws IOException {
+ if (context.reader().getFieldInfos().fieldInfo(field) == null) {
+ return null;
+ }
+ DocValuesSkipper skipper = context.reader().getDocValuesSkipper(field);
+ SortedSetDocValues values = DocValues.getSortedSet(context.reader(), field);
+ // implement ScorerSupplier, since we do some expensive stuff to make a scorer
+ return new ScorerSupplier() {
+ @Override
+ public Scorer get(long leadCost) throws IOException {
+ if (rangeClauses.isEmpty()) {
+ return empty();
+ }
+ TermsEnum termsEnum = values.termsEnum();
+ LongBitSet matchingOrdsShifted = null;
+ long minOrd = 0, maxOrd = values.getValueCount() - 1;
+ long matchesAbove =
+ values.getValueCount(); // it's last range goes to maxOrd, by default - no match
+ long maxSeenOrd = values.getValueCount();
+ TermsEnum.SeekStatus seekStatus = TermsEnum.SeekStatus.NOT_FOUND;
+ for (int r = 0; r < rangeClauses.size(); r++) {
+ MultiRangeQuery.RangeClause range = rangeClauses.get(r);
+ long startingOrd;
+ seekStatus = termsEnum.seekCeil(new BytesRef(range.lowerValue));
+ if (matchingOrdsShifted == null) { // first iter
+ if (seekStatus == TermsEnum.SeekStatus.END) {
+ return empty(); // no bitset yet, give up
+ }
+ minOrd = termsEnum.ord();
+ if (skipper != null) {
Review Comment:
@gsmiller How to test skipper logic via test like https://github.com/apache/lucene/pull/13974/files#diff-5c4a4738d4643b48f34fb00fa3b67098f9bf4f1744e12955372df0f32812670d ?
--
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] SortedSet DV Multi Range query [lucene]
Posted by "gsmiller (via GitHub)" <gi...@apache.org>.
gsmiller commented on code in PR #13974:
URL: https://github.com/apache/lucene/pull/13974#discussion_r1893073059
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/search/SortedSetMultiRangeQuery.java:
##########
@@ -0,0 +1,300 @@
+/*
+ * 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.sandbox.search;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Objects;
+import org.apache.lucene.document.SortedSetDocValuesField;
+import org.apache.lucene.index.DocValues;
+import org.apache.lucene.index.DocValuesSkipper;
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.index.SortedSetDocValues;
+import org.apache.lucene.index.TermsEnum;
+import org.apache.lucene.search.BooleanQuery;
+import org.apache.lucene.search.ConstantScoreScorer;
+import org.apache.lucene.search.ConstantScoreWeight;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.search.DocValuesRangeIterator;
+import org.apache.lucene.search.IndexSearcher;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.search.QueryVisitor;
+import org.apache.lucene.search.ScoreMode;
+import org.apache.lucene.search.Scorer;
+import org.apache.lucene.search.ScorerSupplier;
+import org.apache.lucene.search.TwoPhaseIterator;
+import org.apache.lucene.search.Weight;
+import org.apache.lucene.util.ArrayUtil;
+import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.LongBitSet;
+
+/** A union multiple ranges over SortedSetDocValuesField */
+public class SortedSetMultiRangeQuery extends Query {
Review Comment:
- I think the name is fine. Including `DocValues` in the naming is a little more consistent with the code base, but it's also pretty verbose (as you point out). I'm fine with either.
- Right. I don't think there is any point to having `bytesPerDim` here is there? That's needed in `MultiRangeQuery` since it needs to unpack multidimensional points, but you're not doing that here. This goes back to my initial misunderstanding of what was being proposed. `MultiRangeQuery` is a multi-range version of `PointRangeQuery`, which are both range queries over n-dimensional points indexed in a points index. To my knowledge, there isn't a "slow" version of these queries that operate over doc values. What I initially thought was being proposed was a doc values version of these queries, but this is something different. As you point out, it's really a multi-range version of `SortedSetDocValuesRangeQuery`. So actually, as I'm writing this, I'm starting to think maybe naming this `SortedSetDocValuesMultiRangeQuery` might be good to make this connection a little more clear?
- Yeah, I think sandbox is still a good fit here. Let's not change that.
- I think it's OK to reuse the existing `RangeClause` for now since it's not part of the public API. As you point out, this would be easy enough to change later if we need to.
--
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] SortedSet DV Multi Range query [lucene]
Posted by "mkhludnev (via GitHub)" <gi...@apache.org>.
mkhludnev commented on code in PR #13974:
URL: https://github.com/apache/lucene/pull/13974#discussion_r1926069638
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/search/SortedSetMultiRangeQuery.java:
##########
@@ -0,0 +1,300 @@
+/*
+ * 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.sandbox.search;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Objects;
+import org.apache.lucene.document.SortedSetDocValuesField;
+import org.apache.lucene.index.DocValues;
+import org.apache.lucene.index.DocValuesSkipper;
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.index.SortedSetDocValues;
+import org.apache.lucene.index.TermsEnum;
+import org.apache.lucene.search.BooleanQuery;
+import org.apache.lucene.search.ConstantScoreScorer;
+import org.apache.lucene.search.ConstantScoreWeight;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.search.DocValuesRangeIterator;
+import org.apache.lucene.search.IndexSearcher;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.search.QueryVisitor;
+import org.apache.lucene.search.ScoreMode;
+import org.apache.lucene.search.Scorer;
+import org.apache.lucene.search.ScorerSupplier;
+import org.apache.lucene.search.TwoPhaseIterator;
+import org.apache.lucene.search.Weight;
+import org.apache.lucene.util.ArrayUtil;
+import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.LongBitSet;
+
+/** A union multiple ranges over SortedSetDocValuesField */
+public class SortedSetMultiRangeQuery extends Query {
+ private final String field;
+ private final int bytesPerDim;
+ private final ArrayUtil.ByteArrayComparator comparator;
+ List<MultiRangeQuery.RangeClause> rangeClauses;
+
+ SortedSetMultiRangeQuery(
+ String name,
+ List<MultiRangeQuery.RangeClause> clauses,
+ int bytes,
+ ArrayUtil.ByteArrayComparator comparator) {
+ this.field = name;
+ this.rangeClauses = clauses;
+ this.bytesPerDim = bytes;
+ this.comparator = comparator;
+ }
+
+ /** Builder for creating a SortedSetMultiRangeQuery. */
+ public static class Builder {
+ private final String name;
+ protected final List<MultiRangeQuery.RangeClause> clauses = new ArrayList<>();
+ private final int bytes;
+ private final ArrayUtil.ByteArrayComparator comparator;
+
+ public Builder(String name, int bytes) {
+ this.name = Objects.requireNonNull(name);
+ this.bytes = bytes; // TODO assrt positive
+ this.comparator = ArrayUtil.getUnsignedComparator(bytes);
+ }
+
+ public Builder add(BytesRef lowerValue, BytesRef upperValue) {
+ byte[] low = lowerValue.clone().bytes;
+ byte[] up = upperValue.clone().bytes;
+ if (this.comparator.compare(low, 0, up, 0) > 0) {
+ throw new IllegalArgumentException("lowerValue must be <= upperValue");
+ } else {
+ clauses.add(new MultiRangeQuery.RangeClause(low, up));
+ }
+ return this;
+ }
+
+ public Query build() {
+ if (clauses.isEmpty()) {
+ return new BooleanQuery.Builder().build();
+ }
+ if (clauses.size() == 1) {
+ return SortedSetDocValuesField.newSlowRangeQuery(
+ name,
+ new BytesRef(clauses.getFirst().lowerValue),
+ new BytesRef(clauses.getFirst().upperValue),
+ true,
+ true);
+ }
+ return new SortedSetMultiRangeQuery(name, clauses, this.bytes, comparator);
+ }
+ }
+
+ @Override
+ public Query rewrite(IndexSearcher indexSearcher) throws IOException {
+ ArrayList<MultiRangeQuery.RangeClause> sortedClauses = new ArrayList<>(this.rangeClauses);
+ sortedClauses.sort(
+ (o1, o2) -> {
+ // if (result == 0) {
+ // return comparator.compare(o1.upperValue, 0, o2.upperValue, 0);
+ // } else {
+ return comparator.compare(o1.lowerValue, 0, o2.lowerValue, 0);
+ // }
+ });
+ if (!this.rangeClauses.equals(sortedClauses)) {
+ return new SortedSetMultiRangeQuery(
+ this.field, sortedClauses, this.bytesPerDim, this.comparator);
+ } else {
+ return this;
+ }
+ }
+
+ @Override
+ public String toString(String fld) {
+ return "SortedSetMultiRangeQuery{"
+ + "field='"
+ + fld
+ + '\''
+ + ", rangeClauses="
+ + rangeClauses
+ + // TODO better toString
+ '}';
+ }
+
+ // what TODO with reverse ranges ???
+ @Override
+ public Weight createWeight(IndexSearcher searcher, ScoreMode scoreMode, float boost)
+ throws IOException {
+ return new ConstantScoreWeight(this, boost) {
+ @Override
+ public ScorerSupplier scorerSupplier(LeafReaderContext context) throws IOException {
+ if (context.reader().getFieldInfos().fieldInfo(field) == null) {
+ return null;
+ }
+ DocValuesSkipper skipper = context.reader().getDocValuesSkipper(field);
+ SortedSetDocValues values = DocValues.getSortedSet(context.reader(), field);
+ // implement ScorerSupplier, since we do some expensive stuff to make a scorer
+ return new ScorerSupplier() {
+ @Override
+ public Scorer get(long leadCost) throws IOException {
+ if (rangeClauses.isEmpty()) {
+ return empty();
+ }
+ TermsEnum termsEnum = values.termsEnum();
+ LongBitSet matchingOrdsShifted = null;
+ long minOrd = 0, maxOrd = values.getValueCount() - 1;
+ long matchesAbove =
+ values.getValueCount(); // it's last range goes to maxOrd, by default - no match
+ long maxSeenOrd = values.getValueCount();
+ TermsEnum.SeekStatus seekStatus = TermsEnum.SeekStatus.NOT_FOUND;
+ for (int r = 0; r < rangeClauses.size(); r++) {
+ MultiRangeQuery.RangeClause range = rangeClauses.get(r);
+ long startingOrd;
+ seekStatus = termsEnum.seekCeil(new BytesRef(range.lowerValue));
+ if (matchingOrdsShifted == null) { // first iter
+ if (seekStatus == TermsEnum.SeekStatus.END) {
+ return empty(); // no bitset yet, give up
+ }
+ minOrd = termsEnum.ord();
+ if (skipper != null) {
+ minOrd = Math.max(minOrd, skipper.minValue());
+ maxOrd = Math.min(maxOrd, skipper.maxValue());
+ }
+ if (maxOrd < minOrd) {
+ return empty();
+ }
+ startingOrd = minOrd;
+ } else {
+ if (seekStatus == TermsEnum.SeekStatus.END) {
+ break; // ranges - we are done, terms are exhausted
+ } else {
+ startingOrd = termsEnum.ord();
+ }
+ }
+ byte[] upper = range.upperValue; // TODO ignore reverse ranges
+ // looking for overlap
+ for (int overlap = r + 1; overlap < rangeClauses.size(); overlap++, r++) {
+ MultiRangeQuery.RangeClause mayOverlap = rangeClauses.get(overlap);
+ assert comparator.compare(range.lowerValue, 0, mayOverlap.lowerValue, 0) <= 0
+ : "since they are sorted";
+ // TODO it might be contiguous ranges, it's worth to check but I have no idea how
+ if (comparator.compare(mayOverlap.lowerValue, 0, upper, 0) <= 0) {
+ // overlap, expand if needed
+ if (comparator.compare(upper, 0, mayOverlap.upperValue, 0) < 0) {
+ upper = mayOverlap.upperValue;
+ }
+ // continue; // skip overlapping rng
+ } else {
+ break; // no r++
+ }
+ }
+ seekStatus = termsEnum.seekCeil(new BytesRef(upper));
+
+ if (seekStatus == TermsEnum.SeekStatus.END) {
+ maxSeenOrd = maxOrd; // perhaps it's worth to set for skipper
+ matchesAbove = startingOrd;
+ break; // no need to create bitset
+ }
+ maxSeenOrd =
+ seekStatus == TermsEnum.SeekStatus.FOUND
+ ? termsEnum.ord()
+ : termsEnum.ord() - 1; // floor
+
+ if (matchingOrdsShifted == null) {
+ matchingOrdsShifted = new LongBitSet(maxOrd + 1 - minOrd);
+ }
+ matchingOrdsShifted.set(
+ startingOrd - minOrd, maxSeenOrd - minOrd + 1); // up is exclusive
+ }
+ /// ranges are over, there might be no set!!
+ TwoPhaseIterator iterator;
+ long finalMatchesAbove = matchesAbove;
+ LongBitSet finalMatchingOrdsShifted = matchingOrdsShifted;
+ long finalMinOrd = minOrd;
+ iterator =
+ new TwoPhaseIterator(values) {
+ // TODO unwrap singleton?
+ @Override
+ public boolean matches() throws IOException {
+ for (int i = 0; i < values.docValueCount(); i++) {
+ long ord = values.nextOrd();
+ if (ord >= finalMinOrd
+ && ((finalMatchesAbove < values.getValueCount()
+ && ord >= finalMatchesAbove)
+ || finalMatchingOrdsShifted.get(ord - finalMinOrd))) {
Review Comment:
Thanks for your attention @gsmiller .
You are right.
`resolveOverlaps` literally merges overlapping ranges. Why it's necessary? I think just for some pathological queries. Imagine, many distinct ranges covered by the huge one, it may drop covered ranges from the future processing whether it be bitset or a tree set approach. I'm open for any stronger arguments.
Then, [createOrdRanges](https://github.com/apache/lucene/pull/13974/files#diff-7261e59f0cdf2536185e8e55d2fe1be04bbad37473b0eba30b4126326a289551R190) turns bytearrays to ordinals (btw, this step won't be available for NumericDVs and other w/o ords), at here some ranges might become adjacent, not really overlapping, but eligible for merging into bigger ones. I checked the code and comments there, there's no occurrence of `overlap` only `adjacent`.
--
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] SortedSet DV Multi Range query [lucene]
Posted by "mkhludnev (via GitHub)" <gi...@apache.org>.
mkhludnev commented on code in PR #13974:
URL: https://github.com/apache/lucene/pull/13974#discussion_r1891648727
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/search/SortedSetMultiRangeQuery.java:
##########
@@ -0,0 +1,300 @@
+/*
+ * 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.sandbox.search;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Objects;
+import org.apache.lucene.document.SortedSetDocValuesField;
+import org.apache.lucene.index.DocValues;
+import org.apache.lucene.index.DocValuesSkipper;
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.index.SortedSetDocValues;
+import org.apache.lucene.index.TermsEnum;
+import org.apache.lucene.search.BooleanQuery;
+import org.apache.lucene.search.ConstantScoreScorer;
+import org.apache.lucene.search.ConstantScoreWeight;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.search.DocValuesRangeIterator;
+import org.apache.lucene.search.IndexSearcher;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.search.QueryVisitor;
+import org.apache.lucene.search.ScoreMode;
+import org.apache.lucene.search.Scorer;
+import org.apache.lucene.search.ScorerSupplier;
+import org.apache.lucene.search.TwoPhaseIterator;
+import org.apache.lucene.search.Weight;
+import org.apache.lucene.util.ArrayUtil;
+import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.LongBitSet;
+
+/** A union multiple ranges over SortedSetDocValuesField */
+public class SortedSetMultiRangeQuery extends Query {
+ private final String field;
+ private final int bytesPerDim;
+ private final ArrayUtil.ByteArrayComparator comparator;
+ List<MultiRangeQuery.RangeClause> rangeClauses;
+
+ SortedSetMultiRangeQuery(
+ String name,
+ List<MultiRangeQuery.RangeClause> clauses,
+ int bytes,
+ ArrayUtil.ByteArrayComparator comparator) {
+ this.field = name;
+ this.rangeClauses = clauses;
+ this.bytesPerDim = bytes;
+ this.comparator = comparator;
+ }
+
+ /** Builder for creating a SortedSetMultiRangeQuery. */
+ public static class Builder {
+ private final String name;
+ protected final List<MultiRangeQuery.RangeClause> clauses = new ArrayList<>();
+ private final int bytes;
+ private final ArrayUtil.ByteArrayComparator comparator;
+
+ public Builder(String name, int bytes) {
+ this.name = Objects.requireNonNull(name);
+ this.bytes = bytes; // TODO assrt positive
+ this.comparator = ArrayUtil.getUnsignedComparator(bytes);
+ }
+
+ public Builder add(BytesRef lowerValue, BytesRef upperValue) {
+ byte[] low = lowerValue.clone().bytes;
+ byte[] up = upperValue.clone().bytes;
+ if (this.comparator.compare(low, 0, up, 0) > 0) {
+ throw new IllegalArgumentException("lowerValue must be <= upperValue");
+ } else {
+ clauses.add(new MultiRangeQuery.RangeClause(low, up));
+ }
+ return this;
+ }
+
+ public Query build() {
+ if (clauses.isEmpty()) {
+ return new BooleanQuery.Builder().build();
+ }
+ if (clauses.size() == 1) {
+ return SortedSetDocValuesField.newSlowRangeQuery(
+ name,
+ new BytesRef(clauses.getFirst().lowerValue),
+ new BytesRef(clauses.getFirst().upperValue),
+ true,
+ true);
+ }
+ return new SortedSetMultiRangeQuery(name, clauses, this.bytes, comparator);
+ }
+ }
+
+ @Override
+ public Query rewrite(IndexSearcher indexSearcher) throws IOException {
+ ArrayList<MultiRangeQuery.RangeClause> sortedClauses = new ArrayList<>(this.rangeClauses);
+ sortedClauses.sort(
+ (o1, o2) -> {
+ // if (result == 0) {
+ // return comparator.compare(o1.upperValue, 0, o2.upperValue, 0);
+ // } else {
+ return comparator.compare(o1.lowerValue, 0, o2.lowerValue, 0);
+ // }
+ });
+ if (!this.rangeClauses.equals(sortedClauses)) {
+ return new SortedSetMultiRangeQuery(
+ this.field, sortedClauses, this.bytesPerDim, this.comparator);
+ } else {
+ return this;
+ }
+ }
+
+ @Override
+ public String toString(String fld) {
+ return "SortedSetMultiRangeQuery{"
+ + "field='"
+ + fld
+ + '\''
+ + ", rangeClauses="
+ + rangeClauses
+ + // TODO better toString
+ '}';
+ }
+
+ // what TODO with reverse ranges ???
+ @Override
+ public Weight createWeight(IndexSearcher searcher, ScoreMode scoreMode, float boost)
+ throws IOException {
+ return new ConstantScoreWeight(this, boost) {
+ @Override
+ public ScorerSupplier scorerSupplier(LeafReaderContext context) throws IOException {
+ if (context.reader().getFieldInfos().fieldInfo(field) == null) {
+ return null;
+ }
+ DocValuesSkipper skipper = context.reader().getDocValuesSkipper(field);
+ SortedSetDocValues values = DocValues.getSortedSet(context.reader(), field);
+ // implement ScorerSupplier, since we do some expensive stuff to make a scorer
+ return new ScorerSupplier() {
+ @Override
+ public Scorer get(long leadCost) throws IOException {
+ if (rangeClauses.isEmpty()) {
+ return empty();
+ }
+ TermsEnum termsEnum = values.termsEnum();
+ LongBitSet matchingOrdsShifted = null;
+ long minOrd = 0, maxOrd = values.getValueCount() - 1;
+ long matchesAbove =
+ values.getValueCount(); // it's last range goes to maxOrd, by default - no match
+ long maxSeenOrd = values.getValueCount();
+ TermsEnum.SeekStatus seekStatus = TermsEnum.SeekStatus.NOT_FOUND;
+ for (int r = 0; r < rangeClauses.size(); r++) {
+ MultiRangeQuery.RangeClause range = rangeClauses.get(r);
+ long startingOrd;
+ seekStatus = termsEnum.seekCeil(new BytesRef(range.lowerValue));
+ if (matchingOrdsShifted == null) { // first iter
+ if (seekStatus == TermsEnum.SeekStatus.END) {
+ return empty(); // no bitset yet, give up
+ }
+ minOrd = termsEnum.ord();
+ if (skipper != null) {
Review Comment:
@gsmiller How to test skipper logic via test like https://github.com/apache/lucene/pull/13974/files#diff-5c4a4738d4643b48f34fb00fa3b67098f9bf4f1744e12955372df0f32812670d ?
--
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] SortedSet DV Multi Range query [lucene]
Posted by "gsmiller (via GitHub)" <gi...@apache.org>.
gsmiller commented on code in PR #13974:
URL: https://github.com/apache/lucene/pull/13974#discussion_r1904400249
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/search/SortedSetMultiRangeQuery.java:
##########
@@ -0,0 +1,300 @@
+/*
+ * 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.sandbox.search;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Objects;
+import org.apache.lucene.document.SortedSetDocValuesField;
+import org.apache.lucene.index.DocValues;
+import org.apache.lucene.index.DocValuesSkipper;
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.index.SortedSetDocValues;
+import org.apache.lucene.index.TermsEnum;
+import org.apache.lucene.search.BooleanQuery;
+import org.apache.lucene.search.ConstantScoreScorer;
+import org.apache.lucene.search.ConstantScoreWeight;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.search.DocValuesRangeIterator;
+import org.apache.lucene.search.IndexSearcher;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.search.QueryVisitor;
+import org.apache.lucene.search.ScoreMode;
+import org.apache.lucene.search.Scorer;
+import org.apache.lucene.search.ScorerSupplier;
+import org.apache.lucene.search.TwoPhaseIterator;
+import org.apache.lucene.search.Weight;
+import org.apache.lucene.util.ArrayUtil;
+import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.LongBitSet;
+
+/** A union multiple ranges over SortedSetDocValuesField */
+public class SortedSetMultiRangeQuery extends Query {
+ private final String field;
+ private final int bytesPerDim;
+ private final ArrayUtil.ByteArrayComparator comparator;
+ List<MultiRangeQuery.RangeClause> rangeClauses;
+
+ SortedSetMultiRangeQuery(
+ String name,
+ List<MultiRangeQuery.RangeClause> clauses,
+ int bytes,
+ ArrayUtil.ByteArrayComparator comparator) {
+ this.field = name;
+ this.rangeClauses = clauses;
+ this.bytesPerDim = bytes;
+ this.comparator = comparator;
+ }
+
+ /** Builder for creating a SortedSetMultiRangeQuery. */
+ public static class Builder {
+ private final String name;
+ protected final List<MultiRangeQuery.RangeClause> clauses = new ArrayList<>();
+ private final int bytes;
+ private final ArrayUtil.ByteArrayComparator comparator;
+
+ public Builder(String name, int bytes) {
+ this.name = Objects.requireNonNull(name);
+ this.bytes = bytes; // TODO assrt positive
+ this.comparator = ArrayUtil.getUnsignedComparator(bytes);
+ }
+
+ public Builder add(BytesRef lowerValue, BytesRef upperValue) {
+ byte[] low = lowerValue.clone().bytes;
+ byte[] up = upperValue.clone().bytes;
+ if (this.comparator.compare(low, 0, up, 0) > 0) {
+ throw new IllegalArgumentException("lowerValue must be <= upperValue");
+ } else {
+ clauses.add(new MultiRangeQuery.RangeClause(low, up));
+ }
+ return this;
+ }
+
+ public Query build() {
+ if (clauses.isEmpty()) {
+ return new BooleanQuery.Builder().build();
+ }
+ if (clauses.size() == 1) {
+ return SortedSetDocValuesField.newSlowRangeQuery(
+ name,
+ new BytesRef(clauses.getFirst().lowerValue),
+ new BytesRef(clauses.getFirst().upperValue),
+ true,
+ true);
+ }
+ return new SortedSetMultiRangeQuery(name, clauses, this.bytes, comparator);
+ }
+ }
+
+ @Override
+ public Query rewrite(IndexSearcher indexSearcher) throws IOException {
+ ArrayList<MultiRangeQuery.RangeClause> sortedClauses = new ArrayList<>(this.rangeClauses);
+ sortedClauses.sort(
+ (o1, o2) -> {
+ // if (result == 0) {
+ // return comparator.compare(o1.upperValue, 0, o2.upperValue, 0);
+ // } else {
+ return comparator.compare(o1.lowerValue, 0, o2.lowerValue, 0);
+ // }
+ });
+ if (!this.rangeClauses.equals(sortedClauses)) {
+ return new SortedSetMultiRangeQuery(
+ this.field, sortedClauses, this.bytesPerDim, this.comparator);
+ } else {
+ return this;
+ }
+ }
+
+ @Override
+ public String toString(String fld) {
+ return "SortedSetMultiRangeQuery{"
+ + "field='"
+ + fld
+ + '\''
+ + ", rangeClauses="
+ + rangeClauses
+ + // TODO better toString
+ '}';
+ }
+
+ // what TODO with reverse ranges ???
+ @Override
+ public Weight createWeight(IndexSearcher searcher, ScoreMode scoreMode, float boost)
+ throws IOException {
+ return new ConstantScoreWeight(this, boost) {
+ @Override
+ public ScorerSupplier scorerSupplier(LeafReaderContext context) throws IOException {
+ if (context.reader().getFieldInfos().fieldInfo(field) == null) {
+ return null;
+ }
+ DocValuesSkipper skipper = context.reader().getDocValuesSkipper(field);
+ SortedSetDocValues values = DocValues.getSortedSet(context.reader(), field);
+ // implement ScorerSupplier, since we do some expensive stuff to make a scorer
+ return new ScorerSupplier() {
+ @Override
+ public Scorer get(long leadCost) throws IOException {
+ if (rangeClauses.isEmpty()) {
+ return empty();
+ }
+ TermsEnum termsEnum = values.termsEnum();
+ LongBitSet matchingOrdsShifted = null;
+ long minOrd = 0, maxOrd = values.getValueCount() - 1;
+ long matchesAbove =
+ values.getValueCount(); // it's last range goes to maxOrd, by default - no match
+ long maxSeenOrd = values.getValueCount();
+ TermsEnum.SeekStatus seekStatus = TermsEnum.SeekStatus.NOT_FOUND;
+ for (int r = 0; r < rangeClauses.size(); r++) {
+ MultiRangeQuery.RangeClause range = rangeClauses.get(r);
+ long startingOrd;
+ seekStatus = termsEnum.seekCeil(new BytesRef(range.lowerValue));
+ if (matchingOrdsShifted == null) { // first iter
+ if (seekStatus == TermsEnum.SeekStatus.END) {
+ return empty(); // no bitset yet, give up
+ }
+ minOrd = termsEnum.ord();
+ if (skipper != null) {
+ minOrd = Math.max(minOrd, skipper.minValue());
+ maxOrd = Math.min(maxOrd, skipper.maxValue());
+ }
+ if (maxOrd < minOrd) {
+ return empty();
+ }
+ startingOrd = minOrd;
+ } else {
+ if (seekStatus == TermsEnum.SeekStatus.END) {
+ break; // ranges - we are done, terms are exhausted
+ } else {
+ startingOrd = termsEnum.ord();
+ }
+ }
+ byte[] upper = range.upperValue; // TODO ignore reverse ranges
+ // looking for overlap
+ for (int overlap = r + 1; overlap < rangeClauses.size(); overlap++, r++) {
+ MultiRangeQuery.RangeClause mayOverlap = rangeClauses.get(overlap);
+ assert comparator.compare(range.lowerValue, 0, mayOverlap.lowerValue, 0) <= 0
+ : "since they are sorted";
+ // TODO it might be contiguous ranges, it's worth to check but I have no idea how
+ if (comparator.compare(mayOverlap.lowerValue, 0, upper, 0) <= 0) {
+ // overlap, expand if needed
+ if (comparator.compare(upper, 0, mayOverlap.upperValue, 0) < 0) {
+ upper = mayOverlap.upperValue;
+ }
+ // continue; // skip overlapping rng
+ } else {
+ break; // no r++
+ }
+ }
+ seekStatus = termsEnum.seekCeil(new BytesRef(upper));
+
+ if (seekStatus == TermsEnum.SeekStatus.END) {
+ maxSeenOrd = maxOrd; // perhaps it's worth to set for skipper
+ matchesAbove = startingOrd;
+ break; // no need to create bitset
+ }
+ maxSeenOrd =
+ seekStatus == TermsEnum.SeekStatus.FOUND
+ ? termsEnum.ord()
+ : termsEnum.ord() - 1; // floor
+
+ if (matchingOrdsShifted == null) {
+ matchingOrdsShifted = new LongBitSet(maxOrd + 1 - minOrd);
+ }
+ matchingOrdsShifted.set(
+ startingOrd - minOrd, maxSeenOrd - minOrd + 1); // up is exclusive
+ }
+ /// ranges are over, there might be no set!!
+ TwoPhaseIterator iterator;
+ long finalMatchesAbove = matchesAbove;
+ LongBitSet finalMatchingOrdsShifted = matchingOrdsShifted;
+ long finalMinOrd = minOrd;
+ iterator =
+ new TwoPhaseIterator(values) {
+ // TODO unwrap singleton?
+ @Override
+ public boolean matches() throws IOException {
+ for (int i = 0; i < values.docValueCount(); i++) {
+ long ord = values.nextOrd();
+ if (ord >= finalMinOrd
+ && ((finalMatchesAbove < values.getValueCount()
+ && ord >= finalMatchesAbove)
+ || finalMatchingOrdsShifted.get(ord - finalMinOrd))) {
Review Comment:
@mkhludnev apologies for missing this conversation. I was mostly away over the holidays at the end of the year and just catching up more now. I just took a quick look at the latest version and I wonder if we're making this more complex than it needs to be for an initial version? What do you think of going back to the bitset-based version and getting that merged first, then proposing/measuring possible optimizations? WDYT?
--
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] SortedSet DV Multi Range query [lucene]
Posted by "mkhludnev (via GitHub)" <gi...@apache.org>.
mkhludnev commented on code in PR #13974:
URL: https://github.com/apache/lucene/pull/13974#discussion_r1896745244
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/search/SortedSetMultiRangeQuery.java:
##########
@@ -0,0 +1,300 @@
+/*
+ * 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.sandbox.search;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Objects;
+import org.apache.lucene.document.SortedSetDocValuesField;
+import org.apache.lucene.index.DocValues;
+import org.apache.lucene.index.DocValuesSkipper;
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.index.SortedSetDocValues;
+import org.apache.lucene.index.TermsEnum;
+import org.apache.lucene.search.BooleanQuery;
+import org.apache.lucene.search.ConstantScoreScorer;
+import org.apache.lucene.search.ConstantScoreWeight;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.search.DocValuesRangeIterator;
+import org.apache.lucene.search.IndexSearcher;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.search.QueryVisitor;
+import org.apache.lucene.search.ScoreMode;
+import org.apache.lucene.search.Scorer;
+import org.apache.lucene.search.ScorerSupplier;
+import org.apache.lucene.search.TwoPhaseIterator;
+import org.apache.lucene.search.Weight;
+import org.apache.lucene.util.ArrayUtil;
+import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.LongBitSet;
+
+/** A union multiple ranges over SortedSetDocValuesField */
+public class SortedSetMultiRangeQuery extends Query {
Review Comment:
Since I want to limit the scope of this PR to:
- single dimension fields, lately it might be extended to ranges in fields.
- fixed length values.
I'm going to hide constuctor and introduce public factory method. **UPD** ops, it's a builder already. hmm ..need to think more
--
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] SortedSet DV Multi Range query [lucene]
Posted by "mkhludnev (via GitHub)" <gi...@apache.org>.
mkhludnev commented on code in PR #13974:
URL: https://github.com/apache/lucene/pull/13974#discussion_r1891306672
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/search/SortedSetMultiRangeQuery.java:
##########
@@ -0,0 +1,300 @@
+/*
+ * 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.sandbox.search;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Objects;
+import org.apache.lucene.document.SortedSetDocValuesField;
+import org.apache.lucene.index.DocValues;
+import org.apache.lucene.index.DocValuesSkipper;
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.index.SortedSetDocValues;
+import org.apache.lucene.index.TermsEnum;
+import org.apache.lucene.search.BooleanQuery;
+import org.apache.lucene.search.ConstantScoreScorer;
+import org.apache.lucene.search.ConstantScoreWeight;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.search.DocValuesRangeIterator;
+import org.apache.lucene.search.IndexSearcher;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.search.QueryVisitor;
+import org.apache.lucene.search.ScoreMode;
+import org.apache.lucene.search.Scorer;
+import org.apache.lucene.search.ScorerSupplier;
+import org.apache.lucene.search.TwoPhaseIterator;
+import org.apache.lucene.search.Weight;
+import org.apache.lucene.util.ArrayUtil;
+import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.LongBitSet;
+
+/** A union multiple ranges over SortedSetDocValuesField */
+public class SortedSetMultiRangeQuery extends Query {
+ private final String field;
+ private final int bytesPerDim;
+ private final ArrayUtil.ByteArrayComparator comparator;
+ List<MultiRangeQuery.RangeClause> rangeClauses;
+
+ SortedSetMultiRangeQuery(
+ String name,
+ List<MultiRangeQuery.RangeClause> clauses,
+ int bytes,
+ ArrayUtil.ByteArrayComparator comparator) {
+ this.field = name;
+ this.rangeClauses = clauses;
+ this.bytesPerDim = bytes;
+ this.comparator = comparator;
+ }
+
+ /** Builder for creating a SortedSetMultiRangeQuery. */
+ public static class Builder {
+ private final String name;
+ protected final List<MultiRangeQuery.RangeClause> clauses = new ArrayList<>();
+ private final int bytes;
+ private final ArrayUtil.ByteArrayComparator comparator;
+
+ public Builder(String name, int bytes) {
+ this.name = Objects.requireNonNull(name);
+ this.bytes = bytes; // TODO assrt positive
+ this.comparator = ArrayUtil.getUnsignedComparator(bytes);
+ }
+
+ public Builder add(BytesRef lowerValue, BytesRef upperValue) {
+ byte[] low = lowerValue.clone().bytes;
+ byte[] up = upperValue.clone().bytes;
+ if (this.comparator.compare(low, 0, up, 0) > 0) {
+ throw new IllegalArgumentException("lowerValue must be <= upperValue");
+ } else {
+ clauses.add(new MultiRangeQuery.RangeClause(low, up));
+ }
+ return this;
+ }
+
+ public Query build() {
+ if (clauses.isEmpty()) {
+ return new BooleanQuery.Builder().build();
+ }
+ if (clauses.size() == 1) {
+ return SortedSetDocValuesField.newSlowRangeQuery(
+ name,
+ new BytesRef(clauses.getFirst().lowerValue),
+ new BytesRef(clauses.getFirst().upperValue),
+ true,
+ true);
+ }
+ return new SortedSetMultiRangeQuery(name, clauses, this.bytes, comparator);
+ }
+ }
+
+ @Override
+ public Query rewrite(IndexSearcher indexSearcher) throws IOException {
+ ArrayList<MultiRangeQuery.RangeClause> sortedClauses = new ArrayList<>(this.rangeClauses);
+ sortedClauses.sort(
+ (o1, o2) -> {
+ // if (result == 0) {
+ // return comparator.compare(o1.upperValue, 0, o2.upperValue, 0);
+ // } else {
+ return comparator.compare(o1.lowerValue, 0, o2.lowerValue, 0);
+ // }
+ });
+ if (!this.rangeClauses.equals(sortedClauses)) {
+ return new SortedSetMultiRangeQuery(
+ this.field, sortedClauses, this.bytesPerDim, this.comparator);
+ } else {
+ return this;
+ }
+ }
+
+ @Override
+ public String toString(String fld) {
+ return "SortedSetMultiRangeQuery{"
+ + "field='"
+ + fld
+ + '\''
+ + ", rangeClauses="
+ + rangeClauses
+ + // TODO better toString
+ '}';
+ }
+
+ // what TODO with reverse ranges ???
+ @Override
+ public Weight createWeight(IndexSearcher searcher, ScoreMode scoreMode, float boost)
+ throws IOException {
+ return new ConstantScoreWeight(this, boost) {
+ @Override
+ public ScorerSupplier scorerSupplier(LeafReaderContext context) throws IOException {
+ if (context.reader().getFieldInfos().fieldInfo(field) == null) {
+ return null;
+ }
+ DocValuesSkipper skipper = context.reader().getDocValuesSkipper(field);
+ SortedSetDocValues values = DocValues.getSortedSet(context.reader(), field);
+ // implement ScorerSupplier, since we do some expensive stuff to make a scorer
+ return new ScorerSupplier() {
+ @Override
+ public Scorer get(long leadCost) throws IOException {
+ if (rangeClauses.isEmpty()) {
+ return empty();
+ }
+ TermsEnum termsEnum = values.termsEnum();
+ LongBitSet matchingOrdsShifted = null;
+ long minOrd = 0, maxOrd = values.getValueCount() - 1;
+ long matchesAbove =
+ values.getValueCount(); // it's last range goes to maxOrd, by default - no match
+ long maxSeenOrd = values.getValueCount();
+ TermsEnum.SeekStatus seekStatus = TermsEnum.SeekStatus.NOT_FOUND;
+ for (int r = 0; r < rangeClauses.size(); r++) {
+ MultiRangeQuery.RangeClause range = rangeClauses.get(r);
+ long startingOrd;
+ seekStatus = termsEnum.seekCeil(new BytesRef(range.lowerValue));
+ if (matchingOrdsShifted == null) { // first iter
+ if (seekStatus == TermsEnum.SeekStatus.END) {
+ return empty(); // no bitset yet, give up
+ }
+ minOrd = termsEnum.ord();
+ if (skipper != null) {
Review Comment:
Need to think through. Honestly, never see `DocValuesSkipper`, have only vague idea how to test it.
--
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] SortedSet DV Multi Range query [lucene]
Posted by "gsmiller (via GitHub)" <gi...@apache.org>.
gsmiller commented on code in PR #13974:
URL: https://github.com/apache/lucene/pull/13974#discussion_r1893061461
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/search/SortedSetMultiRangeQuery.java:
##########
@@ -0,0 +1,300 @@
+/*
+ * 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.sandbox.search;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Objects;
+import org.apache.lucene.document.SortedSetDocValuesField;
+import org.apache.lucene.index.DocValues;
+import org.apache.lucene.index.DocValuesSkipper;
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.index.SortedSetDocValues;
+import org.apache.lucene.index.TermsEnum;
+import org.apache.lucene.search.BooleanQuery;
+import org.apache.lucene.search.ConstantScoreScorer;
+import org.apache.lucene.search.ConstantScoreWeight;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.search.DocValuesRangeIterator;
+import org.apache.lucene.search.IndexSearcher;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.search.QueryVisitor;
+import org.apache.lucene.search.ScoreMode;
+import org.apache.lucene.search.Scorer;
+import org.apache.lucene.search.ScorerSupplier;
+import org.apache.lucene.search.TwoPhaseIterator;
+import org.apache.lucene.search.Weight;
+import org.apache.lucene.util.ArrayUtil;
+import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.LongBitSet;
+
+/** A union multiple ranges over SortedSetDocValuesField */
+public class SortedSetMultiRangeQuery extends Query {
+ private final String field;
+ private final int bytesPerDim;
+ private final ArrayUtil.ByteArrayComparator comparator;
+ List<MultiRangeQuery.RangeClause> rangeClauses;
+
+ SortedSetMultiRangeQuery(
+ String name,
+ List<MultiRangeQuery.RangeClause> clauses,
+ int bytes,
+ ArrayUtil.ByteArrayComparator comparator) {
+ this.field = name;
+ this.rangeClauses = clauses;
+ this.bytesPerDim = bytes;
+ this.comparator = comparator;
+ }
+
+ /** Builder for creating a SortedSetMultiRangeQuery. */
+ public static class Builder {
+ private final String name;
+ protected final List<MultiRangeQuery.RangeClause> clauses = new ArrayList<>();
+ private final int bytes;
+ private final ArrayUtil.ByteArrayComparator comparator;
+
+ public Builder(String name, int bytes) {
+ this.name = Objects.requireNonNull(name);
+ this.bytes = bytes; // TODO assrt positive
+ this.comparator = ArrayUtil.getUnsignedComparator(bytes);
+ }
+
+ public Builder add(BytesRef lowerValue, BytesRef upperValue) {
+ byte[] low = lowerValue.clone().bytes;
+ byte[] up = upperValue.clone().bytes;
+ if (this.comparator.compare(low, 0, up, 0) > 0) {
+ throw new IllegalArgumentException("lowerValue must be <= upperValue");
+ } else {
+ clauses.add(new MultiRangeQuery.RangeClause(low, up));
+ }
+ return this;
+ }
+
+ public Query build() {
+ if (clauses.isEmpty()) {
+ return new BooleanQuery.Builder().build();
+ }
+ if (clauses.size() == 1) {
+ return SortedSetDocValuesField.newSlowRangeQuery(
+ name,
+ new BytesRef(clauses.getFirst().lowerValue),
+ new BytesRef(clauses.getFirst().upperValue),
+ true,
+ true);
+ }
+ return new SortedSetMultiRangeQuery(name, clauses, this.bytes, comparator);
+ }
+ }
+
+ @Override
+ public Query rewrite(IndexSearcher indexSearcher) throws IOException {
+ ArrayList<MultiRangeQuery.RangeClause> sortedClauses = new ArrayList<>(this.rangeClauses);
+ sortedClauses.sort(
+ (o1, o2) -> {
+ // if (result == 0) {
+ // return comparator.compare(o1.upperValue, 0, o2.upperValue, 0);
+ // } else {
+ return comparator.compare(o1.lowerValue, 0, o2.lowerValue, 0);
+ // }
+ });
+ if (!this.rangeClauses.equals(sortedClauses)) {
+ return new SortedSetMultiRangeQuery(
+ this.field, sortedClauses, this.bytesPerDim, this.comparator);
+ } else {
+ return this;
+ }
+ }
+
+ @Override
+ public String toString(String fld) {
+ return "SortedSetMultiRangeQuery{"
+ + "field='"
+ + fld
+ + '\''
+ + ", rangeClauses="
+ + rangeClauses
+ + // TODO better toString
+ '}';
+ }
+
+ // what TODO with reverse ranges ???
+ @Override
+ public Weight createWeight(IndexSearcher searcher, ScoreMode scoreMode, float boost)
+ throws IOException {
+ return new ConstantScoreWeight(this, boost) {
+ @Override
+ public ScorerSupplier scorerSupplier(LeafReaderContext context) throws IOException {
+ if (context.reader().getFieldInfos().fieldInfo(field) == null) {
+ return null;
+ }
+ DocValuesSkipper skipper = context.reader().getDocValuesSkipper(field);
+ SortedSetDocValues values = DocValues.getSortedSet(context.reader(), field);
+ // implement ScorerSupplier, since we do some expensive stuff to make a scorer
+ return new ScorerSupplier() {
+ @Override
+ public Scorer get(long leadCost) throws IOException {
+ if (rangeClauses.isEmpty()) {
+ return empty();
+ }
+ TermsEnum termsEnum = values.termsEnum();
+ LongBitSet matchingOrdsShifted = null;
+ long minOrd = 0, maxOrd = values.getValueCount() - 1;
+ long matchesAbove =
+ values.getValueCount(); // it's last range goes to maxOrd, by default - no match
+ long maxSeenOrd = values.getValueCount();
+ TermsEnum.SeekStatus seekStatus = TermsEnum.SeekStatus.NOT_FOUND;
+ for (int r = 0; r < rangeClauses.size(); r++) {
+ MultiRangeQuery.RangeClause range = rangeClauses.get(r);
+ long startingOrd;
+ seekStatus = termsEnum.seekCeil(new BytesRef(range.lowerValue));
+ if (matchingOrdsShifted == null) { // first iter
+ if (seekStatus == TermsEnum.SeekStatus.END) {
+ return empty(); // no bitset yet, give up
+ }
+ minOrd = termsEnum.ord();
+ if (skipper != null) {
+ minOrd = Math.max(minOrd, skipper.minValue());
+ maxOrd = Math.min(maxOrd, skipper.maxValue());
+ }
+ if (maxOrd < minOrd) {
+ return empty();
+ }
+ startingOrd = minOrd;
+ } else {
+ if (seekStatus == TermsEnum.SeekStatus.END) {
+ break; // ranges - we are done, terms are exhausted
+ } else {
+ startingOrd = termsEnum.ord();
+ }
+ }
+ byte[] upper = range.upperValue; // TODO ignore reverse ranges
+ // looking for overlap
+ for (int overlap = r + 1; overlap < rangeClauses.size(); overlap++, r++) {
+ MultiRangeQuery.RangeClause mayOverlap = rangeClauses.get(overlap);
+ assert comparator.compare(range.lowerValue, 0, mayOverlap.lowerValue, 0) <= 0
+ : "since they are sorted";
+ // TODO it might be contiguous ranges, it's worth to check but I have no idea how
+ if (comparator.compare(mayOverlap.lowerValue, 0, upper, 0) <= 0) {
+ // overlap, expand if needed
+ if (comparator.compare(upper, 0, mayOverlap.upperValue, 0) < 0) {
+ upper = mayOverlap.upperValue;
+ }
+ // continue; // skip overlapping rng
+ } else {
+ break; // no r++
+ }
+ }
+ seekStatus = termsEnum.seekCeil(new BytesRef(upper));
+
+ if (seekStatus == TermsEnum.SeekStatus.END) {
+ maxSeenOrd = maxOrd; // perhaps it's worth to set for skipper
+ matchesAbove = startingOrd;
+ break; // no need to create bitset
+ }
+ maxSeenOrd =
+ seekStatus == TermsEnum.SeekStatus.FOUND
+ ? termsEnum.ord()
+ : termsEnum.ord() - 1; // floor
+
+ if (matchingOrdsShifted == null) {
+ matchingOrdsShifted = new LongBitSet(maxOrd + 1 - minOrd);
+ }
+ matchingOrdsShifted.set(
+ startingOrd - minOrd, maxSeenOrd - minOrd + 1); // up is exclusive
+ }
+ /// ranges are over, there might be no set!!
+ TwoPhaseIterator iterator;
+ long finalMatchesAbove = matchesAbove;
+ LongBitSet finalMatchingOrdsShifted = matchingOrdsShifted;
+ long finalMinOrd = minOrd;
+ iterator =
+ new TwoPhaseIterator(values) {
+ // TODO unwrap singleton?
+ @Override
+ public boolean matches() throws IOException {
+ for (int i = 0; i < values.docValueCount(); i++) {
+ long ord = values.nextOrd();
+ if (ord >= finalMinOrd
+ && ((finalMatchesAbove < values.getValueCount()
+ && ord >= finalMatchesAbove)
+ || finalMatchingOrdsShifted.get(ord - finalMinOrd))) {
Review Comment:
Right. As you point out, there are definitely other situations where we use this bitset approach. My only thought here is that we should be able to use less memory by keeping track of the range min/max values and not needing the dense representation (this isn't really as feasible with `DocValuesRewriteMethod` since it's encoding a set of unique terms that aren't particularly likely to be contiguous ranges). If we track ranges, we can take advantage of them being sorted and the doc-level ordinals also being sorted. A binary search approach might be a good fit, and we can keep pushing up the lower bound of the search based on the last range that matched (since doc-level ordinals are sorted). I suspect this would still be less efficient than the dense bitset approach, but I bet it wouldn't be that big of a difference.
Without a way to benchmark and test though, it's just a bit of a guess. I'm OK with keeping it the way you have it for now if that's your preference. We can always benchmark alternatives in the future and evolve this if we want. Should we do that for now?
--
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] SortedSet DV Multi Range query [lucene]
Posted by "gsmiller (via GitHub)" <gi...@apache.org>.
gsmiller merged PR #13974:
URL: https://github.com/apache/lucene/pull/13974
--
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] SortedSet DV Multi Range query [lucene]
Posted by "gsmiller (via GitHub)" <gi...@apache.org>.
gsmiller commented on code in PR #13974:
URL: https://github.com/apache/lucene/pull/13974#discussion_r1892988895
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/search/SortedSetMultiRangeQuery.java:
##########
@@ -0,0 +1,300 @@
+/*
+ * 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.sandbox.search;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Objects;
+import org.apache.lucene.document.SortedSetDocValuesField;
+import org.apache.lucene.index.DocValues;
+import org.apache.lucene.index.DocValuesSkipper;
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.index.SortedSetDocValues;
+import org.apache.lucene.index.TermsEnum;
+import org.apache.lucene.search.BooleanQuery;
+import org.apache.lucene.search.ConstantScoreScorer;
+import org.apache.lucene.search.ConstantScoreWeight;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.search.DocValuesRangeIterator;
+import org.apache.lucene.search.IndexSearcher;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.search.QueryVisitor;
+import org.apache.lucene.search.ScoreMode;
+import org.apache.lucene.search.Scorer;
+import org.apache.lucene.search.ScorerSupplier;
+import org.apache.lucene.search.TwoPhaseIterator;
+import org.apache.lucene.search.Weight;
+import org.apache.lucene.util.ArrayUtil;
+import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.LongBitSet;
+
+/** A union multiple ranges over SortedSetDocValuesField */
+public class SortedSetMultiRangeQuery extends Query {
+ private final String field;
+ private final int bytesPerDim;
+ private final ArrayUtil.ByteArrayComparator comparator;
+ List<MultiRangeQuery.RangeClause> rangeClauses;
+
+ SortedSetMultiRangeQuery(
+ String name,
+ List<MultiRangeQuery.RangeClause> clauses,
+ int bytes,
+ ArrayUtil.ByteArrayComparator comparator) {
+ this.field = name;
+ this.rangeClauses = clauses;
+ this.bytesPerDim = bytes;
+ this.comparator = comparator;
+ }
+
+ /** Builder for creating a SortedSetMultiRangeQuery. */
+ public static class Builder {
+ private final String name;
+ protected final List<MultiRangeQuery.RangeClause> clauses = new ArrayList<>();
+ private final int bytes;
+ private final ArrayUtil.ByteArrayComparator comparator;
+
+ public Builder(String name, int bytes) {
+ this.name = Objects.requireNonNull(name);
+ this.bytes = bytes; // TODO assrt positive
+ this.comparator = ArrayUtil.getUnsignedComparator(bytes);
+ }
+
+ public Builder add(BytesRef lowerValue, BytesRef upperValue) {
+ byte[] low = lowerValue.clone().bytes;
+ byte[] up = upperValue.clone().bytes;
+ if (this.comparator.compare(low, 0, up, 0) > 0) {
+ throw new IllegalArgumentException("lowerValue must be <= upperValue");
+ } else {
+ clauses.add(new MultiRangeQuery.RangeClause(low, up));
+ }
+ return this;
+ }
+
+ public Query build() {
+ if (clauses.isEmpty()) {
+ return new BooleanQuery.Builder().build();
+ }
+ if (clauses.size() == 1) {
+ return SortedSetDocValuesField.newSlowRangeQuery(
+ name,
+ new BytesRef(clauses.getFirst().lowerValue),
+ new BytesRef(clauses.getFirst().upperValue),
+ true,
+ true);
+ }
+ return new SortedSetMultiRangeQuery(name, clauses, this.bytes, comparator);
+ }
+ }
+
+ @Override
+ public Query rewrite(IndexSearcher indexSearcher) throws IOException {
+ ArrayList<MultiRangeQuery.RangeClause> sortedClauses = new ArrayList<>(this.rangeClauses);
Review Comment:
Cool, thanks! Of course another option would be to do this in the builder if you think that's a better fit. No strong preference on my part.
--
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] SortedSet DV Multi Range query [lucene]
Posted by "mkhludnev (via GitHub)" <gi...@apache.org>.
mkhludnev commented on code in PR #13974:
URL: https://github.com/apache/lucene/pull/13974#discussion_r2023179556
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/search/SortedSetMultiRangeQuery.java:
##########
@@ -0,0 +1,300 @@
+/*
+ * 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.sandbox.search;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Objects;
+import org.apache.lucene.document.SortedSetDocValuesField;
+import org.apache.lucene.index.DocValues;
+import org.apache.lucene.index.DocValuesSkipper;
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.index.SortedSetDocValues;
+import org.apache.lucene.index.TermsEnum;
+import org.apache.lucene.search.BooleanQuery;
+import org.apache.lucene.search.ConstantScoreScorer;
+import org.apache.lucene.search.ConstantScoreWeight;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.search.DocValuesRangeIterator;
+import org.apache.lucene.search.IndexSearcher;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.search.QueryVisitor;
+import org.apache.lucene.search.ScoreMode;
+import org.apache.lucene.search.Scorer;
+import org.apache.lucene.search.ScorerSupplier;
+import org.apache.lucene.search.TwoPhaseIterator;
+import org.apache.lucene.search.Weight;
+import org.apache.lucene.util.ArrayUtil;
+import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.LongBitSet;
+
+/** A union multiple ranges over SortedSetDocValuesField */
+public class SortedSetMultiRangeQuery extends Query {
+ private final String field;
+ private final int bytesPerDim;
+ private final ArrayUtil.ByteArrayComparator comparator;
+ List<MultiRangeQuery.RangeClause> rangeClauses;
+
+ SortedSetMultiRangeQuery(
+ String name,
+ List<MultiRangeQuery.RangeClause> clauses,
+ int bytes,
+ ArrayUtil.ByteArrayComparator comparator) {
+ this.field = name;
+ this.rangeClauses = clauses;
+ this.bytesPerDim = bytes;
+ this.comparator = comparator;
+ }
+
+ /** Builder for creating a SortedSetMultiRangeQuery. */
+ public static class Builder {
+ private final String name;
+ protected final List<MultiRangeQuery.RangeClause> clauses = new ArrayList<>();
+ private final int bytes;
+ private final ArrayUtil.ByteArrayComparator comparator;
+
+ public Builder(String name, int bytes) {
+ this.name = Objects.requireNonNull(name);
+ this.bytes = bytes; // TODO assrt positive
+ this.comparator = ArrayUtil.getUnsignedComparator(bytes);
+ }
+
+ public Builder add(BytesRef lowerValue, BytesRef upperValue) {
+ byte[] low = lowerValue.clone().bytes;
+ byte[] up = upperValue.clone().bytes;
+ if (this.comparator.compare(low, 0, up, 0) > 0) {
+ throw new IllegalArgumentException("lowerValue must be <= upperValue");
+ } else {
+ clauses.add(new MultiRangeQuery.RangeClause(low, up));
+ }
+ return this;
+ }
+
+ public Query build() {
+ if (clauses.isEmpty()) {
+ return new BooleanQuery.Builder().build();
+ }
+ if (clauses.size() == 1) {
+ return SortedSetDocValuesField.newSlowRangeQuery(
+ name,
+ new BytesRef(clauses.getFirst().lowerValue),
+ new BytesRef(clauses.getFirst().upperValue),
+ true,
+ true);
+ }
+ return new SortedSetMultiRangeQuery(name, clauses, this.bytes, comparator);
+ }
+ }
+
+ @Override
+ public Query rewrite(IndexSearcher indexSearcher) throws IOException {
+ ArrayList<MultiRangeQuery.RangeClause> sortedClauses = new ArrayList<>(this.rangeClauses);
+ sortedClauses.sort(
+ (o1, o2) -> {
+ // if (result == 0) {
+ // return comparator.compare(o1.upperValue, 0, o2.upperValue, 0);
+ // } else {
+ return comparator.compare(o1.lowerValue, 0, o2.lowerValue, 0);
+ // }
+ });
+ if (!this.rangeClauses.equals(sortedClauses)) {
+ return new SortedSetMultiRangeQuery(
+ this.field, sortedClauses, this.bytesPerDim, this.comparator);
+ } else {
+ return this;
+ }
+ }
+
+ @Override
+ public String toString(String fld) {
+ return "SortedSetMultiRangeQuery{"
+ + "field='"
+ + fld
+ + '\''
+ + ", rangeClauses="
+ + rangeClauses
+ + // TODO better toString
+ '}';
+ }
+
+ // what TODO with reverse ranges ???
+ @Override
+ public Weight createWeight(IndexSearcher searcher, ScoreMode scoreMode, float boost)
+ throws IOException {
+ return new ConstantScoreWeight(this, boost) {
+ @Override
+ public ScorerSupplier scorerSupplier(LeafReaderContext context) throws IOException {
+ if (context.reader().getFieldInfos().fieldInfo(field) == null) {
+ return null;
+ }
+ DocValuesSkipper skipper = context.reader().getDocValuesSkipper(field);
+ SortedSetDocValues values = DocValues.getSortedSet(context.reader(), field);
+ // implement ScorerSupplier, since we do some expensive stuff to make a scorer
+ return new ScorerSupplier() {
+ @Override
+ public Scorer get(long leadCost) throws IOException {
+ if (rangeClauses.isEmpty()) {
+ return empty();
+ }
+ TermsEnum termsEnum = values.termsEnum();
+ LongBitSet matchingOrdsShifted = null;
+ long minOrd = 0, maxOrd = values.getValueCount() - 1;
+ long matchesAbove =
+ values.getValueCount(); // it's last range goes to maxOrd, by default - no match
+ long maxSeenOrd = values.getValueCount();
+ TermsEnum.SeekStatus seekStatus = TermsEnum.SeekStatus.NOT_FOUND;
+ for (int r = 0; r < rangeClauses.size(); r++) {
+ MultiRangeQuery.RangeClause range = rangeClauses.get(r);
+ long startingOrd;
+ seekStatus = termsEnum.seekCeil(new BytesRef(range.lowerValue));
+ if (matchingOrdsShifted == null) { // first iter
+ if (seekStatus == TermsEnum.SeekStatus.END) {
+ return empty(); // no bitset yet, give up
+ }
+ minOrd = termsEnum.ord();
+ if (skipper != null) {
+ minOrd = Math.max(minOrd, skipper.minValue());
+ maxOrd = Math.min(maxOrd, skipper.maxValue());
+ }
+ if (maxOrd < minOrd) {
+ return empty();
+ }
+ startingOrd = minOrd;
+ } else {
+ if (seekStatus == TermsEnum.SeekStatus.END) {
+ break; // ranges - we are done, terms are exhausted
+ } else {
+ startingOrd = termsEnum.ord();
+ }
+ }
+ byte[] upper = range.upperValue; // TODO ignore reverse ranges
+ // looking for overlap
+ for (int overlap = r + 1; overlap < rangeClauses.size(); overlap++, r++) {
+ MultiRangeQuery.RangeClause mayOverlap = rangeClauses.get(overlap);
+ assert comparator.compare(range.lowerValue, 0, mayOverlap.lowerValue, 0) <= 0
+ : "since they are sorted";
+ // TODO it might be contiguous ranges, it's worth to check but I have no idea how
+ if (comparator.compare(mayOverlap.lowerValue, 0, upper, 0) <= 0) {
+ // overlap, expand if needed
+ if (comparator.compare(upper, 0, mayOverlap.upperValue, 0) < 0) {
+ upper = mayOverlap.upperValue;
+ }
+ // continue; // skip overlapping rng
+ } else {
+ break; // no r++
+ }
+ }
+ seekStatus = termsEnum.seekCeil(new BytesRef(upper));
+
+ if (seekStatus == TermsEnum.SeekStatus.END) {
+ maxSeenOrd = maxOrd; // perhaps it's worth to set for skipper
+ matchesAbove = startingOrd;
+ break; // no need to create bitset
+ }
+ maxSeenOrd =
+ seekStatus == TermsEnum.SeekStatus.FOUND
+ ? termsEnum.ord()
+ : termsEnum.ord() - 1; // floor
+
+ if (matchingOrdsShifted == null) {
+ matchingOrdsShifted = new LongBitSet(maxOrd + 1 - minOrd);
+ }
+ matchingOrdsShifted.set(
+ startingOrd - minOrd, maxSeenOrd - minOrd + 1); // up is exclusive
+ }
+ /// ranges are over, there might be no set!!
+ TwoPhaseIterator iterator;
+ long finalMatchesAbove = matchesAbove;
+ LongBitSet finalMatchingOrdsShifted = matchingOrdsShifted;
+ long finalMinOrd = minOrd;
+ iterator =
+ new TwoPhaseIterator(values) {
+ // TODO unwrap singleton?
+ @Override
+ public boolean matches() throws IOException {
+ for (int i = 0; i < values.docValueCount(); i++) {
+ long ord = values.nextOrd();
+ if (ord >= finalMinOrd
+ && ((finalMatchesAbove < values.getValueCount()
+ && ord >= finalMatchesAbove)
+ || finalMatchingOrdsShifted.get(ord - finalMinOrd))) {
Review Comment:
> If we track ranges, we can take advantage of them being sorted and the doc-level ordinals also being sorted. A binary search approach might be a good fit, and we can keep pushing up the lower bound of the search based on the last range that matched (since doc-level ordinals are sorted).
Hello @gsmiller
Just did that in #14404. Really appreciate your attention.
--
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] SortedSet DV Multi Range query [lucene]
Posted by "mkhludnev (via GitHub)" <gi...@apache.org>.
mkhludnev commented on PR #13974:
URL: https://github.com/apache/lucene/pull/13974#issuecomment-2581987319
open items from my POV:
- improve testing via copying `TestDocValuesQueries`
- may DVSkipper limit and reduce the given ranges before matching to limit bitset?
- if ranges reaches ordinals boundaries: `[0 TO a],[b TO c],...[y TO dv.getValueCount()-1]` we can reduce bitset to `[a+1 TO y-1]`, and check boundary ranges explicitly.
--
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] SortedSet DV Multi Range query [lucene]
Posted by "gsmiller (via GitHub)" <gi...@apache.org>.
gsmiller commented on PR #13974:
URL: https://github.com/apache/lucene/pull/13974#issuecomment-2643826042
Thanks @mkhludnev .
1. I'm not as worried about getting the API perfect with this initial commit. One benefit of doing this in `sandbox` is that we can iterate on this in breaking ways without being too concerned. So if you're planning to add more use-cases, I can imagine this evolving and getting iterated on over time. So I wasn't going to comment on the API too much right now since this is in `sandbox`.
2. More testing, and toString is great :)
3. I think what you're doing with skipper already is correct. It's possible you could do more, but I'd save that for a follow up. The skipper gives you the min and max values represented by a range of docs. So what you're essentially doing right now is saying that if a given doc falls into a skip interval that doesn't intersect with the full min-max range that covers all of your multi-ranges, then it cannot match any of your ranges so you can skip it without loading its doc value and checking explicitly. If you're unsure of what you're doing with skipper though, you could also remove it as an optimization for now and add it back in separately (e.g., if you're concerned it might be incorrect).
--
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] SortedSet DV Multi Range query [lucene]
Posted by "mkhludnev (via GitHub)" <gi...@apache.org>.
mkhludnev commented on PR #13974:
URL: https://github.com/apache/lucene/pull/13974#issuecomment-2671447690
one idea:
- optimize one seekCeil() call `if r.upper==r.lower || r.equals(r.lower)` TBC
--
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] SortedSet DV Multi Range query [lucene]
Posted by "gsmiller (via GitHub)" <gi...@apache.org>.
gsmiller commented on code in PR #13974:
URL: https://github.com/apache/lucene/pull/13974#discussion_r1890984514
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/search/SortedSetMultiRangeQuery.java:
##########
@@ -0,0 +1,300 @@
+/*
+ * 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.sandbox.search;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Objects;
+import org.apache.lucene.document.SortedSetDocValuesField;
+import org.apache.lucene.index.DocValues;
+import org.apache.lucene.index.DocValuesSkipper;
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.index.SortedSetDocValues;
+import org.apache.lucene.index.TermsEnum;
+import org.apache.lucene.search.BooleanQuery;
+import org.apache.lucene.search.ConstantScoreScorer;
+import org.apache.lucene.search.ConstantScoreWeight;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.search.DocValuesRangeIterator;
+import org.apache.lucene.search.IndexSearcher;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.search.QueryVisitor;
+import org.apache.lucene.search.ScoreMode;
+import org.apache.lucene.search.Scorer;
+import org.apache.lucene.search.ScorerSupplier;
+import org.apache.lucene.search.TwoPhaseIterator;
+import org.apache.lucene.search.Weight;
+import org.apache.lucene.util.ArrayUtil;
+import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.LongBitSet;
+
+/** A union multiple ranges over SortedSetDocValuesField */
+public class SortedSetMultiRangeQuery extends Query {
+ private final String field;
+ private final int bytesPerDim;
+ private final ArrayUtil.ByteArrayComparator comparator;
+ List<MultiRangeQuery.RangeClause> rangeClauses;
Review Comment:
Any particular reason this shouldn't be `private final`? Maybe you're following the pattern in `MultiRangeQuery`, but I'm not sure what the reasoning is over in that class either (and might advocate to change that as well). Seems maybe even more important since `rangeClauses` is part of object identity?
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/search/SortedSetMultiRangeQuery.java:
##########
@@ -0,0 +1,300 @@
+/*
+ * 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.sandbox.search;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Objects;
+import org.apache.lucene.document.SortedSetDocValuesField;
+import org.apache.lucene.index.DocValues;
+import org.apache.lucene.index.DocValuesSkipper;
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.index.SortedSetDocValues;
+import org.apache.lucene.index.TermsEnum;
+import org.apache.lucene.search.BooleanQuery;
+import org.apache.lucene.search.ConstantScoreScorer;
+import org.apache.lucene.search.ConstantScoreWeight;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.search.DocValuesRangeIterator;
+import org.apache.lucene.search.IndexSearcher;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.search.QueryVisitor;
+import org.apache.lucene.search.ScoreMode;
+import org.apache.lucene.search.Scorer;
+import org.apache.lucene.search.ScorerSupplier;
+import org.apache.lucene.search.TwoPhaseIterator;
+import org.apache.lucene.search.Weight;
+import org.apache.lucene.util.ArrayUtil;
+import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.LongBitSet;
+
+/** A union multiple ranges over SortedSetDocValuesField */
+public class SortedSetMultiRangeQuery extends Query {
+ private final String field;
+ private final int bytesPerDim;
+ private final ArrayUtil.ByteArrayComparator comparator;
+ List<MultiRangeQuery.RangeClause> rangeClauses;
+
+ SortedSetMultiRangeQuery(
+ String name,
+ List<MultiRangeQuery.RangeClause> clauses,
+ int bytes,
+ ArrayUtil.ByteArrayComparator comparator) {
+ this.field = name;
+ this.rangeClauses = clauses;
+ this.bytesPerDim = bytes;
+ this.comparator = comparator;
+ }
+
+ /** Builder for creating a SortedSetMultiRangeQuery. */
+ public static class Builder {
+ private final String name;
+ protected final List<MultiRangeQuery.RangeClause> clauses = new ArrayList<>();
+ private final int bytes;
+ private final ArrayUtil.ByteArrayComparator comparator;
+
+ public Builder(String name, int bytes) {
+ this.name = Objects.requireNonNull(name);
+ this.bytes = bytes; // TODO assrt positive
+ this.comparator = ArrayUtil.getUnsignedComparator(bytes);
+ }
+
+ public Builder add(BytesRef lowerValue, BytesRef upperValue) {
+ byte[] low = lowerValue.clone().bytes;
+ byte[] up = upperValue.clone().bytes;
+ if (this.comparator.compare(low, 0, up, 0) > 0) {
+ throw new IllegalArgumentException("lowerValue must be <= upperValue");
+ } else {
+ clauses.add(new MultiRangeQuery.RangeClause(low, up));
+ }
+ return this;
+ }
+
+ public Query build() {
+ if (clauses.isEmpty()) {
+ return new BooleanQuery.Builder().build();
Review Comment:
Maybe `MatchNoDocsQuery` instead?
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/search/SortedSetMultiRangeQuery.java:
##########
@@ -0,0 +1,300 @@
+/*
+ * 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.sandbox.search;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Objects;
+import org.apache.lucene.document.SortedSetDocValuesField;
+import org.apache.lucene.index.DocValues;
+import org.apache.lucene.index.DocValuesSkipper;
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.index.SortedSetDocValues;
+import org.apache.lucene.index.TermsEnum;
+import org.apache.lucene.search.BooleanQuery;
+import org.apache.lucene.search.ConstantScoreScorer;
+import org.apache.lucene.search.ConstantScoreWeight;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.search.DocValuesRangeIterator;
+import org.apache.lucene.search.IndexSearcher;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.search.QueryVisitor;
+import org.apache.lucene.search.ScoreMode;
+import org.apache.lucene.search.Scorer;
+import org.apache.lucene.search.ScorerSupplier;
+import org.apache.lucene.search.TwoPhaseIterator;
+import org.apache.lucene.search.Weight;
+import org.apache.lucene.util.ArrayUtil;
+import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.LongBitSet;
+
+/** A union multiple ranges over SortedSetDocValuesField */
+public class SortedSetMultiRangeQuery extends Query {
+ private final String field;
+ private final int bytesPerDim;
+ private final ArrayUtil.ByteArrayComparator comparator;
+ List<MultiRangeQuery.RangeClause> rangeClauses;
+
+ SortedSetMultiRangeQuery(
+ String name,
+ List<MultiRangeQuery.RangeClause> clauses,
+ int bytes,
+ ArrayUtil.ByteArrayComparator comparator) {
+ this.field = name;
+ this.rangeClauses = clauses;
+ this.bytesPerDim = bytes;
+ this.comparator = comparator;
+ }
+
+ /** Builder for creating a SortedSetMultiRangeQuery. */
+ public static class Builder {
+ private final String name;
+ protected final List<MultiRangeQuery.RangeClause> clauses = new ArrayList<>();
Review Comment:
Is there a reason this can't be `private`?
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/search/SortedSetMultiRangeQuery.java:
##########
@@ -0,0 +1,300 @@
+/*
+ * 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.sandbox.search;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Objects;
+import org.apache.lucene.document.SortedSetDocValuesField;
+import org.apache.lucene.index.DocValues;
+import org.apache.lucene.index.DocValuesSkipper;
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.index.SortedSetDocValues;
+import org.apache.lucene.index.TermsEnum;
+import org.apache.lucene.search.BooleanQuery;
+import org.apache.lucene.search.ConstantScoreScorer;
+import org.apache.lucene.search.ConstantScoreWeight;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.search.DocValuesRangeIterator;
+import org.apache.lucene.search.IndexSearcher;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.search.QueryVisitor;
+import org.apache.lucene.search.ScoreMode;
+import org.apache.lucene.search.Scorer;
+import org.apache.lucene.search.ScorerSupplier;
+import org.apache.lucene.search.TwoPhaseIterator;
+import org.apache.lucene.search.Weight;
+import org.apache.lucene.util.ArrayUtil;
+import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.LongBitSet;
+
+/** A union multiple ranges over SortedSetDocValuesField */
+public class SortedSetMultiRangeQuery extends Query {
+ private final String field;
+ private final int bytesPerDim;
+ private final ArrayUtil.ByteArrayComparator comparator;
+ List<MultiRangeQuery.RangeClause> rangeClauses;
+
+ SortedSetMultiRangeQuery(
+ String name,
+ List<MultiRangeQuery.RangeClause> clauses,
+ int bytes,
+ ArrayUtil.ByteArrayComparator comparator) {
+ this.field = name;
+ this.rangeClauses = clauses;
+ this.bytesPerDim = bytes;
+ this.comparator = comparator;
+ }
+
+ /** Builder for creating a SortedSetMultiRangeQuery. */
+ public static class Builder {
+ private final String name;
+ protected final List<MultiRangeQuery.RangeClause> clauses = new ArrayList<>();
+ private final int bytes;
+ private final ArrayUtil.ByteArrayComparator comparator;
+
+ public Builder(String name, int bytes) {
+ this.name = Objects.requireNonNull(name);
+ this.bytes = bytes; // TODO assrt positive
+ this.comparator = ArrayUtil.getUnsignedComparator(bytes);
+ }
+
+ public Builder add(BytesRef lowerValue, BytesRef upperValue) {
+ byte[] low = lowerValue.clone().bytes;
+ byte[] up = upperValue.clone().bytes;
+ if (this.comparator.compare(low, 0, up, 0) > 0) {
+ throw new IllegalArgumentException("lowerValue must be <= upperValue");
+ } else {
+ clauses.add(new MultiRangeQuery.RangeClause(low, up));
+ }
+ return this;
+ }
+
+ public Query build() {
+ if (clauses.isEmpty()) {
+ return new BooleanQuery.Builder().build();
+ }
+ if (clauses.size() == 1) {
+ return SortedSetDocValuesField.newSlowRangeQuery(
+ name,
+ new BytesRef(clauses.getFirst().lowerValue),
+ new BytesRef(clauses.getFirst().upperValue),
+ true,
+ true);
+ }
+ return new SortedSetMultiRangeQuery(name, clauses, this.bytes, comparator);
+ }
+ }
+
+ @Override
+ public Query rewrite(IndexSearcher indexSearcher) throws IOException {
+ ArrayList<MultiRangeQuery.RangeClause> sortedClauses = new ArrayList<>(this.rangeClauses);
Review Comment:
I'm not sure why this logic exists in rewrite? Do we rely on having the ranges sorted in a specific order? Is so, should we just sort them in the ctor or in the builder? I don't think we need the rewrite hook for this. (Rewrite is useful if there is some state of the IndexSearcher that can be leveraged to optimize the query in some way).
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/search/SortedSetMultiRangeQuery.java:
##########
@@ -0,0 +1,300 @@
+/*
+ * 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.sandbox.search;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Objects;
+import org.apache.lucene.document.SortedSetDocValuesField;
+import org.apache.lucene.index.DocValues;
+import org.apache.lucene.index.DocValuesSkipper;
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.index.SortedSetDocValues;
+import org.apache.lucene.index.TermsEnum;
+import org.apache.lucene.search.BooleanQuery;
+import org.apache.lucene.search.ConstantScoreScorer;
+import org.apache.lucene.search.ConstantScoreWeight;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.search.DocValuesRangeIterator;
+import org.apache.lucene.search.IndexSearcher;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.search.QueryVisitor;
+import org.apache.lucene.search.ScoreMode;
+import org.apache.lucene.search.Scorer;
+import org.apache.lucene.search.ScorerSupplier;
+import org.apache.lucene.search.TwoPhaseIterator;
+import org.apache.lucene.search.Weight;
+import org.apache.lucene.util.ArrayUtil;
+import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.LongBitSet;
+
+/** A union multiple ranges over SortedSetDocValuesField */
+public class SortedSetMultiRangeQuery extends Query {
+ private final String field;
+ private final int bytesPerDim;
+ private final ArrayUtil.ByteArrayComparator comparator;
+ List<MultiRangeQuery.RangeClause> rangeClauses;
+
+ SortedSetMultiRangeQuery(
+ String name,
+ List<MultiRangeQuery.RangeClause> clauses,
+ int bytes,
+ ArrayUtil.ByteArrayComparator comparator) {
+ this.field = name;
+ this.rangeClauses = clauses;
+ this.bytesPerDim = bytes;
+ this.comparator = comparator;
+ }
+
+ /** Builder for creating a SortedSetMultiRangeQuery. */
+ public static class Builder {
+ private final String name;
+ protected final List<MultiRangeQuery.RangeClause> clauses = new ArrayList<>();
+ private final int bytes;
+ private final ArrayUtil.ByteArrayComparator comparator;
+
+ public Builder(String name, int bytes) {
+ this.name = Objects.requireNonNull(name);
+ this.bytes = bytes; // TODO assrt positive
+ this.comparator = ArrayUtil.getUnsignedComparator(bytes);
+ }
+
+ public Builder add(BytesRef lowerValue, BytesRef upperValue) {
+ byte[] low = lowerValue.clone().bytes;
+ byte[] up = upperValue.clone().bytes;
+ if (this.comparator.compare(low, 0, up, 0) > 0) {
+ throw new IllegalArgumentException("lowerValue must be <= upperValue");
+ } else {
+ clauses.add(new MultiRangeQuery.RangeClause(low, up));
+ }
+ return this;
+ }
+
+ public Query build() {
+ if (clauses.isEmpty()) {
+ return new BooleanQuery.Builder().build();
+ }
+ if (clauses.size() == 1) {
+ return SortedSetDocValuesField.newSlowRangeQuery(
+ name,
+ new BytesRef(clauses.getFirst().lowerValue),
+ new BytesRef(clauses.getFirst().upperValue),
+ true,
+ true);
+ }
+ return new SortedSetMultiRangeQuery(name, clauses, this.bytes, comparator);
+ }
+ }
+
+ @Override
+ public Query rewrite(IndexSearcher indexSearcher) throws IOException {
+ ArrayList<MultiRangeQuery.RangeClause> sortedClauses = new ArrayList<>(this.rangeClauses);
+ sortedClauses.sort(
+ (o1, o2) -> {
+ // if (result == 0) {
+ // return comparator.compare(o1.upperValue, 0, o2.upperValue, 0);
+ // } else {
+ return comparator.compare(o1.lowerValue, 0, o2.lowerValue, 0);
+ // }
+ });
+ if (!this.rangeClauses.equals(sortedClauses)) {
+ return new SortedSetMultiRangeQuery(
+ this.field, sortedClauses, this.bytesPerDim, this.comparator);
+ } else {
+ return this;
+ }
+ }
+
+ @Override
+ public String toString(String fld) {
+ return "SortedSetMultiRangeQuery{"
+ + "field='"
+ + fld
+ + '\''
+ + ", rangeClauses="
+ + rangeClauses
+ + // TODO better toString
+ '}';
+ }
+
+ // what TODO with reverse ranges ???
+ @Override
+ public Weight createWeight(IndexSearcher searcher, ScoreMode scoreMode, float boost)
+ throws IOException {
+ return new ConstantScoreWeight(this, boost) {
+ @Override
+ public ScorerSupplier scorerSupplier(LeafReaderContext context) throws IOException {
+ if (context.reader().getFieldInfos().fieldInfo(field) == null) {
+ return null;
+ }
+ DocValuesSkipper skipper = context.reader().getDocValuesSkipper(field);
+ SortedSetDocValues values = DocValues.getSortedSet(context.reader(), field);
+ // implement ScorerSupplier, since we do some expensive stuff to make a scorer
+ return new ScorerSupplier() {
+ @Override
+ public Scorer get(long leadCost) throws IOException {
+ if (rangeClauses.isEmpty()) {
+ return empty();
+ }
+ TermsEnum termsEnum = values.termsEnum();
+ LongBitSet matchingOrdsShifted = null;
+ long minOrd = 0, maxOrd = values.getValueCount() - 1;
+ long matchesAbove =
+ values.getValueCount(); // it's last range goes to maxOrd, by default - no match
+ long maxSeenOrd = values.getValueCount();
+ TermsEnum.SeekStatus seekStatus = TermsEnum.SeekStatus.NOT_FOUND;
+ for (int r = 0; r < rangeClauses.size(); r++) {
+ MultiRangeQuery.RangeClause range = rangeClauses.get(r);
+ long startingOrd;
+ seekStatus = termsEnum.seekCeil(new BytesRef(range.lowerValue));
+ if (matchingOrdsShifted == null) { // first iter
+ if (seekStatus == TermsEnum.SeekStatus.END) {
+ return empty(); // no bitset yet, give up
+ }
+ minOrd = termsEnum.ord();
+ if (skipper != null) {
+ minOrd = Math.max(minOrd, skipper.minValue());
+ maxOrd = Math.min(maxOrd, skipper.maxValue());
+ }
+ if (maxOrd < minOrd) {
+ return empty();
+ }
+ startingOrd = minOrd;
+ } else {
+ if (seekStatus == TermsEnum.SeekStatus.END) {
+ break; // ranges - we are done, terms are exhausted
+ } else {
+ startingOrd = termsEnum.ord();
+ }
+ }
+ byte[] upper = range.upperValue; // TODO ignore reverse ranges
+ // looking for overlap
+ for (int overlap = r + 1; overlap < rangeClauses.size(); overlap++, r++) {
+ MultiRangeQuery.RangeClause mayOverlap = rangeClauses.get(overlap);
+ assert comparator.compare(range.lowerValue, 0, mayOverlap.lowerValue, 0) <= 0
+ : "since they are sorted";
+ // TODO it might be contiguous ranges, it's worth to check but I have no idea how
+ if (comparator.compare(mayOverlap.lowerValue, 0, upper, 0) <= 0) {
+ // overlap, expand if needed
+ if (comparator.compare(upper, 0, mayOverlap.upperValue, 0) < 0) {
+ upper = mayOverlap.upperValue;
+ }
+ // continue; // skip overlapping rng
+ } else {
+ break; // no r++
+ }
+ }
+ seekStatus = termsEnum.seekCeil(new BytesRef(upper));
+
+ if (seekStatus == TermsEnum.SeekStatus.END) {
+ maxSeenOrd = maxOrd; // perhaps it's worth to set for skipper
+ matchesAbove = startingOrd;
+ break; // no need to create bitset
+ }
+ maxSeenOrd =
+ seekStatus == TermsEnum.SeekStatus.FOUND
+ ? termsEnum.ord()
+ : termsEnum.ord() - 1; // floor
+
+ if (matchingOrdsShifted == null) {
+ matchingOrdsShifted = new LongBitSet(maxOrd + 1 - minOrd);
+ }
+ matchingOrdsShifted.set(
+ startingOrd - minOrd, maxSeenOrd - minOrd + 1); // up is exclusive
+ }
+ /// ranges are over, there might be no set!!
+ TwoPhaseIterator iterator;
+ long finalMatchesAbove = matchesAbove;
+ LongBitSet finalMatchingOrdsShifted = matchingOrdsShifted;
+ long finalMinOrd = minOrd;
+ iterator =
+ new TwoPhaseIterator(values) {
+ // TODO unwrap singleton?
+ @Override
+ public boolean matches() throws IOException {
+ for (int i = 0; i < values.docValueCount(); i++) {
+ long ord = values.nextOrd();
+ if (ord >= finalMinOrd
+ && ((finalMatchesAbove < values.getValueCount()
+ && ord >= finalMatchesAbove)
+ || finalMatchingOrdsShifted.get(ord - finalMinOrd))) {
Review Comment:
This approach of densely memorizing all ordinals that fall within the ranges has me a bit worried. This could potentially be a quite large bitset. I wonder if we could instead just keep track of all the ranges actually represented in the query and then just check against them for each doc ord? Like what we do in `SortedSetDocValuesRangeQuery` but keeping tracking of multiple min/max tuples to check against instead of only one? Is there a reason you didn't go with that approach and feel the dense bitset is necessary here?
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/search/SortedSetMultiRangeQuery.java:
##########
@@ -0,0 +1,300 @@
+/*
+ * 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.sandbox.search;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Objects;
+import org.apache.lucene.document.SortedSetDocValuesField;
+import org.apache.lucene.index.DocValues;
+import org.apache.lucene.index.DocValuesSkipper;
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.index.SortedSetDocValues;
+import org.apache.lucene.index.TermsEnum;
+import org.apache.lucene.search.BooleanQuery;
+import org.apache.lucene.search.ConstantScoreScorer;
+import org.apache.lucene.search.ConstantScoreWeight;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.search.DocValuesRangeIterator;
+import org.apache.lucene.search.IndexSearcher;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.search.QueryVisitor;
+import org.apache.lucene.search.ScoreMode;
+import org.apache.lucene.search.Scorer;
+import org.apache.lucene.search.ScorerSupplier;
+import org.apache.lucene.search.TwoPhaseIterator;
+import org.apache.lucene.search.Weight;
+import org.apache.lucene.util.ArrayUtil;
+import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.LongBitSet;
+
+/** A union multiple ranges over SortedSetDocValuesField */
+public class SortedSetMultiRangeQuery extends Query {
+ private final String field;
+ private final int bytesPerDim;
+ private final ArrayUtil.ByteArrayComparator comparator;
+ List<MultiRangeQuery.RangeClause> rangeClauses;
+
+ SortedSetMultiRangeQuery(
+ String name,
+ List<MultiRangeQuery.RangeClause> clauses,
+ int bytes,
+ ArrayUtil.ByteArrayComparator comparator) {
+ this.field = name;
+ this.rangeClauses = clauses;
+ this.bytesPerDim = bytes;
+ this.comparator = comparator;
+ }
+
+ /** Builder for creating a SortedSetMultiRangeQuery. */
+ public static class Builder {
+ private final String name;
+ protected final List<MultiRangeQuery.RangeClause> clauses = new ArrayList<>();
+ private final int bytes;
+ private final ArrayUtil.ByteArrayComparator comparator;
+
+ public Builder(String name, int bytes) {
+ this.name = Objects.requireNonNull(name);
+ this.bytes = bytes; // TODO assrt positive
+ this.comparator = ArrayUtil.getUnsignedComparator(bytes);
+ }
+
+ public Builder add(BytesRef lowerValue, BytesRef upperValue) {
+ byte[] low = lowerValue.clone().bytes;
+ byte[] up = upperValue.clone().bytes;
+ if (this.comparator.compare(low, 0, up, 0) > 0) {
+ throw new IllegalArgumentException("lowerValue must be <= upperValue");
+ } else {
+ clauses.add(new MultiRangeQuery.RangeClause(low, up));
+ }
+ return this;
+ }
+
+ public Query build() {
+ if (clauses.isEmpty()) {
+ return new BooleanQuery.Builder().build();
+ }
+ if (clauses.size() == 1) {
+ return SortedSetDocValuesField.newSlowRangeQuery(
+ name,
+ new BytesRef(clauses.getFirst().lowerValue),
+ new BytesRef(clauses.getFirst().upperValue),
+ true,
+ true);
+ }
+ return new SortedSetMultiRangeQuery(name, clauses, this.bytes, comparator);
+ }
+ }
+
+ @Override
+ public Query rewrite(IndexSearcher indexSearcher) throws IOException {
+ ArrayList<MultiRangeQuery.RangeClause> sortedClauses = new ArrayList<>(this.rangeClauses);
+ sortedClauses.sort(
+ (o1, o2) -> {
+ // if (result == 0) {
+ // return comparator.compare(o1.upperValue, 0, o2.upperValue, 0);
+ // } else {
+ return comparator.compare(o1.lowerValue, 0, o2.lowerValue, 0);
+ // }
+ });
+ if (!this.rangeClauses.equals(sortedClauses)) {
+ return new SortedSetMultiRangeQuery(
+ this.field, sortedClauses, this.bytesPerDim, this.comparator);
+ } else {
+ return this;
+ }
+ }
+
+ @Override
+ public String toString(String fld) {
+ return "SortedSetMultiRangeQuery{"
+ + "field='"
+ + fld
+ + '\''
+ + ", rangeClauses="
+ + rangeClauses
+ + // TODO better toString
+ '}';
+ }
+
+ // what TODO with reverse ranges ???
+ @Override
+ public Weight createWeight(IndexSearcher searcher, ScoreMode scoreMode, float boost)
+ throws IOException {
+ return new ConstantScoreWeight(this, boost) {
+ @Override
+ public ScorerSupplier scorerSupplier(LeafReaderContext context) throws IOException {
+ if (context.reader().getFieldInfos().fieldInfo(field) == null) {
+ return null;
+ }
+ DocValuesSkipper skipper = context.reader().getDocValuesSkipper(field);
+ SortedSetDocValues values = DocValues.getSortedSet(context.reader(), field);
+ // implement ScorerSupplier, since we do some expensive stuff to make a scorer
+ return new ScorerSupplier() {
+ @Override
+ public Scorer get(long leadCost) throws IOException {
+ if (rangeClauses.isEmpty()) {
+ return empty();
+ }
+ TermsEnum termsEnum = values.termsEnum();
+ LongBitSet matchingOrdsShifted = null;
+ long minOrd = 0, maxOrd = values.getValueCount() - 1;
+ long matchesAbove =
+ values.getValueCount(); // it's last range goes to maxOrd, by default - no match
+ long maxSeenOrd = values.getValueCount();
+ TermsEnum.SeekStatus seekStatus = TermsEnum.SeekStatus.NOT_FOUND;
+ for (int r = 0; r < rangeClauses.size(); r++) {
+ MultiRangeQuery.RangeClause range = rangeClauses.get(r);
+ long startingOrd;
+ seekStatus = termsEnum.seekCeil(new BytesRef(range.lowerValue));
+ if (matchingOrdsShifted == null) { // first iter
+ if (seekStatus == TermsEnum.SeekStatus.END) {
+ return empty(); // no bitset yet, give up
+ }
+ minOrd = termsEnum.ord();
+ if (skipper != null) {
+ minOrd = Math.max(minOrd, skipper.minValue());
+ maxOrd = Math.min(maxOrd, skipper.maxValue());
+ }
+ if (maxOrd < minOrd) {
Review Comment:
I'm not sure this can ever happen?
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/search/SortedSetMultiRangeQuery.java:
##########
@@ -0,0 +1,300 @@
+/*
+ * 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.sandbox.search;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Objects;
+import org.apache.lucene.document.SortedSetDocValuesField;
+import org.apache.lucene.index.DocValues;
+import org.apache.lucene.index.DocValuesSkipper;
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.index.SortedSetDocValues;
+import org.apache.lucene.index.TermsEnum;
+import org.apache.lucene.search.BooleanQuery;
+import org.apache.lucene.search.ConstantScoreScorer;
+import org.apache.lucene.search.ConstantScoreWeight;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.search.DocValuesRangeIterator;
+import org.apache.lucene.search.IndexSearcher;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.search.QueryVisitor;
+import org.apache.lucene.search.ScoreMode;
+import org.apache.lucene.search.Scorer;
+import org.apache.lucene.search.ScorerSupplier;
+import org.apache.lucene.search.TwoPhaseIterator;
+import org.apache.lucene.search.Weight;
+import org.apache.lucene.util.ArrayUtil;
+import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.LongBitSet;
+
+/** A union multiple ranges over SortedSetDocValuesField */
+public class SortedSetMultiRangeQuery extends Query {
+ private final String field;
+ private final int bytesPerDim;
+ private final ArrayUtil.ByteArrayComparator comparator;
+ List<MultiRangeQuery.RangeClause> rangeClauses;
+
+ SortedSetMultiRangeQuery(
+ String name,
+ List<MultiRangeQuery.RangeClause> clauses,
+ int bytes,
+ ArrayUtil.ByteArrayComparator comparator) {
+ this.field = name;
+ this.rangeClauses = clauses;
+ this.bytesPerDim = bytes;
+ this.comparator = comparator;
+ }
+
+ /** Builder for creating a SortedSetMultiRangeQuery. */
+ public static class Builder {
+ private final String name;
+ protected final List<MultiRangeQuery.RangeClause> clauses = new ArrayList<>();
+ private final int bytes;
+ private final ArrayUtil.ByteArrayComparator comparator;
+
+ public Builder(String name, int bytes) {
+ this.name = Objects.requireNonNull(name);
+ this.bytes = bytes; // TODO assrt positive
+ this.comparator = ArrayUtil.getUnsignedComparator(bytes);
+ }
+
+ public Builder add(BytesRef lowerValue, BytesRef upperValue) {
+ byte[] low = lowerValue.clone().bytes;
Review Comment:
You need to be aware of `offset` here. It might be better to array-copy the underlying bytes into a new array instead of cloning?
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/search/SortedSetMultiRangeQuery.java:
##########
@@ -0,0 +1,300 @@
+/*
+ * 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.sandbox.search;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Objects;
+import org.apache.lucene.document.SortedSetDocValuesField;
+import org.apache.lucene.index.DocValues;
+import org.apache.lucene.index.DocValuesSkipper;
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.index.SortedSetDocValues;
+import org.apache.lucene.index.TermsEnum;
+import org.apache.lucene.search.BooleanQuery;
+import org.apache.lucene.search.ConstantScoreScorer;
+import org.apache.lucene.search.ConstantScoreWeight;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.search.DocValuesRangeIterator;
+import org.apache.lucene.search.IndexSearcher;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.search.QueryVisitor;
+import org.apache.lucene.search.ScoreMode;
+import org.apache.lucene.search.Scorer;
+import org.apache.lucene.search.ScorerSupplier;
+import org.apache.lucene.search.TwoPhaseIterator;
+import org.apache.lucene.search.Weight;
+import org.apache.lucene.util.ArrayUtil;
+import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.LongBitSet;
+
+/** A union multiple ranges over SortedSetDocValuesField */
+public class SortedSetMultiRangeQuery extends Query {
+ private final String field;
+ private final int bytesPerDim;
+ private final ArrayUtil.ByteArrayComparator comparator;
+ List<MultiRangeQuery.RangeClause> rangeClauses;
+
+ SortedSetMultiRangeQuery(
+ String name,
+ List<MultiRangeQuery.RangeClause> clauses,
+ int bytes,
+ ArrayUtil.ByteArrayComparator comparator) {
+ this.field = name;
+ this.rangeClauses = clauses;
+ this.bytesPerDim = bytes;
+ this.comparator = comparator;
+ }
+
+ /** Builder for creating a SortedSetMultiRangeQuery. */
+ public static class Builder {
+ private final String name;
+ protected final List<MultiRangeQuery.RangeClause> clauses = new ArrayList<>();
+ private final int bytes;
Review Comment:
nit: maybe `bytesPerDim` (and renaming elsewhere as well to be consistent)?
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/search/SortedSetMultiRangeQuery.java:
##########
@@ -0,0 +1,300 @@
+/*
+ * 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.sandbox.search;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Objects;
+import org.apache.lucene.document.SortedSetDocValuesField;
+import org.apache.lucene.index.DocValues;
+import org.apache.lucene.index.DocValuesSkipper;
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.index.SortedSetDocValues;
+import org.apache.lucene.index.TermsEnum;
+import org.apache.lucene.search.BooleanQuery;
+import org.apache.lucene.search.ConstantScoreScorer;
+import org.apache.lucene.search.ConstantScoreWeight;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.search.DocValuesRangeIterator;
+import org.apache.lucene.search.IndexSearcher;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.search.QueryVisitor;
+import org.apache.lucene.search.ScoreMode;
+import org.apache.lucene.search.Scorer;
+import org.apache.lucene.search.ScorerSupplier;
+import org.apache.lucene.search.TwoPhaseIterator;
+import org.apache.lucene.search.Weight;
+import org.apache.lucene.util.ArrayUtil;
+import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.LongBitSet;
+
+/** A union multiple ranges over SortedSetDocValuesField */
+public class SortedSetMultiRangeQuery extends Query {
+ private final String field;
+ private final int bytesPerDim;
+ private final ArrayUtil.ByteArrayComparator comparator;
+ List<MultiRangeQuery.RangeClause> rangeClauses;
+
+ SortedSetMultiRangeQuery(
+ String name,
+ List<MultiRangeQuery.RangeClause> clauses,
+ int bytes,
+ ArrayUtil.ByteArrayComparator comparator) {
+ this.field = name;
+ this.rangeClauses = clauses;
+ this.bytesPerDim = bytes;
+ this.comparator = comparator;
+ }
+
+ /** Builder for creating a SortedSetMultiRangeQuery. */
+ public static class Builder {
+ private final String name;
+ protected final List<MultiRangeQuery.RangeClause> clauses = new ArrayList<>();
+ private final int bytes;
+ private final ArrayUtil.ByteArrayComparator comparator;
+
+ public Builder(String name, int bytes) {
+ this.name = Objects.requireNonNull(name);
+ this.bytes = bytes; // TODO assrt positive
+ this.comparator = ArrayUtil.getUnsignedComparator(bytes);
+ }
+
+ public Builder add(BytesRef lowerValue, BytesRef upperValue) {
+ byte[] low = lowerValue.clone().bytes;
+ byte[] up = upperValue.clone().bytes;
+ if (this.comparator.compare(low, 0, up, 0) > 0) {
+ throw new IllegalArgumentException("lowerValue must be <= upperValue");
+ } else {
+ clauses.add(new MultiRangeQuery.RangeClause(low, up));
+ }
+ return this;
+ }
+
+ public Query build() {
+ if (clauses.isEmpty()) {
+ return new BooleanQuery.Builder().build();
+ }
+ if (clauses.size() == 1) {
+ return SortedSetDocValuesField.newSlowRangeQuery(
+ name,
+ new BytesRef(clauses.getFirst().lowerValue),
+ new BytesRef(clauses.getFirst().upperValue),
+ true,
+ true);
+ }
+ return new SortedSetMultiRangeQuery(name, clauses, this.bytes, comparator);
+ }
+ }
+
+ @Override
+ public Query rewrite(IndexSearcher indexSearcher) throws IOException {
+ ArrayList<MultiRangeQuery.RangeClause> sortedClauses = new ArrayList<>(this.rangeClauses);
+ sortedClauses.sort(
+ (o1, o2) -> {
+ // if (result == 0) {
+ // return comparator.compare(o1.upperValue, 0, o2.upperValue, 0);
+ // } else {
+ return comparator.compare(o1.lowerValue, 0, o2.lowerValue, 0);
+ // }
+ });
+ if (!this.rangeClauses.equals(sortedClauses)) {
+ return new SortedSetMultiRangeQuery(
+ this.field, sortedClauses, this.bytesPerDim, this.comparator);
+ } else {
+ return this;
+ }
+ }
+
+ @Override
+ public String toString(String fld) {
+ return "SortedSetMultiRangeQuery{"
+ + "field='"
+ + fld
+ + '\''
+ + ", rangeClauses="
+ + rangeClauses
+ + // TODO better toString
+ '}';
+ }
+
+ // what TODO with reverse ranges ???
+ @Override
+ public Weight createWeight(IndexSearcher searcher, ScoreMode scoreMode, float boost)
+ throws IOException {
+ return new ConstantScoreWeight(this, boost) {
+ @Override
+ public ScorerSupplier scorerSupplier(LeafReaderContext context) throws IOException {
+ if (context.reader().getFieldInfos().fieldInfo(field) == null) {
+ return null;
+ }
+ DocValuesSkipper skipper = context.reader().getDocValuesSkipper(field);
+ SortedSetDocValues values = DocValues.getSortedSet(context.reader(), field);
+ // implement ScorerSupplier, since we do some expensive stuff to make a scorer
+ return new ScorerSupplier() {
+ @Override
+ public Scorer get(long leadCost) throws IOException {
+ if (rangeClauses.isEmpty()) {
Review Comment:
Can we make sure `rangeClauses` is never empty at this point? Ideally we would want to have returned a null scorer supplier if this was the case. But I think you have this already covered elsewhere in your builder logic? So maybe we can just `assert` here instead?
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/search/SortedSetMultiRangeQuery.java:
##########
@@ -0,0 +1,300 @@
+/*
+ * 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.sandbox.search;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Objects;
+import org.apache.lucene.document.SortedSetDocValuesField;
+import org.apache.lucene.index.DocValues;
+import org.apache.lucene.index.DocValuesSkipper;
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.index.SortedSetDocValues;
+import org.apache.lucene.index.TermsEnum;
+import org.apache.lucene.search.BooleanQuery;
+import org.apache.lucene.search.ConstantScoreScorer;
+import org.apache.lucene.search.ConstantScoreWeight;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.search.DocValuesRangeIterator;
+import org.apache.lucene.search.IndexSearcher;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.search.QueryVisitor;
+import org.apache.lucene.search.ScoreMode;
+import org.apache.lucene.search.Scorer;
+import org.apache.lucene.search.ScorerSupplier;
+import org.apache.lucene.search.TwoPhaseIterator;
+import org.apache.lucene.search.Weight;
+import org.apache.lucene.util.ArrayUtil;
+import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.LongBitSet;
+
+/** A union multiple ranges over SortedSetDocValuesField */
+public class SortedSetMultiRangeQuery extends Query {
Review Comment:
This is a bit of an odd companion to `MultiRangeQuery`. `MultiRangeQuery` seems meant for numeric-based points in the points index, while this is specific to term ranges. I'm not sure I have a great concrete suggestion here, but I think the way it's currently positioned (reusing some internal classes of MRQ and being in the same sandbox package) could be confusing.
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/search/SortedSetMultiRangeQuery.java:
##########
@@ -0,0 +1,300 @@
+/*
+ * 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.sandbox.search;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Objects;
+import org.apache.lucene.document.SortedSetDocValuesField;
+import org.apache.lucene.index.DocValues;
+import org.apache.lucene.index.DocValuesSkipper;
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.index.SortedSetDocValues;
+import org.apache.lucene.index.TermsEnum;
+import org.apache.lucene.search.BooleanQuery;
+import org.apache.lucene.search.ConstantScoreScorer;
+import org.apache.lucene.search.ConstantScoreWeight;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.search.DocValuesRangeIterator;
+import org.apache.lucene.search.IndexSearcher;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.search.QueryVisitor;
+import org.apache.lucene.search.ScoreMode;
+import org.apache.lucene.search.Scorer;
+import org.apache.lucene.search.ScorerSupplier;
+import org.apache.lucene.search.TwoPhaseIterator;
+import org.apache.lucene.search.Weight;
+import org.apache.lucene.util.ArrayUtil;
+import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.LongBitSet;
+
+/** A union multiple ranges over SortedSetDocValuesField */
+public class SortedSetMultiRangeQuery extends Query {
+ private final String field;
+ private final int bytesPerDim;
+ private final ArrayUtil.ByteArrayComparator comparator;
+ List<MultiRangeQuery.RangeClause> rangeClauses;
+
+ SortedSetMultiRangeQuery(
+ String name,
+ List<MultiRangeQuery.RangeClause> clauses,
+ int bytes,
+ ArrayUtil.ByteArrayComparator comparator) {
+ this.field = name;
+ this.rangeClauses = clauses;
+ this.bytesPerDim = bytes;
+ this.comparator = comparator;
+ }
+
+ /** Builder for creating a SortedSetMultiRangeQuery. */
+ public static class Builder {
+ private final String name;
+ protected final List<MultiRangeQuery.RangeClause> clauses = new ArrayList<>();
+ private final int bytes;
+ private final ArrayUtil.ByteArrayComparator comparator;
+
+ public Builder(String name, int bytes) {
+ this.name = Objects.requireNonNull(name);
+ this.bytes = bytes; // TODO assrt positive
+ this.comparator = ArrayUtil.getUnsignedComparator(bytes);
+ }
+
+ public Builder add(BytesRef lowerValue, BytesRef upperValue) {
+ byte[] low = lowerValue.clone().bytes;
+ byte[] up = upperValue.clone().bytes;
+ if (this.comparator.compare(low, 0, up, 0) > 0) {
+ throw new IllegalArgumentException("lowerValue must be <= upperValue");
+ } else {
+ clauses.add(new MultiRangeQuery.RangeClause(low, up));
+ }
+ return this;
+ }
+
+ public Query build() {
+ if (clauses.isEmpty()) {
+ return new BooleanQuery.Builder().build();
+ }
+ if (clauses.size() == 1) {
+ return SortedSetDocValuesField.newSlowRangeQuery(
+ name,
+ new BytesRef(clauses.getFirst().lowerValue),
+ new BytesRef(clauses.getFirst().upperValue),
+ true,
+ true);
+ }
+ return new SortedSetMultiRangeQuery(name, clauses, this.bytes, comparator);
+ }
+ }
+
+ @Override
+ public Query rewrite(IndexSearcher indexSearcher) throws IOException {
+ ArrayList<MultiRangeQuery.RangeClause> sortedClauses = new ArrayList<>(this.rangeClauses);
+ sortedClauses.sort(
+ (o1, o2) -> {
+ // if (result == 0) {
+ // return comparator.compare(o1.upperValue, 0, o2.upperValue, 0);
+ // } else {
+ return comparator.compare(o1.lowerValue, 0, o2.lowerValue, 0);
+ // }
+ });
+ if (!this.rangeClauses.equals(sortedClauses)) {
+ return new SortedSetMultiRangeQuery(
+ this.field, sortedClauses, this.bytesPerDim, this.comparator);
+ } else {
+ return this;
+ }
+ }
+
+ @Override
+ public String toString(String fld) {
+ return "SortedSetMultiRangeQuery{"
+ + "field='"
+ + fld
+ + '\''
+ + ", rangeClauses="
+ + rangeClauses
+ + // TODO better toString
+ '}';
+ }
+
+ // what TODO with reverse ranges ???
+ @Override
+ public Weight createWeight(IndexSearcher searcher, ScoreMode scoreMode, float boost)
+ throws IOException {
+ return new ConstantScoreWeight(this, boost) {
+ @Override
+ public ScorerSupplier scorerSupplier(LeafReaderContext context) throws IOException {
+ if (context.reader().getFieldInfos().fieldInfo(field) == null) {
+ return null;
+ }
+ DocValuesSkipper skipper = context.reader().getDocValuesSkipper(field);
Review Comment:
Let's move these lines inside `#get`. No need to do this work up-front in case a scorer is never pulled.
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/search/SortedSetMultiRangeQuery.java:
##########
@@ -0,0 +1,300 @@
+/*
+ * 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.sandbox.search;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Objects;
+import org.apache.lucene.document.SortedSetDocValuesField;
+import org.apache.lucene.index.DocValues;
+import org.apache.lucene.index.DocValuesSkipper;
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.index.SortedSetDocValues;
+import org.apache.lucene.index.TermsEnum;
+import org.apache.lucene.search.BooleanQuery;
+import org.apache.lucene.search.ConstantScoreScorer;
+import org.apache.lucene.search.ConstantScoreWeight;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.search.DocValuesRangeIterator;
+import org.apache.lucene.search.IndexSearcher;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.search.QueryVisitor;
+import org.apache.lucene.search.ScoreMode;
+import org.apache.lucene.search.Scorer;
+import org.apache.lucene.search.ScorerSupplier;
+import org.apache.lucene.search.TwoPhaseIterator;
+import org.apache.lucene.search.Weight;
+import org.apache.lucene.util.ArrayUtil;
+import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.LongBitSet;
+
+/** A union multiple ranges over SortedSetDocValuesField */
+public class SortedSetMultiRangeQuery extends Query {
+ private final String field;
+ private final int bytesPerDim;
+ private final ArrayUtil.ByteArrayComparator comparator;
+ List<MultiRangeQuery.RangeClause> rangeClauses;
+
+ SortedSetMultiRangeQuery(
+ String name,
+ List<MultiRangeQuery.RangeClause> clauses,
+ int bytes,
+ ArrayUtil.ByteArrayComparator comparator) {
+ this.field = name;
+ this.rangeClauses = clauses;
+ this.bytesPerDim = bytes;
+ this.comparator = comparator;
+ }
+
+ /** Builder for creating a SortedSetMultiRangeQuery. */
+ public static class Builder {
+ private final String name;
Review Comment:
nit: maybe `fieldName`?
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/search/SortedSetMultiRangeQuery.java:
##########
@@ -0,0 +1,300 @@
+/*
+ * 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.sandbox.search;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Objects;
+import org.apache.lucene.document.SortedSetDocValuesField;
+import org.apache.lucene.index.DocValues;
+import org.apache.lucene.index.DocValuesSkipper;
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.index.SortedSetDocValues;
+import org.apache.lucene.index.TermsEnum;
+import org.apache.lucene.search.BooleanQuery;
+import org.apache.lucene.search.ConstantScoreScorer;
+import org.apache.lucene.search.ConstantScoreWeight;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.search.DocValuesRangeIterator;
+import org.apache.lucene.search.IndexSearcher;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.search.QueryVisitor;
+import org.apache.lucene.search.ScoreMode;
+import org.apache.lucene.search.Scorer;
+import org.apache.lucene.search.ScorerSupplier;
+import org.apache.lucene.search.TwoPhaseIterator;
+import org.apache.lucene.search.Weight;
+import org.apache.lucene.util.ArrayUtil;
+import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.LongBitSet;
+
+/** A union multiple ranges over SortedSetDocValuesField */
+public class SortedSetMultiRangeQuery extends Query {
+ private final String field;
+ private final int bytesPerDim;
+ private final ArrayUtil.ByteArrayComparator comparator;
+ List<MultiRangeQuery.RangeClause> rangeClauses;
+
+ SortedSetMultiRangeQuery(
+ String name,
+ List<MultiRangeQuery.RangeClause> clauses,
+ int bytes,
+ ArrayUtil.ByteArrayComparator comparator) {
+ this.field = name;
+ this.rangeClauses = clauses;
+ this.bytesPerDim = bytes;
+ this.comparator = comparator;
+ }
+
+ /** Builder for creating a SortedSetMultiRangeQuery. */
+ public static class Builder {
+ private final String name;
+ protected final List<MultiRangeQuery.RangeClause> clauses = new ArrayList<>();
+ private final int bytes;
+ private final ArrayUtil.ByteArrayComparator comparator;
+
+ public Builder(String name, int bytes) {
+ this.name = Objects.requireNonNull(name);
+ this.bytes = bytes; // TODO assrt positive
+ this.comparator = ArrayUtil.getUnsignedComparator(bytes);
+ }
+
+ public Builder add(BytesRef lowerValue, BytesRef upperValue) {
+ byte[] low = lowerValue.clone().bytes;
+ byte[] up = upperValue.clone().bytes;
+ if (this.comparator.compare(low, 0, up, 0) > 0) {
+ throw new IllegalArgumentException("lowerValue must be <= upperValue");
+ } else {
+ clauses.add(new MultiRangeQuery.RangeClause(low, up));
+ }
+ return this;
+ }
+
+ public Query build() {
+ if (clauses.isEmpty()) {
+ return new BooleanQuery.Builder().build();
+ }
+ if (clauses.size() == 1) {
+ return SortedSetDocValuesField.newSlowRangeQuery(
+ name,
+ new BytesRef(clauses.getFirst().lowerValue),
+ new BytesRef(clauses.getFirst().upperValue),
+ true,
+ true);
+ }
+ return new SortedSetMultiRangeQuery(name, clauses, this.bytes, comparator);
+ }
+ }
+
+ @Override
+ public Query rewrite(IndexSearcher indexSearcher) throws IOException {
+ ArrayList<MultiRangeQuery.RangeClause> sortedClauses = new ArrayList<>(this.rangeClauses);
+ sortedClauses.sort(
+ (o1, o2) -> {
+ // if (result == 0) {
+ // return comparator.compare(o1.upperValue, 0, o2.upperValue, 0);
+ // } else {
+ return comparator.compare(o1.lowerValue, 0, o2.lowerValue, 0);
+ // }
+ });
+ if (!this.rangeClauses.equals(sortedClauses)) {
+ return new SortedSetMultiRangeQuery(
+ this.field, sortedClauses, this.bytesPerDim, this.comparator);
+ } else {
+ return this;
+ }
+ }
+
+ @Override
+ public String toString(String fld) {
+ return "SortedSetMultiRangeQuery{"
+ + "field='"
+ + fld
+ + '\''
+ + ", rangeClauses="
+ + rangeClauses
+ + // TODO better toString
+ '}';
+ }
+
+ // what TODO with reverse ranges ???
+ @Override
+ public Weight createWeight(IndexSearcher searcher, ScoreMode scoreMode, float boost)
+ throws IOException {
+ return new ConstantScoreWeight(this, boost) {
+ @Override
+ public ScorerSupplier scorerSupplier(LeafReaderContext context) throws IOException {
+ if (context.reader().getFieldInfos().fieldInfo(field) == null) {
+ return null;
+ }
+ DocValuesSkipper skipper = context.reader().getDocValuesSkipper(field);
+ SortedSetDocValues values = DocValues.getSortedSet(context.reader(), field);
+ // implement ScorerSupplier, since we do some expensive stuff to make a scorer
+ return new ScorerSupplier() {
+ @Override
+ public Scorer get(long leadCost) throws IOException {
+ if (rangeClauses.isEmpty()) {
+ return empty();
+ }
+ TermsEnum termsEnum = values.termsEnum();
+ LongBitSet matchingOrdsShifted = null;
+ long minOrd = 0, maxOrd = values.getValueCount() - 1;
+ long matchesAbove =
+ values.getValueCount(); // it's last range goes to maxOrd, by default - no match
+ long maxSeenOrd = values.getValueCount();
+ TermsEnum.SeekStatus seekStatus = TermsEnum.SeekStatus.NOT_FOUND;
+ for (int r = 0; r < rangeClauses.size(); r++) {
+ MultiRangeQuery.RangeClause range = rangeClauses.get(r);
+ long startingOrd;
+ seekStatus = termsEnum.seekCeil(new BytesRef(range.lowerValue));
+ if (matchingOrdsShifted == null) { // first iter
+ if (seekStatus == TermsEnum.SeekStatus.END) {
+ return empty(); // no bitset yet, give up
+ }
+ minOrd = termsEnum.ord();
+ if (skipper != null) {
Review Comment:
I'm not really sure I understand how the skipper helps us here. Any ordinal you get from the terms enum is going to be present somewhere in the segment, so by definition, I don't see how the global min or max from the skipper could provide tighter bounds. Maybe I'm missing something?
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/search/SortedSetMultiRangeQuery.java:
##########
@@ -0,0 +1,300 @@
+/*
+ * 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.sandbox.search;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Objects;
+import org.apache.lucene.document.SortedSetDocValuesField;
+import org.apache.lucene.index.DocValues;
+import org.apache.lucene.index.DocValuesSkipper;
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.index.SortedSetDocValues;
+import org.apache.lucene.index.TermsEnum;
+import org.apache.lucene.search.BooleanQuery;
+import org.apache.lucene.search.ConstantScoreScorer;
+import org.apache.lucene.search.ConstantScoreWeight;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.search.DocValuesRangeIterator;
+import org.apache.lucene.search.IndexSearcher;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.search.QueryVisitor;
+import org.apache.lucene.search.ScoreMode;
+import org.apache.lucene.search.Scorer;
+import org.apache.lucene.search.ScorerSupplier;
+import org.apache.lucene.search.TwoPhaseIterator;
+import org.apache.lucene.search.Weight;
+import org.apache.lucene.util.ArrayUtil;
+import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.LongBitSet;
+
+/** A union multiple ranges over SortedSetDocValuesField */
+public class SortedSetMultiRangeQuery extends Query {
+ private final String field;
+ private final int bytesPerDim;
+ private final ArrayUtil.ByteArrayComparator comparator;
+ List<MultiRangeQuery.RangeClause> rangeClauses;
+
+ SortedSetMultiRangeQuery(
+ String name,
+ List<MultiRangeQuery.RangeClause> clauses,
+ int bytes,
+ ArrayUtil.ByteArrayComparator comparator) {
+ this.field = name;
+ this.rangeClauses = clauses;
+ this.bytesPerDim = bytes;
+ this.comparator = comparator;
+ }
+
+ /** Builder for creating a SortedSetMultiRangeQuery. */
+ public static class Builder {
+ private final String name;
+ protected final List<MultiRangeQuery.RangeClause> clauses = new ArrayList<>();
+ private final int bytes;
+ private final ArrayUtil.ByteArrayComparator comparator;
+
+ public Builder(String name, int bytes) {
+ this.name = Objects.requireNonNull(name);
+ this.bytes = bytes; // TODO assrt positive
+ this.comparator = ArrayUtil.getUnsignedComparator(bytes);
+ }
+
+ public Builder add(BytesRef lowerValue, BytesRef upperValue) {
+ byte[] low = lowerValue.clone().bytes;
+ byte[] up = upperValue.clone().bytes;
+ if (this.comparator.compare(low, 0, up, 0) > 0) {
+ throw new IllegalArgumentException("lowerValue must be <= upperValue");
+ } else {
+ clauses.add(new MultiRangeQuery.RangeClause(low, up));
+ }
+ return this;
+ }
+
+ public Query build() {
+ if (clauses.isEmpty()) {
+ return new BooleanQuery.Builder().build();
+ }
+ if (clauses.size() == 1) {
+ return SortedSetDocValuesField.newSlowRangeQuery(
+ name,
+ new BytesRef(clauses.getFirst().lowerValue),
+ new BytesRef(clauses.getFirst().upperValue),
+ true,
+ true);
+ }
+ return new SortedSetMultiRangeQuery(name, clauses, this.bytes, comparator);
+ }
+ }
+
+ @Override
+ public Query rewrite(IndexSearcher indexSearcher) throws IOException {
+ ArrayList<MultiRangeQuery.RangeClause> sortedClauses = new ArrayList<>(this.rangeClauses);
+ sortedClauses.sort(
+ (o1, o2) -> {
+ // if (result == 0) {
+ // return comparator.compare(o1.upperValue, 0, o2.upperValue, 0);
+ // } else {
+ return comparator.compare(o1.lowerValue, 0, o2.lowerValue, 0);
+ // }
+ });
+ if (!this.rangeClauses.equals(sortedClauses)) {
+ return new SortedSetMultiRangeQuery(
+ this.field, sortedClauses, this.bytesPerDim, this.comparator);
+ } else {
+ return this;
+ }
+ }
+
+ @Override
+ public String toString(String fld) {
+ return "SortedSetMultiRangeQuery{"
+ + "field='"
+ + fld
+ + '\''
+ + ", rangeClauses="
+ + rangeClauses
+ + // TODO better toString
+ '}';
+ }
+
+ // what TODO with reverse ranges ???
+ @Override
+ public Weight createWeight(IndexSearcher searcher, ScoreMode scoreMode, float boost)
+ throws IOException {
+ return new ConstantScoreWeight(this, boost) {
+ @Override
+ public ScorerSupplier scorerSupplier(LeafReaderContext context) throws IOException {
+ if (context.reader().getFieldInfos().fieldInfo(field) == null) {
+ return null;
+ }
+ DocValuesSkipper skipper = context.reader().getDocValuesSkipper(field);
+ SortedSetDocValues values = DocValues.getSortedSet(context.reader(), field);
+ // implement ScorerSupplier, since we do some expensive stuff to make a scorer
+ return new ScorerSupplier() {
+ @Override
+ public Scorer get(long leadCost) throws IOException {
+ if (rangeClauses.isEmpty()) {
+ return empty();
+ }
+ TermsEnum termsEnum = values.termsEnum();
+ LongBitSet matchingOrdsShifted = null;
+ long minOrd = 0, maxOrd = values.getValueCount() - 1;
+ long matchesAbove =
+ values.getValueCount(); // it's last range goes to maxOrd, by default - no match
+ long maxSeenOrd = values.getValueCount();
+ TermsEnum.SeekStatus seekStatus = TermsEnum.SeekStatus.NOT_FOUND;
+ for (int r = 0; r < rangeClauses.size(); r++) {
+ MultiRangeQuery.RangeClause range = rangeClauses.get(r);
+ long startingOrd;
+ seekStatus = termsEnum.seekCeil(new BytesRef(range.lowerValue));
Review Comment:
There's a fair amount of `BytesRef` creation going on here. Should we just store bytes ref instances in the ranges instead of storing byte arrays then converting 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] SortedSet DV Multi Range query [lucene]
Posted by "mkhludnev (via GitHub)" <gi...@apache.org>.
mkhludnev commented on code in PR #13974:
URL: https://github.com/apache/lucene/pull/13974#discussion_r1896708416
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/search/SortedSetMultiRangeQuery.java:
##########
@@ -0,0 +1,300 @@
+/*
+ * 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.sandbox.search;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Objects;
+import org.apache.lucene.document.SortedSetDocValuesField;
+import org.apache.lucene.index.DocValues;
+import org.apache.lucene.index.DocValuesSkipper;
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.index.SortedSetDocValues;
+import org.apache.lucene.index.TermsEnum;
+import org.apache.lucene.search.BooleanQuery;
+import org.apache.lucene.search.ConstantScoreScorer;
+import org.apache.lucene.search.ConstantScoreWeight;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.search.DocValuesRangeIterator;
+import org.apache.lucene.search.IndexSearcher;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.search.QueryVisitor;
+import org.apache.lucene.search.ScoreMode;
+import org.apache.lucene.search.Scorer;
+import org.apache.lucene.search.ScorerSupplier;
+import org.apache.lucene.search.TwoPhaseIterator;
+import org.apache.lucene.search.Weight;
+import org.apache.lucene.util.ArrayUtil;
+import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.LongBitSet;
+
+/** A union multiple ranges over SortedSetDocValuesField */
+public class SortedSetMultiRangeQuery extends Query {
+ private final String field;
+ private final int bytesPerDim;
+ private final ArrayUtil.ByteArrayComparator comparator;
+ List<MultiRangeQuery.RangeClause> rangeClauses;
+
+ SortedSetMultiRangeQuery(
+ String name,
+ List<MultiRangeQuery.RangeClause> clauses,
+ int bytes,
+ ArrayUtil.ByteArrayComparator comparator) {
+ this.field = name;
+ this.rangeClauses = clauses;
+ this.bytesPerDim = bytes;
+ this.comparator = comparator;
+ }
+
+ /** Builder for creating a SortedSetMultiRangeQuery. */
+ public static class Builder {
+ private final String name;
+ protected final List<MultiRangeQuery.RangeClause> clauses = new ArrayList<>();
+ private final int bytes;
+ private final ArrayUtil.ByteArrayComparator comparator;
+
+ public Builder(String name, int bytes) {
+ this.name = Objects.requireNonNull(name);
+ this.bytes = bytes; // TODO assrt positive
+ this.comparator = ArrayUtil.getUnsignedComparator(bytes);
+ }
+
+ public Builder add(BytesRef lowerValue, BytesRef upperValue) {
+ byte[] low = lowerValue.clone().bytes;
+ byte[] up = upperValue.clone().bytes;
+ if (this.comparator.compare(low, 0, up, 0) > 0) {
+ throw new IllegalArgumentException("lowerValue must be <= upperValue");
+ } else {
+ clauses.add(new MultiRangeQuery.RangeClause(low, up));
+ }
+ return this;
+ }
+
+ public Query build() {
+ if (clauses.isEmpty()) {
+ return new BooleanQuery.Builder().build();
+ }
+ if (clauses.size() == 1) {
+ return SortedSetDocValuesField.newSlowRangeQuery(
+ name,
+ new BytesRef(clauses.getFirst().lowerValue),
+ new BytesRef(clauses.getFirst().upperValue),
+ true,
+ true);
+ }
+ return new SortedSetMultiRangeQuery(name, clauses, this.bytes, comparator);
+ }
+ }
+
+ @Override
+ public Query rewrite(IndexSearcher indexSearcher) throws IOException {
+ ArrayList<MultiRangeQuery.RangeClause> sortedClauses = new ArrayList<>(this.rangeClauses);
+ sortedClauses.sort(
+ (o1, o2) -> {
+ // if (result == 0) {
+ // return comparator.compare(o1.upperValue, 0, o2.upperValue, 0);
+ // } else {
+ return comparator.compare(o1.lowerValue, 0, o2.lowerValue, 0);
+ // }
+ });
+ if (!this.rangeClauses.equals(sortedClauses)) {
+ return new SortedSetMultiRangeQuery(
+ this.field, sortedClauses, this.bytesPerDim, this.comparator);
+ } else {
+ return this;
+ }
+ }
+
+ @Override
+ public String toString(String fld) {
+ return "SortedSetMultiRangeQuery{"
+ + "field='"
+ + fld
+ + '\''
+ + ", rangeClauses="
+ + rangeClauses
+ + // TODO better toString
+ '}';
+ }
+
+ // what TODO with reverse ranges ???
+ @Override
+ public Weight createWeight(IndexSearcher searcher, ScoreMode scoreMode, float boost)
+ throws IOException {
+ return new ConstantScoreWeight(this, boost) {
+ @Override
+ public ScorerSupplier scorerSupplier(LeafReaderContext context) throws IOException {
+ if (context.reader().getFieldInfos().fieldInfo(field) == null) {
+ return null;
+ }
+ DocValuesSkipper skipper = context.reader().getDocValuesSkipper(field);
+ SortedSetDocValues values = DocValues.getSortedSet(context.reader(), field);
+ // implement ScorerSupplier, since we do some expensive stuff to make a scorer
+ return new ScorerSupplier() {
+ @Override
+ public Scorer get(long leadCost) throws IOException {
+ if (rangeClauses.isEmpty()) {
+ return empty();
+ }
+ TermsEnum termsEnum = values.termsEnum();
+ LongBitSet matchingOrdsShifted = null;
+ long minOrd = 0, maxOrd = values.getValueCount() - 1;
+ long matchesAbove =
+ values.getValueCount(); // it's last range goes to maxOrd, by default - no match
+ long maxSeenOrd = values.getValueCount();
+ TermsEnum.SeekStatus seekStatus = TermsEnum.SeekStatus.NOT_FOUND;
+ for (int r = 0; r < rangeClauses.size(); r++) {
+ MultiRangeQuery.RangeClause range = rangeClauses.get(r);
+ long startingOrd;
+ seekStatus = termsEnum.seekCeil(new BytesRef(range.lowerValue));
+ if (matchingOrdsShifted == null) { // first iter
+ if (seekStatus == TermsEnum.SeekStatus.END) {
+ return empty(); // no bitset yet, give up
+ }
+ minOrd = termsEnum.ord();
+ if (skipper != null) {
+ minOrd = Math.max(minOrd, skipper.minValue());
+ maxOrd = Math.min(maxOrd, skipper.maxValue());
+ }
+ if (maxOrd < minOrd) {
+ return empty();
+ }
+ startingOrd = minOrd;
+ } else {
+ if (seekStatus == TermsEnum.SeekStatus.END) {
+ break; // ranges - we are done, terms are exhausted
+ } else {
+ startingOrd = termsEnum.ord();
+ }
+ }
+ byte[] upper = range.upperValue; // TODO ignore reverse ranges
+ // looking for overlap
+ for (int overlap = r + 1; overlap < rangeClauses.size(); overlap++, r++) {
+ MultiRangeQuery.RangeClause mayOverlap = rangeClauses.get(overlap);
+ assert comparator.compare(range.lowerValue, 0, mayOverlap.lowerValue, 0) <= 0
+ : "since they are sorted";
+ // TODO it might be contiguous ranges, it's worth to check but I have no idea how
+ if (comparator.compare(mayOverlap.lowerValue, 0, upper, 0) <= 0) {
+ // overlap, expand if needed
+ if (comparator.compare(upper, 0, mayOverlap.upperValue, 0) < 0) {
+ upper = mayOverlap.upperValue;
+ }
+ // continue; // skip overlapping rng
+ } else {
+ break; // no r++
+ }
+ }
+ seekStatus = termsEnum.seekCeil(new BytesRef(upper));
+
+ if (seekStatus == TermsEnum.SeekStatus.END) {
+ maxSeenOrd = maxOrd; // perhaps it's worth to set for skipper
+ matchesAbove = startingOrd;
+ break; // no need to create bitset
+ }
+ maxSeenOrd =
+ seekStatus == TermsEnum.SeekStatus.FOUND
+ ? termsEnum.ord()
+ : termsEnum.ord() - 1; // floor
+
+ if (matchingOrdsShifted == null) {
+ matchingOrdsShifted = new LongBitSet(maxOrd + 1 - minOrd);
+ }
+ matchingOrdsShifted.set(
+ startingOrd - minOrd, maxSeenOrd - minOrd + 1); // up is exclusive
+ }
+ /// ranges are over, there might be no set!!
+ TwoPhaseIterator iterator;
+ long finalMatchesAbove = matchesAbove;
+ LongBitSet finalMatchingOrdsShifted = matchingOrdsShifted;
+ long finalMinOrd = minOrd;
+ iterator =
+ new TwoPhaseIterator(values) {
+ // TODO unwrap singleton?
+ @Override
+ public boolean matches() throws IOException {
+ for (int i = 0; i < values.docValueCount(); i++) {
+ long ord = values.nextOrd();
+ if (ord >= finalMinOrd
+ && ((finalMatchesAbove < values.getValueCount()
+ && ord >= finalMatchesAbove)
+ || finalMatchingOrdsShifted.get(ord - finalMinOrd))) {
Review Comment:
I mostly agree. Thanks for sharing your considerations. Let me clarify your points:
> isn't really as feasible with DocValuesRewriteMethod
Why this "set" query can't use a tree of unique values with log(n) access complexity? These queries might be quite close to each other. In the edge case ranges are quite narrow having 1 or 2 ordinals, thus SsDvMultyRange would be the same as TermsInSet. If ranges are wide, it definitely spends more time on setting 1s in the bitset, but maybe it's not lethal due to SIMD intrinsic (who knows) with a gain on search time per doc check.
I agree it's a field for benchmarking and picking optimizations dynamically (later). Also, something like KD-tree might be applicable 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] SortedSet DV Multi Range query [lucene]
Posted by "mkhludnev (via GitHub)" <gi...@apache.org>.
mkhludnev commented on code in PR #13974:
URL: https://github.com/apache/lucene/pull/13974#discussion_r1896747989
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/search/SortedSetMultiRangeQuery.java:
##########
@@ -0,0 +1,300 @@
+/*
+ * 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.sandbox.search;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Objects;
+import org.apache.lucene.document.SortedSetDocValuesField;
+import org.apache.lucene.index.DocValues;
+import org.apache.lucene.index.DocValuesSkipper;
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.index.SortedSetDocValues;
+import org.apache.lucene.index.TermsEnum;
+import org.apache.lucene.search.BooleanQuery;
+import org.apache.lucene.search.ConstantScoreScorer;
+import org.apache.lucene.search.ConstantScoreWeight;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.search.DocValuesRangeIterator;
+import org.apache.lucene.search.IndexSearcher;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.search.QueryVisitor;
+import org.apache.lucene.search.ScoreMode;
+import org.apache.lucene.search.Scorer;
+import org.apache.lucene.search.ScorerSupplier;
+import org.apache.lucene.search.TwoPhaseIterator;
+import org.apache.lucene.search.Weight;
+import org.apache.lucene.util.ArrayUtil;
+import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.LongBitSet;
+
+/** A union multiple ranges over SortedSetDocValuesField */
+public class SortedSetMultiRangeQuery extends Query {
+ private final String field;
+ private final int bytesPerDim;
+ private final ArrayUtil.ByteArrayComparator comparator;
+ List<MultiRangeQuery.RangeClause> rangeClauses;
+
+ SortedSetMultiRangeQuery(
+ String name,
+ List<MultiRangeQuery.RangeClause> clauses,
+ int bytes,
+ ArrayUtil.ByteArrayComparator comparator) {
+ this.field = name;
+ this.rangeClauses = clauses;
+ this.bytesPerDim = bytes;
+ this.comparator = comparator;
+ }
+
+ /** Builder for creating a SortedSetMultiRangeQuery. */
+ public static class Builder {
+ private final String name;
+ protected final List<MultiRangeQuery.RangeClause> clauses = new ArrayList<>();
+ private final int bytes;
+ private final ArrayUtil.ByteArrayComparator comparator;
+
+ public Builder(String name, int bytes) {
+ this.name = Objects.requireNonNull(name);
+ this.bytes = bytes; // TODO assrt positive
+ this.comparator = ArrayUtil.getUnsignedComparator(bytes);
+ }
+
+ public Builder add(BytesRef lowerValue, BytesRef upperValue) {
+ byte[] low = lowerValue.clone().bytes;
+ byte[] up = upperValue.clone().bytes;
+ if (this.comparator.compare(low, 0, up, 0) > 0) {
+ throw new IllegalArgumentException("lowerValue must be <= upperValue");
+ } else {
+ clauses.add(new MultiRangeQuery.RangeClause(low, up));
+ }
+ return this;
+ }
+
+ public Query build() {
+ if (clauses.isEmpty()) {
+ return new BooleanQuery.Builder().build();
+ }
+ if (clauses.size() == 1) {
+ return SortedSetDocValuesField.newSlowRangeQuery(
+ name,
+ new BytesRef(clauses.getFirst().lowerValue),
+ new BytesRef(clauses.getFirst().upperValue),
+ true,
+ true);
+ }
+ return new SortedSetMultiRangeQuery(name, clauses, this.bytes, comparator);
+ }
+ }
+
+ @Override
+ public Query rewrite(IndexSearcher indexSearcher) throws IOException {
+ ArrayList<MultiRangeQuery.RangeClause> sortedClauses = new ArrayList<>(this.rangeClauses);
+ sortedClauses.sort(
+ (o1, o2) -> {
+ // if (result == 0) {
+ // return comparator.compare(o1.upperValue, 0, o2.upperValue, 0);
+ // } else {
+ return comparator.compare(o1.lowerValue, 0, o2.lowerValue, 0);
+ // }
+ });
+ if (!this.rangeClauses.equals(sortedClauses)) {
+ return new SortedSetMultiRangeQuery(
+ this.field, sortedClauses, this.bytesPerDim, this.comparator);
+ } else {
+ return this;
+ }
+ }
+
+ @Override
+ public String toString(String fld) {
+ return "SortedSetMultiRangeQuery{"
+ + "field='"
+ + fld
+ + '\''
+ + ", rangeClauses="
+ + rangeClauses
+ + // TODO better toString
+ '}';
+ }
+
+ // what TODO with reverse ranges ???
+ @Override
+ public Weight createWeight(IndexSearcher searcher, ScoreMode scoreMode, float boost)
+ throws IOException {
+ return new ConstantScoreWeight(this, boost) {
+ @Override
+ public ScorerSupplier scorerSupplier(LeafReaderContext context) throws IOException {
+ if (context.reader().getFieldInfos().fieldInfo(field) == null) {
+ return null;
+ }
+ DocValuesSkipper skipper = context.reader().getDocValuesSkipper(field);
+ SortedSetDocValues values = DocValues.getSortedSet(context.reader(), field);
+ // implement ScorerSupplier, since we do some expensive stuff to make a scorer
+ return new ScorerSupplier() {
+ @Override
+ public Scorer get(long leadCost) throws IOException {
+ if (rangeClauses.isEmpty()) {
+ return empty();
+ }
+ TermsEnum termsEnum = values.termsEnum();
+ LongBitSet matchingOrdsShifted = null;
+ long minOrd = 0, maxOrd = values.getValueCount() - 1;
+ long matchesAbove =
+ values.getValueCount(); // it's last range goes to maxOrd, by default - no match
+ long maxSeenOrd = values.getValueCount();
+ TermsEnum.SeekStatus seekStatus = TermsEnum.SeekStatus.NOT_FOUND;
+ for (int r = 0; r < rangeClauses.size(); r++) {
+ MultiRangeQuery.RangeClause range = rangeClauses.get(r);
+ long startingOrd;
+ seekStatus = termsEnum.seekCeil(new BytesRef(range.lowerValue));
+ if (matchingOrdsShifted == null) { // first iter
+ if (seekStatus == TermsEnum.SeekStatus.END) {
+ return empty(); // no bitset yet, give up
+ }
+ minOrd = termsEnum.ord();
+ if (skipper != null) {
+ minOrd = Math.max(minOrd, skipper.minValue());
+ maxOrd = Math.min(maxOrd, skipper.maxValue());
+ }
+ if (maxOrd < minOrd) {
+ return empty();
+ }
+ startingOrd = minOrd;
+ } else {
+ if (seekStatus == TermsEnum.SeekStatus.END) {
+ break; // ranges - we are done, terms are exhausted
+ } else {
+ startingOrd = termsEnum.ord();
+ }
+ }
+ byte[] upper = range.upperValue; // TODO ignore reverse ranges
+ // looking for overlap
+ for (int overlap = r + 1; overlap < rangeClauses.size(); overlap++, r++) {
+ MultiRangeQuery.RangeClause mayOverlap = rangeClauses.get(overlap);
+ assert comparator.compare(range.lowerValue, 0, mayOverlap.lowerValue, 0) <= 0
+ : "since they are sorted";
+ // TODO it might be contiguous ranges, it's worth to check but I have no idea how
+ if (comparator.compare(mayOverlap.lowerValue, 0, upper, 0) <= 0) {
+ // overlap, expand if needed
+ if (comparator.compare(upper, 0, mayOverlap.upperValue, 0) < 0) {
+ upper = mayOverlap.upperValue;
+ }
+ // continue; // skip overlapping rng
+ } else {
+ break; // no r++
+ }
+ }
+ seekStatus = termsEnum.seekCeil(new BytesRef(upper));
+
+ if (seekStatus == TermsEnum.SeekStatus.END) {
+ maxSeenOrd = maxOrd; // perhaps it's worth to set for skipper
+ matchesAbove = startingOrd;
+ break; // no need to create bitset
+ }
+ maxSeenOrd =
+ seekStatus == TermsEnum.SeekStatus.FOUND
+ ? termsEnum.ord()
+ : termsEnum.ord() - 1; // floor
+
+ if (matchingOrdsShifted == null) {
+ matchingOrdsShifted = new LongBitSet(maxOrd + 1 - minOrd);
+ }
+ matchingOrdsShifted.set(
+ startingOrd - minOrd, maxSeenOrd - minOrd + 1); // up is exclusive
+ }
+ /// ranges are over, there might be no set!!
+ TwoPhaseIterator iterator;
+ long finalMatchesAbove = matchesAbove;
+ LongBitSet finalMatchingOrdsShifted = matchingOrdsShifted;
+ long finalMinOrd = minOrd;
+ iterator =
+ new TwoPhaseIterator(values) {
+ // TODO unwrap singleton?
+ @Override
+ public boolean matches() throws IOException {
+ for (int i = 0; i < values.docValueCount(); i++) {
+ long ord = values.nextOrd();
+ if (ord >= finalMinOrd
+ && ((finalMatchesAbove < values.getValueCount()
+ && ord >= finalMatchesAbove)
+ || finalMatchingOrdsShifted.get(ord - finalMinOrd))) {
Review Comment:
> we can take advantage of them being sorted and the doc-level ordinals also being sorted.
Frankly speaking, I suppose singular values are more common than long sets of values, so, I don't think it get much gain for many users.
--
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] SortedSet DV Multi Range query [lucene]
Posted by "mkhludnev (via GitHub)" <gi...@apache.org>.
mkhludnev commented on code in PR #13974:
URL: https://github.com/apache/lucene/pull/13974#discussion_r1898420567
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/search/DocValuesMultiRangeQuery.java:
##########
@@ -0,0 +1,125 @@
+/*
+ * 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.sandbox.search;
+
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Objects;
+import java.util.function.BiConsumer;
+import java.util.function.Supplier;
+import org.apache.lucene.document.SortedSetDocValuesField;
+import org.apache.lucene.search.*;
+import org.apache.lucene.util.ArrayUtil;
+import org.apache.lucene.util.BytesRef;
+
+/** A few query builder for doc values multi range queries */
+public final class DocValuesMultiRangeQuery {
+
+ private DocValuesMultiRangeQuery() {}
+
+ /** Representation of a single clause in a MultiRangeQuery */
+ static final class Range {
+ BytesRef lower;
+ BytesRef upper;
+
+ /** NB: One absolutely must copy ByteRefs before. */
+ private Range(BytesRef lowerValue, BytesRef upperValue) {
+ this.lower = lowerValue;
+ this.upper = upperValue;
+ }
+
+ // TODO test equals
+ @Override
+ public boolean equals(Object o) {
+ if (this == o) {
+ return true;
+ }
+ if (o == null || getClass() != o.getClass()) {
+ return false;
+ }
+ Range that = (Range) o;
+ return lower.equals(that.lower) && upper.equals(that.upper);
+ }
+
+ @Override
+ public int hashCode() {
+ int result = lower.hashCode();
+ result = 31 * result + upper.hashCode();
+ return result;
+ }
+ }
+
+ /**
+ * Builder for creating a query for matching multi-range field values. Highlights two key points:
+ *
+ * <ul>
+ * <li>treats multiple or single field value as scalar for range matching
+ * <li>field values have fixed width
+ * </ul>
+ */
+ public static class SordedSetFieldValueFixedBuilder
Review Comment:
@gsmiller what do you think about such a verbose way of constructing query? Is it worth to piggyback on `java.function` nice interfaces?
--
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] SortedSet DV Multi Range query [lucene]
Posted by "mkhludnev (via GitHub)" <gi...@apache.org>.
mkhludnev commented on code in PR #13974:
URL: https://github.com/apache/lucene/pull/13974#discussion_r1900463220
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/search/SortedSetMultiRangeQuery.java:
##########
@@ -0,0 +1,300 @@
+/*
+ * 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.sandbox.search;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Objects;
+import org.apache.lucene.document.SortedSetDocValuesField;
+import org.apache.lucene.index.DocValues;
+import org.apache.lucene.index.DocValuesSkipper;
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.index.SortedSetDocValues;
+import org.apache.lucene.index.TermsEnum;
+import org.apache.lucene.search.BooleanQuery;
+import org.apache.lucene.search.ConstantScoreScorer;
+import org.apache.lucene.search.ConstantScoreWeight;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.search.DocValuesRangeIterator;
+import org.apache.lucene.search.IndexSearcher;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.search.QueryVisitor;
+import org.apache.lucene.search.ScoreMode;
+import org.apache.lucene.search.Scorer;
+import org.apache.lucene.search.ScorerSupplier;
+import org.apache.lucene.search.TwoPhaseIterator;
+import org.apache.lucene.search.Weight;
+import org.apache.lucene.util.ArrayUtil;
+import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.LongBitSet;
+
+/** A union multiple ranges over SortedSetDocValuesField */
+public class SortedSetMultiRangeQuery extends Query {
+ private final String field;
+ private final int bytesPerDim;
+ private final ArrayUtil.ByteArrayComparator comparator;
+ List<MultiRangeQuery.RangeClause> rangeClauses;
+
+ SortedSetMultiRangeQuery(
+ String name,
+ List<MultiRangeQuery.RangeClause> clauses,
+ int bytes,
+ ArrayUtil.ByteArrayComparator comparator) {
+ this.field = name;
+ this.rangeClauses = clauses;
+ this.bytesPerDim = bytes;
+ this.comparator = comparator;
+ }
+
+ /** Builder for creating a SortedSetMultiRangeQuery. */
+ public static class Builder {
+ private final String name;
+ protected final List<MultiRangeQuery.RangeClause> clauses = new ArrayList<>();
+ private final int bytes;
+ private final ArrayUtil.ByteArrayComparator comparator;
+
+ public Builder(String name, int bytes) {
+ this.name = Objects.requireNonNull(name);
+ this.bytes = bytes; // TODO assrt positive
+ this.comparator = ArrayUtil.getUnsignedComparator(bytes);
+ }
+
+ public Builder add(BytesRef lowerValue, BytesRef upperValue) {
+ byte[] low = lowerValue.clone().bytes;
+ byte[] up = upperValue.clone().bytes;
+ if (this.comparator.compare(low, 0, up, 0) > 0) {
+ throw new IllegalArgumentException("lowerValue must be <= upperValue");
+ } else {
+ clauses.add(new MultiRangeQuery.RangeClause(low, up));
+ }
+ return this;
+ }
+
+ public Query build() {
+ if (clauses.isEmpty()) {
+ return new BooleanQuery.Builder().build();
+ }
+ if (clauses.size() == 1) {
+ return SortedSetDocValuesField.newSlowRangeQuery(
+ name,
+ new BytesRef(clauses.getFirst().lowerValue),
+ new BytesRef(clauses.getFirst().upperValue),
+ true,
+ true);
+ }
+ return new SortedSetMultiRangeQuery(name, clauses, this.bytes, comparator);
+ }
+ }
+
+ @Override
+ public Query rewrite(IndexSearcher indexSearcher) throws IOException {
+ ArrayList<MultiRangeQuery.RangeClause> sortedClauses = new ArrayList<>(this.rangeClauses);
+ sortedClauses.sort(
+ (o1, o2) -> {
+ // if (result == 0) {
+ // return comparator.compare(o1.upperValue, 0, o2.upperValue, 0);
+ // } else {
+ return comparator.compare(o1.lowerValue, 0, o2.lowerValue, 0);
+ // }
+ });
+ if (!this.rangeClauses.equals(sortedClauses)) {
+ return new SortedSetMultiRangeQuery(
+ this.field, sortedClauses, this.bytesPerDim, this.comparator);
+ } else {
+ return this;
+ }
+ }
+
+ @Override
+ public String toString(String fld) {
+ return "SortedSetMultiRangeQuery{"
+ + "field='"
+ + fld
+ + '\''
+ + ", rangeClauses="
+ + rangeClauses
+ + // TODO better toString
+ '}';
+ }
+
+ // what TODO with reverse ranges ???
+ @Override
+ public Weight createWeight(IndexSearcher searcher, ScoreMode scoreMode, float boost)
+ throws IOException {
+ return new ConstantScoreWeight(this, boost) {
+ @Override
+ public ScorerSupplier scorerSupplier(LeafReaderContext context) throws IOException {
+ if (context.reader().getFieldInfos().fieldInfo(field) == null) {
+ return null;
+ }
+ DocValuesSkipper skipper = context.reader().getDocValuesSkipper(field);
+ SortedSetDocValues values = DocValues.getSortedSet(context.reader(), field);
+ // implement ScorerSupplier, since we do some expensive stuff to make a scorer
+ return new ScorerSupplier() {
+ @Override
+ public Scorer get(long leadCost) throws IOException {
+ if (rangeClauses.isEmpty()) {
+ return empty();
+ }
+ TermsEnum termsEnum = values.termsEnum();
+ LongBitSet matchingOrdsShifted = null;
+ long minOrd = 0, maxOrd = values.getValueCount() - 1;
+ long matchesAbove =
+ values.getValueCount(); // it's last range goes to maxOrd, by default - no match
+ long maxSeenOrd = values.getValueCount();
+ TermsEnum.SeekStatus seekStatus = TermsEnum.SeekStatus.NOT_FOUND;
+ for (int r = 0; r < rangeClauses.size(); r++) {
+ MultiRangeQuery.RangeClause range = rangeClauses.get(r);
+ long startingOrd;
+ seekStatus = termsEnum.seekCeil(new BytesRef(range.lowerValue));
+ if (matchingOrdsShifted == null) { // first iter
+ if (seekStatus == TermsEnum.SeekStatus.END) {
+ return empty(); // no bitset yet, give up
+ }
+ minOrd = termsEnum.ord();
+ if (skipper != null) {
+ minOrd = Math.max(minOrd, skipper.minValue());
+ maxOrd = Math.min(maxOrd, skipper.maxValue());
+ }
+ if (maxOrd < minOrd) {
+ return empty();
+ }
+ startingOrd = minOrd;
+ } else {
+ if (seekStatus == TermsEnum.SeekStatus.END) {
+ break; // ranges - we are done, terms are exhausted
+ } else {
+ startingOrd = termsEnum.ord();
+ }
+ }
+ byte[] upper = range.upperValue; // TODO ignore reverse ranges
+ // looking for overlap
+ for (int overlap = r + 1; overlap < rangeClauses.size(); overlap++, r++) {
+ MultiRangeQuery.RangeClause mayOverlap = rangeClauses.get(overlap);
+ assert comparator.compare(range.lowerValue, 0, mayOverlap.lowerValue, 0) <= 0
+ : "since they are sorted";
+ // TODO it might be contiguous ranges, it's worth to check but I have no idea how
+ if (comparator.compare(mayOverlap.lowerValue, 0, upper, 0) <= 0) {
+ // overlap, expand if needed
+ if (comparator.compare(upper, 0, mayOverlap.upperValue, 0) < 0) {
+ upper = mayOverlap.upperValue;
+ }
+ // continue; // skip overlapping rng
+ } else {
+ break; // no r++
+ }
+ }
+ seekStatus = termsEnum.seekCeil(new BytesRef(upper));
+
+ if (seekStatus == TermsEnum.SeekStatus.END) {
+ maxSeenOrd = maxOrd; // perhaps it's worth to set for skipper
+ matchesAbove = startingOrd;
+ break; // no need to create bitset
+ }
+ maxSeenOrd =
+ seekStatus == TermsEnum.SeekStatus.FOUND
+ ? termsEnum.ord()
+ : termsEnum.ord() - 1; // floor
+
+ if (matchingOrdsShifted == null) {
+ matchingOrdsShifted = new LongBitSet(maxOrd + 1 - minOrd);
+ }
+ matchingOrdsShifted.set(
+ startingOrd - minOrd, maxSeenOrd - minOrd + 1); // up is exclusive
+ }
+ /// ranges are over, there might be no set!!
+ TwoPhaseIterator iterator;
+ long finalMatchesAbove = matchesAbove;
+ LongBitSet finalMatchingOrdsShifted = matchingOrdsShifted;
+ long finalMinOrd = minOrd;
+ iterator =
+ new TwoPhaseIterator(values) {
+ // TODO unwrap singleton?
+ @Override
+ public boolean matches() throws IOException {
+ for (int i = 0; i < values.docValueCount(); i++) {
+ long ord = values.nextOrd();
+ if (ord >= finalMinOrd
+ && ((finalMatchesAbove < values.getValueCount()
+ && ord >= finalMatchesAbove)
+ || finalMatchingOrdsShifted.get(ord - finalMinOrd))) {
Review Comment:
> My only thought here is that we should be able to use less memory by keeping track of the range min/max values and not needing the dense representation
Introduced the second implementation treeset instead of bitset.
https://github.com/apache/lucene/blob/eea9e815c311b006d3297b8d9977fa6cb7c8e3f2/lucene/sandbox/src/java/org/apache/lucene/sandbox/search/DocValuesMultiRangeQuery.java#L198
It seems doubtful, however if we need to match NumericsDVs this is the only option.
How to scope this PR?
--
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] SortedSet DV Multi Range query [lucene]
Posted by "mkhludnev (via GitHub)" <gi...@apache.org>.
mkhludnev commented on PR #13974:
URL: https://github.com/apache/lucene/pull/13974#issuecomment-2669657925
It would be interesting to extend it to Numerics DVs and ranges aiming IP/masks
--
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] SortedSet DV Multi Range query [lucene]
Posted by "mkhludnev (via GitHub)" <gi...@apache.org>.
mkhludnev commented on PR #13974:
URL: https://github.com/apache/lucene/pull/13974#issuecomment-2692875765
>.. ranges aiming IP/masks
Turns out there are many varieties in range fields: single vs multiple values, number of dimensions and range search operations. Let's postpone it till the real life usecase.
--
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] SortedSet DV Multi Range query [lucene]
Posted by "mkhludnev (via GitHub)" <gi...@apache.org>.
mkhludnev commented on PR #13974:
URL: https://github.com/apache/lucene/pull/13974#issuecomment-2553941620
@gsmiller thanks for reviewing. Looking into!
--
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] SortedSet DV Multi Range query [lucene]
Posted by "mkhludnev (via GitHub)" <gi...@apache.org>.
mkhludnev commented on code in PR #13974:
URL: https://github.com/apache/lucene/pull/13974#discussion_r1896618101
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/search/SortedSetMultiRangeQuery.java:
##########
@@ -0,0 +1,300 @@
+/*
+ * 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.sandbox.search;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Objects;
+import org.apache.lucene.document.SortedSetDocValuesField;
+import org.apache.lucene.index.DocValues;
+import org.apache.lucene.index.DocValuesSkipper;
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.index.SortedSetDocValues;
+import org.apache.lucene.index.TermsEnum;
+import org.apache.lucene.search.BooleanQuery;
+import org.apache.lucene.search.ConstantScoreScorer;
+import org.apache.lucene.search.ConstantScoreWeight;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.search.DocValuesRangeIterator;
+import org.apache.lucene.search.IndexSearcher;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.search.QueryVisitor;
+import org.apache.lucene.search.ScoreMode;
+import org.apache.lucene.search.Scorer;
+import org.apache.lucene.search.ScorerSupplier;
+import org.apache.lucene.search.TwoPhaseIterator;
+import org.apache.lucene.search.Weight;
+import org.apache.lucene.util.ArrayUtil;
+import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.LongBitSet;
+
+/** A union multiple ranges over SortedSetDocValuesField */
+public class SortedSetMultiRangeQuery extends Query {
+ private final String field;
+ private final int bytesPerDim;
+ private final ArrayUtil.ByteArrayComparator comparator;
+ List<MultiRangeQuery.RangeClause> rangeClauses;
+
+ SortedSetMultiRangeQuery(
+ String name,
+ List<MultiRangeQuery.RangeClause> clauses,
+ int bytes,
+ ArrayUtil.ByteArrayComparator comparator) {
+ this.field = name;
+ this.rangeClauses = clauses;
+ this.bytesPerDim = bytes;
+ this.comparator = comparator;
+ }
+
+ /** Builder for creating a SortedSetMultiRangeQuery. */
+ public static class Builder {
+ private final String name;
+ protected final List<MultiRangeQuery.RangeClause> clauses = new ArrayList<>();
+ private final int bytes;
+ private final ArrayUtil.ByteArrayComparator comparator;
+
+ public Builder(String name, int bytes) {
+ this.name = Objects.requireNonNull(name);
+ this.bytes = bytes; // TODO assrt positive
+ this.comparator = ArrayUtil.getUnsignedComparator(bytes);
+ }
+
+ public Builder add(BytesRef lowerValue, BytesRef upperValue) {
+ byte[] low = lowerValue.clone().bytes;
+ byte[] up = upperValue.clone().bytes;
+ if (this.comparator.compare(low, 0, up, 0) > 0) {
+ throw new IllegalArgumentException("lowerValue must be <= upperValue");
+ } else {
+ clauses.add(new MultiRangeQuery.RangeClause(low, up));
+ }
+ return this;
+ }
+
+ public Query build() {
+ if (clauses.isEmpty()) {
+ return new BooleanQuery.Builder().build();
+ }
+ if (clauses.size() == 1) {
+ return SortedSetDocValuesField.newSlowRangeQuery(
+ name,
+ new BytesRef(clauses.getFirst().lowerValue),
+ new BytesRef(clauses.getFirst().upperValue),
+ true,
+ true);
+ }
+ return new SortedSetMultiRangeQuery(name, clauses, this.bytes, comparator);
+ }
+ }
+
+ @Override
+ public Query rewrite(IndexSearcher indexSearcher) throws IOException {
+ ArrayList<MultiRangeQuery.RangeClause> sortedClauses = new ArrayList<>(this.rangeClauses);
+ sortedClauses.sort(
+ (o1, o2) -> {
+ // if (result == 0) {
+ // return comparator.compare(o1.upperValue, 0, o2.upperValue, 0);
+ // } else {
+ return comparator.compare(o1.lowerValue, 0, o2.lowerValue, 0);
+ // }
+ });
+ if (!this.rangeClauses.equals(sortedClauses)) {
+ return new SortedSetMultiRangeQuery(
+ this.field, sortedClauses, this.bytesPerDim, this.comparator);
+ } else {
+ return this;
+ }
+ }
+
+ @Override
+ public String toString(String fld) {
+ return "SortedSetMultiRangeQuery{"
+ + "field='"
+ + fld
+ + '\''
+ + ", rangeClauses="
+ + rangeClauses
+ + // TODO better toString
+ '}';
+ }
+
+ // what TODO with reverse ranges ???
+ @Override
+ public Weight createWeight(IndexSearcher searcher, ScoreMode scoreMode, float boost)
+ throws IOException {
+ return new ConstantScoreWeight(this, boost) {
+ @Override
+ public ScorerSupplier scorerSupplier(LeafReaderContext context) throws IOException {
+ if (context.reader().getFieldInfos().fieldInfo(field) == null) {
+ return null;
+ }
+ DocValuesSkipper skipper = context.reader().getDocValuesSkipper(field);
Review Comment:
Turns out, DV access should happen right here since `ScorerSupplier#cost()` needs DV for estimate.
Actually I copied it from
https://github.com/apache/lucene/blob/0494c824e0ac8049b757582f60d085932a890800/lucene/core/src/java/org/apache/lucene/document/SortedSetDocValuesRangeQuery.java#L122
--
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] SortedSet DV Multi Range query [lucene]
Posted by "mkhludnev (via GitHub)" <gi...@apache.org>.
mkhludnev commented on code in PR #13974:
URL: https://github.com/apache/lucene/pull/13974#discussion_r1896745244
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/search/SortedSetMultiRangeQuery.java:
##########
@@ -0,0 +1,300 @@
+/*
+ * 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.sandbox.search;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Objects;
+import org.apache.lucene.document.SortedSetDocValuesField;
+import org.apache.lucene.index.DocValues;
+import org.apache.lucene.index.DocValuesSkipper;
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.index.SortedSetDocValues;
+import org.apache.lucene.index.TermsEnum;
+import org.apache.lucene.search.BooleanQuery;
+import org.apache.lucene.search.ConstantScoreScorer;
+import org.apache.lucene.search.ConstantScoreWeight;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.search.DocValuesRangeIterator;
+import org.apache.lucene.search.IndexSearcher;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.search.QueryVisitor;
+import org.apache.lucene.search.ScoreMode;
+import org.apache.lucene.search.Scorer;
+import org.apache.lucene.search.ScorerSupplier;
+import org.apache.lucene.search.TwoPhaseIterator;
+import org.apache.lucene.search.Weight;
+import org.apache.lucene.util.ArrayUtil;
+import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.LongBitSet;
+
+/** A union multiple ranges over SortedSetDocValuesField */
+public class SortedSetMultiRangeQuery extends Query {
Review Comment:
Since I want to limit the scope of this PR to:
- single dimension fields, lately it might be extended to ranges in fields.
- fixed length values.
I'm going to hide constuctor and introduce public factory method.
--
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] SortedSet DV Multi Range query [lucene]
Posted by "mkhludnev (via GitHub)" <gi...@apache.org>.
mkhludnev commented on code in PR #13974:
URL: https://github.com/apache/lucene/pull/13974#discussion_r1909946407
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/search/SortedSetMultiRangeQuery.java:
##########
@@ -0,0 +1,300 @@
+/*
+ * 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.sandbox.search;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Objects;
+import org.apache.lucene.document.SortedSetDocValuesField;
+import org.apache.lucene.index.DocValues;
+import org.apache.lucene.index.DocValuesSkipper;
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.index.SortedSetDocValues;
+import org.apache.lucene.index.TermsEnum;
+import org.apache.lucene.search.BooleanQuery;
+import org.apache.lucene.search.ConstantScoreScorer;
+import org.apache.lucene.search.ConstantScoreWeight;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.search.DocValuesRangeIterator;
+import org.apache.lucene.search.IndexSearcher;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.search.QueryVisitor;
+import org.apache.lucene.search.ScoreMode;
+import org.apache.lucene.search.Scorer;
+import org.apache.lucene.search.ScorerSupplier;
+import org.apache.lucene.search.TwoPhaseIterator;
+import org.apache.lucene.search.Weight;
+import org.apache.lucene.util.ArrayUtil;
+import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.LongBitSet;
+
+/** A union multiple ranges over SortedSetDocValuesField */
+public class SortedSetMultiRangeQuery extends Query {
+ private final String field;
+ private final int bytesPerDim;
+ private final ArrayUtil.ByteArrayComparator comparator;
+ List<MultiRangeQuery.RangeClause> rangeClauses;
+
+ SortedSetMultiRangeQuery(
+ String name,
+ List<MultiRangeQuery.RangeClause> clauses,
+ int bytes,
+ ArrayUtil.ByteArrayComparator comparator) {
+ this.field = name;
+ this.rangeClauses = clauses;
+ this.bytesPerDim = bytes;
+ this.comparator = comparator;
+ }
+
+ /** Builder for creating a SortedSetMultiRangeQuery. */
+ public static class Builder {
+ private final String name;
+ protected final List<MultiRangeQuery.RangeClause> clauses = new ArrayList<>();
+ private final int bytes;
+ private final ArrayUtil.ByteArrayComparator comparator;
+
+ public Builder(String name, int bytes) {
+ this.name = Objects.requireNonNull(name);
+ this.bytes = bytes; // TODO assrt positive
+ this.comparator = ArrayUtil.getUnsignedComparator(bytes);
+ }
+
+ public Builder add(BytesRef lowerValue, BytesRef upperValue) {
+ byte[] low = lowerValue.clone().bytes;
+ byte[] up = upperValue.clone().bytes;
+ if (this.comparator.compare(low, 0, up, 0) > 0) {
+ throw new IllegalArgumentException("lowerValue must be <= upperValue");
+ } else {
+ clauses.add(new MultiRangeQuery.RangeClause(low, up));
+ }
+ return this;
+ }
+
+ public Query build() {
+ if (clauses.isEmpty()) {
+ return new BooleanQuery.Builder().build();
+ }
+ if (clauses.size() == 1) {
+ return SortedSetDocValuesField.newSlowRangeQuery(
+ name,
+ new BytesRef(clauses.getFirst().lowerValue),
+ new BytesRef(clauses.getFirst().upperValue),
+ true,
+ true);
+ }
+ return new SortedSetMultiRangeQuery(name, clauses, this.bytes, comparator);
+ }
+ }
+
+ @Override
+ public Query rewrite(IndexSearcher indexSearcher) throws IOException {
+ ArrayList<MultiRangeQuery.RangeClause> sortedClauses = new ArrayList<>(this.rangeClauses);
+ sortedClauses.sort(
+ (o1, o2) -> {
+ // if (result == 0) {
+ // return comparator.compare(o1.upperValue, 0, o2.upperValue, 0);
+ // } else {
+ return comparator.compare(o1.lowerValue, 0, o2.lowerValue, 0);
+ // }
+ });
+ if (!this.rangeClauses.equals(sortedClauses)) {
+ return new SortedSetMultiRangeQuery(
+ this.field, sortedClauses, this.bytesPerDim, this.comparator);
+ } else {
+ return this;
+ }
+ }
+
+ @Override
+ public String toString(String fld) {
+ return "SortedSetMultiRangeQuery{"
+ + "field='"
+ + fld
+ + '\''
+ + ", rangeClauses="
+ + rangeClauses
+ + // TODO better toString
+ '}';
+ }
+
+ // what TODO with reverse ranges ???
+ @Override
+ public Weight createWeight(IndexSearcher searcher, ScoreMode scoreMode, float boost)
+ throws IOException {
+ return new ConstantScoreWeight(this, boost) {
+ @Override
+ public ScorerSupplier scorerSupplier(LeafReaderContext context) throws IOException {
+ if (context.reader().getFieldInfos().fieldInfo(field) == null) {
+ return null;
+ }
+ DocValuesSkipper skipper = context.reader().getDocValuesSkipper(field);
+ SortedSetDocValues values = DocValues.getSortedSet(context.reader(), field);
+ // implement ScorerSupplier, since we do some expensive stuff to make a scorer
+ return new ScorerSupplier() {
+ @Override
+ public Scorer get(long leadCost) throws IOException {
+ if (rangeClauses.isEmpty()) {
+ return empty();
+ }
+ TermsEnum termsEnum = values.termsEnum();
+ LongBitSet matchingOrdsShifted = null;
+ long minOrd = 0, maxOrd = values.getValueCount() - 1;
+ long matchesAbove =
+ values.getValueCount(); // it's last range goes to maxOrd, by default - no match
+ long maxSeenOrd = values.getValueCount();
+ TermsEnum.SeekStatus seekStatus = TermsEnum.SeekStatus.NOT_FOUND;
+ for (int r = 0; r < rangeClauses.size(); r++) {
+ MultiRangeQuery.RangeClause range = rangeClauses.get(r);
+ long startingOrd;
+ seekStatus = termsEnum.seekCeil(new BytesRef(range.lowerValue));
+ if (matchingOrdsShifted == null) { // first iter
+ if (seekStatus == TermsEnum.SeekStatus.END) {
+ return empty(); // no bitset yet, give up
+ }
+ minOrd = termsEnum.ord();
+ if (skipper != null) {
+ minOrd = Math.max(minOrd, skipper.minValue());
+ maxOrd = Math.min(maxOrd, skipper.maxValue());
+ }
+ if (maxOrd < minOrd) {
+ return empty();
+ }
+ startingOrd = minOrd;
+ } else {
+ if (seekStatus == TermsEnum.SeekStatus.END) {
+ break; // ranges - we are done, terms are exhausted
+ } else {
+ startingOrd = termsEnum.ord();
+ }
+ }
+ byte[] upper = range.upperValue; // TODO ignore reverse ranges
+ // looking for overlap
+ for (int overlap = r + 1; overlap < rangeClauses.size(); overlap++, r++) {
+ MultiRangeQuery.RangeClause mayOverlap = rangeClauses.get(overlap);
+ assert comparator.compare(range.lowerValue, 0, mayOverlap.lowerValue, 0) <= 0
+ : "since they are sorted";
+ // TODO it might be contiguous ranges, it's worth to check but I have no idea how
+ if (comparator.compare(mayOverlap.lowerValue, 0, upper, 0) <= 0) {
+ // overlap, expand if needed
+ if (comparator.compare(upper, 0, mayOverlap.upperValue, 0) < 0) {
+ upper = mayOverlap.upperValue;
+ }
+ // continue; // skip overlapping rng
+ } else {
+ break; // no r++
+ }
+ }
+ seekStatus = termsEnum.seekCeil(new BytesRef(upper));
+
+ if (seekStatus == TermsEnum.SeekStatus.END) {
+ maxSeenOrd = maxOrd; // perhaps it's worth to set for skipper
+ matchesAbove = startingOrd;
+ break; // no need to create bitset
+ }
+ maxSeenOrd =
+ seekStatus == TermsEnum.SeekStatus.FOUND
+ ? termsEnum.ord()
+ : termsEnum.ord() - 1; // floor
+
+ if (matchingOrdsShifted == null) {
+ matchingOrdsShifted = new LongBitSet(maxOrd + 1 - minOrd);
+ }
+ matchingOrdsShifted.set(
+ startingOrd - minOrd, maxSeenOrd - minOrd + 1); // up is exclusive
+ }
+ /// ranges are over, there might be no set!!
+ TwoPhaseIterator iterator;
+ long finalMatchesAbove = matchesAbove;
+ LongBitSet finalMatchingOrdsShifted = matchingOrdsShifted;
+ long finalMinOrd = minOrd;
+ iterator =
+ new TwoPhaseIterator(values) {
+ // TODO unwrap singleton?
+ @Override
+ public boolean matches() throws IOException {
+ for (int i = 0; i < values.docValueCount(); i++) {
+ long ord = values.nextOrd();
+ if (ord >= finalMinOrd
+ && ((finalMatchesAbove < values.getValueCount()
+ && ord >= finalMatchesAbove)
+ || finalMatchingOrdsShifted.get(ord - finalMinOrd))) {
Review Comment:
Thanks @gsmiller. Moved range tree to https://github.com/mkhludnev/lucene/tree/dvOnly-multirangeQ-rangetree keep here the bitset only.
The advantage of bitset impl is that it can handle a set of values and multi-range in the single query that should be common in SIEM (afaik) where we need a set of IPs and masks altogether.
--
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] SortedSet DV Multi Range query [lucene]
Posted by "mkhludnev (via GitHub)" <gi...@apache.org>.
mkhludnev commented on code in PR #13974:
URL: https://github.com/apache/lucene/pull/13974#discussion_r1929607965
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/search/SortedSetMultiRangeQuery.java:
##########
@@ -0,0 +1,300 @@
+/*
+ * 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.sandbox.search;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Objects;
+import org.apache.lucene.document.SortedSetDocValuesField;
+import org.apache.lucene.index.DocValues;
+import org.apache.lucene.index.DocValuesSkipper;
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.index.SortedSetDocValues;
+import org.apache.lucene.index.TermsEnum;
+import org.apache.lucene.search.BooleanQuery;
+import org.apache.lucene.search.ConstantScoreScorer;
+import org.apache.lucene.search.ConstantScoreWeight;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.search.DocValuesRangeIterator;
+import org.apache.lucene.search.IndexSearcher;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.search.QueryVisitor;
+import org.apache.lucene.search.ScoreMode;
+import org.apache.lucene.search.Scorer;
+import org.apache.lucene.search.ScorerSupplier;
+import org.apache.lucene.search.TwoPhaseIterator;
+import org.apache.lucene.search.Weight;
+import org.apache.lucene.util.ArrayUtil;
+import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.LongBitSet;
+
+/** A union multiple ranges over SortedSetDocValuesField */
+public class SortedSetMultiRangeQuery extends Query {
+ private final String field;
+ private final int bytesPerDim;
+ private final ArrayUtil.ByteArrayComparator comparator;
+ List<MultiRangeQuery.RangeClause> rangeClauses;
+
+ SortedSetMultiRangeQuery(
+ String name,
+ List<MultiRangeQuery.RangeClause> clauses,
+ int bytes,
+ ArrayUtil.ByteArrayComparator comparator) {
+ this.field = name;
+ this.rangeClauses = clauses;
+ this.bytesPerDim = bytes;
+ this.comparator = comparator;
+ }
+
+ /** Builder for creating a SortedSetMultiRangeQuery. */
+ public static class Builder {
+ private final String name;
+ protected final List<MultiRangeQuery.RangeClause> clauses = new ArrayList<>();
+ private final int bytes;
+ private final ArrayUtil.ByteArrayComparator comparator;
+
+ public Builder(String name, int bytes) {
+ this.name = Objects.requireNonNull(name);
+ this.bytes = bytes; // TODO assrt positive
+ this.comparator = ArrayUtil.getUnsignedComparator(bytes);
+ }
+
+ public Builder add(BytesRef lowerValue, BytesRef upperValue) {
+ byte[] low = lowerValue.clone().bytes;
+ byte[] up = upperValue.clone().bytes;
+ if (this.comparator.compare(low, 0, up, 0) > 0) {
+ throw new IllegalArgumentException("lowerValue must be <= upperValue");
+ } else {
+ clauses.add(new MultiRangeQuery.RangeClause(low, up));
+ }
+ return this;
+ }
+
+ public Query build() {
+ if (clauses.isEmpty()) {
+ return new BooleanQuery.Builder().build();
+ }
+ if (clauses.size() == 1) {
+ return SortedSetDocValuesField.newSlowRangeQuery(
+ name,
+ new BytesRef(clauses.getFirst().lowerValue),
+ new BytesRef(clauses.getFirst().upperValue),
+ true,
+ true);
+ }
+ return new SortedSetMultiRangeQuery(name, clauses, this.bytes, comparator);
+ }
+ }
+
+ @Override
+ public Query rewrite(IndexSearcher indexSearcher) throws IOException {
+ ArrayList<MultiRangeQuery.RangeClause> sortedClauses = new ArrayList<>(this.rangeClauses);
+ sortedClauses.sort(
+ (o1, o2) -> {
+ // if (result == 0) {
+ // return comparator.compare(o1.upperValue, 0, o2.upperValue, 0);
+ // } else {
+ return comparator.compare(o1.lowerValue, 0, o2.lowerValue, 0);
+ // }
+ });
+ if (!this.rangeClauses.equals(sortedClauses)) {
+ return new SortedSetMultiRangeQuery(
+ this.field, sortedClauses, this.bytesPerDim, this.comparator);
+ } else {
+ return this;
+ }
+ }
+
+ @Override
+ public String toString(String fld) {
+ return "SortedSetMultiRangeQuery{"
+ + "field='"
+ + fld
+ + '\''
+ + ", rangeClauses="
+ + rangeClauses
+ + // TODO better toString
+ '}';
+ }
+
+ // what TODO with reverse ranges ???
+ @Override
+ public Weight createWeight(IndexSearcher searcher, ScoreMode scoreMode, float boost)
+ throws IOException {
+ return new ConstantScoreWeight(this, boost) {
+ @Override
+ public ScorerSupplier scorerSupplier(LeafReaderContext context) throws IOException {
+ if (context.reader().getFieldInfos().fieldInfo(field) == null) {
+ return null;
+ }
+ DocValuesSkipper skipper = context.reader().getDocValuesSkipper(field);
+ SortedSetDocValues values = DocValues.getSortedSet(context.reader(), field);
+ // implement ScorerSupplier, since we do some expensive stuff to make a scorer
+ return new ScorerSupplier() {
+ @Override
+ public Scorer get(long leadCost) throws IOException {
+ if (rangeClauses.isEmpty()) {
+ return empty();
+ }
+ TermsEnum termsEnum = values.termsEnum();
+ LongBitSet matchingOrdsShifted = null;
+ long minOrd = 0, maxOrd = values.getValueCount() - 1;
+ long matchesAbove =
+ values.getValueCount(); // it's last range goes to maxOrd, by default - no match
+ long maxSeenOrd = values.getValueCount();
+ TermsEnum.SeekStatus seekStatus = TermsEnum.SeekStatus.NOT_FOUND;
+ for (int r = 0; r < rangeClauses.size(); r++) {
+ MultiRangeQuery.RangeClause range = rangeClauses.get(r);
+ long startingOrd;
+ seekStatus = termsEnum.seekCeil(new BytesRef(range.lowerValue));
+ if (matchingOrdsShifted == null) { // first iter
+ if (seekStatus == TermsEnum.SeekStatus.END) {
+ return empty(); // no bitset yet, give up
+ }
+ minOrd = termsEnum.ord();
+ if (skipper != null) {
+ minOrd = Math.max(minOrd, skipper.minValue());
+ maxOrd = Math.min(maxOrd, skipper.maxValue());
+ }
+ if (maxOrd < minOrd) {
+ return empty();
+ }
+ startingOrd = minOrd;
+ } else {
+ if (seekStatus == TermsEnum.SeekStatus.END) {
+ break; // ranges - we are done, terms are exhausted
+ } else {
+ startingOrd = termsEnum.ord();
+ }
+ }
+ byte[] upper = range.upperValue; // TODO ignore reverse ranges
+ // looking for overlap
+ for (int overlap = r + 1; overlap < rangeClauses.size(); overlap++, r++) {
+ MultiRangeQuery.RangeClause mayOverlap = rangeClauses.get(overlap);
+ assert comparator.compare(range.lowerValue, 0, mayOverlap.lowerValue, 0) <= 0
+ : "since they are sorted";
+ // TODO it might be contiguous ranges, it's worth to check but I have no idea how
+ if (comparator.compare(mayOverlap.lowerValue, 0, upper, 0) <= 0) {
+ // overlap, expand if needed
+ if (comparator.compare(upper, 0, mayOverlap.upperValue, 0) < 0) {
+ upper = mayOverlap.upperValue;
+ }
+ // continue; // skip overlapping rng
+ } else {
+ break; // no r++
+ }
+ }
+ seekStatus = termsEnum.seekCeil(new BytesRef(upper));
+
+ if (seekStatus == TermsEnum.SeekStatus.END) {
+ maxSeenOrd = maxOrd; // perhaps it's worth to set for skipper
+ matchesAbove = startingOrd;
+ break; // no need to create bitset
+ }
+ maxSeenOrd =
+ seekStatus == TermsEnum.SeekStatus.FOUND
+ ? termsEnum.ord()
+ : termsEnum.ord() - 1; // floor
+
+ if (matchingOrdsShifted == null) {
+ matchingOrdsShifted = new LongBitSet(maxOrd + 1 - minOrd);
+ }
+ matchingOrdsShifted.set(
+ startingOrd - minOrd, maxSeenOrd - minOrd + 1); // up is exclusive
+ }
+ /// ranges are over, there might be no set!!
+ TwoPhaseIterator iterator;
+ long finalMatchesAbove = matchesAbove;
+ LongBitSet finalMatchingOrdsShifted = matchingOrdsShifted;
+ long finalMinOrd = minOrd;
+ iterator =
+ new TwoPhaseIterator(values) {
+ // TODO unwrap singleton?
+ @Override
+ public boolean matches() throws IOException {
+ for (int i = 0; i < values.docValueCount(); i++) {
+ long ord = values.nextOrd();
+ if (ord >= finalMinOrd
+ && ((finalMatchesAbove < values.getValueCount()
+ && ord >= finalMatchesAbove)
+ || finalMatchingOrdsShifted.get(ord - finalMinOrd))) {
Review Comment:
ok. let's drop `resolveOverlaps`, `createOrdRanges`. Let's just loop ranges and call `seekCeil()` twice per range. Does it make sense to find min and max ords attempting to reduce bitset allocation upfront?
If it does should it turn byte array ranges into ord ranges and store it for the second pass filling bitset?
--
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] SortedSet DV Multi Range query [lucene]
Posted by "mkhludnev (via GitHub)" <gi...@apache.org>.
mkhludnev commented on PR #13974:
URL: https://github.com/apache/lucene/pull/13974#issuecomment-2661610834
> Would you mind adding a CHANGES entry?
done
--
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] SortedSet DV Multi Range query [lucene]
Posted by "mkhludnev (via GitHub)" <gi...@apache.org>.
mkhludnev commented on code in PR #13974:
URL: https://github.com/apache/lucene/pull/13974#discussion_r1938278091
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/search/SortedSetMultiRangeQuery.java:
##########
@@ -0,0 +1,300 @@
+/*
+ * 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.sandbox.search;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Objects;
+import org.apache.lucene.document.SortedSetDocValuesField;
+import org.apache.lucene.index.DocValues;
+import org.apache.lucene.index.DocValuesSkipper;
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.index.SortedSetDocValues;
+import org.apache.lucene.index.TermsEnum;
+import org.apache.lucene.search.BooleanQuery;
+import org.apache.lucene.search.ConstantScoreScorer;
+import org.apache.lucene.search.ConstantScoreWeight;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.search.DocValuesRangeIterator;
+import org.apache.lucene.search.IndexSearcher;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.search.QueryVisitor;
+import org.apache.lucene.search.ScoreMode;
+import org.apache.lucene.search.Scorer;
+import org.apache.lucene.search.ScorerSupplier;
+import org.apache.lucene.search.TwoPhaseIterator;
+import org.apache.lucene.search.Weight;
+import org.apache.lucene.util.ArrayUtil;
+import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.LongBitSet;
+
+/** A union multiple ranges over SortedSetDocValuesField */
+public class SortedSetMultiRangeQuery extends Query {
+ private final String field;
+ private final int bytesPerDim;
+ private final ArrayUtil.ByteArrayComparator comparator;
+ List<MultiRangeQuery.RangeClause> rangeClauses;
+
+ SortedSetMultiRangeQuery(
+ String name,
+ List<MultiRangeQuery.RangeClause> clauses,
+ int bytes,
+ ArrayUtil.ByteArrayComparator comparator) {
+ this.field = name;
+ this.rangeClauses = clauses;
+ this.bytesPerDim = bytes;
+ this.comparator = comparator;
+ }
+
+ /** Builder for creating a SortedSetMultiRangeQuery. */
+ public static class Builder {
+ private final String name;
+ protected final List<MultiRangeQuery.RangeClause> clauses = new ArrayList<>();
+ private final int bytes;
+ private final ArrayUtil.ByteArrayComparator comparator;
+
+ public Builder(String name, int bytes) {
+ this.name = Objects.requireNonNull(name);
+ this.bytes = bytes; // TODO assrt positive
+ this.comparator = ArrayUtil.getUnsignedComparator(bytes);
+ }
+
+ public Builder add(BytesRef lowerValue, BytesRef upperValue) {
+ byte[] low = lowerValue.clone().bytes;
+ byte[] up = upperValue.clone().bytes;
+ if (this.comparator.compare(low, 0, up, 0) > 0) {
+ throw new IllegalArgumentException("lowerValue must be <= upperValue");
+ } else {
+ clauses.add(new MultiRangeQuery.RangeClause(low, up));
+ }
+ return this;
+ }
+
+ public Query build() {
+ if (clauses.isEmpty()) {
+ return new BooleanQuery.Builder().build();
+ }
+ if (clauses.size() == 1) {
+ return SortedSetDocValuesField.newSlowRangeQuery(
+ name,
+ new BytesRef(clauses.getFirst().lowerValue),
+ new BytesRef(clauses.getFirst().upperValue),
+ true,
+ true);
+ }
+ return new SortedSetMultiRangeQuery(name, clauses, this.bytes, comparator);
+ }
+ }
+
+ @Override
+ public Query rewrite(IndexSearcher indexSearcher) throws IOException {
+ ArrayList<MultiRangeQuery.RangeClause> sortedClauses = new ArrayList<>(this.rangeClauses);
+ sortedClauses.sort(
+ (o1, o2) -> {
+ // if (result == 0) {
+ // return comparator.compare(o1.upperValue, 0, o2.upperValue, 0);
+ // } else {
+ return comparator.compare(o1.lowerValue, 0, o2.lowerValue, 0);
+ // }
+ });
+ if (!this.rangeClauses.equals(sortedClauses)) {
+ return new SortedSetMultiRangeQuery(
+ this.field, sortedClauses, this.bytesPerDim, this.comparator);
+ } else {
+ return this;
+ }
+ }
+
+ @Override
+ public String toString(String fld) {
+ return "SortedSetMultiRangeQuery{"
+ + "field='"
+ + fld
+ + '\''
+ + ", rangeClauses="
+ + rangeClauses
+ + // TODO better toString
+ '}';
+ }
+
+ // what TODO with reverse ranges ???
+ @Override
+ public Weight createWeight(IndexSearcher searcher, ScoreMode scoreMode, float boost)
+ throws IOException {
+ return new ConstantScoreWeight(this, boost) {
+ @Override
+ public ScorerSupplier scorerSupplier(LeafReaderContext context) throws IOException {
+ if (context.reader().getFieldInfos().fieldInfo(field) == null) {
+ return null;
+ }
+ DocValuesSkipper skipper = context.reader().getDocValuesSkipper(field);
+ SortedSetDocValues values = DocValues.getSortedSet(context.reader(), field);
+ // implement ScorerSupplier, since we do some expensive stuff to make a scorer
+ return new ScorerSupplier() {
+ @Override
+ public Scorer get(long leadCost) throws IOException {
+ if (rangeClauses.isEmpty()) {
+ return empty();
+ }
+ TermsEnum termsEnum = values.termsEnum();
+ LongBitSet matchingOrdsShifted = null;
+ long minOrd = 0, maxOrd = values.getValueCount() - 1;
+ long matchesAbove =
+ values.getValueCount(); // it's last range goes to maxOrd, by default - no match
+ long maxSeenOrd = values.getValueCount();
+ TermsEnum.SeekStatus seekStatus = TermsEnum.SeekStatus.NOT_FOUND;
+ for (int r = 0; r < rangeClauses.size(); r++) {
+ MultiRangeQuery.RangeClause range = rangeClauses.get(r);
+ long startingOrd;
+ seekStatus = termsEnum.seekCeil(new BytesRef(range.lowerValue));
+ if (matchingOrdsShifted == null) { // first iter
+ if (seekStatus == TermsEnum.SeekStatus.END) {
+ return empty(); // no bitset yet, give up
+ }
+ minOrd = termsEnum.ord();
+ if (skipper != null) {
+ minOrd = Math.max(minOrd, skipper.minValue());
+ maxOrd = Math.min(maxOrd, skipper.maxValue());
+ }
+ if (maxOrd < minOrd) {
+ return empty();
+ }
+ startingOrd = minOrd;
+ } else {
+ if (seekStatus == TermsEnum.SeekStatus.END) {
+ break; // ranges - we are done, terms are exhausted
+ } else {
+ startingOrd = termsEnum.ord();
+ }
+ }
+ byte[] upper = range.upperValue; // TODO ignore reverse ranges
+ // looking for overlap
+ for (int overlap = r + 1; overlap < rangeClauses.size(); overlap++, r++) {
+ MultiRangeQuery.RangeClause mayOverlap = rangeClauses.get(overlap);
+ assert comparator.compare(range.lowerValue, 0, mayOverlap.lowerValue, 0) <= 0
+ : "since they are sorted";
+ // TODO it might be contiguous ranges, it's worth to check but I have no idea how
+ if (comparator.compare(mayOverlap.lowerValue, 0, upper, 0) <= 0) {
+ // overlap, expand if needed
+ if (comparator.compare(upper, 0, mayOverlap.upperValue, 0) < 0) {
+ upper = mayOverlap.upperValue;
+ }
+ // continue; // skip overlapping rng
+ } else {
+ break; // no r++
+ }
+ }
+ seekStatus = termsEnum.seekCeil(new BytesRef(upper));
+
+ if (seekStatus == TermsEnum.SeekStatus.END) {
+ maxSeenOrd = maxOrd; // perhaps it's worth to set for skipper
+ matchesAbove = startingOrd;
+ break; // no need to create bitset
+ }
+ maxSeenOrd =
+ seekStatus == TermsEnum.SeekStatus.FOUND
+ ? termsEnum.ord()
+ : termsEnum.ord() - 1; // floor
+
+ if (matchingOrdsShifted == null) {
+ matchingOrdsShifted = new LongBitSet(maxOrd + 1 - minOrd);
+ }
+ matchingOrdsShifted.set(
+ startingOrd - minOrd, maxSeenOrd - minOrd + 1); // up is exclusive
+ }
+ /// ranges are over, there might be no set!!
+ TwoPhaseIterator iterator;
+ long finalMatchesAbove = matchesAbove;
+ LongBitSet finalMatchingOrdsShifted = matchingOrdsShifted;
+ long finalMinOrd = minOrd;
+ iterator =
+ new TwoPhaseIterator(values) {
+ // TODO unwrap singleton?
+ @Override
+ public boolean matches() throws IOException {
+ for (int i = 0; i < values.docValueCount(); i++) {
+ long ord = values.nextOrd();
+ if (ord >= finalMinOrd
+ && ((finalMatchesAbove < values.getValueCount()
+ && ord >= finalMatchesAbove)
+ || finalMatchingOrdsShifted.get(ord - finalMinOrd))) {
Review Comment:
> 2\. Drop `resolveOverlaps` but keep the logic in `createOrdRanges` as you currently have i
done. https://github.com/apache/lucene/pull/13974/commits/1751e70be15ab8bc54cfe5764c9bd9a5f14b2658
Thanks for looking into @gsmiller !
--
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] SortedSet DV Multi Range query [lucene]
Posted by "gsmiller (via GitHub)" <gi...@apache.org>.
gsmiller commented on code in PR #13974:
URL: https://github.com/apache/lucene/pull/13974#discussion_r1924528363
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/search/SortedSetMultiRangeQuery.java:
##########
@@ -0,0 +1,300 @@
+/*
+ * 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.sandbox.search;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Objects;
+import org.apache.lucene.document.SortedSetDocValuesField;
+import org.apache.lucene.index.DocValues;
+import org.apache.lucene.index.DocValuesSkipper;
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.index.SortedSetDocValues;
+import org.apache.lucene.index.TermsEnum;
+import org.apache.lucene.search.BooleanQuery;
+import org.apache.lucene.search.ConstantScoreScorer;
+import org.apache.lucene.search.ConstantScoreWeight;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.search.DocValuesRangeIterator;
+import org.apache.lucene.search.IndexSearcher;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.search.QueryVisitor;
+import org.apache.lucene.search.ScoreMode;
+import org.apache.lucene.search.Scorer;
+import org.apache.lucene.search.ScorerSupplier;
+import org.apache.lucene.search.TwoPhaseIterator;
+import org.apache.lucene.search.Weight;
+import org.apache.lucene.util.ArrayUtil;
+import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.LongBitSet;
+
+/** A union multiple ranges over SortedSetDocValuesField */
+public class SortedSetMultiRangeQuery extends Query {
+ private final String field;
+ private final int bytesPerDim;
+ private final ArrayUtil.ByteArrayComparator comparator;
+ List<MultiRangeQuery.RangeClause> rangeClauses;
+
+ SortedSetMultiRangeQuery(
+ String name,
+ List<MultiRangeQuery.RangeClause> clauses,
+ int bytes,
+ ArrayUtil.ByteArrayComparator comparator) {
+ this.field = name;
+ this.rangeClauses = clauses;
+ this.bytesPerDim = bytes;
+ this.comparator = comparator;
+ }
+
+ /** Builder for creating a SortedSetMultiRangeQuery. */
+ public static class Builder {
+ private final String name;
+ protected final List<MultiRangeQuery.RangeClause> clauses = new ArrayList<>();
+ private final int bytes;
+ private final ArrayUtil.ByteArrayComparator comparator;
+
+ public Builder(String name, int bytes) {
+ this.name = Objects.requireNonNull(name);
+ this.bytes = bytes; // TODO assrt positive
+ this.comparator = ArrayUtil.getUnsignedComparator(bytes);
+ }
+
+ public Builder add(BytesRef lowerValue, BytesRef upperValue) {
+ byte[] low = lowerValue.clone().bytes;
+ byte[] up = upperValue.clone().bytes;
+ if (this.comparator.compare(low, 0, up, 0) > 0) {
+ throw new IllegalArgumentException("lowerValue must be <= upperValue");
+ } else {
+ clauses.add(new MultiRangeQuery.RangeClause(low, up));
+ }
+ return this;
+ }
+
+ public Query build() {
+ if (clauses.isEmpty()) {
+ return new BooleanQuery.Builder().build();
+ }
+ if (clauses.size() == 1) {
+ return SortedSetDocValuesField.newSlowRangeQuery(
+ name,
+ new BytesRef(clauses.getFirst().lowerValue),
+ new BytesRef(clauses.getFirst().upperValue),
+ true,
+ true);
+ }
+ return new SortedSetMultiRangeQuery(name, clauses, this.bytes, comparator);
+ }
+ }
+
+ @Override
+ public Query rewrite(IndexSearcher indexSearcher) throws IOException {
+ ArrayList<MultiRangeQuery.RangeClause> sortedClauses = new ArrayList<>(this.rangeClauses);
+ sortedClauses.sort(
+ (o1, o2) -> {
+ // if (result == 0) {
+ // return comparator.compare(o1.upperValue, 0, o2.upperValue, 0);
+ // } else {
+ return comparator.compare(o1.lowerValue, 0, o2.lowerValue, 0);
+ // }
+ });
+ if (!this.rangeClauses.equals(sortedClauses)) {
+ return new SortedSetMultiRangeQuery(
+ this.field, sortedClauses, this.bytesPerDim, this.comparator);
+ } else {
+ return this;
+ }
+ }
+
+ @Override
+ public String toString(String fld) {
+ return "SortedSetMultiRangeQuery{"
+ + "field='"
+ + fld
+ + '\''
+ + ", rangeClauses="
+ + rangeClauses
+ + // TODO better toString
+ '}';
+ }
+
+ // what TODO with reverse ranges ???
+ @Override
+ public Weight createWeight(IndexSearcher searcher, ScoreMode scoreMode, float boost)
+ throws IOException {
+ return new ConstantScoreWeight(this, boost) {
+ @Override
+ public ScorerSupplier scorerSupplier(LeafReaderContext context) throws IOException {
+ if (context.reader().getFieldInfos().fieldInfo(field) == null) {
+ return null;
+ }
+ DocValuesSkipper skipper = context.reader().getDocValuesSkipper(field);
+ SortedSetDocValues values = DocValues.getSortedSet(context.reader(), field);
+ // implement ScorerSupplier, since we do some expensive stuff to make a scorer
+ return new ScorerSupplier() {
+ @Override
+ public Scorer get(long leadCost) throws IOException {
+ if (rangeClauses.isEmpty()) {
+ return empty();
+ }
+ TermsEnum termsEnum = values.termsEnum();
+ LongBitSet matchingOrdsShifted = null;
+ long minOrd = 0, maxOrd = values.getValueCount() - 1;
+ long matchesAbove =
+ values.getValueCount(); // it's last range goes to maxOrd, by default - no match
+ long maxSeenOrd = values.getValueCount();
+ TermsEnum.SeekStatus seekStatus = TermsEnum.SeekStatus.NOT_FOUND;
+ for (int r = 0; r < rangeClauses.size(); r++) {
+ MultiRangeQuery.RangeClause range = rangeClauses.get(r);
+ long startingOrd;
+ seekStatus = termsEnum.seekCeil(new BytesRef(range.lowerValue));
+ if (matchingOrdsShifted == null) { // first iter
+ if (seekStatus == TermsEnum.SeekStatus.END) {
+ return empty(); // no bitset yet, give up
+ }
+ minOrd = termsEnum.ord();
+ if (skipper != null) {
+ minOrd = Math.max(minOrd, skipper.minValue());
+ maxOrd = Math.min(maxOrd, skipper.maxValue());
+ }
+ if (maxOrd < minOrd) {
+ return empty();
+ }
+ startingOrd = minOrd;
+ } else {
+ if (seekStatus == TermsEnum.SeekStatus.END) {
+ break; // ranges - we are done, terms are exhausted
+ } else {
+ startingOrd = termsEnum.ord();
+ }
+ }
+ byte[] upper = range.upperValue; // TODO ignore reverse ranges
+ // looking for overlap
+ for (int overlap = r + 1; overlap < rangeClauses.size(); overlap++, r++) {
+ MultiRangeQuery.RangeClause mayOverlap = rangeClauses.get(overlap);
+ assert comparator.compare(range.lowerValue, 0, mayOverlap.lowerValue, 0) <= 0
+ : "since they are sorted";
+ // TODO it might be contiguous ranges, it's worth to check but I have no idea how
+ if (comparator.compare(mayOverlap.lowerValue, 0, upper, 0) <= 0) {
+ // overlap, expand if needed
+ if (comparator.compare(upper, 0, mayOverlap.upperValue, 0) < 0) {
+ upper = mayOverlap.upperValue;
+ }
+ // continue; // skip overlapping rng
+ } else {
+ break; // no r++
+ }
+ }
+ seekStatus = termsEnum.seekCeil(new BytesRef(upper));
+
+ if (seekStatus == TermsEnum.SeekStatus.END) {
+ maxSeenOrd = maxOrd; // perhaps it's worth to set for skipper
+ matchesAbove = startingOrd;
+ break; // no need to create bitset
+ }
+ maxSeenOrd =
+ seekStatus == TermsEnum.SeekStatus.FOUND
+ ? termsEnum.ord()
+ : termsEnum.ord() - 1; // floor
+
+ if (matchingOrdsShifted == null) {
+ matchingOrdsShifted = new LongBitSet(maxOrd + 1 - minOrd);
+ }
+ matchingOrdsShifted.set(
+ startingOrd - minOrd, maxSeenOrd - minOrd + 1); // up is exclusive
+ }
+ /// ranges are over, there might be no set!!
+ TwoPhaseIterator iterator;
+ long finalMatchesAbove = matchesAbove;
+ LongBitSet finalMatchingOrdsShifted = matchingOrdsShifted;
+ long finalMinOrd = minOrd;
+ iterator =
+ new TwoPhaseIterator(values) {
+ // TODO unwrap singleton?
+ @Override
+ public boolean matches() throws IOException {
+ for (int i = 0; i < values.docValueCount(); i++) {
+ long ord = values.nextOrd();
+ if (ord >= finalMinOrd
+ && ((finalMatchesAbove < values.getValueCount()
+ && ord >= finalMatchesAbove)
+ || finalMatchingOrdsShifted.get(ord - finalMinOrd))) {
Review Comment:
Hey @mkhludnev trying to catch back up on some of the progress here. Looking through `SortedSetDocValuesMultiRangeQuery` in its current implementation, it seems like there are a couple different places you deal with overlapping ranges. There's `resolveOverlaps` at initialization time, then there's also logic when creating the scorer that handles the fact that ranges can overlap (i.e., in `createOrdRanges`). I'm trying to wrap my head around the need for both. Is there a reason we need to handle overlaps during initialization? It seems like we only really care about overlapping ranges so we can avoid re-setting the same bits in the bitset over-and-over right? So this is really an optimization for scorer setup right? In case there was some huge number of ranges provided that all happen to have a bunch of common overlap? Do I have the right understanding here, or am I missing some other important bit of this (trying to make sure I'm not misunderstanding your intent here...). 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
Re: [PR] SortedSet DV Multi Range query [lucene]
Posted by "gsmiller (via GitHub)" <gi...@apache.org>.
gsmiller commented on code in PR #13974:
URL: https://github.com/apache/lucene/pull/13974#discussion_r1929422639
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/search/SortedSetMultiRangeQuery.java:
##########
@@ -0,0 +1,300 @@
+/*
+ * 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.sandbox.search;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Objects;
+import org.apache.lucene.document.SortedSetDocValuesField;
+import org.apache.lucene.index.DocValues;
+import org.apache.lucene.index.DocValuesSkipper;
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.index.SortedSetDocValues;
+import org.apache.lucene.index.TermsEnum;
+import org.apache.lucene.search.BooleanQuery;
+import org.apache.lucene.search.ConstantScoreScorer;
+import org.apache.lucene.search.ConstantScoreWeight;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.search.DocValuesRangeIterator;
+import org.apache.lucene.search.IndexSearcher;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.search.QueryVisitor;
+import org.apache.lucene.search.ScoreMode;
+import org.apache.lucene.search.Scorer;
+import org.apache.lucene.search.ScorerSupplier;
+import org.apache.lucene.search.TwoPhaseIterator;
+import org.apache.lucene.search.Weight;
+import org.apache.lucene.util.ArrayUtil;
+import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.LongBitSet;
+
+/** A union multiple ranges over SortedSetDocValuesField */
+public class SortedSetMultiRangeQuery extends Query {
+ private final String field;
+ private final int bytesPerDim;
+ private final ArrayUtil.ByteArrayComparator comparator;
+ List<MultiRangeQuery.RangeClause> rangeClauses;
+
+ SortedSetMultiRangeQuery(
+ String name,
+ List<MultiRangeQuery.RangeClause> clauses,
+ int bytes,
+ ArrayUtil.ByteArrayComparator comparator) {
+ this.field = name;
+ this.rangeClauses = clauses;
+ this.bytesPerDim = bytes;
+ this.comparator = comparator;
+ }
+
+ /** Builder for creating a SortedSetMultiRangeQuery. */
+ public static class Builder {
+ private final String name;
+ protected final List<MultiRangeQuery.RangeClause> clauses = new ArrayList<>();
+ private final int bytes;
+ private final ArrayUtil.ByteArrayComparator comparator;
+
+ public Builder(String name, int bytes) {
+ this.name = Objects.requireNonNull(name);
+ this.bytes = bytes; // TODO assrt positive
+ this.comparator = ArrayUtil.getUnsignedComparator(bytes);
+ }
+
+ public Builder add(BytesRef lowerValue, BytesRef upperValue) {
+ byte[] low = lowerValue.clone().bytes;
+ byte[] up = upperValue.clone().bytes;
+ if (this.comparator.compare(low, 0, up, 0) > 0) {
+ throw new IllegalArgumentException("lowerValue must be <= upperValue");
+ } else {
+ clauses.add(new MultiRangeQuery.RangeClause(low, up));
+ }
+ return this;
+ }
+
+ public Query build() {
+ if (clauses.isEmpty()) {
+ return new BooleanQuery.Builder().build();
+ }
+ if (clauses.size() == 1) {
+ return SortedSetDocValuesField.newSlowRangeQuery(
+ name,
+ new BytesRef(clauses.getFirst().lowerValue),
+ new BytesRef(clauses.getFirst().upperValue),
+ true,
+ true);
+ }
+ return new SortedSetMultiRangeQuery(name, clauses, this.bytes, comparator);
+ }
+ }
+
+ @Override
+ public Query rewrite(IndexSearcher indexSearcher) throws IOException {
+ ArrayList<MultiRangeQuery.RangeClause> sortedClauses = new ArrayList<>(this.rangeClauses);
+ sortedClauses.sort(
+ (o1, o2) -> {
+ // if (result == 0) {
+ // return comparator.compare(o1.upperValue, 0, o2.upperValue, 0);
+ // } else {
+ return comparator.compare(o1.lowerValue, 0, o2.lowerValue, 0);
+ // }
+ });
+ if (!this.rangeClauses.equals(sortedClauses)) {
+ return new SortedSetMultiRangeQuery(
+ this.field, sortedClauses, this.bytesPerDim, this.comparator);
+ } else {
+ return this;
+ }
+ }
+
+ @Override
+ public String toString(String fld) {
+ return "SortedSetMultiRangeQuery{"
+ + "field='"
+ + fld
+ + '\''
+ + ", rangeClauses="
+ + rangeClauses
+ + // TODO better toString
+ '}';
+ }
+
+ // what TODO with reverse ranges ???
+ @Override
+ public Weight createWeight(IndexSearcher searcher, ScoreMode scoreMode, float boost)
+ throws IOException {
+ return new ConstantScoreWeight(this, boost) {
+ @Override
+ public ScorerSupplier scorerSupplier(LeafReaderContext context) throws IOException {
+ if (context.reader().getFieldInfos().fieldInfo(field) == null) {
+ return null;
+ }
+ DocValuesSkipper skipper = context.reader().getDocValuesSkipper(field);
+ SortedSetDocValues values = DocValues.getSortedSet(context.reader(), field);
+ // implement ScorerSupplier, since we do some expensive stuff to make a scorer
+ return new ScorerSupplier() {
+ @Override
+ public Scorer get(long leadCost) throws IOException {
+ if (rangeClauses.isEmpty()) {
+ return empty();
+ }
+ TermsEnum termsEnum = values.termsEnum();
+ LongBitSet matchingOrdsShifted = null;
+ long minOrd = 0, maxOrd = values.getValueCount() - 1;
+ long matchesAbove =
+ values.getValueCount(); // it's last range goes to maxOrd, by default - no match
+ long maxSeenOrd = values.getValueCount();
+ TermsEnum.SeekStatus seekStatus = TermsEnum.SeekStatus.NOT_FOUND;
+ for (int r = 0; r < rangeClauses.size(); r++) {
+ MultiRangeQuery.RangeClause range = rangeClauses.get(r);
+ long startingOrd;
+ seekStatus = termsEnum.seekCeil(new BytesRef(range.lowerValue));
+ if (matchingOrdsShifted == null) { // first iter
+ if (seekStatus == TermsEnum.SeekStatus.END) {
+ return empty(); // no bitset yet, give up
+ }
+ minOrd = termsEnum.ord();
+ if (skipper != null) {
+ minOrd = Math.max(minOrd, skipper.minValue());
+ maxOrd = Math.min(maxOrd, skipper.maxValue());
+ }
+ if (maxOrd < minOrd) {
+ return empty();
+ }
+ startingOrd = minOrd;
+ } else {
+ if (seekStatus == TermsEnum.SeekStatus.END) {
+ break; // ranges - we are done, terms are exhausted
+ } else {
+ startingOrd = termsEnum.ord();
+ }
+ }
+ byte[] upper = range.upperValue; // TODO ignore reverse ranges
+ // looking for overlap
+ for (int overlap = r + 1; overlap < rangeClauses.size(); overlap++, r++) {
+ MultiRangeQuery.RangeClause mayOverlap = rangeClauses.get(overlap);
+ assert comparator.compare(range.lowerValue, 0, mayOverlap.lowerValue, 0) <= 0
+ : "since they are sorted";
+ // TODO it might be contiguous ranges, it's worth to check but I have no idea how
+ if (comparator.compare(mayOverlap.lowerValue, 0, upper, 0) <= 0) {
+ // overlap, expand if needed
+ if (comparator.compare(upper, 0, mayOverlap.upperValue, 0) < 0) {
+ upper = mayOverlap.upperValue;
+ }
+ // continue; // skip overlapping rng
+ } else {
+ break; // no r++
+ }
+ }
+ seekStatus = termsEnum.seekCeil(new BytesRef(upper));
+
+ if (seekStatus == TermsEnum.SeekStatus.END) {
+ maxSeenOrd = maxOrd; // perhaps it's worth to set for skipper
+ matchesAbove = startingOrd;
+ break; // no need to create bitset
+ }
+ maxSeenOrd =
+ seekStatus == TermsEnum.SeekStatus.FOUND
+ ? termsEnum.ord()
+ : termsEnum.ord() - 1; // floor
+
+ if (matchingOrdsShifted == null) {
+ matchingOrdsShifted = new LongBitSet(maxOrd + 1 - minOrd);
+ }
+ matchingOrdsShifted.set(
+ startingOrd - minOrd, maxSeenOrd - minOrd + 1); // up is exclusive
+ }
+ /// ranges are over, there might be no set!!
+ TwoPhaseIterator iterator;
+ long finalMatchesAbove = matchesAbove;
+ LongBitSet finalMatchingOrdsShifted = matchingOrdsShifted;
+ long finalMinOrd = minOrd;
+ iterator =
+ new TwoPhaseIterator(values) {
+ // TODO unwrap singleton?
+ @Override
+ public boolean matches() throws IOException {
+ for (int i = 0; i < values.docValueCount(); i++) {
+ long ord = values.nextOrd();
+ if (ord >= finalMinOrd
+ && ((finalMatchesAbove < values.getValueCount()
+ && ord >= finalMatchesAbove)
+ || finalMatchingOrdsShifted.get(ord - finalMinOrd))) {
Review Comment:
> I think just for some pathological queries. Imagine, many distinct ranges covered by the huge one, it may drop covered ranges from the future processing [...]
It makes sense to me that we may want to do some optimizations for pathological cases with many ranges that overlap. I do wonder a bit on the importance of this. My reasoning here is that the cost only hits when creating the bitset, which is an upfront cost and not a per-doc cost. I'm not opposed to pursuing this, but I'm trying to find a way to balance some of the added code complexity. In this case, it looks like you're relying on a couple helper classes (`OrdRange` and `Edge`) along with a reasonably complex algorithm for finding all the overlaps (which to be perfectly honest, I haven't dug into, only glanced at).
> [...] whether it be bitset or a tree set approach
I'm not sure I understand this point completely. I think what you're saying is that you might want to follow up this PR with another approach that uses a tree set approach instead of a bitset for matching (I believe you had an iteration of this PR that introduced the idea). I wonder if a common solution for merging overlapping ranges might become more important later if we really do have multiple implementations? Maybe this is a candidate for a spin-off issue that gets pursued as a later PR? (This goes back to my motivation of trying to reduce complexity of this initial change until it becomes more obvious we need the added complexity).
> [...] this step won't be available for NumericDVs and other w/o ords
Ah yes, that's fair. I think this is a continued discussion of the last point. Maybe we can pursue some merging when we do have multiple implementations that could obviously benefit from something like this? I can an optimization becoming more important in these other situations since it will become a per-doc cost as opposed to an up-front setup cost. Again though, I wonder if this could be tackled as a spin-off issue once we have more implementations?
> createOrdRanges [...] at here some ranges might become adjacent, not really overlapping, but eligible for merging into bigger ones. I checked the code and comments there, there's no occurrence of overlap only adjacent.
Are you suggesting that `createOrdRanges` as you currently have it implemented would not merge ranges that overlap? It looks to me like it would, but I might be missing something. If the ranges are sorted by their `min`, then I believe this method will merge away all the overlaps (as well as adjacent) wouldn't it? What do you think? Maybe I'm missing some cases or not properly wrapping my head around what you've got implemented here?
Apologies if it feels like I'm pushing back on this too much. I'm not against pursuing these optimizations by any means, I'm just seeing if there's a way to simplify this PR so we can get it merged and follow up with spin-off issues. Please let me know what you think (and thanks for your patience!).
--
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] SortedSet DV Multi Range query [lucene]
Posted by "gsmiller (via GitHub)" <gi...@apache.org>.
gsmiller commented on code in PR #13974:
URL: https://github.com/apache/lucene/pull/13974#discussion_r1931291804
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/search/SortedSetMultiRangeQuery.java:
##########
@@ -0,0 +1,300 @@
+/*
+ * 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.sandbox.search;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Objects;
+import org.apache.lucene.document.SortedSetDocValuesField;
+import org.apache.lucene.index.DocValues;
+import org.apache.lucene.index.DocValuesSkipper;
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.index.SortedSetDocValues;
+import org.apache.lucene.index.TermsEnum;
+import org.apache.lucene.search.BooleanQuery;
+import org.apache.lucene.search.ConstantScoreScorer;
+import org.apache.lucene.search.ConstantScoreWeight;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.search.DocValuesRangeIterator;
+import org.apache.lucene.search.IndexSearcher;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.search.QueryVisitor;
+import org.apache.lucene.search.ScoreMode;
+import org.apache.lucene.search.Scorer;
+import org.apache.lucene.search.ScorerSupplier;
+import org.apache.lucene.search.TwoPhaseIterator;
+import org.apache.lucene.search.Weight;
+import org.apache.lucene.util.ArrayUtil;
+import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.LongBitSet;
+
+/** A union multiple ranges over SortedSetDocValuesField */
+public class SortedSetMultiRangeQuery extends Query {
+ private final String field;
+ private final int bytesPerDim;
+ private final ArrayUtil.ByteArrayComparator comparator;
+ List<MultiRangeQuery.RangeClause> rangeClauses;
+
+ SortedSetMultiRangeQuery(
+ String name,
+ List<MultiRangeQuery.RangeClause> clauses,
+ int bytes,
+ ArrayUtil.ByteArrayComparator comparator) {
+ this.field = name;
+ this.rangeClauses = clauses;
+ this.bytesPerDim = bytes;
+ this.comparator = comparator;
+ }
+
+ /** Builder for creating a SortedSetMultiRangeQuery. */
+ public static class Builder {
+ private final String name;
+ protected final List<MultiRangeQuery.RangeClause> clauses = new ArrayList<>();
+ private final int bytes;
+ private final ArrayUtil.ByteArrayComparator comparator;
+
+ public Builder(String name, int bytes) {
+ this.name = Objects.requireNonNull(name);
+ this.bytes = bytes; // TODO assrt positive
+ this.comparator = ArrayUtil.getUnsignedComparator(bytes);
+ }
+
+ public Builder add(BytesRef lowerValue, BytesRef upperValue) {
+ byte[] low = lowerValue.clone().bytes;
+ byte[] up = upperValue.clone().bytes;
+ if (this.comparator.compare(low, 0, up, 0) > 0) {
+ throw new IllegalArgumentException("lowerValue must be <= upperValue");
+ } else {
+ clauses.add(new MultiRangeQuery.RangeClause(low, up));
+ }
+ return this;
+ }
+
+ public Query build() {
+ if (clauses.isEmpty()) {
+ return new BooleanQuery.Builder().build();
+ }
+ if (clauses.size() == 1) {
+ return SortedSetDocValuesField.newSlowRangeQuery(
+ name,
+ new BytesRef(clauses.getFirst().lowerValue),
+ new BytesRef(clauses.getFirst().upperValue),
+ true,
+ true);
+ }
+ return new SortedSetMultiRangeQuery(name, clauses, this.bytes, comparator);
+ }
+ }
+
+ @Override
+ public Query rewrite(IndexSearcher indexSearcher) throws IOException {
+ ArrayList<MultiRangeQuery.RangeClause> sortedClauses = new ArrayList<>(this.rangeClauses);
+ sortedClauses.sort(
+ (o1, o2) -> {
+ // if (result == 0) {
+ // return comparator.compare(o1.upperValue, 0, o2.upperValue, 0);
+ // } else {
+ return comparator.compare(o1.lowerValue, 0, o2.lowerValue, 0);
+ // }
+ });
+ if (!this.rangeClauses.equals(sortedClauses)) {
+ return new SortedSetMultiRangeQuery(
+ this.field, sortedClauses, this.bytesPerDim, this.comparator);
+ } else {
+ return this;
+ }
+ }
+
+ @Override
+ public String toString(String fld) {
+ return "SortedSetMultiRangeQuery{"
+ + "field='"
+ + fld
+ + '\''
+ + ", rangeClauses="
+ + rangeClauses
+ + // TODO better toString
+ '}';
+ }
+
+ // what TODO with reverse ranges ???
+ @Override
+ public Weight createWeight(IndexSearcher searcher, ScoreMode scoreMode, float boost)
+ throws IOException {
+ return new ConstantScoreWeight(this, boost) {
+ @Override
+ public ScorerSupplier scorerSupplier(LeafReaderContext context) throws IOException {
+ if (context.reader().getFieldInfos().fieldInfo(field) == null) {
+ return null;
+ }
+ DocValuesSkipper skipper = context.reader().getDocValuesSkipper(field);
+ SortedSetDocValues values = DocValues.getSortedSet(context.reader(), field);
+ // implement ScorerSupplier, since we do some expensive stuff to make a scorer
+ return new ScorerSupplier() {
+ @Override
+ public Scorer get(long leadCost) throws IOException {
+ if (rangeClauses.isEmpty()) {
+ return empty();
+ }
+ TermsEnum termsEnum = values.termsEnum();
+ LongBitSet matchingOrdsShifted = null;
+ long minOrd = 0, maxOrd = values.getValueCount() - 1;
+ long matchesAbove =
+ values.getValueCount(); // it's last range goes to maxOrd, by default - no match
+ long maxSeenOrd = values.getValueCount();
+ TermsEnum.SeekStatus seekStatus = TermsEnum.SeekStatus.NOT_FOUND;
+ for (int r = 0; r < rangeClauses.size(); r++) {
+ MultiRangeQuery.RangeClause range = rangeClauses.get(r);
+ long startingOrd;
+ seekStatus = termsEnum.seekCeil(new BytesRef(range.lowerValue));
+ if (matchingOrdsShifted == null) { // first iter
+ if (seekStatus == TermsEnum.SeekStatus.END) {
+ return empty(); // no bitset yet, give up
+ }
+ minOrd = termsEnum.ord();
+ if (skipper != null) {
+ minOrd = Math.max(minOrd, skipper.minValue());
+ maxOrd = Math.min(maxOrd, skipper.maxValue());
+ }
+ if (maxOrd < minOrd) {
+ return empty();
+ }
+ startingOrd = minOrd;
+ } else {
+ if (seekStatus == TermsEnum.SeekStatus.END) {
+ break; // ranges - we are done, terms are exhausted
+ } else {
+ startingOrd = termsEnum.ord();
+ }
+ }
+ byte[] upper = range.upperValue; // TODO ignore reverse ranges
+ // looking for overlap
+ for (int overlap = r + 1; overlap < rangeClauses.size(); overlap++, r++) {
+ MultiRangeQuery.RangeClause mayOverlap = rangeClauses.get(overlap);
+ assert comparator.compare(range.lowerValue, 0, mayOverlap.lowerValue, 0) <= 0
+ : "since they are sorted";
+ // TODO it might be contiguous ranges, it's worth to check but I have no idea how
+ if (comparator.compare(mayOverlap.lowerValue, 0, upper, 0) <= 0) {
+ // overlap, expand if needed
+ if (comparator.compare(upper, 0, mayOverlap.upperValue, 0) < 0) {
+ upper = mayOverlap.upperValue;
+ }
+ // continue; // skip overlapping rng
+ } else {
+ break; // no r++
+ }
+ }
+ seekStatus = termsEnum.seekCeil(new BytesRef(upper));
+
+ if (seekStatus == TermsEnum.SeekStatus.END) {
+ maxSeenOrd = maxOrd; // perhaps it's worth to set for skipper
+ matchesAbove = startingOrd;
+ break; // no need to create bitset
+ }
+ maxSeenOrd =
+ seekStatus == TermsEnum.SeekStatus.FOUND
+ ? termsEnum.ord()
+ : termsEnum.ord() - 1; // floor
+
+ if (matchingOrdsShifted == null) {
+ matchingOrdsShifted = new LongBitSet(maxOrd + 1 - minOrd);
+ }
+ matchingOrdsShifted.set(
+ startingOrd - minOrd, maxSeenOrd - minOrd + 1); // up is exclusive
+ }
+ /// ranges are over, there might be no set!!
+ TwoPhaseIterator iterator;
+ long finalMatchesAbove = matchesAbove;
+ LongBitSet finalMatchingOrdsShifted = matchingOrdsShifted;
+ long finalMinOrd = minOrd;
+ iterator =
+ new TwoPhaseIterator(values) {
+ // TODO unwrap singleton?
+ @Override
+ public boolean matches() throws IOException {
+ for (int i = 0; i < values.docValueCount(); i++) {
+ long ord = values.nextOrd();
+ if (ord >= finalMinOrd
+ && ((finalMatchesAbove < values.getValueCount()
+ && ord >= finalMatchesAbove)
+ || finalMatchingOrdsShifted.get(ord - finalMinOrd))) {
Review Comment:
Thanks for your thoughts @mkhludnev. I'd suggest one-of-two options. I'd be happy to move forward with either:
1. Keep it as simple as possible and drop all range merging, as you outline above (e.g., drop `resolveOverlaps` and `createOrdRanges`). Then consider adding these ideas back in as spin-off SIMs after the initial implementation is merged.
2. Drop `resolveOverlaps` but keep the logic in `createOrdRanges` as you currently have it. I like how you have this implemented currently. Seems like a pretty clean way of reducing unnecessary calls to `seekCeil` and bitset sets by recognizing adjacent or overlapping ranges without adding much code complexity.
Apologies on my above communication. It may not have been as specific as it could have been. The complexity that I'd like to avoid (at least in the initial version of this) is `resolveOverlaps`. I don't mind `createOrdRanges` since it is immediately applicable in this implementation and isn't particularly complex to reason about. The `resolveOverlaps` method seems more future-looking to other implementations, etc., so the value vs. complexity trade-off isn't as clear to me right now.
What do you think? (I'm happy to go with whatever you think will help get this merged and reduce headaches for you since we're discussed plenty at this point and I don't want to slow you down further )
--
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] SortedSet DV Multi Range query [lucene]
Posted by "mkhludnev (via GitHub)" <gi...@apache.org>.
mkhludnev commented on code in PR #13974:
URL: https://github.com/apache/lucene/pull/13974#discussion_r1891293118
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/search/SortedSetMultiRangeQuery.java:
##########
@@ -0,0 +1,300 @@
+/*
+ * 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.sandbox.search;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Objects;
+import org.apache.lucene.document.SortedSetDocValuesField;
+import org.apache.lucene.index.DocValues;
+import org.apache.lucene.index.DocValuesSkipper;
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.index.SortedSetDocValues;
+import org.apache.lucene.index.TermsEnum;
+import org.apache.lucene.search.BooleanQuery;
+import org.apache.lucene.search.ConstantScoreScorer;
+import org.apache.lucene.search.ConstantScoreWeight;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.search.DocValuesRangeIterator;
+import org.apache.lucene.search.IndexSearcher;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.search.QueryVisitor;
+import org.apache.lucene.search.ScoreMode;
+import org.apache.lucene.search.Scorer;
+import org.apache.lucene.search.ScorerSupplier;
+import org.apache.lucene.search.TwoPhaseIterator;
+import org.apache.lucene.search.Weight;
+import org.apache.lucene.util.ArrayUtil;
+import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.LongBitSet;
+
+/** A union multiple ranges over SortedSetDocValuesField */
+public class SortedSetMultiRangeQuery extends Query {
Review Comment:
Aghh right. Let me gather my considerations:
- do you mean to rename it to `SortedSetDocValuesMultiRangeQuery` or somehow abbreviate it? -I'm totally for it- wait a sec: `SortedSet` means docValues anyway.
- `SortedSetDocValuesRangeQuery` which is a singular analog of `SortedSetMultiRangeQuery`, has no `bytePerDim` constraint. However, I purpose `SortedSetMultiRangeQuery` for fixed width usages like IP, lately for IP ranges. I'm not sure it's possible at all, but do you think it's worth to drop `bytePerDim` constrain to move it forward?
- `sandbox` package is an only option for now, I suppose
- is it worth to copy `MultiRangeQuery.RangeClause` here? I used it only because it's public. Whether we do it now or later, it doesn't leak from public interface. WDYT?
--
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] SortedSet DV Multi Range query [lucene]
Posted by "mkhludnev (via GitHub)" <gi...@apache.org>.
mkhludnev commented on code in PR #13974:
URL: https://github.com/apache/lucene/pull/13974#discussion_r1891524385
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/search/SortedSetMultiRangeQuery.java:
##########
@@ -0,0 +1,300 @@
+/*
+ * 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.sandbox.search;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Objects;
+import org.apache.lucene.document.SortedSetDocValuesField;
+import org.apache.lucene.index.DocValues;
+import org.apache.lucene.index.DocValuesSkipper;
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.index.SortedSetDocValues;
+import org.apache.lucene.index.TermsEnum;
+import org.apache.lucene.search.BooleanQuery;
+import org.apache.lucene.search.ConstantScoreScorer;
+import org.apache.lucene.search.ConstantScoreWeight;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.search.DocValuesRangeIterator;
+import org.apache.lucene.search.IndexSearcher;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.search.QueryVisitor;
+import org.apache.lucene.search.ScoreMode;
+import org.apache.lucene.search.Scorer;
+import org.apache.lucene.search.ScorerSupplier;
+import org.apache.lucene.search.TwoPhaseIterator;
+import org.apache.lucene.search.Weight;
+import org.apache.lucene.util.ArrayUtil;
+import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.LongBitSet;
+
+/** A union multiple ranges over SortedSetDocValuesField */
+public class SortedSetMultiRangeQuery extends Query {
+ private final String field;
+ private final int bytesPerDim;
+ private final ArrayUtil.ByteArrayComparator comparator;
+ List<MultiRangeQuery.RangeClause> rangeClauses;
+
+ SortedSetMultiRangeQuery(
+ String name,
+ List<MultiRangeQuery.RangeClause> clauses,
+ int bytes,
+ ArrayUtil.ByteArrayComparator comparator) {
+ this.field = name;
+ this.rangeClauses = clauses;
+ this.bytesPerDim = bytes;
+ this.comparator = comparator;
+ }
+
+ /** Builder for creating a SortedSetMultiRangeQuery. */
+ public static class Builder {
+ private final String name;
+ protected final List<MultiRangeQuery.RangeClause> clauses = new ArrayList<>();
+ private final int bytes;
+ private final ArrayUtil.ByteArrayComparator comparator;
+
+ public Builder(String name, int bytes) {
+ this.name = Objects.requireNonNull(name);
+ this.bytes = bytes; // TODO assrt positive
+ this.comparator = ArrayUtil.getUnsignedComparator(bytes);
+ }
+
+ public Builder add(BytesRef lowerValue, BytesRef upperValue) {
+ byte[] low = lowerValue.clone().bytes;
+ byte[] up = upperValue.clone().bytes;
+ if (this.comparator.compare(low, 0, up, 0) > 0) {
+ throw new IllegalArgumentException("lowerValue must be <= upperValue");
+ } else {
+ clauses.add(new MultiRangeQuery.RangeClause(low, up));
+ }
+ return this;
+ }
+
+ public Query build() {
+ if (clauses.isEmpty()) {
+ return new BooleanQuery.Builder().build();
+ }
+ if (clauses.size() == 1) {
+ return SortedSetDocValuesField.newSlowRangeQuery(
+ name,
+ new BytesRef(clauses.getFirst().lowerValue),
+ new BytesRef(clauses.getFirst().upperValue),
+ true,
+ true);
+ }
+ return new SortedSetMultiRangeQuery(name, clauses, this.bytes, comparator);
+ }
+ }
+
+ @Override
+ public Query rewrite(IndexSearcher indexSearcher) throws IOException {
+ ArrayList<MultiRangeQuery.RangeClause> sortedClauses = new ArrayList<>(this.rangeClauses);
+ sortedClauses.sort(
+ (o1, o2) -> {
+ // if (result == 0) {
+ // return comparator.compare(o1.upperValue, 0, o2.upperValue, 0);
+ // } else {
+ return comparator.compare(o1.lowerValue, 0, o2.lowerValue, 0);
+ // }
+ });
+ if (!this.rangeClauses.equals(sortedClauses)) {
+ return new SortedSetMultiRangeQuery(
+ this.field, sortedClauses, this.bytesPerDim, this.comparator);
+ } else {
+ return this;
+ }
+ }
+
+ @Override
+ public String toString(String fld) {
+ return "SortedSetMultiRangeQuery{"
+ + "field='"
+ + fld
+ + '\''
+ + ", rangeClauses="
+ + rangeClauses
+ + // TODO better toString
+ '}';
+ }
+
+ // what TODO with reverse ranges ???
+ @Override
+ public Weight createWeight(IndexSearcher searcher, ScoreMode scoreMode, float boost)
+ throws IOException {
+ return new ConstantScoreWeight(this, boost) {
+ @Override
+ public ScorerSupplier scorerSupplier(LeafReaderContext context) throws IOException {
+ if (context.reader().getFieldInfos().fieldInfo(field) == null) {
+ return null;
+ }
+ DocValuesSkipper skipper = context.reader().getDocValuesSkipper(field);
+ SortedSetDocValues values = DocValues.getSortedSet(context.reader(), field);
+ // implement ScorerSupplier, since we do some expensive stuff to make a scorer
+ return new ScorerSupplier() {
+ @Override
+ public Scorer get(long leadCost) throws IOException {
+ if (rangeClauses.isEmpty()) {
+ return empty();
+ }
+ TermsEnum termsEnum = values.termsEnum();
+ LongBitSet matchingOrdsShifted = null;
+ long minOrd = 0, maxOrd = values.getValueCount() - 1;
+ long matchesAbove =
+ values.getValueCount(); // it's last range goes to maxOrd, by default - no match
+ long maxSeenOrd = values.getValueCount();
+ TermsEnum.SeekStatus seekStatus = TermsEnum.SeekStatus.NOT_FOUND;
+ for (int r = 0; r < rangeClauses.size(); r++) {
+ MultiRangeQuery.RangeClause range = rangeClauses.get(r);
+ long startingOrd;
+ seekStatus = termsEnum.seekCeil(new BytesRef(range.lowerValue));
Review Comment:
OK. this would be a reason to copy Range 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] SortedSet DV Multi Range query [lucene]
Posted by "mkhludnev (via GitHub)" <gi...@apache.org>.
mkhludnev commented on code in PR #13974:
URL: https://github.com/apache/lucene/pull/13974#discussion_r1891551211
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/search/SortedSetMultiRangeQuery.java:
##########
@@ -0,0 +1,300 @@
+/*
+ * 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.sandbox.search;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Objects;
+import org.apache.lucene.document.SortedSetDocValuesField;
+import org.apache.lucene.index.DocValues;
+import org.apache.lucene.index.DocValuesSkipper;
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.index.SortedSetDocValues;
+import org.apache.lucene.index.TermsEnum;
+import org.apache.lucene.search.BooleanQuery;
+import org.apache.lucene.search.ConstantScoreScorer;
+import org.apache.lucene.search.ConstantScoreWeight;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.search.DocValuesRangeIterator;
+import org.apache.lucene.search.IndexSearcher;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.search.QueryVisitor;
+import org.apache.lucene.search.ScoreMode;
+import org.apache.lucene.search.Scorer;
+import org.apache.lucene.search.ScorerSupplier;
+import org.apache.lucene.search.TwoPhaseIterator;
+import org.apache.lucene.search.Weight;
+import org.apache.lucene.util.ArrayUtil;
+import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.LongBitSet;
+
+/** A union multiple ranges over SortedSetDocValuesField */
+public class SortedSetMultiRangeQuery extends Query {
+ private final String field;
+ private final int bytesPerDim;
+ private final ArrayUtil.ByteArrayComparator comparator;
+ List<MultiRangeQuery.RangeClause> rangeClauses;
+
+ SortedSetMultiRangeQuery(
+ String name,
+ List<MultiRangeQuery.RangeClause> clauses,
+ int bytes,
+ ArrayUtil.ByteArrayComparator comparator) {
+ this.field = name;
+ this.rangeClauses = clauses;
+ this.bytesPerDim = bytes;
+ this.comparator = comparator;
+ }
+
+ /** Builder for creating a SortedSetMultiRangeQuery. */
+ public static class Builder {
+ private final String name;
+ protected final List<MultiRangeQuery.RangeClause> clauses = new ArrayList<>();
+ private final int bytes;
+ private final ArrayUtil.ByteArrayComparator comparator;
+
+ public Builder(String name, int bytes) {
+ this.name = Objects.requireNonNull(name);
+ this.bytes = bytes; // TODO assrt positive
+ this.comparator = ArrayUtil.getUnsignedComparator(bytes);
+ }
+
+ public Builder add(BytesRef lowerValue, BytesRef upperValue) {
+ byte[] low = lowerValue.clone().bytes;
+ byte[] up = upperValue.clone().bytes;
+ if (this.comparator.compare(low, 0, up, 0) > 0) {
+ throw new IllegalArgumentException("lowerValue must be <= upperValue");
+ } else {
+ clauses.add(new MultiRangeQuery.RangeClause(low, up));
+ }
+ return this;
+ }
+
+ public Query build() {
+ if (clauses.isEmpty()) {
+ return new BooleanQuery.Builder().build();
+ }
+ if (clauses.size() == 1) {
+ return SortedSetDocValuesField.newSlowRangeQuery(
+ name,
+ new BytesRef(clauses.getFirst().lowerValue),
+ new BytesRef(clauses.getFirst().upperValue),
+ true,
+ true);
+ }
+ return new SortedSetMultiRangeQuery(name, clauses, this.bytes, comparator);
+ }
+ }
+
+ @Override
+ public Query rewrite(IndexSearcher indexSearcher) throws IOException {
+ ArrayList<MultiRangeQuery.RangeClause> sortedClauses = new ArrayList<>(this.rangeClauses);
+ sortedClauses.sort(
+ (o1, o2) -> {
+ // if (result == 0) {
+ // return comparator.compare(o1.upperValue, 0, o2.upperValue, 0);
+ // } else {
+ return comparator.compare(o1.lowerValue, 0, o2.lowerValue, 0);
+ // }
+ });
+ if (!this.rangeClauses.equals(sortedClauses)) {
+ return new SortedSetMultiRangeQuery(
+ this.field, sortedClauses, this.bytesPerDim, this.comparator);
+ } else {
+ return this;
+ }
+ }
+
+ @Override
+ public String toString(String fld) {
+ return "SortedSetMultiRangeQuery{"
+ + "field='"
+ + fld
+ + '\''
+ + ", rangeClauses="
+ + rangeClauses
+ + // TODO better toString
+ '}';
+ }
+
+ // what TODO with reverse ranges ???
+ @Override
+ public Weight createWeight(IndexSearcher searcher, ScoreMode scoreMode, float boost)
+ throws IOException {
+ return new ConstantScoreWeight(this, boost) {
+ @Override
+ public ScorerSupplier scorerSupplier(LeafReaderContext context) throws IOException {
+ if (context.reader().getFieldInfos().fieldInfo(field) == null) {
+ return null;
+ }
+ DocValuesSkipper skipper = context.reader().getDocValuesSkipper(field);
+ SortedSetDocValues values = DocValues.getSortedSet(context.reader(), field);
+ // implement ScorerSupplier, since we do some expensive stuff to make a scorer
+ return new ScorerSupplier() {
+ @Override
+ public Scorer get(long leadCost) throws IOException {
+ if (rangeClauses.isEmpty()) {
+ return empty();
+ }
+ TermsEnum termsEnum = values.termsEnum();
+ LongBitSet matchingOrdsShifted = null;
+ long minOrd = 0, maxOrd = values.getValueCount() - 1;
+ long matchesAbove =
+ values.getValueCount(); // it's last range goes to maxOrd, by default - no match
+ long maxSeenOrd = values.getValueCount();
+ TermsEnum.SeekStatus seekStatus = TermsEnum.SeekStatus.NOT_FOUND;
+ for (int r = 0; r < rangeClauses.size(); r++) {
+ MultiRangeQuery.RangeClause range = rangeClauses.get(r);
+ long startingOrd;
+ seekStatus = termsEnum.seekCeil(new BytesRef(range.lowerValue));
+ if (matchingOrdsShifted == null) { // first iter
+ if (seekStatus == TermsEnum.SeekStatus.END) {
+ return empty(); // no bitset yet, give up
+ }
+ minOrd = termsEnum.ord();
+ if (skipper != null) {
+ minOrd = Math.max(minOrd, skipper.minValue());
+ maxOrd = Math.min(maxOrd, skipper.maxValue());
+ }
+ if (maxOrd < minOrd) {
+ return empty();
+ }
+ startingOrd = minOrd;
+ } else {
+ if (seekStatus == TermsEnum.SeekStatus.END) {
+ break; // ranges - we are done, terms are exhausted
+ } else {
+ startingOrd = termsEnum.ord();
+ }
+ }
+ byte[] upper = range.upperValue; // TODO ignore reverse ranges
+ // looking for overlap
+ for (int overlap = r + 1; overlap < rangeClauses.size(); overlap++, r++) {
+ MultiRangeQuery.RangeClause mayOverlap = rangeClauses.get(overlap);
+ assert comparator.compare(range.lowerValue, 0, mayOverlap.lowerValue, 0) <= 0
+ : "since they are sorted";
+ // TODO it might be contiguous ranges, it's worth to check but I have no idea how
+ if (comparator.compare(mayOverlap.lowerValue, 0, upper, 0) <= 0) {
+ // overlap, expand if needed
+ if (comparator.compare(upper, 0, mayOverlap.upperValue, 0) < 0) {
+ upper = mayOverlap.upperValue;
+ }
+ // continue; // skip overlapping rng
+ } else {
+ break; // no r++
+ }
+ }
+ seekStatus = termsEnum.seekCeil(new BytesRef(upper));
+
+ if (seekStatus == TermsEnum.SeekStatus.END) {
+ maxSeenOrd = maxOrd; // perhaps it's worth to set for skipper
+ matchesAbove = startingOrd;
+ break; // no need to create bitset
+ }
+ maxSeenOrd =
+ seekStatus == TermsEnum.SeekStatus.FOUND
+ ? termsEnum.ord()
+ : termsEnum.ord() - 1; // floor
+
+ if (matchingOrdsShifted == null) {
+ matchingOrdsShifted = new LongBitSet(maxOrd + 1 - minOrd);
+ }
+ matchingOrdsShifted.set(
+ startingOrd - minOrd, maxSeenOrd - minOrd + 1); // up is exclusive
+ }
+ /// ranges are over, there might be no set!!
+ TwoPhaseIterator iterator;
+ long finalMatchesAbove = matchesAbove;
+ LongBitSet finalMatchingOrdsShifted = matchingOrdsShifted;
+ long finalMinOrd = minOrd;
+ iterator =
+ new TwoPhaseIterator(values) {
+ // TODO unwrap singleton?
+ @Override
+ public boolean matches() throws IOException {
+ for (int i = 0; i < values.docValueCount(); i++) {
+ long ord = values.nextOrd();
+ if (ord >= finalMinOrd
+ && ((finalMatchesAbove < values.getValueCount()
+ && ord >= finalMatchesAbove)
+ || finalMatchingOrdsShifted.get(ord - finalMinOrd))) {
Review Comment:
This was my first though too. However, then I've found [DocValuesRewriteMethod](https://github.com/apache/lucene/blob/aef16daa76b6efb354c216fbc1415fa63cd4c58c/lucene/core/src/java/org/apache/lucene/search/DocValuesRewriteMethod.java#L176) where there's the set over ordinals. So, if it's feasible for set of point values, why not do the same for set of ranges?
Perhaps, it needs to set too many 1s for ranges which fully cover all ords? I dont know.
If we think about Numeric or Binary DVs, there are no ords, and we have to search in the tree of ranges. Also, for me it's purposed for queries with more that 1000 ranges, because smaller sets can be handled via plain BooleanQuery.SHOULD.
Anyway, I'm really open for suggestions.
--
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] SortedSet DV Multi Range query [lucene]
Posted by "mkhludnev (via GitHub)" <gi...@apache.org>.
mkhludnev commented on code in PR #13974:
URL: https://github.com/apache/lucene/pull/13974#discussion_r1891510978
##########
lucene/sandbox/src/java/org/apache/lucene/sandbox/search/SortedSetMultiRangeQuery.java:
##########
@@ -0,0 +1,300 @@
+/*
+ * 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.sandbox.search;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
+import java.util.Objects;
+import org.apache.lucene.document.SortedSetDocValuesField;
+import org.apache.lucene.index.DocValues;
+import org.apache.lucene.index.DocValuesSkipper;
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.index.SortedSetDocValues;
+import org.apache.lucene.index.TermsEnum;
+import org.apache.lucene.search.BooleanQuery;
+import org.apache.lucene.search.ConstantScoreScorer;
+import org.apache.lucene.search.ConstantScoreWeight;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.search.DocValuesRangeIterator;
+import org.apache.lucene.search.IndexSearcher;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.search.QueryVisitor;
+import org.apache.lucene.search.ScoreMode;
+import org.apache.lucene.search.Scorer;
+import org.apache.lucene.search.ScorerSupplier;
+import org.apache.lucene.search.TwoPhaseIterator;
+import org.apache.lucene.search.Weight;
+import org.apache.lucene.util.ArrayUtil;
+import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.LongBitSet;
+
+/** A union multiple ranges over SortedSetDocValuesField */
+public class SortedSetMultiRangeQuery extends Query {
+ private final String field;
+ private final int bytesPerDim;
+ private final ArrayUtil.ByteArrayComparator comparator;
+ List<MultiRangeQuery.RangeClause> rangeClauses;
+
+ SortedSetMultiRangeQuery(
+ String name,
+ List<MultiRangeQuery.RangeClause> clauses,
+ int bytes,
+ ArrayUtil.ByteArrayComparator comparator) {
+ this.field = name;
+ this.rangeClauses = clauses;
+ this.bytesPerDim = bytes;
+ this.comparator = comparator;
+ }
+
+ /** Builder for creating a SortedSetMultiRangeQuery. */
+ public static class Builder {
+ private final String name;
+ protected final List<MultiRangeQuery.RangeClause> clauses = new ArrayList<>();
+ private final int bytes;
+ private final ArrayUtil.ByteArrayComparator comparator;
+
+ public Builder(String name, int bytes) {
+ this.name = Objects.requireNonNull(name);
+ this.bytes = bytes; // TODO assrt positive
+ this.comparator = ArrayUtil.getUnsignedComparator(bytes);
+ }
+
+ public Builder add(BytesRef lowerValue, BytesRef upperValue) {
+ byte[] low = lowerValue.clone().bytes;
+ byte[] up = upperValue.clone().bytes;
+ if (this.comparator.compare(low, 0, up, 0) > 0) {
+ throw new IllegalArgumentException("lowerValue must be <= upperValue");
+ } else {
+ clauses.add(new MultiRangeQuery.RangeClause(low, up));
+ }
+ return this;
+ }
+
+ public Query build() {
+ if (clauses.isEmpty()) {
+ return new BooleanQuery.Builder().build();
+ }
+ if (clauses.size() == 1) {
+ return SortedSetDocValuesField.newSlowRangeQuery(
+ name,
+ new BytesRef(clauses.getFirst().lowerValue),
+ new BytesRef(clauses.getFirst().upperValue),
+ true,
+ true);
+ }
+ return new SortedSetMultiRangeQuery(name, clauses, this.bytes, comparator);
+ }
+ }
+
+ @Override
+ public Query rewrite(IndexSearcher indexSearcher) throws IOException {
+ ArrayList<MultiRangeQuery.RangeClause> sortedClauses = new ArrayList<>(this.rangeClauses);
+ sortedClauses.sort(
+ (o1, o2) -> {
+ // if (result == 0) {
+ // return comparator.compare(o1.upperValue, 0, o2.upperValue, 0);
+ // } else {
+ return comparator.compare(o1.lowerValue, 0, o2.lowerValue, 0);
+ // }
+ });
+ if (!this.rangeClauses.equals(sortedClauses)) {
+ return new SortedSetMultiRangeQuery(
+ this.field, sortedClauses, this.bytesPerDim, this.comparator);
+ } else {
+ return this;
+ }
+ }
+
+ @Override
+ public String toString(String fld) {
+ return "SortedSetMultiRangeQuery{"
+ + "field='"
+ + fld
+ + '\''
+ + ", rangeClauses="
+ + rangeClauses
+ + // TODO better toString
+ '}';
+ }
+
+ // what TODO with reverse ranges ???
+ @Override
+ public Weight createWeight(IndexSearcher searcher, ScoreMode scoreMode, float boost)
+ throws IOException {
+ return new ConstantScoreWeight(this, boost) {
+ @Override
+ public ScorerSupplier scorerSupplier(LeafReaderContext context) throws IOException {
+ if (context.reader().getFieldInfos().fieldInfo(field) == null) {
+ return null;
+ }
+ DocValuesSkipper skipper = context.reader().getDocValuesSkipper(field);
+ SortedSetDocValues values = DocValues.getSortedSet(context.reader(), field);
+ // implement ScorerSupplier, since we do some expensive stuff to make a scorer
+ return new ScorerSupplier() {
+ @Override
+ public Scorer get(long leadCost) throws IOException {
+ if (rangeClauses.isEmpty()) {
+ return empty();
+ }
+ TermsEnum termsEnum = values.termsEnum();
+ LongBitSet matchingOrdsShifted = null;
+ long minOrd = 0, maxOrd = values.getValueCount() - 1;
+ long matchesAbove =
+ values.getValueCount(); // it's last range goes to maxOrd, by default - no match
+ long maxSeenOrd = values.getValueCount();
+ TermsEnum.SeekStatus seekStatus = TermsEnum.SeekStatus.NOT_FOUND;
+ for (int r = 0; r < rangeClauses.size(); r++) {
+ MultiRangeQuery.RangeClause range = rangeClauses.get(r);
+ long startingOrd;
+ seekStatus = termsEnum.seekCeil(new BytesRef(range.lowerValue));
+ if (matchingOrdsShifted == null) { // first iter
+ if (seekStatus == TermsEnum.SeekStatus.END) {
+ return empty(); // no bitset yet, give up
+ }
+ minOrd = termsEnum.ord();
+ if (skipper != null) {
+ minOrd = Math.max(minOrd, skipper.minValue());
+ maxOrd = Math.min(maxOrd, skipper.maxValue());
+ }
+ if (maxOrd < minOrd) {
Review Comment:
ok.
--
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