RookieDB

proj0

基于Java的关系型数据库项目 基于UCB CS186 课程，用Java 语言实现关系型数据库，加强面向对象编程能力与对数据库的理解 RookieDB CS186

概述

Tips :本文主要内容是解析RookieDB项目，并进行相关代码框架阐述，RookieDB 项目对于需要学习数据库领域的同学们来说是一个不可多得的基础底层项目，我们虽没有完整深入关系型数据库的整体开发，但给了我们一个很好的学习视角和途径，让我们更明白数据库的数据类型、索引、缓存、备份、恢复等关键技术节点。

课程资源

• 课程网站：https://cs186berkeley.net/
• 课程视频：https://www.bilibili.com/video/BV13a411c7Qo
• 课程作业：7 个 Project
  • Setup
  • SQL
  • B+ Trees
  • Joins and Query Optimization
  • Concurrency
  • Recovery
  • NoSQL

资源汇总

• https://csdiy.wiki/数据库系统/CS186/
• https://blog.csdn.net/hjw199666?type=blog
• https://zhuanlan.zhihu.com/p/504749706
• https://www.zhihu.com/answer/830026280
• https://zhuanlan.zhihu.com/p/553091835
• https://zhuanlan.zhihu.com/p/366093227
• https://blog.csdn.net/qq_43176812/article/details/124615756
• https://blog.csdn.net/qq_43176812/article/details/123229155

OneTab备份

https://csdiy.wiki/%E6%95%B0%E6%8D%AE%E5%BA%93%E7%B3%BB%E7%BB%9F/CS186/ | UCB CS186: Introduction to Database System - CS自学指南 https://cs186.gitbook.io/project/assignments/proj4/part-2-lockcontext-and-lockutil#task-3-lockcontext | Part 2: Multigranularity - CS186 Projects https://github.com/berkeley-cs186/sp23-rookiedb/blob/main/src/main/java/edu/berkeley/cs186/database/table/PageDirectory.java#L107 | sp23-rookiedb/src/main/java/edu/berkeley/cs186/database/table/PageDirectory.java at main · berkeley-cs186/sp23-rookiedb https://github.com/berkeley-cs186/sp23-rookiedb/blob/main/src/main/java/edu/berkeley/cs186/database/memory/Page.java#L188 | sp23-rookiedb/src/main/java/edu/berkeley/cs186/database/memory/Page.java at main · berkeley-cs186/sp23-rookiedb https://blog.csdn.net/xpy870663266/article/details/78163423 | 伯克利大学数据库作业实现SimpleDB_pyxiea的博客-CSDN博客 https://github.com/SimpleCodeJust4Fun/rookiedb-proj2-to-proj5/tree/main | SimpleCodeJust4Fun/rookiedb-proj2-to-proj5 https://zhuanlan.zhihu.com/p/504749706 | CS186 2022 spring 个人笔记 - 知乎 https://zhuanlan.zhihu.com/p/517891940 | CS186 projects - 知乎 https://www.zhihu.com/people/shou-zu-tai-ye/posts | 收租太爷 - 知乎 https://faustpromaxpx.github.io/2022/07/05/rookie-db/#Multigranularity | 如果我是DJ你会爱我吗 https://faustpromaxpx.github.io/2022/08/02/Database/#Concurrency | Remake | 数据库 | 狂奔的蜗牛 https://blog.csdn.net/qq_43176812/article/details/123229155 | 【cs186】Project3 Join and Query Optimization part1_0 & 1的博客-CSDN博客 https://blog.codesnake.space/archives/rookiedbproject02btrees | blog.codesnake.space https://blog.codesnake.space/archives/project02implementationdetails | Project_02_Implementation Details - CodeSnake的学习日志 - 空气越稀薄 风景越广阔 https://blog.csdn.net/qq_43176812/article/details/124615756 | (21条消息) 【cs186】Project3 Join and Query Optimization part2_cs186 project 3_0 & 1的博客-CSDN博客 https://dev.mysql.com/doc/refman/8.0/en/hash-joins.html | MySQL :: MySQL 8.0 Reference Manual :: 8.2.1.4 Hash Join Optimization https://xiaolincoding.com/mysql/log/how_update.html#%E4%B8%A4%E9%98%B6%E6%AE%B5%E6%8F%90%E4%BA%A4%E7%9A%84%E8%BF%87%E7%A8%8B%E6%98%AF%E6%80%8E%E6%A0%B7%E7%9A%84 | MySQL 日志：undo log、redo log、binlog 有什么用？ | 小林coding https://zhuanlan.zhihu.com/p/35040231#Grace%20Hash%20Join | 如何在分布式数据库中实现 Hash Join ? - 知乎 https://cn.greenplum.org/hashjoin-in-pggp/ | 全面解读PostgreSQL和Greenplum的Hash Join - Greenplum 中文社区 https://zhuanlan.zhihu.com/p/94065716 | zhuanlan.zhihu.com https://zhuanlan.zhihu.com/p/121301503 | 哈希连接（hash join)原理介绍 - 知乎

在学习这门课中用到的所有资源和作业实现都汇总在 PKUFlyingPig/CS186 - GitHub 中。

RookieDB Overview

RookieDB is a bare-bones database implementation which supports executing simple transactions in series. In the assignments of this class you will be adding support for B+ tree indices, efficient join algorithms, query optimization, multigranularity locking to allow concurrent execution of transactions, and database recovery.

RookieDB是一个光秃秃的数据库，支持串联执行简单的事务。在这门课的作业中，你将会使其支持B+树索引、高效的连接算法、查询优化、允许并发执行事务的多粒度锁，以及数据库恢复。

For convenience, the staff will be maintaining a read-only public repo here containing the project skeleton. When starting projects remember to work off of the private repos provided to you through GitHub Classroom rather than the public one.

为方便起见，工作人员将在这里维护一个包含项目骨架的只读公共仓库。当开始项目时，请记得使用通过GitHub教室提供给你的私人仓库而不是公共仓库。

As you will be working with this codebase for the rest of the semester, it is a good idea to get familiar with it. The code is located in the src/main/java/edu/berkeley/cs186/database directory, while the tests are located in the src/test/java/edu/berkeley/cs186/database directory. The following is a brief overview of each of the major sections of the codebase.

由于你将在本学期余下的时间里使用这个代码库，熟悉它是一个好主意。代码位于 src/main/java/edu/berkeley/cs186/database 目录中，而测试则位于 src/test/java/edu/berkeley/cs186/database<span> </span>目录中。下面是对代码库中每个主要部分的简要概述。

cli_命令行界面

The cli directory contains all the logic for the database’s command line interface. Running the main method of CommandLineInterface.java will create an instance of the database and create a simple text interface that you can send and review the results of queries in. The inner workings of this section are beyond the scope of the class (although you’re free to look around), you’ll just need to know how to run the Command Line Interface.

cli目录包含了数据库命令行界面的所有逻辑。运行CommandLineInterface.java的主方法将创建一个数据库的实例，并创建一个简单的文本界面，你可以在其中发送和审查查询结果。这一部分的内部工作超出了本类的范围（尽管你可以自由地查看），你只需要知道如何运行命令行界面。

parser_解析

The subdirectory cli/parser contains a lot of scary looking code! Don’t be intimidated, this is all automatically generated automatically from the file RookieParser.jjt in the root directory of the repo. The code here handles the logic to convert from user inputted queries (strings) into a tree of nodes representing the query (parse tree).

子目录cli/parser(解释器)包含了很多看起来很吓人的代码! 不要被吓到，这都是由 repo 根目录下的 RookieParser.jjt 文件自动生成的。这里的代码处理的是将用户输入的查询（字符串）转换成代表查询的节点树（解析树）的逻辑。

visitor_访问

The subdirectory cli/visitor contains classes that help traverse the trees created from the parser and create objects that the database can work with directly.

子目录cli/visitor(访问者)包含帮助遍历从解析器创建的树并创建数据库可以直接处理的对象的类。

common_公共目录

The common directory contains bits of useful code and general interfaces that are not limited to any one part of the codebase.

common(公共)目录包含了一些有用的代码和一般的接口，不限于代码库的任何一个部分。

concurrency_并发

The concurrency directory contains a skeleton for adding multigranularity locking to the database. You will be implementing this in Project 4.

concurrency（并发)目录包含一个骨架，用于向数据库添加多粒度锁。你将在项目4中实现这一点。

databox_数据盒

Our database has, like most DBMS’s, a type system distinct from that of the programming language used to implement the DBMS. (Our DBMS doesn’t quite provide SQL types either, but it’s modeled on a simplified version of SQL types).

像大多数DBMS一样，我们的数据库有一个与用于实现DBMS的编程语言不同的类型系统。(我们的DBMS也不提供完全的SQL类型，但它是以SQL类型的简化版本为模型的）。

The databox directory contains classes which represents values stored in a database, as well as their types. The various DataBox classes represent values of certain types, whereas the Type class represents types used in the database.

databox目录包含了代表存储在数据库中的值的类，以及它们的类型。各种DataBox类代表某些类型的值，而Type类代表数据库中使用的类型。

An example:

1
2
3
4
5

DataBox x = new IntDataBox(42); // The integer value '42'.
Type t = Type.intType();        // The type 'int'.
Type xsType = x.type();         // Get x's type, which is Type.intType().
int y = x.getInt();             // Get x's value: 42.
String s = x.getString();       // An exception is thrown, since x is not a string.

index_索引

The index directory contains a skeleton for implementing B+ tree indices. You will be implementing this in Project 2.

Index(索引)目录包含一个实现B+树索引的骨架。你将在项目2中实现它。

memory_内存

The memory directory contains classes for managing the loading of data into and out of memory (in other words, buffer management).

memory(内存)目录包含管理数据载入和流出内存的类（换句话说，缓冲区管理）。

The BufferFrame class represents a single buffer frame (page in the buffer pool) and supports pinning/unpinning and reading/writing to the buffer frame. All reads and writes require the frame be pinned (which is often done via the requireValidFrame method, which reloads data from disk if necessary, and then returns a pinned frame for the page).

BufferFrame类表示一个缓冲帧 (缓冲池中的页面)，并支持对缓冲帧的固定/取消固定和读/写。所有的读和写都需要固定帧(这通常是通过requireValidFrame方法完成的，该方法在必要时从磁盘重新加载数据，然后返回页面的固定帧)。**

The BufferManager interface is the public interface for the buffer manager of our DBMS.

The BufferManagerImpl class implements a buffer manager using a write-back buffer cache with configurable eviction policy . It is responsible for fetching pages (via the disk space manager) into buffer frames, and returns Page objects to allow for manipulation of data in memory.

BufferManager接口是我们DBMS的缓冲区管理器的公共接口。

BufferManagerImpl类使用带有可配置的提取策略的回写缓冲区缓存实现了缓冲区管理器。它负责将页面(通过磁盘空间管理器)获取到缓冲区帧中，并返回Page对象以允许对内存中的数据进行操作。

The Page class represents a single page. When data in the page is accessed or modified, it delegates reads/writes to the underlying buffer frame containing the page.

The EvictionPolicy interface defines a few methods that determine how the buffer manager evicts pages from memory when necessary. Implementations of these include the LRUEvictionPolicy (for LRU) and ClockEvictionPolicy (for clock).

Page类表示单个页面。当访问或修改页中的数据时，它将读/写委托给包含页的底层缓冲帧。

EvictionPolicy接口定义了一些方法，用于确定缓冲区管理器在必要时如何从内存中清除页。这些方法的实现包括LRUEvictionPolicy（用于LRU）和ClockEvictionPolicy（用于时钟）。

IO_输入输出流

The io directory contains classes for managing data on-disk (in other words, disk space management).

IO目录包含用于管理磁盘上数据的类(换句话说，磁盘空间管理)。

The DiskSpaceManager interface is the public interface for the disk space manager of our DBMS.

The DiskSpaceMangerImpl class is the implementation of the disk space manager, which maps groups of pages (partitions) to OS-level files, assigns each page a virtual page number, and loads/writes these pages from/to disk.

DiskSpaceManager接口是DBMS的磁盘空间管理器的公共接口。

DiskSpaceMangerImpl类是磁盘空间管理器的实现，它将页面组(分区)映射到操作系统级文件，为每个页面分配一个虚拟页码，并将这些页面从/写入磁盘。

query_查询

The query directory contains classes for managing and manipulating queries.

The various operator classes are query operators (pieces of a query), some of which you will be implementing in Project 3.

Query（查询）目录包含用于管理和操作查询的类。

各种操作符类都是查询操作符(查询的一部分)，其中一些将在项目3中实现。

The QueryPlan class represents a plan for executing a query (which we will be covering in more detail later in the semester). It currently executes the query as given (runs things in logical order, and performs joins in the order given), but you will be implementing a query optimizer in Project 3 to run the query in a more efficient manner.

QueryPlan类表示执行查询的计划(我们将在本学期晚些时候更详细地讨论)。它目前按照给定的顺序执行查询(按照逻辑顺序运行，并按照给定的顺序执行连接)，但是您将在Project 3中实现一个查询优化器，以更有效的方式运行查询。

recovery_恢复

The recovery directory contains a skeleton for implementing database recovery a la ARIES. You will be implementing this in Project 5.

Recovery（恢复）目录包含实现数据库恢复的框架。您将在项目5中实现它。

table_表

The table directory contains classes representing entire tables and records.

The Table class is, as the name suggests, a table in our database. See the comments at the top of this class for information on how table data is layed out on pages.

The Schema class represents the schema of a table (a list of column names and their types).

The Record class represents a record of a table (a single row). Records are made up of multiple DataBoxes (one for each column of the table it belongs to).

The RecordId class identifies a single record in a table.

The HeapFile interface is the interface for a heap file that the Table class uses to find pages to write data to.

The PageDirectory class is an implementation of HeapFile that uses a page directory.

Table（表）目录包含表示整个表和记录的类。

顾名思义，Table类是数据库中的一个表。有关表数据如何在页面上布局的信息，请参阅该类顶部的注释。

Schema类表示表的模式（表结构）(列名称及其类型的列表)。

Record类表示一个表(单行)的记录。记录由多个databox组成(它所属的表的每列对应一个databox)。

RecordId类标识表中的单个记录。

HeapFile接口是堆文件的接口，Table类使用堆文件查找要写入数据的页面。

PageDirectory类是使用页面目录的HeapFile的一个实现。

stats_统计数据

The table/stats directory contains classes for keeping track of statistics of a table. These are used to compare the costs of different query plans, when you implement query optimization in Project 4.

table/stats目录包含用于跟踪表统计信息的类。在项目4中实现查询优化时，这些参数用于比较不同查询计划的成本。

关键类

Transaction.java

The Transaction interface is the public interface of a transaction - it contains methods that users of the database use to query and manipulate data.

Transaction接口是事务的公共接口——它包含数据库用户用于查询和操作数据的方法。

This interface is partially implemented by the AbstractTransaction abstract class, and fully implemented in the Database.Transaction inner class.

该接口部分由AbstractTransaction抽象类实现，并在Database中完全实现。事务内部类。

TransactionContext.java

The TransactionContext interface is the internal interface of a transaction - it contains methods tied to the current transaction that internal methods (such as a table record fetch) may utilize.

TransactionContext接口是事务的内部接口——它包含绑定到当前事务的方法，内部方法(如表记录获取)可以利用这些方法。

The current running transaction’s transaction context is set at the beginning of a Database.Transaction call (and available through the static getCurrentTransaction method) and unset at the end of the call.

当前正在运行的事务的事务上下文设置在 **Database.Transaction**的开头。事务调用(并且可通过静态getCurrentTransaction方法获得)并在调用结束时取消设置。

This interface is partially implemented by the AbstractTransactionContext abstract class, and fully implemented in the Database.TransactionContext inner class.

该接口部分由AbstractTransactionContext抽象类实现，并在数据库中完全实现。TransactionContext内部类。

Database.java

The Database class represents the entire database. It is the public interface of our database - users of our database can use it like a Java library.

Database类表示整个数据库。它是我们数据库的公共接口——我们数据库的用户可以像使用Java库一样使用它。

All work is done in transactions, so to use the database, a user would start a transaction with Database#beginTransaction, then call some of Transaction’s numerous methods to perform selects, inserts, and updates.

所有的工作都是在事务中完成的，因此要使用数据库，用户需要使用databdatab# beginTransaction启动一个事务，然后调用transaction的许多方法中的一些来执行选择、插入和更新。

For example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

Database db = new Database("database-dir");
try (Transaction t1 = db.beginTransaction()) {
    Schema s = new Schema()
            .add("id", Type.intType())
            .add("firstName", Type.stringType(10))
            .add("lastName", Type.stringType(10));
    t1.createTable(s, "table1");
    t1.insert("table1", 1, "Jane", "Doe");
    t1.insert("table1", 2, "John", "Doe");
    t1.commit();
}
try (Transaction t2 = db.beginTransaction()) {
    // .query("table1") is how you run "SELECT * FROM table1"
    Iterator<Record> iter = t2.query("table1").execute();
    System.out.println(iter.next()); // prints [1, John, Doe]
    System.out.println(iter.next()); // prints [2, Jane, Doe]
    t2.commit();
}
db.close();

More complex queries can be found in src/test/java/edu/berkeley/cs186/database/TestDatabase.java

更复杂的查询可以在 src/test/java/edu/berkeley/cs186/database/TestDatabase.java 中找到。

For example:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

Database db = new Database("database-dir");
try (Transaction t1 = db.beginTransaction()) {
   Schema s = new Schema()
           .add("id", Type.intType())
           .add("firstName", Type.stringType(10))
           .add("lastName", Type.stringType(10));
   t1.createTable(s, "table1");
   t1.insert("table1", 1, "Jane", "Doe");
   t1.insert("table1", 2, "John", "Doe");
   t1.commit();
}
try (Transaction t2 = db.beginTransaction()) {
   // .query("table1") is how you run "SELECT * FROM table1"
   Iterator`<Record>` iter = t2.query("table1").execute();
   System.out.println(iter.next()); // prints [1, John, Doe]
   System.out.println(iter.next()); // prints [2, Jane, Doe]
   t2.commit();
}
db.close();

More complex queries can be found in src/test/java/edu/berkeley/cs186/database/TestDatabase.java

更复杂的查询可以在 src/test/java/edu/berkeley/cs186/database/TestDatabase.java 中找到。

proj1: 写SQL

略

proj2: B+树

• 实现B+ 树的索引结构（结点的新增、插入、删除、扫描），实现批量加载以优化建树开销

主要是理解基础概念，理解B+树的数据结构，操作中的一些考虑，性能开销等

prerequisite： 做实验之前先学习两个课件：diskfiles，B+Tree

Implementation Details 实现细节

• 注意：阅读index目录中的所有代码，例如 BPlusNode::put 说明了在split结点后如何重新分配entry，请多多阅读代码中的注释;
• 假设1: 我们的B+树实现不支持重复键.每当插入重复的密钥时,会引发异常
• 假设2: 我们对B+树的实现假定内部节点和叶节点可以在单个页上序列化.你不必支持跨多个页的结点;
• 假设3: 我们执行delete 不会 重新平衡树.因此,打破了阶数为 d 的B+树中所有非根叶子结点都包含在 d 和 2d 条目之间的不变性. 请注意,实际的B+树在删除后会"重新平衡",但是为了简单起见,我们将"不会"在此项目中实现重新平衡树.

Task1: fromBytes

leafNode在字节层面的存储方式：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

When we serialize a leaf node, we write:

a. the literal value 1 (1 byte) which indicates that this node is a
    leaf node,
b. the page id (8 bytes) of our right sibling (or -1 if we don't have
    a right sibling),
c. the number (4 bytes) of (key, rid) pairs this leaf node contains,
    and
d. the (key, rid) pairs themselves.

For example, the following bytes:

+----+-------------------------+-------------+----+-------------------------------+
| 01 | 00 00 00 00 00 00 00 04 | 00 00 00 01 | 03 | 00 00 00 00 00 00 00 03 00 01 |
+----+-------------------------+-------------+----+-------------------------------+
\__/ \_______________________/ \___________/ \__________________________________/
    a               b                   c                         d

represent a leaf node with sibling on page 4 and a single (key, rid)
pair with key 3 and page id (3, 1).

看懂了这个就能够实现fromBytes的反序列化代码了，注意buf的getInt、getLong等方法会自动把buf的开始移动到当前读完了的Bytes的正后方，所以要按nodeType、rightSibling、nums、（keys-rids）的顺序依次去get()、getLong、getInt、getKeySchema

目前存在疑问的地方：

• Optional <T>：

  • 介绍
    • Optional 类是一个可以为null的容器对象。如果值存在则isPresent()方法会返回true，调用get()方法会返回该对象。
    • Optional 是个容器：它可以保存类型T的值，或者仅仅保存null。Optional提供很多有用的方法，这样我们就不用显式进行空值检测。
    • Optional 类的引入很好的解决空指针异常(npe)。
  • 项目中用法
    • public Optional<Pair<DataBox, Long» put(DataBox key, RecordId rid)
    • Optional.of
      • put中

• Databox：

  • 数据模型，用作索引里的key，因为key可能是很多种类型的。int、long、string等
  • Comparable接口
    • Comparable是排序接口；若一个类实现了Comparable接口，就意味着“该类支持排序”。可以使用Arrays.sort()对改类进行排序

• RecordId:

  • (pageNum, entryNum) comprise a RecordId
  • A record in a table is uniquely identified by its page number (the number of the page on which it resides) and its entry number (the record’s index on the page). These two numbers (pageNum, entryNum) comprise a RecordId.

• Optional<Pair<DataBox, Long»

  • 这个是rookirDB项目已经定义好的put函数的返回类型
  • a pair (split_key, right_node_page_num) is returned where right_node_page_num is the page number of the newly created right node
  • 为什么要这么返回？

• Rids

• Page

• getPage

  • newSplitedRightNode.getPage().getPageNum()
  • 因为一个node的私有属性里只有Page，要想拿到页号码，需要调用Page对象的getPageNum方法

  • 1 2 3

    If this leaf is the rightmost leaf, then rightSibling is Optional.empty(). Otherwise, rightSibling is Optional.of(n) where n is the page number of this leaf's right sibling. private Optional<Long> rightSibling;

• iterators(Java)

b+树的反序列化：第一个字节表示结点类型（叶子/非叶子），之后8个字节表示右兄弟结点的pageid，后4个字节表示结点中的记录数，之后代表的都是所有记录

然后定义b+树的结点类，有叶子结点类和非叶子结点类

b+树结点的增删改查，d是b+树的阶（一个节点的子节点数量的最大值），结点的孩子大于d时就需要分裂了。保证平衡。

bulkload是第一次建树的流程，是先有一系列按索引顺序排好序的叶子结点，这样就可以直接构建双向链表，然后从下往上构建第一颗b+树，存在一个分裂指标的参数fillfactor，（3/4）时分裂新的非叶子结点。相比于一个一个插入，这样的好处是能够避免掉每次插入都要查询到插入位置的消耗。

proj3: Join与查询优化

• 实现多种Join 操作符（简单嵌套、排序归并、优雅哈希），并基于动态规划实现SQL优化

理解JOIN的过程，JOIN的本质，数据库系统的结构（执行器，解释器，优化器，引擎），SQL优化，执行计划等概念。编程上的细节其实不多。优化的本质（高效组织和利用计算机的软硬件资源），与计算机体系结构也息息相关。哈希的本质等。

in-memory join

• ChatGPT问答集合：
  • https://chat.openai.com/share/5cf2f81e-1d44-4ed9-ae60-018c9fe5432a

前置知识：

Block、Page、Row

块（Block）：数据库存储的最小单位，计算机磁盘上一组连续的扇区，

页（Page）：本来是操作系统和文件系统的一个概念（虚拟内存管理的最小单位）

行（Row）：数据库中的一条记录

Join

Simple Nested Loop Join

简单嵌套循环连接 Simple Nested Loop Join是最简单的一种连接实现算法，外层循环遍历a表，内层循环则遍历b表，如果满足连接条件，则组合两个表的列输出，最终生成连接后的临时表。 这种连接算法效率比较低下，其复杂度表示为： O(Ra * Rb)。

Block Nested-Loop Join（缓存块嵌套循环连接）

Block Nested-Loop Join 其优化思路是减少内层表的扫表次数，通过简单的嵌套循环查询的图，我们可以看到，左表的每一条记录都会对右表进行一次扫表，扫表的过程其实也就是从磁盘读取数据的过程，那么这个过程其实是比较消耗性能的。

只有left Block和right page

hash join

Hash Join Hash Join 是 Oracle、SQLServer 、PostgreSQL 中重要的关联算法，当两个表关联时，选择一张表按照 join 条件给的列构建 hash 表，然后将第二张表的每行记录去探测 hash 表中的数据，如果符合连接条件就输出该数据。前一张表我们叫做 build 表，后一张表我们的叫做 probe 表。为了减少内存使用量，通常选择小表作为 hash 表，大表作为 probe 表。

经典 Hash Join 主要有两个步骤：选择 hash 表，扫描该表并创建 hash 表；将另一个作为 probe 表，扫描每一行数据，然后在 hash 表中找寻对应的满足条件的记录。忽略内存和 CPU 时间，它的成本是：

Cost(HJ) = Read(M) + Read(N)

Hash Join 需要把表放到内存中，如果内存不够怎么办？为了处理这种情况，又诞生一些 Hash Join 的变种，比如 Grace Hash Join 。简单说是通过分区方式实现，根据关联字段将两个表的数据分区，然后对同一分区的数据再进行原生 Hash join 的 build 与 probe 过程，最后将所有分区的数据合并成最后的结果集。当然在实际中会更复杂，比如在大数据量的情况下，有概率出现不同数据的 HASH 值却是相同的问题。

总的来说，Hash Join 是处理大表间 Join 的不错选择。MySQL 在 8.0.18 前一直没有 Hash join 的实现，甚至在 5.5 以前只有最原始的 NLJ，5.5 后才有 NLJ 优化变种的 B（Block）NLJ。但 Oracle 早在 7.3 版本之后就引入了 Hash join 算法，在 OLAP 领域中 Hash join 更是绝对的标配，Greenplum 和 Spark SQL 就充分利用了它。但是它也有缺点，比如只能使用等值查询、需要更多的内存资源等。

Bulid Phase

选择一个表（一般情况下是较小的那个表，以减少建立哈希表的时间和空间），对其中每个元组上的连接属性（join attribute)采用哈希函数得到哈希值，从而建立一个哈希表。

Probe Phase

对另一个表，扫描它的每一行并计算连接属性的哈希值，与bulid phase建立的哈希表对比，若有落在同一个bucket的，如果满足连接谓词（predicate)则连接成新的表。

private Run joinedRecords; 这个东西居然是run

Grace hash join

这个方法适合用于内存不足的情况，核心在于分块处理

第一阶段分块阶段(Partition Phase)：把每个关系（relation）分别用同一个哈希函数h(x)在连接属性上进行分块（partition）。分块后每个元组分配到对应的bucket，然后分别把这些buckets写到磁盘当中。

第二阶段和普通的哈希连接类似，将分别来自于两个关系对应的bucket加载到内存中，为较小的那个bucket构建哈希表（注意，这里一定要用不同的哈希函数，因为数据很多的情况下不同值的哈希值可能相同，但不同值的两个哈希值都相同可能性非常小）

图来自于Database Management Systems, S. Chakravarthy 也有可能出现一个或多个bucket扔无法写入到内存的情况，这时可递归对每一个bucket采用该算法。与此同时这会增加很多时间，所以最好尽可能通过选择合理的哈希函数形成小的bucket来减少这种情况的发生。

当 build 表数据量比较大，无法在内存中全部存下的时候，我们需要利用磁盘来完成 join 操作。最直观的想法，就是分片加载 build 表。每加载一个 build 表的一个分片，然后从头到尾扫描一遍probe表，进行一次 probe 操作，完成 join 操作。这样做的问题是扫描磁盘的次数过多。总的扫描量是build表 + n * probe 表。n 是 build 表的分片个数。

Grace Hash Join 的方法是: 先对两个即将做 Hash Join 的表按照同一个 hash 函数分配到不同的分片中。然后再分别对不同的分片做 In-Memory Hash Join。这是典型的分治的思想。如果单个分片还是不能全部放到内存中，可以迭代的使用 Grace Hash Join 方法。

partition只是分

这里pass可以用作区分，使用不同的随机种子生成新的hash值

// 这里实际上选了左右中小于numbuffers-2的部分那个作为build（所以run里面的条件是or而不是and），另一个作为probe，于是问题回到了SHJ

为什么要用相同值的record塞满partitions？因为相同值的record会被add进同一个partitions的slot（hash得到的partitionNum相同），partitions[partitionNum].getNumPages()可以看出当前这个分区里数据页的数量（这个项目中设定一个数据页可以保存8个record），因此要想用最少的record让GHJ崩溃，就是要用值相同的record，如果用不同的record也可以，但是数量要更多。如果重复是33个record。不重复呢？无法验证，GCoverhead了，如何验证？

这是个概率问题，123456并不会老老实实地分到按顺序的partition去，而是完全随机的。所以只有值完全一样才能保证命中率

sort merge join

本质上就是写一个归并排序，排序还不用写，只用写归并 主要还是看如何用numBuffer去分任务吧，思想本身很简单，就是用有序查找来加快JOIN的速度

Query plan

query plan: 一串关系代数表达式，可以返回SQL查询需要的结果

query space： 对于一个查询的所有query plan的集合

Query Optimization ： 对于给定的查询，设计一个算法找出(近似)最优的查询策略(query plan)。

Query operator ：操作符，关系代数中的 （ project）， （select predicate），join，order by， group by…. 在的项目proj3中，每种操作符都是一个类。操作符本质是一个 Iterable <Record> .

即：操作符接受一个 Iterable <Record> ， 返回一个 Iterable <Record>作为下一个操作符的输入。

火山模型： This is the volcano model, where the operators are layered atop one another, and each operator requests tuples from the input operator(s) as it needs to generate its next output tuple. Note that each operator only fetches tuples from its input operator(s) as needed, rather than all at once!

1 Selectivity Estimation 选择性是是针对操作符而言的。

操作符的选择性有其自己的算法。这里不展开细说了。

算子选择问题

.2 Common Heuristics 查询优化算法是基于搜索，我们可以用一些启发式策略剪枝。 路径问题

.3 materialize ”物质化“就是把操作符的结果写回磁盘，这个操作符返回的迭代器就是磁盘中数据的迭代器。 比如之前我们学过的GHJ, SortOperator ，最终结果都会写回磁盘。 即把它写到一个临时文件中，这个过程会产生额外的I/O。当下一个运算符需要使用这个表时，我们必须再次将其从磁盘读入内存。如果不选择物质化，直接将一个运算符的输出流向下一个运算符，我们就不会将中间表写入磁盘。

.4 通过dp解决plan space search 我们需要解决的问题是找到IO 最少的plan，优化的核心在于找到连接plan中所有的表最少的IO，连接完所有的表后，group by ，project， order by等等依次加上即可。

我们采用动态规划算法，dp<set,QueryOperator> 表示把set中的表连接起来 代节最小的plan的 最后一次join操作符 （我们对最后一次join操作符调用 this.estimateIOCost()可以得到整个plan的IO cost）

这个dp本质是一个状压dp，所以最多用来处理十多个表的连接。

http://blog.itpub.net/30206145/viewspace-1651583/

理解prevMap，prevSet和result就可以了，

每一次的result就是当前代找到的最优边界，会作为下一代的prevMap

1
2
3
4

while (prevMap.size() != 1) {
    //看起来 size=1是终止条件，应该是越join，这个结果集合越小
    prevMap = minCostJoins(prevMap, pass1Map);
    }

优化手段

1. 物化临时表到内存中：上文提到被驱动表提前进行选择操作无优化作用的原因是每次都会重新提取一整张被驱动表。但如果在做完选择操作后，将该临时表物化到内存中，就可以让驱动表与该临时表进行join，大大减少要探索的记录数。
2. 选取更加高效的Join算法。
3. 只考虑使用左深树，即每次join的结果都作为左表，新加入的表作为右表。使得join操作可以流水线式操作，中途不需要将临时表物化进内存，减少物化带来的额外io开销。
   1. 左深树和右深树并不一定要理解为树的结果，其实更直接的理解是，将join的结果作为左表，存在内存中进行下一次join，那么我们就可以称这些表的顺序组成的树为左深树。

pass和run分别是什么？

可以调试运行对应的测试方法来查看方法中各个变量的含义

可以直接调试commandCli主程序来看SQL的执行流程、queryPlan的生成等

主流数据库的JOIN方法，对技术选型的意义？

以前 MySQL 的 join 算法只有 nested loop 这一种，在 MySQL8 中推出了一种新的算法 hash join，比 nested loop 更加高效。

• Oracle
• MySQL
  • MySQL 5.7:
  • MySQL 8.0: hash join PostgreSQL

Join流程

proj4: 实现多粒度锁以支持并发控制

• 实现基于三层多粒度锁（锁管理器、锁上下文、锁工具类）的并发控制，支持事务的隔离性

事务：需要保证原子性、隔离性、一致性和持久性的一个或多个数据库操作称之为一个事务。事务的本质其实只是一系列数据库操作，只不过这些数据库操作符合ACID 特性而已

InnoDB 引擎通过什么技术来保证事务ACID的？

• 持久性是通过 redo log （重做日志）来保证的；
• 原子性是通过 undo log（回滚日志） 来保证的；
• 隔离性是通过 MVCC（多版本并发控制） 或锁机制来保证的；
• 一致性则是通过持久性+原子性+隔离性来保证；

并发的目的是什么？提升DBMS的运行效率：

多粒度锁：行（记录、record）锁、表锁、全局锁（锁整个数据库）

全局锁

全库逻辑备份时锁住，整个数据库都是只读状态

表级锁

• 表锁
• 元数据锁（MDL）
• 意向锁

行级锁

innoDB才支持行级锁，MyISAM不支持

• 行锁/记录锁 Record Lock
  • S记录锁（共享锁），兼容新增S但不兼容新增X
  • X记录锁（独占锁），不兼容新增S和新增X
• 间隙锁 Gap Lock
  • 只锁定记录间的范围，不锁定记录本身
• 邻键锁 Next-Key Lock
  • 前两种的锁的一种组合

面试官: 解释下什么是死锁?

应聘者: 你录用我,我就告诉你

面试官: 你告诉我,我就录用你

应聘者: 你录用我,我就告诉你

面试官: 卧槽滚！

Part 1：锁队列

Task 1: LockType类型

定义锁的类型及锁间关系

父子关系（依赖），替代关系（包含），叠加关系（兼容）

Task 2: LockManager层

像是一个全局的锁管理器，管理全部的锁

1. acquireAndRelease：这个方法会原子性地获取一个锁并释放零个或多个锁。它具有对队列请求的优先级（即使有队列，它也会继续执行，如果不能立即执行，则会被放置在队列的前面）。
2. acquire：这个方法是标准的获取锁的方法。如果资源没有队列且锁请求与现有锁兼容，则将请求授予事务。否则，它会将请求放入队列（在队尾）并阻塞事务。不允许对已持有S锁的资源请求X锁，因为隐式锁升级是无效的。
3. release：这个方法是标准的释放锁的方法。它允许事务释放它持有的一个锁。在释放锁之后，将处理资源的队列，以授予等待请求的锁。
4. promote：这个方法允许事务显式地将持有的锁升级为同一资源上的更强的锁。该请求具有队列优先级，并将放置在队列的前面。不允许将锁升级为SIX锁，这样的请求应该通过 acquireAndRelease方法进行处理。因为在SIX锁升级时，我们可能需要释放冗余的锁，因此需要用 acquireAndRelease方法处理这些升级请求。
5. getLockType：这是查询LockManager的主要方式，它返回事务在特定资源上持有的锁的类型，该方法在之前的任务中已经实现。

Part 2：多粒度锁

Task 3: LockContext层

Task 4: LockUtIl层

Task 5: 两阶段锁

里面用的什么锁：Java的synchronized关键字，它基于更底层的互斥锁实现的。

做到的事情：支持了数据库开发人员对资源获取锁，getLock(S/X/IX)等，比如我要实现一个可重复读的隔离级别，或者对于单个的数据行get操作，需要保证其原子性，我就需要在这些操作中以synchronized关键字包住，并使用我实现的lockUtil里的对应方法，保证锁被拿到了，才去访问并操作资源

互斥锁和自旋锁：基础的操作系统层面锁的实现，互斥锁线程切换，自旋锁忙等待（占着CPU不放，因此需要被抢占）

锁管理器：对锁类型（LockType）进行基础的封装，维护一个锁的获取、释放、升级等的锁管理队列 锁上下文：用锁管理器，对不同级别的资源实现加锁，（database、table、page、record）资源之间是树形结构，注意保证父子结点间的锁关系（拿住一个父结点，就相当于锁定了子结点的意向，意向锁） 锁工具类：用锁上下文实现，给数据库的业务去用的，加锁时调用 LockUtil.ensureSufficientLockHeld(getTableContext(tableName), LockType.S);