# 实验 05：pandas 里的位序列——布尔掩码就是位图索引

> 做数据库实验不一定非要先造一个数据库。本实验用 150 行的鸢尾花数据集，说明一个天天在用、却常常被忽略的事实：**pandas 的布尔 Series 就是一条位序列**，而 `iris[mask]` 就是一次位图索引查找。理解了这一点，实验 04 里那些"位运算求值""候选集压缩"的说法就不再抽象了。

---

## 一、实验目标

做完本实验，你应当能够：

1. 说明 pandas 布尔 Series 与数据库位图索引的对应关系，指出二者在存储上的一处关键差别。
2. 用 `&`、`|`、`~` 组合多个掩码，并解释组合后的语义。
3. 用 `sum()` 读出掩码的选择性（命中比例），并据此判断"该不该为这一列建位图索引"。
4. 复现本实验给出的三个实测数字：150 行数据中，`sepal_width == 3.8` 命中 6 行，`petal_length == 1.9` 命中 2 行，两者取交集命中 1 行。
5. 说清"位图索引适合低基数列、不适合高基数列"这句话的量化依据。

---

## 二、预备知识

### 2.1 位序列与位图索引

**位序列（bit sequence）**是一串 0/1，长度等于表的行数，第 $i$ 位表示"第 $i$ 行是否满足某个条件"。

数据库里的**位图索引（bitmap index）**正是这个结构：为某个列的某个取值建一条位序列。查询 `WHERE species = 'setosa'` 就变成"取出 setosa 那一条位序列，值为 1 的行就是结果"。

本实验要说明的核心对应：

| 数据库概念 | pandas 中的写法 |
|---|---|
| 一条位序列 | 一个布尔 `Series` |
| 位与（AND） | `mask1 & mask2` |
| 位或（OR） | `mask1 \| mask2` |
| 位取反（NOT） | `~mask` |
| 用位序列取行 | `df[mask]` |
| 基数（cardinality） | `df[col].nunique()` |
| 选择性（selectivity） | `mask.sum() / len(df)` |

### 2.2 一处必须点明的差别

数据库的位图索引**只存 0/1 比特**，一行一个比特，并且通常会做游程压缩（实验 04 的 WAH）。pandas 的布尔 Series 在 **NumPy 里用一个字节（8 比特）存一个布尔值**——它是"位序列的语义 + 字节数组的实现"。

所以**不能**用 pandas 的内存占用来论证"位图索引省空间"。pandas 给你的是位序列的**语义与运算方式**，不是它的**压缩存储**。这一点很容易被讲错。

可以用一行代码验证：

```python
import numpy as np
a = np.array([True, False, True])
print(a.dtype, a.itemsize)      # 输出: bool 1   —— 每个布尔占 1 字节，不是 1 比特
```

### 2.3 为什么低基数列才适合位图索引

设列的基数为 $d$（不同取值的个数），表有 $n$ 行：

- 位图索引要存 $d$ 条位序列，共 $n \times d$ 个比特；
- 每个取值平均命中 $n / d$ 行。

$d$ 很小（如性别、洲、订单状态）时，每条位序列很短、选择性适中，位运算一次能筛掉大量行，非常划算。
$d$ 很大（如用户 ID、交易金额、经纬度）时，要维护 $d$ 条位序列，空间爆炸，且每条位序列几乎全是 0、选择性极低，反而不如直接扫描或换 B+ 树。

**经验判据**：$d \ll n$（通常 $d$ 在几十以内）才考虑位图索引。

---

## 三、实验原理

### 3.1 掩码是怎么来的

```python
bit_sequence_1 = iris["sepal_width"] == 3.8
```

这一行做了三件事：

1. 取出 `sepal_width` 这一列（150 个浮点数）；
2. 逐元素与 3.8 比较，得到 150 个布尔值；
3. 包成一个 `Series`，索引与原来那 150 行一一对应。

结果是 `pandas.Series`，`dtype` 为 `bool`，长度 150。

**注意 `==` 在这里是"逐元素比较"，不是"判断两个对象相等"。** 这是 NumPy 的广播语义，也是初学者最容易卡住的地方。

### 3.2 掩码怎么用来取行

```python
iris[bit_sequence_1]
```

pandas 保留布尔值为 `True` 的那些行，丢掉 `False` 的行。这就是一次"位图索引查找"。

### 3.3 掩码怎么组合

多个条件用位运算组合，语义完全对应 SQL 的 `AND` / `OR` / `NOT`：

```python
iris[bit_sequence_1 & bit_sequence_2]     # 两个条件都满足  → WHERE a AND b
iris[bit_sequence_1 | bit_sequence_2]     # 至少一个满足    → WHERE a OR b
iris[~bit_sequence_1]                     # 不满足          → WHERE NOT a
```

**一个高频错误：用 `and` / `or` 代替 `&` / `|`。** Python 的 `and` 会对整个 Series 做真值判断，而长度为 150 的 Series 没有唯一的真假，于是抛出 `ValueError: The truth value of a Series is ambiguous`。记住：**按位运算用 `&` `|`，逻辑连接词用 `and` `or`，在位序列上永远用前者。**

### 3.4 组合的代价

$m$ 条位序列做 AND，需要 $m-1$ 次位与，每次扫 $n$ 个比特。现代 CPU 一次能处理 256 比特（AVX2），所以 $n = 10^6$、$m = 3$ 时，理论耗时在毫秒量级——这正是实验 04 实测"位图查询 1.5184 ms、朴素查询 153.588 ms"差距的来源。

---

## 四、实验环境与准备

```bash
pip install pandas seaborn
```

验证：

```python
import pandas as pd, seaborn as sns
print(pd.__version__)
iris = sns.load_dataset("iris")
print(iris.shape)      # 期望输出 (150, 5)
```

若 `load_dataset` 因网络失败，可改用等价的本地构造（行数与列名相同即可，后面所有结论不变）：

```python
import pandas as pd
iris = pd.read_csv(
    "https://raw.githubusercontent.com/mwaskom/seaborn-data/master/iris.csv"
)
```

---

## 五、实验步骤

### 步骤 1：加载数据并看清它的形状

```python
import seaborn as sns

iris = sns.load_dataset("iris")
print(iris.shape)                  # 期望 (150, 5)
print(iris.columns.tolist())
iris.head()
```

期望输出：

```text
(150, 5)
['sepal_length', 'sepal_width', 'petal_length', 'petal_width', 'species']
```

### 步骤 2：造第一条位序列

```python
bit_sequence_1 = iris["sepal_width"] == 3.8

print(type(bit_sequence_1))        # <class 'pandas.core.series.Series'>
print(bit_sequence_1.dtype)        # bool
print(len(bit_sequence_1))         # 150
print(int(bit_sequence_1.sum()))   # 6
```

期望输出：

```text
<class 'pandas.core.series.Series'>
bool
150
6
```

**记录**：`sepal_width == 3.8` 命中 **6** 行，选择性 $6 / 150 = 4.0\%$。

### 步骤 3：造第二条位序列

```python
bit_sequence_2 = iris["petal_length"] == 1.9
print(int(bit_sequence_2.sum()))   # 2
```

期望输出：`2`。选择性 $2 / 150 = 1.3\%$。

### 步骤 4：分别用两条掩码取行

```python
print(len(iris[bit_sequence_1]))   # 6
print(len(iris[bit_sequence_2]))   # 2
```

### 步骤 5：组合掩码（本实验的关键一步）

```python
both = bit_sequence_1 & bit_sequence_2
print(int(both.sum()))             # 1
print(iris[both])
```

期望输出：

```text
1
    sepal_length  sepal_width  petal_length  petal_width species
44           5.1          3.8           1.9          0.4  setosa
```

**这就是位图索引的全部要义**：不做任何逐行比较，只把两条位序列按位与，就得到了同时满足两个条件的行。

### 步骤 6：验证位运算的语义

```python
print(int((bit_sequence_1 | bit_sequence_2).sum()))   # 6 + 2 - 1 = 7
print(int((~bit_sequence_1).sum()))                   # 150 - 6 = 144
print(int((bit_sequence_1 & ~bit_sequence_2).sum()))  # 6 - 1 = 5
```

期望输出：

```text
7
144
5
```

这三条正好验证了容斥关系：$|A \cup B| = |A| + |B| - |A \cap B| = 6 + 2 - 1 = 7$。

### 步骤 7：用基数判断"该不该建位图索引"

```python
for col in iris.columns:
    d = iris[col].nunique()
    print(f"{col:14s} 基数 = {d:4d}", end="")
    if d <= 10:
        print("   → 低基数，适合位图索引")
    else:
        print("   → 高基数，不适合位图索引")
```

期望输出（基数会因数据源版本略有出入，`species` 一定是 3）：

```text
sepal_length  基数 =   35   → 高基数，不适合位图索引
sepal_width   基数 =   23   → 高基数，不适合位图索引
petal_length  基数 =   43   → 高基数，不适合位图索引
petal_width   基数 =   22   → 高基数，不适合位图索引
species       基数 =    3   → 低基数，适合位图索引
```

**结论**：这份数据里只有 `species` 适合位图索引。这解释了为什么本实验前面用的是 `== 3.8`、`== 1.9` 这种"等值但基数不低"的条件——它们只是用来演示位序列的**运算**，并不代表工程上应该在 `sepal_width` 上建位图索引。

### 步骤 8：看清 pandas 存布尔用的是字节而不是比特

```python
import numpy as np
a = bit_sequence_1.to_numpy()
print(a.dtype, a.itemsize)          # bool 1
print("150 个布尔占:", a.nbytes, "字节")
print("若按 1 比特/行存，只需:", -(-150 // 8), "字节")
print("相差倍数:", a.nbytes / (-(-150 // 8)))
```

期望输出：

```text
bool 1
150 个布尔占: 150 字节
若按 1 比特/行存，只需: 19 字节
相差倍数: 7.894736842105263
```

**这一步是本实验最重要的一课**：pandas 给你的是位序列的**语义**，不是它的**压缩实现**。真正的位图索引会把这 150 个比特压进 19 字节，还能再做游程压缩。

### 步骤 9：画掩码示意图

```python
import matplotlib.pyplot as plt

fig, ax = plt.subplots(figsize=(11, 2.4))
for i, (name, m) in enumerate([("sepal_width == 3.8", bit_sequence_1),
                               ("petal_length == 1.9", bit_sequence_2),
                               ("两者 AND", bit_sequence_1 & bit_sequence_2)]):
    bits = m.to_numpy().astype(int)
    ax.scatter(range(len(bits)), [i] * len(bits),
               c=np.where(bits == 1, "#1F4E79", "#E8E8E8"), s=14, marker="s")
    ax.text(len(bits) + 2, i, f"命中 {int(bits.sum())}", va="center", fontsize=10)
ax.set_yticks(range(3))
ax.set_yticklabels(["sepal_width == 3.8", "petal_length == 1.9", "两者 AND"])
ax.set_xlabel("行号")
ax.set_title("三条位序列：1 的位置就是满足条件的行")
ax.set_xlim(-3, 175)
plt.tight_layout()
plt.show()
```

![pandas 掩码与位序列](../figures/fig_pandas_mask.png)

---

## 六、观测记录表

| 条件 | 命中行数 | 选择性 | 你的实测 |
|---|---|---|---|
| `sepal_width == 3.8` | 6 | 4.0% | |
| `petal_length == 1.9` | 2 | 1.3% | |
| 两者 AND | 1 | 0.67% | |
| 两者 OR | 7 | 4.7% | |
| `NOT (sepal_width == 3.8)` | 144 | 96.0% | |
| `(sepal_width==3.8) AND NOT (petal_length==1.9)` | 5 | 3.3% | |

| 列 | 基数 | 是否适合位图索引 | 你的实测 |
|---|---|---|---|
| `sepal_length` | 35 | 否 | |
| `sepal_width` | 23 | 否 | |
| `petal_length` | 43 | 否 | |
| `petal_width` | 22 | 否 | |
| `species` | 3 | **是** | |

| 存储对比 | 数值 |
|---|---|
| pandas 布尔 Series（150 行） | 150 字节 |
| 按 1 比特/行的位图 | 19 字节 |
| 倍数 | 约 7.9× |

---

## 七、思考题

1. 为什么 `iris[bit_sequence_1 and bit_sequence_2]` 会报错，而 `iris[bit_sequence_1 & bit_sequence_2]` 不会？报错信息里 "ambiguous" 指的是什么？
2. 位图索引常被说成"适合低基数列"。请用本实验的数字说明：**如果给 `sepal_length`（基数 35）建位图索引，会付出什么代价、换到什么收益？**
3. `~bit_sequence_1` 的选择性是 96%。这么高的选择性对查询有什么意义？（提示：想想什么时候索引还不如全表扫描。）
4. 本实验说"pandas 的布尔 Series 是位序列的语义、字节数组的实现"。请设计一个小实验，验证 pandas 在做 `&` 时是否真的用到了 CPU 的位运算并行能力（提示：比较 `numpy.packbits` 后的位与与直接 `&` 的耗时）。
5. 数据库里"位图索引 + B+ 树"经常被组合使用（例如先按日期范围用 B+ 树定位，再在位图上做 AND）。请结合实验 03 与实验 04，说明这种组合各自解决什么问题。
6. 如果一张表有 10 亿行、某列基数只有 2（比如"是否已删除"），位图索引需要多少个比特？做完游程压缩后大概能压到多少？说出你的估算思路。

---

## 八、思考题答案与解析

**第 1 题**

`and` 是 Python 的**逻辑连接词**，它要求左右两边都能被解释成一个布尔真值。长度为 150 的 Series 有 150 个布尔值，Python 不知道该按"全部为真"还是"任一为真"来解释，因此拒绝猜测并抛出 `ValueError: The truth value of a Series is ambiguous. Use a.empty, a.bool(), a.item(), a.any() or a.all().`

`&` 是**按位与运算符**，pandas 为 Series 重载了它，语义是"逐元素做与"，返回一条同样长度的新 Series，正是我们想要的操作。

顺带一句：报错信息里列出的 `a.any()` / `a.all()` 是"把整条 Series 归约成一个布尔值"的正确写法，适用于"是否存在满足条件的行"这类提问。

**第 2 题**

代价：要为 35 个不同取值各建一条长度 150 的位序列，共 $150 \times 35 = 5250$ 个比特（不做压缩约 656 字节）。相比只存原始列，索引比数据本身还大——这就是"空间爆炸"。

收益：查询 `sepal_length == 5.1` 时，能一次位运算取出命中的行。但这类等值查询在高基数列上命中极少（本实验中 `== 3.8` 只命中 6 行，选择性 4%），用 B+ 树只需 $O(\log n)$ 次比较就能定位到这 6 行，代价更小。

结论：**高基数列上，位图索引的维护成本远超收益，应选 B+ 树。** 位图索引的优势区间是低基数 + 多条件组合，因为多条件 AND/OR 在位图上只是一次位运算，而在 B+ 树上要做多次查找与结果归并。

**第 3 题**

选择性 96% 意味着"几乎每一行都满足"。此时无论用什么索引，都要返回 144/150 行——索引带来的收益趋近于 0，却仍要付出读取索引结构、做位运算、回表取行的代价。**优化器在选择性很高时应当放弃索引、直接全表扫描**（顺序 I/O 反而更快）。

业界常见的经验阈值在 5%~30% 之间（随系统而异）：选择性低于阈值走索引，高于阈值走扫描。PostgreSQL 用代价模型而非硬编码阈值来判断，参数 `random_page_cost` / `seq_page_cost` 直接影响这个判断。

**第 4 题**

思路：把布尔数组用 `numpy.packbits` 压成真正的位（uint8 数组），再对压缩后的数组做 `&`，与直接对原布尔数组做 `&` 比较耗时。若后者没有明显慢于前者，说明 NumPy 内部已经做了批量处理，两者的瓶颈都在内存带宽而非位运算本身。

注意一个容易搞错的点：`packbits` 本身要花时间。如果只做**一次** AND，压缩再运算通常更慢；只有位序列要被**反复使用**（数据库里的典型情况，索引建一次、查很多次），压缩才划算。这正好解释了为什么数据库愿意在索引上花压缩的代价。

**第 5 题**

- **B+ 树**擅长**范围查询**与**有序遍历**：`WHERE date BETWEEN '2026-01-01' AND '2026-03-31'` 可以沿叶链顺序扫出一段区间，代价与结果集大小成正比，而不是与全表大小成正比。它不擅长多条件组合——每个条件各查一次再归并，代价随条件数线性增长。
- **位图索引**擅长**多条件组合**：`WHERE 条件1 AND 条件2 AND 条件3` 只做两次位与，代价与条件数无关、只与行数有关。它不擅长范围查询——要把范围内每个取值对应的位序列都取出来做 OR，取值多时很快退化。

所以组合方式是：**用 B+ 树处理范围，用位图处理等值组合**；或者先用 B+ 树把候选行圈定到一个较小的集合，再在这个集合上做位运算。这正是很多分析型数据库（以及 PostgreSQL 的 Bitmap Scan 算子）的做法。

**第 6 题**

不压缩：$10^9$ 个比特 = $10^9 / 8$ 字节 ≈ **119 MB**（更精确地说是 125,000,000 字节 ≈ 119.2 MiB）。

压缩后：游程编码（RLE）的压缩率完全取决于"已删除"标记在物理存储顺序上的**聚集程度**。

- 最理想情况（按删除标记有序存放，只有 2 个游程）：几乎可以压到几十字节。
- 最坏情况（删除标记随机分布，平均每 2 行切换一次）：游程数约 $5 \times 10^8$，每个游程按 WAH 的 32 比特字算，反而可能膨胀到 2 GB 以上——**比不压缩还大**。

现实通常介于两者之间：如果"已删除"的比例很低（比如 1%），且删除行在存储上比较聚集，游程数约等于删除行的"连续段数"，压缩率可达数十倍。

**这个估算要传达的核心结论**：位图索引的压缩率不是算法的性质，而是**数据分布的性質**。建索引前应该先测，而不是假设。这也正是实验 04 里 WAH 压缩那张图要展示的内容（密度 0.1% 时能压到 5 个字，密度 ≥10% 时压缩失效）。

---

## 九、扩展任务（选做）

1. **用 `species` 列建真正的位图索引。** 为 3 个物种各建一条位序列，验证三条位序列按位或之后正好覆盖全部 150 行（即 `setosa | versicolor | virginica` 全为 True）。

2. **测量多条件 AND 的耗时。** 造一张 100 万行的 DataFrame，构造 5 个掩码，测 `m1 & m2 & m3 & m4 & m5` 的耗时，与"逐行 if 判断"的写法对比。观察加速比，并与实验 04 的 101× 对照，说明为什么这里的加速比通常更小。

3. **验证选择性对结果的影响。** 把 `== 3.8` 改成 `> 3.0`（选择性大幅提高），重复步骤 2–5，观察命中行数与组合结果的变化。

4. **自己实现一次 WAH 压缩。** 把一条 150 位的位序列按 32 位一组做游程压缩（WAH 字面字的有效载荷是低 31 位，最高位是标志位，与实验 04 实现的 `WORD = 32` 一致），统计压缩后的字数，与实验 04 的 WAH 实测结果对照。

---

## 十、常见错误与排查

| 现象 | 原因 | 解决办法 |
|---|---|---|
| `ValueError: The truth value of a Series is ambiguous` | 用了 `and` / `or` 组合掩码 | 改成 `&` / `|`，并给每个条件加括号 |
| 掩码长度与 DataFrame 行数不一致 | 掩码来自另一个 DataFrame，或做了 `dropna` / 切片 | 确认 `len(mask) == len(df)`；用 `mask = mask.reindex(df.index, fill_value=False)` 对齐 |
| `iris[mask]` 报 `IndexingError` | 传了二维布尔 DataFrame 而不是一维 Series | 检查 `mask.ndim`，需要时取一列或做 `.all(axis=1)` |
| `sns.load_dataset("iris")` 报网络错误 | 需要联网下载内置数据集 | 改用第"四"节给出的等价 `read_csv` 方式，或用 `sklearn.datasets.load_iris()` 构造 |
| 比较结果全为 False | 浮点数列用 `==` 比较（如 `petal_width == 0.4`） | 浮点等值比较本身不可靠，改用 `np.isclose()` 或先做分箱 |
| `mask.sum()` 返回的是 `numpy.int64` 而非 Python int | NumPy 的返回类型 | 用 `int(mask.sum())` 转换后再参与字符串格式化 |
| 掩码里有 `NaN` | 原始列有缺失值，比较结果为 False 但 dtype 变成 object | 先 `df[col].fillna(...)`，或显式检查 `mask.dtype == bool` |