StoneDB 作為開源項目，一直秉持開源開放的基本原則，我們的社群版代碼現在已經完全在 Github 上開源，并不斷提高代碼的可讀友好性，同時，為了讓大家更好地了解我們是如何打造一款一體化 HTAP 開源資料庫的，我們會定期把一些核心技術的研發實作思路分享給大家，也算是抛磚引玉，如果讀者有更好的實作思路，也歡迎與我們溝通，甚至可以參與到我們社群版的開發中~
Tianmu 引擎是 StoneDB 團隊自研的一款列式存儲引擎，在6月初剛開源時，并不支援 delete 功能，對此很多使用者都提出了需求的意見，是以我們當時也把 delete 功能列入到我們的年度 Roadmap裡了，預計在10月20号的 StoneDB_5.7_v1.0.1 正式版本中，上線此功能。第一期，我将分享一下對 delete 功能的調研情況。
前置知識：資料庫中删除資料的三種方式
以 Mysql 5.7 為例，資料庫删除資料的方式一共有三種：
- delete
- truncate
- drop
以上三種方式都可以删除資料，但是使用場景是不同的。
對于整個表進行删除的執行速度來說：
drop > truncate >> delete
DELETE
delete 是屬于資料庫的 DML 操作語言，一般是根據條件逐行進行删除。
使用 delete 删除資料時，資料庫隻能删除資料不能删除表的結構，并且會觸發資料庫的事務機制。
delete 執行時，會先将所删除資料緩存到 rollback segment 中，事務 commit 之後生效。
在 InnoDB 中，使用 delete 其實并不會真正的把資料删除，是一種邏輯删，資料庫底層實際上隻是給删除的資料做了一個已删除的标記，是以，删除資料後的表占空間大小和删除前是一樣的。
TRUNCATE
truncate 屬于資料庫 DDL 定義語言，不走事務，原資料不放到 rollback segment 中，操作不觸發 trigger。執行後立即生效，無法找回（慎用 删除執行後，資料就沒了，不可恢複）。
truncate 删除表會立刻釋放磁盤空間。truncate table其實有點類似于drop table 然後 create,隻不過這個 create table 的過程做了優化，比如表結構檔案之前已經有了等等。是以速度上是接近 drop table 的速度；
DROP
drop 屬于資料庫 DDL 定義語言，同 truncate ，執行後立即生效，無法找回。
drop table table_name立刻釋放磁盤空間，drop 語句将删除表的結構、被依賴的限制(constraint)、觸發器(trigger)、索引(index)；依賴于該表的存儲過程/函數将保留,但是變為 invalid 狀态。
Tianmu 引擎對 delete 功能的調研
Tianmu 是一個列式存儲引擎，列式存儲的出現主要是為了友善快捷查詢和高效存儲大量同類型的資料而設計的，主要使用場景就是 OLAP。下面是 OLAP場景的部分關鍵特征：
- 絕大多數是讀請求。
- 資料以相當大的批次(> 1000行)更新，而不是單行更新;或者根本沒有更新。
- 已添加到資料庫的資料不能修改。
- 對于讀取，從資料庫中提取相當多的行，但隻提取列的一小部分。
- 列中的資料相對較小：數字和短字元串(例如，每個URL 60個位元組)。
- 處理單個查詢時需要高吞吐量(每台伺服器每秒可達數十億行)。
- 事務不是必須的。
- 對資料一緻性要求低。
而 OLAP 場景下，對于資料的 delete 的操作可以說沒有或者頻率很小。列式存儲對比行式存儲來說并不擅長資料的增删改，如果是為了極緻的查詢性能，完全可以舍棄 DML 操作（比如初期的 ClickHouse 也不支援 delete）。但是為了功能的完整性，我們初期就放開了 insert 和 update 的功能，不過沒有對 delete 功能進行支援。
随着使用者的呼聲越來越多，我們開始對各個有列式存儲的資料庫進行了一個調研，如下表所示：
目前行業現狀
通過分析目前行業内支援列式存儲的主流資料庫，大部分都是支援的，就算不支援直接 delete,也是支援 DML 同步的，是以 Tianmu 引擎的 delete 功能确實有必要進行開發支援。
主流列式資料庫的 delete 方案
openGauss
存儲結構
openGauss 列存儲引擎的底層存儲結構與 Tianmu 引擎類似 ，存儲基本機關是CU（Compression Unit，壓縮單元），即表中一列的一部分資料組成的壓縮資料塊。行存引擎中是以行作為機關來管理，而當使用列存儲時，整個表整體被按照不同列劃分為若幹個 CU。
每個 CU 對應一個 CUDesc 的記錄，在 CUDesc 裡記錄了整個 CU 的事務時間戳資訊、CU 的大小、存儲位置、magic 校驗碼、min/max 等資訊。
每張列存表還配有張 Delta 表，Delta 表自身為行存儲表。當有少量的資料插入到一張列存表時，資料會被暫時放入 Delta 表，等到達門檻值或滿足一定條件或操作時再行整合為 CU 檔案。Delta 表可以避免單點資料操作帶來的很重的 CU 操作與開銷。
delete 政策
CU 中資料的删除，實際上是标記删除。删除操作，相當于是更新了 CUDesc 表中 CU 對應 CUDesc 記錄的 delete bitmap（删除位圖）結構，标記列中某行對應資料已被删除，而 CU 檔案資料不會被更改。這樣可以避免删除操作帶來的 IO 放大以及解壓、壓縮的高額 CPU 開銷。這樣的設計，也可以使得對于同一個 CU 的 select（查詢）和 delete（删除）互不阻塞，提升并發能力。列存儲 CU 中資料更新，則是遵循 append-only（僅允許追加）原則的，即 CU 檔案僅會向後進行延展擴充，亦或是啟用新的 CU 檔案，而不是在對應行在 CU 中的位置就地更新。
ClickHouse
存儲結構
ClickHouse 支援在建表時，指定将資料按照某些列進行 sort by。排序後，保證了相同 sort key 的資料在磁盤上連續存儲，且有序擺放。在進行等值、範圍查詢時，where 條件命中的資料都緊密存儲在一個或若幹個連續的 Block 中，而不是分散的存儲在任意多個 Block， 大幅減少需要 IO 的 block 數量。另外，連續 IO 也能夠充分利用作業系統 page cache的預取能力，減少 page fault。
delete 政策
特點：缺少高頻率，低延遲的修改或删除已存在資料的能力。僅能用于批量删除或修改資料。
ClickHouse是個分析型資料庫。OLAP場景下，資料一般是不變的，是以 ClickHouse 對 update、delete 的支援是比較弱的，實際上并不支援标準的 update、delete 操作。
ClickHouse 通過 alter 方式實作更新、删除，它把 update、delete 操作叫做 mutation(突變)。
标準SQL的更新、删除操作是同步的，即用戶端要等服務端傳回執行結果（通常是int值），而ClickHouse的update、delete是通過異步方式實作的，當執行update語句時，服務端立即傳回，但是實際上此時資料還沒變，而是排隊等着。
Mutation具體過程
首先，使用where條件找到需要修改的分區；然後，重建每個分區，用新的分區替換舊的，分區一旦被替換，就不可回退；對于單獨一個分區，是原子性的；但對于整個 mutation，如果涉及多個分區，則不是原子性的。
PolarDB In-Memory Column Index
存儲結構
特點：PolarDB 将列存實作為 InnoDB 的二級索引。
在 PolarDB 中所有 Primary Index 和 Secondary Index 都實作為一個 B+Tree。列索引在定義上是一個 Index，但其實是一個虛拟的索引，用于捕獲對該索引覆寫列的增删改操作。
實作為 InnoDB 二級索引方案的優點：
- 查詢執行器的工程實作非常簡單
- 可以複用 InnoDB 的事務處理架構
- 可以複用 InnoDB 的資料編碼格式
- DDL 語句操作非常靈活
- 可以複用 InnoDB 的 Redo 事務日志子產品
- 二級索引與主表有一樣的生命周期，友善管理
PolarDB In-Memory Column Index 的存儲使用了無序且追加寫的格式。
列索引中記錄按 RowGroup 進行組織，每個 RowGroup 中不同的列會各自打包形成 DataPack。
每個 RowGroup 都采用追加寫，分屬每個列的 DataPack 也是采用追加寫模式。
對于一個列索引，隻有個 Active RowGroup 負責接受新的寫入。
當該 RowGroup 寫滿之後即當機，其包含的所有 DataPack 會轉為壓縮格儲存到磁盤上，同時記錄每個資料塊的統計資訊便于過濾。
列存 RowGroup 中每新寫入一行都會配置設定一個 RowID 用作定位，屬于一行的所有列都可以用該 RowID 計算定位，同時系統維護 PK 到 RowID 的映射索引，以支援後續的删除和修改操作。
delete 政策
在 PolarDB In-Memory Column Index 中，删除操作隻需要設定一個删除标記位。更新操作采用标記删除的方式來支援，對于更新操作，首先根據 RowID 計算出其原始位置并設定删除标記，然後在 ActiveRowGroup 中寫入新的資料版本。