opt: internal error: memo group optimization passes surpassed limit of 100000 #80901
Assignees
Labels
C-test-failure
Broken test (automatically or manually discovered).
deprecated-branch-release-22.1.0
O-roachtest
O-robot
Originated from a bot.
T-sql-queries
SQL Queries Team
Comments
cockroach-teamcity
added
deprecated-branch-release-22.1.0
C-test-failure
|
Easy to reproduce: On 22.1, it produces the internal error |
rytaft
removed
the
release-blocker
rytaft
changed the title
|
Here's a reduced reproduction: And here's what the memo looks like (click to expand)The cycle in this memo is a needle in a haystack. Maybe I should write a tool that can automatically find it... |
|
The cycle is in G14. It points to itself: |
mgartner
added a commit
to mgartner/cockroach
that referenced
this issue
May 9, 2022
The optimizer will error with "memo group optimization passes surpassed limit of 100000; there may be a cycle in the memo" when it detects a potential memo cycle. The error includes the memo in the error details to aid in debugging. However, it can be hard for a human to find the cycle in the formatted memo when it contains many groups (see cockroachdb#80901). This commit updates the formatted memo within the error details to include the path to the cycle, if one exists. A cycle is not searched for in other cases where the memo is formatted, to avoid the overhead of cycle detection. A simple cycle detection library has been added that the memo formatter uses to locate a path in a memo to a cycle. Release note: None
mgartner
added a commit
to mgartner/cockroach
that referenced
this issue
May 13, 2022
The optimizer will error with "memo group optimization passes surpassed limit of 100000; there may be a cycle in the memo" when it detects a potential memo cycle. The error includes the memo in the error details to aid in debugging. However, it can be hard for a human to find the cycle in the formatted memo when it contains many groups (see cockroachdb#80901). This commit updates the formatted memo within the error details to include the path to the cycle, if one exists. A cycle is not searched for in other cases where the memo is formatted, to avoid the overhead of cycle detection. A simple cycle detection library has been added that the memo formatter uses to locate a path in a memo to a cycle. Release note: None
mgartner
added a commit
to mgartner/cockroach
that referenced
this issue
May 24, 2022
The optimizer will error with "memo group optimization passes surpassed limit of 100000; there may be a cycle in the memo" when it detects a potential memo cycle. The error includes the memo in the error details to aid in debugging. However, it can be hard for a human to find the cycle in the formatted memo when it contains many groups (see cockroachdb#80901). This commit updates the formatted memo within the error details to include the path to the cycle, if one exists. A cycle is not searched for in other cases where the memo is formatted, to avoid the overhead of cycle detection. A simple cycle detection library has been added that the memo formatter uses to locate a path in a memo to a cycle. Release note: None
mgartner
added a commit
to mgartner/cockroach
that referenced
this issue
May 24, 2022
The optimizer will error with "memo group optimization passes surpassed limit of 100000; there may be a cycle in the memo" when it detects a potential memo cycle. The error includes the memo in the error details to aid in debugging. However, it can be hard for a human to find the cycle in the formatted memo when it contains many groups (see cockroachdb#80901). This commit updates the formatted memo within the error details to include the path to the cycle, if one exists. A cycle is not searched for in other cases where the memo is formatted, to avoid the overhead of cycle detection. A simple cycle detection library has been added that the memo formatter uses to locate a path in a memo to a cycle. Release note: None
craig bot
pushed a commit
that referenced
this issue
May 24, 2022
80580: rfcs: rbac extensions and system privileges r=RichardJCai a=RichardJCai Release note: None 81121: opt: display memo cycle when potential cycle is detected r=mgartner a=mgartner #### opt: print error details in `expropt` test directive Error details are now printed in the output of the `expropt` optimizer test directive. This is helpful for seeing the formatted memo that is included in the detail of the error that occurs when a memo cycle is detected. Release note: None #### opt: display memo cycle when potential cycle is detected The optimizer will error with "memo group optimization passes surpassed limit of 100000; there may be a cycle in the memo" when it detects a potential memo cycle. The error includes the memo in the error details to aid in debugging. However, it can be hard for a human to find the cycle in the formatted memo when it contains many groups (see #80901). This commit updates the formatted memo within the error details to include the path to the cycle, if one exists. A cycle is not searched for in other cases where the memo is formatted, to avoid the overhead of cycle detection. A simple cycle detection library has been added that the memo formatter uses to locate a path in a memo to a cycle. Release note: None 81767: kv: don't consider skipped snapshots to be "processed" by queues r=nvanbenschoten a=nvanbenschoten In a support issue, we saw a very high rate of successful raftsnapshot queue process attempts. This was confusing, as the rate of snapshots sent was much lower. It turns out that this was because most snapshots were being skipped on the "replica is likely in the process of being added" path. To avoid this confusion in the future, we no longer return `true` as the value for `processed` from `raftSnapshotQueue.process` method in these cases. 81783: cast: set volatility of casts to/from TEXT and NAME to leak-proof r=mgartner a=mgartner In Postgres 14, some casts which were previously immutable and not leak-proof are now leak-proof. This commit updates the volatility of casts to and from TEXT and NAME to leak-proof to match Postgres. This should aid the optimizer in decorrelating more subqueries. This is not backward incompatible because it is less restrictive and should not change the behavior of any users' existing queries. There are many other casts that can be changed to leak-proof, but our implementations of those casts need to be audited to ensure that they cannot err (one of the requirements for leak-proof). I leave this as future work. We must also take care with assignment casts, which currently use the same volatility as a normal cast. Some casts which cannot err and are leak-proof can err as an assignment cast, so the assignment cast cannot be leak-proof. For example, a cast like `'foo'::VARCHAR(1)` does not err, but an assignment cast with the same inputs will err because the value does not fit into the target type's width. To handle cases like this, we may need to label each cast with two volatilities, one for regular casts and one for assignment casts. Release note: None Co-authored-by: richardjcai <[email protected]> Co-authored-by: Marcus Gartner <[email protected]> Co-authored-by: Nathan VanBenschoten <[email protected]>
|
This one's a bug in the |
DrewKimball
added a commit
to DrewKimball/cockroach
that referenced
this issue
Jul 6, 2022
In some rare cases when null-rejection rules fail to fire, a redundant filter
can be inferred in an `InnerJoin` - `LeftJoin` complex. This could previously
result in the `JoinOrderBuilder` attempting to add a `Select` to the same memo
group as its input, which would create a memo cycle. This patch prevents the
`JoinOrderBuilder` from adding the `Select` to the memo in such cases.
What follows is a more detailed explanation of the conditions that could
previously cause a memo cycle.
`InnerJoin` operators have two properties that make them more 'reorderable'
than other types of joins: (1) their conjuncts can be reordered separately
and (2) new conjuncts can be inferred from equalities. As a special case of
(1), an `InnerJoin` can be pushed into the left side of a `LeftJoin`, leaving
behind any `Select` conjuncts that reference the right side of the `LeftJoin`.
This allows the `JoinOrderBuilder` to make the following transformation:
```
(InnerJoin
A
(InnerJoin
B
(LeftJoin
C
D
c=d
)
b=c
)
a=b, a=d
)
=>
(InnerJoin
A
(Select
(LeftJoin
(InnerJoin
B
C
b=c
)
D
c=d
)
b=d // Inferred filter!
)
a=b, a=d
)
```
Note the new `b=d` filter that was inferred and subsequently left on
a `Select` operator after the reordering. The crucial point is that
this filter is redundant - the input to the `Select` is already a
valid reordering of the `BCD` join complex.
The `JoinOrderBuilder` avoids adding redundant filters to `InnerJoin`
operators, but does not do the same for the `Select` case because it
was assumed that the filters left on the `Select` would never be redundant.
This is because the `a=d` filter *should* rejects nulls, so the `LeftJoin`
should have been simplified. However, in rare cases null-rejection does not
take place. Because the input to the `Select` is already a valid reordering,
the `JoinOrderBuilder` ends up trying to add the `Select` to the same group
as its input - namely, the `BCD` join group. This causes a cycle in the memo.
Fixes cockroachdb#80901
Release note (bug fix): Fixed a bug that could cause an optimizer
panic in rare cases when a query had a left join in the input of
an inner join.
craig bot
pushed a commit
that referenced
this issue
Jul 7, 2022
83875: opt: fix memo cycle caused by join ordering r=DrewKimball a=DrewKimball
In some rare cases when null-rejection rules fail to fire, a redundant filter
can be inferred in an `InnerJoin` - `LeftJoin` complex. This could previously
result in the `JoinOrderBuilder` attempting to add a `Select` to the same memo
group as its input, which would create a memo cycle. This patch prevents the
`JoinOrderBuilder` from adding the `Select` to the memo in such cases.
What follows is a more detailed explanation of the conditions that could
previously cause a memo cycle.
`InnerJoin` operators have two properties that make them more 'reorderable'
than other types of joins: (1) their conjuncts can be reordered separately
and (2) new conjuncts can be inferred from equalities. As a special case of
(1), an `InnerJoin` can be pushed into the left side of a `LeftJoin`, leaving
behind any `Select` conjuncts that reference the right side of the `LeftJoin`.
This allows the `JoinOrderBuilder` to make the following transformation:
```
(InnerJoin
A
(InnerJoin
B
(LeftJoin
C
D
c=d
)
b=c
)
a=b, a=d
)
=>
(InnerJoin
A
(Select
(LeftJoin
(InnerJoin
B
C
b=c
)
D
c=d
)
b=d // Inferred filter!
)
a=b, a=d
)
```
Note the new `b=d` filter that was inferred and subsequently left on
a `Select` operator after the reordering. The crucial point is that
this filter is redundant - the input to the `Select` is already a
valid reordering of the `BCD` join complex.
The `JoinOrderBuilder` avoids adding redundant filters to `InnerJoin`
operators, but does not do the same for the `Select` case because it
was assumed that the filters left on the `Select` would never be redundant.
This is because the `a=d` filter *should* rejects nulls, so the `LeftJoin`
should have been simplified. However, in rare cases null-rejection does not
take place. Because the input to the `Select` is already a valid reordering,
the `JoinOrderBuilder` ends up trying to add the `Select` to the same group
as its input - namely, the `BCD` join group. This causes a cycle in the memo.
Fixes #80901
Release note (bug fix): Fixed a bug that could cause an optimizer
panic in rare cases when a query had a left join in the input of
an inner join.
83945: storage/metamorphic: Add MVCC delete range using tombstone r=erikgrinaker a=itsbilal
This change adds MVCCDeleteRangeUsingTombstone to the MVCC
metamorphic tests. MVCCDeleteRange had already existed in
this test suite, so this ended up being a relatively simple
addition.
One part of #82545, with possibly more parts to follow
as other MVCC-level operations are added that utilize
`writer.{Put,Clear}{MVCC,Engine}RangeKey`.
Release note: None.
83992: server: log stacks on 500 errors r=ajwerner a=ajwerner
Before this change, we'd just log the error body, which often is not very
helpful. The format specifier makes me think that the intention was to log
the stacks. This made debugging [this](#83677 (comment))
trivial as opposed to hard.
Release note: None
84015: bazel: clear configurations when running `git grep` in `check.sh` r=miretskiy,mari-crl a=rickystewart
The configurations `grep.{column,lineNumber,fullName}` can be set
globally or on a per-user basis and change the output of `git grep`,
which breaks checks that do exact-string matching. We manually clear
these configurations for the `git grep`s in this file to ensure the
output is predictable on any machine.
Release note: None
Co-authored-by: Andrew Kimball <[email protected]>
Co-authored-by: Bilal Akhtar <[email protected]>
Co-authored-by: Andrew Werner <[email protected]>
Co-authored-by: Ricky Stewart <[email protected]>
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
roachtest.sqlsmith/setup=rand-tables/setting=no-ddl failed with artifacts on release-22.1.0 @ 120fbbb2cb4bdd071c1835f29d5364953752a5bd:
Help
See: roachtest README
See: How To Investigate (internal)
This test on roachdash | Improve this report!
Jira issue: CRDB-15462
The text was updated successfully, but these errors were encountered: