關於如何在流數據上計算 Top K 的應用問題

Hi,

最近正在研究 Top K 的問題，在研究中找到了 Blink SQL 可以透過維護一個儲存 K 的最大紀錄的 ”堆”來優化底下這類 SQL，不過我認為這只能針對 score 只會增加不減少的情況。

SELECT user_id, score FROM ( SELECT *, ROW_NUMBER() OVER (ORDER BY score DESC) AS row_num FROM user_scores) WHERE row_num <= 3 我的問題是當如果這樣的計算是應用在流數據上，且 score 可能隨時間增加或是“減少”的話，例 如底下這類的 SQL，能有什麼樣的優化？

SELECT user_id, score FROM ( SELECT *, ROW_NUMBER() OVER (ORDER BY score DESC) AS row_num FROM ( SELECT user_id, LAST_VAL(score) AS score FROM user_scores GROUP BY user_id)) WHERE row_num <= 3

SQL 中的 user_scores 可以當作是從 DataStream 直接轉換過來的 Dynamic Table， LAST_VAL假設是一種 UDAF，可以挑出目前最新的值。所以，可以想像這張 table 的 user's score 是會隨時間變化增減。

上面所說堆的優化無法處理這樣的問題，底下舉個例子。假設今天有一個 top-3 的堆中已經存放 了三個使用者：A, B, C，各自的 scores 是：4, 3, 2，接下來收到了一個使用者 D 和他的分數是 1 的話，這個時候演算法會直接忽略掉 D，因為他不在 top-3 的範圍內。但是當下一個如果收到 的是一個更新 A 使用者的 score 為 0 的紀錄的話，這個時候理論上我們知道 top-3 會改為 B, C, D，但是在維護 top-3 的堆中我們無力找回被忽略的使用者 D。這樣的優化在 batch mode 是沒有 問題的，因為最新的 score 在有限的數據中會是固定的不動的。

不過當處理流數據，我目前只想到這種應用最終可能需要退回成存放全部使用者 scores 才有辦 法處理，才能隨時計算出正確的 top-k。所以我想請教各位大牛有沒有什麼樣的優化方式可以處 理這樣的問題，讓狀態不需要存到全部資料？當然這個問題不侷限在 SQL，如果有任何實作在 DataStream 上的優化都是可接受。感謝大家幫忙。*来自志愿者整理的flink邮件归档