[ 
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)

Reply via email to