包含标签 CMU-Database 的文章

Advanced Database Systems: History of Databases

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

阅读全文

bustub数据库

卡耐基梅隆的bustub数据库,实验课程;包括:LRU-k实现、可扩展的hash表、B+的的增删改查、B+树的并发控制、各种SQL算子的执行和优化,并发处理

阅读全文

Advanced Database Systems: Query Execution & Processing

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

阅读全文

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

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

阅读全文

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

卡内基梅隆的数据库课程,包括:事务的定义和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

卡内基梅隆的数据库课程,包括:失败的各种情况,各种存储类型,失败的分类;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

卡内基梅隆的数据库课程,包括:分布式数据库,并行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优化;统一的访问格式

阅读全文