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的实时数据处理...

偏序/DAG的一个例子

偏序/DAG的一个例子
  序问题可以说是分布式系统中天字第一号问题,因为它来自分布式系统最基础的那个系统模型假设 - 异步网络,而且影响了分布式系统算法设计等等很多方面。分布式系统的序问题阐述起来非常庞大,这里只是简单描述下跟偏序/DAG的一个例子 - 区块链公链的DAG。   前面已经写过一点关于偏序的东西,读者可以参见Anna KVS中的Lattice是什么?里面介绍的一些内容。   首先从比特币网络开始,比特币...

分布式事务性能的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三选二在业界影响...

Calvin简介

Calvin简介
前面介绍的并发控制算法评估里面,测试也把Cavlin算进来了,这里简单介绍下Calvin。详细的可以参考下原论文 Calvin: Fast Distributed Transactions for Partitioned Database Systems (SIGMOD12')。   Calvin面向的场景是确定性事务,不支持交互式事务。这一点需要特别注意。在互联网很多业务里,这点是不适用的。   Calvin也是一个deterministic的分布式数据库,这里先简单介绍下它的架构。...

Hekaton内存引擎

Hekaton内存引擎
Hekaton: SQL Server’s Memory-Optimized OLTP Engine(SIGMOD13') Hekaton是SQL Server的一个纯内存数据引擎,用户可以声明一张表存放在Hekaton上,这张表完全支持原SQL Server所有操作,包括T-SQL。同时如果T-SQL只涉及Hekaton表,T-SQL还可以进一步编译执行,性能更高。   为什么要重新设计Hekaton引擎? 单纯优化现有的SQL Server还能不能有10-100倍吞吐提升? 说到底吞吐提升的三条路:提升sca...