Steve's
0%

发表于
本文字数： 5k 阅读时长 ≈ 5 分钟

Bustub的查询

Binder - 产生AST，查询表示为BoundSelect
Planner - 产生query plan，树
Optimizer - 优化查询

EXPLAIN计划节点后的是输出架构

1
Projection { exprs=[#0.0, #0.1] } | (__mock_table_1.colA:INTEGER, __mock_table_1.colB:INTEGER)

产生两列，整数类型

Bustub使用iterator模型，每个executer实现Next函数，这个函数返回1.单个tuple 2.null标识没有更多的tuple。每个executer实现一个循环，在循环中调用子executer的Next来获得tuple并处理。
每个executer出了返回tuple还有RID作为tuple的标识符。

Task #1 - Access Method Executors

SeqScan

Hint: Make sure that you understand the difference between the pre-increment and post-increment operators when using the TableIterator object. You might get strange output if you confuse ++iter with iter++. (Check here for a quick refresher.)

实现扫描table需要用到TableIterator，可以用TableHeap::MakeIterator()来构造：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
void SeqScanExecutor::Init() {
  auto *catalog = exec_ctx_->GetCatalog();
  auto *table_info = catalog->GetTable(plan_->GetTableOid());
  auto &table_heap = table_info->table_;
  it_ = std::make_unique<TableIterator>(table_heap->MakeIterator());
}

auto SeqScanExecutor::Next(Tuple *tuple, RID *rid) -> bool {
  if (it_->IsEnd()) {
    return false;
  }
  while (true) {
    auto res = it_->GetTuple();
    ++(*it_);
    if (res.first.is_deleted_) {
      continue;
    }
    *tuple = res.second;
    *rid = res.second.GetRid();
    break;
  }
  return true;
}

Insert

Hint: See the Index Updates section below for further details about updating a table’s indexes.

在Insert中，可以使用TableHeap::InsertTuple，但是根据Hint，我们需要同时更新对应的TableIndex，一个table可能包括多个index
Insert的内容就从child_plan中获取

Update

Hint: To implement an update, first delete the affected tuple and then insert a new tuple. Do not use the TableHeap UpdateTupleInplaceUnsafe function unless you are implementing leaderboard optimizations for project 4.

Update需要先删除然后添加

  • 删除是GetTupleMeta后再Update，同时要删除Index
  • 添加同样要添加Index

Delete

delete是一半的Update，设置TupleMeta即可（也要删除Index）

IndexScan

Bustub中，select * from t1 order by v1;如果已经有对v1的索引，会直接优化成为IndexScan，在现在的实现中就是B+树的Scan，这里发现了之前留下的两个坑

  • IndexIterator的是一个trivial copy的类（直接保存了Page*而不是PageGuard），复制直接用了memcpy，但是复制后需要析构的对象释放了对应page的read lock，导致lock和unlock没有对应
  • BPlusTree::Remove的时候，如果只剩一个root节点，并且root节点为空，需要删除掉这个空节点，否则与Iterator配合使用时，无法正确判断Iterator是否到End（因为Page*并不是nullptr，!=tree.End()）

Task #2 - Aggregation & Join Executors

Task 2中需要实现Aggregation和Join

Aggregation

SimpleAggregationHashTable 维护一张 hashmap，键为 AggregateKey，值为 AggregateValue，均为 std::vector<Value>。key 代表 group by 的字段的数组，value 则是需要 aggregate 的字段的数组。在下层算子传来一个 tuple 时，将 tuple 的 group by 字段和 aggregate 字段分别提取出来，调用 InsertCombine() 将 group by 和 aggregate 的映射关系存入 SimpleAggregationHashTable。若当前 hashmap 中没有 group by 的记录，则创建初值；若已有记录，则按 aggregate 规则逐一更新所有的 aggregate 字段，例如取 max/min，求 sum 等等。例如下面这条 sql：

1
SELECT min(t.z), max(t.z), sum(t.z) FROM t GROUP BY t.x, t.y;

group by（AggregateKey）为 {t.x, t.y}，aggregate（AggregateValue）为 {t.z, t.z, t.z}。aggregate 规则为 {min, max, sum}。

在Next()中需要返回一个个完成聚合操作后的tuple，所以需要在Init时遍历完child_executer

1
2
3
4
5
6
7
8
9
10
EXPLAIN SELECT MIN(colB), colA FROM __mock_table_1 GROUP BY colA;
 === OPTIMIZER ===                     
 Projection { exprs=[#0.1, #0.0] } | (<unnamed>:INTEGER, __mock_table_1.colA:INTEGER)                     
   Agg { types=[min], aggregates=[#0.1], group_by=[#0.0] } | (__mock_table_1.colA:INTEGER, agg#0:INTEGER) 
     MockScan { table=__mock_table_1 } | (__mock_table_1.colA:INTEGER, __mock_table_1.colB:INTEGER) 

EXPLAIN SELECT colA, MIN(colB) FROM __mock_table_1 GROUP BY colA;
 === OPTIMIZER ===                                                                                          
 Agg { types=[min], aggregates=[#0.1], group_by=[#0.0] } | (__mock_table_1.colA:INTEGER, <unnamed>:INTEGER) 
   MockScan { table=__mock_table_1 } | (__mock_table_1.colA:INTEGER, __mock_table_1.colB:INTEGER)

Next的返回值中总是key在前边，aggregate value在后边

NestedLoopJoin

nlj中，在Init中取出来所有的right_tuples，然后在Next中匹配
需要注意在Next中怎么处理来保存当前的状态，类似于python generator

HashJoin

当join的条件都是相等时，可以使用hash table而不是两次遍历

Optimizing NestedLoopJoin to HashJoin

新增一个optimizer规则，这个可以从nlj_as_hash_join.cpp抄

1
select * from A inner join B where B.c1 == A.c2;

这句话中，LeftPlan是A的SeqScan，RightPlan是B的SeqScan
expression中左儿子是B.c1，右儿子是A.c2，根据TupleIdx区分，在转换的时候需要注意

Task #3 - Sort + Limit Executors and Top-N Optimization

Sort

sort按照多个关键词排序，这里有点绕多写了几行

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
std::sort(sorted_.begin(), sorted_.end(),
          [this](const decltype(sorted_)::value_type &lhs, const decltype(sorted_)::value_type &rhs) {
            const auto &l_key = lhs.first;
            const auto &r_key = rhs.first;
            BUSTUB_ASSERT(l_key.keys_.size() == r_key.keys_.size(), "key size not match");
            for (uint32_t i = 0; i < l_key.keys_.size(); i++) {
              const auto &l = l_key.keys_[i];
              const auto &r = r_key.keys_[i];
              auto t = this->plan_->order_bys_[i].first;
              bool less = l.CompareLessThan(r) == CmpBool::CmpTrue;
              bool greater = l.CompareGreaterThan(r) == CmpBool::CmpTrue;
              bool desc = t == OrderByType::DESC;
              bool asc = t == OrderByType::ASC || t == OrderByType::DEFAULT;
              if ((less && desc) || (greater && asc)) {
                return false;
              }
              if ((greater && desc) || (less && asc)) {
                return true;
              }
            }
            return true;
          });

TopN

用优先队列实现TopN，反转下比较函数

Optimization

之后补充

ADDITIONAL INFORMATION

这一个实验中的Additional Information中详细介绍了我们可以使用的工具

System Catalog

catalog用来维护数据库的元数据，GetTable() GetIndex()可以获得表和索引
catalog中保存了数据库中table和index的映射：一个table可以包含多个index

发表于
本文字数： 7k 阅读时长 ≈ 6 分钟

Task #1 - B+Tree Pages

实现三种Page

  • B+Tree Page 基类，记录了类型、尺寸
  • B+Tree Internal Page 内部节点，m个key，m+1个孩子指针(第一个key是空的来实现)
  • B+Tree Leaf Page 叶子节点，m个key，m个记录IDRID
    考虑每种Page需要实现的操作
  • Insert 插入key-value
  • Lowerbound 获得小于等于key的index
  • Lookup 寻找Key，内部节点和叶子节点的两个Lookup有着不同的语义
    • 叶子节点的Lookup使用Lowerbound找到第一个>=key的index，是为了找到对应的key
    • 内部节点使用Upperbound-1获得**最后一个<=key的**的index，因为对应的value子树中的所有值一定是>=key[Upperbound-1] && < key[Upperbound]的。比如[0,3,5,7]，Key=4在3的子树中，Key=3也在3的子树中
    • 考虑0和n的边界情况
  • Split 分割一半Key到另一个Page，内部节点的分割需要注意下
    实现两个小函数
  • Lowerbound 获得第一个>=key的index
  • Upperbound 获得第一个>key的index

Task #2a - B+Tree Insertion and Search for Single Values

实现插入和查找，查找比较简单，插入有几点需要注意

  • 内部节点什么时候分裂：要避免内部节点Size=1的情况（内部节点第一个key是空的，value是子指针），在我的实现中对内部节点分裂后再插入，如果新的内部节点Size<2，把原来内部节点的最后一个Key移过去
  • 分裂内部节点时：新的内部节点的第一个Key是要给父亲节点的

关于Lower bound和Upper bound

在做这个的过程中，想统一下Lower和Upper bound的实现，统一使用$[l,r)$左闭右开

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
INDEX_TEMPLATE_ARGUMENTS
auto B_PLUS_TREE_INTERNAL_PAGE_TYPE::Lowerbound(const KeyType &key, const KeyComparator &comparator) const -> int {
  auto n = GetSize();
  BUSTUB_ASSERT(n != 0, "lookup in empty node");
  int l = 1;  // ignore the first key
  int r = n;  // [l, r)
  while (l < r) {
    int m = (l + r) >> 1;
    auto res = comparator(key, array_[m].first);
    if (res > 0) {
      l = m + 1;
    } else {
      r = m;
    }
  }
  return l;
}

INDEX_TEMPLATE_ARGUMENTS
auto B_PLUS_TREE_INTERNAL_PAGE_TYPE::Upperbound(const KeyType &key, const KeyComparator &comparator) const -> int {
  auto n = GetSize();
  BUSTUB_ASSERT(n != 0, "lookup in empty node");
  int l = 0;  // ignore the first key
  int r = n;  // [l, r)
  while (l < r) {
    int m = (l + r) >> 1;
    auto res = comparator(key, array_[m].first);
    if (res >= 0) {
      l = m + 1;
    } else {
      r = m;
    }
  }
  return l;
}

两者唯一的区别就是当array_[m] == key时的处理方式

  • Upperbound中，找的是>key的index，所以l=m+1
  • Lowerbound中，找的是>=key的index，所以r=m

Task #2b - B+Tree Deletions

CMU 15445-2022 P2 B+Tree Insert/Delete - 知乎
删除这块有点麻烦，看一下书上是怎么写的
目标是删除Srinivasan 是上边链接中的(internal page borrow)
![[Pasted image 20230822224149.png]]

  1. 找到叶子节点，将Srinivasan删除后，叶子节点中只剩下一个key，少于最小大小
  2. 删除后，可以将Wu的叶子节点与左侧的合并，然后在第二层节点中删除掉指向已删除叶子结点的key（这里是Srinivasan）
  3. 在第二层节点中删除后，这个内部节点小于最小大小。首先看能不能与兄弟节点合并，但是兄弟节点已满。所以要与兄弟节点**重新分配(redistribute)**：将最右侧的Gold移过来
  4. 这时，第二层的右侧内部节点有两个pointer：一个是原来的指向Mozart的，另一个是Gold自带的，发现没有一个Key可以分割这两个pointer（分割这两个pointer的Key在父亲节点中(Mozart)，因为Mozart左侧小于Mozart，右侧大于Mozart)。这时分割第二层的两个内部结点的Key应该变成了Gold。
    删除完后变成了下图：Gold跑到了根节点，Mozart到了第二层中
    ![[Pasted image 20230822225530.png]]
    然后删除Singh和Wu，也是相同的方式，叶子节点从左侧借一个，然后更新父亲节点中的Key(leafpage borrow：不会改变internal page的大小，只需要叶子节点borrow然后更新internal page的key)
    ![[Pasted image 20230822230459.png]]
    在此之上删除Gold(internal page merge)：
  5. 叶子节点与右侧的Kim合并，合并后在内部节点中删掉对应的Key
  6. 内部节点小于最小大小，与左侧合并，合并的Key从内部结点的父亲来，这里是Gold
  7. 内部节点合并后在第一层里删掉原来的Gold，正好是根节点，根节点变过去
    ![[Pasted image 20230822231609.png]]
    在B+树中，可能会出现叶子节点中删除的Key仍然在内部节点中出现，如Gold
    ![[IMG_B5D15EFE7985-1.jpeg]]
    如果需要借，
  8. 叶子节点，借过来后更新父亲节点中的Key（最多借一个，因为删掉的就一个），return
  9. 内部节点，将兄弟节点偷走的Key放到父亲位置，父亲的Key和偷走的Value放过来(对应图中的2.1)，return
    如果需要合并，往左侧合并，在父亲节点中删掉指向原来右侧的Key
  10. 叶子结点，往左侧挪过去，在父亲节点中删掉，设置NextPageId，更新内部节点
  11. 内部结点，将父亲的Key和被合并的KV放到合并节点中(因为被合并的中间，最左侧只有一个Value，没有Key，相当于补了一个Key)，在父亲节点中删掉(对应图中的2.2)，更新内部节点

在实现中，内部结点的借 (Borrow)可以有一个简单的实现方式：

  1. 对于内部节点，因为有n个key和n+1个指针，所以第一个key是空的，但是我们在分裂的时候是把分裂点的key提到了父亲的key中(绿色)，我们可以把这个key保存在分裂节点的第一个key中（如下图）
    ![[20230824_145857316_iOS.png]]
  2. 当需要Borrow的时候，因为第一个隐藏的key就是父节点的key
    • 向左边借(offset=-1)，直接把最后一个插入到需要的节点的第一个位置，相当于把借来的value(橙色)和父节点的key(绿色)组成了新的kv
    • 向右边借(offset=1)，把右边节点的第一个节点插入到需要的节点的最后，相当于删掉了第二个key(实际有意义的第一个key)
    • 最后根据右边节点的第一个key更新父节点(offset=-1的橙色箭头)
      ![[20230824_145607089_iOS.png]]

Contention

一开始实现B+树操作的时候，都是用的Context从根到叶子拿上读锁，这样效果是很差的，也过不了contention test ，应该使用Crabing的方法：18-notes-indexconcurrency.pdf

Debug Deadlock

在改代码的过程中出现了./test/b_plus_tree_contention_test这个测试的deadlock，正好学习一下怎么debug deadlock
![[Pasted image 20230901201123.png]]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
(lldb) thread select 4
(lldb) bt
* thread #4, name = 'b_plus_tree_con', stop reason = signal SIGSTOP
  * frame #0: 0x00007f9a90f6cf37 libpthread.so.0`__GI___pthread_rwlock_wrlock at futex-internal.h:284:13
    frame #1: 0x00007f9a90f6cf21 libpthread.so.0`__GI___pthread_rwlock_wrlock at pthread_rwlock_common.c:830:14
    frame #2: 0x00007f9a90f6cdc0 libpthread.so.0`__GI___pthread_rwlock_wrlock(rwlock=0x000055e176bb2fa0) at pthread_rwlock_wrlock.c:27:16
    frame #3: 0x000055e174c2aa23 b_plus_tree_contention_test`std::__glibcxx_rwlock_wrlock(__rwlock=0x000055e176bb2fa0) at shared_mutex:73:3
    frame #4: 0x000055e174c2bea5 b_plus_tree_contention_test`std::__shared_mutex_pthread::lock(this=0x000055e176bb2fa0) at shared_mutex:186:19
    frame #5: 0x000055e174c2be85 b_plus_tree_contention_test`std::shared_mutex::lock(this=0x000055e176bb2fa0) at shared_mutex:412:27
(lldb) frame select 3
frame #3: 0x000055e174c2aa23 b_plus_tree_contention_test`std::__glibcxx_rwlock_wrlock(__rwlock=0x000055e176bb2fa0) at shared_mutex:73:3
   70  	  }
   71  	  _GLIBCXX_GTHRW(rwlock_rdlock)
   72  	  _GLIBCXX_GTHRW(rwlock_tryrdlock)
-> 73  	  _GLIBCXX_GTHRW(rwlock_wrlock)
   74  	  _GLIBCXX_GTHRW(rwlock_trywrlock)
   75  	  _GLIBCXX_GTHRW(rwlock_unlock)
   76  	# ifndef PTHREAD_RWLOCK_INITIALIZER
(lldb) frame variable
(pthread_rwlock_t *) __rwlock = 0x000055e176bb2fa0
(lldb) p *__rwlock
(pthread_rwlock_t) $1 = {
  __data = {
    __readers = 250
    __writers = 0
    __wrphase_futex = 2
    __writers_futex = 1
    __pad3 = 0
    __pad4 = 0
    __cur_writer = 0
    __shared = 0
    __rwelision = '\0'
    __pad1 = "\0\0\0\0\0\0"
    __pad2 = 0
    __flags = 0
  }
  __size = "\xfa\0\0\0\0\0\0\0\U00000002\0\0\0\U00000001\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0\0"
  __align = 250
}

可以看到有250个reader，这显然是不对的，应该是某些reader没有及时释放锁
原因是我的insert实现的是

  1. 拿从根节点到叶子节点的读锁
  2. 从叶子节点反向将一个个读锁换成写锁
    但是这样是有问题的:
  3. 一个线程可能拿着儿子节点的WLock，获取父节点的WLock
  4. 另一个线程在拿着父节点的RLock，试图获取儿子节点的RLock
    解决方式是Insert和Remove都需要从叶子节点开始拿WLock，首先将上一层锁住，所有的加锁顺序都是从上一层到下一层，不会出现循环等待的情况（无论是RLock还是WLock）
    因为Insert和Remove都是从下往上处理，下层节点处理完后就可以把锁释放掉了（因为还拿着上层的锁）

    Improved Lock Crabbing (Optimistic Lock Coupling): The problem with the basic lock crabbing algorithm is that transactions always acquire an exclusive lock on the root for every insert/delete operation. This greatly limits parallelism. Instead, we can assume that having to resize (i.e., split/merge nodes) is rare, and thus transactions can acquire shared locks down to the leaf nodes. Each transaction will assume that the path to the target leaf node is safe, and use S-locks and crabbing to reach it, and verify. If any node in the path is not safe, then do previous algorithm (i.e., acquire X-locks)

一种优化的方式是Insert/Remove从跟节点到叶子节点拿RLock，叶子节点拿WLock，如果需要Split/Merge/Borrow，再重新从跟节点拿下来WLock(Optimistic)

Iterator

Iterator是从左往右获得叶子节点的锁，然而当Merge或者Borrow时，可能会相反，造成deadlock

  • We do not test your iterator for thread-safe leaf scans. A correct implementation, however, would require the Leaf Page to throw a std::exception when it cannot acquire a latch on its sibling to avoid potential dead-locks.

但是事实上我们无法修改RLatch的实现(修改的page.h并不在gradescope提交文件中)

Deal with concurrent

  1. 任何的拿锁释放锁都是有道理的，不要为了实现功能随意的拿锁释放锁
  2. 涉及到多个锁，要考虑不同情况下的拿锁顺序，考虑死锁

遇到的问题

  1. 一开始的实现中，在LeafPage Remove时，将Lowerbound(key)到GetSize()依次向前移动，最后忘了清零array_[GetSize()]。而Lowerbound当给定的key大于所有key的时候会返回GetSize()，这样造成了问题：解决方法是拿到LowerBound结果后验证是否小于GetSize()——Commit
  2. 有两个MixTest1和InsertTest2死活过不去，发现原来是自己的MoveEndToHeadOf函数写错了，这个函数是Split后进行调整的，比如说Size=5的节点，Split再Insert可能会造成一个Size=4另一个Size=2，需要调整下

发表于
本文字数： 1.5k 阅读时长 ≈ 1 分钟

Task #1 - LRU-K Replacement Policy

实现一个LRU-K替换算法，如果用堆的话，在RecordAccess时需要先删除在插入$O(logn)$，所以先直接用$O(n)$暴力

When multiple frames have +inf backward k-distance, the replacer evicts the frame with the earliest overall timestamp (i.e., the frame whose least-recent recorded access is the overall least recent access, overall, out of all frames).

说明中当多个frame最后一次有+inf时，evict掉最早访问时间最早的(不是最近一次访问)

Task #2 - Buffer Pool Manager

  • NewPage(page_id_t* page_id)如果page在buffer中，直接返回该page。如果不在buffer中，分配一个AllocatePage()
  • FetchPage(page_id_t page_id) 如果该page已经存在buffer中，那么应该增加引用计数并且记录访问，如果不在buffer中那么分配一个并执行相同操作（我一开始理解成了如果在buffer中直接返回）
  • UnpinPage(page_id_t page_id, bool is_dirty)减少对应page的引用计数，设定is dirty
  • FlushPage(page_id_t page_id) FlushAllPages() Flush对应的Page
  • DeletePage(page_id_t page_id)在buffer中删除对应的page，归还给freelist

Task #3 - Read/Write Page Guards

类似于std::lock_guard，对page实现一个RAII的封装
实现对应的拷贝构造/赋值，析构函数
还有ReadPageGuard和WritePageGuard，调用对应的Latch就好concurrency - What is the difference between a lock and a latch in the context of concurrent access to a database? - Stack Overflow

Leaderboard

先记录下可能的思路，后续做完Project再来搞

  1. Buffer Manager一把大锁，没法做到并行的从磁盘读取，恰好读取/写入的时候延迟比较高，可以考虑每个frame(buffer slot)有单独的锁，在disk_manager read/write时放掉大锁（注意下不能先放掉大锁，会有race）
  2. (By ChatGPT)优先替换扫描线程访问的页面：由于 get 线程的工作负载是倾斜的，你可能希望在缓冲区管理器中保留那些更频繁地被访问的页面。因此，当需要替换页面时，你可以首先考虑那些由扫描线程访问的页面。——在LRUKNode中记录访问模式，第一遍从SCAN的Node中做LRU，找不到再去Get的Node中找
  3. LRU-K: 可以用Heap，但是替换后RecordAccess的操作就从$O(1)$变成了$O(logn)$，

Reading List

发表于 更新于
本文字数： 4.2k 阅读时长 ≈ 4 分钟

FaRM可以提供强可串行性的分布式事务、高性能、高可用性。关键是设计新的事务、复制与恢复协议以利用RDMA与non-volatile DRAM。

阅读全文 »

发表于 更新于
本文字数： 4.4k 阅读时长 ≈ 4 分钟

这是FAST22的一篇文章

阅读全文 »