jpountz commented on code in PR #13563:
URL: https://github.com/apache/lucene/pull/13563#discussion_r1677204200
##########
lucene/core/src/java/org/apache/lucene/codecs/lucene90/Lucene90DocValuesFormat.java:
##########
@@ -194,5 +194,34 @@ public DocValuesProducer fieldsProducer(SegmentReadState
state) throws IOExcepti
static final int TERMS_DICT_REVERSE_INDEX_SIZE = 1 <<
TERMS_DICT_REVERSE_INDEX_SHIFT;
static final int TERMS_DICT_REVERSE_INDEX_MASK =
TERMS_DICT_REVERSE_INDEX_SIZE - 1;
+ // number of documents in an interval
private static final int DEFAULT_SKIP_INDEX_INTERVAL_SIZE = 4096;
+ // number of intervals represented as a shift to create a new level, this is
1 << 3 == 8
+ // intervals.
+ static final int SKIP_INDEX_LEVEL_SHIFT = 3;
+ // max number of levels
+ // Increasing this number, it increases how much heap we need at index time.
+ // we currently need (1 * 8 * 8 * 8) = 512 accumulators on heap
+ static final int SKIP_INDEX_MAX_LEVEL = 4;
+ // how many intervals at level 0 are in each level (1 <<
(SKIP_INDEX_LEVEL_SHIFT * level)).
+ static int[] SKIP_INDEX_NUMBER_INTERVALS_PER_LEVEL = new
int[SKIP_INDEX_MAX_LEVEL];
+ // number of bytes to skip when skipping a level. It does not take into
account the
+ // current interval that is being read.
+ static long[] SKIP_INDEX_JUMP_LENGTH_PER_LEVEL = new
long[SKIP_INDEX_MAX_LEVEL];
+
+ static {
+ for (int level = 0; level < SKIP_INDEX_MAX_LEVEL; level++) {
+ SKIP_INDEX_NUMBER_INTERVALS_PER_LEVEL[level] = 1 <<
(SKIP_INDEX_LEVEL_SHIFT * level);
Review Comment:
Nit: It's so cheap to compute that I wonder if we should really use a lookup
table vs. recomputing it all the time.
##########
lucene/core/src/java/org/apache/lucene/codecs/lucene90/Lucene90DocValuesProducer.java:
##########
@@ -1792,61 +1794,88 @@ public DocValuesSkipper getSkipper(FieldInfo field)
throws IOException {
if (input.length() > 0) {
input.prefetch(0, 1);
}
+ // TODO: should we write to disk the actual max level for this segment?
return new DocValuesSkipper() {
- int minDocID = -1;
- int maxDocID = -1;
- long minValue, maxValue;
- int docCount;
+ final int[] minDocID = new int[SKIP_INDEX_MAX_LEVEL];
+ final int[] maxDocID = new int[SKIP_INDEX_MAX_LEVEL];
+
+ {
+ for (int i = 0; i < SKIP_INDEX_MAX_LEVEL; i++) {
+ minDocID[i] = maxDocID[i] = -1;
+ }
+ }
+
+ final long[] minValue = new long[SKIP_INDEX_MAX_LEVEL];
+ final long[] maxValue = new long[SKIP_INDEX_MAX_LEVEL];
+ final int[] docCount = new int[SKIP_INDEX_MAX_LEVEL];
+ int levels;
@Override
public void advance(int target) throws IOException {
if (target > entry.maxDocId) {
- minDocID = DocIdSetIterator.NO_MORE_DOCS;
- maxDocID = DocIdSetIterator.NO_MORE_DOCS;
+ // skipper is exhausted
+ for (int i = 0; i < SKIP_INDEX_MAX_LEVEL; i++) {
+ minDocID[i] = maxDocID[i] = DocIdSetIterator.NO_MORE_DOCS;
+ }
} else {
+ // find next interval
+ assert target > maxDocID[0] : "target must be bigger that current
interval";
while (true) {
- maxDocID = input.readInt();
- if (maxDocID >= target) {
- minDocID = input.readInt();
- maxValue = input.readLong();
- minValue = input.readLong();
- docCount = input.readInt();
+ levels = input.readByte();
Review Comment:
I'm a bit confused by this, because this `levels` variable feels like the
number of lower levels that are getting updated, while some highel levels may
still be valid? But then it would not be correct to return `levels` in
`numLevels()` as we'd be missing these higher levels that are still valid?
E.g. if there are 8 intervals, there are two levels. But when we read the
second interval, then `levels` is 1 because only the lower level needs
updating, but there are still 2 valid levels?
##########
lucene/core/src/java/org/apache/lucene/codecs/lucene90/Lucene90DocValuesConsumer.java:
##########
@@ -207,65 +210,120 @@ void accumulate(long value) {
maxValue = Math.max(maxValue, value);
}
+ void accumulate(SkipAccumulator other) {
+ maxDocID = other.maxDocID;
+ minValue = Math.min(minValue, other.minValue);
+ maxValue = Math.max(maxValue, other.maxValue);
+ docCount += other.docCount;
+ }
+
void nextDoc(int docID) {
maxDocID = docID;
++docCount;
}
- void writeTo(DataOutput output) throws IOException {
- output.writeInt(maxDocID);
- output.writeInt(minDocID);
- output.writeLong(maxValue);
- output.writeLong(minValue);
- output.writeInt(docCount);
+ public static SkipAccumulator merge(List<SkipAccumulator> list, int index,
int length) {
+ SkipAccumulator acc = new SkipAccumulator(list.get(index).minDocID);
+ for (int i = 0; i < length; i++) {
+ acc.accumulate(list.get(index + i));
+ }
+ return acc;
}
}
private void writeSkipIndex(FieldInfo field, DocValuesProducer
valuesProducer)
throws IOException {
assert field.hasDocValuesSkipIndex();
- // TODO: This disk compression once we introduce levels
- long start = data.getFilePointer();
- SortedNumericDocValues values = valuesProducer.getSortedNumeric(field);
+ final long start = data.getFilePointer();
+ final SortedNumericDocValues values =
valuesProducer.getSortedNumeric(field);
long globalMaxValue = Long.MIN_VALUE;
long globalMinValue = Long.MAX_VALUE;
int globalDocCount = 0;
int maxDocId = -1;
+ List<SkipAccumulator> accumulators = new ArrayList<>();
SkipAccumulator accumulator = null;
- int counter = 0;
for (int doc = values.nextDoc(); doc != DocIdSetIterator.NO_MORE_DOCS; doc
= values.nextDoc()) {
- if (counter == 0) {
+ if (accumulator == null) {
accumulator = new SkipAccumulator(doc);
+ accumulators.add(accumulator);
}
accumulator.nextDoc(doc);
for (int i = 0, end = values.docValueCount(); i < end; ++i) {
accumulator.accumulate(values.nextValue());
}
- if (++counter == skipIndexIntervalSize) {
+ if (accumulator.docCount == skipIndexIntervalSize) {
globalMaxValue = Math.max(globalMaxValue, accumulator.maxValue);
globalMinValue = Math.min(globalMinValue, accumulator.minValue);
globalDocCount += accumulator.docCount;
maxDocId = accumulator.maxDocID;
- accumulator.writeTo(data);
- counter = 0;
+ accumulator = null;
+ if (accumulators.size()
+ == SKIP_INDEX_NUMBER_INTERVALS_PER_LEVEL[SKIP_INDEX_MAX_LEVEL -
1]) {
+ writeLevels(accumulators);
+ accumulators.clear();
+ }
}
}
- if (counter > 0) {
- globalMaxValue = Math.max(globalMaxValue, accumulator.maxValue);
- globalMinValue = Math.min(globalMinValue, accumulator.minValue);
- globalDocCount += accumulator.docCount;
- maxDocId = accumulator.maxDocID;
- accumulator.writeTo(data);
+ if (accumulators.isEmpty() == false) {
+ if (accumulator != null) {
+ globalMaxValue = Math.max(globalMaxValue, accumulator.maxValue);
+ globalMinValue = Math.min(globalMinValue, accumulator.minValue);
+ globalDocCount += accumulator.docCount;
+ maxDocId = accumulator.maxDocID;
+ }
+ writeLevels(accumulators);
}
meta.writeLong(start); // record the start in meta
meta.writeLong(data.getFilePointer() - start); // record the length
+ assert globalDocCount == 0 || globalMaxValue >= globalMinValue;
meta.writeLong(globalMaxValue);
meta.writeLong(globalMinValue);
+ assert globalDocCount <= maxDocId + 1;
meta.writeInt(globalDocCount);
meta.writeInt(maxDocId);
}
+ private void writeLevels(List<SkipAccumulator> accumulators) throws
IOException {
+ for (int index = 0; index < accumulators.size(); index++) {
+ // compute how many levels we need to write for the current accumulator
+ final int levels = getLevels(index, accumulators.size());
+ // build the levels
+ final SkipAccumulator[] accLevels = new SkipAccumulator[levels];
+ for (int level = 0; level < levels; level++) {
+ accLevels[level] =
+ SkipAccumulator.merge(
+ accumulators, index,
SKIP_INDEX_NUMBER_INTERVALS_PER_LEVEL[level]);
Review Comment:
It would be a bit more efficient to compute the accumulators on a level
based on the accumulator of the previous level rather than using accumulators
at level 0 all the time?
##########
lucene/core/src/java/org/apache/lucene/codecs/lucene90/Lucene90DocValuesFormat.java:
##########
@@ -194,5 +194,34 @@ public DocValuesProducer fieldsProducer(SegmentReadState
state) throws IOExcepti
static final int TERMS_DICT_REVERSE_INDEX_SIZE = 1 <<
TERMS_DICT_REVERSE_INDEX_SHIFT;
static final int TERMS_DICT_REVERSE_INDEX_MASK =
TERMS_DICT_REVERSE_INDEX_SIZE - 1;
+ // number of documents in an interval
private static final int DEFAULT_SKIP_INDEX_INTERVAL_SIZE = 4096;
+ // number of intervals represented as a shift to create a new level, this is
1 << 3 == 8
+ // intervals.
+ static final int SKIP_INDEX_LEVEL_SHIFT = 3;
+ // max number of levels
+ // Increasing this number, it increases how much heap we need at index time.
+ // we currently need (1 * 8 * 8 * 8) = 512 accumulators on heap
+ static final int SKIP_INDEX_MAX_LEVEL = 4;
+ // how many intervals at level 0 are in each level (1 <<
(SKIP_INDEX_LEVEL_SHIFT * level)).
+ static int[] SKIP_INDEX_NUMBER_INTERVALS_PER_LEVEL = new
int[SKIP_INDEX_MAX_LEVEL];
+ // number of bytes to skip when skipping a level. It does not take into
account the
+ // current interval that is being read.
+ static long[] SKIP_INDEX_JUMP_LENGTH_PER_LEVEL = new
long[SKIP_INDEX_MAX_LEVEL];
+
+ static {
+ for (int level = 0; level < SKIP_INDEX_MAX_LEVEL; level++) {
+ SKIP_INDEX_NUMBER_INTERVALS_PER_LEVEL[level] = 1 <<
(SKIP_INDEX_LEVEL_SHIFT * level);
+ if (level > 0) {
+ SKIP_INDEX_JUMP_LENGTH_PER_LEVEL[level] =
+ // jump from previous level
+ SKIP_INDEX_JUMP_LENGTH_PER_LEVEL[level - 1]
+ // add nodes added by new level minus first one
+ + (SKIP_INDEX_NUMBER_INTERVALS_PER_LEVEL[level] - 1) * 29L
Review Comment:
Can you add a constant for this `29` and explain how it's computed?
--
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-unsubscr...@lucene.apache.org
For queries about this service, please contact Infrastructure at:
us...@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-unsubscr...@lucene.apache.org
For additional commands, e-mail: issues-h...@lucene.apache.org
