michaeljmarshall commented on code in PR #16571: URL: https://github.com/apache/lucene/pull/16571#discussion_r3884186760
########## lucene/core/src/java/org/apache/lucene/index/DocRangeDocValuesProducer.java: ########## @@ -0,0 +1,256 @@ +/* + * 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 org.apache.lucene.codecs.DocValuesProducer; + +/** + * A doc values producer whose iterators cover only {@code [start, end)} of the segment. + * + * <p>Marking the other documents deleted is not enough to keep a merge from reading them. A merge + * walks each field's values with {@link DocValuesIterator#nextDoc()} and drops whatever the + * document map sends to {@code -1}, so the values are decoded first and discarded afterwards; an + * output of a partitioned merge that wants a twentieth of the segment still pays for all of it, and + * k outputs pay k times over. Seeking to the range and stopping at its end turns that back into one + * read of the whole segment shared between the outputs. + * + * <p>Only the iteration is restricted. The value space -- the term dictionary behind a sorted field + * and the ordinals into it -- is left whole, because a merge builds its ordinal map from it and + * expects the same dictionary a full reader would have shown. + * + * <p>The five kinds of doc values differ only in the values they hand back, and not at all in how + * they are iterated, so each one below is Lucene's plain filter for its kind with the iteration + * taken over by a shared {@link RangeCursor}. + */ +final class DocRangeDocValuesProducer extends DocValuesProducer { + + private final DocValuesProducer in; + private final int start; + private final int end; + + DocRangeDocValuesProducer(DocValuesProducer in, int start, int end) { + this.in = in; + this.start = start; + this.end = end; + } + + /** Iteration restricted to {@code [start, end)}, over any kind of doc values. */ + private final class RangeCursor { + private final DocValuesIterator values; + private int doc = -1; + + RangeCursor(DocValuesIterator values) { + this.values = values; + } + + int docID() { + return doc; + } + + int nextDoc() throws IOException { + // The first call seeks to the range; the rest walk inside it. Reaching its end is the end of + // the iteration, not a step to the next document. + return doc = clamp(doc < start ? values.advance(start) : values.nextDoc()); + } + + int advance(int target) throws IOException { + return doc = clamp(values.advance(Math.max(target, start))); + } + + boolean advanceExact(int target) throws IOException { + doc = target; + return target >= start && target < end && values.advanceExact(target); Review Comment: Looks like we can get corrupted state if the `advanceExact(target)` method is called with a `target >= end` followed up by a call to `nextDoc()`. I think we want a defensive check to `doc >= end` in the `nextDoc()` method to return `DocValuesIterator.NO_MORE_DOCS`. Doesn't look like it's used this way, but I don't see anything in the javadocs indicating it is invalid to call `advanceExact` then `nextDoc` ########## lucene/core/src/java/org/apache/lucene/index/DocRangeCodecReader.java: ########## @@ -0,0 +1,119 @@ +/* + * 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.codecs.DocValuesProducer; +import org.apache.lucene.codecs.KnnVectorsReader; +import org.apache.lucene.codecs.NormsProducer; +import org.apache.lucene.util.Bits; +import org.apache.lucene.util.FixedBitSet; + +/** + * Exposes only documents in {@code [start, end)} of the wrapped reader, by treating everything + * outside that range as deleted. Used by {@link IndexWriter} to build one output of a partitioned + * merge (see {@link MergePolicy.OneMerge#getDocRangePartitions(java.util.List)}). + * + * <p>Documents outside the range map to {@code -1} in the resulting {@link MergeState.DocMap}, + * which is what lets the existing delete carry-over logic route each concurrently-arriving delete + * to exactly the one output that owns the document, with no additional bookkeeping. + */ +final class DocRangeCodecReader extends FilterCodecReader { + + private final Bits liveDocs; + private final int numDocs; + private final int start; + private final int end; + + DocRangeCodecReader(CodecReader in, int start, int end) { + super(in); + this.start = start; + this.end = end; + assert start >= 0 && end <= in.maxDoc() && start <= end + : "bad range [" + start + "," + end + ") maxDoc=" + in.maxDoc(); + FixedBitSet bits = new FixedBitSet(in.maxDoc()); + if (start < end) { + // An output can legitimately own no document in this reader -- a key + // missing here makes two cuts land on the same offset -- and + // FixedBitSet#set rejects an empty range starting at maxDoc. + bits.set(start, end); + } + Bits existing = in.getLiveDocs(); + if (existing != null) { + existing.applyMask(bits, 0); + } Review Comment: Nit: we could be more memory efficient by adding a `RangeBitSet` that stores the bounds and a reference to the live docs `Bits`. ########## lucene/core/src/java/org/apache/lucene/index/DocRangeNormsProducer.java: ########## @@ -0,0 +1,86 @@ +/* + * 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 org.apache.lucene.codecs.NormsProducer; + +/** + * Norms restricted to {@code [start, end)} rather than merely masked. + * + * <p>Masking is enough for correctness but not for cost: merging a field's norms walks the column + * with {@link NumericDocValues#nextDoc()} and drops whatever the document map sends to {@code -1}, + * having already read it. Each output of a partitioned merge would therefore read the whole column, + * and k outputs would read it k times. Seeking to the range instead makes the outputs together read + * it once. + */ +final class DocRangeNormsProducer extends NormsProducer { + + private final NormsProducer in; + private final int start; + private final int end; + + DocRangeNormsProducer(NormsProducer in, int start, int end) { + this.in = in; + this.start = start; + this.end = end; + } + + @Override + public NumericDocValues getNorms(FieldInfo field) throws IOException { + final NumericDocValues values = in.getNorms(field); + return new FilterNumericDocValues(values) { + private int doc = -1; + + @Override + public int docID() { + return doc; + } + + @Override + public int nextDoc() throws IOException { + // The first call seeks to the range; the rest walk inside it. + return doc = clamp(doc < start ? values.advance(start) : values.nextDoc()); + } + + @Override + public int advance(int target) throws IOException { + return doc = clamp(values.advance(Math.max(target, start))); + } + + @Override + public boolean advanceExact(int target) throws IOException { + doc = target; + return target >= start && target < end && values.advanceExact(target); + } Review Comment: Same observation about `advanceExact` then `nextDoc`. ########## lucene/core/src/java/org/apache/lucene/index/DocRangeCodecReader.java: ########## @@ -0,0 +1,119 @@ +/* + * 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.codecs.DocValuesProducer; +import org.apache.lucene.codecs.KnnVectorsReader; +import org.apache.lucene.codecs.NormsProducer; +import org.apache.lucene.util.Bits; +import org.apache.lucene.util.FixedBitSet; + +/** + * Exposes only documents in {@code [start, end)} of the wrapped reader, by treating everything + * outside that range as deleted. Used by {@link IndexWriter} to build one output of a partitioned + * merge (see {@link MergePolicy.OneMerge#getDocRangePartitions(java.util.List)}). + * + * <p>Documents outside the range map to {@code -1} in the resulting {@link MergeState.DocMap}, + * which is what lets the existing delete carry-over logic route each concurrently-arriving delete + * to exactly the one output that owns the document, with no additional bookkeeping. + */ +final class DocRangeCodecReader extends FilterCodecReader { + + private final Bits liveDocs; + private final int numDocs; + private final int start; + private final int end; + + DocRangeCodecReader(CodecReader in, int start, int end) { Review Comment: IIUC, in the special case where `start == end`, we don't have any docs and can skip the iterating the terms tree. A possible optimization could ensure skip that iteration when the two bounds are equal. -- 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: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
