Copilot commented on code in PR #2428: URL: https://github.com/apache/phoenix/pull/2428#discussion_r3918225131
########## phoenix-core-client/src/main/java/org/apache/phoenix/compile/keyspace/scan/V2ScanBuilder.java: ########## @@ -0,0 +1,374 @@ +/* + * 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.phoenix.compile.keyspace.scan; + +import java.util.ArrayList; +import java.util.Collections; +import java.util.List; +import java.util.Set; + +import org.apache.phoenix.compile.ScanRanges; +import org.apache.phoenix.compile.keyspace.KeyRangeExtractor; +import org.apache.phoenix.compile.keyspace.KeySpace; +import org.apache.phoenix.compile.keyspace.KeySpaceList; +import org.apache.phoenix.parse.HintNode.Hint; +import org.apache.phoenix.query.KeyRange; +import org.apache.phoenix.query.QueryConstants; +import org.apache.phoenix.schema.PTable; +import org.apache.phoenix.schema.RowKeySchema; +import org.apache.phoenix.schema.SortOrder; +import org.apache.phoenix.schema.types.PChar; + +import org.apache.phoenix.thirdparty.com.google.common.base.Optional; + +/** + * Scan-construction entry point for the V2 WHERE optimizer. + * <p> + * Pipeline: + * + * <pre> + * WhereOptimizerV2.run + * → ExpressionNormalizer → KeySpaceExpressionVisitor (produces KeySpaceList) + * → V2ScanBuilder.build (this class) + * → CompoundByteEncoderEmitter.overrideScanRows (in-envelope shapes) + * → context.setScanRanges / context.setV2ScanArtifact + * </pre> + * + * Dispatches on a classification of the {@link KeySpaceList} (see + * {@code docs/where-optimizer-v2-scan-construction.md} §"Classification tree"): + * <ul> + * <li>Class 1 DEGENERATE → {@link ScanRanges#NOTHING}</li> + * <li>Class 2 EVERYTHING → {@link ScanRanges#EVERYTHING}</li> + * <li>Class 3 POINT_LOOKUP_LIST → natively emitted via {@link CompoundByteEncoder}</li> + * <li>Classes 4a–4e (RANGE_SCAN subcases) and 5 (SKIP_SCAN_LIST) → route through the + * {@link KeyRangeExtractor} adapter to produce V1-shaped CNF; scan start/stop bytes + * are then sourced from {@link CompoundByteEncoder} (via + * {@link CompoundByteEncoderEmitter} in {@code WhereOptimizerV2.run}) for shapes in + * the encoder's proven envelope.</li> + * </ul> + * Downstream consumers (SkipScanFilter, ScanRanges.isPointLookup, explain-plan + * formatter, local-index pruning) read from the ScanRanges this builder produces. + * V2-owned metadata is attached via {@link V2ScanArtifact} so the explain-plan formatter + * renders from the pre-encoding {@link KeySpaceList} rather than the post-encoding bytes. + */ +public final class V2ScanBuilder { + + private V2ScanBuilder() { + } + + /** + * Inputs gathered at {@code WhereOptimizerV2.run} and passed to the scan builder. + * All fields are read-only. + */ + public static final class Inputs { + public final KeySpaceList list; + public final PTable table; + public final RowKeySchema schema; + public final int nPkColumns; + public final int prefixSlots; + public final Integer nBuckets; + public final boolean isSalted; + public final boolean isMultiTenant; + public final boolean isSharedIndex; + public final byte[] tenantIdBytes; + public final Set<Hint> hints; + public final int cartesianBound; + public final Optional<byte[]> minOffset; + + public Inputs(KeySpaceList list, PTable table, RowKeySchema schema, int nPkColumns, + int prefixSlots, Integer nBuckets, boolean isSalted, boolean isMultiTenant, + boolean isSharedIndex, byte[] tenantIdBytes, Set<Hint> hints, int cartesianBound, + Optional<byte[]> minOffset) { + this.list = list; + this.table = table; + this.schema = schema; + this.nPkColumns = nPkColumns; + this.prefixSlots = prefixSlots; + this.nBuckets = nBuckets; + this.isSalted = isSalted; + this.isMultiTenant = isMultiTenant; + this.isSharedIndex = isSharedIndex; + this.tenantIdBytes = tenantIdBytes; + this.hints = hints; + this.cartesianBound = cartesianBound; + this.minOffset = minOffset; + } + } + + /** + * Output of the scan builder. For now this is a thin wrapper around + * {@link ScanRanges} (the existing type), leaving room to grow into a richer V2-owned + * adapter as more responsibilities move into this class. + */ + public static final class Result { + public final ScanRanges scanRanges; + /** + * {@code true} iff the builder's classification of the emitted key space is "matches + * nothing" — the caller short-circuits the residual and returns {@code null}. Distinct + * from {@code scanRanges.isDegenerate()} only insofar as it's set by the builder's + * own classification path (not always derivable from {@code scanRanges}). + */ + public final boolean isNothing; + + public Result(ScanRanges scanRanges, boolean isNothing) { + this.scanRanges = scanRanges; + this.isNothing = isNothing; + } + + public static Result nothing() { + return new Result(ScanRanges.NOTHING, true); + } + + public static Result everything() { + return new Result(ScanRanges.EVERYTHING, false); + } + } + + /** + * Build a {@link ScanRanges} from the given {@link KeySpaceList} and context. + * <p> + * Follows the classification tree in {@code docs/where-optimizer-v2-scan-construction.md} + * §"Classification tree". Shapes with a native V2 emission path are handled directly; + * shapes routed through the {@link KeyRangeExtractor} adapter produce the V1-projected + * per-slot CNF shape that {@link org.apache.phoenix.compile.ScanRanges#create} + the + * downstream {@code ScanUtil.setKey} consume. + * <p> + * Currently native classes: + * <ul> + * <li><b>1 DEGENERATE</b> — {@code list.isUnsatisfiable()} → {@link ScanRanges#NOTHING}.</li> + * <li><b>2 EVERYTHING</b> — {@code list.isEverything() && !prefixSlots && !minOffset} + * → {@link ScanRanges#EVERYTHING}.</li> + * <li><b>3 POINT_LOOKUP_LIST</b> — every space all-single-key across every productive + * dim past prefix, {@code list.size() ≥ 2} (single-space single-tuple routes through + * adapter to preserve DESC var-width byte shape). Emitted directly via + * {@link CompoundByteEncoder}, preserving cross-dim tuple correlation.</li> + * </ul> + * Classes 4 (RANGE_SCAN subcases) and 5 (SKIP_SCAN_LIST) currently route through the + * {@link KeyRangeExtractor} adapter to produce the V1-shaped CNF that + * {@link SkipScanFilter} consumes. {@link CompoundByteEncoderEmitter} then overrides + * {@code scan.startRow}/{@code stopRow} with encoder-sourced bytes for in-envelope + * shapes (see {@code docs/where-optimizer-v2-scan-construction.md} §"Byte emission + * envelope"). Native emission for classes 4 and 5 is PHOENIX-6791 follow-up work. + */ + public static Result build(Inputs in) { + // Class 1: DEGENERATE. + if (in.list.isUnsatisfiable()) { + return Result.nothing(); + } + // Class 2: EVERYTHING. + if (in.list.isEverything()) { + if (in.prefixSlots == 0 && !in.minOffset.isPresent()) { + return Result.everything(); + } + } + + // Class 3: POINT_LOOKUP_LIST. + if (isPointLookupList(in)) { + Result pl = buildPointLookupList(in); + if (pl != null) { + return pl; + } + // Native path opted out (encoder refused a space, e.g., IS_NULL sentinel). + // Fall through to the classical adapter. + } + + // Classes 4 (RANGE_SCAN subcases) and 5 (SKIP_SCAN_LIST): adapter. + + KeyRangeExtractor.Result extract = KeyRangeExtractor.extract( + in.list, in.nPkColumns, in.cartesianBound, in.prefixSlots, in.schema); + if (extract.isNothing()) { + return Result.nothing(); + } + + // Build CNF exactly the way WhereOptimizerV2.run does today: prefix slots (salt / + // viewIndexId / tenantId) + extractor-emitted user tail. + List<List<KeyRange>> cnf = new ArrayList<>(in.nPkColumns); + if (in.isSalted) { + // Salt byte placeholder. ScanRanges.isPointLookup requires a singleton point range + // (not EVERYTHING) for the whole query to classify as a point lookup when the user + // slots also carry single keys. + cnf.add(Collections.singletonList( + PChar.INSTANCE.getKeyRange(QueryConstants.SEPARATOR_BYTE_ARRAY, SortOrder.ASC))); + } + if (in.isSharedIndex) { + byte[] viewIndexBytes = in.table.getviewIndexIdType().toBytes(in.table.getViewIndexId()); + cnf.add(Collections.singletonList(KeyRange.getKeyRange(viewIndexBytes))); + } + if (in.isMultiTenant) { + cnf.add(Collections.singletonList(KeyRange.getKeyRange(in.tenantIdBytes))); + } + boolean useSkipScan = extract.useSkipScan; + if (in.hints != null) { + if (in.hints.contains(Hint.SKIP_SCAN)) { + useSkipScan = true; + } else if (in.hints.contains(Hint.RANGE_SCAN)) { + useSkipScan = false; + } + } + for (int i = 0; i < extract.ranges.size(); i++) { + cnf.add(extract.ranges.get(i)); + } + int[] slotSpan = new int[cnf.size()]; + if (extract.slotSpan.length > 0) { + int len = Math.min(extract.slotSpan.length, slotSpan.length - in.prefixSlots); + if (len > 0) { + System.arraycopy(extract.slotSpan, 0, slotSpan, in.prefixSlots, len); + } + } + + ScanRanges scanRanges = ScanRanges.create(in.schema, cnf, slotSpan, in.nBuckets, useSkipScan, + in.table.getRowTimestampColPos(), in.minOffset); + return new Result(scanRanges, false); + } + + /** + * Classifier: is every space in the list all-single-key across every productive dim, + * with no IS_NULL / IS_NOT_NULL sentinels? This is the RVC-IN / RVC-equality OR shape. + * <p> + * Restricted to multi-space lists (size ≥ 2). Single-space all-pinned shapes flow + * through the classical path which is already byte-identical to V1 (proven by parity + * harness across 142 tests); routing them through the native path would change byte + * output unnecessarily and break byte-shape assertions on point lookups. + */ + private static boolean isPointLookupList(Inputs in) { + if (in.list.isUnsatisfiable() || in.list.isEverything()) { + return false; + } + if (in.list.size() < 2) { + return false; + } + if (in.isSalted) { + // Salted tables: each row's salt byte is hash(row_key_no_salt) % nBuckets; the + // native path can't replicate that hashing here. ScanRanges.create does it + // correctly for point-lookup shapes via getPointKeys; defer to the adapter. + return false; + } + if (in.minOffset.isPresent()) { + // RVC-OFFSET uses getScanRange().getLowerRange() downstream; the classical path's + // byte layout is what that consumer expects. Stay on the adapter. + return false; + } + // Every space must be all-single-key past prefix, every dim must be constrained + // (no middle gaps), and no IS_NULL / IS_NOT_NULL sentinels. + int nPk = in.nPkColumns; + int productiveDims = 0; + for (KeySpace s : in.list.spaces()) { + int thisProductive = 0; + for (int d = in.prefixSlots; d < nPk; d++) { + KeyRange r = s.get(d); + if (r == KeyRange.EVERYTHING_RANGE) { + if (thisProductive > 0) return false; // middle gap + continue; + } Review Comment: The point-lookup classifier still accepts leading `EVERYTHING` dimensions. For a variable-width leading PK, `CompoundByteEncoder.encodeLower` emits a separator for that wildcard, and `buildPointLookupList` then treats the resulting bytes as an exact point key. A query such as an RVC `IN` over PK2/PK3 with unconstrained VARCHAR PK1 can therefore scan only the synthetic empty-PK1 keys and miss valid rows. Reject any unconstrained user dimension as the method contract requires, and let the adapter handle partial keys. ########## phoenix-core/src/test/java/org/apache/phoenix/query/BaseTest.java: ########## @@ -194,6 +194,32 @@ public abstract class BaseTest { public static final String DRIVER_CLASS_NAME_ATTRIB = "phoenix.driver.class.name"; protected static final String NULL_STRING = "NULL"; + + /** + * Captures the {@code -Dphoenix.where.optimizer.v2.enabled=...} value (if any) layered + * into the test driver via {@link #initDriver}. Tests use {@link #isV2Optimizer()} to + * branch their expected output between V1 and V2 forms when the optimizer's compound + * scan emission produces a tighter scan range or different residual filter shape. + */ + private static volatile String v2OptimizerEnabledOverride; + + /** + * True when the V2 WHERE optimizer is enabled for this test JVM (either via the + * {@code -Dphoenix.where.optimizer.v2.enabled=true} JVM arg or the codebase default + * if it has been flipped on). Returns false when the property is unset and the + * codebase default is V1. Use this from IT/UT tests whose expected scan-range or + * EXPLAIN output differs between V1 and V2. Review Comment: The documented fallback is stale: the current codebase default is V2 (`DEFAULT_WHERE_OPTIMIZER_V2_ENABLED` is `true`), not V1. Describe the precedence without claiming an incorrect default so tests do not select the wrong expected plan. ########## pom.xml: ########## @@ -177,6 +177,12 @@ <numForkedIT>7</numForkedIT> <it.failIfNoSpecifiedTests>false</it.failIfNoSpecifiedTests> <surefire.failIfNoSpecifiedTests>false</surefire.failIfNoSpecifiedTests> + <!-- WHERE optimizer V2 flag, forwarded into forked test JVMs by the surefire and + failsafe configurations below. Default empty so the connectionless test driver + picks the codebase default (V1). Override with + `mvn test -Dphoenix.where.optimizer.v2.enabled=true` to run the same suites + under V2. --> Review Comment: This describes the default backwards: `DEFAULT_WHERE_OPTIMIZER_V2_ENABLED` is `true`, so an empty property runs V2 and passing `true` does not switch modes. This can mislead developers about which optimizer the default test run covers; document V2 as the default and use `false` for a V1 run. ########## phoenix-core-client/src/main/java/org/apache/phoenix/query/KeyRange.java: ########## @@ -383,14 +383,24 @@ public boolean lowerUnbound() { return lowerRange == UNBOUND; } + // Cached hash. 0 means uncomputed (the chance of a legitimate 0 hash is negligible and + // even if it hits we just recompute). KeyRange is effectively immutable once constructed + // (fields are final), so memoization is safe. + private int cachedHashCode; + @Override public int hashCode() { + int h = cachedHashCode; + if (h != 0) { + return h; + } final int prime = 31; int result = 1; result = prime * result + Arrays.hashCode(lowerRange); if (lowerRange != null) result = prime * result + (lowerInclusive ? 1231 : 1237); result = prime * result + Arrays.hashCode(upperRange); if (upperRange != null) result = prime * result + (upperInclusive ? 1231 : 1237); + cachedHashCode = result; return result; } Review Comment: `KeyRange` is not immutable: its bound fields are protected and `readFields` replaces them. If `hashCode()` is called before a Writable instance is reused for deserialization, this cache retains the old value, violating the `equals`/`hashCode` contract and breaking hash-based collections. Remove the memoization (or comprehensively invalidate it on every mutation, including subclass mutations). ########## phoenix-core-client/src/main/java/org/apache/phoenix/compile/keyspace/WhereOptimizerV2.java: ########## @@ -0,0 +1,270 @@ +/* + * 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.phoenix.compile.keyspace; + +import java.sql.SQLException; +import java.util.Collections; +import java.util.HashSet; +import java.util.List; +import java.util.Set; + +import org.apache.phoenix.compile.ScanRanges; +import org.apache.phoenix.compile.StatementContext; +import org.apache.phoenix.compile.WhereOptimizer; +import org.apache.phoenix.compile.keyspace.scan.V2ScanBuilder; +import org.apache.phoenix.expression.Expression; +import org.apache.phoenix.expression.LiteralExpression; +import org.apache.phoenix.parse.HintNode.Hint; +import org.apache.phoenix.query.QueryServices; +import org.apache.phoenix.query.QueryServicesOptions; +import org.apache.phoenix.schema.PName; +import org.apache.phoenix.schema.PColumn; +import org.apache.phoenix.schema.PTable; +import org.apache.phoenix.schema.RowKeySchema; +import org.apache.phoenix.util.ScanUtil; + +import org.apache.phoenix.thirdparty.com.google.common.base.Optional; + +/** + * Entry point for the N-dimensional key-space WHERE optimizer. Pipes an expression through + * {@link ExpressionNormalizer}, {@link KeySpaceExpressionVisitor}, {@link KeyRangeExtractor}, + * and finally {@link ScanRanges#create}, then strips fully-consumed nodes via + * {@link WhereOptimizer.RemoveExtractedNodesVisitor}. + * <p> + * The driver is invoked in place of the legacy {@link WhereOptimizer} visitor when the + * {@link QueryServices#WHERE_OPTIMIZER_V2_ENABLED} flag is set. Both the legacy path and this + * one write the same shape to {@code context.setScanRanges(...)} and return an Expression + * representing the residual filter. + */ +public final class WhereOptimizerV2 { + + private WhereOptimizerV2() { + } + + public static Expression run(StatementContext context, Set<Hint> hints, Expression whereClause, + Set<Expression> extractNodes, Optional<byte[]> minOffset) throws SQLException { + + PTable table = context.getCurrentTable().getTable(); + RowKeySchema schema = table.getRowKeySchema(); + Integer nBuckets = table.getBucketNum(); + boolean isSalted = nBuckets != null; + PName tenantId = context.getConnection().getTenantId(); + boolean isMultiTenant = tenantId != null && table.isMultiTenant(); + boolean isSharedIndex = table.getViewIndexId() != null; + byte[] tenantIdBytes = isMultiTenant + ? ScanUtil.getTenantIdBytes(schema, isSalted, tenantId, isSharedIndex) + : null; + + // Short-circuits matching WhereOptimizer.pushKeyExpressionsToScan. + if (whereClause == null && !isMultiTenant && !isSharedIndex && !minOffset.isPresent()) { + context.setScanRanges(ScanRanges.EVERYTHING); + return whereClause; + } + if (LiteralExpression.isBooleanFalseOrNull(whereClause)) { + context.setScanRanges(ScanRanges.NOTHING); + return null; + } + + // FROM-less SELECT (e.g., `SELECT 1` or expression-only queries) resolves to a + // synthetic PTable with no PK columns. Phoenix represents this by returning null + // from getPKColumns(). There's nothing the optimizer can narrow in that case — leave + // the scan as EVERYTHING and return the residual expression unchanged so the + // executor evaluates it at scan time. + List<PColumn> pkColumns = table.getPKColumns(); + if (pkColumns == null || pkColumns.isEmpty()) { + context.setScanRanges(ScanRanges.EVERYTHING); + return whereClause; + } + int nPk = pkColumns.size(); + int prefixSlots = (isSalted ? 1 : 0) + (isSharedIndex ? 1 : 0) + (isMultiTenant ? 1 : 0); + + // Step 1: normalize + visit. The normalized tree is what the residual filter is built + // from — extracted Expression nodes come from the normalized tree, not the caller's + // original tree, so applying {@link WhereOptimizer.RemoveExtractedNodesVisitor} against + // the original would find nothing to strip for RVC-inequality and IN rewrites. + KeySpaceList keySpaceList; + Set<Expression> consumed = (extractNodes == null) ? new HashSet<Expression>() : extractNodes; + Expression residualInput = whereClause; + Set<Expression> visitorConsumed = Collections.emptySet(); + if (whereClause == null) { + keySpaceList = KeySpaceList.everything(nPk); + } else { + Expression normalized = ExpressionNormalizer.normalize(whereClause); + residualInput = normalized; + KeySpaceExpressionVisitor visitor = new KeySpaceExpressionVisitor(table); + KeySpaceExpressionVisitor.Result r = normalized.accept(visitor); + if (r == null || r.list().isEverything()) { + keySpaceList = KeySpaceList.everything(nPk); + } else if (r.list().isUnsatisfiable()) { + // PHOENIX-6669 short-circuit: degeneracy detected uniformly across all PK positions. + context.setScanRanges(ScanRanges.NOTHING); + return null; + } else { + keySpaceList = r.list(); + visitorConsumed = r.consumed(); + } + } + + int bound = context.getConnection().getQueryServices().getConfiguration() + .getInt(QueryServices.WHERE_OPTIMIZER_V2_CARTESIAN_BOUND, + QueryServicesOptions.DEFAULT_WHERE_OPTIMIZER_V2_CARTESIAN_BOUND); + + V2ScanBuilder.Inputs inputs = new V2ScanBuilder.Inputs(keySpaceList, table, schema, nPk, + prefixSlots, nBuckets, isSalted, isMultiTenant, isSharedIndex, tenantIdBytes, hints, + bound, minOffset); + V2ScanBuilder.Result r = V2ScanBuilder.build(inputs); + if (r.isNothing) { + context.setScanRanges(ScanRanges.NOTHING); + return null; + } + boolean emittedEverything = r.scanRanges == ScanRanges.EVERYTHING; + context.setScanRanges(r.scanRanges); + // Attach the V2 artifact so downstream consumers (explain-plan formatter) can read + // the logical KeySpaceList rather than the byte-encoded ScanRanges. Skipped for + // EVERYTHING since there's nothing to display anyway. + if (!emittedEverything) { + context.setV2ScanArtifact(new org.apache.phoenix.compile.keyspace.scan.V2ScanArtifact( + keySpaceList, nPk, prefixSlots)); + } + // Override scan start/stop rows with CompoundByteEncoder output for shapes in the + // encoder's proven envelope. The encoder's bytes preserve trailing separators that + // ScanUtil.setKey's tail-strip would drop, and its multi-space list envelope preserves + // cross-dim tuple correlation that per-slot projection loses — see + // docs/where-optimizer-v2-scan-construction.md. RVC OFFSET is skipped because + // RVCOffsetCompiler reads scan.startRow to build the paging cursor and is sensitive + // to the classical path's exact byte layout. See QueryMoreIT.testRVCOnDescWithLeadingPKEquality. + if (!emittedEverything && !minOffset.isPresent() + && org.apache.phoenix.compile.keyspace.scan.CompoundByteEncoderEmitter.isInScope( + keySpaceList, schema, prefixSlots, isSalted)) { + org.apache.phoenix.compile.keyspace.scan.CompoundByteEncoderEmitter.overrideScanRows( + context.getScan(), keySpaceList, schema, prefixSlots, + buildPrefixBytes(isSalted, isSharedIndex, isMultiTenant, table, tenantIdBytes)); + } + + // If the emitted scan range is "everything" (no leading-PK narrowing survived the + // extract pass, e.g. a predicate on a non-leading PK column with no leading + // constraint), the visitor may still have populated consumed nodes for those + // predicates, but since they didn't influence the scan range, the residual filter + // must retain them for correctness. Match v1 semantics by clearing consumed in that + // case. + // + // Additionally, when the leading productive slot (the first user-PK dim at + // {@code prefixSlots}) is EVERYTHING in every space but a trailing slot is + // constrained, we cannot safely install a SkipScanFilter. Its setNextCellHint path + // builds startKey by concatenating each slot's lower bound — an EVERYTHING slot + // contributes zero bytes, producing a seek hint shorter than (and lex-less than) + // any row already past the trailing-slot boundary. HBase rejects the backward + // seek with {@code "next hint must come after previous hint"}. Prefix bytes (salt + // bucket, viewIndexId, tenantId) from {@code [0, prefixSlots)} are concrete, but + // they only anchor the scan's start/stop — the hint construction still uses the + // user slots and the same invariant applies. The predicate must stay in the + // residual BooleanExpressionFilter. + // Exception: when the caller forces SKIP_SCAN via hint, honor the hint — + // V2ScanBuilder installs the SkipScanFilter anyway and the caller accepts the + // associated risk (V1 has the same behavior); consume so the shape matches V1's + // compile-plan output. + boolean forcedSkipScan = hints != null && hints.contains(Hint.SKIP_SCAN); + boolean leadingEverythingPastPrefix = !emittedEverything && !forcedSkipScan + && hasLeadingEverythingAt(keySpaceList, prefixSlots); + if (!emittedEverything && !leadingEverythingPastPrefix) { + consumed.addAll(visitorConsumed); Review Comment: A non-`EVERYTHING` scan does not prove that every visitor-consumed predicate survived later approximation. `KeySpaceList.widenToBudget` can replace constrained dimensions with `EVERYTHING`, and `emitV1Projection` can drop trailing slots, yet this adds all original predicates to the removal set. For an over-budget conjunction, a dropped predicate is then absent from both the scan and residual filter, admitting rows that do not satisfy the WHERE clause. Propagate exactness/dropped-dimension metadata from the algebra and scan builder and retain the affected expressions in the residual. ########## phoenix-core-client/src/main/java/org/apache/phoenix/compile/keyspace/KeyRangeExtractor.java: ########## @@ -0,0 +1,1190 @@ +/* + * 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.phoenix.compile.keyspace; + +import java.math.BigInteger; +import java.util.ArrayList; +import java.util.Collections; +import java.util.List; + +import org.apache.phoenix.query.KeyRange; +import org.apache.phoenix.schema.RowKeySchema; +import org.apache.phoenix.util.ScanUtil; + +/** + * Converts a final {@link KeySpaceList} into the shape + * {@link org.apache.phoenix.compile.ScanRanges#create} consumes: + * {@code List<List<KeyRange>> ranges}, {@code int[] slotSpan}, {@code boolean useSkipScan}. + * <p> + * <b>The V1 projection (default output shape).</b> The legacy optimizer produced one + * {@link KeyRange} list per PK column ("slot"): the disjunction of every narrowing the + * WHERE clause places on that column. {@link org.apache.phoenix.compile.ScanRanges} + * and {@link org.apache.phoenix.filter.SkipScanFilter} are built against that shape. + * V2 computes its narrowing as a {@link KeySpaceList} (disjunction of N-dim boxes) + * and, by projecting each {@link KeySpace} onto each PK column and coalescing per column, + * produces the same V1-compatible shape. This is the role of + * {@link #emitV1Projection}. The method name reflects its job: it's the boundary layer + * where V2's N-dim key-space algebra is converted into V1's per-slot disjunctions so + * the existing downstream machinery can consume it unchanged. + * <p> + * <b>Compound emission (optional optimization).</b> For some shapes a tighter scan is + * possible by concatenating per-dim bytes into a single compound {@link KeyRange} per + * {@link KeySpace} — preserving cross-dim tuple correlation at the byte level. Compound + * emission uses one output slot with {@code slotSpan = maxProductiveLen - 1}; the start + * and stop rows then narrow to the exact compound interval (e.g. a 15-tuple RVC-IN + * becomes a POINT LOOKUP on 15 compound keys rather than a SkipScan over 15 per-column + * disjunctions). When compound emission is unsafe — single productive dim, IS_NULL + * sentinels, middle-EVERYTHING gap, mixed-width coalesced ranges with non-point values + * — the extractor falls back to {@link #emitV1Projection}. + * <p> + * Once the legacy V1 optimizer is removed and downstream utilities ({@code ScanUtil.setKey}, + * {@code ScanRanges.create}'s special cases for {@code IS_NULL_RANGE}, etc.) are + * simplified to match the compound shape natively, the per-slot fallback can be + * deleted and compound emission becomes the sole path. + * <p> + * Correctness guarantee (for both paths): for every row the original predicate matches, + * the emitted scan contains it. False positives (rows in the emitted scan that don't + * satisfy the predicate) are handled by the residual filter. The cartesian-bound + * widening rule (drop trailing dims when the list size would exceed a threshold) is + * applied inside the extractor for the per-slot path and upstream in + * {@link KeySpaceList} for the compound path. + * <p> + * Prefix slots (salt byte, view-index id, tenant id) are prepended by {@link WhereOptimizerV2} + * at CNF-build time; this class emits only the user tail. + */ +public final class KeyRangeExtractor { + + /** Result of an extraction pass, shaped exactly like the inputs to {@code ScanRanges.create}. */ + public static final class Result { + public final List<List<KeyRange>> ranges; + public final int[] slotSpan; + public final boolean useSkipScan; + + public Result(List<List<KeyRange>> ranges, int[] slotSpan, boolean useSkipScan) { + this.ranges = ranges; + this.slotSpan = slotSpan; + this.useSkipScan = useSkipScan; + } + + public boolean isNothing() { + return ranges.size() == 1 && ranges.get(0).size() == 1 + && ranges.get(0).get(0) == KeyRange.EMPTY_RANGE; + } + + public boolean isEverything() { + return ranges.isEmpty(); + } + } + + public static Result everything() { + return new Result(Collections.<List<KeyRange>>emptyList(), new int[0], false); + } + + public static Result nothing() { + return new Result( + Collections.<List<KeyRange>>singletonList(Collections.singletonList(KeyRange.EMPTY_RANGE)), + ScanUtil.SINGLE_COLUMN_SLOT_SPAN, false); + } + + private KeyRangeExtractor() { + } + + /** + * Legacy entry point used by tests that don't have a schema handy. Emits per-slot output + * (pre-compound-emission behavior). Kept for test compatibility. + */ + public static Result extract(KeySpaceList list, int nPkColumns, int cartesianBound) { + return emitV1ProjectionStopAtGap(list, nPkColumns, cartesianBound, 0); + } + + /** + * Legacy entry point for schema-less tests with prefix slots. + */ + public static Result extract(KeySpaceList list, int nPkColumns, int cartesianBound, + int prefixSlots) { + return emitV1ProjectionStopAtGap(list, nPkColumns, cartesianBound, prefixSlots); + } + + /** + * Compound-emission entry point: emits one compound {@link KeyRange} per {@link KeySpace} + * in the list, into a single output slot with {@code slotSpan = maxProductiveLen - 1}. + * Requires a schema to concatenate per-dim bytes with correct separator handling. + */ + public static Result extract(KeySpaceList list, int nPkColumns, int cartesianBound, + int prefixSlots, RowKeySchema schema) { + if (schema == null) { + return emitV1ProjectionStopAtGap(list, nPkColumns, cartesianBound, prefixSlots); + } + if (list.isUnsatisfiable()) { + return nothing(); + } + if (list.isEverything()) { + return everything(); + } + + // Scan spaces to find the widest productive extent and whether every space has a + // middle-EVERYTHING gap. When every space has a middle gap past the prefix, emit + // per-slot so SkipScanFilter can narrow the trailing dim independently. When only + // some spaces have middle gaps, compound-emit each space independently so the + // non-middle-gap spaces can anchor a tight compound startRow. + int minProductiveStart = nPkColumns; + int maxProductiveEnd = prefixSlots; + boolean allSpacesHaveMiddleGap = true; + for (KeySpace ks : list.spaces()) { + int start = firstConstrainedDim(ks, prefixSlots); + if (start < 0) { + // Space is EVERYTHING past the prefix — whole list is EVERYTHING from our view. + return everything(); + } + if (start < minProductiveStart) minProductiveStart = start; + int endStrict = firstProductiveStopStrict(ks, prefixSlots); + int endAny = firstProductiveStopAnyPrefix(ks, prefixSlots); + if (endAny > maxProductiveEnd) maxProductiveEnd = endAny; + // Detect a middle gap by comparing the strict stop (first EVERYTHING past prefix) + // against the any-prefix stop (last constrained dim past prefix). They diverge + // iff there's an EVERYTHING dim BEFORE the last constrained dim, i.e. a gap. + boolean hasMiddleGap = start == prefixSlots && endStrict < endAny; + if (!hasMiddleGap) { + allSpacesHaveMiddleGap = false; + } + } + + // Leading EVERYTHING past the prefix, or EVERY space has a middle gap: emit per-slot. + // The per-slot SkipScanFilter handles narrowing past the gap and ScanRanges reports + // boundPkColumnCount correctly for the local-index-pruning heuristic. + if (minProductiveStart > prefixSlots || allSpacesHaveMiddleGap) { + return emitV1Projection(list, nPkColumns, cartesianBound, prefixSlots); + } + + + // Single-space, single-productive-dim: trivial case with no compound benefit. + // Using compound emission would pre-build bytes with separators, then ScanRanges.create + // (via getPointKeys -> ScanUtil.setKey) re-appends separator bytes for DESC fields, + // producing wider-than-correct scan. Per-slot emission lets ScanRanges process the + // range once with the real schema, matching V1's byte output exactly. + if (list.spaces().size() == 1 && (maxProductiveEnd - prefixSlots) == 1) { + return emitV1Projection(list, nPkColumns, cartesianBound, prefixSlots); + } + + // If any space has IS_NULL_RANGE / IS_NOT_NULL_RANGE at ANY productive dim, route + // to per-slot emission so ScanRanges receives the IS_NULL / IS_NOT_NULL sentinel + // intact. ScanRanges.create has special-case handling for IS_NULL_RANGE (producing + // the correct empty-bytes + separator boundary). Compound emission would collapse + // the sentinel into either a degenerate half-open range or a zero-length + // single-key at the wrong byte position, both of which produce scan rows that + // skip actual null-value rows. + for (KeySpace ks : list.spaces()) { + for (int d = prefixSlots; d < ks.nDims(); d++) { + KeyRange dim = ks.get(d); + if (dim == KeyRange.IS_NULL_RANGE || dim == KeyRange.IS_NOT_NULL_RANGE) { + return emitV1Projection(list, nPkColumns, cartesianBound, prefixSlots); + } + } + } + + // Mixed comparator safety gate: SkipScanFilter uses a single BytesComparator per + // compound slot, derived from schema.getField(rowKeyPosition) — i.e. the slot's + // LEADING field. When the compound spans multiple fields that require different + // comparators (e.g. ASC fixed-width BIGINT leading + DESC variable-width DECIMAL + // trailing), the leading-field comparator produces wrong results for the trailing + // field's bytes. Concretely: DESC var-width uses DescVarLengthFastByteComparisons + // which handles the variable-length DESC sort correctly; plain lex comparison + // (ASC fixed) does not. Fall back to per-slot emission so each slot gets its own + // comparator. See SortOrderIT.testSkipScanCompare. + if (prefixSlots < maxProductiveEnd) { + org.apache.phoenix.schema.ValueSchema.Field leadingField = schema.getField(prefixSlots); + org.apache.phoenix.util.ScanUtil.BytesComparator leadingCmp = + org.apache.phoenix.util.ScanUtil.getComparator(leadingField); + for (int d = prefixSlots + 1; d < maxProductiveEnd; d++) { + org.apache.phoenix.schema.ValueSchema.Field f = schema.getField(d); + if (org.apache.phoenix.util.ScanUtil.getComparator(f) != leadingCmp) { + return emitV1Projection(list, nPkColumns, cartesianBound, prefixSlots); + } + } + } + + // (Compound-too-wide safety gate moved below, after compound window is computed.) + + // IN-list-on-leading + range-on-trailing gate: when the leading productive dim is a + // single-key per space but points differ across spaces (classical IN-list shape) + // AND some later dim has a non-single-key range, route to per-slot emission. V2's + // compound-per-space form collapses the two-dimensional shape `[IN-list] × [range]` + // into one compound slot with {@code slotSpan = compoundLen - 1}, which under- + // counts PK columns covered (trailing unconstrained cols aren't accounted for). + // Server-side consumers that walk scans per-slot (e.g. {@link org.apache.phoenix + // .coprocessor.UncoveredGlobalIndexRegionScanner} / + // {@link org.apache.phoenix.coprocessor.CDCGlobalIndexRegionScanner} decode + // index-row keys to reconstruct data-row keys; ordering depends on how + // {@link org.apache.phoenix.filter.SkipScanFilter#intersect} steps the schema + // cursor, which reads {@code slotSpan[0]}) rely on the per-slot shape. Per-slot + // emission produces `[IN-list]` on slot 0 and `[range]` on slot 1 with the correct + // trailing-col coverage in slotSpan. See CDCQueryIT.testSelectCDC with salted + // data tables. + if (prefixSlots < maxProductiveEnd && list.spaces().size() >= 2) { + boolean leadingIsInList = true; + KeyRange firstLeading = null; + boolean leadingDiffers = false; + for (KeySpace ks : list.spaces()) { + KeyRange leading = ks.get(prefixSlots); + if (!leading.isSingleKey() || leading == KeyRange.IS_NULL_RANGE + || leading == KeyRange.IS_NOT_NULL_RANGE) { + leadingIsInList = false; + break; + } + if (firstLeading == null) { + firstLeading = leading; + } else if (!firstLeading.equals(leading)) { + leadingDiffers = true; + } + } + if (leadingIsInList && leadingDiffers) { + boolean laterRangeExists = false; + outer: + for (KeySpace ks : list.spaces()) { + for (int d = prefixSlots + 1; d < maxProductiveEnd; d++) { + KeyRange dim = ks.get(d); + if (dim == KeyRange.EVERYTHING_RANGE) continue; + if (!dim.isSingleKey()) { + laterRangeExists = true; + break outer; + } + } + } + if (laterRangeExists) { + return emitV1Projection(list, nPkColumns, cartesianBound, prefixSlots); + } + } + } + + int productiveStart = prefixSlots; + int maxProductiveLen = maxProductiveEnd - productiveStart; + if (maxProductiveLen <= 0) { + return everything(); + } + + // Classify each dim in [productiveStart, maxProductiveEnd) as "pinned" or not. + // A dim is pinned iff every space has the same single-key value on that dim. + // + // Only trailing-pinned dims are split out into their own slots; leading-pinned + // dims are folded into the compound. V1's shape works this way: when all spaces + // agree on an equality on some leading dim(s), the compound bytes anchor the + // scan tightly with that prefix. But when pinned equalities appear after an + // unbounded-range slot (i.e., trailing-pinned), they don't narrow the scan's + // start/stop bounds any further — V1 emits them as separate slots past the + // unbounded-compound slot, and ScanRanges.getBoundPkColumnCount() correctly + // stops counting at the first unbounded slot. + // + // Example: (pk1, pk2) > ('0','0') AND pk3 = '...' AND pk4 = '...' → + // compound spans pk1+pk2 with unbounded upper; pk3 and pk4 become trailing + // pinned slots. Bound count stops at the compound (3 cols total with tenantId). + KeyRange[] pinnedValue = new KeyRange[maxProductiveEnd]; + for (int d = productiveStart; d < maxProductiveEnd; d++) { + KeyRange shared = null; + boolean allAgree = true; + for (KeySpace ks : list.spaces()) { + KeyRange r = ks.get(d); + if ( + !r.isSingleKey() || r == KeyRange.IS_NULL_RANGE || r == KeyRange.IS_NOT_NULL_RANGE + ) { + allAgree = false; + break; + } + if (shared == null) { + shared = r; + } else if (!shared.equals(r)) { + allAgree = false; + break; + } + } + pinnedValue[d] = allAgree ? shared : null; + } + // Compound window: [compoundStart, compoundEnd). Leading-pinned dims stay in + // the compound (compoundStart = productiveStart); trailing-pinned dims are + // split out only when the compound has at least one non-pinned range dim AND + // the compound would end up with an unbounded side. Splitting otherwise would + // break scans where the compound captures all narrowing in a single fully- + // bounded range (e.g., `id LIKE 'xy%' AND type = 1` → one 2-col compound + // with both bounds fully specified). + int compoundStart = productiveStart; + int compoundEnd = maxProductiveEnd; + // Check whether splitting is warranted: find the first non-pinned dim. If all + // dims are pinned or there's no non-pinned dim before the trailing pinned + // run, don't split. + int firstNonPinned = -1; + for (int d = productiveStart; d < maxProductiveEnd; d++) { + if (pinnedValue[d] == null) { + firstNonPinned = d; + break; + } + } + if (firstNonPinned >= 0) { + // Check whether the non-pinned dim(s) would produce a compound with an + // unbounded side across any space. Only then is trailing-split beneficial. + boolean anyUnbound = false; + for (KeySpace ks : list.spaces()) { + for (int d = firstNonPinned; d < maxProductiveEnd && pinnedValue[d] == null; d++) { + KeyRange r = ks.get(d); + if (r == KeyRange.EVERYTHING_RANGE || r.isUnbound()) { + anyUnbound = true; + break; + } + } + if (anyUnbound) break; + } + if (anyUnbound) { + while (compoundEnd > compoundStart && pinnedValue[compoundEnd - 1] != null) { + compoundEnd--; + } + } + } + int compoundLen = compoundEnd - compoundStart; + + // Safety gate: compound emission is UNSAFE when any space has a non-single-key dim + // followed by ANY further constraint (pinned or range) on a later dim WITHIN THE + // COMPOUND WINDOW. The compound byte range [lo1+lo2, hi1+hi2) is lex-wider than the + // conjunction, so rows with col1 strictly between lo1 and hi1 pass regardless of + // col2's value — and V2 doesn't emit a residual SkipScanFilter to reject them. V1 + // falls back to per-column projection with a SkipScanFilter for this shape. + // + // Example broken shapes: + // key_1 in [000,200) AND key_2 in [aabb,aadd) → rows with key_1='100', key_2='aaaa' + // are in the compound [000aabb, 200) but shouldn't match (key_2 out of range). + // CREATETIME in [A,B] AND ACCOUNTID='v' → rows with any ACCOUNTID value in the + // middle CREATETIME band are in the compound but shouldn't match. + // + // Checked within compound window: trailing pinned dims outside the window are split + // into separate slots and don't participate in this check. + // + // Rule: if any space has a non-single-key dim followed by any further constrained + // dim (single-key or range) in the compound window, fall back. Trailing non-single- + // key within the window is safe (last dim of the compound range, bound correctly). + for (KeySpace ks : list.spaces()) { + boolean sawNonSingleKey = false; + for (int d = compoundStart; d < compoundEnd; d++) { + KeyRange dim = ks.get(d); + if (dim == KeyRange.EVERYTHING_RANGE) continue; + if (!dim.isSingleKey()) { + if (sawNonSingleKey) { + return emitV1Projection(list, nPkColumns, cartesianBound, prefixSlots); + } + sawNonSingleKey = true; + } else if (sawNonSingleKey) { + return emitV1Projection(list, nPkColumns, cartesianBound, prefixSlots); + } + } + } + + // Build one compound KeyRange per space, only over the [compoundStart, compoundEnd) + // window. Pinned prefix/suffix dims are emitted as individual slots outside the loop. + List<KeyRange> compounds = new ArrayList<>(list.size()); + // Skip the compound build entirely when every productive dim is pinned: no range + // part to compound. The pinned slots below carry all the narrowing. + if (compoundLen > 0) { + for (KeySpace ks : list.spaces()) { + int end = firstProductiveStop(ks, prefixSlots); + // Clamp end to the compound window: trailing pinned dims are emitted separately. + if (end > compoundEnd) end = compoundEnd; + // Per-dim view: dims [compoundStart, end) as individual slots with slotSpan 0. + int len = end - compoundStart; + if (len <= 0) { + // Space is all-EVERYTHING past the prefix — contributes EVERYTHING. The whole + // list's emission becomes EVERYTHING. + return everything(); + } + List<List<KeyRange>> perDimSlots = new ArrayList<>(len); + int[] perDimSpan = new int[len]; + boolean allSingleKey = true; + // IS_NULL_RANGE has empty bounds and KeyRange.isSingleKey() returns true. For + // a non-leading IS NULL with trailing unconstrained PK columns AND leading + // single-key equality prefix, the compound must be half-open to exclude rows with + // non-null values on the null-dim. For leading IS NULL (no single-key prefix), + // keeping the IS_NULL_RANGE sentinel lets ScanRanges.create handle it specially + // (it has separate codepaths for IS_NULL_RANGE that set the right scan bounds). + boolean hasTrailingUnconstrained = end < ks.nDims(); + // Count the leading single-key equality prefix within this space's productive run. + int leadingSingleKeyCount = 0; + for (int d = compoundStart; d < end; d++) { + KeyRange dim = ks.get(d); + if (dim.isSingleKey() && dim != KeyRange.IS_NULL_RANGE + && dim != KeyRange.IS_NOT_NULL_RANGE) { + leadingSingleKeyCount++; + } else { + break; + } + } + for (int d = compoundStart; d < end; d++) { + KeyRange dim = ks.get(d); + perDimSlots.add(Collections.singletonList(dim)); + if (!dim.isSingleKey()) { + allSingleKey = false; + } else if ((dim == KeyRange.IS_NULL_RANGE || dim == KeyRange.IS_NOT_NULL_RANGE) + && hasTrailingUnconstrained && leadingSingleKeyCount > 0) { + // Non-leading IS NULL with leading equality prefix: convert to half-open so + // trailing non-null rows don't sneak in via the nextKey-bumped upper. + allSingleKey = false; + } + } + // Use setKey variant with schemaStartIndex so the schema is walked starting from + // the user-tail fields (after prefix columns like salt, viewIndexId, tenantId). + // Without this, the first user-tail slot's bytes get decoded against the schema's + // leading field (e.g. the VARCHAR tenantId slot), which appends a spurious `\x00` + // separator for non-fixed-width leading fields. + byte[] lo = getKeyWithSchemaOffset(schema, perDimSlots, perDimSpan, + KeyRange.Bound.LOWER, compoundStart); + byte[] hi = getKeyWithSchemaOffset(schema, perDimSlots, perDimSpan, + KeyRange.Bound.UPPER, compoundStart); + // Strip the trailing separator byte for the last productive field if it's + // variable-length AND that field is the last field in the full PK schema. + // ScanUtil.getMinKey/getMaxKey append a trailing separator for variable-length + // fields (both ASC `\x00` and DESC `\xFF`). Downstream ScanRanges.create -> + // ScanUtil.setKey walks our compound bytes again and re-appends another separator + // when it finishes the same field, producing a double-separator bug (extra + // trailing `\xFF` for DESC, extra `\x00` for ASC). Stripping here lets the + // downstream setKey re-add it correctly. + // + // IMPORTANT: only strip when the last productive field is actually the last field + // in the PK. If there are unconstrained PK fields after the productive run, the + // trailing separator is an internal boundary marker between the last-productive + // dim and the (wildcard) next dim — downstream setKey needs it to know where the + // constrained prefix ends. Stripping in that case produces a startRow that's too + // short and misses the dim boundary (see QueryCompilerTest.testRVCScanBoundaries1). + org.apache.phoenix.schema.ValueSchema.Field lastField = + schema.getField(compoundStart + len - 1); + boolean lastIsVarLength = !lastField.getDataType().isFixedWidth(); + boolean lastIsLastPkField = (compoundStart + len) == schema.getMaxFields(); + // Strip when: + // (a) this field is the last PK field (no trailing unconstrained dims), OR + // (b) all productive dims are single-key (we'll emit as a point key, and the + // trailing separator is redundant — downstream SkipScanFilter works with + // raw point bytes). + // When neither condition holds (range with trailing EVERYTHING dims), keep the + // separator as a boundary marker for downstream setKey (see testRVCScanBoundaries1). + if (lastIsVarLength && (lastIsLastPkField || allSingleKey)) { + lo = stripTrailingSeparator(lo, lastField); + hi = stripTrailingSeparator(hi, lastField); + } + // Wrap into a compound KeyRange. getMinKey/getMaxKey already apply exclusive-bound + // bumping internally. + // + // For all-single-key compounds (every productive dim is a point equality), emit as + // KeyRange.getKeyRange(bytes) — a single-key range. Downstream + // ScanRanges.isPointLookup() needs isSingleKey()=true on the range to promote the + // scan to a proper GET-style point lookup; a half-open [lo, hi) range never + // qualifies even when lo and hi are nextKey-adjacent. + // + // EXCEPTION: when this space's productive dims end before maxProductiveEnd (i.e. the + // slot-span covers more dims than this space constrains), a single-key compound would + // have fewer bytes than the SkipScanFilter expects for this slot. Emit a half-open + // range [lo, nextKey(lo)) in that case so the range matches any row whose leading + // bytes equal lo — the trailing unconstrained dims are implicitly wild. + KeyRange compound; + boolean shorterThanSlotSpan = end < compoundEnd; + if (allSingleKey && lo != null && lo.length > 0 && !shorterThanSlotSpan) { + compound = KeyRange.getKeyRange(lo); + } else { + compound = KeyRange.getKeyRange(lo == null ? KeyRange.UNBOUND : lo, true, + hi == null ? KeyRange.UNBOUND : hi, false); + } + if (compound == KeyRange.EMPTY_RANGE) { + continue; + } + compounds.add(compound); + } + if (compounds.isEmpty()) { + return nothing(); + } + + // Cartesian bound: if the number of compound ranges exceeds the bound, we need to + // widen. That widening happens upstream in KeySpaceList; by the time we reach here + // the list is already bounded. Still, apply a defensive cap. + BigInteger bound = BigInteger.valueOf(Math.max(1, cartesianBound)); + if (BigInteger.valueOf(compounds.size()).compareTo(bound) > 0) { + // Over budget — drop everything past the bound (sound widening: truncation admits + // more rows but never fewer; residual filter handles any extras). + compounds = compounds.subList(0, cartesianBound); Review Comment: Truncating this list narrows the union; it does not widen it. Any matching compound range after the cutoff disappears from the scan start/stop envelope and SkipScanFilter, producing false negatives that a residual filter cannot recover. When over budget, replace discarded ranges with a covering superset (or fall back to an unbounded/per-slot scan) rather than taking the first entries. This issue also appears on line 980 of the same file. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected]
