You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@lucene.apache.org by at...@apache.org on 2025/04/18 10:09:15 UTC
(lucene) 01/09: Initial commit without triggering changes
This is an automated email from the ASF dual-hosted git repository.
atri pushed a commit to branch index_binning_changes
in repository https://gitbox.apache.org/repos/asf/lucene.git
commit 8e6ff8fffa787fa1230f52b6e35471c9ab45d8d4
Author: Atri Sharma <at...@192.168.1.25>
AuthorDate: Fri Apr 18 01:02:37 2025 +0530
Initial commit without triggering changes
---
.../apache/lucene/codecs/ApproximateDocBinner.java | 61 ++++++
.../lucene/codecs/ApproximateDocGraphBuilder.java | 139 ++++++++++++++
.../org/apache/lucene/codecs/BinMapReader.java | 110 +++++++++++
.../org/apache/lucene/codecs/BinMapWriter.java | 116 ++++++++++++
.../apache/lucene/codecs/BinQualityMetrics.java | 51 +++++
.../lucene/codecs/DocBinningGraphBuilder.java | 126 +++++++++++++
.../org/apache/lucene/codecs/DocGraphBuilder.java | 185 +++++++++++++++++++
.../org/apache/lucene/codecs/FieldsLeafReader.java | 172 +++++++++++++++++
.../lucene/codecs/InMemorySparseEdgeGraph.java | 79 ++++++++
.../org/apache/lucene/codecs/SparseEdgeGraph.java | 52 ++++++
.../codecs/lucene103/Lucene103PostingsFormat.java | 138 +++++++++++++-
.../apache/lucene/index/BinScoreLeafReader.java | 56 ++++++
.../org/apache/lucene/index/BinScoreReader.java | 53 ++++++
.../java/org/apache/lucene/index/BinScoreUtil.java | 134 ++++++++++++++
.../lucene/search/AnytimeRankingCollector.java | 109 +++++++++++
.../search/AnytimeRankingCollectorManager.java | 69 +++++++
.../lucene/search/AnytimeRankingSearcher.java | 52 ++++++
.../apache/lucene/search/BinBoostCalculator.java | 95 ++++++++++
.../apache/lucene/util/HeuristicSLAEstimator.java | 205 +++++++++++++++++++++
.../java/org/apache/lucene/util/SLAEstimator.java | 27 +++
20 files changed, 2028 insertions(+), 1 deletion(-)
diff --git a/lucene/core/src/java/org/apache/lucene/codecs/ApproximateDocBinner.java b/lucene/core/src/java/org/apache/lucene/codecs/ApproximateDocBinner.java
new file mode 100644
index 00000000000..ac889998d8c
--- /dev/null
+++ b/lucene/core/src/java/org/apache/lucene/codecs/ApproximateDocBinner.java
@@ -0,0 +1,61 @@
+/*
+ * 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.codecs;
+
+import java.io.IOException;
+
+/** Approximate binning for documents using locality-sensitive hashing over sparse edge graph. */
+public final class ApproximateDocBinner {
+
+ private ApproximateDocBinner() {}
+
+ /**
+ * Assign documents to bins approximately based on edge distribution.
+ *
+ * @param graph sparse edge graph
+ * @param maxDoc number of documents
+ * @param numBins number of bins (must be power of 2)
+ * @return bin assignments for each document
+ */
+ public static int[] assign(SparseEdgeGraph graph, int maxDoc, int numBins) throws IOException {
+ if (Integer.bitCount(numBins) != 1) {
+ throw new IllegalArgumentException("numBins must be a power of 2");
+ }
+
+ final int[] bins = new int[maxDoc];
+ final int mask = numBins - 1;
+
+ for (int docID = 0; docID < maxDoc; docID++) {
+ int[] neighbors = graph.getNeighbors(docID);
+ float[] weights = graph.getWeights(docID);
+ int hash = 0;
+ for (int i = 0; i < neighbors.length; i++) {
+ hash = mix(hash, neighbors[i], weights[i]);
+ }
+ bins[docID] = hash & mask;
+ }
+
+ return bins;
+ }
+
+ private static int mix(int h, int neighbor, float weight) {
+ int x = neighbor * 31 + Float.floatToIntBits(weight);
+ h ^= Integer.rotateLeft(x, 13);
+ h *= 0x5bd1e995;
+ return h;
+ }
+}
diff --git a/lucene/core/src/java/org/apache/lucene/codecs/ApproximateDocGraphBuilder.java b/lucene/core/src/java/org/apache/lucene/codecs/ApproximateDocGraphBuilder.java
new file mode 100644
index 00000000000..9ec03df5367
--- /dev/null
+++ b/lucene/core/src/java/org/apache/lucene/codecs/ApproximateDocGraphBuilder.java
@@ -0,0 +1,139 @@
+/*
+ * 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
+ */
+
+package org.apache.lucene.codecs;
+
+import org.apache.lucene.index.LeafReader;
+import org.apache.lucene.index.PostingsEnum;
+import org.apache.lucene.index.Terms;
+import org.apache.lucene.index.TermsEnum;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.util.BytesRef;
+
+import java.io.IOException;
+import java.util.BitSet;
+import java.util.HashMap;
+import java.util.HashSet;
+import java.util.Map;
+import java.util.Set;
+
+/**
+ * Approximates a sparse similarity graph from token co-occurrence without exact vector comparison.
+ */
+public final class ApproximateDocGraphBuilder {
+
+ /** Default number of edges retained per document in the similarity graph. */
+ public static final int DEFAULT_MAX_EDGES = 10;
+
+ private final String field;
+ private final int maxEdgesPerDoc;
+
+ /**
+ * Creates a new graph builder for the specified field.
+ *
+ * @param field the indexed field to use for term overlap computation
+ * @param maxEdgesPerDoc maximum number of outgoing edges to retain per document
+ */
+ public ApproximateDocGraphBuilder(String field, int maxEdgesPerDoc) {
+ this.field = field;
+ this.maxEdgesPerDoc = maxEdgesPerDoc;
+ }
+
+ /**
+ * Constructs the similarity graph for documents in the provided reader using term co-occurrence.
+ *
+ * <p>Documents that share terms in the specified field are connected with an edge, with edge
+ * weights based on normalized overlap count. The number of outgoing edges per document is limited
+ * by {@code maxEdgesPerDoc}.
+ *
+ * @param reader a leaf reader over a single Lucene segment
+ * @return a sparse document similarity graph based on token overlap
+ * @throws IOException if an I/O error occurs during term enumeration or postings access
+ */
+ public SparseEdgeGraph build(LeafReader reader) throws IOException {
+ final int maxDoc = reader.maxDoc();
+ final InMemorySparseEdgeGraph graph = new InMemorySparseEdgeGraph();
+ @SuppressWarnings("unchecked")
+ final Set<String>[] docTokens = (Set<String>[]) new Set<?>[maxDoc];
+ final Map<String, BitSet> tokenBitsets = new HashMap<>();
+
+ Terms terms = reader.terms(field);
+ if (terms == null) {
+ return graph;
+ }
+
+ TermsEnum termsEnum = terms.iterator();
+ BytesRef term;
+ while ((term = termsEnum.next()) != null) {
+ PostingsEnum postings = termsEnum.postings(null, PostingsEnum.NONE);
+ if (postings == null) {
+ continue;
+ }
+
+ final BitSet seen = new BitSet(maxDoc);
+ while (postings.nextDoc() != DocIdSetIterator.NO_MORE_DOCS) {
+ int docID = postings.docID();
+ seen.set(docID);
+ Set<String> tokens = docTokens[docID];
+ if (tokens == null) {
+ tokens = new HashSet<>();
+ docTokens[docID] = tokens;
+ }
+ tokens.add(term.utf8ToString());
+ }
+ tokenBitsets.put(term.utf8ToString(), seen);
+ }
+
+ for (int docA = 0; docA < maxDoc; docA++) {
+ Set<String> tokensA = docTokens[docA];
+ if (tokensA == null || tokensA.isEmpty()) {
+ continue;
+ }
+
+ final BitSet candidates = new BitSet(maxDoc);
+ for (String token : tokensA) {
+ BitSet seen = tokenBitsets.get(token);
+ if (seen != null) {
+ candidates.or(seen);
+ }
+ }
+
+ int added = 0;
+ for (int docB = candidates.nextSetBit(0);
+ docB >= 0 && added < maxEdgesPerDoc;
+ docB = candidates.nextSetBit(docB + 1)) {
+ if (docA == docB) {
+ continue;
+ }
+
+ Set<String> tokensB = docTokens[docB];
+ if (tokensB == null || tokensB.isEmpty()) {
+ continue;
+ }
+
+ int overlap = 0;
+ for (String token : tokensA) {
+ if (tokensB.contains(token)) {
+ overlap++;
+ }
+ }
+
+ if (overlap > 0) {
+ float weight = (float) overlap / Math.max(tokensA.size(), tokensB.size());
+ graph.addEdge(docA, docB, weight);
+ added++;
+ }
+ }
+ }
+
+ return graph;
+ }
+}
diff --git a/lucene/core/src/java/org/apache/lucene/codecs/BinMapReader.java b/lucene/core/src/java/org/apache/lucene/codecs/BinMapReader.java
new file mode 100644
index 00000000000..d98b44ff874
--- /dev/null
+++ b/lucene/core/src/java/org/apache/lucene/codecs/BinMapReader.java
@@ -0,0 +1,110 @@
+/*
+ * 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
+ */
+package org.apache.lucene.codecs;
+
+import org.apache.lucene.index.IndexFileNames;
+import org.apache.lucene.index.SegmentReadState;
+import org.apache.lucene.store.ChecksumIndexInput;
+import org.apache.lucene.store.Directory;
+import org.apache.lucene.util.IOUtils;
+
+import java.io.Closeable;
+import java.io.IOException;
+
+/**
+ * Reads the binmap file for a segment and exposes per-document bin assignments.
+ *
+ * <p>Each document is assigned to a bin during indexing. The binmap file encodes a mapping from
+ * docID to binID and is used at search time to access bin-specific metadata such as scoring boosts.
+ *
+ * <p>This class validates file integrity using Lucene’s codec header/footer checks.
+ */
+public final class BinMapReader implements Closeable {
+
+ private static final String EXTENSION = "binmap";
+ private static final int VERSION_START = 0;
+ private static final String CODEC_NAME = "BinMap";
+
+ private final int[] bins;
+ private final int binCount;
+
+ /**
+ * Loads the binmap file for the given segment.
+ *
+ * @param dir directory containing the segment files
+ * @param state read state for the segment
+ * @throws IOException if the file cannot be read or fails validation
+ */
+ public BinMapReader(Directory dir, SegmentReadState state) throws IOException {
+ final String fileName =
+ IndexFileNames.segmentFileName(state.segmentInfo.name, state.segmentSuffix, EXTENSION);
+
+ ChecksumIndexInput in = null;
+ boolean success = false;
+ try {
+ in = dir.openChecksumInput(fileName);
+ CodecUtil.checkIndexHeader(
+ in,
+ CODEC_NAME,
+ VERSION_START,
+ VERSION_START,
+ state.segmentInfo.getId(),
+ state.segmentSuffix);
+
+ int maxDoc = in.readInt();
+ this.binCount = in.readInt();
+
+ if (maxDoc != state.segmentInfo.maxDoc()) {
+ throw new IOException(
+ "maxDoc mismatch: expected=" + state.segmentInfo.maxDoc() + " actual=" + maxDoc);
+ }
+
+ this.bins = new int[maxDoc];
+ for (int i = 0; i < maxDoc; i++) {
+ bins[i] = in.readInt();
+ }
+
+ CodecUtil.checkFooter(in);
+ success = true;
+ } finally {
+ if (success) {
+ IOUtils.close(in);
+ } else {
+ IOUtils.closeWhileHandlingException(in);
+ }
+ }
+ }
+
+ /**
+ * Returns the bin ID assigned to the given document.
+ *
+ * @param docID document ID
+ * @return the bin ID
+ */
+ public int getBin(int docID) {
+ return bins[docID];
+ }
+
+ /** Returns the total number of bins used in this segment. */
+ public int getBinCount() {
+ return binCount;
+ }
+
+ /** Returns a copy of the full bin assignment array. */
+ public int[] getBinArrayCopy() {
+ int[] copy = new int[bins.length];
+ System.arraycopy(bins, 0, copy, 0, bins.length);
+ return copy;
+ }
+
+ @Override
+ public void close() {}
+}
diff --git a/lucene/core/src/java/org/apache/lucene/codecs/BinMapWriter.java b/lucene/core/src/java/org/apache/lucene/codecs/BinMapWriter.java
new file mode 100644
index 00000000000..ec20137f571
--- /dev/null
+++ b/lucene/core/src/java/org/apache/lucene/codecs/BinMapWriter.java
@@ -0,0 +1,116 @@
+/*
+ * 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.codecs;
+
+import org.apache.lucene.index.IndexFileNames;
+import org.apache.lucene.index.SegmentWriteState;
+import org.apache.lucene.store.Directory;
+import org.apache.lucene.store.IndexOutput;
+import org.apache.lucene.util.IOUtils;
+
+import java.io.IOException;
+
+/**
+ * Writes a binmap file for a segment.
+ *
+ * <p>The binmap assigns each document in the segment to a bin ID, typically used for scoring or
+ * early termination. The output is a binary file storing one integer bin ID per document.
+ */
+public final class BinMapWriter implements AutoCloseable {
+
+ /** File extension for binmap files. */
+ public static final String EXTENSION = "binmap";
+
+ /** Initial file format version. */
+ public static final int VERSION_START = 0;
+
+ private static final String CODEC_NAME = "BinMap";
+
+ private final Directory directory;
+ private final SegmentWriteState state;
+ private final int maxDoc;
+ private final int binCount;
+ private final int[] bins;
+
+ private boolean closed = false;
+
+ /**
+ * Creates a new {@link BinMapWriter} instance.
+ *
+ * @param directory output directory
+ * @param state current segment write state
+ * @param docToBin mapping from docID to bin ID
+ * @param binCount total number of bins
+ */
+ public BinMapWriter(Directory directory, SegmentWriteState state, int[] docToBin, int binCount) {
+ this.directory = directory;
+ this.state = state;
+ this.maxDoc = state.segmentInfo.maxDoc();
+ this.binCount = binCount;
+ this.bins = docToBin;
+ }
+
+ /**
+ * Writes the binmap file to the index output directory.
+ *
+ * <p>The format is:
+ *
+ * <ul>
+ * <li>Header (versioned with {@link CodecUtil})
+ * <li>maxDoc (int)
+ * <li>binCount (int)
+ * <li>{@code maxDoc} bin IDs, one int per document
+ * <li>Footer
+ * </ul>
+ */
+ @Override
+ public void close() throws IOException {
+ final String fileName =
+ IndexFileNames.segmentFileName(state.segmentInfo.name, state.segmentSuffix, EXTENSION);
+
+ if (closed) return;
+ closed = true;
+
+ // Prevent double-write in case close() is called multiple times
+ for (String existing : directory.listAll()) {
+ if (existing.equals(fileName)) {
+ return; // already written
+ }
+ }
+ IndexOutput out = null;
+ boolean success = false;
+ try {
+ out = directory.createOutput(fileName, state.context);
+ CodecUtil.writeIndexHeader(
+ out, CODEC_NAME, VERSION_START, state.segmentInfo.getId(), state.segmentSuffix);
+ out.writeInt(maxDoc);
+ out.writeInt(binCount);
+ for (int i = 0; i < maxDoc; i++) {
+ out.writeInt(bins[i]);
+ }
+ CodecUtil.writeFooter(out);
+ success = true;
+ } finally {
+ if (success) {
+ IOUtils.close(out);
+ } else {
+ IOUtils.closeWhileHandlingException(out);
+ IOUtils.deleteFilesIgnoringExceptions(directory, fileName);
+ }
+ }
+ }
+}
diff --git a/lucene/core/src/java/org/apache/lucene/codecs/BinQualityMetrics.java b/lucene/core/src/java/org/apache/lucene/codecs/BinQualityMetrics.java
new file mode 100644
index 00000000000..42c3c7eb18b
--- /dev/null
+++ b/lucene/core/src/java/org/apache/lucene/codecs/BinQualityMetrics.java
@@ -0,0 +1,51 @@
+/*
+ * 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.codecs;
+
+import java.util.Arrays;
+
+/** Computes bin quality metrics like balance, skewness, and Gini index. */
+public final class BinQualityMetrics {
+
+ private BinQualityMetrics() {}
+
+ /** Computes standard deviation of document counts across bins. */
+ public static double computeStdDev(int[] docCounts) {
+ double mean = Arrays.stream(docCounts).average().orElse(0.0);
+ double variance = 0.0;
+ for (int count : docCounts) {
+ double delta = count - mean;
+ variance += delta * delta;
+ }
+ return Math.sqrt(variance / docCounts.length);
+ }
+
+ /** Computes the Gini index to measure bin inequality. */
+ public static double computeGiniIndex(int[] docCounts) {
+ int n = docCounts.length;
+ if (n == 0) return 0.0;
+ int[] sorted = docCounts.clone();
+ Arrays.sort(sorted);
+ double cumulative = 0.0;
+ for (int i = 0; i < n; i++) {
+ cumulative += (i + 1L) * sorted[i];
+ }
+ double total = Arrays.stream(sorted).sum();
+ if (total == 0.0) return 0.0;
+ return (2.0 * cumulative) / (n * total) - (n + 1.0) / n;
+ }
+}
diff --git a/lucene/core/src/java/org/apache/lucene/codecs/DocBinningGraphBuilder.java b/lucene/core/src/java/org/apache/lucene/codecs/DocBinningGraphBuilder.java
new file mode 100644
index 00000000000..7773f302e99
--- /dev/null
+++ b/lucene/core/src/java/org/apache/lucene/codecs/DocBinningGraphBuilder.java
@@ -0,0 +1,126 @@
+/*
+ * 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.codecs;
+
+import java.io.IOException;
+import java.util.ArrayDeque;
+import java.util.Deque;
+
+/**
+ * Partitions documents into bins using iterative graph bisection.
+ *
+ * <p>This utility approximates a balanced clustering of documents using a sparse similarity graph.
+ * It uses fixed seed points and edge weights to recursively assign documents to bins, ensuring that
+ * similar documents are grouped together.
+ */
+public final class DocBinningGraphBuilder {
+
+ private DocBinningGraphBuilder() {}
+
+ /**
+ * Assigns each document to a bin by performing recursive bisection over a similarity graph.
+ *
+ * @param graph the sparse edge graph of document similarities
+ * @param maxDoc total number of documents
+ * @param numBins number of bins (must be a power of 2)
+ * @return an array mapping docID to bin ID
+ * @throws IOException if an error occurs during graph access
+ */
+ public static int[] computeBins(SparseEdgeGraph graph, int maxDoc, int numBins)
+ throws IOException {
+ if (maxDoc <= 0 || Integer.bitCount(numBins) != 1) {
+ throw new IllegalArgumentException("maxDoc must be > 0 and numBins must be a power of 2");
+ }
+
+ final int[] docToBin = new int[maxDoc];
+ final int[] docIndices = new int[maxDoc];
+ for (int i = 0; i < maxDoc; i++) {
+ docToBin[i] = -1;
+ docIndices[i] = i;
+ }
+
+ final Deque<PartitionTask> queue = new ArrayDeque<>();
+ queue.add(new PartitionTask(0, maxDoc, 0, numBins));
+
+ while (!queue.isEmpty()) {
+ PartitionTask task = queue.removeFirst();
+ final int size = task.end - task.start;
+ if (task.binCount == 1 || size <= 1) {
+ for (int i = task.start; i < task.end; i++) {
+ docToBin[docIndices[i]] = task.binBase;
+ }
+ continue;
+ }
+
+ final int seedA = docIndices[task.start];
+ final int seedB = docIndices[task.end - 1];
+
+ final int[] left = new int[size];
+ final int[] right = new int[size];
+ int leftSize = 0;
+ int rightSize = 0;
+
+ for (int i = 0; i < size; i++) {
+ final int docID = docIndices[task.start + i];
+ final float simA = similarity(graph, docID, seedA);
+ final float simB = similarity(graph, docID, seedB);
+ if (simA >= simB) {
+ left[leftSize++] = docID;
+ } else {
+ right[rightSize++] = docID;
+ }
+ }
+
+ System.arraycopy(left, 0, docIndices, task.start, leftSize);
+ System.arraycopy(right, 0, docIndices, task.start + leftSize, rightSize);
+
+ final int mid = task.start + leftSize;
+ final int nextBin = task.binCount >>> 1;
+
+ queue.add(new PartitionTask(task.start, mid, task.binBase, nextBin));
+ queue.add(new PartitionTask(mid, task.end, task.binBase + nextBin, nextBin));
+ }
+
+ for (int i = 0; i < maxDoc; i++) {
+ if (docToBin[i] == -1) {
+ throw new IllegalStateException("Unassigned docID: " + i);
+ }
+ }
+
+ return docToBin;
+ }
+
+ /**
+ * Computes similarity between two documents using the sparse graph.
+ *
+ * <p>The similarity is computed as the sum of edge weights from docA to docB.
+ */
+ private static float similarity(SparseEdgeGraph graph, int docA, int docB) {
+ int[] neighbors = graph.getNeighbors(docA);
+ float[] weights = graph.getWeights(docA);
+ float score = 0f;
+ for (int i = 0; i < neighbors.length; i++) {
+ if (neighbors[i] == docB) {
+ score += weights[i];
+ }
+ }
+ return score;
+ }
+
+ /** Internal task used to represent a partition step. */
+ private record PartitionTask(int start, int end, int binBase, int binCount) {}
+}
diff --git a/lucene/core/src/java/org/apache/lucene/codecs/DocGraphBuilder.java b/lucene/core/src/java/org/apache/lucene/codecs/DocGraphBuilder.java
new file mode 100644
index 00000000000..f028b67ff50
--- /dev/null
+++ b/lucene/core/src/java/org/apache/lucene/codecs/DocGraphBuilder.java
@@ -0,0 +1,185 @@
+/*
+ * 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.codecs;
+
+import org.apache.lucene.index.LeafReader;
+import org.apache.lucene.index.PostingsEnum;
+import org.apache.lucene.index.Terms;
+import org.apache.lucene.index.TermsEnum;
+import org.apache.lucene.search.DocIdSetIterator;
+import org.apache.lucene.util.BytesRef;
+
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.HashMap;
+import java.util.Map;
+import java.util.PriorityQueue;
+import java.util.Set;
+
+/** Builds a sparse document similarity graph from postings lists. */
+public final class DocGraphBuilder {
+
+ /** Default maximum outgoing edges per document */
+ public static final int DEFAULT_MAX_EDGES = 10;
+
+ private final String field;
+ private final int maxEdgesPerDoc;
+
+ /** Reusable vector store for term frequencies */
+ private final Map<Integer, IntVector> docTermVectors = new HashMap<>();
+
+ /**
+ * Constructs a new graph builder.
+ *
+ * @param field field to use for binning
+ * @param maxEdgesPerDoc number of outgoing edges to retain per document
+ */
+ public DocGraphBuilder(String field, int maxEdgesPerDoc) {
+ this.field = field;
+ this.maxEdgesPerDoc = maxEdgesPerDoc;
+ }
+
+ /** Constructs the sparse similarity graph using term overlap. */
+ public SparseEdgeGraph build(LeafReader reader) throws IOException {
+ final SparseEdgeGraph graph = new InMemorySparseEdgeGraph();
+ final Map<String, ArrayList<Integer>> termToDocList = new HashMap<>();
+
+ Terms terms = reader.terms(field);
+ if (terms == null) {
+ return graph;
+ }
+
+ TermsEnum termsEnum = terms.iterator();
+ BytesRef term;
+ while ((term = termsEnum.next()) != null) {
+ String termStr = term.utf8ToString();
+ PostingsEnum postings = termsEnum.postings(null, PostingsEnum.FREQS);
+ if (postings == null) {
+ continue;
+ }
+ while (postings.nextDoc() != DocIdSetIterator.NO_MORE_DOCS) {
+ int docID = postings.docID();
+ int freq = postings.freq();
+
+ docTermVectors.computeIfAbsent(docID, _ -> new IntVector()).add(termStr, freq);
+ termToDocList.computeIfAbsent(termStr, _ -> new ArrayList<>()).add(docID);
+ }
+ }
+
+ for (Map.Entry<Integer, IntVector> entryA : docTermVectors.entrySet()) {
+ int docA = entryA.getKey();
+ IntVector vecA = entryA.getValue();
+
+ PriorityQueue<Neighbor> topK = new PriorityQueue<>(maxEdgesPerDoc);
+ final Map<Integer, Float> candidates = new HashMap<>();
+
+ for (String termKey : vecA.keys()) {
+ for (int docB : termToDocList.getOrDefault(termKey, new ArrayList<>())) {
+ if (docA == docB) {
+ continue;
+ }
+ candidates.putIfAbsent(docB, 0f);
+ }
+ }
+
+ for (Map.Entry<Integer, Float> candidate : candidates.entrySet()) {
+ int docB = candidate.getKey();
+ IntVector vecB = docTermVectors.get(docB);
+ if (vecB == null) {
+ continue;
+ }
+ float sim = cosine(vecA, vecB);
+ if (sim > 0) {
+ topK.offer(new Neighbor(docB, sim));
+ if (topK.size() > maxEdgesPerDoc) {
+ topK.poll();
+ }
+ }
+ }
+
+ while (!topK.isEmpty()) {
+ Neighbor neighbor = topK.poll();
+ graph.addEdge(docA, neighbor.docID, neighbor.score);
+ }
+ }
+
+ return graph;
+ }
+
+ private static float cosine(IntVector a, IntVector b) {
+ float dot = 0f, normA = 0f, normB = 0f;
+
+ for (Map.Entry<String, Integer> entry : a.entries()) {
+ int tfA = entry.getValue();
+ normA += tfA * tfA;
+ Integer tfB = b.get(entry.getKey());
+ if (tfB != null) {
+ dot += tfA * tfB;
+ }
+ }
+
+ for (int tfB : b.values()) {
+ normB += tfB * tfB;
+ }
+
+ if (normA == 0f || normB == 0f) {
+ return 0f;
+ }
+
+ return dot / (float) (Math.sqrt(normA) * Math.sqrt(normB));
+ }
+
+ private static final class Neighbor implements Comparable<Neighbor> {
+ final int docID;
+ final float score;
+
+ Neighbor(int docID, float score) {
+ this.docID = docID;
+ this.score = score;
+ }
+
+ @Override
+ public int compareTo(Neighbor other) {
+ return Float.compare(this.score, other.score);
+ }
+ }
+
+ /** Lightweight term frequency vector with string keys and int values. */
+ private static final class IntVector {
+ private final Map<String, Integer> tf = new HashMap<>();
+
+ void add(String key, int freq) {
+ tf.merge(key, freq, Integer::sum);
+ }
+
+ Integer get(String key) {
+ return tf.get(key);
+ }
+
+ Set<String> keys() {
+ return tf.keySet();
+ }
+
+ Iterable<Map.Entry<String, Integer>> entries() {
+ return tf.entrySet();
+ }
+
+ Iterable<Integer> values() {
+ return tf.values();
+ }
+ }
+}
diff --git a/lucene/core/src/java/org/apache/lucene/codecs/FieldsLeafReader.java b/lucene/core/src/java/org/apache/lucene/codecs/FieldsLeafReader.java
new file mode 100644
index 00000000000..fd2c9f58c87
--- /dev/null
+++ b/lucene/core/src/java/org/apache/lucene/codecs/FieldsLeafReader.java
@@ -0,0 +1,172 @@
+/*
+ * 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.codecs;
+
+import org.apache.lucene.index.BinaryDocValues;
+import org.apache.lucene.index.ByteVectorValues;
+import org.apache.lucene.index.DocValuesSkipper;
+import org.apache.lucene.index.FieldInfos;
+import org.apache.lucene.index.FloatVectorValues;
+import org.apache.lucene.index.LeafMetaData;
+import org.apache.lucene.index.LeafReader;
+import org.apache.lucene.index.NumericDocValues;
+import org.apache.lucene.index.PointValues;
+import org.apache.lucene.index.SortedDocValues;
+import org.apache.lucene.index.SortedNumericDocValues;
+import org.apache.lucene.index.SortedSetDocValues;
+import org.apache.lucene.index.StoredFields;
+import org.apache.lucene.index.TermVectors;
+import org.apache.lucene.index.Terms;
+import org.apache.lucene.search.KnnCollector;
+import org.apache.lucene.util.Bits;
+import org.apache.lucene.util.Version;
+
+import java.io.IOException;
+import java.util.Map;
+
+/** Minimal LeafReader exposing term statistics for one or more fields. */
+public final class FieldsLeafReader extends LeafReader {
+
+ private final Map<String, Terms> fieldTerms;
+ private final int maxDoc;
+
+ /**
+ * Creates a {@code FieldsLeafReader} for the given field terms.
+ *
+ * @param fieldTerms mapping of field names to {@link Terms} enumerations
+ * @param maxDoc total number of documents in this reader
+ */
+ public FieldsLeafReader(Map<String, Terms> fieldTerms, int maxDoc) {
+ this.fieldTerms = fieldTerms;
+ this.maxDoc = maxDoc;
+ }
+
+ @Override
+ public CacheHelper getCoreCacheHelper() {
+ return null;
+ }
+
+ @Override
+ public Terms terms(String field) throws IOException {
+ return fieldTerms.get(field);
+ }
+
+ @Override
+ public int maxDoc() {
+ return maxDoc;
+ }
+
+ @Override
+ public StoredFields storedFields() throws IOException {
+ return null;
+ }
+
+ @Override
+ public TermVectors termVectors() throws IOException {
+ return null;
+ }
+
+ @Override
+ public int numDocs() {
+ return maxDoc;
+ }
+
+ @Override
+ public Bits getLiveDocs() {
+ return null;
+ }
+
+ @Override
+ public FieldInfos getFieldInfos() {
+ throw new UnsupportedOperationException("field infos not supported");
+ }
+
+ @Override
+ public NumericDocValues getNumericDocValues(String field) {
+ return null;
+ }
+
+ @Override
+ public BinaryDocValues getBinaryDocValues(String field) throws IOException {
+ return null;
+ }
+
+ @Override
+ public SortedNumericDocValues getSortedNumericDocValues(String field) {
+ return null;
+ }
+
+ @Override
+ public SortedDocValues getSortedDocValues(String field) {
+ return null;
+ }
+
+ @Override
+ public SortedSetDocValues getSortedSetDocValues(String field) {
+ return null;
+ }
+
+ @Override
+ public NumericDocValues getNormValues(String field) throws IOException {
+ return null;
+ }
+
+ @Override
+ public DocValuesSkipper getDocValuesSkipper(String field) throws IOException {
+ return null;
+ }
+
+ @Override
+ public FloatVectorValues getFloatVectorValues(String field) throws IOException {
+ return null;
+ }
+
+ @Override
+ public ByteVectorValues getByteVectorValues(String field) throws IOException {
+ return null;
+ }
+
+ @Override
+ public void searchNearestVectors(
+ String field, float[] target, KnnCollector knnCollector, Bits acceptDocs)
+ throws IOException {}
+
+ @Override
+ public void searchNearestVectors(
+ String field, byte[] target, KnnCollector knnCollector, Bits acceptDocs) throws IOException {}
+
+ @Override
+ public PointValues getPointValues(String field) {
+ return null;
+ }
+
+ @Override
+ public LeafMetaData getMetaData() {
+ return new LeafMetaData(Version.LATEST.major, Version.LATEST, null, false);
+ }
+
+ @Override
+ public void checkIntegrity() {}
+
+ @Override
+ protected void doClose() {}
+
+ @Override
+ public CacheHelper getReaderCacheHelper() {
+ return null;
+ }
+}
diff --git a/lucene/core/src/java/org/apache/lucene/codecs/InMemorySparseEdgeGraph.java b/lucene/core/src/java/org/apache/lucene/codecs/InMemorySparseEdgeGraph.java
new file mode 100644
index 00000000000..f0a26a67682
--- /dev/null
+++ b/lucene/core/src/java/org/apache/lucene/codecs/InMemorySparseEdgeGraph.java
@@ -0,0 +1,79 @@
+/*
+ * 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.codecs;
+
+import java.util.HashMap;
+import java.util.Map;
+
+/**
+ * Simple in-memory implementation of {@link SparseEdgeGraph}. Intended for unit testing and
+ * non-production use.
+ */
+public final class InMemorySparseEdgeGraph implements SparseEdgeGraph {
+
+ private final Map<Integer, int[]> neighbors = new HashMap<>();
+ private final Map<Integer, float[]> weights = new HashMap<>();
+
+ private void addDirectedEdge(int from, int to, float weight) {
+ int[] existingNeighbors = neighbors.get(from);
+ float[] existingWeights = weights.get(from);
+
+ int len = existingNeighbors == null ? 0 : existingNeighbors.length;
+ int[] newNeighbors = new int[len + 1];
+ float[] newWeights = new float[len + 1];
+
+ if (len > 0) {
+ System.arraycopy(existingNeighbors, 0, newNeighbors, 0, len);
+ System.arraycopy(existingWeights, 0, newWeights, 0, len);
+ }
+
+ newNeighbors[len] = to;
+ newWeights[len] = weight;
+
+ neighbors.put(from, newNeighbors);
+ weights.put(from, newWeights);
+ }
+
+ /** Adds a symmetric edge between two documents with the given weight. */
+ @Override
+ public void addEdge(int docA, int docB, float weight) {
+ addDirectedEdge(docA, docB, weight);
+ addDirectedEdge(docB, docA, weight);
+ }
+
+ @Override
+ public int[] getNeighbors(int docID) {
+ return neighbors.getOrDefault(docID, new int[0]);
+ }
+
+ @Override
+ public float[] getWeights(int docID) {
+ return weights.getOrDefault(docID, new float[0]);
+ }
+
+ @Override
+ public void ensureVertex(int docID) {
+ neighbors.computeIfAbsent(docID, _ -> new int[0]);
+ weights.computeIfAbsent(docID, _ -> new float[0]);
+ }
+
+ /** Returns the number of vertices in the graph with at least one edge. */
+ @Override
+ public int size() {
+ return neighbors.size();
+ }
+}
diff --git a/lucene/core/src/java/org/apache/lucene/codecs/SparseEdgeGraph.java b/lucene/core/src/java/org/apache/lucene/codecs/SparseEdgeGraph.java
new file mode 100644
index 00000000000..59f2d71730e
--- /dev/null
+++ b/lucene/core/src/java/org/apache/lucene/codecs/SparseEdgeGraph.java
@@ -0,0 +1,52 @@
+/*
+ * 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
+ */
+package org.apache.lucene.codecs;
+
+/**
+ * Interface for a sparse directed graph of documents. Used to represent approximate similarity
+ * relationships between documents.
+ */
+public interface SparseEdgeGraph {
+ /**
+ * Adds a directed edge from {@code fromDocID} to {@code toDocID} with the given weight.
+ *
+ * @param fromDocID source document ID
+ * @param toDocID destination document ID
+ * @param weight edge weight representing similarity
+ */
+ void addEdge(int fromDocID, int toDocID, float weight);
+
+ /**
+ * Returns the list of neighboring document IDs for a given source document.
+ *
+ * @param docID source document ID
+ * @return array of neighboring document IDs
+ */
+ int[] getNeighbors(int docID);
+
+ /**
+ * Returns the edge weights associated with the neighbors of the given document.
+ *
+ * @param docID source document ID
+ * @return array of weights corresponding to {@link #getNeighbors(int)}
+ */
+ float[] getWeights(int docID);
+
+ /** Returns the number of vertices in the graph. */
+ int size();
+
+ /**
+ * Ensures internal data structures can accommodate the given document ID.
+ *
+ * @param docID document ID to reserve space for
+ */
+ void ensureVertex(int docID);
+}
diff --git a/lucene/core/src/java/org/apache/lucene/codecs/lucene103/Lucene103PostingsFormat.java b/lucene/core/src/java/org/apache/lucene/codecs/lucene103/Lucene103PostingsFormat.java
index 3c489f9d3ca..b463ddc062e 100644
--- a/lucene/core/src/java/org/apache/lucene/codecs/lucene103/Lucene103PostingsFormat.java
+++ b/lucene/core/src/java/org/apache/lucene/codecs/lucene103/Lucene103PostingsFormat.java
@@ -17,20 +17,34 @@
package org.apache.lucene.codecs.lucene103;
import java.io.IOException;
+
+import org.apache.lucene.codecs.ApproximateDocBinner;
+import org.apache.lucene.codecs.ApproximateDocGraphBuilder;
+import org.apache.lucene.codecs.BinMapWriter;
import org.apache.lucene.codecs.BlockTermState;
import org.apache.lucene.codecs.CodecUtil;
+import org.apache.lucene.codecs.DocBinningGraphBuilder;
+import org.apache.lucene.codecs.DocGraphBuilder;
import org.apache.lucene.codecs.FieldsConsumer;
+import org.apache.lucene.codecs.FieldsLeafReader;
import org.apache.lucene.codecs.FieldsProducer;
+import org.apache.lucene.codecs.NormsProducer;
import org.apache.lucene.codecs.PostingsFormat;
import org.apache.lucene.codecs.PostingsReaderBase;
import org.apache.lucene.codecs.PostingsWriterBase;
+import org.apache.lucene.codecs.SparseEdgeGraph;
import org.apache.lucene.codecs.lucene103.blocktree.Lucene103BlockTreeTermsReader;
import org.apache.lucene.codecs.lucene103.blocktree.Lucene103BlockTreeTermsWriter;
+import org.apache.lucene.index.FieldInfo;
+import org.apache.lucene.index.FieldInfos;
+import org.apache.lucene.index.Fields;
import org.apache.lucene.index.ImpactsEnum;
import org.apache.lucene.index.IndexOptions;
+import org.apache.lucene.index.LeafReader;
import org.apache.lucene.index.SegmentReadState;
import org.apache.lucene.index.SegmentWriteState;
import org.apache.lucene.index.TermState;
+import org.apache.lucene.index.Terms;
import org.apache.lucene.store.DataOutput;
import org.apache.lucene.util.IOUtils;
import org.apache.lucene.util.packed.PackedInts;
@@ -369,6 +383,7 @@ public final class Lucene103PostingsFormat extends PostingsFormat {
static final String PAY_CODEC = "Lucene103PostingsWriterPay";
static final int VERSION_START = 0;
+ private static final int MAX_DOC_FOR_EXACT_BINNING = 10;
static final int VERSION_CURRENT = VERSION_START;
@@ -406,6 +421,92 @@ public final class Lucene103PostingsFormat extends PostingsFormat {
this.maxTermBlockSize = maxTermBlockSize;
}
+ static void maybeWriteDocBinning(SegmentWriteState state) throws IOException {
+ final int maxDoc = state.segmentInfo.maxDoc();
+ if (maxDoc == 0) {
+ return;
+ }
+
+ final FieldInfos fieldInfos = state.fieldInfos;
+ String binningField = null;
+ String graphBuilderType = null;
+ int binCount = -1;
+
+ for (FieldInfo fi : fieldInfos) {
+ if ("true".equalsIgnoreCase(fi.getAttribute("doBinning"))) {
+ binningField = fi.name;
+ String binCountAttr = fi.getAttribute("bin.count");
+ binCount =
+ (binCountAttr != null)
+ ? Integer.parseInt(binCountAttr)
+ : Math.max(1, Integer.highestOneBit(maxDoc >>> 4));
+ String graphBuilderAttr = fi.getAttribute("bin.builder");
+ graphBuilderType = (graphBuilderAttr != null) ? graphBuilderAttr : "auto";
+ break;
+ }
+ }
+
+ if (binningField == null || binCount <= 0) {
+ return;
+ }
+
+ final PostingsFormat format = new Lucene103PostingsFormat();
+ try (FieldsProducer fields =
+ format.fieldsProducer(
+ new SegmentReadState(
+ state.directory,
+ state.segmentInfo,
+ state.fieldInfos,
+ state.context,
+ state.segmentSuffix))) {
+
+ Terms terms = fields.terms(binningField);
+ if (terms == null) {
+ return;
+ }
+
+ try (LeafReader reader =
+ new FieldsLeafReader(java.util.Collections.singletonMap(binningField, terms), maxDoc)) {
+
+ final int[] docToBin;
+
+ final SparseEdgeGraph graph;
+
+ if ("approx".equalsIgnoreCase(graphBuilderType)) {
+ ApproximateDocGraphBuilder builder =
+ new ApproximateDocGraphBuilder(
+ binningField, ApproximateDocGraphBuilder.DEFAULT_MAX_EDGES);
+ graph = builder.build(reader);
+ docToBin = ApproximateDocBinner.assign(graph, maxDoc, binCount);
+ } else if ("exact".equalsIgnoreCase(graphBuilderType)) {
+ DocGraphBuilder builder =
+ new DocGraphBuilder(binningField, DocGraphBuilder.DEFAULT_MAX_EDGES);
+ graph = builder.build(reader);
+ docToBin = DocBinningGraphBuilder.computeBins(graph, maxDoc, binCount);
+ } else {
+ // default: auto fallback based on doc count
+ if (maxDoc > MAX_DOC_FOR_EXACT_BINNING) {
+ ApproximateDocGraphBuilder builder =
+ new ApproximateDocGraphBuilder(
+ binningField, ApproximateDocGraphBuilder.DEFAULT_MAX_EDGES);
+ graph = builder.build(reader);
+ docToBin = ApproximateDocBinner.assign(graph, maxDoc, binCount);
+ } else {
+ DocGraphBuilder builder =
+ new DocGraphBuilder(binningField, DocGraphBuilder.DEFAULT_MAX_EDGES);
+ graph = builder.build(reader);
+ docToBin = DocBinningGraphBuilder.computeBins(graph, maxDoc, binCount);
+ }
+ }
+
+ try (BinMapWriter writer = new BinMapWriter(state.directory, state, docToBin, binCount)) {
+ // Trigger side-effect and keep compiler happy
+ assert writer != null;
+ }
+ }
+ }
+ }
+
@Override
public FieldsConsumer fieldsConsumer(SegmentWriteState state) throws IOException {
PostingsWriterBase postingsWriter = new Lucene103PostingsWriter(state, version);
@@ -415,7 +516,42 @@ public final class Lucene103PostingsFormat extends PostingsFormat {
new Lucene103BlockTreeTermsWriter(
state, postingsWriter, minTermBlockSize, maxTermBlockSize);
success = true;
- return ret;
+
+ return new FieldsConsumer() {
+ @Override
+ public void write(Fields fields, NormsProducer normsProducer) throws IOException {
+ ret.write(fields, normsProducer);
+ }
+
+ @Override
+ public void close() throws IOException {
+ IOException prior = null;
+ try {
+ ret.close();
+ } catch (IOException e) {
+ prior = e;
+ }
+
+ /*try {
+ if (prior == null) {
+ // Now that all outputs are flushed, perform binning safely
+ maybeWriteDocBinning(state);
+ }
+ } catch (IOException e) {
+ if (prior != null) {
+ prior.addSuppressed(e);
+ throw prior;
+ } else {
+ throw e;
+ }
+ }*/
+
+ if (prior != null) {
+ throw prior;
+ }
+ }
+ };
+ //return ret;
} finally {
if (!success) {
IOUtils.closeWhileHandlingException(postingsWriter);
diff --git a/lucene/core/src/java/org/apache/lucene/index/BinScoreLeafReader.java b/lucene/core/src/java/org/apache/lucene/index/BinScoreLeafReader.java
new file mode 100644
index 00000000000..a562a88ae4a
--- /dev/null
+++ b/lucene/core/src/java/org/apache/lucene/index/BinScoreLeafReader.java
@@ -0,0 +1,56 @@
+/*
+ * 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.util.IOUtils;
+
+import java.io.Closeable;
+import java.io.IOException;
+
+/** Reader wrapper that exposes bin-aware scoring. */
+public class BinScoreLeafReader extends FilterLeafReader {
+
+ private final BinScoreReader binScore;
+ private final Closeable[] resources;
+
+ /** Default constructor */
+ public BinScoreLeafReader(LeafReader in, BinScoreReader binScore, Closeable... resources) {
+ super(in);
+ this.binScore = binScore;
+ this.resources = resources;
+ }
+
+ /** Returns the bin score reader. */
+ public BinScoreReader getBinScoreReader() {
+ return binScore;
+ }
+
+ @Override
+ protected void doClose() throws IOException {
+ IOUtils.close(resources);
+ }
+
+ @Override
+ public CacheHelper getReaderCacheHelper() {
+ return in.getReaderCacheHelper();
+ }
+
+ @Override
+ public CacheHelper getCoreCacheHelper() {
+ return in.getCoreCacheHelper();
+ }
+}
diff --git a/lucene/core/src/java/org/apache/lucene/index/BinScoreReader.java b/lucene/core/src/java/org/apache/lucene/index/BinScoreReader.java
new file mode 100644
index 00000000000..60a55cf7935
--- /dev/null
+++ b/lucene/core/src/java/org/apache/lucene/index/BinScoreReader.java
@@ -0,0 +1,53 @@
+/*
+ * 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.BinMapReader;
+
+import java.io.IOException;
+import java.util.Objects;
+
+/**
+ * Provides per-document bin assignments for scoring adjustments.
+ *
+ * @lucene.experimental
+ */
+public final class BinScoreReader {
+
+ private final BinMapReader binMap;
+
+ /** Creates a new {@link BinScoreReader} from a {@link BinMapReader}. */
+ public BinScoreReader(BinMapReader binMap) {
+ this.binMap = Objects.requireNonNull(binMap, "binMap must not be null");
+ }
+
+ /**
+ * Returns the bin ID for the specified document.
+ *
+ * @param docID doc ID within the segment
+ * @return assigned bin ID
+ * @throws IOException if bin lookup fails
+ */
+ public int getBinForDoc(int docID) throws IOException {
+ return binMap.getBin(docID);
+ }
+
+ /** Returns the total number of bins in this segment. */
+ public int getBinCount() {
+ return binMap.getBinCount();
+ }
+}
diff --git a/lucene/core/src/java/org/apache/lucene/index/BinScoreUtil.java b/lucene/core/src/java/org/apache/lucene/index/BinScoreUtil.java
new file mode 100644
index 00000000000..cd095165565
--- /dev/null
+++ b/lucene/core/src/java/org/apache/lucene/index/BinScoreUtil.java
@@ -0,0 +1,134 @@
+/*
+ * 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.BinMapReader;
+import org.apache.lucene.store.Directory;
+import org.apache.lucene.store.IOContext;
+import org.apache.lucene.util.IOUtils;
+
+import java.io.Closeable;
+import java.io.IOException;
+import java.util.ArrayList;
+import java.util.List;
+
+/** Utilities for wrapping readers with binning support. */
+public final class BinScoreUtil {
+
+ private BinScoreUtil() {}
+
+ /** Wrap an IndexReader with bin support. */
+ public static IndexReader wrap(IndexReader reader) throws IOException {
+ if (reader instanceof LeafReader) {
+ return wrap((LeafReader) reader);
+ }
+ if (reader instanceof CompositeReader) {
+ return wrapComposite((CompositeReader) reader);
+ }
+ return reader;
+ }
+
+ private static CompositeReader wrapComposite(CompositeReader reader) throws IOException {
+ List<LeafReader> wrapped = new ArrayList<>();
+ for (LeafReaderContext ctx : reader.leaves()) {
+ wrapped.add(wrap(ctx.reader()));
+ }
+ // This MultiReader just wraps the readers — responsibility for cleanup is delegated to
+ // individual leaves.
+ return new MultiReader(wrapped.toArray(new LeafReader[0]), true);
+ }
+
+ /** Wrap a LeafReader with bin score logic if binmap file is found. */
+ public static LeafReader wrap(LeafReader reader) throws IOException {
+ SegmentReader sr = getSegmentReader(reader);
+ if (sr == null) {
+ return reader;
+ }
+
+ SegmentCommitInfo commitInfo = sr.getSegmentInfo();
+ SegmentInfo info = commitInfo.info;
+ Directory dir = sr.directory();
+ Closeable compoundReader = null;
+
+ if (info.getUseCompoundFile()) {
+ var format = info.getCodec().compoundFormat();
+ if (format != null) {
+ compoundReader = format.getCompoundReader(dir, info);
+ dir = (Directory) compoundReader;
+ }
+ }
+
+ String name = info.name;
+ String binmapFile = findBinmapFile(dir, name);
+ if (binmapFile == null) {
+ IOUtils.closeWhileHandlingException(compoundReader);
+ return reader;
+ }
+
+ String suffix =
+ binmapFile.substring(name.length() + 1, binmapFile.length() - ".binmap".length());
+ SegmentReadState state =
+ new SegmentReadState(dir, info, sr.getFieldInfos(), IOContext.READONCE, suffix);
+
+ BinMapReader binMap = null;
+ try {
+ binMap = new BinMapReader(dir, state);
+ BinScoreReader binScore = new BinScoreReader(binMap);
+
+ final Closeable closeOnClose = compoundReader;
+ return new BinScoreLeafReader(reader, binScore, binMap) {
+ @Override
+ protected void doClose() throws IOException {
+ IOUtils.close(closeOnClose); // closes compoundReader if present
+ super.doClose(); // closes binMap, etc.
+ }
+ };
+ } catch (Throwable t) {
+ IOUtils.closeWhileHandlingException(binMap, compoundReader);
+ throw t;
+ }
+ }
+
+ private static SegmentReader getSegmentReader(LeafReader reader) {
+ if (reader instanceof SegmentReader) {
+ return (SegmentReader) reader;
+ }
+ LeafReader unwrapped = FilterLeafReader.unwrap(reader);
+ return (unwrapped instanceof SegmentReader) ? (SegmentReader) unwrapped : null;
+ }
+
+ private static String findBinmapFile(Directory dir, String segmentName) throws IOException {
+ for (String file : dir.listAll()) {
+ if (file.startsWith(segmentName + "_") && file.endsWith(".binmap")) {
+ return file;
+ }
+ }
+ return null;
+ }
+
+ /** Return bin score reader if available. */
+ public static BinScoreReader getBinScoreReader(LeafReader reader) {
+ if (reader instanceof BinScoreLeafReader) {
+ return ((BinScoreLeafReader) reader).getBinScoreReader();
+ }
+ LeafReader unwrapped = FilterLeafReader.unwrap(reader);
+ if (unwrapped instanceof BinScoreLeafReader) {
+ return ((BinScoreLeafReader) unwrapped).getBinScoreReader();
+ }
+ return null;
+ }
+}
diff --git a/lucene/core/src/java/org/apache/lucene/search/AnytimeRankingCollector.java b/lucene/core/src/java/org/apache/lucene/search/AnytimeRankingCollector.java
new file mode 100644
index 00000000000..a1f614ec50f
--- /dev/null
+++ b/lucene/core/src/java/org/apache/lucene/search/AnytimeRankingCollector.java
@@ -0,0 +1,109 @@
+/*
+ * 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.search;
+
+import org.apache.lucene.index.BinScoreLeafReader;
+import org.apache.lucene.index.BinScoreReader;
+import org.apache.lucene.index.LeafReader;
+import org.apache.lucene.index.LeafReaderContext;
+
+import java.io.IOException;
+
+/** SLA-aware collector that boosts score based on bin distribution. */
+public final class AnytimeRankingCollector extends TopDocsCollector<ScoreDoc> {
+
+ private static final int DOCS_PER_CHECK = 100;
+ private static final int MIN_CHECK_INTERVAL = 32;
+ private static final int MAX_CHECK_INTERVAL = 512;
+
+ private final long cutoffNanos;
+ private final long start;
+ private final float[] binBoosts;
+
+ private int count = 0;
+
+ AnytimeRankingCollector(int topK, long cutoffNanos, float[] binBoosts) {
+ super(new HitQueue(topK, false));
+ this.cutoffNanos = cutoffNanos;
+ this.start = System.nanoTime();
+ this.binBoosts = binBoosts;
+ }
+
+ @Override
+ protected int topDocsSize() {
+ return pq.size();
+ }
+
+ @Override
+ protected TopDocs newTopDocs(ScoreDoc[] results, int start) {
+ return new TopDocs(
+ new TotalHits(totalHits, TotalHits.Relation.GREATER_THAN_OR_EQUAL_TO),
+ results != null ? results : EMPTY_TOPDOCS.scoreDocs);
+ }
+
+ @Override
+ public LeafCollector getLeafCollector(LeafReaderContext ctx) throws IOException {
+ final int base = ctx.docBase;
+ final LeafReader reader = ctx.reader();
+ final BinScoreReader binReader =
+ reader instanceof BinScoreLeafReader
+ ? ((BinScoreLeafReader) reader).getBinScoreReader()
+ : null;
+
+ int interval =
+ Math.max(
+ MIN_CHECK_INTERVAL, Math.min(MAX_CHECK_INTERVAL, reader.numDocs() / DOCS_PER_CHECK));
+
+ return new LeafCollector() {
+ private Scorable scorer;
+
+ @Override
+ public void setScorer(Scorable scorer) {
+ this.scorer = scorer;
+ }
+
+ @Override
+ public void collect(int doc) throws IOException {
+ float score = scorer.score();
+ if (score <= 0 || Float.isNaN(score)) {
+ return;
+ }
+
+ int globalDoc = doc + base;
+ if (binReader != null && binBoosts != null) {
+ int bin = binReader.getBinForDoc(doc);
+ if (bin >= 0 && bin < binBoosts.length) {
+ score *= binBoosts[bin];
+ }
+ }
+
+ if (pq.insertWithOverflow(new ScoreDoc(globalDoc, score)) != null) {
+ totalHits++;
+ }
+
+ if (++count % interval == 0 && System.nanoTime() - start > cutoffNanos) {
+ throw new CollectionTerminatedException();
+ }
+ }
+ };
+ }
+
+ @Override
+ public ScoreMode scoreMode() {
+ return ScoreMode.TOP_SCORES;
+ }
+}
diff --git a/lucene/core/src/java/org/apache/lucene/search/AnytimeRankingCollectorManager.java b/lucene/core/src/java/org/apache/lucene/search/AnytimeRankingCollectorManager.java
new file mode 100644
index 00000000000..c30dcde6d7a
--- /dev/null
+++ b/lucene/core/src/java/org/apache/lucene/search/AnytimeRankingCollectorManager.java
@@ -0,0 +1,69 @@
+/*
+ * 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.search;
+
+import org.apache.lucene.index.IndexReader;
+
+import java.io.IOException;
+import java.util.Collection;
+import java.util.PriorityQueue;
+
+/** CollectorManager that provides bin-aware SLA-constrained collectors. */
+public final class AnytimeRankingCollectorManager
+ implements CollectorManager<AnytimeRankingCollector, TopDocs> {
+
+ private final int topK;
+ private final long slaCutoffNanos;
+ private final float[] binBoosts;
+
+ public AnytimeRankingCollectorManager(int topK, long slaCutoffNanos, IndexReader reader)
+ throws IOException {
+ this.topK = topK;
+ this.slaCutoffNanos = slaCutoffNanos;
+ this.binBoosts = BinBoostCalculator.compute(reader);
+ }
+
+ @Override
+ public AnytimeRankingCollector newCollector() {
+ return new AnytimeRankingCollector(topK, slaCutoffNanos, binBoosts);
+ }
+
+ @Override
+ public TopDocs reduce(Collection<AnytimeRankingCollector> collectors) throws IOException {
+ PriorityQueue<ScoreDoc> queue =
+ new PriorityQueue<>(topK, (a, b) -> Float.compare(a.score, b.score));
+ long totalHits = 0;
+
+ for (AnytimeRankingCollector collector : collectors) {
+ TopDocs shard = collector.topDocs();
+ totalHits += shard.totalHits.value();
+ for (ScoreDoc sd : shard.scoreDocs) {
+ if (queue.size() < topK) {
+ queue.offer(sd);
+ } else if (sd.score > queue.peek().score) {
+ queue.poll();
+ queue.offer(sd);
+ }
+ }
+ }
+
+ ScoreDoc[] results = queue.toArray(new ScoreDoc[0]);
+ java.util.Arrays.sort(results, (a, b) -> Float.compare(b.score, a.score));
+ return new TopDocs(
+ new TotalHits(totalHits, TotalHits.Relation.GREATER_THAN_OR_EQUAL_TO), results);
+ }
+}
diff --git a/lucene/core/src/java/org/apache/lucene/search/AnytimeRankingSearcher.java b/lucene/core/src/java/org/apache/lucene/search/AnytimeRankingSearcher.java
new file mode 100644
index 00000000000..981275ed6a5
--- /dev/null
+++ b/lucene/core/src/java/org/apache/lucene/search/AnytimeRankingSearcher.java
@@ -0,0 +1,52 @@
+/*
+ * 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.search;
+
+import org.apache.lucene.util.HeuristicSLAEstimator;
+import org.apache.lucene.util.SLAEstimator;
+
+import java.io.IOException;
+
+/** SLA-aware searcher that applies bin-aware boosting and early termination. */
+public final class AnytimeRankingSearcher {
+
+ private final IndexSearcher searcher;
+ private final int topK;
+ private final long baseSlaMs;
+ private final SLAEstimator estimator;
+
+ /** Constructs a searcher with SLA cutoff and bin boosting. */
+ public AnytimeRankingSearcher(IndexSearcher searcher, int topK, long baseSlaMs, String field) {
+ this.searcher = searcher;
+ this.topK = topK;
+ this.baseSlaMs = baseSlaMs;
+ this.estimator = new HeuristicSLAEstimator(field);
+ }
+
+ /** Executes a search with bin-aware scoring and SLA cutoff. */
+ public TopDocs search(Query query) throws IOException {
+ long estimated = (long) estimator.estimate(query, searcher.getIndexReader(), baseSlaMs);
+ AnytimeRankingCollectorManager manager =
+ new AnytimeRankingCollectorManager(topK, estimated, searcher.getIndexReader());
+ return searcher.search(query, manager);
+ }
+
+ /** Returns the wrapped IndexSearcher. */
+ public IndexSearcher getSearcher() {
+ return searcher;
+ }
+}
diff --git a/lucene/core/src/java/org/apache/lucene/search/BinBoostCalculator.java b/lucene/core/src/java/org/apache/lucene/search/BinBoostCalculator.java
new file mode 100644
index 00000000000..50fb399d322
--- /dev/null
+++ b/lucene/core/src/java/org/apache/lucene/search/BinBoostCalculator.java
@@ -0,0 +1,95 @@
+/*
+ * 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.search;
+
+import org.apache.lucene.index.BinScoreLeafReader;
+import org.apache.lucene.index.BinScoreReader;
+import org.apache.lucene.index.IndexReader;
+import org.apache.lucene.index.LeafReader;
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.util.ArrayUtil;
+
+import java.io.IOException;
+
+/** Computes per-bin score boosts using inverse frequency heuristics. */
+final class BinBoostCalculator {
+
+ private BinBoostCalculator() {}
+
+ /** Computes bin-level boosts using inverse frequency weighting with log scaling. */
+ static float[] compute(IndexReader reader) throws IOException {
+ int[] binCounts = new int[8]; // start small, grow as needed
+ int totalDocs = 0;
+ int maxBin = -1;
+
+ for (LeafReaderContext ctx : reader.leaves()) {
+ LeafReader leaf = ctx.reader();
+ BinScoreReader binReader =
+ (leaf instanceof BinScoreLeafReader)
+ ? ((BinScoreLeafReader) leaf).getBinScoreReader()
+ : null;
+ if (binReader == null) {
+ continue;
+ }
+
+ for (int docID = 0; docID < leaf.maxDoc(); docID++) {
+ int bin = binReader.getBinForDoc(docID);
+ if (bin >= binCounts.length) {
+ int newLength = Math.max(bin + 1, binCounts.length * 2);
+ binCounts = ArrayUtil.growExact(binCounts, newLength);
+ }
+ binCounts[bin]++;
+ totalDocs++;
+ maxBin = Math.max(maxBin, bin);
+ }
+ }
+
+ if (totalDocs == 0 || maxBin < 0) {
+ return new float[0];
+ }
+
+ float[] boosts = new float[maxBin + 1];
+ float maxBoost = 0f;
+
+ for (int bin = 0; bin <= maxBin; bin++) {
+ int count = binCounts[bin];
+ if (count == 0) {
+ boosts[bin] = 0f;
+ continue;
+ }
+
+ // Boost is proportional to inverse frequency
+ float freq = (float) count / totalDocs;
+ float boost = (float) Math.log((1.0f + 1.0f / freq)); // avoid log(0)
+ boosts[bin] = boost;
+ maxBoost = Math.max(maxBoost, boost);
+ }
+
+ // Normalize boosts to the range [1.0, max], where 1.0 is neutral
+ if (maxBoost > 0f) {
+ for (int i = 0; i < boosts.length; i++) {
+ if (boosts[i] == 0f) {
+ continue;
+ }
+ // Scale so the most underrepresented bin gets higher score
+ boosts[i] = 1.0f + (boosts[i] / maxBoost); // final boost ∈ [1.0, 2.0]
+ }
+ }
+
+ return boosts;
+ }
+}
diff --git a/lucene/core/src/java/org/apache/lucene/util/HeuristicSLAEstimator.java b/lucene/core/src/java/org/apache/lucene/util/HeuristicSLAEstimator.java
new file mode 100644
index 00000000000..27b1c1a9968
--- /dev/null
+++ b/lucene/core/src/java/org/apache/lucene/util/HeuristicSLAEstimator.java
@@ -0,0 +1,205 @@
+/*
+ * 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.util;
+
+import org.apache.lucene.index.IndexReader;
+import org.apache.lucene.index.LeafReaderContext;
+import org.apache.lucene.index.Terms;
+import org.apache.lucene.index.TermsEnum;
+import org.apache.lucene.search.BooleanClause;
+import org.apache.lucene.search.BooleanQuery;
+import org.apache.lucene.search.BoostQuery;
+import org.apache.lucene.search.ConstantScoreQuery;
+import org.apache.lucene.search.DisjunctionMaxQuery;
+import org.apache.lucene.search.MatchAllDocsQuery;
+import org.apache.lucene.search.MultiTermQuery;
+import org.apache.lucene.search.PhraseQuery;
+import org.apache.lucene.search.Query;
+import org.apache.lucene.search.SynonymQuery;
+import org.apache.lucene.search.TermQuery;
+
+import java.io.IOException;
+
+/**
+ * Estimate SLA based the number of query terms, query complexity, and average document frequency
+ */
+public class HeuristicSLAEstimator implements SLAEstimator {
+
+ private static final int MAX_SAMPLE_TERMS = 64;
+ private static final double MAX_MULT = 3.0;
+ private static final double TERM_COST = 0.2;
+ private static final double FREQ_COST = 0.0015;
+ private static final double QUERY_COMPLEXITY = 0.15;
+
+ private final String field;
+
+ public HeuristicSLAEstimator(String field) {
+ this.field = field;
+ }
+
+ @Override
+ public double estimate(Query query, IndexReader reader, long baseSlaMs) throws IOException {
+ final int termCount = estimateTermCount(query);
+ final double avgDocFreq = estimateAvgDocFreq(reader);
+ final int queryCost = estimateQueryCost(query);
+
+ double m = 1.0;
+ m += TERM_COST * termCount;
+ m += FREQ_COST * avgDocFreq;
+ m += QUERY_COMPLEXITY * queryCost;
+
+ return baseSlaMs * Math.min(MAX_MULT, m);
+ }
+
+ /** Estimate of number of terms that will participate in the scoring */
+ private int estimateTermCount(Query query) {
+ if (query instanceof MatchAllDocsQuery) {
+ return 0;
+ }
+
+ if (query instanceof TermQuery) {
+ return 1;
+ }
+
+ if (query instanceof PhraseQuery pq) {
+ return pq.getTerms().length;
+ }
+
+ if (query instanceof BooleanQuery bq) {
+ int total = 0;
+ for (BooleanClause clause : bq) {
+ BooleanClause.Occur occur = clause.occur();
+ if (occur == BooleanClause.Occur.MUST || occur == BooleanClause.Occur.SHOULD) {
+ total += estimateTermCount(clause.query());
+ }
+ }
+ return total > 0 ? total : 1;
+ }
+
+ if (query instanceof DisjunctionMaxQuery dmq) {
+ // Take the cost of max cost branch
+ int max = 0;
+ for (Query sub : dmq.getDisjuncts()) {
+ max = Math.max(max, estimateTermCount(sub));
+ }
+ return max > 0 ? max : 1;
+ }
+
+ if (query instanceof SynonymQuery sq) {
+ return sq.getTerms().size();
+ }
+
+ if (query instanceof MultiTermQuery) {
+ // Conservative measure - no way to actually estimate
+ return 2;
+ }
+
+ if (query instanceof BoostQuery bq) {
+ return estimateTermCount(bq.getQuery());
+ }
+
+ if (query instanceof ConstantScoreQuery csq) {
+ return estimateTermCount(csq.getQuery());
+ }
+
+ // Default baseline cost - fallback if unknown query type
+ // Returning 0 will reduce the SLA to impractical values
+
+ return 1;
+ }
+
+ /** Coarse estimate of query execution cost. */
+ private int estimateQueryCost(Query query) {
+ if (query instanceof MatchAllDocsQuery) {
+ return 1;
+ }
+
+ if (query instanceof TermQuery) {
+ return 2;
+ }
+
+ if (query instanceof PhraseQuery pq) {
+ return 3 + pq.getTerms().length;
+ }
+
+ if (query instanceof BooleanQuery bq) {
+ int total = 0;
+ for (BooleanClause clause : bq) {
+ BooleanClause.Occur occur = clause.occur();
+ if (occur == BooleanClause.Occur.MUST || occur == BooleanClause.Occur.SHOULD) {
+ total += estimateQueryCost(clause.query());
+ }
+ }
+ return Math.max(2, total);
+ }
+
+ if (query instanceof DisjunctionMaxQuery dmq) {
+ // Max cost branch
+ int max = 0;
+ for (Query sub : dmq.getDisjuncts()) {
+ max = Math.max(max, estimateQueryCost(sub));
+ }
+ return 2 + max;
+ }
+
+ if (query instanceof SynonymQuery sq) {
+ return 2 + sq.getTerms().size();
+ }
+
+ if (query instanceof MultiTermQuery) {
+ // Conservative estimate - no way to actually measure
+ return 6;
+ }
+
+ if (query instanceof BoostQuery bq) {
+ return estimateQueryCost(bq.getQuery());
+ }
+
+ if (query instanceof ConstantScoreQuery csq) {
+ return estimateQueryCost(csq.getQuery());
+ }
+
+ // Default baseline cost - fallback if unknown query type
+ // Returning 0 will reduce the SLA to impractical values
+ return 4;
+ }
+
+ /** Computes average document frequency across a sample of terms in the field. */
+ private double estimateAvgDocFreq(IndexReader reader) throws IOException {
+ long docFreqSum = 0;
+ int sampled = 0;
+
+ for (LeafReaderContext leaf : reader.leaves()) {
+ Terms terms = leaf.reader().terms(field);
+ if (terms == null) {
+ continue;
+ }
+
+ TermsEnum te = terms.iterator();
+ while (te.next() != null && sampled < MAX_SAMPLE_TERMS) {
+ docFreqSum += te.docFreq();
+ sampled++;
+ }
+
+ if (sampled >= MAX_SAMPLE_TERMS) {
+ break;
+ }
+ }
+
+ return sampled > 0 ? (double) docFreqSum / sampled : 0.0;
+ }
+}
diff --git a/lucene/core/src/java/org/apache/lucene/util/SLAEstimator.java b/lucene/core/src/java/org/apache/lucene/util/SLAEstimator.java
new file mode 100644
index 00000000000..667e4bc111c
--- /dev/null
+++ b/lucene/core/src/java/org/apache/lucene/util/SLAEstimator.java
@@ -0,0 +1,27 @@
+/*
+ * 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.util;
+
+import org.apache.lucene.index.IndexReader;
+import org.apache.lucene.search.Query;
+
+import java.io.IOException;
+
+/** Interface to implement SLA Estimator */
+public interface SLAEstimator {
+ double estimate(Query query, IndexReader reader, long baseSlaMs) throws IOException;
+}