stefanvodita commented on code in PR #14204: URL: https://github.com/apache/lucene/pull/14204#discussion_r1947943381
########## lucene/facet/src/java/org/apache/lucene/facet/histogram/HistogramCollector.java: ########## @@ -0,0 +1,252 @@ +/* + * 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.facet.histogram; + +import java.io.IOException; +import org.apache.lucene.index.DocValues; +import org.apache.lucene.index.DocValuesSkipper; +import org.apache.lucene.index.DocValuesType; +import org.apache.lucene.index.FieldInfo; +import org.apache.lucene.index.LeafReaderContext; +import org.apache.lucene.index.NumericDocValues; +import org.apache.lucene.index.SortedNumericDocValues; +import org.apache.lucene.internal.hppc.LongIntHashMap; +import org.apache.lucene.search.CollectionTerminatedException; +import org.apache.lucene.search.Collector; +import org.apache.lucene.search.LeafCollector; +import org.apache.lucene.search.Scorable; +import org.apache.lucene.search.ScoreMode; + +final class HistogramCollector implements Collector { Review Comment: To clarify - were the abstractions difficult to get started with or do you think they would have complicated the implementation? Tagging @epotyom and @Shradha26 since I know they would like to improve that code. ########## lucene/facet/src/java/org/apache/lucene/facet/histogram/HistogramCollector.java: ########## @@ -0,0 +1,274 @@ +/* + * 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.facet.histogram; + +import java.io.IOException; +import org.apache.lucene.index.DocValues; +import org.apache.lucene.index.DocValuesSkipper; +import org.apache.lucene.index.DocValuesType; +import org.apache.lucene.index.FieldInfo; +import org.apache.lucene.index.LeafReaderContext; +import org.apache.lucene.index.NumericDocValues; +import org.apache.lucene.index.SortedNumericDocValues; +import org.apache.lucene.internal.hppc.LongIntHashMap; +import org.apache.lucene.search.CollectionTerminatedException; +import org.apache.lucene.search.Collector; +import org.apache.lucene.search.LeafCollector; +import org.apache.lucene.search.Scorable; +import org.apache.lucene.search.ScoreMode; + +final class HistogramCollector implements Collector { + + private final String field; + private final long interval; + private final int maxBuckets; + private final LongIntHashMap counts; + + HistogramCollector(String field, long interval, int maxBuckets) { + this.field = field; + this.interval = interval; + this.maxBuckets = maxBuckets; + this.counts = new LongIntHashMap(); + } + + @Override + public LeafCollector getLeafCollector(LeafReaderContext context) throws IOException { + FieldInfo fi = context.reader().getFieldInfos().fieldInfo(field); + if (fi == null) { + // The segment has no values, nothing to do. + throw new CollectionTerminatedException(); + } + if (fi.getDocValuesType() != DocValuesType.NUMERIC + && fi.getDocValuesType() != DocValuesType.SORTED_NUMERIC) { + throw new IllegalStateException( + "Expected numeric field, but got doc-value type: " + fi.getDocValuesType()); + } + SortedNumericDocValues values = DocValues.getSortedNumeric(context.reader(), field); + NumericDocValues singleton = DocValues.unwrapSingleton(values); + if (singleton == null) { + return new HistogramNaiveLeafCollector(values, interval, maxBuckets, counts); + } else { + DocValuesSkipper skipper = context.reader().getDocValuesSkipper(field); + if (skipper != null) { + long leafMinQuotient = Math.floorDiv(skipper.minValue(), interval); + long leafMaxQuotient = Math.floorDiv(skipper.maxValue(), interval); + if (leafMaxQuotient - leafMinQuotient <= 1024) { + // Only use the optimized implementation if there is a small number of unique quotients, + // so that we can count them using a dense array instead of a hash table. + return new HistogramLeafCollector(singleton, skipper, interval, maxBuckets, counts); + } + } + return new HistogramNaiveSingleValuedLeafCollector(singleton, interval, maxBuckets, counts); + } + } + + @Override + public ScoreMode scoreMode() { + return ScoreMode.COMPLETE_NO_SCORES; + } + + LongIntHashMap getCounts() { + return counts; + } + + /** + * Naive implementation of a histogram {@link LeafCollector}, which iterates all maches and looks + * up the value to determine the corresponding bucket. + */ + private static class HistogramNaiveLeafCollector implements LeafCollector { + + private final SortedNumericDocValues values; + private final long interval; + private final int maxBuckets; + private final LongIntHashMap counts; + + HistogramNaiveLeafCollector( + SortedNumericDocValues values, long interval, int maxBuckets, LongIntHashMap counts) { + this.values = values; + this.interval = interval; + this.maxBuckets = maxBuckets; + this.counts = counts; + } + + @Override + public void setScorer(Scorable scorer) throws IOException {} + + @Override + public void collect(int doc) throws IOException { + if (values.advanceExact(doc)) { + int valueCount = values.docValueCount(); + long prevQuotient = Long.MIN_VALUE; + for (int i = 0; i < valueCount; ++i) { + final long value = values.nextValue(); + final long quotient = Math.floorDiv(value, interval); + // We must not double-count values that divide to the same quotient since this returns doc + // counts as opposed to value counts. + if (quotient != prevQuotient) { + counts.addTo(quotient, 1); Review Comment: I was a little confused by the usage of quotient up to this point. To me quotient suggests a counter, how much of something there is (more likely to be the value in a map than a key). I think the concept here is more akin to quantile, what we refer to as bucket elsewhere. Am I misunderstanding how this is meant to work? ########## lucene/facet/src/java/org/apache/lucene/facet/histogram/HistogramCollectorManager.java: ########## @@ -0,0 +1,93 @@ +/* + * 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.facet.histogram; + +import java.io.IOException; +import java.util.Collection; +import java.util.Objects; +import org.apache.lucene.document.FieldType; +import org.apache.lucene.internal.hppc.LongIntHashMap; +import org.apache.lucene.internal.hppc.LongIntHashMap.LongIntCursor; +import org.apache.lucene.search.CollectorManager; + +/** + * {@link CollectorManager} that computes a histogram of the distribution of the values of a field. + * + * <p>The returned {@link LongIntHashMap} maps quotients to the number of documents whose value + * returns this number when divided by the given {@code interval}. + * + * <p>This implementation is optimized for the case when {@code field} is part of the index sort and + * has a {@link FieldType#setDocValuesSkipIndexType skip index}. + * + * <p>Note: this collector is inspired from "YU, Muzhi, LIN, Zhaoxiang, SUN, Jinan, et al. + * TencentCLS: the cloud log service with high query performances. Proceedings of the VLDB + * Endowment, 2022, vol. 15, no 12, p. 3472-3482.", where the authors describe how they run + * "histogram queries" by sorting the index by timestamp and pre-computing ranges of doc IDs for + * every possible bucket. + */ +public final class HistogramCollectorManager + implements CollectorManager<HistogramCollector, LongIntHashMap> { + + private static final int DEFAULT_MAX_BUCKETS = 1024; + + private final String field; + private final long interval; + private final int maxBuckets; + + /** + * Compute a histogram of the distribution of the values of the given {@code field} according to + * the given {@code interval}. This configures a maximum number of buckets equal to the default of Review Comment: Can we be more explicit about what `interval` represents? I might call it `bucketWidth`. Maybe the comment can say "Compute a histogram of the distribution of values of the given field, with buckets from 0 to `interval`, from `interval` to `2*interval`, and so on, up to the configured maximum number of buckets." -- 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
