"Cohort Query Processing" 論文閱讀

09-06

VLDB論文閱讀-"Cohort Query Processing"

論文鏈接

摘要

傳統的資料庫進行群體分析(cohort analysis)代價比較高，因為涉及到多張表的很多條記錄。這篇文章提出了一種擴展的資料庫系統來支持群體分析。通過對SQL擴展了3個新操作來實現的，並且設計了三種不同的群體分析請求處理的機制，其中兩種採用了非侵入式的方法，第三種方式是為群體分析特別優化過的基於列存儲(columnar)的機制。

Introduction

通過一個例子介紹了Cohort Analysis的好處，它能比直接分析一大堆數據得到更多的信息。群體分析：一種數據分析手段，能夠得到在變化的社會環境中年齡對人類行為的影響，它允許我們把社會的改變和年齡分開，因此能提供更多信息。

cohort analytics中，分為3步：1）把用戶分為群體 2）決定用戶群體的年齡 3）計算每個群體的聚集。第1步實施被稱為cohort的操作來捕獲社會不同的影響。社會科學家選擇一個特定的動作e（被稱為初始動作），基於用戶執行這個動作e的時間（稱為初始時間）把用戶劃分成不同的群體。一個用戶的每個活動記錄然後被賦予給這個用戶屬於的相同cohort。第2步，把每個cohort基於age劃分成更小的子分區。一個記錄t的age是這條記錄和初始時間的間隔。最後，對每個cohort進行聚集行為。然後作者舉了一個遊戲記錄的例子來詳細的說明第1步是怎麼回事。

傳統的群體分析有兩個限制：1）分析整個數據集，因此沒有機制能夠提取一部分用戶或記錄來進行分析 2）只能使用時間屬性來區分群體。此外，作者還舉了幾個例子說明傳統的群體分析會受到限制。

這篇文章的貢獻：

- 在DBMS的語義下定義了群體分析的問題

- 介紹了一種模型化用戶活動數據的擴展的群組分析方法，介紹了三個新的操作符可以用於擴展的關係和組成群體分析查詢語句。

- 構建了群體分析查詢引擎，COHAHA，為群體分析實現了多種優化

- 為比較COHANA和非侵入式的機制設計了基準測試研究

群體分析的一種非侵入式方法

作者舉了一個群體分析的例子，然後用sql語句實現。可以看出用了很多join，性能低下，並且sql很複雜。即使採用MV的方法，也有一些問題，包括性能、存儲空間、擴展性等等。

群體分析基礎

數據模型

活動數據的集合稱為活動關係的實例，也稱為活動表。

一個活動表D是一個關係，包含屬性Au，At，Ae，A1,...,An。Au是一個字元串唯一標識一個用戶，Ae表示動作，At表示Au執行Ae的時間。其它屬性都是標準的關係屬性。並且，活動表D在（Au，At，Ae）上有主鍵限制。

基本概念

三個核心概念：初始動作（birth action）, 初始時間（birth time）和年齡（age）.給定一個動作，初始時間是第一次執行這個動作的時間。一個動作e被稱為初始動作，如果它被用來定義用戶的初始時間。

操作符

提出了兩個新的操作符用來獲得活動記錄的子集，一個聚集操作符用來聚集每個（cohort，age）組合。

這是個初始記錄選擇操作符，用來獲得初始活動記錄滿足條件C的用戶的活動記錄。

比如我們想獲得初始時在Australia執行launch動作的用戶的活動記錄，就可以這樣寫

年齡選擇操作符用來從活動表中返回所有的初始活動記錄以及符合條件C的年齡活動記錄。

這個操作符產生群體聚集用兩步：1）用戶分群體 2）聚集活動記錄。

第一步，把用戶劃分成群體，基於用戶初始活動記錄在指定屬性集合上的映射。

在例子中，假設launch是初始動作，屬性集合是{country}，玩家1，2，3都根據country屬性的值被賦給不同的cohort。

在第2步，對於每個可能的群體和年齡的組合，選擇屬於的用戶的關聯的年齡活動記錄，然後執行聚集函數。

操作符的屬性

第1，2個操作符滿足交換律，因此我們可以把birth選擇操作在查詢中往下壓，來優化查詢。

群體查詢

給定一個活動表D和上述三個操作符，一個查詢可以表示成上述三個操作符的組合，這些操作符的birth action都是一樣的。一個群體查詢可以表示成下面的形式：

擴展

群體查詢的方案可以在很多方面擴展，首先，可以把上述查詢的結果和sql語句混合。另一個擴展是引入二元操作符(比如join，intersection)來操作多張表。

群體查詢操作符到SQL語句的映射

展示了怎麼把操作符用SQL語句表示

COHANA查詢引擎

為了用新設計的群體操作符支持群體分析，我們呈現了4種基於列存儲的資料庫的擴展：1）一個良好調節的水平存儲格式用來持久化活動表 2）一個修改的表掃描操作符能夠跳過不符合用戶的年齡活動記錄 3）一種cohort操作符的原生高效的實現 4）一個查詢策劃器能夠利用cohort操作符的特性。

活動表存儲格式

用主鍵(Au,At,Ae)的順序存儲活動表的記錄，這種存儲布局有兩個好的特性：1）相同用戶的記錄聚集在一起 2）每個用戶的記錄按照時間順序存儲。有這兩個特性，我們可以高效的找到任何用戶的任何初始動作的初始活動記錄，只需要順序掃描就好了。

我們採用了分塊機制和多種壓縮技術來加速cohort查詢處理。首先把活動表水平分區成多個數據塊，每個用戶的活動記錄被包含在恰好一個塊中（這一步怎麼做的還不清楚？）。然後，在每個數據塊，活動記錄按列存儲。對於一個數據塊中的每一列，我們基於列類型選擇合適的壓縮機制。

對於用戶列Au，採用Run-Length-Encoding機制，也就是：Au的值被存儲成三元組序列（u, f, n），u是Au中的用戶，f是u在這一列第一次出現的位置，n是出現的次數。我們會看到採用這種方法，修改的表掃描器能夠高效的跳過不符合條件的用戶活動記錄。

對於字元串列，採用一種兩級的壓縮機制。對於這樣的列A，首先構建一個全局的字典，包含了A中出現的所有值，並且已經排好序和唯一化。A中的每個值都有一個全局id，代表這個值在字典中的位置。對於每個數據塊，在這個塊中的A的值的全局id構建成這個塊的字典。這種兩級的壓縮機制使得可以高效的剪掉沒有任何用戶執行初始動作的數據塊。對於一個給定動作e，首先用二分找到全局id，再把這個id在數據塊字典中二分查找，找不到的話就可以跳過這個塊了。

對於整數列也採用相似的二級壓縮方法。

用上述的壓縮方法，使得字元串和整數列都可以用整數數組來表示，因此可以用整數壓縮技術來減少存儲空間。具體思想是每個整數都採用固定長度的位元組存儲，這樣支持高效的隨機讀寫。

群體查詢的求值

這一節講了怎麼對一次查詢請求求值。首先，生成一個邏輯的查詢計劃並對它進行優化，然後對每個數據塊執行優化後的請求，最後合併每個塊的結果。

我們介紹的查詢計劃由4個操作符組成，包括TableScan和上面說的3種操作符。跟其它基於列的資料庫一樣，映射操作是在預處理中做的：在請求準備階段收集要求的列並把列傳給TableScan操作符，來得到每列的值。

在查詢計劃中，根節點是聚集操作符，唯一的葉子節點是TableScan操作符。在他們之間是初始選擇操作符和年齡選擇操作符。

根據等式1，我們把初始選擇操作符儘可能的下壓，來優化查詢。因為我們可以在4.3節看到，特別設計的TableScan實現可以高效的跳過那些初始活動記錄不滿足選擇條件的用戶的年齡活動記錄。因此，儘可能的早做初始選擇可以優化查詢。

然後，我們利用Ae列的兩級壓縮機制來跳過沒有用戶執行初始動作e的數據塊，然後對每個數據塊執行查詢。

TableScan操作符

我們為高效的群體分析處理擴展了標準的TableScan操作符。修改過的TableScan在壓縮後的列上掃描，主要擴展了兩個函數:GetNextUser()和SkipCurUser(). GetNextUser返回下一個用戶的活動記錄，SkipCurUser()跳過當前用戶的活動記錄。

TableScan實現如下:對於每個數據塊，在查詢初始話階段，TableScan收集所有在請求中用到的列，並對每個列維護一個文件指針，初始時都指向列的起始位置。

GetNextUser()的實現：首先獲取Au列的下一個三元組，然後讓每個文件指針都向前走這個三元組相對於用戶u的偏移。(註：這裡因為是列存儲的資料庫，所以同一列的數據是順序存放的，得到Au列的偏移後，其它列加上這個偏移就可以得到對應用戶那行的數據)

SkipCurUser()的實現相似，當被調用時，首先計算當前用戶剩餘元組的個數，然後讓指針前進相應的長度。

Cohort演算法

這一節開發了cohort操作符在提出的存儲格式上的實現的演算法。

第一個介紹的是初始選擇操作符。沒什麼新奇之處，首先找到一個用戶的初始元組，然後判斷它滿不滿足條件，不滿足的話調用SkipCurUser跳過當前用戶，滿足的話調用GetNext返回當前用戶的元組，當取完後調用GetNextUser拿到下一個用戶的數據塊繼續判斷。

年齡選擇操作符類似。

聚集操作符的實現。聚集操作符的含義是根據用戶的初始活動元組在指定屬性集上的映射來聚集用戶的元組，並可以對每個年齡活動記錄執行fA函數。實現時，維護兩個hash表，一個裝群體的大小，一個裝群體的每個年齡(cohort,age)的聚集結果。

性能研究

略