[
https://issues.apache.org/jira/browse/CALCITE-3118?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Botong Huang updated CALCITE-3118:
----------------------------------
Description:
In VolcanoRuleCall.matchRecurse(), when ascending (child operand is matched,
looking for parent operand match), we want to check that the matched parent
indeed has the previously matched RelNode as a child *with the* *expected child
ordinal*.
However, there is a bug in this child ordinal check:
{noformat}
333 if (ascending && operand.childPolicy !=
RelOptRuleOperandChildPolicy.UNORDERED) {
334 // We know that the previous operand was *a* child of its parent,
335 // but now check that it is the *correct* child.
336 final RelSubset input =
337 (RelSubset) rel.getInput(previousOperand.ordinalInParent);
338 List<RelNode> inputRels = input.set.getRelsFromAllSubsets();
339 if (!inputRels.contains(previous)) {
340 continue;
341 }
342 }
{noformat}
We intend to make sure that "previous" is in Subset "input". However line 338
looked at RelNodes from the entire RelSet, rather than RelNodes only in Subset
"input". As a result, in some cases, incorrect parent is not skipped as
expected and matched incorrectly.
The unit test case included is a case that triggers this bug, where a second
child RelNode incorrectly get matched as the first child of the parent RelNode.
--------------------------
Here's a detailed explanation of the test case that triggers the bug
We constructed a RelNode structure:
{noformat}
PhysBiRel
/ \
Subset1 Subset2
| |
leftPhy rightPhy
{noformat}
Where PhysBiRel has two inputs: leftPhy and rightPhy, both are logically
equivalent, but with different traits (Convention in this test case), and thus
are in different subsets.
(Two Rels in two subsets in the same RelSet is a necessary condition to
trigger this bug. )
A rule AssertOperandsDifferentRule is constructed as follows:
{noformat}
operand(PhysBiRel.class,
operand(PhysLeafRel.class, any()),
operand(PhysLeafRel.class, any()))
{noformat}
Obviously the correct match would be:
{noformat}
PhysBiRel
/ \
leftPhy rightPhy
{noformat}
However, with the bug, another match is also returned:
{noformat}
PhysBiRel
/ \
rightPhy rightPhy
{noformat}
*This is wrong because rightPhy is not PhysBiRel's first input at all, and
should not match as parent operand's first child.*
----------------------------
Here's how the incorrect match occurs.
1. When rightPhy is registered, we attempt to match it to both the left and
right child operand of AssertOperandsDifferentRule above.
2. When matched to the right child operand, it eventually leads to the correct
match result above.
3. When matched to the left child operand, it should have skipped/failed
matching the parent operand to PhysBiRel because rightPhy is !!!!not!!!
PhysBiRel's first input.
But because of the bug, the match succeeded. After parent is matched, then it
attempt to match the right child operand, and again matched the rightPhy as
expected.
As a result, both child operand end up matching the same RelNode rightPhy.
was:In VolcanoRuleCall.matchRecurse(), when ascending (child operand is
matched, looking for parent operand match), we want to check that the matched
parent indeed has the previously matched child RelNode as a child with the
expected ordinal. However, there is a bug in this check. As a result, some
incorrect parent is not skipped as expected and matched incorrectly. See unit
test included in PR for a case that triggers this bug, where a second child
RelNode get matched as first child of the parent RelNode.
> VolcanoRuleCall match parent child ordinal not properly checked
> ---------------------------------------------------------------
>
> Key: CALCITE-3118
> URL: https://issues.apache.org/jira/browse/CALCITE-3118
> Project: Calcite
> Issue Type: Bug
> Reporter: Botong Huang
> Priority: Major
> Labels: pull-request-available
> Time Spent: 1h 10m
> Remaining Estimate: 0h
>
> In VolcanoRuleCall.matchRecurse(), when ascending (child operand is matched,
> looking for parent operand match), we want to check that the matched parent
> indeed has the previously matched RelNode as a child *with the* *expected
> child ordinal*.
> However, there is a bug in this child ordinal check:
> {noformat}
> 333 if (ascending && operand.childPolicy !=
> RelOptRuleOperandChildPolicy.UNORDERED) {
> 334 // We know that the previous operand was *a* child of its parent,
> 335 // but now check that it is the *correct* child.
> 336 final RelSubset input =
> 337 (RelSubset) rel.getInput(previousOperand.ordinalInParent);
> 338 List<RelNode> inputRels = input.set.getRelsFromAllSubsets();
> 339 if (!inputRels.contains(previous)) {
> 340 continue;
> 341 }
> 342 }
> {noformat}
> We intend to make sure that "previous" is in Subset "input". However line 338
> looked at RelNodes from the entire RelSet, rather than RelNodes only in
> Subset "input". As a result, in some cases, incorrect parent is not skipped
> as expected and matched incorrectly.
> The unit test case included is a case that triggers this bug, where a second
> child RelNode incorrectly get matched as the first child of the parent
> RelNode.
> --------------------------
> Here's a detailed explanation of the test case that triggers the bug
> We constructed a RelNode structure:
> {noformat}
> PhysBiRel
> / \
> Subset1 Subset2
> | |
> leftPhy rightPhy
> {noformat}
> Where PhysBiRel has two inputs: leftPhy and rightPhy, both are logically
> equivalent, but with different traits (Convention in this test case), and
> thus are in different subsets.
> (Two Rels in two subsets in the same RelSet is a necessary condition to
> trigger this bug. )
> A rule AssertOperandsDifferentRule is constructed as follows:
> {noformat}
> operand(PhysBiRel.class,
> operand(PhysLeafRel.class, any()),
> operand(PhysLeafRel.class, any()))
> {noformat}
> Obviously the correct match would be:
> {noformat}
> PhysBiRel
> / \
> leftPhy rightPhy
> {noformat}
> However, with the bug, another match is also returned:
> {noformat}
> PhysBiRel
> / \
> rightPhy rightPhy
> {noformat}
> *This is wrong because rightPhy is not PhysBiRel's first input at all, and
> should not match as parent operand's first child.*
> ----------------------------
> Here's how the incorrect match occurs.
> 1. When rightPhy is registered, we attempt to match it to both the left and
> right child operand of AssertOperandsDifferentRule above.
> 2. When matched to the right child operand, it eventually leads to the
> correct match result above.
> 3. When matched to the left child operand, it should have skipped/failed
> matching the parent operand to PhysBiRel because rightPhy is !!!!not!!!
> PhysBiRel's first input.
> But because of the bug, the match succeeded. After parent is matched, then
> it attempt to match the right child operand, and again matched the rightPhy
> as expected.
> As a result, both child operand end up matching the same RelNode rightPhy.
--
This message was sent by Atlassian JIRA
(v7.6.3#76005)
