关系数据库优化器概述

关系数据库优化器概述
《An Overview of Query Optimization in Relational Systems》PODS 1998, Microsoft Research 优化器的输入是用户查询,负责生成一个高效的执行计划,优化过程是一个比较复杂的过程。 优化器主要包含三个部分: Search Space:搜索空间包含足够好的计划 代价估计:代价估计足够精确 枚举算法:枚举算法要足够高效 System R优化器案例 以System R为例来初步看下优化器的这三部分,通过这一节,对优化器...

The Columbia Optimizer

The Columbia Optimizer
  《EFFICIENCY IN THE COLUMBIA DATABASE QUERY OPTIMIZER》 1998 这是Portland State University的硕士论文,作者是YONGWEN XU,相比Cascades论文的跳跃和晦涩,这篇可以说是很良心了。 Motivation 当时背景下,优化器仍然是值得研究的方向,尤其是在Decision Support Systems(DSS)、OLAP、大数据量、复杂对象、新的执行技术如并行和分布式执行等等。 第一代可扩展的优化器包括EXODUS、Starburst...

The Volcano Optimizer Generator

The Volcano Optimizer Generator
  《The Volcano Optimizer Generator : Extensibility and Efficient Search》1993 论文介绍了在EXODUS之后的一个新的优化器生成器Volcano。 一个好的optimizer generator要满足如下条件: 既能用到Volcano Executor,也能用到已经存在的其他执行器 优化的时间消耗和内存消耗都比较低 能够高效、可扩展地支持物理属性(如sort order、compression) 允许使用启发信息和数据模型语义来引导搜索和剪枝...

Extensible/Rule Based Query Rewrite Optimization in Starburst

Extensible/Rule Based Query Rewrite Optimization in Starburst
      《Extensible/Rule Based Query Rewrite Optimization in Starburst》SIGMOD 1992 这篇文章是介绍Starburst的基于规则的优化器实现框架。 背景 很多业务的SQL语句或类SQL语句,尤其是中间件软件自动生成的SQL语句,主要面向业务模型,如果不做query rewrite,可能执行非常慢。 例如: 12345678 DISTINCT PFROM Patient p IN Patient_S...

Grammar-like Functional Rules - for Representing Query Optimization Alternatives

Grammar-like Functional Rules - for Representing Query Optimization Alternatives
  《Grammar-like Functional Rules - for Representing Query Optimization Alternatives》 SIGMOD 1988 概述 优化器如果要做到可扩展,则要求执行计划的变换策略需要作为数据而不是代码存在。本质上优化器就是一个专家系统,使用strategy rules将一个查询计划变成另一个等价的更好的计划。这种灵活可扩展带来一个问题是 不够高效:在任意一步,都需要检查很多转换规则的使用条件,而且可能有多个规...

Access Path Selection in a RDBMS

Access Path Selection in a RDBMS
《Access Path Selection in a Relational Database Management System》 1979   SQL语句处理的四个阶段:Parsing, Optimization, Code Generation, Execution。 query block: 由select from where表达的查询块。   单表查询 代价 Access Path Cost公式: cost = page fetches + w * (RSI calls),其中rsi for system R storage interface。 公式是IO代价(主要是读取页面)和CPU代价(System R...

LB+Tree:面向3DXPoint优化的B+Tree

LB+Tree:面向3DXPoint优化的B+Tree
  《LB+Trees: Optimizing Persistent Index Performance on 3DXPoint Memory》(VLDB20')   这是个设计非常巧妙的数据结构,这里简单描述下核心内容,读者可以直接读原文,行文非常清晰。   Abstract 3DXPoint的有些硬件特性,跟常规NVM差不多: 3DXPoint的访存粒度是64字节Cache Line 3DXPoint比DRAM慢2倍,比SSD快几个数量级 3DXPoint的写比读慢 使用clwb/sfence等特殊指令将数据从CPU...

浅析Aurora Quorum

浅析Aurora Quorum
  Aurora在SIGMOD18'的论文《Amazon Aurora: On Avoiding Distributed Consensus for I/Os, Commits, and Membership Changes》中描述了Aurora关于共识方案的选择和Quorum方案的详细内容,本文这里做一些简单的分析。     Aurora架构背景 在描述Aurora的Quorum方案前,先介绍下Aurora的系统架构。 Aurora是share-storage、一写多读的架构,构建在MySQL(InnoDB)代码库上,当然后来增加了mult...

LSMTree综述

LSMTree综述
  LSM-based storage techniques: a survey (VLDBJ 2020)   This paper aims to serve as a guide to the state of the art in LSM-based storage techniques for researchers, practitioners, and users.   LSMTree引擎在业界已经有了很多的落地。很多NoSQL系统如Bigtable、Dynamo、HBase、Cassandra、LevelDB、RocksDB、AsterixDB底层都是LSMTree引擎。RocksDB在Facebook的实时数据处理...

分布式事务性能的FIT取舍

分布式事务性能的FIT取舍
  《FIT: A Distributed Database Performance Tradeoff》 Bulletin of the IEEE Computer Society Technical Committee on Data Engineering 2015   这篇文章不长,内容也不多,介绍了一个分布式数据库性能的tradeoff原则叫FIT。其实也不叫原则,就是一个模糊的设计直觉。   FIT的意思是分布式数据库的Fairness, Isolation, Throughput必须要取舍,最多三选二。 可能CAP三选二在业界影响...