oleg-zinovev commented on code in PR #12096:
URL: https://github.com/apache/ignite/pull/12096#discussion_r3442291753
##########
modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/rel/IgniteWindow.java:
##########
@@ -135,123 +137,159 @@ public boolean isStreaming() {
}
/** {@inheritDoc} */
- @Override public RelOptCost computeSelfCost(RelOptPlanner planner,
RelMetadataQuery mq) {
- IgniteCostFactory costFactory =
(IgniteCostFactory)planner.getCostFactory();
-
- int aggCnt = grp.aggCalls.size();
-
- double rowCnt = mq.getRowCount(getInput());
- double cpuCost = rowCnt * ROW_COMPARISON_COST;
- double memCost = (getRowType().getFieldCount() * AVERAGE_FIELD_SIZE +
aggCnt * AGG_CALL_MEM_COST) * (streaming ? 1.0 : rowCnt);
-
- RelOptCost cost = costFactory.makeCost(rowCnt, cpuCost, 0, memCost, 0);
-
- // Distributed processing is more preferable than processing on the
single node.
- if
(TraitUtils.distribution(traitSet).satisfies(IgniteDistributions.single()))
- cost = cost.plus(costFactory.makeTinyCost());
+ @Override public Pair<RelTraitSet, List<RelTraitSet>>
passThroughTraits(RelTraitSet required) {
+ if (required.getConvention() != IgniteConvention.INSTANCE)
+ return null;
- return cost;
- }
+ if (!satisfiesDistribution(TraitUtils.distribution(required)))
+ return null;
- /** {@inheritDoc} */
- @Override public Pair<RelTraitSet, List<RelTraitSet>>
passThroughTraits(RelTraitSet required) {
- RelTraitSet traits = passThroughOrDerivedTraits(required, true);
- if (traits == null)
+ RelCollation requiredCollation = TraitUtils.collation(required);
+ RelCollation relCollation = TraitUtils.collation(traitSet);
+ if (satisfiesCollationSansGroupFields(relCollation, requiredCollation))
+ required =
required.replace(adjustGroupFieldsCollation(relCollation, requiredCollation));
+ else if (satisfiesCollationSansGroupFields(requiredCollation,
relCollation))
+ required = required.replace(truncateCollation(requiredCollation));
+ else
return null;
- return Pair.of(traits, ImmutableList.of(traits));
+ return Pair.of(required, ImmutableList.of(required));
}
/** {@inheritDoc} */
@Override public Pair<RelTraitSet, List<RelTraitSet>>
deriveTraits(RelTraitSet childTraits, int childId) {
assert childId == 0;
- RelTraitSet traits = passThroughOrDerivedTraits(childTraits, false);
- if (traits == null)
+ if (childTraits.getConvention() != IgniteConvention.INSTANCE)
+ return null;
+
+ RelCollation childCollation = TraitUtils.collation(childTraits);
+ RelCollation relCollation = TraitUtils.collation(traitSet);
+ if (satisfiesCollationSansGroupFields(relCollation, childCollation))
+ childTraits =
childTraits.replace(adjustGroupFieldsCollation(relCollation, childCollation));
+ else if (!satisfiesCollationSansGroupFields(childCollation,
relCollation))
return null;
- return Pair.of(traits, ImmutableList.of(traits));
+ // If a child node has the appropriate collation but not the required
distribution
+ // (e.g., a randomly distributed table that has the index we need),
+ // we can use its collation to eliminate extra sorting.
+ // However, we must replace the distribution with current window one.
+ if (!satisfiesDistribution(TraitUtils.distribution(childTraits)))
+ childTraits = childTraits.replace(distribution());
+
+ return Pair.of(childTraits, ImmutableList.of(childTraits));
}
- /**
- * Propagates the trait set from the parent to the child, or derives it
from the child node.
- *
- * <p>The Window node cannot independently satisfy any traits. Therefore:
- * - Validate that collation and distribution traits are compatible with
the Window node.
- * - If they are not, replace them with suitable traits.
- * - Request a new trait set from the input accordingly.
- */
- private @Nullable RelTraitSet passThroughOrDerivedTraits(RelTraitSet
target, boolean passThrough) {
- if (target.getConvention() != IgniteConvention.INSTANCE)
- return null;
+ /** {@inheritDoc} */
+ @Override public RelOptCost computeSelfCost(RelOptPlanner planner,
RelMetadataQuery mq) {
+ IgniteCostFactory costFactory =
(IgniteCostFactory)planner.getCostFactory();
- RelTraitSet traits = target;
- RelCollation requiredCollation = TraitUtils.collation(target);
- if (!satisfiesCollationSansGroupFields(requiredCollation))
- traits = traits.replace(collation());
- else if (passThrough) {
- // In case of pass through, required collation can use fields
outside of input row type.
- // So, we should truncate required collation to input row type.
- // We do not need any additional range checks, since current
collation keys is a prefix to required collation keys.
- // Therefore, only additional keys in suffix can be removed here.
- List<RelFieldCollation> requiredCollationFields =
requiredCollation.getFieldCollations();
- for (int i = 0; i < requiredCollationFields.size(); i++) {
- if (requiredCollationFields.get(i).getFieldIndex() >=
input.getRowType().getFieldCount()) {
- traits =
traits.replace(RelCollations.of(requiredCollationFields.subList(0, i)));
- break;
- }
- }
- }
+ int aggCnt = grp.aggCalls.size();
- IgniteDistribution distribution = TraitUtils.distribution(target);
- if (!satisfiesDistribution(distribution))
- traits = traits.replace(distribution());
+ double rowCnt = mq.getRowCount(getInput());
+ double cpuCost = rowCnt * ROW_COMPARISON_COST;
+ double memCost = (getRowType().getFieldCount() * AVERAGE_FIELD_SIZE +
aggCnt * AGG_CALL_MEM_COST) * (streaming ? 1.0 : rowCnt);
- if (traits == traitSet)
- // New traits equal to current traits of window.
- // No need to pass throught or derive any.
- return null;
+ RelOptCost cost = costFactory.makeCost(rowCnt, cpuCost, 0, memCost, 0);
- return traits;
+ // Distributed processing is more preferable than processing on the
single node.
+ if
(TraitUtils.distribution(traitSet).satisfies(IgniteDistributions.single()))
+ cost = cost.plus(costFactory.makeTinyCost());
+
+ return cost;
}
- /** Check input distribution satisfies collation of this window. */
- private boolean satisfiesDistribution(IgniteDistribution
desiredDistribution) {
- if (desiredDistribution.satisfies(IgniteDistributions.single()) ||
desiredDistribution.function().correlated())
+ /** Check input distribution satisfies distribution of this window. */
+ private boolean satisfiesDistribution(IgniteDistribution required) {
+ if (required.satisfies(IgniteDistributions.single()) ||
required.function().correlated())
return true;
- if (desiredDistribution.getType() ==
RelDistribution.Type.HASH_DISTRIBUTED)
- return
grp.keys.contains(ImmutableBitSet.of(desiredDistribution.getKeys()));
+ if (required.getType() == RelDistribution.Type.HASH_DISTRIBUTED)
+ return grp.keys.contains(ImmutableBitSet.of(required.getKeys()));
return false;
}
/**
- * Check input collation satisfies collation of this window.
- * - Collations field indicies of the window should be a prefix for
desired collation.
+ * Check left collation satisfies right one.
+ * - Collations field indicies of the right should be a prefix for left
collation.
* - Group fields sort direction can be changed to desired collation.
* - Order fields sort direction should be the same as in desired
collation.
*/
- private boolean satisfiesCollationSansGroupFields(RelCollation
desiredCollation) {
- RelCollation collation = collation();
- if (desiredCollation.satisfies(collation))
+ private boolean satisfiesCollationSansGroupFields(RelCollation left,
RelCollation right) {
+ if (left.satisfies(right))
return true;
- if (desiredCollation.getFieldCollations().size() <
collation.getFieldCollations().size())
+ int leftFldCnt = left.getFieldCollations().size();
+ int rightFldCnt = right.getFieldCollations().size();
+ if (leftFldCnt < rightFldCnt)
return false;
int grpKeysSize = grp.keys.cardinality();
+ assert leftFldCnt >= grpKeysSize || rightFldCnt >= grpKeysSize;
+
// Check group keys (collation field order and direction meaningless).
// Since window collation starts with group keys with 'default'
sorting direction,
// desired collation should start with same fields in any order / with
any direction.
- ImmutableBitSet desiredGrpFields =
ImmutableBitSet.of(Util.first(desiredCollation.getKeys(), grpKeysSize));
- if (!desiredGrpFields.equals(grp.keys))
+ int rightGrpFldsCnt = Math.min(grpKeysSize, rightFldCnt);
+ ImmutableBitSet leftGrpFlds =
ImmutableBitSet.of(Util.first(left.getKeys(), grpKeysSize));
+ ImmutableBitSet rightGrpFlds =
ImmutableBitSet.of(Util.first(right.getKeys(), rightGrpFldsCnt));
+ if (!leftGrpFlds.contains(rightGrpFlds))
return false;
+ else if (grpKeysSize >= rightFldCnt)
+ // Right collation fiels in group keys only
Review Comment:
fixed
##########
modules/calcite/src/main/java/org/apache/ignite/internal/processors/query/calcite/rel/IgniteWindow.java:
##########
@@ -135,123 +137,159 @@ public boolean isStreaming() {
}
/** {@inheritDoc} */
- @Override public RelOptCost computeSelfCost(RelOptPlanner planner,
RelMetadataQuery mq) {
- IgniteCostFactory costFactory =
(IgniteCostFactory)planner.getCostFactory();
-
- int aggCnt = grp.aggCalls.size();
-
- double rowCnt = mq.getRowCount(getInput());
- double cpuCost = rowCnt * ROW_COMPARISON_COST;
- double memCost = (getRowType().getFieldCount() * AVERAGE_FIELD_SIZE +
aggCnt * AGG_CALL_MEM_COST) * (streaming ? 1.0 : rowCnt);
-
- RelOptCost cost = costFactory.makeCost(rowCnt, cpuCost, 0, memCost, 0);
-
- // Distributed processing is more preferable than processing on the
single node.
- if
(TraitUtils.distribution(traitSet).satisfies(IgniteDistributions.single()))
- cost = cost.plus(costFactory.makeTinyCost());
+ @Override public Pair<RelTraitSet, List<RelTraitSet>>
passThroughTraits(RelTraitSet required) {
+ if (required.getConvention() != IgniteConvention.INSTANCE)
+ return null;
- return cost;
- }
+ if (!satisfiesDistribution(TraitUtils.distribution(required)))
+ return null;
- /** {@inheritDoc} */
- @Override public Pair<RelTraitSet, List<RelTraitSet>>
passThroughTraits(RelTraitSet required) {
- RelTraitSet traits = passThroughOrDerivedTraits(required, true);
- if (traits == null)
+ RelCollation requiredCollation = TraitUtils.collation(required);
+ RelCollation relCollation = TraitUtils.collation(traitSet);
+ if (satisfiesCollationSansGroupFields(relCollation, requiredCollation))
+ required =
required.replace(adjustGroupFieldsCollation(relCollation, requiredCollation));
+ else if (satisfiesCollationSansGroupFields(requiredCollation,
relCollation))
+ required = required.replace(truncateCollation(requiredCollation));
+ else
return null;
- return Pair.of(traits, ImmutableList.of(traits));
+ return Pair.of(required, ImmutableList.of(required));
}
/** {@inheritDoc} */
@Override public Pair<RelTraitSet, List<RelTraitSet>>
deriveTraits(RelTraitSet childTraits, int childId) {
assert childId == 0;
- RelTraitSet traits = passThroughOrDerivedTraits(childTraits, false);
- if (traits == null)
+ if (childTraits.getConvention() != IgniteConvention.INSTANCE)
+ return null;
+
+ RelCollation childCollation = TraitUtils.collation(childTraits);
+ RelCollation relCollation = TraitUtils.collation(traitSet);
+ if (satisfiesCollationSansGroupFields(relCollation, childCollation))
+ childTraits =
childTraits.replace(adjustGroupFieldsCollation(relCollation, childCollation));
+ else if (!satisfiesCollationSansGroupFields(childCollation,
relCollation))
return null;
- return Pair.of(traits, ImmutableList.of(traits));
+ // If a child node has the appropriate collation but not the required
distribution
+ // (e.g., a randomly distributed table that has the index we need),
+ // we can use its collation to eliminate extra sorting.
+ // However, we must replace the distribution with current window one.
+ if (!satisfiesDistribution(TraitUtils.distribution(childTraits)))
+ childTraits = childTraits.replace(distribution());
+
+ return Pair.of(childTraits, ImmutableList.of(childTraits));
}
- /**
- * Propagates the trait set from the parent to the child, or derives it
from the child node.
- *
- * <p>The Window node cannot independently satisfy any traits. Therefore:
- * - Validate that collation and distribution traits are compatible with
the Window node.
- * - If they are not, replace them with suitable traits.
- * - Request a new trait set from the input accordingly.
- */
- private @Nullable RelTraitSet passThroughOrDerivedTraits(RelTraitSet
target, boolean passThrough) {
- if (target.getConvention() != IgniteConvention.INSTANCE)
- return null;
+ /** {@inheritDoc} */
+ @Override public RelOptCost computeSelfCost(RelOptPlanner planner,
RelMetadataQuery mq) {
+ IgniteCostFactory costFactory =
(IgniteCostFactory)planner.getCostFactory();
- RelTraitSet traits = target;
- RelCollation requiredCollation = TraitUtils.collation(target);
- if (!satisfiesCollationSansGroupFields(requiredCollation))
- traits = traits.replace(collation());
- else if (passThrough) {
- // In case of pass through, required collation can use fields
outside of input row type.
- // So, we should truncate required collation to input row type.
- // We do not need any additional range checks, since current
collation keys is a prefix to required collation keys.
- // Therefore, only additional keys in suffix can be removed here.
- List<RelFieldCollation> requiredCollationFields =
requiredCollation.getFieldCollations();
- for (int i = 0; i < requiredCollationFields.size(); i++) {
- if (requiredCollationFields.get(i).getFieldIndex() >=
input.getRowType().getFieldCount()) {
- traits =
traits.replace(RelCollations.of(requiredCollationFields.subList(0, i)));
- break;
- }
- }
- }
+ int aggCnt = grp.aggCalls.size();
- IgniteDistribution distribution = TraitUtils.distribution(target);
- if (!satisfiesDistribution(distribution))
- traits = traits.replace(distribution());
+ double rowCnt = mq.getRowCount(getInput());
+ double cpuCost = rowCnt * ROW_COMPARISON_COST;
+ double memCost = (getRowType().getFieldCount() * AVERAGE_FIELD_SIZE +
aggCnt * AGG_CALL_MEM_COST) * (streaming ? 1.0 : rowCnt);
- if (traits == traitSet)
- // New traits equal to current traits of window.
- // No need to pass throught or derive any.
- return null;
+ RelOptCost cost = costFactory.makeCost(rowCnt, cpuCost, 0, memCost, 0);
- return traits;
+ // Distributed processing is more preferable than processing on the
single node.
+ if
(TraitUtils.distribution(traitSet).satisfies(IgniteDistributions.single()))
+ cost = cost.plus(costFactory.makeTinyCost());
+
+ return cost;
}
- /** Check input distribution satisfies collation of this window. */
- private boolean satisfiesDistribution(IgniteDistribution
desiredDistribution) {
- if (desiredDistribution.satisfies(IgniteDistributions.single()) ||
desiredDistribution.function().correlated())
+ /** Check input distribution satisfies distribution of this window. */
+ private boolean satisfiesDistribution(IgniteDistribution required) {
+ if (required.satisfies(IgniteDistributions.single()) ||
required.function().correlated())
return true;
- if (desiredDistribution.getType() ==
RelDistribution.Type.HASH_DISTRIBUTED)
- return
grp.keys.contains(ImmutableBitSet.of(desiredDistribution.getKeys()));
+ if (required.getType() == RelDistribution.Type.HASH_DISTRIBUTED)
+ return grp.keys.contains(ImmutableBitSet.of(required.getKeys()));
return false;
}
/**
- * Check input collation satisfies collation of this window.
- * - Collations field indicies of the window should be a prefix for
desired collation.
+ * Check left collation satisfies right one.
+ * - Collations field indicies of the right should be a prefix for left
collation.
* - Group fields sort direction can be changed to desired collation.
* - Order fields sort direction should be the same as in desired
collation.
*/
- private boolean satisfiesCollationSansGroupFields(RelCollation
desiredCollation) {
- RelCollation collation = collation();
- if (desiredCollation.satisfies(collation))
+ private boolean satisfiesCollationSansGroupFields(RelCollation left,
RelCollation right) {
+ if (left.satisfies(right))
return true;
- if (desiredCollation.getFieldCollations().size() <
collation.getFieldCollations().size())
+ int leftFldCnt = left.getFieldCollations().size();
+ int rightFldCnt = right.getFieldCollations().size();
+ if (leftFldCnt < rightFldCnt)
return false;
int grpKeysSize = grp.keys.cardinality();
+ assert leftFldCnt >= grpKeysSize || rightFldCnt >= grpKeysSize;
+
// Check group keys (collation field order and direction meaningless).
// Since window collation starts with group keys with 'default'
sorting direction,
// desired collation should start with same fields in any order / with
any direction.
- ImmutableBitSet desiredGrpFields =
ImmutableBitSet.of(Util.first(desiredCollation.getKeys(), grpKeysSize));
- if (!desiredGrpFields.equals(grp.keys))
+ int rightGrpFldsCnt = Math.min(grpKeysSize, rightFldCnt);
+ ImmutableBitSet leftGrpFlds =
ImmutableBitSet.of(Util.first(left.getKeys(), grpKeysSize));
+ ImmutableBitSet rightGrpFlds =
ImmutableBitSet.of(Util.first(right.getKeys(), rightGrpFldsCnt));
+ if (!leftGrpFlds.contains(rightGrpFlds))
return false;
+ else if (grpKeysSize >= rightFldCnt)
+ // Right collation fiels in group keys only
+ return true;
// Check remaining collation (collation field order and direction
meaningfull).
- List<RelFieldCollation> desiredFieldCollations =
Util.skip(desiredCollation.getFieldCollations(), grpKeysSize);
- List<RelFieldCollation> fieldCollations =
Util.skip(collation.getFieldCollations(), grpKeysSize);
- return Util.startsWith(desiredFieldCollations, fieldCollations);
+ List<RelFieldCollation> leftFldCollations =
Util.skip(left.getFieldCollations(), grpKeysSize);
+ List<RelFieldCollation> rightFldCollations =
Util.skip(right.getFieldCollations(), grpKeysSize);
+ return Util.startsWith(rightFldCollations, leftFldCollations);
+ }
+
+ /** */
+ private RelCollation adjustGroupFieldsCollation(RelCollation relCollation,
RelCollation requiredCollation) {
+ // Current collation satisfies required collation, but group fields in
prefix may have invalid field collation.
+ // So, we should replace it with field collation from required.
+ List<RelFieldCollation> fldCollations = new
ArrayList<>(relCollation.getFieldCollations().size());
+
+ int grpFldCnt = grp.keys.cardinality();
+ IntMap<RelFieldCollation> currGrpFldCollations = new
IntHashMap<>(grpFldCnt);
+ for (int i = 0; i < grpFldCnt; i++) {
+ RelFieldCollation grpFldCollation =
relCollation.getFieldCollations().get(i);
+ currGrpFldCollations.put(grpFldCollation.getFieldIndex(),
grpFldCollation);
+ }
+
+ int requiredGrpFldCnt =
Math.min(requiredCollation.getFieldCollations().size(), grpFldCnt);
+ for (int i = 0; i < requiredGrpFldCnt; i++) {
+ RelFieldCollation requiredGrpFldCollation =
requiredCollation.getFieldCollations().get(i);
+ fldCollations.add(requiredGrpFldCollation);
+
+ assert
currGrpFldCollations.containsKey(requiredGrpFldCollation.getFieldIndex());
+
currGrpFldCollations.remove(requiredGrpFldCollation.getFieldIndex());
+ }
+
+ // Add remaining group fields collation.
+ fldCollations.addAll(currGrpFldCollations.values());
+
+ // Add remaining fields collation.
+ fldCollations.addAll(Util.skip(relCollation.getFieldCollations(),
grpFldCnt));
+
+ return RelCollations.of(fldCollations);
+ }
+
+ /** */
+ private RelCollation truncateCollation(RelCollation requiredCollation) {
+ // In case of pass through, required collation can use fields outside
of input row type.
+ // So, we should truncate required collation to input row type.
+ // We do not need any additional range checks, since current collation
keys is a prefix to required collation keys.
+ // Therefore, only additional keys in suffix can be removed here.
+ List<RelFieldCollation> requiredCollationFields =
requiredCollation.getFieldCollations();
+ for (int i = 0; i < requiredCollationFields.size(); i++) {
+ if (requiredCollationFields.get(i).getFieldIndex() >=
input.getRowType().getFieldCount()) {
Review Comment:
done
--
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]
