[
https://issues.apache.org/jira/browse/FLINK-41216?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Gustavo de Morais updated FLINK-41216:
--------------------------------------
Description:
A ROW_NUMBER Top-N that outputs the row number has two upsert keys in the
planner: {{rn}} and the input key {{id}}. The Top-N operators emit their
changelog per rank, as -U/+U pairs. That is correct per {{rn}}, but not per
{{id}}. Upsert sinks and joins keyed by {{id}} end up with wrong rows. The
planner trusts {{id}}, so it adds no upsert materializer in front of a sink
with PRIMARY KEY (id).
{code:sql}
CREATE TABLE items (id BIGINT, score INT, PRIMARY KEY (id) NOT ENFORCED) WITH
(...);
CREATE TABLE snk (id BIGINT, rn BIGINT, PRIMARY KEY (id) NOT ENFORCED) WITH
(...);
INSERT INTO snk SELECT id, rn FROM
(SELECT *, ROW_NUMBER() OVER (ORDER BY score DESC) AS rn FROM items) WHERE rn
<= 2;
{code}
*Example 1: a delete moves a row up (RetractStrategy)*
{code}
Input
-- +I[id: 1, score: 100]
-- +I[id: 2, score: 90]
-- -D[id: 1, score: 100]
Output (the upsert sink drops -U)
-- +I[id: 1, rn: 1]
-- +I[id: 2, rn: 2]
-- -U[id: 1, rn: 1] (dropped)
-- +U[id: 2, rn: 1]
-- -D[id: 2, rn: 2] (deletes id 2)
Table (PK id)
id: 1, rn: 1 (expected: id: 2, rn: 1)
{code}
*Example 2: an insert pushes a row out (AppendFastStrategy, append-only input)*
{code}
Input
-- +I[id: 1, score: 100]
-- +I[id: 2, score: 90]
-- +I[id: 3, score: 95]
Output (the upsert sink drops -U)
-- +I[id: 1, rn: 1]
-- +I[id: 2, rn: 2]
-- -U[id: 2, rn: 2] (dropped, so id 2 is never deleted)
-- +U[id: 3, rn: 2]
Table (PK id)
id: 1, rn: 1
id: 2, rn: 2 (stale)
id: 3, rn: 2 (expected: only id 1 and id 3)
{code}
With PRIMARY KEY (rn) both examples are correct. A regular join keyed by {{id}}
has the same problem. Since FLINK-40997, such a join always picks {{id}} when
the row number is the last column.
*How this happened:* the unique keys of a Top-N include the input key, which is
correct: {{id}} is unique at any point in time. FLINK-22901 (1.14) introduced
upsert keys and reused the unique key derivation for Rank
({{FlinkRelMdUniqueKeys#getRankUniqueKeys}}). An upsert key also needs every
change of a key to arrive in order, which the Top-N only does for {{rn}}.
FLINK-23054 then started to rely on upsert keys to skip the sink upsert
materializer. FLINK-23142 found the same ordering issue in
{{UpdatableTopNFunction}} and fixed it inside that function only.
Possible solutions:
* Stop exposing the input key as an upsert key of a Top-N that outputs the row
number. It stays a unique key. This is a small planner change, but it changes
plans: the planner then adds an upsert materializer in front of such sinks, and
joins key by {{rn}}. Compiled plans keep their stored keys.
* Change every Top-N function to emit a changelog that is also correct per
{{id}}: retract each moved row before re-adding it, and emit -D for rows that
leave. This touches the retract, append-only, fast-top1 and updatable
functions, sync and async, and changes the emitted changelog of every such
Top-N.
was:
When a row of a ROW_NUMBER Top-N with the row number in its output moves up in
the ranking, {{RetractableTopNFunction}} emits it at its new rank before
retracting it at its old rank. Deleting the top row of [1, 2, 3] emits:
{code}
-U[1,1] +U[2,1] -U[2,2] +U[3,2] -D[3,3]
{code}
The order is correct per {{rn}}, but not per the input key {{id}}, which the
planner also exposes as an upsert key of the Top-N. Operators and sinks keyed
by {{id}} end up with wrong results. FLINK-23142 fixed the same ordering issue
in {{UpdatableTopNFunction}}.
{code:sql}
CREATE TABLE items (id BIGINT, score INT, PRIMARY KEY (id) NOT ENFORCED)
WITH ('connector' = 'values', 'changelog-mode' = 'I,UB,UA,D');
CREATE TABLE snk (id BIGINT, rn BIGINT, PRIMARY KEY (id) NOT ENFORCED)
WITH ('connector' = 'values', 'sink-insert-only' = 'false');
INSERT INTO snk SELECT id, rn FROM
(SELECT *, ROW_NUMBER() OVER (ORDER BY score DESC) AS rn FROM items) WHERE rn
<= 3;
{code}
||Input||Sink PK||Result||Correct||
|+I[1, 100], +I[2, 90], +I[3, 80], -D[1, 100]|(id)|[1, 1], [2, 1]|no, id 1
stays after its delete and id 3 is missing|
|same|(rn)|[2, 1], [3, 2]|yes|
|+I[1, 100], +I[2, 90], +I[3, 80], -U[1, 100], +U[1, 50]|(id)|[1, 3], [2,
1]|no, id 3 is missing|
|same|(rn)|[1, 3], [2, 1], [3, 2]|yes|
Because {{id}} is an upsert key, the planner adds no upsert materializer in
front of the sink. The upsert sink drops the -U messages and receives {{+U[2,1]
+U[3,2] -D[3,3]}}, so it deletes id 3 and never deletes id 1. A regular join
keyed by {{id}} has the same problem: it stores id 2 on {{+U[2,1]}} and removes
it again on {{-U[2,2]}}. Since FLINK-40997, such a join always picks {{id}}
when the row number is the last column.
Possible solutions:
* Emit the retraction of each moved row before its insert at the new rank,
walking the ranks top-down. This keeps both {{id}} and {{rn}} valid upsert keys
and changes no plan or state.
* Stop exposing the input key as an upsert key of a Top-N that outputs the row
number. This is a smaller change, but it changes plans, so jobs that re-submit
their SQL switch state keys.
> Retracting ROW_NUMBER Top-N emits +U before -U for rows moving up, so
> operators keyed by the input upsert key lose rows
> -----------------------------------------------------------------------------------------------------------------------
>
> Key: FLINK-41216
> URL: https://issues.apache.org/jira/browse/FLINK-41216
> Project: Flink
> Issue Type: Bug
> Components: Table SQL / Planner, Table SQL / Runtime
> Affects Versions: 2.0.2, 2.3.0, 2.2.1, 1.20.5, 2.1.3, 2.4.0
> Reporter: Gustavo de Morais
> Priority: Major
>
> A ROW_NUMBER Top-N that outputs the row number has two upsert keys in the
> planner: {{rn}} and the input key {{id}}. The Top-N operators emit their
> changelog per rank, as -U/+U pairs. That is correct per {{rn}}, but not per
> {{id}}. Upsert sinks and joins keyed by {{id}} end up with wrong rows. The
> planner trusts {{id}}, so it adds no upsert materializer in front of a sink
> with PRIMARY KEY (id).
> {code:sql}
> CREATE TABLE items (id BIGINT, score INT, PRIMARY KEY (id) NOT ENFORCED) WITH
> (...);
> CREATE TABLE snk (id BIGINT, rn BIGINT, PRIMARY KEY (id) NOT ENFORCED) WITH
> (...);
> INSERT INTO snk SELECT id, rn FROM
> (SELECT *, ROW_NUMBER() OVER (ORDER BY score DESC) AS rn FROM items) WHERE
> rn <= 2;
> {code}
> *Example 1: a delete moves a row up (RetractStrategy)*
> {code}
> Input
> -- +I[id: 1, score: 100]
> -- +I[id: 2, score: 90]
> -- -D[id: 1, score: 100]
> Output (the upsert sink drops -U)
> -- +I[id: 1, rn: 1]
> -- +I[id: 2, rn: 2]
> -- -U[id: 1, rn: 1] (dropped)
> -- +U[id: 2, rn: 1]
> -- -D[id: 2, rn: 2] (deletes id 2)
> Table (PK id)
> id: 1, rn: 1 (expected: id: 2, rn: 1)
> {code}
> *Example 2: an insert pushes a row out (AppendFastStrategy, append-only
> input)*
> {code}
> Input
> -- +I[id: 1, score: 100]
> -- +I[id: 2, score: 90]
> -- +I[id: 3, score: 95]
> Output (the upsert sink drops -U)
> -- +I[id: 1, rn: 1]
> -- +I[id: 2, rn: 2]
> -- -U[id: 2, rn: 2] (dropped, so id 2 is never deleted)
> -- +U[id: 3, rn: 2]
> Table (PK id)
> id: 1, rn: 1
> id: 2, rn: 2 (stale)
> id: 3, rn: 2 (expected: only id 1 and id 3)
> {code}
> With PRIMARY KEY (rn) both examples are correct. A regular join keyed by
> {{id}} has the same problem. Since FLINK-40997, such a join always picks
> {{id}} when the row number is the last column.
> *How this happened:* the unique keys of a Top-N include the input key, which
> is correct: {{id}} is unique at any point in time. FLINK-22901 (1.14)
> introduced upsert keys and reused the unique key derivation for Rank
> ({{FlinkRelMdUniqueKeys#getRankUniqueKeys}}). An upsert key also needs every
> change of a key to arrive in order, which the Top-N only does for {{rn}}.
> FLINK-23054 then started to rely on upsert keys to skip the sink upsert
> materializer. FLINK-23142 found the same ordering issue in
> {{UpdatableTopNFunction}} and fixed it inside that function only.
> Possible solutions:
> * Stop exposing the input key as an upsert key of a Top-N that outputs the
> row number. It stays a unique key. This is a small planner change, but it
> changes plans: the planner then adds an upsert materializer in front of such
> sinks, and joins key by {{rn}}. Compiled plans keep their stored keys.
> * Change every Top-N function to emit a changelog that is also correct per
> {{id}}: retract each moved row before re-adding it, and emit -D for rows that
> leave. This touches the retract, append-only, fast-top1 and updatable
> functions, sync and async, and changes the emitted changelog of every such
> Top-N.
--
This message was sent by Atlassian Jira
(v10.3.26#10030026)