You are viewing a plain text version of this content. The canonical link for it is here.
Posted to oak-commits@jackrabbit.apache.org by th...@apache.org on 2026/05/20 13:15:49 UTC

(jackrabbit-oak) branch OAK-12221 created (now 7fa818a2d6)

This is an automated email from the ASF dual-hosted git repository.

thomasmueller pushed a change to branch OAK-12221
in repository https://gitbox.apache.org/repos/asf/jackrabbit-oak.git


      at 7fa818a2d6 OAK-12221 Cost estimation should be lower if more conditions are indexed

This branch includes the following new commits:

     new 7fa818a2d6 OAK-12221 Cost estimation should be lower if more conditions are indexed

The 1 revisions listed above as "new" are entirely new to this
repository and will be described in separate emails.  The revisions
listed as "add" were already present in the repository and have only
been added to this reference.



(jackrabbit-oak) 01/01: OAK-12221 Cost estimation should be lower if more conditions are indexed

Posted by th...@apache.org.
This is an automated email from the ASF dual-hosted git repository.

thomasmueller pushed a commit to branch OAK-12221
in repository https://gitbox.apache.org/repos/asf/jackrabbit-oak.git

commit 7fa818a2d62d5f0ed1db9150339140464e152928
Author: Thomas Mueller <mu...@adobe.com>
AuthorDate: Wed May 20 15:15:27 2026 +0200

    OAK-12221 Cost estimation should be lower if more conditions are indexed
---
 .../index/lucene/LuceneIndexProviderService.java   |   3 +
 .../oak/plugins/index/lucene/IndexPlannerTest.java | 138 +++++++++++++++++++++
 .../index/elastic/ElasticIndexProviderService.java |   3 +
 .../index/search/FulltextIndexConstants.java       |   9 ++
 .../plugins/index/search/PropertyDefinition.java   |  39 ++++++
 .../search/spi/query/FulltextIndexPlanner.java     |  54 ++++++--
 .../index/search/util/IndexDefinitionBuilder.java  |   5 +
 7 files changed, 239 insertions(+), 12 deletions(-)

diff --git a/oak-lucene/src/main/java/org/apache/jackrabbit/oak/plugins/index/lucene/LuceneIndexProviderService.java b/oak-lucene/src/main/java/org/apache/jackrabbit/oak/plugins/index/lucene/LuceneIndexProviderService.java
index f981b715c6..ec2c5990d4 100644
--- a/oak-lucene/src/main/java/org/apache/jackrabbit/oak/plugins/index/lucene/LuceneIndexProviderService.java
+++ b/oak-lucene/src/main/java/org/apache/jackrabbit/oak/plugins/index/lucene/LuceneIndexProviderService.java
@@ -378,6 +378,9 @@ public class LuceneIndexProviderService {
         oakRegs.add(whiteboard.register(FeatureToggle.class,
                 new FeatureToggle(FulltextIndexPlanner.FT_OAK_12171, FulltextIndexPlanner.FT_OAK_12171_DISABLE),
                 emptyMap()));
+        oakRegs.add(whiteboard.register(FeatureToggle.class,
+                new FeatureToggle(FulltextIndexPlanner.FT_OAK_12221, FulltextIndexPlanner.FT_OAK_12221_ENABLE),
+                emptyMap()));
         oakRegs.add(whiteboard.register(FeatureToggle.class,
                 new FeatureToggle(FulltextIndexEditor.FT_OAK_12193, FulltextIndexEditor.FT_OAK_12193_DISABLE),
                 emptyMap()));
diff --git a/oak-lucene/src/test/java/org/apache/jackrabbit/oak/plugins/index/lucene/IndexPlannerTest.java b/oak-lucene/src/test/java/org/apache/jackrabbit/oak/plugins/index/lucene/IndexPlannerTest.java
index aa5d05b8c1..eca64a8aff 100644
--- a/oak-lucene/src/test/java/org/apache/jackrabbit/oak/plugins/index/lucene/IndexPlannerTest.java
+++ b/oak-lucene/src/test/java/org/apache/jackrabbit/oak/plugins/index/lucene/IndexPlannerTest.java
@@ -1465,6 +1465,144 @@ public class IndexPlannerTest {
         assertEquals(0, plan.getEstimatedEntryCount());
     }
 
+    /**
+     * Verifies cost estimation for a query with more indexed conditions against one with fewer.
+     *
+     * Real-world case: a query on (@id = 'X' or @identifier = 'X') and @type = 'variant'
+     * may be evaluated as a UNION; one leg carries both id and type restrictions.
+     * That leg should cost less than a plan using only type.
+     *
+     * Without FT_OAK-12221 the legacy min-model is used: both plans estimate
+     * min(ceil(100/5), ceil(100/5)) = 20, so adding id has no effect on cost.
+     *
+     * With FT_OAK-12221 enabled the multiplicative model divides by each condition's weight:
+     *   - plan1 (type only):      ceil(100/5)        = 20
+     *   - plan2 (id AND type): ceil(ceil(100/5)/5) =  4
+     */
+    @Test
+    public void moreRestrictedQueryShouldCostLess() throws Exception {
+        String indexPath = "/test";
+        LuceneIndexDefinitionBuilder idxBuilder = new LuceneIndexDefinitionBuilder(child(builder, indexPath));
+        idxBuilder.indexRule("nt:base")
+            .property("type").propertyIndex()
+            .enclosingRule()
+            .property("id").propertyIndex();
+        NodeState defn = idxBuilder.build();
+
+        // 100 documents, every one carrying both indexed properties.
+        List<Document> docs = new ArrayList<>();
+        for (int i = 0; i < 100; i++) {
+            Document doc = new Document();
+            doc.add(new StringField("type", "variant", Field.Store.NO));
+            doc.add(new StringField("id", "id" + i, Field.Store.NO));
+            docs.add(doc);
+        }
+        Directory sampleDirectory = createSampleDirectory(0, docs);
+        LuceneIndexDefinition idxDefn = new LuceneIndexDefinition(root, defn, indexPath);
+        LuceneIndexNode node = createIndexNode(idxDefn, sampleDirectory);
+
+        // Less specific: only restrict on type
+        FilterImpl filter1 = createFilter("nt:base");
+        filter1.restrictProperty("type", Operator.EQUAL, PropertyValues.newString("variant"));
+        FulltextIndexPlanner planner1 = new FulltextIndexPlanner(node, indexPath, filter1, Collections.emptyList());
+        QueryIndex.IndexPlan plan1 = planner1.getPlan();
+        assertNotNull(plan1);
+
+        // More specific: restrict on both id and type.
+        // This corresponds to one branch of a UNION query for
+        //   (@id = '151215Z71' or @identifier = '151215Z71') and @type = 'variant'.
+        FilterImpl filter2 = createFilter("nt:base");
+        filter2.restrictProperty("type", Operator.EQUAL, PropertyValues.newString("variant"));
+        filter2.restrictProperty("id", Operator.EQUAL, PropertyValues.newString("151215Z71"));
+        FulltextIndexPlanner planner2 = new FulltextIndexPlanner(node, indexPath, filter2, Collections.emptyList());
+        QueryIndex.IndexPlan plan2 = planner2.getPlan();
+        assertNotNull(plan2);
+
+        // Legacy (toggle off): both plans yield the same estimate because the min-model cannot
+        // distinguish between one and two conditions when all fields have identical doc counts.
+        assertEquals(documentsPerValue(100), plan1.getEstimatedEntryCount());
+        assertEquals(documentsPerValue(100), plan2.getEstimatedEntryCount());
+
+        // With FT_OAK-12221 the multiplicative model gives a strictly lower estimate for plan2.
+        FulltextIndexPlanner.FT_OAK_12221_ENABLE.set(true);
+        try {
+            QueryIndex.IndexPlan plan1ft = new FulltextIndexPlanner(node, indexPath, filter1, Collections.emptyList()).getPlan();
+            QueryIndex.IndexPlan plan2ft = new FulltextIndexPlanner(node, indexPath, filter2, Collections.emptyList()).getPlan();
+            // plan1ft: ceil(100/5) = 20
+            assertEquals(documentsPerValue(100), plan1ft.getEstimatedEntryCount());
+            // plan2ft: ceil(ceil(100/5)/5) = ceil(20/5) = 4  <  20
+            assertThat(plan2ft.getEstimatedEntryCount(), lessThan(plan1ft.getEstimatedEntryCount()));
+        } finally {
+            FulltextIndexPlanner.FT_OAK_12221_ENABLE.set(false);
+        }
+    }
+
+    /**
+     * Verifies that MCV (Most Common Values) statistics in the 'stats' property override
+     * the weight-based estimate when querying for a specific value, when FT_OAK-12221 is enabled.
+     *
+     * The index has 900 documents: 800 with status=active, 100 with status=deleted.
+     * The 'stats' property encodes those counts. With the toggle on:
+     *   - status=active  → 800  (from MCV)
+     *   - status=deleted → 100  (from MCV)
+     *   - status=unknown → 180  (ceil(900/5), MCV fallback)
+     * With the toggle off all values yield the same weight-based estimate of 180.
+     */
+    @Test
+    public void mcvStatsShouldBeUsedForCostEstimation() throws Exception {
+        String indexPath = "/test";
+        LuceneIndexDefinitionBuilder idxBuilder = new LuceneIndexDefinitionBuilder(child(builder, indexPath));
+        idxBuilder.indexRule("nt:base")
+            .property("status").propertyIndex()
+                .stats("{\"common\":{\"active\":800,\"deleted\":100}}");
+        NodeState defn = idxBuilder.build();
+
+        // 800 docs with status=active, 100 with status=deleted
+        List<Document> docs = new ArrayList<>();
+        for (int i = 0; i < 800; i++) {
+            Document doc = new Document();
+            doc.add(new StringField("status", "active", Field.Store.NO));
+            docs.add(doc);
+        }
+        for (int i = 0; i < 100; i++) {
+            Document doc = new Document();
+            doc.add(new StringField("status", "deleted", Field.Store.NO));
+            docs.add(doc);
+        }
+        Directory sampleDirectory = createSampleDirectory(0, docs);
+        LuceneIndexDefinition idxDefn = new LuceneIndexDefinition(root, defn, indexPath);
+        LuceneIndexNode node = createIndexNode(idxDefn, sampleDirectory);
+
+        // Toggle off (default): MCV is ignored, all values get the same weight-based estimate
+        FilterImpl filter = createFilter("nt:base");
+        filter.restrictProperty("status", Operator.EQUAL, PropertyValues.newString("active"));
+        QueryIndex.IndexPlan plan = new FulltextIndexPlanner(node, indexPath, filter, Collections.emptyList()).getPlan();
+        assertNotNull(plan);
+        assertEquals(documentsPerValue(900), plan.getEstimatedEntryCount());
+
+        // Toggle on: MCV counts are used for known values; unknown values fall back to weight
+        FulltextIndexPlanner.FT_OAK_12221_ENABLE.set(true);
+        try {
+            filter = createFilter("nt:base");
+            filter.restrictProperty("status", Operator.EQUAL, PropertyValues.newString("active"));
+            plan = new FulltextIndexPlanner(node, indexPath, filter, Collections.emptyList()).getPlan();
+            assertEquals(800, plan.getEstimatedEntryCount());
+
+            filter = createFilter("nt:base");
+            filter.restrictProperty("status", Operator.EQUAL, PropertyValues.newString("deleted"));
+            plan = new FulltextIndexPlanner(node, indexPath, filter, Collections.emptyList()).getPlan();
+            assertEquals(100, plan.getEstimatedEntryCount());
+
+            // Unknown value: no MCV entry, falls back to multiplicative estimate ceil(900/5) = 180
+            filter = createFilter("nt:base");
+            filter.restrictProperty("status", Operator.EQUAL, PropertyValues.newString("unknown"));
+            plan = new FulltextIndexPlanner(node, indexPath, filter, Collections.emptyList()).getPlan();
+            assertEquals(documentsPerValue(900), plan.getEstimatedEntryCount());
+        } finally {
+            FulltextIndexPlanner.FT_OAK_12221_ENABLE.set(false);
+        }
+    }
+
     @Test
     public void weightedRegexPropDefs() throws Exception {
         String indexPath = "/test";
diff --git a/oak-search-elastic/src/main/java/org/apache/jackrabbit/oak/plugins/index/elastic/ElasticIndexProviderService.java b/oak-search-elastic/src/main/java/org/apache/jackrabbit/oak/plugins/index/elastic/ElasticIndexProviderService.java
index b784a9445e..fdeba0da1a 100644
--- a/oak-search-elastic/src/main/java/org/apache/jackrabbit/oak/plugins/index/elastic/ElasticIndexProviderService.java
+++ b/oak-search-elastic/src/main/java/org/apache/jackrabbit/oak/plugins/index/elastic/ElasticIndexProviderService.java
@@ -218,6 +218,9 @@ public class ElasticIndexProviderService {
         oakRegs.add(whiteboard.register(FeatureToggle.class,
                 new FeatureToggle(FulltextIndexPlanner.FT_OAK_12171, FulltextIndexPlanner.FT_OAK_12171_DISABLE),
                 emptyMap()));
+        oakRegs.add(whiteboard.register(FeatureToggle.class,
+                new FeatureToggle(FulltextIndexPlanner.FT_OAK_12221, FulltextIndexPlanner.FT_OAK_12221_ENABLE),
+                emptyMap()));
         oakRegs.add(whiteboard.register(FeatureToggle.class,
                 new FeatureToggle(ElasticIndexEditorProvider.FT_OAK_12206, ElasticIndexEditorProvider.FT_OAK_12206_DISABLE),
                 emptyMap()));
diff --git a/oak-search/src/main/java/org/apache/jackrabbit/oak/plugins/index/search/FulltextIndexConstants.java b/oak-search/src/main/java/org/apache/jackrabbit/oak/plugins/index/search/FulltextIndexConstants.java
index a28c299e09..5dbb68a2d1 100644
--- a/oak-search/src/main/java/org/apache/jackrabbit/oak/plugins/index/search/FulltextIndexConstants.java
+++ b/oak-search/src/main/java/org/apache/jackrabbit/oak/plugins/index/search/FulltextIndexConstants.java
@@ -139,6 +139,15 @@ public interface FulltextIndexConstants {
 
     String PROP_WEIGHT = "weight";
 
+    /**
+     * JSON string property on a property definition for Most Common Values (MCV) statistics.
+     * Format: {@code {"common":{"value1": count1, "value2": count2}}}
+     * Used for cost estimation when the query restricts a property to a specific value.
+     * If the value is present in "common", its count is used directly; otherwise falls back
+     * to {@link #PROP_WEIGHT}.
+     */
+    String PROP_STATS = "stats";
+
     /**
      * Weight used for cost estimation of "is null" property restrictions.
      * Falls back to {@link #PROP_WEIGHT} if not set.
diff --git a/oak-search/src/main/java/org/apache/jackrabbit/oak/plugins/index/search/PropertyDefinition.java b/oak-search/src/main/java/org/apache/jackrabbit/oak/plugins/index/search/PropertyDefinition.java
index 4078f91410..9c9559a6e6 100644
--- a/oak-search/src/main/java/org/apache/jackrabbit/oak/plugins/index/search/PropertyDefinition.java
+++ b/oak-search/src/main/java/org/apache/jackrabbit/oak/plugins/index/search/PropertyDefinition.java
@@ -23,13 +23,19 @@ import static org.apache.jackrabbit.oak.commons.PathUtils.isAbsolute;
 import static org.apache.jackrabbit.oak.plugins.index.search.FulltextIndexConstants.FIELD_BOOST;
 import static org.apache.jackrabbit.oak.plugins.index.search.FulltextIndexConstants.PROP_IS_REGEX;
 import static org.apache.jackrabbit.oak.plugins.index.search.FulltextIndexConstants.PROP_SIMILARITY_SEARCH_DENSE_VECTOR_SIZE;
+import static org.apache.jackrabbit.oak.plugins.index.search.FulltextIndexConstants.PROP_STATS;
 import static org.apache.jackrabbit.oak.plugins.index.search.FulltextIndexConstants.PROP_WEIGHT;
 import static org.apache.jackrabbit.oak.plugins.index.search.spi.query.FulltextIndexPlanner.DEFAULT_PROPERTY_WEIGHT;
 import static org.apache.jackrabbit.oak.plugins.index.search.util.ConfigUtil.getOptionalValue;
 
+import java.util.Collections;
+import java.util.HashMap;
+import java.util.Map;
+
 import org.apache.jackrabbit.oak.api.PropertyState;
 import org.apache.jackrabbit.oak.api.Type;
 import org.apache.jackrabbit.oak.commons.PathUtils;
+import org.apache.jackrabbit.oak.commons.json.JsonObject;
 import org.apache.jackrabbit.oak.commons.collections.IterableUtils;
 import org.apache.jackrabbit.oak.commons.collections.ListUtils;
 import org.apache.jackrabbit.oak.plugins.index.property.ValuePattern;
@@ -124,6 +130,13 @@ public class PropertyDefinition {
      */
     public final int weightNotNull;
 
+    /**
+     * Most Common Values from the {@code stats} property (if present).
+     * Maps a property value (string) to its document count. Used by the cost estimator
+     * when the query restricts this property to a specific value. Empty if not configured.
+     */
+    public final Map<String, Long> commonValues;
+
     public final boolean dynamicBoost;
 
     /**
@@ -165,6 +178,7 @@ public class PropertyDefinition {
         this.weight = getOptionalValue(defn, PROP_WEIGHT, DEFAULT_PROPERTY_WEIGHT);
         this.weightNull = getOptionalValue(defn, FulltextIndexConstants.PROP_WEIGHT_NULL, -1);
         this.weightNotNull = getOptionalValue(defn, FulltextIndexConstants.PROP_WEIGHT_NOT_NULL, -1);
+        this.commonValues = parseCommonValues(defn);
         this.dynamicBoost = getOptionalValue(defn, FulltextIndexConstants.PROP_DYNAMIC_BOOST, false);
 
         //By default if a property is defined it is indexed
@@ -211,6 +225,31 @@ public class PropertyDefinition {
         validate();
     }
 
+    private static Map<String, Long> parseCommonValues(NodeState defn) {
+        PropertyState statsProperty = defn.getProperty(PROP_STATS);
+        if (statsProperty == null) {
+            return Map.of();
+        }
+        try {
+            JsonObject stats = JsonObject.fromJson(statsProperty.getValue(Type.STRING), false);
+            JsonObject common = stats.getChildren().get("common");
+            if (common == null) {
+                return Map.of();
+            }
+            Map<String, String> props = common.getProperties();
+            if (props.isEmpty()) {
+                return Map.of();
+            }
+            Map<String, Long> result = new HashMap<>(props.size());
+            for (Map.Entry<String, String> e : props.entrySet()) {
+                result.put(e.getKey(), Long.parseLong(e.getValue()));
+            }
+            return Collections.unmodifiableMap(result);
+        } catch (Exception e) {
+            log.warn("Failed to parse 'stats' property: {}", statsProperty.getValue(Type.STRING), e);
+            return Map.of();
+        }
+    }
 
     /**
      * If 'analyzed' is enabled then property value would be used to evaluate the
diff --git a/oak-search/src/main/java/org/apache/jackrabbit/oak/plugins/index/search/spi/query/FulltextIndexPlanner.java b/oak-search/src/main/java/org/apache/jackrabbit/oak/plugins/index/search/spi/query/FulltextIndexPlanner.java
index 5bd413085a..fe10f0c76b 100644
--- a/oak-search/src/main/java/org/apache/jackrabbit/oak/plugins/index/search/spi/query/FulltextIndexPlanner.java
+++ b/oak-search/src/main/java/org/apache/jackrabbit/oak/plugins/index/search/spi/query/FulltextIndexPlanner.java
@@ -93,6 +93,20 @@ public class FulltextIndexPlanner {
      */
     public static final AtomicBoolean FT_OAK_12171_DISABLE = new AtomicBoolean(false);
 
+    /**
+     * Feature toggle name for OAK-12221.
+     * When enabled, cost estimation uses a multiplicative selectivity model: each indexed
+     * condition reduces the estimated entry count by dividing by its weight, so queries with
+     * more indexed conditions produce lower cost estimates.  Disabled by default.
+     */
+    public static final String FT_OAK_12221 = "FT_OAK-12221";
+
+    /**
+     * Enable flag for the multiplicative cost estimation introduced by OAK-12221.
+     * Default is {@code false} (feature disabled). Wired to {@link #FT_OAK_12221} at runtime.
+     */
+    public static final AtomicBoolean FT_OAK_12221_ENABLE = new AtomicBoolean(false);
+
     /**
      * IndexPlan Attribute name which refers to the name of the fields that should be used for facets.
      */
@@ -912,19 +926,35 @@ public class FulltextIndexPlanner {
                 }
             }
 
-            if (weight > 1) {
-                // use it to scale down the doc count - in broad strokes, we can think of weight
-                // as number of terms for the field with all terms getting equal share of
-                // the documents in this field
-                double scaledDocCnt = Math.ceil((double) docCntForField / weight);
-                if (minNumDocs < scaledDocCnt) {
-                    continue;
+            if (FT_OAK_12221_ENABLE.get()) {
+                // With OAK-12221: check MCV stats first for equality restrictions, then fall
+                // back to the multiplicative selectivity model.
+                Long mcvCount = null;
+                if (pr != null && isEqualityRestriction(pr)) {
+                    mcvCount = propDef.getValue().commonValues.get(pr.first.getValue(Type.STRING));
+                }
+                if (mcvCount != null) {
+                    // Use the MCV count directly, capped at docCntForField.
+                    minNumDocs = (int) Math.min(Math.min(mcvCount, docCntForField), minNumDocs);
+                } else if (weight > 1) {
+                    // Multiplicative model: divide the running estimate by this condition's weight,
+                    // then cap at docCntForField.
+                    double scaledEst = Math.ceil((double) minNumDocs / weight);
+                    minNumDocs = (int) Math.min(docCntForField, scaledEst);
+                } else if (docCntForField < minNumDocs) {
+                    minNumDocs = docCntForField;
+                }
+            } else {
+                // Legacy min model: compute a per-field estimate and track the minimum.
+                if (weight > 1) {
+                    double scaledDocCnt = Math.ceil((double) docCntForField / weight);
+                    if (minNumDocs < scaledDocCnt) {
+                        continue;
+                    }
+                    minNumDocs = (int) scaledDocCnt;
+                } else if (docCntForField < minNumDocs) {
+                    minNumDocs = docCntForField;
                 }
-                // since, we've already taken care that scaled cost is lower than minCost,
-                // we can safely cast without risking overflow
-                minNumDocs = (int)scaledDocCnt;
-            } else if (docCntForField < minNumDocs) {
-                minNumDocs = docCntForField;
             }
         }
 
diff --git a/oak-search/src/main/java/org/apache/jackrabbit/oak/plugins/index/search/util/IndexDefinitionBuilder.java b/oak-search/src/main/java/org/apache/jackrabbit/oak/plugins/index/search/util/IndexDefinitionBuilder.java
index 64268aba1a..cb4d0db9f3 100644
--- a/oak-search/src/main/java/org/apache/jackrabbit/oak/plugins/index/search/util/IndexDefinitionBuilder.java
+++ b/oak-search/src/main/java/org/apache/jackrabbit/oak/plugins/index/search/util/IndexDefinitionBuilder.java
@@ -487,6 +487,11 @@ public class IndexDefinitionBuilder {
             return this;
         }
 
+        public PropertyRule stats(String statsJson) {
+            propTree.setProperty(FulltextIndexConstants.PROP_STATS, statsJson);
+            return this;
+        }
+
         public PropertyRule boost(float boost) {
             propTree.setProperty(FIELD_BOOST, (double) boost, Type.DOUBLE);
             return this;