Skip to content

毕设进展

时间规划

时间 安排 完成情况
第二周 03-01 完成开题报告 完成
第三周 03-08 进一步论文调研 完成
第四周 03-15 学习 TiDB SQL Engine 优化器，调研复杂分析型数据库工作负载（Complex Analytical Database Workload） Miss
第五周 03-22 着手实现 Multiway Join 算子
第六周 03-29 继续实现算子，并作正确性验证

具体情况记录

第五周 03-22

  • 确定一下算子的实现方式

有两个思路，第一个是用 Looking Ahead 那篇 paper 的方法，小表建 bloom filter 然后拿大表来 probe；另外一个是用大表建 hash table 然后拿小表来 probe。

第四周 03-16

JOB 可以在这个 github repo 下载。我 fork 之后做了一些小修改，已经可以在 tidb 集群上跑起来了，因为暂时没有比对的对象，准备下周在 tiflash 上也跑一次（tiflash 是一个按列存的 tidb 存储后端，对 AP 型的 workload 有更好的效果）。

关于 Star Schema Benchmark，除了提出它的论文之外，ClickHouse 给了一个教程1

另外看到了一篇 paper，关于如何在执行层面提升执行计划的鲁棒性，使用的也是 star schema benchmark 作为评测指标。不过这篇文章比较艰深，我还在读，下周会写一个简单的报告。

  • Looking Ahead Makes Query Plans Robust, VLDB 2017

本周没来得及看 tidb 优化器部分的代码。下周继续看，并希望能出一个如何实现 multiway join 的 proposal。

第三周 03-08

进一步的论文调研，以及研究了一下 fduthesis 这个 latex 论文模板。

调研的论文分为以下几个方向

  • join 算子的具体实现
  • join order 的选择与对效率的影响
  • multiway join 相关

Join order 的相关文章

  • Cardinality estimation done right: index-based join sampling, Leis et al., CIDR 2017

    • join 的顺序对于优化器来说是最 tricky 的部分，自从 Selinger’s 1979 介绍 System R 优化器的论文以来，有非常多关于 join order 的论文。n 张表的 join 顺序的选择是 $O(n!)$ 增长的（实际上是卡特兰数，如果只考虑两路的 join 的话）。
    • 衡量 join order 的优劣靠的是知道每个关系中连接出来的 tuple 的数量的估计，即 cardinality estimation，这个估计是很难的，只能通过数据的分布的统计信息和 heuristics 去估计，效果极差；还有一种估计方式是对数据进行采样（sampling），但通常来说，sampling 的 IO 代价较大，而且采样量随着 join 的关系的数量的增长也是指数级的
    • 另外这篇文章提到了一个 Join Order Benchmark, 可以后续进一步调研这个 benchmark

  • How good are query optimizers, really? Leis et al., VLBD 2015

    • 这篇文章就介绍了 join order benchmark，以及主流的优化器在这个 benchmark 上的表现
    • 一个比较震撼的发现是，cardinality estimation 竟然比 cost model 本身对于好的执行计划来说更加重要
    • （一个有趣的问题是，分布式数据库上的 cardinality estimation 和单机数据库的区别，有没有更多的发挥空间？）
    • good illustration of the core problems in query optimization
    • cost model 的参数设计简直是玄学（dark art，黑魔法）
    • 文章指出了现有的 benchmark （如 TPC-H, TPC-DS, Star Schema Benchmark）的不足之处——即无法反映 cardinality estimation 的好坏，因为这些 benchmark 大多采用自动生成的数据，因此数据分布特征十分明显，现有优化器很容易获得较好的估计
    • JOB 基于 IMDB (internet movie data base)，是真实的数据构成的数据集，113 个 query，每个 query 最少 3 个 join 最多 16 个，平均有 8 个（天哪……）

调研工作还需要继续。另外可以把 JOB 下载下来跑起来看一看，以及 SSB 的 star schema 是 multway join 最适合的场景，也可以调研一番。

第二周 03-01

完成了选题和开题报告的撰写。

  1. 选题的目的和意义;

数据表的连接(join)是关系型数据库系统中最为重要的操作之一,而面对日益复杂的业务需求, 复杂查询中的连接处理往往成为了性能的关键。特别是对于分析型的查询而言,一个查询语句往往 会关系到多个表的连接,不仅对连接顺序的选择提出了更高的要求,在一些十分复杂的查询中出现 星型连接的场景也对传统的逐步连接的方法提出了挑战。TiDB 作为一个开源的分布式关系型 HTAP 数据库系统,除了需要快速响应事务型查询(transactional query)也需要高效地处理分析 型查询(analytical query),因此如何有效地解决复杂多表连接的问题就成为了摆在相关的开发人 员和研究者面前的重要任务。

  1. 国内外相关研究状况综述(列出相应的参考文献);

复杂连接查询的处理是数据库系统研究的重要问题之一2。这方面的研究主要分为查询优化和执行 优化两部分。查询优化指的是通过选择特定的连接顺序降低计算量3 4,而执行优化则包括选择更 加合适的算子,如通过多路连接(multi-way join)的方式同时对多张表进行连接。这两方面的研 究在单机的关系型数据库系统或者分布式的分析型数据库上教为丰富,但在近年来兴起的分布式混 合型数据库系统中的研究仍较为缺乏。特别的,多路连接的方法作为处理复杂多表连接的优化算法, 吸引了较多的研究热情,以下参考文献中关于多路连接的研究包含了多路连接在传统的单机数据库 5 6 7 8和分布式的 Map Reduce 上的实现的研究9,但关于在分布式的 HTAP 数据库上的实现 与优化目前鲜见相关工作。

  1. 主要研究内容与基本思路,详细技术路线,并分析可行性、难点和创新点;

主要研究内容:探究复杂多表连接的查询的处理方式 详细技术路线:首先对具有复杂多表连接的查询做收集和整理,研究查询的模式,同时调研相关的 论文,学习研究 TiDB 的 SQL 引擎的实现,并着手实现多路连接。多路连接是处理一类复杂连接 的算子,可以同时对多张表进行连接,避免了多次连接的重复性计算,因此可以提高连接的效率。 具体实现时需要根据 SQL 优化器选取主要表,然后同时和多张副表进行连接。完成实现后,在 TPC-H (一个标准化的数据库性能测试数据集,具有较多复杂查询) 的 benchmark 上验证相关 实现的优化效果。可行性较高,但难点在于对整个已有系统的理解和对多种复杂的多表连接场景做 适配。创新点在于在一个分布式的 HTAP 系统上优化了复杂多表连接查询。

  1. 预期成果及形式。

预期成果为 TiDB 应对复杂多表连接查询的能力提示,在 TPC-H 的 benchmark 上获得性能提 示,并将修改的代码提交到 TiDB 在 GitHub 上的代码仓库。

  1. https://clickhouse.tech/docs/en/getting_started/example_datasets/star_schema/ ↩

  2. How Good Are Query Optimizers, Really? PVLDB 2015 ↩

  3. Deep Reinforcement Learning for Join Order Enumeration ↩

  4. A polynomial time algorithm for optimizing join queries, ICDE 1993 ↩

  5. Tradeoffs in Processing Multi-Way Join Queries via Hashing in Multiprocessor Database Machines, VLDB90 ↩

  6. Faster joins, self-joins and multi-way joins using join indices, Date & Knowledge Engineering 1999 ↩

  7. Are Multi-way Joins Actually Useful? ICEIS 2013 ↩

  8. Efficient Multiway Hash Join on Reconfigurable Hardware, Arxiv 1905.13376 ↩

  9. Optimizing Joins in a Map-Reduce Environment, EDBT 2010 ↩