open-courses
  • 公开课笔记
  • 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
On this page
  • Sorting
  • Why Do We Need To Sort?
  • Algorithms
  • Aggregations
  • Sorting Aggregation
  • Hashing Aggregation
  • 参考
  1. CMU 15-445/645 Database Systems

Sorting&Aggregations

Sorting

Why Do We Need To Sort?

需要排序算法的原因:本质在于 tuples 在 table 中没有顺序,无论是用户还是 DBMS 本身,在处理某些任务时希望 tuples 能够按一定的顺序排列,如:

  • 若 tuples 已经排好序,去重操作将变得很容易(DISTINCT)

  • 批量将排好序的 tuples 插入到 B+ Tree index 中,速度更快

  • Aggregations (GROUP BY)

Algorithms

若数据能够放入内存中,我们可以使用标准排序算法搞定,如快排;若数据无法放入内存中,就得考虑数据在 disk 与 memory 中移动的成本,以及排序算法的适配。

External Merge Sort

外部排序通常有两个步骤:

  • Sorting Phase:将数据分成多个 chunks,每个 chunk 可以完全读入到 memory 中,在 memory 中排好序后再写回到 disk 中

  • Merge Phase:将多个子文件合并成一个大文件

2-Way External Merge Sort

以下是 2-way external merge sort 的一个简单例子,假设:

  • Files 本分成 N 个 pages

  • DBMS 有 B 个 fixed-size buffers

Pass #0

  • 从 table 中读入 B pages tuples

  • 将这些 tuples 排序后写会到 disk 中

  • 每一轮成为一个 run

Pass #1,2,3,...

  • 递归地将一对 runs 合并成一个两倍长度的 run

  • 这一操作值需要 3 个 buffer pages ( 2 个用于输入,1个用于输出)

完整过程如下图所示:

复杂度:

值得注意的是:

  • 这个算法只需要 3 个 buffer pages,B=3

  • 即使 DBMS 能够提供更多的 buffer pages(B>3),2-way external merge sort 也无法充分地利用它们

如何能够利用到更多的 buffer pages ?

General External Merge Sort

将以上的 2-way external merge sort 泛化成 N-Way 的形式:

Pass #0

  • 使用 B 个 buffer pages

Pass #1,2,3,...

  • 合并 B-1 runs

复杂度:

实例:Sort 108 pages file with 5 buffer pages:N = 108, B = 5

  • Pass #3: sorted file of 108 pages

Using B+ Trees

如果被排序的表在对应的 attribute(s) 上已经建有索引,我们就可以用它来加速排序的过程,按照目标顺序遍历 B+ Tree 的 leaf pages 即可,但这里要注意有两种情况:

  • Clustered B+ Tree

  • Unclustered B+ Tree

case 1: Clustered B+ Tree

这种情况永远由于 external sorting。

case 2: Unclustered B+ Tree

这是最糟糕的情况,因为获取每个 data record 的过程都可能需要一次 I/O。

Aggregations

aggregation 就是对一组 tuples 的某些值做统计,转化成一个标量,如平均值、最大值、最小值等,aggregation 的实现通常有两种方案:

  • Sorting

  • Hashing

Sorting Aggregation

但很多时候我们并不需要排好序的数据,如:

  • Forming groups in GROUP BY

  • Removing duplicates in DISTINCT

在这样的场景下 hashing 是更好的选择,它能有效减少排序所需的额外工作。

Hashing Aggregation

利用一个临时 (ephemeral) 的 hash table 来记录必要的信息,即检查 hash table 中是否存在已经记录过的元素并作出相应操作:

  • DISTINCT: Discard duplicate

  • GROUP BY: Perform aggregate computation

如果所有信息都能一次性读入内存,那事情就很简单了,但如若不然,我们就得变得更聪明。

hashing aggregation 同样分成两步:

  • Partition Phase: 将 tuples 根据 hash key 放入不同的 buckets

    • use a hash function h1 to split tuples into partitions on disk

      • all matches live in the same partition

      • partitions are "spilled" to disk via output buffers

    • 这里有个额外的假设,即每个 partition 能够被放到 memory 中

  • ReHash Phase: 在内存中针对每个 partition 利用 hash table 计算 aggregation 的结果

如下图所示:

  • 如果我们发现相应的 GroupKey 已经在内存中,只需要更新 RunningVal 就可以

  • 反之,则插入新的 GroupKey 到 RunningVal 的键值对

Cost Analysis

使用 hashing aggregation 可以聚合多大的 table ?假设有 B 个 buffer pages

  • Phase #1:使用 1 个 page 读数据,B-1 个 page 写出 B-1 个 partition 的数据

  • 每个 partition 的数据应当小于 B 个 pages

参考

PreviousQuery ProcessingNextJoin Algorithms

Last updated 6 years ago

number of passes:1+ceil(log2N)1+ ceil(log_2{N})1+ceil(log2​N)

cost/pass:I/O 成本为 2N2N2N,系数 2 表示读入 + 写出。

total cost: 2N×(number of passes)2N \times (number \ of \ passes)2N×(number of passes)

产生 ceil(N/B)ceil(N/B)ceil(N/B) 个大小为 B 的 sorted runs

number of passes: 1+ceil(logB−1ceil(N/B))1 + ceil(log_{B-1}{ceil(N/B)})1+ceil(logB−1​ceil(N/B))

cost/pass: 2N2N2N

total cost: 2N×(number of passes)2N\times(number \ of \ passes)2N×(number of passes)

Pass #0: ceil(108/5)=22ceil(108/5) = 22ceil(108/5)=22 sorted runs of 5 pages each

Pass #1: ceil(22/4)=6ceil(22/4) = 6ceil(22/4)=6 sorted runs of 20 pages each

Pass #2: ceil(6/4)=2ceil(6/4) = 2ceil(6/4)=2 sorted runs of 80 pages and 28 pages each

一共有 1+ceil(logB−1ceil(N/B))=1+ceil(log422)=4 passes1+ceil(log_{B-1}{ceil(N/B)}) = 1+ceil(log_4{22}) = 4 \ passes1+ceil(logB−1​ceil(N/B))=1+ceil(log4​22)=4 passes

在 ReHash phase 中,存着 (GroupKey→RunningVal)(GroupKey \rightarrow RunningVal)(GroupKey→RunningVal) 的键值对,当我们需要向 hash table 中插入新的 tuple 时:

因此能够聚合的 table 最大为 B×(B−1)B \times (B-1)B×(B−1)

通常一个大小为 N pages 的 table 需要大约 N\sqrt{N}N​ 个 buffer pages

slides