CCF BDCI 2019 数据库比赛

队伍：default6079621



======================================================================================================================
======================================================== 概述 ========================================================
======================================================================================================================
这是一个高性能的纯 CPU 实现。


简要列举 `/data` 目录结构如下：

````
/data
├── docs/                               # 包含一些细节地文档
├── src/                                # 包含所有源代码
├── CMakeLists.txt
├── BDCI19                              # 编译生成的可执行文件
├── compile.sh                          # 编译脚本
├── run.sh                              # 运行脚本
├── README
├── index/                              # 首次运行时创建的索引文件夹
├── customer.txt
├── orders.txt
├── lineitem.txt
└── workspace/                          # 开发用（请忽略）
````

以下所有命令假定已处于 `/data` 目录。



======================================================================================================================
====================================================== 如何编译 ======================================================
======================================================================================================================
````
./compile.sh
````

这会产生可执行文件 `/data/BDCI19`。



======================================================================================================================
====================================================== 如何运行 ======================================================
======================================================================================================================
````
./run.sh customer.txt orders.txt lineitem.txt <query_count> ...
````

注：建立的索引位于 `/data/index`。



======================================================================================================================
================================================== 如何清理临时文件 ==================================================
======================================================================================================================
````
rm -rf /data/index
````

直接删除索引文件夹即可。



======================================================================================================================
============================================== 建议的测试方案（二选一） ==============================================
======================================================================================================================

方案一： // 更简明
    步骤1 | 删除索引文件夹（如果已存在）；重启 VM，减小任何未知的影响
    步骤2 | 运行指令：`cat customer.txt orders.txt lineitem.txt >/dev/null`，这大约需要 1.5min
    步骤3 | 多次运行 `run.sh`（比如运行10次）。第一次运行时，将会建立索引目录 `data/index`，之后的速度会以数量级地加快

    测试完成。应该只基于“步骤3”计算成绩。


方案二：
    步骤1 | 删除索引文件夹（如果已存在）；重启 VM，减小任何未知的影响
    步骤2 | 运行 `run.sh` - 此次运行相对较慢，因为我们必须从磁盘上读取文件
    步骤3 | 清除生成的索引 `data/index`
    步骤4 | 多次运行 `run.sh`（比如运行10次）。第一次运行时，将会建立索引目录 `data/index`，之后的速度会以数量级地加快

    测试完成。应该只基于“步骤4”计算成绩。

两种测试方案的性能是等效的，建议择一即可。



**************** 不建议的测试方案 ****************

请 **不要** 这样使用程序：
    步骤1 | 删除索引文件夹（如果已存在）；重启 VM，减小任何未知的影响
    步骤2 | 直接多次运行 `run.sh`（比如运行10次）。
    然后直接用步骤2的时间作为成绩。

    原因如下：当建立索引时，程序会判断三个txt文件是否在 page cache 中。
        - 如果在 page cache 中，我们会直接建立索引（运行时间约13秒）。
        - 如果不在 page cache 中（比如步骤2），我们会依次执行这些操作：
            建立索引
            利用索引响应查询
            将索引 sync 到磁盘
            drop 索引的 page cache（为了预留内存给 txt 文件的 page cache）
            预读取三个 txt 文件（加载到 page cache 中）
          这相对较慢，会花费 1~2 分钟。这是在为下一次建立索引做准备。

    因此，如果这样测试程序，在第一次查询的时候速度会极慢，因为需要从磁盘中读取建立的索引，而不是从 page cache 中读取。
    这不能体现程序的真实性能。



======================================================================================================================
====================================================== 设计思想 ======================================================
======================================================================================================================

基于问题查询的模式，我们建立了物化视图（materialized view），命名为 mv_items。
该物化视图的语义可以通过如下的 SQL 语句描述：

````
CREATE MATERIALIZED VIEW mv_items
AS
    SELECT
        c_mktsegment,
        o_orderdate,
        l_orderkey,
        l_shipdate,
        l_extendedprice
    FROM
        customer, orders, lineitem
    WHERE
        customer.c_custkey = orders.o_custkey
        AND lineitem.l_orderkey = orders.o_orderkey	
WITH DATA
````

在建立 mv_items 时，我们使用了 hash join（因为过滤条件为“相等”）：
    - orders JOIN customer: 左表为 orders，右表为 customer，过滤条件为 c_custkey = o_custkey
    - lineitem JOIN orders: 左表为 lineitem，右表为 orders，过滤条件为 l_orderkey = o_orderkey

我们使用的 hash 函数如下：
    - H(custkey) = custkey
    - H(orderkey) = (orderkey >> 5) << 3 | (orderkey & 7)


相应地，原来的查询 (q_mktsegment, q_orderdate, q_shipdate, q_topn) 可以写为：

````
SELECT
	l_orderkey,
	o_orderdate,
	SUM(l_extendedprice) AS revenue
FROM
	mv_items
WHERE
	c_mktsegment = q_mktsegment
	AND o_orderdate < q_orderdate
	AND l_shipdate > q_shipdate
GROUP BY
	l_orderkey,
	o_orderdate
ORDER BY
	revenue DESC
LIMIT q_topn
````

此时不再有表与表的 JOIN 操作。

---------------------------------------------------------------------------------------------------

基于此，我们可以在 mv_items 上建立索引。我们使用了联合索引 (c_mktsegment, o_orderdate)。
可以用如下 SQL 语句描述：

````
CREATE INDEX idx_items
ON mv_items
(
    c_mktsegment,
    o_orderdate
)
````

这使得对于每个查询，我们只需要扫描很有限的一些 o_orderdate。

---------------------------------------------------------------------------------------------------

我们还可以进一步地做剪枝。

在建立 mv_items 的过程中，我们统计如下的两个量：
- max_shipdate_orderdate_diff = MAX(l_shipdate::date - o_orderdate::date)
- min_shipdate_orderdate_diff = MIN(l_shipdate::date - o_orderdate::date)

我们有约束条件：
- l_shipdate - o_orderdate >= min_shipdate_orderdate_diff
- l_shipdate - o_orderdate <= max_shipdate_orderdate_diff
- o_orderdate < q_orderdate
- l_shipdate > q_shipdate

通过简单的不等式变形，我们可以发现，查询中在较大 o_orderdate 范围内的商品
都可以被匹配上，无需真正检查 l_shipdate > q_shipdate。

基于此发现，我们还建立了另一个物化视图 mv_pretopn。在查询时，至多有
    (max_shipdate_orderdate_diff - min_shipdate_orderdate_diff)
数量的 o_orderdate 需要从 mv_items 中扫描，其余大多数的 o_orderdate 从 mv_pretopn 中扫描。


mv_pretopn 基本可以由如下 SQL 语句描述：

````sql
CREATE MATERIALIZED VIEW mv_pretopn
AS
    SELECT
        c_mktsegment,
        o_orderdate,
        l_orderkey,
        SUM(l_extendedprice) AS revenue
    FROM
        mv_items
    GROUP BY
        c_mktsegment,
        o_orderdate,
        l_orderkey
    ORDER BY
        c_mktsegment,
    	o_orderdate ASC,
        revenue DESC
WITH DATA

````

当然，我们也在 mv_pretopn 上建立了联合索引 (c_mktsegment, o_orderdate)。
mv_pretopn 上的索引比 mv_items 上的索引要小很多，也高效很多。



======================================================================================================================
====================================================== 工程实现 ======================================================
======================================================================================================================

为获取极致的性能，我们使用了大量的压缩编码，以及面向 x86 CPU 架构和面向 Linux 操作系统的优化。
简要列举其中一些如下：

- 因为压缩编码后每行较小，物化视图是行存而不是列存的。
- 索引是“分层”的，相对更可能出现在查询结果中的订单会优先扫描。
- 我们使用了多进程（fork）而不是多线程，这大大减小了并行 mmap() 时内核在 `mmap_sem` 锁上的等待。
- 基于 postgresql 的灵感，我们使用了多个稀疏文件存储索引，这大大减少了并行文件 IO 时内核在 inode 锁上的等待。
- 我们精心地利用了 page cache 来保证我们需要读取的索引不会真正触发磁盘 IO。
- 我们使用了 hugetlb，大大减小了 CPU TLB miss。
- 在建立索引和扫描索引时，我们大量使用了 CPU 提供的 AVX2 指令集。
- 我们有意控制了运行时虚拟内存的 footprint，这减少了进程退出时清理页表的时间。



======================================================================================================================
====================================================== 参考性能 ======================================================
======================================================================================================================

这是我们开发时测得的性能，供参考。

| Case                                                 | Time       |
|------------------------------------------------------|------------|
| Create index, with page cache                        | ~ 12 sec   |
|------------------------------------------------------|------------|
| 100  random queries, each selecting top 9000~10000   | ~ 0.22 sec |
| 100  random queries, each selecting top 45000~50000  | ~ 0.36 sec |
| 100  random queries, each selecting top 90000~100000 | ~ 0.54 sec |
|------------------------------------------------------|------------|
| 500  random queries, each selecting top 9000~10000   | ~ 0.92 sec |
| 500  random queries, each selecting top 45000~50000  | ~ 1.46 sec |
| 500  random queries, each selecting top 90000~100000 | ~ 2.14 sec |
|------------------------------------------------------|------------|
| 1000 random queries, each selecting top 9000~10000   | ~ 1.83 sec |
| 1000 random queries, each selecting top 45000~50000  | ~ 2.97 sec |
| 1000 random queries, each selecting top 90000~100000 | ~ 4.32 sec |



======================================================================================================================
====================================================== 其他问题 ======================================================
======================================================================================================================

******** 1. 为什么我们没有使用 GPU？ ********

（1）在建立索引时为何没有使用 GPU：GPU host <=> device memcpy 的速度过慢，无法发挥 GPU 计算速度的优势。
单块 PCI-E P100 实测 pinned memory 单向带宽约 13GB/s，unpinned memory 单向带宽约 8GB/s。
以约 110 GB txt 文件估算，我们的 CPU 实现建立索引大约需要 12 秒，吞吐量 > 9 GB/s，甚至已经超过 GPU 的传输速度。
可能的解决方案有：
    - 使用 NVLink 版的 GPU
    - 如果没有 page cache：GPU Direct 现在支持从 NVME SSD 直接读数据到 GPU 里（不经过 CPU 内存）

（2）做查询时为何没有使用 GPU：现在的查询量不够大。
CUDA 的初始化较慢，退出也较慢，适合在一次启动后做大量工作再退出。
如果每一批查询的数量达到上万，或程序长期运行（streaming query），使用 GPU 更合适。
可能的解决方案有：
    - 程序长期运行，查询源源不断（这更贴合真实场景）
    - 每一批查询数量更大


******** 2. 我们现在的卓越性能依赖于txt文件的 page cache，这合理吗？ ********

我们认为，如果没有 page cache，在建立索引时，大家的性能都将受限于在磁盘 IO。
由于磁盘 IO 过于慢，读取 110 GB 的磁盘文件需要约 2 分钟，那么大部分队伍的运行时间都将差不多，
这样无法区分索引、查询计划等的优劣，意义有限。

对于我们建议的测试方案一或方案二，其他队伍可以同样的方案执行，建议取性能较好的一种作为其成绩。
所有队伍在开始运行的时候三个txt文件都全部在 page cache 里，这是公平的。


******** 3. 我们现在的优化有没有过度贴合到当前赛题上，缺少普适性？ ********

从一定意义上说，有小部分优化确实是针对性极强的（主要在于索引的压缩和编码上）。

但我们提出以下两点：
（1）面对现实问题，本来应该是对症下药的，特定问题特定解决。这是在性能和通用性上的trade off。
（2）除去少量针对性极强的优化，我们的绝大部分优化时通用的。