PostgreSQL 列存索引

大資料時代，單一的資料庫系統已經不能滿足使用者的所有業務需求，OLAP 場景往往資料量大，查詢複雜，需使用專門的資料分析類産品，如 GreenPlum；OLTP 場景往往操作較簡單，要求響應及時，這也是多數關系資料庫系統擅長的場景。AP 系統的資料通常需要定期從 TP 系統同步以進行分析，這也就造成 AP 系統的實時性較差，如隻能查詢 T+1 的資料。為實作實時分析，很多資料庫系統在混合負載方面做了很多工作，逐漸支援大資料量下的複雜查詢，自己先消化一部分分析場景，對于依然無法滿足的場景，再使用其他産品實作。

在資料分析場景下，列存比行存更有優勢。Oracle 從 12c 開始引入

in-memory 元件，使其在資料實時分析和混合負載情況下的性能大幅提升，其主要特性是 In-Memory Column Store (IM column store) ，在存儲中持久化的資料依然是行存，在記憶體中維護行存和列存兩種模式的資料，行存用于 OLTP 場景，列存用于 OLAP 場景。SQL Server 同樣支援 Columnstore indexes

，其性能較行存有高達10倍的提升。

PostgreSQL 在列存方面也做了一些

嘗試 ，本文介紹[1]中提出的一種 PostgreSQL 列存索引（Column Store Index）實作方法，該索引以列存形式組織資料，資料表的 INSERT/UPDATE/DELETE 操作均被同步到列存索引中，以下将從列存索引結構，并發控制，查詢執行等方面介紹其如何增強 PostgreSQL 的 OLAP 處理能力。

建立列存索引

PostgreSQL 中的資料是以堆表組織的，所有索引都可以認為是二級索引（secondary index），索引與資料完全隔離，存儲在單獨的檔案中，并且為擴充新的索引提供了

接口

，隻需實作這些接口即可自定義一個新的索引。

本文引入一種新的索引類型 Column Store Index（CSI），以列存形式組織資料，加速 OLAP 場景下的查詢性能。當執行 INSERT/UPDATE 指令将資料插入/更新至資料表時，會調用以上接口中實作的回調函數

aminsert

在對應索引中插入資料。然而，PostgreSQL 中并沒有 DELETE 指令對應的回調函數，為迅速将删除操作應用到 CSI 中，為 PostgreSQL 擴充一個新的回調函數

amdelete

。

建立 CSI 的文法如下：

CREATE INDEX indexname ON tablename USING csi (a, b, c);           

以上 SQL 建立一個 CSI 索引，索引中每個列對應的資料存儲在一個檔案中，本例中的索引對應三個檔案。

列存索引結構

為保證 CSI 的時效性，行存資料的變更需及時反映到 CSI 中，但又要盡量減小是以帶來的性能損耗，尤其不能影響 OLTP 場景的性能，是以，文中引入了三種結構：Insert/Delete Lists, ROS 和 Local ROS。

從下圖可知，資料表的變更先緩存在 Insert/Delete 清單中，背景程序異步地将清單中對應的資料轉換為列存索引資料（ROS），如果有查詢請求，則将 Insert/Delete 清單中尚未轉換為列存的資料臨時轉換為列存，即 Local ROS，再與 ROS 中的列存資料一起供查詢使用。

Insert/Delete Lists（InsL/DelL）

CSI 中，每個索引列對應一個檔案，如果每次資料變更都同步等待索引列更新完成，将會是非常耗時的，為此，文中引入了兩個結構，Insert Lists（InsL） 和 Delete Lists（DelL），資料的增删都同步記錄在這裡兩個清單中，清單中僅記錄資料的唯一辨別符 TID（Tuple-ID）。

資料從行存轉換為列存是通過後天轉換程序異步完成的，其定期将 InsL 中記錄的 TID 對應的行資料轉換為列資料，儲存在 ROS（Read-Optimized-Storage）中。

ROS

為高效管理 CSI 中的資料，ROS 中的資料被劃分為稱為

extent

的單元，每個

extent

預設儲存 262,144 行資料，資料轉換、寫檔案以及與查詢執行引擎通路資料均以

extent

為機關。如 InsL 中的 TID 數量足夠填充一個

extent

時，會将其引用的資料轉換至 ROS 中；對于 InsL 和 DelL 中都有的 TID，說明其已經被删除，無需轉換，對于僅在 DelL 中有的 TID 則将其記錄在

DeleteVector

中，每個 extent 都會有一個

DeleteVector

Local ROS

由于從 InsL/DelL 轉換行資料至 ROS 的列資料是異步的，當有查詢請求時，并非所有資料都在 ROS 中，還有一部分在 InsL/DelL 中，是以，将 InsL/DelL 中尚未轉換至 ROS 的資料臨時轉換為列存格式，稱其為

Local ROS

并發控制

PostgreSQL 中使用 MVCC 作為其并發控制政策，每個資料行（tuple）中都記錄了插入該行的事務 ID（xmin）和删除該行的事務 ID（xmax），每個查詢或者事務都會有一個快照（snapshot）記錄查詢/事務開始時的最大事務 ID，最小事務 ID，以及活躍事務清單，根據該快照和資料行上的 xmin，xmax 資訊即可判斷目前行對目前查詢/事務是否可見。

CSI 索引不能破壞以上的資料可見性判斷規則，在 InsL/DelL 中同樣記錄了 tuple 的 xmin 和 xmax 資訊，其轉換為 ROS 的規則如下：

• 對于 InsL 中的資料，隻有産生該資料的事務已經送出且對所有現存事務均可見才能将其轉換至 ROS；
• 同理，DelL 中，隻有删除該資料的事務已經送出且對其他事務均可見時才能将其記錄在 DeleteVector 中。

這樣做可以確定 ROS 中存儲的總是在某一時刻對所有事務均可見的資料。

對于 ROS 中的資料，如果每行資料均記錄其 xmin 和 xmax，據此做可見性判斷，其處理代價是很高的。為此，在每個

extent

中記錄産生和删除該

extent

的事務 ID，分别為

Xgen

和

Xdel

，隻有滿足

Xgen <=? XID < Xdel

的

extent

對事務 XID 是可見的。

以下圖為例，最初有 5 個

extent

，其

Xgen

分别為 X100，X120，X130，X140，X150。假設 query#1 執行前，最後一個轉換的

extent

其

Xgen

是 X150，則該查詢對所有

extent

均可見；對于 InsL 中尚未轉換為 ROS 的資料，通過記錄的 xmin 和 xmax 進行可見性判斷，對于可見的資料将其轉換為 Local ROS。

不妨假設在 query#2 之前，有一個 XID 是 200 的事務，做了一次 ROS 轉換，T100 和 T101 滿足轉換條件（産生該資料的事務均已送出，且對其他事務可見），同時

extent 1

中已經删除的資料超過了某個門檻值，是以，該 ROS 轉換将 extent 1 中尚未被删除的資料拷貝至新的 extent 5，并轉換 InsL 中的 T100 和 T101，轉換完成後将 Xgen 設定為 X200。對于随後而來的 query#2，其可見的 extent 有 0，2，3，4，5，

extent 1

由于

X120 <= ?X200 < X200

不成立，對該查詢不可見，其中的資料已經被拷貝至

extent 5

查詢執行

查詢重寫

引入 CSI 之後，需要在生成查詢計劃時，考慮使用 CSI 的代價是否更低，進而将原生的計劃節點替換為對應的 CSI 計劃節點。CSI 可以看做是一個覆寫索引（Cover Index），對于僅通路 CSI 就可以擷取所有資料且代價較通路行存小的查詢均可以考慮使用。

目前支援重寫的計劃節點有

SeqScan

，

Aggregation

Sort

，其對應的 CSI 計劃節點為

CSI Scan

CSI Aggregation

CSI Sort

，其重寫的實作基于 PostgreSQL 9.5 以後提供的

Custom Scan API

計劃執行

重寫後的計劃從 ROS 和 Local ROS 通路資料，讀資料時會過濾 DeleteVector 和 DelL 中已經被删除的資料，如下圖所示：

向量化處理

為充分利用列存的優勢，處理表達式計算時采用一次一批的方式，其處理機關為

vector

，預設每個

vector

包含 128 行資料，進而使用 SIMD，實作高效資料處理。

并行處理

使用 CSI 時，會盡量以并行模式執行，每個背景工作程序（Dynamic Background Worker，DBW）處理不同的

extent

，具體并行度依賴于優化器的具體實作。以下圖為例，SMC（Shared Memory Context）表示動态建立的多程序間共享的記憶體，每個 DBW 處理一部分資料，并将局部結果放置在對應的 SMC 中，使用者的處理程序（backend process）将局部結果彙總并計算出最終結果。

PostgreSQL 的并行處理實作可以參考這篇

文章

總結

本文介紹了一種新的 PostgreSQL 索引結構，列存索引（CSI），其将行存資料以索引的形式按列存儲，同時配合其他元件的改造，如實作列存算子，優化器通過代價估算生成通路列存索引的計劃，向量化處理以及并行處理等，充分發揮列存優勢，進而在大資料量複雜查詢的 OLAP 場景獲得更高的性能。

個人認為，列存索引是一種很好的将行存與列存整合的方式，PostgreSQL 本身對于索引的接口式實作，以及 Custom Scan API 機制，使得列存索引的實作非常靈活且侵入性不強。本文僅做原理性介紹，并沒有太多的實作細節，感興趣的讀者可以參考 [3] 中作者送出的 patch，該 patch 目前尚未合入社群。

參考文獻

[1] Nakamura, Minoru , et al. "Extending postgreSQL to handle OLXP workloads." Fifth International Conference on Innovative Computing Technology IEEE, 2015.

[2]

https://wiki.postgresql.org/wiki/Future_of_storage

[3]

https://www.postgresql.org/message-id/flat/[e-mail]