CMU 15-445/645 Intro to Database Systems

课程学习总结。 课程内部要求的不要把solution直接放到网上，我这边就贴各种具体实现了，只是记录一些Project的关键想法和实现，另外再补充记录一些c++的知识。

Homework #1 SQL

数据库系统的接口。课程的第一个assignment是使用sqlite3，完成10个查询操作。

group by

any attribute that is not present in the group by clause may appear in the select clause only as an argument to an aggregate function. (Chapter 3.7)

Project #1 Buffer Pool Manager

cache从disk中读取的page，使用LRU的替换策略管理Buffer。对于Parallel BPM，可能有多个instance。

Task #1 LRU Replacer

使用双向链表和hashmap来实现lru，hashmap保存双向链表的迭代器，快速增删。 unpin操作，降低一个page的引用次数。buffer Pool中一个page的refrence count为0了，将这个page放入到Replace的frame中，Replacer调用unpin记录这个frame pin操作，标记这个page正在被使用。一个已经在Replacer的frame，在buffer pool中又被引用了，增加page的引用计数，从Replacer中移除这个frame

Task #2 Buffer Pool Manager Instance

使用free_list记录空闲的page，如果free_list为空了，再使用LRU策略淘汰page。

使用页表映射内存中frame_id -> disk的page_id frame_id_t，指的是buffer中的page pool的下标 page_id_t，指的是物理页号

Task #3 Parallel BPM

用page_id来决定映射到哪个instance。每个instance有自己的latch进行同步。

Project #2 Hash Index

数据库中表的索引（storage/index/extensible_hash_table_index）的实现，基于extensible Hash table，快速查找Key对应的page_id，只支持non-unique key。

Task #1 Page Layouts

实现桶的页结构时，在删除一个key value pair（a item）的时候，只把readable置0，认为当readableNum == 0时，一个bucket为空。当从一个桶中删除一个item，不改变Occupied，而设置Readable为false，形成一个“tombstone”。当桶中所有item都被标记为Occupied时，则认为桶是满的，这时候可以使用分裂操作，重新创建两个新的桶。避免的不必要的删除item操作。

Task #3 并发控制

整个hash table的一个大锁table_latch_，和每个桶的小锁page latch（从BPM中获得的raw_page中的锁）配合使用。

Project #4 Query Execution

从test/executor/executor_test.cpp出发，看看怎么使用plan来确定执行的？ 每个test构建一个plan，executionEngin完成具体的执行，executor_factory根据plan的类型创建executor， executor根据plan执行。

关于如何获取table的有关信息？ Catalog保存了table_oid到TableInfo的映射，tableInfo保存了一个tableheap对象，tableHeap保存了table的存储页位置信息，可用于开始获得iterator的起始位置

SeqScanExecutor的实现

增加成员table_info_、itr_，方便保存迭代信息 注意都要使用智能指针来防止内存泄漏 使用unique_ptr管理新创建的itr_，由于table_info是从catalog中获得的一个没有所有权的指针，不使用智能指针管理 另外当plan为nullptr的时候记得Next直接返回true src/catalog中有table_generator，里面生成的测试用table的 schema信息

InsertExecutor

插入tuple到table、更新index 学习table_generator中的FillTable来进行插入，先构造vector<Value>的tuple值，再构造tuple 更新index的时候，使用index提供的接口（insertEntry），接口内部使用的是之前写好的extensible_hash_table来完成的 在catalog_test的里面看使用index的方式

对于复合的insert executor，需要使用child_executor获取select的执行结果。编码时注意使用std::move来获取右值引用来初始化unique_ptr。

UpdateExecutor

更新index使用先根据Key Delete，再Insert，在相关测试中增加了index更新的检查，注意Index的创建，使用ParseSQL来确定index的类型（列名无关紧要，因为后面的key_attr会确定建立索引的列序号）

DeleteExecutor

在测试的时候发现ScanKey的时候发现写入时大小不匹配，因为extendible_hash_table_index的key大小为8，在generic_key.h中的SetFromKey的copy的时候，是根据tuple的大小决定复制的长度的，tuple的大小可能超过key

const Tuple index_key = Tuple(result_set[0]);

改为根据key_schema获取tuple的方式

const Tuple index_key = result_set[0].KeyFromTuple(table_info->schema_, *index_info->index_->GetKeySchema(), index_info->index_->GetKeyAttrs());

Nested Loop Join

如何构造tuple？发现column_value_expression中有很方便获取join有关schema的列值的接口（EvaluateJoin），重写ConstructTuple。

Hash Join

怎么根据多个key构建hash，参考aggregate_executor 在hash_join_plan中定义JoinKey和JoinValue，提前实例化，再在hash_join_executor中定义hash_table 在构建JoinKey的时候，由于 plan_->LeftJoinKeyExpression() 只能获取一个ColumnValueExpression，所以只能获得tuple的一个列，并不能获取多个属性的值， 虽然我的JoinKey设计的时候是支持多个属性进行散列的。

Aggregate

Group by的实现是多个key的hash表，对于没有group_by的聚集查询，输出结果只有一行（一个tuple），所以hash表中只有一个key 注意关联容器的迭代器失效的问题， hash表的映射是从group_by的列值映射到aggregation的value

Distinct

出现了heap_buffer_overflow，在MakeDistinctKey的时候,主要是column_index超出了schema的列数量，直接通过tuple->GetValue来获取 另外，修改seq_scan_executor，让返回的tuple符合outputSchema格式，同时注意rid的获取要在origin_tuple中获得

Concurrency Control

通过使用 two-phase lock 来实现lock_manager。 lock_manager中的lock_table记录每个rid对应的RequestQueue，每个Queue有自己的锁，让想要获取锁的事务在同一把锁上等待，配合condition_variable使用。

Deadlock prevention

wound wait: 老事务让当前拿着锁的事务rollback；新事务需等待锁

如何判断老事务？ 在transaction_manager的begin中，使用全局递增的next_txn_id来创建id，可以用这个来判断事务的新老, 老事务的id更小

如何让已经获取锁的年轻线程abort？ 拿着锁的、等待锁的年轻事务，都会被请求锁的老事务abort

当老事务请求锁的时候，检查请求队列中的所有事务，如果都比他年轻，则notify all，并将老事务的请求加到最前面，并清空其他在等待的request

在LockRequest中增加Transaction *txn成员，保存指针，便于找到已经获得锁的事务。 老事务在WoundWait过程中，将年轻事务的状态设置为ABORTED。在等待锁的年轻事务返回的时候，会检查自己的状态，抛出异常，最终释放自己所有的锁在transaction_manager的Abort中完成

Project #5 Concurrent Query Execution

四种隔离级别的区别

  • SERIALIZABLE: No phantoms, all reads repeatable, no dirty reads.
  • REPEATABLE READS: Phantoms may happen.
  • READ COMMITTED: Phantoms and unrepeatable reads may happen.
  • READ UNCOMMITTED: All of them may happen.

事务独立性被破坏：

  1. unrepeatable read: 一个事务的连续两个read操作获取的结果不一样
  2. phantom read: 事务read的结果和insert、delete操作顺序有关，只锁了当前存在的record，而没有锁index
  3. dirty read: read的结果与其他被回滚的事务有关

如何实现：

  • serializable read: 获取所有锁，包括index lock，strict two-phase lock
  • repeatable read: same as above, 但没有index lock ：本次试验默认行为，同时忽略index lock的管理
  • read commit: same as above, 但立即释放Shared lock：这个在读query中实现，获取到数据后，立即调用Unlock shared
  • read uncommitted: same as above，但不获取读锁：这个在lock manager中实现

事务ACID性质：

  • Atomicity: “all or nothing”
  • Consistency: “it looks correct to me”
  • Isolation: “as if alone”
  • Durability: “survive failures”

C++知识补充

Smart Pointer

容器中存放智能指针而非局部对象

std::vector<std::shared_ptr<BufferPoolManager>> instances_;

unique_ptr的get()方法返回被管理对象的指针，而不是释放所有权

右值引用

为了实现对象移动而不是拷贝，避免在某些情况下对象拷贝后就被立即销毁了，用于提升性能。

cpp primer Chapter 13.6 标准库容器、string和shared_ptr类既支持移动有支持拷贝。IO类和unique_ptr类只能移动。

// 只能使用std::move使用移动构造函数初始化left_executor_的成员，因为left_executor不支持拷贝
NestedLoopJoinExecutor::NestedLoopJoinExecutor(ExecutorContext *exec_ctx, const NestedLoopJoinPlanNode *plan, std::unique_ptr<AbstractExecutor> &&left_executor,std::unique_ptr<AbstractExecutor> &&right_executor)
    : AbstractExecutor(exec_ctx), plan_(plan), left_executor_(std::move(left_executor)), right_executor_(std::move(right_executor)) {}

为了支持移动操作，引入右值引用，右值引用只能绑定到一个即将被销毁的对象上。

标准库的std::move函数 方便构造函数确定使用那种类型的构造（移动构造还是复制构造）

vector

vector的reserve，预留空间，不改变size

type cast

强制类型转换

  • static_cast: 不去除常量性和易变性的类型转换

  • const_cast: 改变运算对象的底层const

    top-level const(顶层const): 指针本身是一个常量
    low-level const(底层const): 指针所指对象是一个常量

  • reinterpret_cast: 纯粹是一个编译时指令，指示编译器将 表达式 视为如同具有 新类型 类型一样处理。

  • dynamic_cast: 用于运行时类型识别，将基类的指针或引用安全地转换成派生类的指针或引用

template <typename KeyType, typename ValueType, typename KeyComparator>
HashTableDirectoryPage *HASH_TABLE_TYPE::FetchDirectoryPage() {
  return reinterpret_cast<HashTableDirectoryPage*>(buffer_pool_manager_->FetchPage(directory_page_id_)->GetData());
}

template <typename KeyType, typename ValueType, typename KeyComparator>
HASH_TABLE_BUCKET_TYPE *HASH_TABLE_TYPE::FetchBucketPage(page_id_t bucket_page_id) {
  return reinterpret_cast<HashTableBucketPage<KeyType, ValueType, KeyComparator> *>(buffer_pool_manager_->FetchPage(bucket_page_id)->GetData());
}

模板特例化

参考hash

cpp primer Chapter 16.5 定义函数模板特例化的过程中，我们本质上接管了编译器的工作...

可以使用类模板特例化的方式实现我们自己定义的类型的hash版本。

迭代器失效问题

cpp primer Chapter 9.3.6 list删除迭代器的时候，当前迭代器失效，不能在循环后置语句中++，最好不用循环的更改。 但是可以使用下面的方式，利用后缀++的性质

for (std::list<int>::iterator it = c.begin(); it != c.end();)
{
    if (*it % 2 == 0)
        c.erase(it++);
    else
        ++it;
}

或者获得erase的返回值

for (std::list<int>::iterator it = c.begin(); it != c.end();)
{
    if (*it % 2 == 0)
        it = c.erase(it);
    else
        ++it;
}

类前置声明

在transaction.h中发现了类的前置声明，而不是引用头文件，前置声明只能作为指针或引用，不能定义类的对象，自然也就不能调用对象中的方法了。

condition variable

std::condition_variable在锁上等待Predicate 满足

cv.wait(lock, predicate) 相当于：

while (!pred()) {
    wait(lock);
}

如果条件不满足，在锁上等待并释放锁，当收到notify之后，(通过竞争)获取锁，进行predicate判断。因此在调用wait前，lock应该是处于上锁状态的。 配合RAII风格的锁来使用：

{
    std::unique_lock<std::mutex> queue_lk(req_queue.mu_);
    //...
    req_queue.cv_.wait(queue_lk, [&]{
      return txn->GetState() == TransactionState::ABORTED ||
             req_queue.request_queue_.front().txn_id_ == txn->GetTransactionId();
    });
}

Lambda

cpp primer 10.3.2 [capture](parameters) -> return_type { body } 按值捕获：在lambda表示创建时进行拷贝，而不是调用的时候进行拷贝 引用捕获：必须保证在lambda执行时变量是存在的

可变lambda:对于按值捕获的变量，想要改变它 auto f = [v1] () mutable { return ++v1; }

promise

线程间同步，传递值（用future表示） promise<void> 在线程间对状态发信号 promise<int> 在线程间传递结果。