遥凌_社区达人页

2022年02月

• 02.17 18:28:38
  发表了文章 2022-02-17 18:28:38

  PolarDB 并行查询的前世今生

  本文会深入介绍PolarDB MySQL在并行查询这一企业级查询加速特性上做的技术探索、形态演进和相关组件的实现原理，所涉及功能随PolarDB MySQL 8.0.2版本上线。

  

2021年09月

• 09.07 23:31:40
  发表了文章 2021-09-07 23:31:40

  CockroachDB: The Resilient Geo-Distributed SQL Database

  一直以来对CockroachDB(CRDB for short)的设计和实现很感兴趣，最近抽时间研究了下，发现其在技术上还是领先了同类NewSQL产品不少的，个人感觉应该是目前最为先进的类Spanner分布式数据库系统，因此这篇文章会尽可能详细的讨论下其系统的多个方面，重点是事务和一致性相关。 paper中针对的是v.19.2.2版本，不过官方文档中是基于最新的v.21.1.7，两者在描述上有一些冲突的地方，而官方文档中会更为详尽些，因此本文的很多介绍将尽量将paper与官方reference结合，并以reference为准。

  
• 09.07 23:27:10
  发表了文章 2021-09-07 23:27:10

  从CockroachDB看分布式数据库系统的一致性

  最近仔细研究了下CockroachDB的相关文档和paper，感觉在市场上众多的NewSQL分布式数据库系统中，它对于数据的一致性追求应该是最为极致的，由此也回顾了下分布式系统下，所谓的一致性相关概念，由于每次思考起这个东西总感觉有些烧脑，经常会反复走入同一个思维误区，这里感觉记录下自己当前的理解，个人感觉应该是准确的，如果大家看到不对的地方欢迎指正。

  
• 09.07 23:24:52
  发表了文章 2021-09-07 23:24:52

  Adaptive Execution of Compiled Queries 论文解读

  本篇是TUM的内存数据库HyPer针对compile-based执行框架的改进。其中涉及到HyPer的动态编译和并行执行框架 动态编译文章的结尾提到了编译执行系统存在的2个问题，其中之一就是：不可控的编译时间。

  
• 09.07 23:22:27
  发表了文章 2021-09-07 23:22:27

  Morsel-Driven Parallelism: A NUMA-Aware Query Evaluation Framework for the Many-Core Age 论文解读

  这篇paper介绍了TUM的内存数据库系统HyPer中使用的，基于小块数据(morsel)来驱动的并行查询执行框架。用来解决many-cores（NUMA)环境下，分析型查询的scalability问题。

  
• 09.07 23:19:01
  发表了文章 2021-09-07 23:19:01

  Efficiently Compiling Efficient Query Plans for Modern Hardware 论文解读

  这应该是SQL查询编译的一篇经典文章了，作者是著名的Thomas Neumann，主要讲解了TUM的HyPer数据库中对于CodeGen的应用。 在morsel-driven那篇paper 中，介绍了HyPer的整个执行框架，会以task为单位处理一个morsel的数据，而执行的处理逻辑（一个pipeline job）就被编译为一个函数。这篇paper则具体讲如何实现动态编译。

  
• 09.07 23:15:24
  发表了文章 2021-09-07 23:15:24

  Volcano - An Extensible and Parallel Query Evaluation System 论文解读

  前面写了一些关于优化器的文章，现在开个小差，写一些执行器的paper介绍，从这篇开始。 这篇是Graefe的Volcano Project的执行器框架，其概念已被广泛接受和使用，也就是我们最为熟悉的Volcano iterator的执行框架，关于volcano/cascades的优化器介绍
• 09.07 23:14:07
  发表了文章 2021-09-07 23:14:07

  MonetDB/X100: Hyper-Pipelining Query Execution 论文解读

  这是关于MonetDB执行引擎的一篇paper，总体分为了2个部分，第一部分主要讲了下modern cpu的工作原理并给出了一个TPC-H Q1的例子，从这部分中我们便可以清晰的看到为什么向量化的执行方式如此有意义。第二部分则主要介绍了MonetDB X/100这个新的向量化执行引擎。这篇paper被引用的极为广泛，启发了后续很多列存数据库在执行引擎上的设计思路。个人感觉第一部分尤其有意义，如果想入门下列存/向量化执行，看看第一部分应该就有些概念了。

  
• 09.07 23:10:13
  发表了文章 2021-09-07 23:10:13

  Parallel SQL Execution in Oracle 10g 论文解读

  这篇简短的paper从非常high level的角度描述了下Oracle 10g对于parallel query所做的重新设计和其中的一些优化，由于Oracle RAC特殊的share-disk架构，使其在并行计算上与普通的MPP数据库有一些不同，例如对于worker的调度和分配方式以及对于资源/数据的动态调整。

  
• 09.07 23:06:26
  发表了文章 2021-09-07 23:06:26

  The Snowflake Elastic Data WareHouse 论文解读

  Snowflake是目前话题度超高的云原生数仓产品，从20年下半年上市到现在已经市值千亿了。它的流行进一步印证了云的重要性。纵观现在大大小小的数据库厂商，上云是必然要走的战略步骤，而snowflake则更加直接，类似于AWS Aurora或我们的PolarDB，它就是围绕着云基础设施构建的OLAP数据库产品。

  
• 09.07 22:19:13
  发表了文章 2021-09-07 22:19:13

  FoundationDB论文解读 A Distributed Unbundled Transactional Key Value Store

  FoundationDB一个具有事务语义的分布式KV存储，是最早的一批把NoSQL和分布式事务结合起来的数据库系统，它提供了NoSQL的高扩展，高可用和灵活性，同时保证了serializable的强ACID语义。

  
• 09.07 22:15:11
  发表了文章 2021-09-07 22:15:11

  Enhanced Subquery Optimizations in Oracle

  在前面的文章中，介绍了Oracle是如何做cost-based query transformation的，其中也包含Oracle基于rules/cost所做的若干种常见的query rewrite。对于CBQT的极简描述是对一个query做deep copy后，尝试一系列transform并利用physical optimizer计算cost，如果cost更低则保留该变换，否则抛弃。详细介绍可以参考之前的文章。 这篇paper算是之前那篇的后续，把重点放在了对subquery的处理上。subquery是一种在分析型query中非常常见的SQL construct，非常便于表达一些语义因此被

  
• 09.07 22:10:46
  发表了文章 2021-09-07 22:10:46

  WinMagic : Subquery Elimination Using Window Aggregation

  这篇精干的paper介绍了IBM DB2基于window function对相关子查询进行解相关的等价变换。

  
• 09.07 22:07:40
  发表了文章 2021-09-07 22:07:40

  Fundamental Techniques for Order Optimization

  这是一篇1996年的老paper了，主要讲解了IBM DB2如何针对query当中的有序性进行优化。但对于后续physical property的优化有较为深远的影响，由于DB2的优化器起源于System-R以及其后续演进的starburst，因此延续了system-R中的interesting order和order property的概念。关于system-R的介绍请看之前的文章。 order这种physical property并不只限于order by算子，基于有序的group by/distinct等，都会利用到数据的排序操作，而排序本身就是比较昂贵的计算，因此应该对其做尽可能的优化

  
• 09.07 22:04:36
  发表了文章 2021-09-07 22:04:36

  Accelerating Queries with Group-By and Join By Groupjoin

  这篇paper介绍了HyPer中引入的groupjoin算子，针对 join + group by这种query，可以在某些前提条件下，在join的过程中同时完成grouping+agg的计算。 比如用hash table来实现hash join和group by，就可以避免再创建一个hash table，尤其当join的数据量很大，产生的group结果又较少时，可以很好的提升执行效率。

  
• 09.07 21:46:32
  发表了文章 2021-09-07 21:46:32

  Incorporating Partitioning and Parallel Plans into the SCOPE optimizer

  这篇paper中讨论是的Microsoft的cosmos DB，其本身是一个海量数据的大规模计算平台，有些类似hadoop，使用的是一种类SQL的脚本，叫做SCOPE，针对SCOPE的优化器负责生成最优的执行计划。在1998年前后Microsoft基本丢弃了Sybase原有的优化器实现，并由Graefe主导重写了基于cascades的优化器。因此和Microsoft所有其他的数据库产品一样，SCOPE optimizer也是基于Cascades的transformation-based的优化器。

  
• 09.07 21:28:48
  发表了文章 2021-09-07 21:28:48

  Cost-based query transformation in Oracle

  这篇paper主要介绍了Oracle从10g开始引入的CBQT(Cost Based Query Transformation)框架。虽然以Oracle历来的风格，无法期待它在paper中讨论很多细节，不过这篇还是可以让我们一窥Oracle对于query rewrite的处理思路和很多非常实用的query rewrite模式，对于开发优化器的同学很有参考意义。 值得一提的是，PolarDB目前也在做这方面的工作，而主要的参考正是这篇paper。此外这篇paper的思路和MemSQL optimizer中对query rewrite的处理思路非常接近，关于MemSQL optimizer的介绍可

  
• 09.07 21:20:44
  发表了文章 2021-09-07 21:20:44

  TPC-H深入剖析 part2 Quantifying TPC-H Choke Points and Their Optimizations

  这篇承接了上一篇对于TPC-H中chockpoint的定性分析，基于Hyrise这个学术系统进行了较为孤立且细致的量化分析，并给出了不同类型chokepoint优化对于TPCH query的相对影响。 TPC-H的chokepoints在上一篇已详细介绍，并介绍了MySQL和PolarDB的对应优化情况。

  
• 09.07 21:11:49
  发表了文章 2021-09-07 21:11:49

  TPCH 深入剖析 - part1 Hidden Messages and Lessons Learned from an Influential Benchmark

  TPC-H可以说是世界上最为流行的OLAP workload的benchmark程序，无论你看什么样的论文或技术文章，只要是和query processing相关的，大多会在evaluation时使用TPC-H作为评估工具。而如果你从事query optimization/query execution的工作，则怎么都会和TPC-H打上交道，即使是TP型的数据库系统。

  
• 09.07 21:06:40
  发表了文章 2021-09-07 21:06:40

  On the Correct and Complete Enumeration of the Core Search Space

  在之前的文章中我们讨论了基于graph的DP-based算法，来解决join ordering的枚举问题。 这些DP算法通过join predicate描述的连通性，解决了枚举可能的表组合问题，但join graph本身(即使hypergraph)是无法完整的描述join语义的，因为连通边本身无法描述不同类型的join语义，例如left outer join/semi join/anti join...，因此即使找到了所谓的csg-cmp-pair，也不一定是有效的plan。 这篇paper讨论的就是这个问题，当枚举出一个csg-cmp-pair (S1 o S2)，如何判断这是有效的join

  
• 09.07 20:52:23
  发表了文章 2021-09-07 20:52:23

  Dynamic Programming Strikes Back - MySQL8.0的新优化器

  这篇paper是著名的DPccp算法的延续，仍然是讨论如何最高效的基于Dynamic Programing，实现join ordering这个SQL查询优化中最为核心的功能。

  
• 09.07 20:37:33
  发表了文章 2021-09-07 20:37:33

  New Dynamic Programming Algorithm for the Generation of Optimal Bushy Join Trees

  MySQL无疑是现在开源关系型数据库系统的霸主，在DBEngine的最新排名中仍然稳居第2位，与第3位SQL Server的积分差距并不算小，可以说是最受欢迎，使用度最高的数据库系统，这一点看看有多少新型数据库要兼容MySQL的协议和语法就知道了。

  
• 09.07 20:32:46
  发表了文章 2021-09-07 20:32:46

  Optimizing Queries over Partitioned Tables in MPP Systems

  随着互联网数据的爆炸性增长，传统数据库系统在单表数据容量方面承受了越来越大的压力。以前公司内部的数据库，存放的主要是来自公司业务或内部管理系统的信息，中小型公司甚至一个MySQL实例就搞定了。但现在数据源不仅更丰富，数据量也在指数级增长，从业务的角度，基于hash/range的分区表变得越来越有吸引力。

  
• 09.07 20:17:26
  发表了文章 2021-09-07 20:17:26

  Adaptive and Big Data Scale Parallel Execution in Oracle

  在上篇文章中，主要讨论了SQL Server的MPP数仓系统PDW的分布式优化过程，PolarDB的并行优化从中有所借鉴，本篇文章主要看下这篇介绍Oracle并行执行策略的paper，因为在PolarDB的分布式执行策略中，有很多与其有所重叠。

  
• 09.07 20:11:50
  发表了文章 2021-09-07 20:11:50

  Query Optimization in Microsoft SQL Server PDW

  最近一年一直在做PolarDB的并行优化器，过程中调研了各种分布式数据库系统的优化和执行框架，后续几篇文章将一一分享，首先介绍对PolarDB MySQL的并行优化框架影响最大的，也就是SQL Server PDW。

  
• 09.07 20:09:16
  发表了文章 2021-09-07 20:09:16

  The MemSQL Query Optimizer: A modern optimizer for real-time analytics in a distributed database

  今天我们要介绍的MemSQL就采用这样一种新的形态（Oracle也变为了这种方式 ）：即在做transformation时，要基于cost确定其是否可应用。 当然，本篇paper不止讲解了CBQT，还包括一些MemSQL优化器其他方面的介绍，包括一个有意思的heurstic based bushy join的方案。

  
• 09.07 20:04:23
  发表了文章 2021-09-07 20:04:23

  Testing the Accuracy of Query Optimizers

  在前文最后，我们提到了围绕着Orca打造的测试工具集，其中一个就是本篇paper的主角: TAQO。这个测试框架目标是为了测试优化器cost model的精确性，它针对优化的本质目标，提出了一种简单灵活，且易于扩展的方案，且便于实现。目前在PolarDB的分布式优化器中，我们已经采用了这种方法去度量分布式exchange 算子(Enforcer)和复杂计算(aggregation...)的代价因子。 当然，这个框架不局限于Orca，它可以在近乎黑盒的情况下对cost model进行校准，并针对不同optimizer的cost model质量进行横向评估，如果有开发或扩展优化器cost mode

  
• 09.07 19:58:55
  发表了文章 2021-09-07 19:58:55

  Orca: A Modular Query Optimizer Architecture for Big Data

  在之前的几片paper笔记中，对最为主流的两套优化器框架进行了解读，包括bottom-up dynamic programming的search策略和基于Top-down memorization的search策略

  
• 09.07 19:52:55
  发表了文章 2021-09-07 19:52:55

  The Cascades Framework for Query Optimization

  这篇paper是前一篇Volcano optimizer的后续，其涉及的概念和优化思路是一脉相承的，在阅读本篇之前，最好对Volcano optimizer有足够的了解，详见文章Volcano优化器框架。
• 09.07 19:51:31
  发表了文章 2021-09-07 19:51:31

  The Volcano Optimizer Generator : Extensibility and Efficient Search

  数据库查询优化器的搜索技术，基本上分为了基于动态规划的bottom-up search(详见文章System-R论文解读)和基于Cascades/Volcano的top-down search两个流派，这篇文章我们来看一下Cascades的前身也就是Volcano优化器框架的paper。

  
• 09.07 19:46:44
  发表了文章 2021-09-07 19:46:44

  Access Path Selection in a Relational Database Management System

  如果说选一篇在优化器框架上，被引用次数最多的文献，应该非这篇论文莫属了，还记得Andy Pavlo在cmu的课程中提到IBM Research的一群大神们，是怎么一人一个模块来负责System R的设计的，而关于Join order enumeration，Selinger可以说是开创了dynamic programing based 的bottom-up的搜索空间算法的先河，直至今日，很多成熟的商业或开源数据库系统仍在沿用这套框架，比如Oracle / DB2 / PostgreSQL ...

  
• 09.07 18:37:32
  发表了文章 2021-09-07 18:37:32

  数据库查询优化器论文列表

  过去一年间，对优化器相关论文做了个系统性的学习，把过程中阅读的论文笔记记录在这里，和大家分享，欢迎大家和我一起讨论，纠错补差，共同进步 ~ 阅读路线基本遵照了pingcap github上的一个Awesome Database Learning的资料，这个资料非常棒，包含了一些基本的课程 + 书籍，还按照内核中不同模块的不同方面做了分类，非常系统化，尤其是SQL层面非常详尽，正好符合需求，因此阅读基本也是按其中的paper来，并扩展到一些没有涉及的内容，总体目录如下（优化器部分），由于内容较多，主要挑选其中影响力较大的或者最有参考意义的。