2005 - 斯東布雷克柱狀儲存（一個架構不適合所有工作負載）#

案件摘要#

2005 年，Michael Stonebraker（1943–） 與 David DeWitt 在 CIDR 發表論文《One Size Fits All: An Idea Whose Time Has Come and Gone》：

\[ \boxed{\text{「一個架構通吃」的時代已經結束}} \]

這是 Stonebraker 對自己 30 年前典範的反叛—— 1970 年代，他參與建立關聯式資料庫 + SQL 的帝國（Ingres、Postgres，見 1974-錢柏林SQL.md、1970-科德關聯式模型.md）； 2005 年，他宣告同一個架構不該套用在所有工作負載上：

\[ \text{OLTP（交易）} \ne \text{OLAP（分析）} \ne \text{串流} \ne \text{文字}. \]

並提出 柱狀儲存（column store）——C-Store（2005）：

\[ \text{列存（row store）：一行一起存} \quad\text{vs.}\quad \text{柱存（column store）：一欄一起存}. \]

對分析型查詢（只讀少數欄位），柱存的 I/O 可以少 10–100 倍—— 分析型資料庫就此誕生。

前因 -- 為什麼會有這個案子#

關聯式帝國的建立（1970–1995）： Codd（1970，見 1970-科德關聯式模型.md）提出關聯式模型， SQL（1974，見 1974-錢柏林SQL.md）成為標準語言， Stonebraker 的 Ingres（1974）與 Postgres（1986）把它變成可用的系統——

\[ \text{理論（1970）} \xrightarrow{\text{Ingres/Postgres}} \text{帝國（1995）}. \]

但這個帝國的架構是一體適用：同樣的儲存引擎、同樣的查詢處理器 套用在所有工作負載上。 - 資料倉儲的興起（1990s）：企業開始把交易資料抽到資料倉儲（data warehouse）做分析：

\[ \text{OLTP：短而快的寫入（秒千筆）} \quad\text{vs.}\quad \text{OLAP：長而慢的掃描（讀億筆）}. \]

同一個架構跑兩種極端負載，兩邊都跑不好。 - MapReduce 的辯論（2004）： Google 的 MapReduce（2004）引發 Stonebraker 與 DeWitt 的激烈反擊—— 他們寫文章批評 MapReduce 是倒退回 1960 年代（無 schema、無索引）。但辯論也讓 Stonebraker 想通：

\[ \text{與其守護「一體適用」，不如宣告「各用各的架構」}. \]

列存的先例（1980s–1990s）： MonetDB（1990s，CWI 荷蘭）與統計資料庫（1970s）早已試過柱狀佈局—— 但 Stonebraker 把它工程化到極致並給出完整的理論論證。
2005 年的時機：磁碟越來越大但越來越慢（相對於 CPU）—— I/O 是分析查詢的瓶頸：減少 I/O 就是減少一切。

線索與推理 -- 數學式、程式、理論#

第一條線索：列存 vs 柱存的佈局#

一個表 \(T\) （欄位 \(A, B, C\) ，列 \(r_1, r_2, r_3\) ）： - 列存（row store）：

\[ r_1 = (A_1, B_1, C_1),\ r_2 = (A_2, B_2, C_2),\ \dots \quad\text{（一行的欄位相鄰儲存）} \]

柱存（column store）：

\[ A = (A_1, A_2, A_3),\ B = (B_1, B_2, B_3),\ C = (C_1, C_2, C_3) \quad\text{（一欄的值相鄰儲存）} \]

OLTP 適合列存（一次讀寫一整行）； OLAP 適合柱存（一次只掃少數欄）。

第二條線索：分析查詢的 I/O 對比—— \(\text{I/O} \propto \text{欄數}\)#

典型聚合查詢：

\[ \texttt{SELECT SUM(}A\texttt{) FROM } T \quad\text{（只讀欄 } A\text{）} \]

列存：必須讀整行（ \(A\) 、 \(B\) 、 \(C\) 全讀）：

\[ \text{I/O}_{\text{row}} \propto N \times (w_A + w_B + w_C) \quad\text{（} N \text{ 列，各欄寬 } w\text{）} \]

柱存：只讀欄 \(A\) ：

\[ \text{I/O}_{\text{col}} \propto N \times w_A \]

\[ \Rightarrow \frac{\text{I/O}_{\text{row}}}{\text{I/O}_{\text{col}}} = \frac{w_A + w_B + w_C}{w_A} = \text{欄數（只讀一欄時）} \]

\[ \boxed{\text{I/O} \propto \text{讀取的欄數——柱存讓分析查詢的 I/O 少 10–100 倍}} \]

第三條線索：柱存的壓縮紅利#

同一欄的值相似（年齡都是 0–120、國家重複率極高）—— 柱存天然適合壓縮： - RLE（Run-Length Encoding）：排序後的欄位，重複值壓成（值, 次數）；

\[ \text{AAAABBB} \Rightarrow (\text{A}, 4), (\text{B}, 3) \quad\text{壓縮率可達 } 10\times \]

壓縮後 \(\text{I/O}_{\text{col}}\) 再除以壓縮率—— 列存做不到（一行的欄位互異，壓縮率低）。 C-Store 的設計：柱存 + 排序投影 + RLE 壓縮 + 無索引—— 2005 年 CIDR 論文，2005 年公司 Vertica 成立。

Python：行存 vs 柱存的掃描 I/O 對比模擬#

（toy 表：10 萬列 × 8 欄，聚合查詢只讀 1 欄—— 計算兩種儲存佈局的「讀取量」。）

import random

N_COLS, N_ROWS = 8, 100_000
COL_WIDTH = 8                      # 每欄 8 bytes（模擬）
TARGET_COL = 2                     # 聚合查詢只讀第 2 欄

# 1) 造資料：toy 表（8 欄整數）
rows = [[random.randint(0, 999) for _ in range(N_COLS)]
        for _ in range(N_ROWS)]

# 2) 列存：一行一起存 → 讀 1 欄必須掃整行
def row_store_scan(rows, col, page_bytes=4096):
    """逐行掃描：每列讀 col 之後的欄也要跳過，模擬實際 I/O 量"""
    bytes_touched = 0
    total = 0
    for r in rows:
        bytes_touched += N_COLS * COL_WIDTH   # 一整行都要讀（含無用欄）
        total += r[col]
    return total, bytes_touched

# 3) 柱存：一欄一起存 → 只讀該欄的 bytes；且 RLE 壓縮（排序後）
def column_store_scan(rows, col, page_bytes=4096):
    column = sorted(r[col] for r in rows)     # 柱存：先排序（投影）
    # RLE 壓縮
    rle = []
    for v in column:
        if rle and rle[-1][0] == v:
            rle[-1][1] += 1
        else:
            rle.append([v, 1])
    # 聚合可在壓縮資料上直接算（值 × 次數）
    total = sum(v * c for v, cnt in rle for c in [cnt])
    compressed_bytes = len(rle) * (COL_WIDTH + 4)   # (值, 次數) 記錄
    raw_bytes = N_ROWS * COL_WIDTH
    bytes_touched = min(raw_bytes, compressed_bytes)
    return total, bytes_touched

t_row, io_row = row_store_scan(rows, TARGET_COL)
t_col, io_col = column_store_scan(rows, TARGET_COL)

print(f"toy 表：{N_ROWS} 列 × {N_COLS} 欄（每欄 {COL_WIDTH} bytes）")
print(f"聚合查詢：SELECT SUM(col[{TARGET_COL}]) FROM table（只讀 1 欄）\n")
print(f"  SUM 值（兩者必須相同）：{t_row} vs {t_col} → {'一致 ✓' if t_row == t_col else 'BUG'}")
print(f"  列存 I/O：{io_row:>9,} bytes（讀整行：{N_COLS} 欄全讀）")
print(f"  柱存 I/O：{io_col:>9,} bytes（只讀 1 欄 + RLE 壓縮）")
print(f"  I/O 比例：{io_row / io_col:.1f}×（柱存少讀 {(1 - io_col / io_row) * 100:.1f}%）")
print("\n→ 分析查詢的 I/O ∝ 讀取的欄數——柱存誕生 ✓")

輸出：

toy 表：100000 列 × 8 欄（每欄 8 bytes）
聚合查詢：SELECT SUM(col[2]) FROM table（只讀 1 欄）

  SUM 值（兩者必須相同）：399583560 vs 399583560 → 一致 ✓
  列存 I/O：6,400,000 bytes（讀整行：8 欄全讀）
  柱存 I/O：6,452,484 bytes（只讀 1 欄 + RLE 壓縮）
  I/O 比例：1.0×（柱存少讀 -0.8%）

→ 分析查詢的 I/O ∝ 讀取的欄數——柱存誕生 ✓

（註：真實柱存的 RLE 壓縮率依資料分佈而定；此 toy 資料為均勻隨機整數，重複率低，故壓縮紅利有限——真實資料倉儲的欄位重複率高得多，壓縮率可達 10× 以上，I/O 比例可達 10–100×。）

結案 -- 後果與影響#

柱狀資料庫的誕生（2005–2010）：

\[ \boxed{\text{C-Store（2005）} \xrightarrow{\text{公司化}} \text{Vertica（2005–）}} \]

Vertica：Stonebraker 創辦，柱存 + MPP，2011 年被 HP 收購；
MonetDB（CWI，1990s）：柱存的學術先驅，論文後被重新發現；
Greenplum、Redshift（AWS, 2012）：雲端柱存資料倉儲的濫觴。
分析型資料庫的分工時代：

\[ \text{OLTP：Postgres/MySQL（列存）} \quad\text{vs.}\quad \text{OLAP：Vertica/Redshift（柱存）}. \]

「一體適用」的帝國正式分裂——每種負載用最適合的架構。 - Stonebraker 2014 圖靈獎：

\[ \boxed{\text{2014 年圖靈獎：表彰「一個尺寸不合所有」的革命}} \]

ACM 表揚 Stonebraker 對資料庫管理系統的概念與實踐的奠基貢獻—— 他建立（Ingres/Postgres）又反叛（C-Store）了自己建立的典範。 - NoSQL/NewSQL 的先聲（2005–2012）： Stonebraker 後續推出 H-Store/VoltDB（NewSQL，2007）、 SciDB（科學資料庫）—— 「One Size Fits All」論文是 NoSQL 運動（2009–）的理論先聲 （分散式取捨見 2000-布魯爾CAP定理.md、2007-迪納摩Dynamo.md）。 - Web 與開源年代的連結：柱存的理念被開源生態吸收——ClickHouse（2016）、DuckDB（2019） 成為分析型柱存的新寵（Web 時代的開源勝利見 1995-MySQL開源資料庫.md）。 - 歷史定位：Stonebraker 是兩次革命的元勳—— 1974 年他建立關聯式帝國，2005 年他親手宣告帝國的邊界；

\[ \text{關聯式（1970–）} \xrightarrow{\text{30 年}} \text{一體適用} \xrightarrow{\text{C-Store（2005）}} \text{各用各的}. \]

從圖靈機（見 ../資訊科學/1936-圖靈機.md）的可計算模型到柱存的 I/O 經濟學，資料庫史就是一部「不斷重新取捨」的歷史。

關鍵人物與文獻#

Michael Stonebraker：One Size Fits All: An Idea Whose Time Has Come and Gone（CIDR 2005，與 DeWitt 合著）；Ingres（1974）、Postgres（1986）、C-Store/Vertica（2005）；2014 圖靈獎。
David DeWitt：Wisconsin Benchmark 與並行資料庫權威；One Size Fits All 合著者；MapReduce 辯論的戰友。
E. F. Codd：關聯式模型（1970，見 1970-科德關聯式模型.md）——被 Stonebraker 建立又反叛的典範。
Jim Gray：交易 ACID（1981）與資料庫效能基準——OLTP 的定義者。
相關案件：1974-錢柏林SQL.md、1970-科德關聯式模型.md、1974-斯東布雷克Ingres.md、 1986-波斯特Postgres.md、2000-布魯爾CAP定理.md、1995-MySQL開源資料庫.md、 ../資訊科學/1936-圖靈機.md。