实验 01：数据布局 —— 行存与列存
为什么做这个实验
同一张表，按行连续存放还是按列连续存放，字节数完全一样，查询快慢却能差出一倍以上。本实验要把这个差距量出来，并解释它到底来自哪里。
反直觉的地方有两个。第一，**读的字节少不一定快**：多列点查在列存里只读 5.0 KB，比行存的 7.5 KB 更少，结果却更慢——因为真正决定快慢的是 I/O **请求次数**（行存 1 次、列存 2 次），每次请求都要先付一次"起步价"（SSD 4 KiB 随机读约 150 μs，机械盘寻道约 10 ms），而几千字节的传输时间相比之下可以忽略。第二，**你在笔记本里测出来的毫秒数不等于磁盘上的差距**：数据在 Python 进程内、文件又小，文件系统缓存把磁盘时间抹平了，剩下的只有一个零头。要看到确定的结论，得盯住两个与机器无关的确定性指标——I/O 请求次数与传输字节数，而不是墙钟时间。
做完这个实验，你应该能回答：一个查询该用行存还是列存？为什么列越多、投影越窄，列存越赚？以及为什么"点查比请求次数、聚合比字节数"。
运行前准备
1. Python 3.10 及以上（本笔记本用了 `list[Book]` 这类新式类型标注）。
2. 安装依赖（在仓库根目录执行）：
```bash
pip install pandas numpy matplotlib seaborn faker jupyter
```
验证方式：
```python
import pandas, numpy, matplotlib, seaborn, faker
print("环境 OK")
```
3. 必须**从仓库根目录**（其下有 `system/` 与 `notebooks/`）启动 Jupyter，否则下一个代码单元格的 `from system.data_classes import *` 会报 `ModuleNotFoundError`：
```bash
jupyter notebook notebooks/Data-Layout.ipynb
```
4. 本笔记本会在当前目录生成两个临时文件 `row.csv`、`column.csv`，最后一个代码单元格负责删除它们。
import sys, pathlib
# Put the repo root (the directory containing `system/`) on sys.path so
# `from system...` works whether this notebook is opened from its own
# folder or from the repo root.
for _p in (pathlib.Path.cwd(), *pathlib.Path.cwd().parents):
if (_p / "system").is_dir():
if str(_p) not in sys.path:
sys.path.insert(0, str(_p))
break一、背景：二维表放进一维字节流
数据库的表是二维的（行 × 列），磁盘给出的地址空间却是一维的。把二维表放进一维空间必须做一次**线性化（linearization）**——决定先铺哪一维。基本铺法只有两种：
| 布局 | 常用别名 | 字节排列 |
| --- | --- | --- |
| 行式 row-major | NSM（n-ary storage model） | `T1 A1 P1 │ T2 A2 P2 │ T3 A3 P3 │ …` |
| 列式 column-major | DSM（decomposition storage model） | `T1 T2 T3 │ A1 A2 A3 │ P1 P2 P3` |
（T = title，A = author，P = price，下标是行号。）
两种布局的字节数完全相同，差别只在"哪些字节相邻"。查询顺着这个顺序访问就快，跟它打架就要付随机访问的代价。NSM / DSM 这组命名出自 Ailamaki、DeWitt、Hill、Skounakis 等人 2001 年发表于 VLDB 的《Weaving Relations for Cache Performance》。
"线性化"不只发生在写文件的时刻：内存里多维数组的布局、网络传输的序列化格式、列存中一列的字节排列，本质上都是同一个决定，所以本实验的结论对它们同样成立。
为教学方便，本笔记本用 CSV 文本文件模拟两种布局；真实数据库用二进制格式（省掉文本解析开销，但布局原理完全一样）。
二、造一份假数据
用 `faker` 造 10 000 条"书目"记录，三个字段：`title`（随机句子）、`author`（随机人名）、`price`（0–100 的浮点）。
先 `Faker.seed(42)` 固定随机种子，保证每个人造出来的数据一致，后面测出的数字才有可比性。
`number_of_tuples` 是本笔记本唯一的规模旋钮。想看更明显的差距可以调到 20 万，但 `faker` 造数据会明显变慢，建议先保持 1 万把流程跑通。
from system.data_classes import *
from faker import Faker
Faker.seed(42)
fake: Faker = Faker()
number_of_tuples: int = 10000
# create some fake data mimicking tuples in a relation
books: list[Book] = [
Book(
fake.sentence(),
fake.name(),
fake.pyfloat(min_value=0, max_value=100, right_digits=2),
)
for i in range(number_of_tuples)
]
books[:10][Book(title='Agent every development say.', author='Stephanie Miller', price=54.4),
Book(title='Behavior discussion own.', author='Michelle Miles', price=53.28),
Book(title='Operation speak according south recently future choice.', author='Gabrielle Davis', price=12.45),
Book(title='Page southern role movie win her.', author='Sandra Montgomery', price=46.73),
Book(title='Relate animal direction eye bag.', author='Brian Ramirez', price=81.46),
Book(title='Have decide environment view.', author='Lisa Jackson', price=93.31),
Book(title='Left establish understand read.', author='Frederick Tate', price=7.29),
Book(title='Source husband at.', author='Latoya Robbins', price=27.83),
Book(title='How trip learn enter east no enjoy.', author='Stephanie Ross', price=28.17),
Book(title='Management sense technology check civil quite others.', author='Kyle Mcdonald', price=32.7)]装进 DataFrame
把 10 000 个 `Book` 对象（`Book` 来自 `system/data_classes.py`，一个只装三个字段的数据类）转成 pandas 的 `DataFrame`，列名即 `["title", "author", "price"]`。
后面所有"写文件"和"读文件"都以这同一个 DataFrame 为起点——两种布局看到的是**完全相同**的数据，唯一的变量是排列顺序。这就是受控实验要做的事：只改一个因素，其余全部固定。
from pandas import DataFrame, read_csv
# store data in pandas dataframe:
schema: list[str] = ["title", "author", "price"]
df: DataFrame = DataFrame(data=books, columns=schema)
df title author \
0 Agent every development say. Stephanie Miller
1 Behavior discussion own. Michelle Miles
2 Operation speak according south recently futur... Gabrielle Davis
3 Page southern role movie win her. Sandra Montgomery
4 Relate animal direction eye bag. Brian Ramirez
... ... ...
9995 Remember result act. Mark Clark
9996 Tonight list Democrat year forward. Danny Walker
9997 President star room partner. Jennifer Chavez
9998 Well bag develop support. Katherine Ramos
9999 Such create material. Devin Watts
price
0 54.40
1 53.28
2 12.45
3 46.73
4 81.46
... ...
9995 29.10
9996 57.94
9997 0.26
9998 6.50
9999 3.26
[10000 rows x 3 columns]三、模拟行存：元组一个接一个写出去
行式布局的要求是：第 1 个元组的三个字段连续，接着第 2 个元组的三个字段……
代码里用一个小技巧实现：`to_csv(sep="\n")` 让每个字段各占一行，于是 3 字段 × 10 000 行 = 30 000 行文本，其中第 `3i`、`3i+1`、`3i+2` 行正好构成第 `i` 个元组。读回来时用默认分隔符，每行就是一个字段值。
> **两处代码改动及原因**
>
> 1. 部分 pandas 版本不接受换行符作分隔符，会抛 `ValueError: bad delimiter value`，这一格会直接跑不过去。因此写成"先试 `to_csv(sep="\n")`，失败则用手写循环"——两条路径产出的文件内容等价（都是每个字段一行）。你的 pandas 若接受 `sep="\n"`，走的仍是原来的写法。
> 2. 查看文件内容的 `!head` 换成了 Python 读取：`!head` 是 shell 魔法命令，Windows 的 cmd 里没有 `head`，会直接报错。
# 把数据按行主序写进文件，模拟行存
path_row: str = "row.csv"
# 每个字段各占一行：第 3i、3i+1、3i+2 行构成第 i 个元组
try:
df.to_csv(path_or_buf=path_row, sep="\n", header=False, index=False, mode="w")
except ValueError:
# 部分 pandas 版本不接受换行符作分隔符，这里手写等价输出，文件内容完全相同
with open(path_row, mode="w", encoding="utf-8", newline="") as _f:
for _row in df.itertuples(index=False):
for _value in _row:
_f.write(f"{_value}\n")# 看看文件开头：每三个字段一组，组内连续
with open(path_row, encoding="utf-8") as _f:
print("".join(_f.readlines()[:6]))四、模拟列存：一列一列写出去
列式布局的要求是：整列 `title` 连续，接着整列 `author`，再接着整列 `price`。
做法是逐列调用 `to_csv`：第一次用 `mode="w"` 截断文件，之后用 `mode="a"` 追加。
产出的文件同样是 30 000 行，但一行属于哪一列由 `i // number_of_tuples` 决定（0 = title，1 = author，2 = price），它在该列内的行号是 `i % number_of_tuples`。这组"除数 / 余数"就是列式布局的坐标公式，下一节的读代码会原样用到它。
# write data into file in column-major layout to emulate store
path_column: str = "column.csv"
attribute_index: int
col: str
for attribute_index, col in enumerate(df.columns):
df.to_csv(
path_or_buf=path_column,
columns=[col],
header=False,
index=False,
mode=(
"w" if attribute_index == 0 else "a"
), # truncate file before first column, append afterward
)# 看看文件开头：先是一万条 title，之后才轮到 author
with open(path_column, encoding="utf-8") as _f:
print("".join(_f.readlines()[:3]))五、查询 1：多列点查 `LIMIT 314 OFFSET 100`
```sql
SELECT author, price
FROM books
LIMIT 314
OFFSET 100
```
这个查询要的是**连续的一段行**（第 101～414 行，共 314 行），但每行要**多个字段**（author、price）。
• 行式布局下，这 314 行的字节完全连成一片；
• 列式布局下，`author` 和 `price` 是两个互不相干的连续区间，中间隔着整列 `title`。
理论上行存更优。下面分别在两种布局上跑并计时。
行式布局下的读法
`read_csv` 的 `skiprows` 可以接受一个函数，对每一行号返回 True（跳过）或 False（保留）。行式布局的判定是"行号对 3 取余"：
• `line_number < offset * len(schema)`：OFFSET 之前的全部跳过（前 100 个元组 = 300 行）；
• `line_number % len(schema) not in attr_idxs`：只留 `author`（下标 1）和 `price`（下标 2），`title`（下标 0）跳过；
• `nrows=limit * len(attr_idxs)`：读满 314 × 2 = 628 个值就停。
读进来之后还要把值拼回元组：`data.iloc[i + j]` 是**连续访问**，正是行式布局的取数方式。这一步不能省——它模拟的是数据库把字段物化成一条记录的开销；只计时读文件，会把两种布局的差距抹掉一大半。
from time import time_ns
attr_idxs: list[int] = [1, 2]
# start row:
offset: int = 100
# number of rows to consider:
limit: int = 314
row_start: int = time_ns()
# execute query given row-major layout:
data: DataFrame = read_csv(
filepath_or_buffer=path_row,
header=None,
skiprows=lambda line_number: line_number
< offset * len(schema) # before offset, computes which rows to skip from the input
or line_number % len(schema)
not in attr_idxs, # wrong attribute: we are after the offset but only want to read the attribute values projected to
nrows=limit * len(attr_idxs), # do not exceed limit
)
i: int
for i in range(0, len(attr_idxs) * limit, len(attr_idxs)):
# construct tuple by consecutive accesses
l = [data.iloc[i + j][0] for j in range(len(attr_idxs))]
# print(l, sep=", ")
row_end: int = time_ns()
print("Time row-major:", round((row_end - row_start) / 1000000, 1), "ms")Time row-major: 9.6 ms
列式布局下的读法
同样的 `skiprows`，坐标换算换成列式的"除数 / 余数"：
• `line_number % number_of_tuples < offset`：列内行号落在 OFFSET 之前，跳过；
• `line_number % number_of_tuples >= offset + limit`：列内行号超过 LIMIT，跳过；
• `line_number // number_of_tuples not in attr_idxs`：不属于被投影的两列，跳过。
拼元组时用的是 `data.iloc[j * limit + i]`：同一个元组的两个字段相隔 `limit` 个位置，这是**跨列跳着取**，也就是列式布局在点查场景下的取数方式。注意对比上一格的行式写法——一个加 `j`，一个加 `j * limit`，这一行代码就是两种布局的全部差别。
column_start: int = time_ns()
# execute query given column-major layout
data: DataFrame = read_csv(
filepath_or_buffer=path_column,
header=None,
skiprows=lambda line_number: line_number % number_of_tuples
< offset # before offset
or line_number % number_of_tuples >= offset + limit # after limit in column
or line_number // number_of_tuples not in attr_idxs, # wrong column index
nrows=limit * len(attr_idxs), # break after this many entries have been produced
)
i: int
for i in range(limit):
# construct tuple by random accesses:
l = [data.iloc[j * limit + i][0] for j in range(len(attr_idxs))]
# print(l, sep=", ")
column_end: int = time_ns()
print("Time column-major:", round((column_end - column_start) / 1000000, 1), "ms")Time column-major: 10.9 ms
观察与解释
把两次打印的毫秒数记下来。本机实测（1 万行，同一格重跑 7 次取中位数）：
| 查询 | 行式 | 列式 | 列式 / 行式 |
| --- | --- | --- | --- |
| 多列点查（314 行投影 2 列） | 23.3 ms | 30.0 ms | 1.29×（行式更快） |
单次运行的波动很大（同一段代码在不同轮次里能从 19 ms 跳到 42 ms），所以**必须多跑几次取中位数**再下结论。
方向符合预期，但差距远没有 I/O 模型暗示的那么悬殊。原因是这里根本没有磁盘 I/O：CSV 只有几百 KB，第一次读完之后就进了文件系统缓存，剩下的全是内存操作；而 314 个小元组在内存里无论怎么取，都只是几十毫秒里的一小部分——真正的开销是 `read_csv` 的文本解析和 pandas 的索引，两种布局各付一份，把布局带来的差距稀释掉了。
要看确定的结论，得看两个与机器无关的指标。用手算模型（20 万行、字段定长 8 字节、块大小 64 KiB）得到的口径是：
| 查询 | 布局 | I/O 请求次数 | 读取字节量 |
| --- | --- | --- | --- |
| 点查 314 行投影 2 列 | 行式 | 1 | 7.5 KB |
| 点查 314 行投影 2 列 | 列式 | 2 | 5.0 KB |
| 全表聚合单列 | 行式 | 74 | 4.8 MB |
| 全表聚合单列 | 列式 | 25 | 1.6 MB |
结论就在这张表里：**点查比的是请求次数**（行式 1 次对列式 2 次，虽然列式读的字节更少），**聚合比的是传输字节数**（列式只有行式的 1/3）。进程内的墙钟时间测不出这两件事，请求次数与字节数才测得出来。
六、查询 2：单列聚合 `MAX(price)`
```sql
SELECT MAX(price)
FROM books
```
这个查询只碰 `price` 一列，但要扫过全部 10 000 行。
• 列式布局下整列连续，一次定位之后一路顺序扫完；
• 行式布局下 `price` 每 3 行才出现一次，等于被迫把整张表读进来，其中 2/3 的字节（title、author）纯属陪读。
理论上列存更优。照旧先跑行存：`skiprows=lambda x: x % len(schema) != attr_idx` 只保留 `price` 所在位置的值（`attr_idx = 2`）。
attr_idx: int = 2
row_start: int = time_ns()
# execute query given row-major layout
data: DataFrame = read_csv(
filepath_or_buffer=path_row,
header=None,
skiprows=lambda x: x % len(schema) != attr_idx, # wrong attribute
nrows=number_of_tuples,
)
aggregate: float = data.max(0)[0] # compute aggregate
row_end: int = time_ns()
print("Aggregate:", aggregate)
print("Time row-major:", round((row_end - row_start) / 1000000, 1), "ms")Aggregate: 99.98
Time row-major: 5.9 ms
列式布局下的聚合
`skiprows=attr_idx * number_of_tuples` 直接跳过前两列共 20 000 行，从 `price` 列的起点开始读 10 000 个值：一次定位，之后全是顺序读。
对比上一格的行式写法——它要把 30 000 行全扫一遍，再从中挑出三分之一的 `price`。两种写法读到的都是同一列的同一万个值，`MAX` 必然相同（1 万行、种子 42 时是 99.98）。变的只有取数路径。
column_start: int = time_ns()
# execute query given column-major layout
data: DataFrame = read_csv(
filepath_or_buffer=path_column,
header=None,
skiprows=attr_idx * number_of_tuples, # start at attribute column
nrows=number_of_tuples,
)
aggregate: float = data.max(0)[0] # compute aggregate
column_end: int = time_ns()
print("Aggregate:", aggregate)
print("Time column-major:", round((column_end - column_start) / 1000000, 1), "ms")Aggregate: 99.98
Time column-major: 3.3 ms
观察与解释
本机实测（1 万行，同一格重跑 7 次取中位数）：
| 查询 | 行式 | 列式 | 列式 / 行式 |
| --- | --- | --- | --- |
| 单列聚合 `MAX(price)` | 19.7 ms | 14.8 ms | 0.75×（列式快约 1.33 倍） |
方向与 I/O 模型一致。作为对照，20 万行的进程内 NumPy 微基准（7 次取中位数）给出行式 0.554 ms / 列式 0.2325 ms，约 2.4 倍。这里只有 1.33 倍，是因为 1 万行太小，且 `read_csv` 的文本解析开销在两种布局上各收一份，把差距稀释了——**把 `number_of_tuples` 改大再跑一次**，比值会向 2.4 倍靠拢，这是本实验最值得动手的一步。
还有一块加速空间本笔记本没有用上：列式布局下这一列在内存里是连续的，可以走向量化与 SIMD（single instruction multiple data，单指令多数据流），一条指令处理多个值。真实列存系统（如 DuckDB、ClickHouse）的快，很大程度上来自这里，而不是来自"少读了几个字节"。
最后清理两个临时文件（用 `os.remove` 而不是 shell 的 `!rm`，因为 Windows 的 cmd 没有 `rm`）。
import os
os.remove(path_row)
os.remove(path_column)七、思考题与详解
<details>
<summary><b>第 1 题</b>：行式布局和列式布局下，同一张表占用的总字节数是否相同？为什么？</summary>
**相同。** 两种布局只是排列顺序不同，字节一个不少：都是 `n × c × w`（行数 × 列数 × 字段宽度）。布局改变的是"哪些字节相邻"，不是"有多少字节"。真正被改变的是访问这些字节时要付出的代价。
</details>
<details>
<summary><b>第 2 题</b>：`SELECT * FROM books WHERE id = 5000`（按主键取一整行）在哪种布局上更快？用 20 万行、3 列、定长 8 字节、64 KiB 块的模型估算 I/O 次数。</summary>
**行式更快。**
• 行式：目标行的 24 字节连成一片，落在 1 个块里 → **1 次 I/O**。
• 列式：3 个字段分散在 3 段，每段各占 1 个块 → **3 次 I/O**。
取一整行就是 `k = c`（投影列数 = 全部列数）。此时列式没有任何字节优势，只剩下 I/O 次数的劣势。这也解释了本笔记本为什么用 `LIMIT/OFFSET` 的窄投影来展示行存的优势——换成 `SELECT *`，优势会更明显。
</details>
<details>
<summary><b>第 3 题</b>：模型里点查在列式布局上需要的字节更少（5.0 KB 对 7.5 KB），为什么通常还是行式赢？</summary>
**因为瓶颈是 I/O 请求次数，不是字节数。**
一次 I/O 请求要先付"起步价"：SSD 4 KiB 随机读约 150 μs，机械盘寻道约 10 ms。而 2.5 KB 的字节差，按 SSD 顺序读 500 MB/s 估算只需约 5 μs。
行式 1 次请求、列式 2 次请求：省下的那一次起步价，远大于多读 2.5 KB 的传输费。**少碰几次盘，比每次少搬几个字节更值钱。**
</details>
<details>
<summary><b>第 4 题</b>：块大小从 64 KiB 改成 4 KiB，全表聚合在两种布局下的 I/O 次数各变成多少？比例关系变了吗？</summary>
行式：`ceil(4 800 000 / 4096) = 1172` 次；列式：`ceil(1 600 000 / 4096) = 391` 次。
比值 `1172 / 391 ≈ 3.0`，与 64 KiB 时的 `74 / 25 ≈ 3.0` 相同。
**比例不变。** 两种布局读取的字节量都随块变小按同一倍数放大，比值由数据本身决定（这里 `k/c = 1/3`），与块大小无关。块变小只是把绝对次数放大——这也是为什么块太小会让 I/O 次数成为更致命的瓶颈。
</details>
<details>
<summary><b>第 5 题</b>：把 3 列改成 30 列，仍然只聚合 1 列，列式相对行式的优势是变大还是变小？用 k/c 说明。</summary>
**变大，且接近线性。**
列式读取字节量 ≈ 行式读取字节量 × `k / c`。`k = 1` 时：`c = 3` 得 1/3，`c = 30` 得 1/30。I/O 次数的比值在块足够多时同样趋近 `k/c`。
**列越多、查询越窄，列式越赚**——这正是分析型宽表偏爱列存的算术原因，也是 OLAP 系统几乎一律选列存的根源。
</details>
<details>
<summary><b>第 6 题</b>：查询 1 里若 `LIMIT 314` 改成 `LIMIT 100000`，列式点查的 I/O 请求次数还是 2 吗？为什么？</summary>
**不是，会明显变多。**
`LIMIT 100000` 时每列要读的区间长 `100000 × 8 = 800000` 字节，跨 `ceil(800000 / 65536) = 13` 个块，两列合计约 26 次 I/O；行式区间长 `100000 × 24 = 2 400 000` 字节，跨约 37 次 I/O。
列式"只要 2 次"这个直觉只在**区间极短**时成立：区间短到每段各自落在 1 个块里，区域数才等于请求数。区间一长，每个块都要单独请求，比的就是块数了。**点查越短，行式越占优；区间越长，两种布局越接近比块数。**
</details>
<details>
<summary><b>第 7 题</b>：进程内微基准里，为什么"列式风格"的聚合要先做一次 `ascontiguousarray` 拷贝？拷贝有成本，这会不会让列式反而吃亏？</summary>
行式二维数组里同一列的值每隔 `R = c × w` 字节才出现一次 `w` 字节，一条 64 字节缓存行里只有 8 字节有用，带宽利用率 1/8。`ascontiguousarray` 把该列拷成连续内存，之后才能吃满带宽并启用 SIMD。
单次聚合时，拷贝成本确实会吃掉一部分收益——这就是参考实测里差距是 2.4 倍而不是 8 倍的原因之一。**是否划算取决于复用次数**：同一列只聚合一次，拷贝可能不值；若这一列要被反复聚合，拷一次、扫多次，均摊后必赚。数据库里"物化成列存"就是永久拷一次的版本。
具体阈值与列宽、行数、CPU 有关，**需自行实测确认**。
</details>
<details>
<summary><b>第 8 题</b>：一个分析型报表系统 95% 的查询只访问 5 列宽表中的 1～2 列；一个交易系统几乎每次都取整行。各应选什么布局？</summary>
**报表系统选列式，交易系统选行式。**
• 报表：`k/c` 很小（0.2～0.4），以聚合和窄投影为主，列式在字节量与 I/O 次数上双赢。
• 交易：整行读写，`k = c`，行式一次 I/O 就定位到整行；而且行存对单行插入更友好——一次追加 24 字节即可，列存要往 3 个不同区域各写一次。
补充一点：真实系统常常是混合的（HTAP），做法是同一份数据同时维护行存与列存两份，或者用 PAX 这类"块内按列分组"的折中布局。
</details>