以重疊的排序投影、壓縮欄位與可更新寫入儲存打造的讀取最佳化欄式資料庫，並以 snapshot isolation 取代查詢鎖定。
C-Store 是一套讀取最佳化的關聯式資料庫，其前提是 CPU 週期充裕而磁碟頻寬稀缺。它不儲存資料表加索引，只儲存 projection：一組組互相重疊的欄位集合，每組依自己的 sort key 排序，再水平切成 segment，並依欄位的排序方式與相異值數量挑選編碼進行大幅壓縮。更新先寫入以 B-tree 為底、體積很小的 Writeable Store，再由 LSM 風格的 tuple mover 批次搬進龐大的 Read-optimized Store；唯讀查詢則以 epoch 時間戳在 snapshot isolation 下執行，完全不設鎖。跨不同排序的 projection 重建完整資料列，靠的是 storage key 與 join index，而同一份冗餘也在 shared-nothing 叢集上提供 K-safety。在七道 TPC-H 風格查詢上，C-Store 平均比商用 row store 快 164 倍、比商用欄式產品快 21 倍，而且佔用的磁碟空間還更少。
2005 年，各大資料庫廠商清一色是記錄導向的儲存引擎：一筆 tuple 的各欄位連續擺放，一次磁碟寫入就能把整筆記錄推出去，上面再掛 B-tree 的 primary 與 secondary 索引。這種配置是寫入最佳化的，對 OLTP 極為稱職；但資料倉儲與其他讀取為主的系統（CRM、電子圖書目錄、各式臨機查詢系統）是週期性大量載入，接著長時間對超大表只掃描少數幾個欄位。市場上其實已有欄式產品，例如 Sybase IQ、Addamark 與 KDB，但它們通常把欄位維持在 entry sequence 順序，讓附加寫入很便宜，代價是這個順序幾乎不適合任何查詢。像 Walmart 這樣的倉儲營運者早已保留兩份資料副本，因為在 terabyte 等級資料上跑日誌復原的成本高得離譜；OLAP 廠商則仰賴預先計算的 data cube 與物化視圖，而那只有在查詢集合事先已知時才划算。C-Store 針對的正是它們無法處理的情境：在 shared-nothing 的商用叢集上，對無法事先預期的臨機查詢，同時還要支援線上更新。
C-Store 完全不儲存 base table，唯一的實體物件就是 projection：每個 projection 以某張邏輯表為 anchor，包含該表的一個或多個欄位，並可沿著一連串 n:1（外鍵）關係，把其他表的欄位一併拉進來。projection 保留重複列，因此列數與 anchor table 完全相同；它以欄為單位儲存，而其中每個欄位都依同一個 sort key 所定義的順序排列。因為 projection 本身就是排好序的物化結果，而不是無序堆積再外掛索引，對 sort key 的述詞就變成範圍掃描，相鄰數值也變得極易壓縮。所選的 projection 集合必須是 covering 的：每張表的每個欄位至少出現在一個 projection 中，任何 SQL 查詢才回答得出來。
同一個欄位可以出現在多個 projection 中，且在每個裡的排序方式不同，這是刻意背離 row store「每張表只有一份實體副本」的紀律。這份冗餘先換來可用性：管理者要求 K-safety 時，projection 與 join index 的配置必須保證任意 K 個節點失效後，仍存在一組 covering 的 projection 能映射到共同排序。它同時換來效能，因為最佳化器最主要的決策就是這個查詢該從哪個 projection 回答，而排序方式吻合的 projection 可以省掉排序、少讀資料。讓這份冗餘負擔得起的關鍵是積極壓縮：論文自己的評測 schema 有五個重疊 projection，佔用空間仍不到 row store 存放資料表加索引所需的一半。
RS 的每個欄位都以四種編碼之一壓縮，選擇依據兩項性質：這個欄位是依自身數值排序（self-order），還是依同一 projection 中其他欄位排序（foreign-order）；以及它含有多少相異值。排序正是製造出壓縮所需冗餘的來源，因此讓 projection 對查詢變快的那個決定，同時也讓它在磁碟上變小；兩個設計槓桿彼此加成而非互相牽制。這正是同時支援多種排序的理由：夠積極的編碼讓額外的排序順序不至於造成空間爆炸。每種編碼都在編碼後的物件上維護 densepack 的 B-tree，壓縮因此不會犧牲可搜尋性。
查詢執行器由十種節點型別組成，其運算元與結果是 projection、column 與 bitstring，而非資料列；運算子被寫成直接吃壓縮表示法，而不是先解壓再處理。Select 不會限縮輸入，而是產出一個 bitstring，之後再由 Mask 套用；BAnd、BOr、BNot 則負責合併 bitstring，讓述詞可以組合而完全不必物化 tuple。對 Type 2 欄位做 Select 時，即使該欄位並未依此值排序，也只需讀入符合述詞的那幾個 bitmap——這種執行計畫在 row 引擎中根本無從表達。論文明確指出：帶來效能優勢的關鍵是「能在壓縮資料上運算」，而不只是欄式配置本身。
把欄位維持在 entry sequence 以外的排序，會讓原地插入的代價高到無法接受，於是 C-Store 把儲存拆成兩個引擎：一個為高效能插入與更新而設計的小型 Writeable Store，以及一個只接受由 WS 批次搬入的龐大 Read-optimized Store。WS 實作與 RS 完全相同的邏輯設計——一樣的 projection、一樣的 sort key、一樣的 join index——因此只需要寫一套最佳化器；但它以未壓縮的 (value, storage key) 配對存在 B-tree 中，並預期大致常駐於記憶體。背景的 tuple mover 執行借自 LSM-tree 的 merge out：把有序的 WS 物件與 RS 大區塊合併，產生一份新的 RS，完成後再掛上。刪除只做標記，更新等於一次插入加一次刪除，最後全部由 tuple mover 掃進壓縮側。
唯讀查詢以 historical mode 執行，取一個不晚於全系統 high water mark 的有效時間；在該時間點之前已無未提交交易，因此這類查詢完全不設任何鎖，也不會與更新流互相干擾。讀寫交易仍採嚴格兩階段鎖定，但日誌只寫 UNDO 記錄——REDO 由「從其他節點存活的 projection 複製狀態」取代——而分散式提交則完全省略 two-phase commit 的 PREPARE 階段。這之所以安全，唯一理由是 K-safety 保證資料另有副本：被通知提交卻在寫入任何持久資料前當機的節點，靠查詢其他 projection 重建自身狀態。換言之，C-Store 是拿 redo log 與 2PC 的一般性，去換那份為了可用性本來就已經付費的冗餘。
projection 的寫法是欄位清單後接一條垂直線再接 sort key，例如 EMP2(dept, age, DEPT.floor | DEPT.floor)；tuple 依 key 欄位由左至右排序，而其中 K 個欄位各自成為一個資料結構。每個 projection 會水平切成一或多個 segment，帶有大於零的 segment identifier（Sid）；C-Store 只支援以 projection 的 sort key 做 value-based 分割，因此每個 segment 擁有一段 key range，而所有 range 恰好切分整個鍵空間。segment 也是叢集上的配置單位：同一個 segment 的所有欄位必須同址，join index 與其 sender segment 同址，每個 WS segment 則與涵蓋相同 key range 的 RS segment 同址。決定 projection、segment、sort key 與 join index 的組合，就是 C-Store 的實體設計問題，須在給定的訓練工作負載與空間預算 B 之下，由工具自動求解並滿足所需的 K-safety。
在一個 segment 內，每個欄位的每個值都關聯到一個 storage key；同一 segment 中不同欄位若 storage key 相同，就屬於同一個邏輯列。在 RS 中，storage key 就是該記錄在 segment 內的序號，從不儲存而是按需計算；在 WS 中則明確存為整數，且大於任何 RS storage key，由節點本地計數器加上站台 id 產生，因此節點之間不必為了配發 key 而彼此同步。從 projection T1 到 T2 的 join index，是一組以 segment 為單位的表格，每列形如 (s: T2 中的 Sid, k: segment s 中的 storage key)，每個 tuple 一列；由於兩個 projection anchor 在同一張表，這永遠是一對一映射，等價於把 T1 的排序重排成 T2 的排序。要重建一張表，必須找到一條 join index 路徑，把每個欄位都帶到某個共同排序上；論文刻意把每個欄位放進多個 projection，就是為了少維護幾條 join index，因為兩端任一次修改都得同步更新它。
Type 1（self-order、相異值少）以三元組 (v, f, n) 序列表示，分別是數值、首次出現位置與出現次數，因此位置 12 到 18 的一串 4 就是 (4, 12, 7)；每個相異值一個三元組，並在 value 欄位上建 clustered B-tree。Type 2（foreign-order、相異值少）以 (v, b) 配對表示，b 是標記 v 出現位置的 bitmap，例如欄位 0,0,1,1,2,1,0,2,1 編成 (0, 110000100)、(1, 001101001) 與 (2, 000010010)；稀疏 bitmap 本身再做 run length encoding，並以 offset index B-tree 把位置映回數值。Type 3（self-order、相異值多）是以區塊為單位的差值編碼：每個 block 的第一筆是實際數值與其 storage key，之後每筆都是與前一筆的差，於是 1,4,7,7,8,12 變成 1,3,3,0,1,4。Type 4（foreign-order、相異值多）則不做編碼；由於 RS 沒有線上更新，上述 B-tree 都能 densepack、不留空隙，搭配 64 至 128K 的大磁碟區塊，樹高可壓在 2 層以內。
WS 同樣是欄式儲存，實作與 RS 完全相同的實體設計，但一律不壓縮，因為相對 RS 而言 WS 的體積被假設微不足道；WS 也以相同方式分割，因此 WS 與 RS 的 segment 是一對一對應。每個欄位是一組 (v, sk) 配對，放在以 storage key 為鍵的傳統 B-tree 中；此外每個 projection 還額外維護 (s, sk) 配對的 B-tree，鍵為 sort key 欄位，sk 是 sort key 值 s 首次出現的 storage key。因此以 sort key 搜尋時，先用後者找出感興趣的 storage key，再透過各欄位的 B-tree 取回該記錄的其餘欄位。一次插入會變成每個 projection 的每個欄位各一次實體插入，再加上 sort key 結構，全部共用同一個 storage key；這正是此設計建在 BerkeleyDB B-tree 之上、並仰賴超大緩衝池讓熱資料常駐記憶體的原因。
時間被切成粗粒度的 epoch，預期每個長達數秒以上，並指定一個節點擔任 timestamp authority（TA）。要推進 high water mark 時，TA 廣播 end of epoch 訊息；每個節點把 current epoch 由 e 增為 e+1，使新到的交易以時間戳 e+1 執行，接著等待所有在 epoch e 或更早開始的交易完成，再回覆 epoch complete；當 TA 收齊所有節點的回覆後，就把 HWM 設為 e 並廣播出去，之後唯讀交易即可讀取 epoch e 以前的資料，完全不必設鎖，且保證讀到的都是已提交資料。可見性是逐筆計算的，依據是記錄每筆 WS 記錄插入 epoch 的 insertion vector（IV），以及每筆記錄存放 0 或刪除 epoch 的 deleted record vector（DRV）；DRV 因為必須可更新而存在 WS，又因幾乎全是 0 而以 Type 2 bitmap 方式壓縮，至於 RS 則不需要 IV，因為 tuple mover 保證 RS 中沒有任何記錄是在 LWM 之後插入的。low water mark 則限定查詢能回溯多遠，避免支援一般 time travel 的沉重代價；epoch 編號也預計像 TCP 序號那樣，在沒有任何 DRV 仍指向舊值後回繞重用。
tuple mover 以背景工作的形式運行，尋找值得處理的 (RS, WS) segment 配對，每次對一組執行 merge-out 流程（MOP）。MOP 會找出所選 WS segment 中插入時間在 LWM 之前（含）的所有記錄，並一分為二：同樣在 LWM 之前（含）就被刪除的直接丟棄，因為使用者不可能查到它們存在的那段時間；其餘則搬進 RS。它會建立新的 segment RS'，讀入舊 RS segment 的欄位區塊，丟掉 DRV 值小於等於 LWM 的項目，再把 WS 的欄位值合併進來，邊合併邊寫入逐漸長大的 RS'；RS' 中最新的插入時間成為該 segment 新的 tlastmove，且必定小於等於 LWM。由於記錄在 RS' 中會取得新的 storage key，所有指向該 segment 的 join index 都必須維護；等 RS' 與其索引都完成後，系統才從 RS 切換到 RS' 並釋放舊空間——之所以採用 old-master/new-master 而非原地更新，是因為反正幾乎每個資料物件都會被搬動。
讀寫交易以嚴格兩階段鎖定設置讀寫鎖，各節點共同構成分散式鎖表，死結則以 timeout 偵測並中止其中一個交易來化解。日誌採 NO-FORCE、STEAL 政策，但只寫 UNDO 記錄，且如同 ARIES 採邏輯日誌，因為對 WS 的 B-tree 做實體日誌會產生太多筆記錄；rollback 就是反向掃描這份 UNDO 日誌。每個交易都有一個 master，負責把工作分派到各節點並決定最終結果；收到 COMMIT 後，它等所有 worker 完成未竟動作，再直接送出 commit 或 abort，中間沒有 PREPARE 階段，因此某個節點有可能被通知提交後，卻在任何更新或日誌落到穩定儲存前就當機。復原分三種情況：沒有資料遺失的節點，只需把別處排隊的更新往前套用；RS 與 WS 同時全毀的災難性故障，只能從其他 projection 與 join index 重建；最常見的則是 WS 損壞但 RS 完好，此時該節點對遠端 projection 發出復原查詢，取回 insertion_epoch 大於本地 tlastmove 且小於等於 HWM、deletion_epoch 為 0 或大於等於 LWM 的 tuple，最後再套用排隊中的更新。
C-Store 幾乎立刻被商品化為 Vertica，而 2012 年那篇 VLDB 論文讀來就像一份「哪些 C-Store 構想撐過了真實客戶考驗」的報告：帶明確排序的 projection、以不同排序冗餘副本達成的 K-safety，以及「寫入最佳化儲存加讀取最佳化儲存再配 tuple mover」的拆分，全都成功出貨；join index 則被捨棄，改用涵蓋整張表所有欄位的 super projection。壓縮這條線發展成 Abadi 一系列關於壓縮感知執行與 late materialization 的論文，以及 2008 年那份證明「在 row store 內模擬欄式儲存只能取回一小部分好處」的比較研究。「運算子應該直接吃壓縮、以區塊為單位的欄資料」這個想法，與 MonetDB/X100 及 VectorWise 匯流成今日 DuckDB、ClickHouse、Redshift 與 Snowflake 所採用的向量化執行模型。Hadoop 與 lakehouse 時代的欄式檔案格式——Parquet、ORC、Arrow、Snowflake 的 micro-partition、BigQuery 的 Capacitor——都承襲了 run-length、字典與差值編碼，以及 C-Store 的 RS 所定義的不可變、densepack 區塊配置。RS/WS 這個模式則在任何必須吸收寫入的分析型儲存中重現：Vertica 的 ROS 與 WOS、Druid 的 real-time 與 historical segment，以及 Hudi 與 Iceberg 的 merge-on-read 表。最後，以 epoch 時間戳建立快照的機制，也預示了 Snowflake、Delta Lake 與 Iceberg 今日直接開放給使用者的 snapshot 與 time travel 語意。
“CPUs are getting faster at a much greater rate than disk bandwidth is increasing. Hence, it makes sense to trade CPU cycles, which are abundant, for disk bandwidth, which is not.”
“As will be shown in Section 9, the ability to process compressed data is the key to the performance benefits of C-Store.”
“In summary, for this seven query benchmark, C-Store is on average 164 times faster than the commercial row-store and 21 times faster than the commercial column-store in the space-constrained case.”