CMU15445听课笔记

学一学CMU的15445，课程地址

Lecture #01 - Relational Model & Algebra

Notes

一些有关关系型数据库的概念，一些关系源语

---

Lecture #02 - Modern SQL

Notes

彩蛋：Andy 教授在课上播放了在若干年前他教他的女儿写第一条 SQL 查询语句的视频，太可爱了

不同 DBMS 所使用的 SQL 语法有所不同，但最后都要有分号！！！

补充一些之前没有学习到并且很重要的 SQL 语句

• 窗口函数（Window Function）是 SQL 中一种可以在查询结果中对一组行进行计算的函数。与聚合函数（如 SUM、AVG、COUNT 等）不同，聚合函数会对一组行返回一个单一的值，而窗口函数可以对每一行单独进行计算，并且仍然保留查询结果中的所有行（MySQL 不支持）

  SELECT 列1, 列2, 
         窗口函数() OVER (
             PARTITION BY 列名 
             ORDER BY 列名 
             ROWS/RANGE BETWEEN 
             UNBOUNDED PRECEDING AND CURRENT ROW
         )
  FROM 表名;

  1. 窗口函数：指你使用的函数（如 ROW_NUMBER()、RANK()、SUM()、AVG()、LEAD()、LAG() 等）
  2. OVER() 子句：定义了窗口，也就是窗口函数操作的行集 - PARTITION BY：用来将结果集分成不同的分区，每个分区会单独计算窗口函数。类似于 GROUP BY - ORDER BY：定义了每个分区中行的排序，通常是需要的，特别是对于 ROW_NUMBER()、RANK() 这样的函数 - ROWS/RANGE：定义了窗口框架，决定哪些行会被包含在每次计算中

• 横向查询（Lateral Join）是 SQL 中的一种连接类型，它允许子查询引用来自外部查询的列。具体来说，LATERAL 关键字使得子查询在每一行外部查询的结果集时可以“横向”展开，从而为每一行产生不同的结果

  简单来说，LATERAL 使得子查询在查询执行过程中能够访问外部查询的每一行数据，而不像普通的子查询那样仅仅返回一个固定结果

• Common Table Expressions (CTEs) 是 SQL 中的一种构造方式，它允许你定义一个临时结果集（类似于视图），并在查询的其他部分引用它。CTE 提高了查询的可读性和可维护性，特别是在处理复杂的查询时。CTE 是通过使用 WITH 关键字来定义的，它通常用于临时计算、递归查询或者分步解决复杂查询的问题

  WITH cte_name AS (
      -- 子查询
      SELECT column1, column2
      FROM table
      WHERE condition
  )
  SELECT * FROM cte_name;

---

Lecture #03 - Database Storage I

Notes

Andy 教授说话太快了 T_T

focus on Disk-oriented DBMS

这个机制很像 OS 中的 Virtual Memory 的实现，Buffer Pool 类似 TLB

本节主要讨论 DBMS 如何在磁盘文件中组织数据

1. The DBMS stores a databases as one or more files on disk typically in a proprietary format

2. the storage manager 负责将数据以页面的形式组织在文件中，同时追踪数据读写和可用空间，通常不建立和维护页面副本

3. 数据（tuples, meta-data, indexes, log records...）在文件中以 pages 的形式被存储

   • 有些 DBMS 要求页面 self-contained (e.g., Oracle)，原因是在 disaster recovery 时可以恢复尽可能多的数据

   • 每个页有唯一的 page ID 便于检索，the DBMS uses an indirection layer to map page IDs to physical locations

   • 三种 page：Hardware Page (usually 4KB), OS Page (usually 4KB, x64 2MB/1GB), Database Page (512B-32KB)

   • A hardware page is the largest block of data that the storage device can guarantee failsafe writes

4. 大部分 DBMSs 以 Heap File Organization 的方式组织文件中的 pages

   • A heap file is an unordered collection of pages with tuples that are stored in random order.

     

5. Every page contains a header of meta-data about the page's contents (e.g., page size, checksum, DBMS version, transaction visibility, compression/encoding meta-data, schema information, data summary/sketches)

6. 页面中组织数据三种方式：Tuple-oriented Storage, Log-structured Storage, Index-organized Storage

7. Tuple-oriented Storage 的一种普遍的实现方式：slotted pages

   

   • 插入一个新元组：
     • 检查 page directory 找到一个有 free slot 的 page
     • 如果不在内存中的话从磁盘中检索该 page
     • 检查 slot array 找到可以盛下的空位
   • 利用 Record ID 更新已有的元组:
     • 检查 page directory 找到 page 位置
     • 如果不在内存中的话从磁盘中检索该 page
     • 检查 slot array 找到偏移量
     • 如果新数据可以盛下就覆盖原有数据，否则把原有数据标记删除，在新页面插入一个新版本

8. Record IDs: The DBMS assigns each logical tuple a unique record identifier that that represents its physical location in the database (but shouldn't be relied on to fetch data)

最后 tuple layout 的部分 Andy 教授没有讲完，有一些疑惑问了 ChatGPT，记录一下

9. A tuple is essentially a sequence of bytes. These bytes do not have to be contiguous. 这个下一节的 large value 会提到
10. tuple 存储的时候也有自己的 header，主要存储 Visibility info（事务信息，支持并发控制）和 Null Bitmap（空值位图），不存储每个 attribute 的类型，这个下一节的 system catalogs 会提到
11. Denormalize: If two tables are related, the DBMS can "pre-join" them, so the tables end up on the same page. This makes reads faster since the DBMS only has to load in one page rather than two separate pages. However, it makes updates more expensive since the DBMS needs more space for each tuple

---

Lecture #04 - Database Storage II

Notes

Log-Structured Storage

查询/修改过程：

SummaryTable 会告诉你你要找的数据在不在某一个 level

SSTables 的压缩过程：

缺点：

• 写放大（Write-Amplification）：在一个写操作后，这个操作会被重写若干次
• 压缩成本高（Compaction is expensive）

Ideal for write-heavy workloads because it maximizes sequential disk I/O

Index-Organized Storage

B+树为例

Tuple Storage

1. Data 只是一些 bytes，类型甚至是 unsigned char*，我们需要 reinterpret_cast<int32_t*>(address) （在C++中）
2. 为了使查询快速，我们要保证 tuple 的属性值是字节对齐的
3. 不一样的属性顺序排序可能会影响存储 tuple 的大小

Data Representation

1. 单/双精度会有 rounding error，如果不能接受，使用 fixed precision numbers，如 numeric 和 decimal

2. NULL Data Types

   • Row-stores: Null Column Bitmap Header
   • Column-stores: Special Valuew
   • Per Attribute Null Flag，会打乱对齐，不建议

3. 处理 large values

   如果一个值需要的存储空间大于一个页了，DBMS 会将其存储在 overflow storage pages

   

   一些系统允许把 large value 存在外部文件里，类型为 BLOB，但是 DBMS 就管不了了

---