xiedeyantu commented on code in PR #4566:
URL: https://github.com/apache/calcite/pull/4566#discussion_r2412797496
##########
core/src/main/java/org/apache/calcite/rel/metadata/RelMdFunctionalDependency.java:
##########
@@ -64,212 +78,395 @@ protected RelMdFunctionalDependency() {}
return BuiltInMetadata.FunctionalDependency.DEF;
}
+ /**
+ * Determines whether the specified column is functionally dependent on the
given key.
+ *
+ * @param rel Relational node
+ * @param mq Metadata query
+ * @param determinant Determinant column ordinal
+ * @param dependent Dependent column ordinal
+ * @return true if column is functionally dependent on key, false otherwise
+ */
public @Nullable Boolean determines(RelNode rel, RelMetadataQuery mq,
- int key, int column) {
- return determinesImpl2(rel, mq, key, column);
+ int determinant, int dependent) {
+ return determinesSet(rel, mq, ImmutableBitSet.of(determinant),
ImmutableBitSet.of(dependent));
+ }
+
+ /**
+ * Determines whether a set of columns functionally determines another set
of columns.
+ *
+ * @param rel Relational node
+ * @param mq Metadata query
+ * @param determinants Determinant column set
+ * @param dependents Dependent column set
+ * @return true if dependents are functionally determined by determinants,
false otherwise
+ */
+ public Boolean determinesSet(RelNode rel, RelMetadataQuery mq,
+ ImmutableBitSet determinants, ImmutableBitSet dependents) {
+ ArrowSet fdSet = getFDs(rel, mq);
+ return fdSet.implies(determinants, dependents);
}
- public @Nullable Boolean determines(SetOp rel, RelMetadataQuery mq,
- int key, int column) {
- return determinesImpl2(rel, mq, key, column);
+ /**
+ * Computes the closure of a set of column ordinals under all functional
dependencies.
+ *
+ * @param rel Relational node
+ * @param mq Metadata query
+ * @param ordinals Column ordinals
+ * @return Closure of the column ordinals
+ */
+ public ImmutableBitSet computeClosure(RelNode rel, RelMetadataQuery mq,
+ ImmutableBitSet ordinals) {
+ ArrowSet fdSet = getFDs(rel, mq);
+ return fdSet.computeClosure(ordinals);
}
- public @Nullable Boolean determines(Join rel, RelMetadataQuery mq,
- int key, int column) {
- return determinesImpl2(rel, mq, key, column);
+ /**
+ * Finds candidate keys or super keys within the specified attribute set.
+ *
+ * @param rel Relational node
+ * @param mq Metadata query
+ * @param ordinals Column ordinals
+ * @param onlyMinimalKeys Whether to return only minimal candidate keys
+ * @return Set of candidate keys or super keys
+ */
+ public Set<ImmutableBitSet> findCandidateKeysOrSuperKeys(
+ RelNode rel, RelMetadataQuery mq, ImmutableBitSet ordinals, boolean
onlyMinimalKeys) {
+ ArrowSet fdSet = getFDs(rel, mq);
+ return fdSet.findCandidateKeysOrSuperKeys(ordinals, onlyMinimalKeys);
}
- public @Nullable Boolean determines(Correlate rel, RelMetadataQuery mq,
- int key, int column) {
- return determinesImpl2(rel, mq, key, column);
+ /**
+ * Gets the functional dependency set for the specified relational node.
+ * Dispatches to the appropriate handler based on node type.
+ */
+ public ArrowSet getFDs(RelNode rel, RelMetadataQuery mq) {
+ rel = rel.stripped();
+ if (rel instanceof TableScan) {
+ return getTableScanFD((TableScan) rel);
+ } else if (rel instanceof Project) {
+ return getProjectFD((Project) rel, mq);
+ } else if (rel instanceof Aggregate) {
+ return getAggregateFD((Aggregate) rel, mq);
+ } else if (rel instanceof Join) {
+ return getJoinFD((Join) rel, mq);
+ } else if (rel instanceof Calc) {
+ return getCalcFD((Calc) rel, mq);
+ } else if (rel instanceof Filter) {
+ return getFilterFD((Filter) rel, mq);
+ } else if (rel instanceof SetOp) {
+ // TODO: Handle UNION, INTERSECT, EXCEPT functional dependencies
+ return ArrowSet.EMPTY;
+ } else if (rel instanceof Correlate) {
+ // TODO: Handle CORRELATE functional dependencies
+ return ArrowSet.EMPTY;
+ }
+ return getFD(rel.getInputs(), mq);
}
- public @Nullable Boolean determines(Aggregate rel, RelMetadataQuery mq,
- int key, int column) {
- return determinesImpl(rel, mq, key, column);
+ /**
+ * Gets the functional dependencies of input nodes.
+ * For multi-input nodes without specific logic, returns an empty set.
+ */
+ private ArrowSet getFD(List<RelNode> inputs, RelMetadataQuery mq) {
+ if (inputs.size() != 1) {
+ // Conservative approach for multi-input nodes without specific logic
+ return ArrowSet.EMPTY;
+ }
+ return getFDs(inputs.get(0), mq);
}
- public @Nullable Boolean determines(Calc rel, RelMetadataQuery mq,
- int key, int column) {
- return determinesImpl(rel, mq, key, column);
+ /**
+ * Gets the functional dependencies for a TableScan node.
+ * The table's primary key determines all other columns.
+ */
+ private static ArrowSet getTableScanFD(TableScan rel) {
+ ArrowSet.Builder fdBuilder = new ArrowSet.Builder();
+
+ RelOptTable table = rel.getTable();
+ List<ImmutableBitSet> keys = table.getKeys();
+ if (keys == null || keys.isEmpty()) {
+ return fdBuilder.build();
+ }
+
+ for (ImmutableBitSet key : keys) {
+ ImmutableBitSet allColumns =
ImmutableBitSet.range(rel.getRowType().getFieldCount());
+ ImmutableBitSet dependents = allColumns.except(key);
+ if (!dependents.isEmpty()) {
+ fdBuilder.addArrow(key, dependents);
+ }
+ }
+
+ return fdBuilder.build();
}
- public @Nullable Boolean determines(Project rel, RelMetadataQuery mq,
- int key, int column) {
- return determinesImpl(rel, mq, key, column);
+ /**
+ * Gets the functional dependencies for a Project node.
+ * Maps input dependencies through projection expressions.
+ */
+ private ArrowSet getProjectFD(Project rel, RelMetadataQuery mq) {
+ return getProjectionFD(rel.getInput(), rel.getProjects(), mq);
}
/**
- * Checks if a column is functionally determined by a key column through
expression analysis.
+ * Computes the functional dependencies for projection operations
(Project/Calc).
*
- * @param rel The input relation
- * @param mq Metadata query instance
- * @param key Index of the determinant expression
- * @param column Index of the dependent expression
- * @return TRUE if column is determined by key,
- * FALSE if not determined,
- * NULL if undetermined
+ * @param input Input relation
+ * @param projections List of projection expressions
+ * @param mq Metadata query
+ * @return Functional dependency set after projection
*/
- private static @Nullable Boolean determinesImpl(RelNode rel,
RelMetadataQuery mq,
- int key, int column) {
- if (preCheck(rel, key, column)) {
- return true;
- }
-
- ImmutableBitSet keyInputIndices = null;
- ImmutableBitSet columnInputIndices = null;
- if (rel instanceof Project || rel instanceof Calc) {
- List<RexNode> exprs = null;
- if (rel instanceof Project) {
- Project project = (Project) rel;
- exprs = project.getProjects();
- } else {
- Calc calc = (Calc) rel;
- final RexProgram program = calc.getProgram();
- exprs = program.expandList(program.getProjectList());
+ private ArrowSet getProjectionFD(
+ RelNode input, List<RexNode> projections, RelMetadataQuery mq) {
+ ArrowSet inputFdSet = getFDs(input, mq);
+ ArrowSet.Builder fdBuilder = new ArrowSet.Builder();
+
+ // Create mapping from input column indices to project column indices
+ Mappings.TargetMapping inputToOutputMap =
+ RelOptUtil.permutation(projections, input.getRowType()).inverse();
+
+ // Map input functional dependencies to project dependencies
+ mapInputFDs(inputFdSet, inputToOutputMap, fdBuilder);
+
+ int fieldCount = projections.size();
+ final ImmutableBitSet[] inputBits = new ImmutableBitSet[fieldCount];
+ final Map<RexNode, Integer> uniqueExprToIndex = new HashMap<>();
+ final Map<RexLiteral, Integer> literalToIndex = new HashMap<>();
+ final Map<RexInputRef, Integer> refToIndex = new HashMap<>();
+ for (int i = 0; i < fieldCount; i++) {
+ RexNode expr = projections.get(i);
+
+ // Skip non-deterministic expressions
+ if (!RexUtil.isDeterministic(expr)) {
+ continue;
}
- // TODO: Supports dependency analysis for all types of expressions
- if (!(exprs.get(column) instanceof RexInputRef)) {
- return false;
+ // Handle identical expressions in the projection list
+ Integer prev = uniqueExprToIndex.putIfAbsent(expr, i);
+ if (prev != null) {
+ fdBuilder.addBidirectionalArrow(prev, i);
}
- RexNode keyExpr = exprs.get(key);
- RexNode columnExpr = exprs.get(column);
+ // Track literal constants to handle them specially
+ if (expr instanceof RexLiteral) {
+ literalToIndex.put((RexLiteral) expr, i);
+ continue;
+ }
- // Identical expressions imply functional dependency
- if (keyExpr.equals(columnExpr)) {
- return true;
+ if (expr instanceof RexInputRef) {
+ refToIndex.put((RexInputRef) expr, i);
+ inputBits[i] = ImmutableBitSet.of(((RexInputRef) expr).getIndex());
}
- keyInputIndices = extractDeterministicRefs(keyExpr);
- columnInputIndices = extractDeterministicRefs(columnExpr);
- } else if (rel instanceof Aggregate) {
- Aggregate aggregate = (Aggregate) rel;
+ inputBits[i] = RelOptUtil.InputFinder.bits(expr);
+ }
+
+ // Remove literals from uniqueExprToIndex to avoid redundant processing
+ uniqueExprToIndex.keySet().removeIf(key -> key instanceof RexLiteral);
+
+ for (Map.Entry<RexNode, Integer> entry : uniqueExprToIndex.entrySet()) {
+ RexNode expr = entry.getKey();
+ Integer i = entry.getValue();
+
+ // All columns determine literals
+ literalToIndex.values()
+ .forEach(l -> fdBuilder.addArrow(i, l));
+
+ // Input columns determine identical expressions
+ refToIndex.forEach((k, v) -> {
+ ImmutableBitSet refIndex = ImmutableBitSet.of(k.getIndex());
+ ImmutableBitSet bitSet = expr instanceof RexInputRef
+ ? ImmutableBitSet.of(((RexInputRef) expr).getIndex())
+ : inputBits[i];
+ if (inputFdSet.implies(refIndex, bitSet)) {
+ fdBuilder.addArrow(v, i);
+ }
+ });
+ }
+
+ return fdBuilder.build();
+ }
- int groupByCnt = aggregate.getGroupCount();
- if (key < groupByCnt && column >= groupByCnt) {
- return false;
+ /**
+ * Maps input functional dependencies to output dependencies based on column
mapping.
+ */
+ private static void mapInputFDs(ArrowSet inputFdSet,
+ Mappings.TargetMapping mapping, ArrowSet.Builder outputFdBuilder) {
+ for (Arrow inputFd : inputFdSet.getArrows()) {
+ ImmutableBitSet determinants = inputFd.getDeterminants();
+ ImmutableBitSet dependents = inputFd.getDependents();
+
+ // Map all determinant columns
+ ImmutableBitSet mappedDeterminants = mapAllCols(determinants, mapping);
+ if (mappedDeterminants.isEmpty()) {
+ continue;
}
- keyInputIndices = extractDeterministicRefs(aggregate, key);
- columnInputIndices = extractDeterministicRefs(aggregate, column);
- } else {
- throw new UnsupportedOperationException("Unsupported RelNode type: "
- + rel.getClass().getSimpleName());
+ // Map only the dependent columns that can be mapped
+ ImmutableBitSet mappedDependents = mapAvailableCols(dependents, mapping);
+ if (!mappedDependents.isEmpty()) {
+ outputFdBuilder.addArrow(mappedDeterminants, mappedDependents);
+ }
}
+ }
- // Early return if invalid cases
- if (keyInputIndices.isEmpty()
- || columnInputIndices.isEmpty()) {
- return false;
+ /**
+ * Maps all column ordinals in the set. Returns an empty set if any column
cannot be mapped.
+ */
+ private static ImmutableBitSet mapAllCols(
+ ImmutableBitSet ordinals, Mappings.TargetMapping mapping) {
+ ImmutableBitSet.Builder builder = ImmutableBitSet.builder();
+ for (int ord : ordinals) {
+ int mappedOrd = mapping.getTargetOpt(ord);
+ if (mappedOrd < 0) {
+ return ImmutableBitSet.of();
+ }
+ builder.set(mappedOrd);
}
+ return builder.build();
+ }
- // Currently only supports multiple (keyInputIndices) to one
(columnInputIndices)
- // dependency detection
- for (Integer keyRef : keyInputIndices) {
- if (Boolean.FALSE.equals(
- mq.determines(rel.getInput(0), keyRef,
- columnInputIndices.nextSetBit(0)))) {
- return false;
+ /**
+ * Maps only the column ordinals that can be mapped, ignoring unmappable
ones.
+ */
+ private static ImmutableBitSet mapAvailableCols(
+ ImmutableBitSet ordinals, Mappings.TargetMapping mapping) {
+ ImmutableBitSet.Builder builder = ImmutableBitSet.builder();
+ for (int ord : ordinals) {
+ int mappedOrd = mapping.getTargetOpt(ord);
+ if (mappedOrd >= 0) {
+ builder.set(mappedOrd);
}
}
-
- return true;
+ return builder.build();
}
/**
- * determinesImpl2is similar to determinesImpl, but it doesn't need to
handle the
- * mapping between output and input columns.
+ * Gets the functional dependencies for an Aggregate node.
+ * Group keys determine all aggregate columns.
+ * Preserves input dependencies that only involve group columns.
*/
- private static @Nullable Boolean determinesImpl2(RelNode rel,
RelMetadataQuery mq,
- int key, int column) {
- if (preCheck(rel, key, column)) {
- return true;
+ private ArrowSet getAggregateFD(Aggregate rel, RelMetadataQuery mq) {
+ ArrowSet.Builder fdBuilder = new ArrowSet.Builder();
+ ArrowSet inputFdSet = getFDs(rel.getInput(), mq);
+
+ ImmutableBitSet groupSet = rel.getGroupSet();
+
+ // Preserve input FDs that only involve group columns
+ if (Aggregate.isSimple(rel)) {
+ for (Arrow inputFd : inputFdSet.getArrows()) {
+ ImmutableBitSet determinants = inputFd.getDeterminants();
+ ImmutableBitSet dependents = inputFd.getDependents();
+
+ // Only preserve if both determinants and dependents are within group
columns
+ if (groupSet.contains(determinants) && groupSet.contains(dependents)) {
+ fdBuilder.addArrow(determinants, dependents);
+ }
+ }
}
- if (rel instanceof TableScan) {
- TableScan tableScan = (TableScan) rel;
- RelOptTable table = tableScan.getTable();
- List<ImmutableBitSet> keys = table.getKeys();
- return keys != null
- && keys.size() == 1
- && keys.get(0).equals(ImmutableBitSet.of(column));
- } else if (rel instanceof Join) {
- Join join = (Join) rel;
- // TODO Considering column mapping based on equality conditions in join
- int leftFieldCnt = join.getLeft().getRowType().getFieldCount();
- if (key < leftFieldCnt && column < leftFieldCnt) {
- return mq.determines(join.getLeft(), key, column);
- } else if (key >= leftFieldCnt && column >= leftFieldCnt) {
- return mq.determines(join.getRight(), key - leftFieldCnt, column -
leftFieldCnt);
+ // Group keys determine all aggregate columns
+ if (!groupSet.isEmpty() && !rel.getAggCallList().isEmpty()) {
+ for (int i = rel.getGroupCount(); i < rel.getRowType().getFieldCount();
i++) {
+ fdBuilder.addArrow(groupSet, ImmutableBitSet.of(i));
Review Comment:
@julianhyde I've created a new JIRA ticket
[CALCITE-7218](https://issues.apache.org/jira/browse/CALCITE-7218) for this.
--
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]
