关系数据库优化器概述

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

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...
2021年02月13日 数据库 暂无评论 喜欢 0 阅读 207 次 阅读全文

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） 允许使用启发信息和数据模型语义来引导搜索和剪枝...
2021年02月13日 数据库 暂无评论 喜欢 0 阅读 183 次 阅读全文

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...
2021年02月13日 数据库 暂无评论 喜欢 0 阅读 120 次 阅读全文

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将一个查询计划变成另一个等价的更好的计划。这种灵活可扩展带来一个问题是 不够高效：在任意一步，都需要检查很多转换规则的使用条件，而且可能有多个规...
2021年02月13日 数据库 暂无评论 喜欢 0 阅读 153 次 阅读全文

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...
2021年02月13日 数据库 暂无评论 喜欢 0 阅读 121 次 阅读全文

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...
2020年05月10日 数据库 暂无评论 喜欢 10 阅读 1,038 次 阅读全文

浅析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...
2020年04月30日 分布式, 数据库 暂无评论 喜欢 2 阅读 1,143 次 阅读全文

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的实时数据处理...
2020年04月25日 数据库 暂无评论 喜欢 2 阅读 1,403 次 阅读全文

分布式事务性能的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三选二在业界影响...
2020年04月09日 数据库 评论 2 条 喜欢 2 阅读 556 次 阅读全文