You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by jp...@apache.org on 2023/11/03 07:55:20 UTC
(lucene) branch main updated: LUCENE-10560: Faster merging of TermsEnum (#1052)
This is an automated email from the ASF dual-hosted git repository.
jpountz pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/lucene.git
The following commit(s) were added to refs/heads/main by this push:
new 43a568cb337 LUCENE-10560: Faster merging of TermsEnum (#1052)
43a568cb337 is described below
commit 43a568cb3370fc783726fdb3cf8df8c123e0d3d2
Author: Adrien Grand <jp...@gmail.com>
AuthorDate: Fri Nov 3 08:55:15 2023 +0100
LUCENE-10560: Faster merging of TermsEnum (#1052)
Closes #11596
---
lucene/CHANGES.txt | 3 +
.../java/org/apache/lucene/index/MultiTerms.java | 14 +-
.../org/apache/lucene/index/MultiTermsEnum.java | 75 +++------
.../java/org/apache/lucene/index/OrdinalMap.java | 36 ++--
.../org/apache/lucene/index/TermsEnumIndex.java | 183 +++++++++++++++++++++
.../apache/lucene/index/TestTermsEnumIndex.java | 67 ++++++++
6 files changed, 297 insertions(+), 81 deletions(-)
diff --git a/lucene/CHANGES.txt b/lucene/CHANGES.txt
index 953e1b1cbb9..039afcba68d 100644
--- a/lucene/CHANGES.txt
+++ b/lucene/CHANGES.txt
@@ -253,8 +253,11 @@ Optimizations
* GITHUB#12719: Top-level conjunctions that are not sorted by score now have a
specialized bulk scorer. (Adrien Grand)
+* GITHUB#1052: Faster merging of terms enums. (Adrien Grand)
+
* GITHUB#11903: Faster sort on high-cardinality string fields. (Adrien Grand)
+
Changes in runtime behavior
---------------------
diff --git a/lucene/core/src/java/org/apache/lucene/index/MultiTerms.java b/lucene/core/src/java/org/apache/lucene/index/MultiTerms.java
index f56989d5a62..7f61da627ec 100644
--- a/lucene/core/src/java/org/apache/lucene/index/MultiTerms.java
+++ b/lucene/core/src/java/org/apache/lucene/index/MultiTerms.java
@@ -136,17 +136,16 @@ public final class MultiTerms extends Terms {
@Override
public TermsEnum intersect(CompiledAutomaton compiled, BytesRef startTerm) throws IOException {
- final List<MultiTermsEnum.TermsEnumIndex> termsEnums = new ArrayList<>();
+ final List<TermsEnumIndex> termsEnums = new ArrayList<>();
for (int i = 0; i < subs.length; i++) {
final TermsEnum termsEnum = subs[i].intersect(compiled, startTerm);
if (termsEnum != null) {
- termsEnums.add(new MultiTermsEnum.TermsEnumIndex(termsEnum, i));
+ termsEnums.add(new TermsEnumIndex(termsEnum, i));
}
}
if (termsEnums.size() > 0) {
- return new MultiTermsEnum(subSlices)
- .reset(termsEnums.toArray(MultiTermsEnum.TermsEnumIndex.EMPTY_ARRAY));
+ return new MultiTermsEnum(subSlices).reset(termsEnums.toArray(TermsEnumIndex.EMPTY_ARRAY));
} else {
return TermsEnum.EMPTY;
}
@@ -181,17 +180,16 @@ public final class MultiTerms extends Terms {
@Override
public TermsEnum iterator() throws IOException {
- final List<MultiTermsEnum.TermsEnumIndex> termsEnums = new ArrayList<>();
+ final List<TermsEnumIndex> termsEnums = new ArrayList<>();
for (int i = 0; i < subs.length; i++) {
final TermsEnum termsEnum = subs[i].iterator();
if (termsEnum != null) {
- termsEnums.add(new MultiTermsEnum.TermsEnumIndex(termsEnum, i));
+ termsEnums.add(new TermsEnumIndex(termsEnum, i));
}
}
if (termsEnums.size() > 0) {
- return new MultiTermsEnum(subSlices)
- .reset(termsEnums.toArray(MultiTermsEnum.TermsEnumIndex.EMPTY_ARRAY));
+ return new MultiTermsEnum(subSlices).reset(termsEnums.toArray(TermsEnumIndex.EMPTY_ARRAY));
} else {
return TermsEnum.EMPTY;
}
diff --git a/lucene/core/src/java/org/apache/lucene/index/MultiTermsEnum.java b/lucene/core/src/java/org/apache/lucene/index/MultiTermsEnum.java
index b849b07cec9..f4cbb4cc1f5 100644
--- a/lucene/core/src/java/org/apache/lucene/index/MultiTermsEnum.java
+++ b/lucene/core/src/java/org/apache/lucene/index/MultiTermsEnum.java
@@ -36,7 +36,7 @@ public final class MultiTermsEnum extends BaseTermsEnum {
new Comparator<TermsEnumWithSlice>() {
@Override
public int compare(TermsEnumWithSlice o1, TermsEnumWithSlice o2) {
- return o1.index - o2.index;
+ return o1.subIndex - o2.subIndex;
}
};
@@ -56,17 +56,6 @@ public final class MultiTermsEnum extends BaseTermsEnum {
private int numSubs;
private BytesRef current;
- static class TermsEnumIndex {
- public static final TermsEnumIndex[] EMPTY_ARRAY = new TermsEnumIndex[0];
- final int subIndex;
- final TermsEnum termsEnum;
-
- public TermsEnumIndex(TermsEnum termsEnum, int subIndex) {
- this.termsEnum = termsEnum;
- this.subIndex = subIndex;
- }
- }
-
/** Returns how many sub-reader slices contain the current term. @see #getMatchArray */
public int getMatchCount() {
return numTop;
@@ -114,10 +103,10 @@ public final class MultiTermsEnum extends BaseTermsEnum {
final TermsEnumIndex termsEnumIndex = termsEnumsIndex[i];
assert termsEnumIndex != null;
- final BytesRef term = termsEnumIndex.termsEnum.next();
+ final BytesRef term = termsEnumIndex.next();
if (term != null) {
final TermsEnumWithSlice entry = subs[termsEnumIndex.subIndex];
- entry.reset(termsEnumIndex.termsEnum, term);
+ entry.reset(termsEnumIndex);
queue.add(entry);
currentSubs[numSubs++] = entry;
} else {
@@ -154,7 +143,7 @@ public final class MultiTermsEnum extends BaseTermsEnum {
// Doing so is a waste because this sub will simply
// seek to the same spot.
if (seekOpt) {
- final BytesRef curTerm = currentSubs[i].current;
+ final BytesRef curTerm = currentSubs[i].term();
if (curTerm != null) {
final int cmp = term.compareTo(curTerm);
if (cmp == 0) {
@@ -162,19 +151,19 @@ public final class MultiTermsEnum extends BaseTermsEnum {
} else if (cmp < 0) {
status = false;
} else {
- status = currentSubs[i].terms.seekExact(term);
+ status = currentSubs[i].seekExact(term);
}
} else {
status = false;
}
} else {
- status = currentSubs[i].terms.seekExact(term);
+ status = currentSubs[i].seekExact(term);
}
if (status) {
top[numTop++] = currentSubs[i];
- current = currentSubs[i].current = currentSubs[i].terms.term();
- assert term.equals(currentSubs[i].current);
+ current = currentSubs[i].term();
+ assert term.equals(currentSubs[i].term());
}
}
@@ -206,7 +195,7 @@ public final class MultiTermsEnum extends BaseTermsEnum {
// Doing so is a waste because this sub will simply
// seek to the same spot.
if (seekOpt) {
- final BytesRef curTerm = currentSubs[i].current;
+ final BytesRef curTerm = currentSubs[i].term();
if (curTerm != null) {
final int cmp = term.compareTo(curTerm);
if (cmp == 0) {
@@ -214,28 +203,25 @@ public final class MultiTermsEnum extends BaseTermsEnum {
} else if (cmp < 0) {
status = SeekStatus.NOT_FOUND;
} else {
- status = currentSubs[i].terms.seekCeil(term);
+ status = currentSubs[i].seekCeil(term);
}
} else {
status = SeekStatus.END;
}
} else {
- status = currentSubs[i].terms.seekCeil(term);
+ status = currentSubs[i].seekCeil(term);
}
if (status == SeekStatus.FOUND) {
top[numTop++] = currentSubs[i];
- current = currentSubs[i].current = currentSubs[i].terms.term();
+ current = currentSubs[i].term();
queue.add(currentSubs[i]);
} else {
if (status == SeekStatus.NOT_FOUND) {
- currentSubs[i].current = currentSubs[i].terms.term();
- assert currentSubs[i].current != null;
+ assert currentSubs[i].term() != null;
queue.add(currentSubs[i]);
} else {
assert status == SeekStatus.END;
- // enum exhausted
- currentSubs[i].current = null;
}
}
}
@@ -269,15 +255,14 @@ public final class MultiTermsEnum extends BaseTermsEnum {
// top term
assert numTop == 0;
numTop = queue.fillTop(top);
- current = top[0].current;
+ current = top[0].term();
}
private void pushTop() throws IOException {
// call next() on each top, and reorder queue
for (int i = 0; i < numTop; i++) {
TermsEnumWithSlice top = queue.top();
- top.current = top.terms.next();
- if (top.current == null) {
+ if (top.next() == null) {
queue.pop();
} else {
queue.updateTop();
@@ -320,7 +305,7 @@ public final class MultiTermsEnum extends BaseTermsEnum {
public int docFreq() throws IOException {
int sum = 0;
for (int i = 0; i < numTop; i++) {
- sum += top[i].terms.docFreq();
+ sum += top[i].termsEnum.docFreq();
}
return sum;
}
@@ -329,7 +314,7 @@ public final class MultiTermsEnum extends BaseTermsEnum {
public long totalTermFreq() throws IOException {
long sum = 0;
for (int i = 0; i < numTop; i++) {
- final long v = top[i].terms.totalTermFreq();
+ final long v = top[i].termsEnum.totalTermFreq();
assert v != -1;
sum += v;
}
@@ -359,12 +344,12 @@ public final class MultiTermsEnum extends BaseTermsEnum {
final TermsEnumWithSlice entry = top[i];
- assert entry.index < docsEnum.subPostingsEnums.length
- : entry.index + " vs " + docsEnum.subPostingsEnums.length + "; " + subs.length;
+ assert entry.subIndex < docsEnum.subPostingsEnums.length
+ : entry.subIndex + " vs " + docsEnum.subPostingsEnums.length + "; " + subs.length;
final PostingsEnum subPostingsEnum =
- entry.terms.postings(docsEnum.subPostingsEnums[entry.index], flags);
+ entry.termsEnum.postings(docsEnum.subPostingsEnums[entry.subIndex], flags);
assert subPostingsEnum != null;
- docsEnum.subPostingsEnums[entry.index] = subPostingsEnum;
+ docsEnum.subPostingsEnums[entry.subIndex] = subPostingsEnum;
subDocs[upto].postingsEnum = subPostingsEnum;
subDocs[upto].slice = entry.subSlice;
upto++;
@@ -379,26 +364,18 @@ public final class MultiTermsEnum extends BaseTermsEnum {
return new SlowImpactsEnum(postings(null, flags));
}
- static final class TermsEnumWithSlice {
+ static final class TermsEnumWithSlice extends TermsEnumIndex {
private final ReaderSlice subSlice;
- TermsEnum terms;
- public BytesRef current;
- final int index;
public TermsEnumWithSlice(int index, ReaderSlice subSlice) {
+ super(null, index);
this.subSlice = subSlice;
- this.index = index;
assert subSlice.length >= 0 : "length=" + subSlice.length;
}
- public void reset(TermsEnum terms, BytesRef term) {
- this.terms = terms;
- current = term;
- }
-
@Override
public String toString() {
- return subSlice.toString() + ":" + terms;
+ return subSlice.toString() + ":" + super.toString();
}
}
@@ -413,7 +390,7 @@ public final class MultiTermsEnum extends BaseTermsEnum {
@Override
protected boolean lessThan(TermsEnumWithSlice termsA, TermsEnumWithSlice termsB) {
- return termsA.current.compareTo(termsB.current) < 0;
+ return termsA.compareTermTo(termsB) < 0;
}
/**
@@ -435,7 +412,7 @@ public final class MultiTermsEnum extends BaseTermsEnum {
final int leftChild = index << 1;
for (int child = leftChild, end = Math.min(size, leftChild + 1); child <= end; ++child) {
TermsEnumWithSlice te = get(child);
- if (te.current.equals(tops[0].current)) {
+ if (te.compareTermTo(tops[0]) == 0) {
tops[numTop++] = te;
stack[stackLen++] = child;
}
diff --git a/lucene/core/src/java/org/apache/lucene/index/OrdinalMap.java b/lucene/core/src/java/org/apache/lucene/index/OrdinalMap.java
index 04b83a811f2..bcee2f43214 100644
--- a/lucene/core/src/java/org/apache/lucene/index/OrdinalMap.java
+++ b/lucene/core/src/java/org/apache/lucene/index/OrdinalMap.java
@@ -24,8 +24,6 @@ import java.util.Collection;
import java.util.List;
import org.apache.lucene.util.Accountable;
import org.apache.lucene.util.Accountables;
-import org.apache.lucene.util.BytesRef;
-import org.apache.lucene.util.BytesRefBuilder;
import org.apache.lucene.util.InPlaceMergeSorter;
import org.apache.lucene.util.LongValues;
import org.apache.lucene.util.PriorityQueue;
@@ -48,19 +46,15 @@ public class OrdinalMap implements Accountable {
// need it
// TODO: use more efficient packed ints structures?
- private static class TermsEnumIndex {
- final int subIndex;
- final TermsEnum termsEnum;
- BytesRef currentTerm;
+ private static class TermsEnumPriorityQueue extends PriorityQueue<TermsEnumIndex> {
- public TermsEnumIndex(TermsEnum termsEnum, int subIndex) {
- this.termsEnum = termsEnum;
- this.subIndex = subIndex;
+ TermsEnumPriorityQueue(int size) {
+ super(size);
}
- public BytesRef next() throws IOException {
- currentTerm = termsEnum.next();
- return currentTerm;
+ @Override
+ protected boolean lessThan(TermsEnumIndex a, TermsEnumIndex b) {
+ return a.compareTermTo(b) < 0;
}
}
@@ -227,13 +221,7 @@ public class OrdinalMap implements Accountable {
long[] segmentOrds = new long[subs.length];
// Just merge-sorts by term:
- PriorityQueue<TermsEnumIndex> queue =
- new PriorityQueue<TermsEnumIndex>(subs.length) {
- @Override
- protected boolean lessThan(TermsEnumIndex a, TermsEnumIndex b) {
- return a.currentTerm.compareTo(b.currentTerm) < 0;
- }
- };
+ TermsEnumPriorityQueue queue = new TermsEnumPriorityQueue(subs.length);
for (int i = 0; i < subs.length; i++) {
TermsEnumIndex sub = new TermsEnumIndex(subs[segmentMap.newToOld(i)], i);
@@ -242,19 +230,18 @@ public class OrdinalMap implements Accountable {
}
}
- BytesRefBuilder scratch = new BytesRefBuilder();
+ TermsEnumIndex.TermState topState = new TermsEnumIndex.TermState();
long globalOrd = 0;
while (queue.size() != 0) {
TermsEnumIndex top = queue.top();
- scratch.copyBytes(top.currentTerm);
+ topState.copyFrom(top);
int firstSegmentIndex = Integer.MAX_VALUE;
long globalOrdDelta = Long.MAX_VALUE;
// Advance past this term, recording the per-segment ord deltas:
while (true) {
- top = queue.top();
long segmentOrd = top.termsEnum.ord();
long delta = globalOrd - segmentOrd;
int segmentIndex = top.subIndex;
@@ -284,10 +271,11 @@ public class OrdinalMap implements Accountable {
if (queue.size() == 0) {
break;
}
+ top = queue.top();
} else {
- queue.updateTop();
+ top = queue.updateTop();
}
- if (queue.top().currentTerm.equals(scratch.get()) == false) {
+ if (top.termEquals(topState) == false) {
break;
}
}
diff --git a/lucene/core/src/java/org/apache/lucene/index/TermsEnumIndex.java b/lucene/core/src/java/org/apache/lucene/index/TermsEnumIndex.java
new file mode 100644
index 00000000000..57a5d5ae0cb
--- /dev/null
+++ b/lucene/core/src/java/org/apache/lucene/index/TermsEnumIndex.java
@@ -0,0 +1,183 @@
+/*
+ * 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.index;
+
+import java.io.IOException;
+import java.util.Arrays;
+import java.util.Objects;
+import org.apache.lucene.index.TermsEnum.SeekStatus;
+import org.apache.lucene.util.BitUtil;
+import org.apache.lucene.util.BytesRef;
+import org.apache.lucene.util.BytesRefBuilder;
+
+/**
+ * Wrapper around a {@link TermsEnum} and an integer that identifies it. All operations that move
+ * the current position of the {@link TermsEnum} must be performed via this wrapper class, not
+ * directly on the wrapped {@link TermsEnum}.
+ */
+class TermsEnumIndex {
+
+ static final TermsEnumIndex[] EMPTY_ARRAY = new TermsEnumIndex[0];
+
+ /**
+ * Copy the first 8 bytes of the given term as a comparable unsigned long. In case the term has
+ * less than 8 bytes, missing bytes will be replaced with zeroes. Note that two terms that produce
+ * the same long could still be different due to the fact that missing bytes are replaced with
+ * zeroes, e.g. {@code [1, 0]} and {@code [1]} get mapped to the same long.
+ */
+ static long prefix8ToComparableUnsignedLong(BytesRef term) {
+ // Use Big Endian so that longs are comparable
+ if (term.length >= Long.BYTES) {
+ return (long) BitUtil.VH_BE_LONG.get(term.bytes, term.offset);
+ } else {
+ long l;
+ int o;
+ if (Integer.BYTES <= term.length) {
+ l = (int) BitUtil.VH_BE_INT.get(term.bytes, term.offset);
+ o = Integer.BYTES;
+ } else {
+ l = 0;
+ o = 0;
+ }
+ if (o + Short.BYTES <= term.length) {
+ l =
+ (l << Short.SIZE)
+ | Short.toUnsignedLong(
+ (short) BitUtil.VH_BE_SHORT.get(term.bytes, term.offset + o));
+ o += Short.BYTES;
+ }
+ if (o < term.length) {
+ l = (l << Byte.SIZE) | Byte.toUnsignedLong(term.bytes[term.offset + o]);
+ }
+ l <<= (Long.BYTES - term.length) << 3;
+ return l;
+ }
+ }
+
+ final int subIndex;
+ TermsEnum termsEnum;
+ private BytesRef currentTerm;
+ private long currentTermPrefix8;
+
+ TermsEnumIndex(TermsEnum termsEnum, int subIndex) {
+ this.termsEnum = termsEnum;
+ this.subIndex = subIndex;
+ }
+
+ BytesRef term() {
+ return currentTerm;
+ }
+
+ private void setTerm(BytesRef term) {
+ currentTerm = term;
+ if (currentTerm == null) {
+ currentTermPrefix8 = 0;
+ } else {
+ currentTermPrefix8 = prefix8ToComparableUnsignedLong(currentTerm);
+ }
+ }
+
+ BytesRef next() throws IOException {
+ BytesRef term = termsEnum.next();
+ setTerm(term);
+ return term;
+ }
+
+ SeekStatus seekCeil(BytesRef term) throws IOException {
+ SeekStatus status = termsEnum.seekCeil(term);
+ if (status == SeekStatus.END) {
+ setTerm(null);
+ } else {
+ setTerm(termsEnum.term());
+ }
+ return status;
+ }
+
+ boolean seekExact(BytesRef term) throws IOException {
+ boolean found = termsEnum.seekExact(term);
+ if (found) {
+ setTerm(termsEnum.term());
+ } else {
+ setTerm(null);
+ }
+ return found;
+ }
+
+ void seekExact(long ord) throws IOException {
+ termsEnum.seekExact(ord);
+ setTerm(termsEnum.term());
+ }
+
+ void reset(TermsEnumIndex tei) throws IOException {
+ termsEnum = tei.termsEnum;
+ currentTerm = tei.currentTerm;
+ currentTermPrefix8 = tei.currentTermPrefix8;
+ }
+
+ int compareTermTo(TermsEnumIndex that) {
+ if (currentTermPrefix8 != that.currentTermPrefix8) {
+ int cmp = Long.compareUnsigned(currentTermPrefix8, that.currentTermPrefix8);
+ assert Integer.signum(cmp)
+ == Integer.signum(
+ Arrays.compareUnsigned(
+ currentTerm.bytes,
+ currentTerm.offset,
+ currentTerm.offset + currentTerm.length,
+ that.currentTerm.bytes,
+ that.currentTerm.offset,
+ that.currentTerm.offset + that.currentTerm.length));
+ return cmp;
+ }
+
+ return Arrays.compareUnsigned(
+ currentTerm.bytes,
+ currentTerm.offset,
+ currentTerm.offset + currentTerm.length,
+ that.currentTerm.bytes,
+ that.currentTerm.offset,
+ that.currentTerm.offset + that.currentTerm.length);
+ }
+
+ @Override
+ public String toString() {
+ return Objects.toString(termsEnum);
+ }
+
+ /** Wrapper around a term that allows for quick equals comparisons. */
+ static class TermState {
+ private final BytesRefBuilder term = new BytesRefBuilder();
+ private long termPrefix8;
+
+ void copyFrom(TermsEnumIndex tei) {
+ term.copyBytes(tei.term());
+ termPrefix8 = tei.currentTermPrefix8;
+ }
+ }
+
+ boolean termEquals(TermState that) {
+ if (currentTermPrefix8 != that.termPrefix8) {
+ return false;
+ }
+ return Arrays.equals(
+ currentTerm.bytes,
+ currentTerm.offset,
+ currentTerm.offset + currentTerm.length,
+ that.term.bytes(),
+ 0,
+ that.term.length());
+ }
+}
diff --git a/lucene/core/src/test/org/apache/lucene/index/TestTermsEnumIndex.java b/lucene/core/src/test/org/apache/lucene/index/TestTermsEnumIndex.java
new file mode 100644
index 00000000000..ac964052718
--- /dev/null
+++ b/lucene/core/src/test/org/apache/lucene/index/TestTermsEnumIndex.java
@@ -0,0 +1,67 @@
+/*
+ * 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.index;
+
+import org.apache.lucene.tests.util.LuceneTestCase;
+import org.apache.lucene.util.BytesRef;
+
+public class TestTermsEnumIndex extends LuceneTestCase {
+
+ public void testPrefix8ToComparableUnsignedLong() {
+ byte[] b = new byte[] {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12};
+ assertEquals(0L, TermsEnumIndex.prefix8ToComparableUnsignedLong(new BytesRef(b, 1, 0)));
+ assertEquals(4L << 56, TermsEnumIndex.prefix8ToComparableUnsignedLong(new BytesRef(b, 3, 1)));
+ assertEquals(
+ (4L << 56) | (5L << 48),
+ TermsEnumIndex.prefix8ToComparableUnsignedLong(new BytesRef(b, 3, 2)));
+ assertEquals(
+ (4L << 56) | (5L << 48) | (6L << 40),
+ TermsEnumIndex.prefix8ToComparableUnsignedLong(new BytesRef(b, 3, 3)));
+ assertEquals(
+ (4L << 56) | (5L << 48) | (6L << 40) | (7L << 32),
+ TermsEnumIndex.prefix8ToComparableUnsignedLong(new BytesRef(b, 3, 4)));
+ assertEquals(
+ (4L << 56) | (5L << 48) | (6L << 40) | (7L << 32) | (8L << 24),
+ TermsEnumIndex.prefix8ToComparableUnsignedLong(new BytesRef(b, 3, 5)));
+ assertEquals(
+ (4L << 56) | (5L << 48) | (6L << 40) | (7L << 32) | (8L << 24) | (9L << 16),
+ TermsEnumIndex.prefix8ToComparableUnsignedLong(new BytesRef(b, 3, 6)));
+ assertEquals(
+ (4L << 56) | (5L << 48) | (6L << 40) | (7L << 32) | (8L << 24) | (9L << 16) | (10L << 8),
+ TermsEnumIndex.prefix8ToComparableUnsignedLong(new BytesRef(b, 3, 7)));
+ assertEquals(
+ (4L << 56)
+ | (5L << 48)
+ | (6L << 40)
+ | (7L << 32)
+ | (8L << 24)
+ | (9L << 16)
+ | (10L << 8)
+ | 11L,
+ TermsEnumIndex.prefix8ToComparableUnsignedLong(new BytesRef(b, 3, 8)));
+ assertEquals(
+ (4L << 56)
+ | (5L << 48)
+ | (6L << 40)
+ | (7L << 32)
+ | (8L << 24)
+ | (9L << 16)
+ | (10L << 8)
+ | 11L,
+ TermsEnumIndex.prefix8ToComparableUnsignedLong(new BytesRef(b, 3, 9)));
+ }
+}