Query Plan如图所示，通常一个 SQL 会被组织成树状的查询计划，数据从 leaf nodes 流到 root，查询结果在 root 中得出。而本节将讨论在这样一个计划中，如何为这个数据流动过程建模，主要围绕： Processing Models Access Methods Expression Evaluation Processing ModelsDBMS 的 processing model 定义了系统如何执行一个 query plan，目前主要有三种模型，不同模型的适用场景不同。 Model Direction Emits Target Iterator/Volcano Top-Down Single Tuple General Purpose Materialization Bottom-Up Entire Tuple Set OLTP Vectorized Top-Down Tuple Batch OLAP Iterator Modelquery plan 中的每步 operator 都实现一个 next 函数，每次调用 ...

本节主体部分介绍以下三种Join算法： Nested Loop Join（Simple、Block、Index） Sort-Merge Join Hash Join 为什么进行Join操作为了避免保存重复信息，我们一般会通过范式将表数据保存在数据库中。我们利用Join操作来还原重建原始的表数据。以课程伊始时的 table 为例，通过将 Artist 与 Album 之间的多对多关系拆成 Artist, ArtistAlbum 以及 Album 三个 tables 来规范化数据，使得数据存储的冗余减少，查询时我们就需要通过 Join 来重建 Artist 与 Album 的完整关系数据。 本课时主要讨论了Join操作的output以及I/O分析两个方面的内容。 Join 输出逻辑上 Join 的操作的结果是：对任意一个 tuple r ∈ R 和任意一个在 Join Attributes 上对应的 tuple s ∈ S，将 r 和 s 串联成S一个新的 tuple。 Join 操作的结果 tuple 中除了 Join Attributes 之外的信息与多个因素相关：（ ...

Sorting我们需要排序，因为在关系模型中，表中的元组没有特定的顺序。排序（可能）按顺序BY、组BY、JOIN和不同的操作符使用。不仅仅是 order by 需要排序，像 DISTINCT 、GROUP BY 指令也需要有排序T这个需求。DISTINCT 指令的主要工作是先排序，然后去重。GROUP BY 是分组聚合指令，需要把相同的类型聚集在一起，更需要用到排序操作。 我们可以通过从左到右扫描叶节点，使用clustered B+树来加速排序。然而，如果我们使用一个unclustered B+树来排序，这是一个坏主意，因为它会导致大量的I/O读取（通过指针跟踪的随机访问）。 如果我们需要排序的数据可以装入内存，那么DBMS可以使用标准的排序算法（例如，快速排序）。如果数据不能全部装入内存，那么DBMS需要使用外部排序，它能够根据需要溢出到磁盘，并且更倾向于使用顺序排序，而不是随机I/O。 External Merge Sort分治排序算法，将数据集划分为不同的运行，然后分别对它们进行排序。它可以根据需要将运行溢出到磁盘，然后一次读取它们。 下图是一个2路外部归并排序的例子，首先利用 ...

索引并发控制本节讨论让数据结构具备并发安全的特点，尽管本节仅仅是介绍 B+ Tree 上的相关技术。在前两节中讨论的数据结构中，我们都只考虑单线程访问的情况，即只能有一个线程在同时刻访问我们的数据结构。现实中我们是希望多线程在同一时刻访问我们的数据结构。本节课讨论允许多个线程安全地访问我们的数据结构，现在的CPU都是多核，需要考虑到允许多个线程查询和更新。 通常我们会从两个层面上来理解并发控制的正确性： 逻辑正确性：（后续讨论）我希望看到的值是我期待看到的值！例如我插入了5这个值，等我插入完后回过头看，5这个值应该存在，而不会是false的。 物理正确性：（本节讨论）数据的内部表示是否完好？如何保证线程读取数据时该数据结构的可靠性？ Locks vs Latches本课程主要研究的是Latches 数据库中特有的 Locks 一般是指行锁、范围锁、表锁这些。用来做事务之间的并发控制。是更为上层的抽象锁。在整个事务期间持有，DBMS需要具有回滚功能。 Latches 就是在多线程编程、操作系统学习中遇到的多线程中接触到的锁，如 mutex、rwlock、semaphore、spi ...

Indexestable index是数据columns子集的复制，允许DBMS可以比顺序扫描更快的查找tuple。DBMS保证数据表的内容和索引内容同步。对于指定查询，选择哪一种索引以使得查询执行的更快是DBMS来完成的。建立索引需要额外的存储开销，也需要维护，所以每个数据库创建的索引数量需要trade-off。 B+Tree定义： 自平衡，每个叶子节点所处高度一致 除叶子节点外每个节点至少满足:\frac{M}{2} − 1

讨论如何支持DBMS执行引擎从页中读写数据。主要涉及两种数据结构： Hash Tables Trees Data StructureDBMS为系统内部的许多不同部分使用不同的数据结构： Internal Meta-Data： 跟踪有关数据库和系统状态的信息 Core Data Storage： 可用作数据库中的元组的基本存储器 Temporary Data Structure： DBMS可以在处理查询时动态地构建数据结构，以加快执行速度（例如，连接的哈希表） Table Indexes： 辅助数据结构，使它更容易找到特定的元组 设计决策： 数据组织：我们如何布局内存，以及在数据结构中存储的信息。 并发性：如何使多个线程能够访问数据结构而不会引起问题。 Hash Table 哈希表实现了一个将键映射到值的关联数组抽象数据类型。它提供了平均O(1)操作复杂性和O(n)存储复杂度。 哈希表的实现可以分为两个部分： Hash Function： 如何将一个很大的地址空间映射到一个更小的域，将索引通过计算映射到一个桶数组或者slot。需要在计算速度与哈希碰撞率之间进行权衡。 ...

上一节描述了DBMS如何在磁盘的文件上描述数据库，这一节将描述DBMS如何管理其内存以及管理数据在磁盘上的来回移动。 这里总结一下两个概念： Spatial Control：空间控制 将页面写入磁盘的哪个位置 其目标是使一起使用的页面在物理上尽可能接近 Temporal Control：时间控制 何时将页面读入内存，何时将其写入磁盘 其目标是最小化必须从磁盘读取数据时产生的延迟 Locks vs. Latches在讨论DBMS如何保护其内部元素时，我们需要区分锁（lock）和锁存器（latch）。 Lock： 保护数据库的逻辑内容，如元组、表、数据库不受其他事务影响 事务处理期间一直持有 需要能够回滚更改 Latch： 保护DBMS内部数据结构的关键部分不受其他线程的影响 操作期间持有 不需要能够回滚更改 Buffer PoolBuffer Pool是从磁盘读取的页面的内存缓存。由于DBMS比OS更了解数据库的实际状况，所以我们想要自己管理内存以及页面。 Buffer Pool是一个由固定大小页面数组组织起来的内存区域。数组中的每一项称为frame。当DBMS请求一个页 ...

存储我们将重点关注一个“面向磁盘”的DBMS体系结构，该体系结构假设数据库的主存储位置位于非易失性磁盘上。 在存储层次结构的顶部，您有最接近CPU的设备。这是最快的存储空间，但它也是最小和最昂贵的。远离CPU越远，存储设备的容量就越大，但离CPU也越远。这些设备的每GB值也会更便宜。 Volatile Devices: Volatile means that if you pull the power from the machine, then the data is lost. Volatile storage supports fast random access with byte-addressable locations. This means that the program can jump to any byte address and get the data that is there. For our purposes, we will always refer to this storage class as “memory”. Non-Volatile ...

Relational Languages 埃德加·科德在20世纪70年代早期发表了一篇关于关系模型的主要论文。他最初只定义了DBMS如何在关系模型DBMS上执行查询的数学符号。 用户只需要使用声明性语言(即SQL)来指定他们想要的结果。DBMS负责确定最有效的计划来得出这个答案。 关系代数是基于集合（无序，无重复）。SQL基于包（未订购，允许重复）。 SQL History SQL: Structured Query Language IBM originally called it “SEQUEL”. Comprised of different classes of commands: Data Manipulation Language (DML): SELECT, INSERT, UPDATE, DELETE. Data Definition Language (DDL): Schema definition. Data Control Language (DCL): Security, access controls. SQL并不是一种不变的语言。它每隔几年就会更新一次 ...

cmu 14-445是卡耐基梅隆大学的一门数据库课程 Overall Introduction of this class Relation Databases Storage Execution Concurrency Control Distributed Databases Potpourri Databases数据库是一个有组织的相互关联的数据集合，它为现实世界的某些方面建模（例如，在课堂或数字音乐存储中建模学生）。人们经常混淆“数据库”和“数据库管理系统”(例如，MySQL，Oracle，MongoDB)。数据库管理系统(DBMS)是一种管理数据库的软件。 考虑一个为数字音乐商店建模的数据库(例如，Spotify)。让数据库中保存关于这些艺术家的信息，以及这些艺术家已经发布了哪些专辑。 Flat File Strawman数据库以DBMS管理的逗号分隔值(CSV)文件存储。每个实体都将存储在其自己的文件中。应用程序在每次想要读取或更新记录时都必须解析文件。每个实体都有自己的一组属性，因此在每个文件中，不同的记录由新行分隔，而记录中的每个相应属性都用逗号分隔。 按照数字音乐 ...