包含标签 CMU-Database 的文章

Advanced Database Systems: History of Databases

2023年5月21日
| 读书笔记
数据库的发展历史，从复杂模型：网络模型、层次模型，再到简单的关系模型最后胜出，关系模型不止是简单，而且提出了物理、逻辑解耦、高层级别API；所以从1970年代开始，数据库的基本模型，发展方向是定了；后面出现了各种对关系模型的补充，但是大多数只是重复发明，除了code in database，schema last是比较新颖的发明；在这几十年内，商业数据库一直是主导，IBM、Oracle、微软一直是领导者；直到2000年互联网的出现打破了这个局面，数据库面临大量的访问，需要购买大量商业数据库成本太贵，此时开源产品就是更好的选择；同时也出现了各种对关系模型，他们的扩展性、性能都非常好，但他们不支持SQL、不支持事务，十年之后再看这些数据库多多少少都有一些局限性，于是分布式的NewSQL出现，加上云厂商的对象存储，云上数据库也成为主流；现在数据库有很多细分市场，每个主题内都有好几个玩家，这些数据库在巩固自己领地的同时，又在不断扩展自己的能力；他们开始支持SQL，增加事务，从历史角度看，声明式语言、解耦、简单模型一直是有生命力的

阅读全文

bustub数据库

2023年3月20日
| 数据库
卡耐基梅隆的bustub数据库，实验课程；包括：LRU-k实现、可扩展的hash表、B+的的增删改查、B+树的并发控制、各种SQL算子的执行和优化，并发处理

阅读全文

Advanced Database Systems: Query Execution & Processing

2023年1月22日
| 读书笔记
这一部分是属于 执行引擎组件，由于现代系统从I/O变为CPU瓶颈，CPU的指令依赖、分支预测就阻塞了并行优化；MonetDB/X100就指出了火山模型、物化模型的问题，后使用了向量化/批模型来优化，为后续系统提供了方向。查询处理又包括：自顶向下vs字底向上；并行化包括：水平(exchange算子)、垂直、以及混合；worker的分配还包括单核单线程、单核pool；列存重建使用早期物化+SIP达到了早期物化的简单，同时兼具性能；主内存系统中二级索引和scan都有用，但需要综合考虑：选择性；硬件参数、数据布局、并发，优化器也需要配合重构整合；Oracle首创的混合行+列存储，又进一步提供了表达式替换(本质上是语法树子节点替换)

阅读全文

卡内基梅隆的数据库课程-2

2022年7月4日
| 读书笔记
卡内基梅隆的数据库课程，包括：查询执行，火山-物化-向量模型，访问方式，顺序-索引-多索引等，顺序访问的优化，表达式评估，并行VS分布式，调度模式，I/O并行化；查询优化架构、RBO、CBO、逻辑计划VS物理计划、关系代数的优化以及一些例子、复杂谓词的类型和选择性、采样、基于概率的选择性、多join查询的优化，动态规划、遗传优化等

阅读全文

卡内基梅隆的数据库课程-3

2022年7月4日
| 读书笔记
卡内基梅隆的数据库课程，包括：事务的定义和ACID，隔离性(并发场景下的交错执行)，RW、WR、WW冲突，可串行化、Conflict Serializability(交换、优先图)、View Serializability(NP完全问题)；lock VS latch，lock类型，锁管理器，2PL，S2PL，SS2PL；死锁检测(是否有环)，根据各种条件打破循环，死锁预防(基于时间戳分配)，锁粒度(层级锁，支持更高并发)，IS、IX、SIX锁； 时间戳排序并发控制，W-TS(X)、R-TS(X)，可恢复性；OCC，三个方面阶段：读/写、校验、写入，backward validation，forward validation；幻读，重新执行，谓词锁，索引锁，事务隔离级别，基于2PL方式的各种隔离级别；MVCC并发控制，TO、OCC、2PL，版本存储append-only、time-travel、delta-storage；垃圾收集：Tuple-level(Background Vacuuming vs. Cooperative Cleaning)、Transaction-level；索引管理，主索引管理，二级索引管理(Logical Pointers、Physical Pointers)、MVCC index；MVCC delete(Deleted Flag、Tombstone Tuple)

阅读全文

卡内基梅隆的数据库课程-4

2022年7月4日
| 读书笔记
卡内基梅隆的数据库课程，包括：失败的各种情况，各种存储类型，失败的分类；redo 和 undo；buffer pool 策略；steal、no-force；shadow paging，sqlite的shadow paging；WAL协议格式，物理日志，逻辑日志，checkpoint失败恢复算法ARIES：Write-Ahead Logging，Repeating History During Redo，Logging Changes During Undo；LSN Log Sequence Numbers；正常事务操作恢复，终止事务操作恢复；Fuzzy Checkpointing，活跃事务表，脏页表；Recovery Algorithm的三个阶段：Analysis、Redo、Undo，恢复算法的性能改进

阅读全文

卡内基梅隆的数据库课程-5

2022年7月4日
| 读书笔记
卡内基梅隆的数据库课程，包括：分布式数据库，并行vs分布式，分布式数据库架构，shared-everything、shared-memory、shared-disk、shared-nothing；同质化节点vs非同质化节点；数据的透明传输，单节点vs分布式节点；协调事务，hash分区，range分区；OLTP，非拜占庭环境，原子提交协议，2PC，3PC、paxos、raft、zab、viewstamped，2PC的优化，multi-paxos，2PC vs paxos；复制配置：主-副本、多主，k-safety，传播时机：continuous、on commit，主动 vs 被动；CAP理论联邦数据库；OLAP，星型模型vs雪花模型，push vs pull，查询计划片段 vs SQL重写，分布式join算法，云系统，组件分解：系统catalog、节点管理、query优化；统一的访问格式

阅读全文