open-courses
Search…
公开课笔记
CMU 15-445/645 Database Systems
Relational Data Model
Advanced SQL
Database Storage
Buffer Pools
Hash Tables
Tree Indexes
Index Concurrency Control
Query Processing
Sorting&Aggregations
Join Algorithms
Query Optimization
Parallel Execution
Embedded Database Logic
Concurrency Control Theory
Two Phase Locking
Timestamp Ordering Concurrency Control
Multi-Version Concurrency Control
Logging Schemes
Database Recovery
Introduction to Distributed Databases
Distributed OLTP Databases
Distributed OLAP Databases
UCB - CS162
OS intro
Introduction to the Process
Processes, Fork, I/O, Files
I/O Continued, Sockets, Networking
Concurrency: Processes & Threads
Cooperating Threads, Synchronization
Semaphores, Condition Variables, Readers/Writers
Scheduling
Resource Contention & Deadlock
Address Translation, Caching
File System (18,19,20)
Distributed Systems, Networking, TCP/IP, RPC (21,22)
Distributed Storage, Key-Value Stores, Security (23)
Security & Cloud Computing (24)
Topic: Ensuring Data Reaches Disk
MIT - 6.006
Sequence and Set Interface
Data Structure for Dynamic Sequence Interface
Computation Complexity
Algorithms and Computation
Structure Of Computation
Graph & Search
Tree & Search
Weighted Shortest Paths
String Matching, Karp-Rabin
Priority Queue Interface & Implementation
Dictionary Problem & Implementation
Sorting
Dynamic Programming
Backtracking
Self-Balancing Tree
MIT - 6.824
2PC & 3PC
Introduction and MapReduce
RPC and Threads
Primary/Backup Replication
Lab: Primary/Backup Key/Value Service
Google File System (GFS)
Raft
Lab: Raft - Leader Election
Lab: Raft - Log Replication
Stanford-CS107
原始数据类型及相互转化
指鹿为马
泛型函数
泛型栈
运行时内存结构
从 C 到汇编
函数的活动记录
C 与 C++ 代码生成
编译的预处理过程
编译的链接过程
函数的活动记录续、并发
从顺序到并发和并行
信号量与多线程 1
信号量与多线程 2
复杂多线程问题
函数式编程 - Scheme 1
函数式编程 - Scheme 2
函数式编程 - Scheme 3
函数式编程 - Scheme 4
函数式编程 - Scheme 5
Python 基础
MIT - 6.001 - SICP
什么是程序
程序抽象
替代模型
时间/空间复杂度
数据抽象
高阶函数
Symbol
数据驱动编程与防御式编程
数据抽象中的效率与可读性
数据修改
环境模型
面向对象-消息传递
面向对象 - Scheme 实现
构建 Scheme 解释器
Eval-Apply Loop
Normal Order (Lazy) Evaluation
通用机
寄存器机器
子程序、栈与递归
在寄存器机器中执行
内存管理
MIT - 6.046
Randomized Algorithms
Skip Lists
System Design
Twitter
Cache Consistency & Coherence
DDIA 笔记
Replication
Transactions
The Trouble with Distributed Systems
Consistency & Consensus
Papers We Love
Consistent Hashing and Random Trees (1997)
Dynamic Hash Tables (1988)
LFU Implementation With O(1) Complexity (2010)
Time, Clocks, and the Ordering of Events in a Distributed System (1978)
Dapper, a Large-Scale Distributed Systems Tracing Infrastructure (2010)
Gorilla: A Fast, Scalable, In-Memory Time Series Database (2015)
Release It 笔记
Anti-patterns & Patterns in Microservice Architecture
Database Design
Log Structured Merge (LSM) Tree & Usages in KV Stores
Prometheus
Powered By
GitBook
Query Processing
简介
如上图所示,通常一个 SQL 会被组织成树状的查询计划,数据从 leaf nodes 流到 root,查询结果在 root 中得出。而本节将讨论在这样一个计划中,如何为这个数据流动过程建模,大纲如下:
Processing Models
Access Methods
Expression Evaluation
Processing Model
DBMS 的 processing model 定义了系统如何执行一个 query plan,目前主要有三种模型:
Iterator Model
Materialization Model
Vectorized/Batch Model
不同模型的适用场景不同。
Iterator Model
query plan 中的每步 operator 都实现一个 next 函数,每次调用时,operator 返回一个 tuple 或者 null,后者表示数据已经遍历完毕。operator 本身实现一个循环,每次调用其 child operators 的 next 函数,从它们那边获取下一条数据供自己操作,这样整个 query plan 就被从上至下地串联起来,它也称为 Volcano/Pipeline Model:
Iterator 几乎被用在每个 DBMS 中,包括 sqlite、MySQL、PostgreSQL 等等,其它需要注意的是:
有些 operators 会等待 children 返回所有 tuples 后才执行,如 Joins, Subqueries 和 Order By
Output Control 在 Iterator Model 中比较容易,如 Limit,只按需调用 next 即可。
Materialization Model
每个 operator 处理完所有输入后,将所有结果一次性输出,DBMS 会将一些参数传递到 operator 中防止处理过多的数据,这是一种从下至上的思路,示意如下:
materialization model:
更适合 OLTP 场景,因为后者通常指需要处理少量的 tuples,这样能减少不必要的执行、调度成本
不太适合会产生大量中间结果的 OLAP 查询
Vectorization Model
Vectorization Model 是 Iterator 与 Materialization Model 折衷的一种模型:
每个 operator 实现一个 next 函数,但每次 next 调用返回一批 tuples,而不是单个 tuple
operator 内部的循环每次也是一批一批 tuples 地处理
batch 的大小可以根据需要改变(hardware、query properties)
vectorization model 是 OLAP 查询的理想模型:
极大地减少每个 operator 的调用次数
允许 operators 使用 vectorized instructions (SIMD) 来批量处理 tuples
目前在使用这种模型的 DBMS 有 VectorWise, Peloton, Preston, SQL Server, ORACLE, DB2 等。
Summary
Models
Direction
Emits
Target
Iterator/Volcano
Top-Down
Single Tuple
General Purpose
Vectorized
Top-Down
Tuple Batch
OLAP
Materialization
Bottom-Up
Entire Tuple Set
OLTP
Access Methods
access method 指的是 DBMS 从数据表中获取数据的方式,它并没有在 relational algebra 中定义。主要有三种方法:
Sequential Scan
Index Scan
Multi-Index/"Bitmap" Scan
Sequential Scan
顾名思义,sequential scan 就是按顺序从 table 所在的 pages 中取出 tuple,这种方式是 DBMS 能做的最坏的打算。
for
page
in
table
.
pages
:
for
t
in
page
.
tuples
:
if
evalPred
(
t
):
# do something
DBMS 内部需要维护一个 cursor 来追踪之前访问到的位置(page/slot)。Sequential Scan 是最差的方案,因此也针对地有许多优化方案:
Prefetching
Parallelization
Buffer Pool Bypass
(本节) Zone Maps
(本节) Late Materialization
(本节) Heap Clustering
Zone Maps
预先为每个 page 计算好 attribute values 的一些统计值,DBMS 在访问 page 之前先检查 zone map,确认一下是否要继续访问,如下图所示:
当 DBMS 发现 page 的 Zone Map 中记录 val 的最大值为 400 时,就没有必要访问这个 page。
Late Materialization
在列存储 DBMS 中,每个 operator 只选取查询所需的列数据,若该列数据在查询树上方并不需要,则仅需向上传递 offsets 即可:
Heap Clustering
使用 clustering index 时,tuples 在 page 中按照相应的顺序排列,如果查询访问的是被索引的 attributes,DBMS 就可以直接跳跃访问目标 tuples。
Index Scan
DBMS 选择一个 index 来找到查询需要的 tuples。使用哪个 index 取决于以下几个因素:
index 包含哪些 attributes
查询引用了哪些 attributes
attribute 的定义域
predicate composition
index 的 key 是 unique 还是 non-unique
这些问题都将在后面的课程中详细描述,本节只是对 Index Scan 作概括性介绍。
尽管选择哪个 Index 取决于很多因素,但其核心思想就是,越早过滤掉越多的 tuples 越好,如下面这个 query 所示:
SELECT
*
FROM
students
WHERE
age
<
30
AND
dept
=
'CS'
AND
country
=
'US'
;
students 在不同 attributes 上的分布可能如下所示:
Scenario #1:使用 dept 的 index 能过滤掉更多的 tuples
Scenario #2:使用 country 的 index 能过滤掉更多的 tuples
Multi-index Scan
如果有多个 indexes 同时可以供 DBMS 使用,就可以做这样的事情:
计算出符合每个 index 的 tuple id sets
基于 predicates (union vs. intersection) 来确定是对集合取交集还是并集
取出相应的 tuples 并完成剩下的处理
Postgres 称 multi-index scan 为 Bitmap Scan。
仍然以上一个 SQL 为例,使用 multi-index scan 的过程如下所示:
其中取集合交集可以使用 bitmaps, hash tables 或者 bloom filters。
Index Scan Page Sorting
当使用的不是 clustering index 时,实际上按 index 顺序检索的过程是非常低效的,DBMS 很有可能需要不断地在不同的 pages 之间来回切换。为了解决这个问题,DBMS 通常会先找到所有需要的 tuples,根据它们的 page id 来排序,完毕后再读取 tuples 数据,使得整个过程每个需要访问的 page 只会被访问一次。如下图所示:
Expression Evaluation
DBMS 使用 expression tree 来表示一个 WHERE 语句,如下图所示:
然后根据 expression tree 完成数据过滤的判断,但这个过程比较低效,很多 DBMS 采用 JIT Compilation 的方式,直接将比较的过程编译成机器码来执行,提高 expression evaluation 的效率。
参考
slides
, video
CMU 15-445/645 Database Systems - Previous
Index Concurrency Control
Next - CMU 15-445/645 Database Systems
Sorting&Aggregations
Last modified
1yr ago
Copy link
Outline
简介
Processing Model
Iterator Model
Materialization Model
Vectorization Model
Summary
Access Methods
Sequential Scan
Index Scan
Expression Evaluation
参考