返回学习路线

同一个连接答案怎样执行：DB-4完整账本 ​

先独立完成问题，再用下面的完整答案核对。目标是同时交出三份证据：查询没有改答案；任一时刻内存装得下；每一次读写都能说明来处。最后把页的修改接到一次崩溃恢复，而不是把“读到内存”“页已写回”“事务提交”混成一个时刻。

阅读入口 ​

核心七站：多重集语义理路多重集分组聚合Bag aggregation · Group-by aggregation · 分组聚合有限多重集的分组聚合用行重数计算 COUNT、SUM 与 AVG；完整连接算例和有限和恒等式说明如何保留连接键及 sum/count 状态，安全地把聚合提前执行。 → 页与内存账本理路数据库物理计划的页与内存账本Physical query cost model · Materialization cost · Query I/O accounting固定含重复键的数据、记录宽度和四帧预算，分开正确答案、可执行调度与代价估计，并核算物化和流水边界。 → 迭代器与流水线理路迭代器执行、阻塞与流水线Volcano iterator · Query pipeline · Pipeline breaker · Iterator execution用open/next/close契约跟踪行出现次数、暂停状态和页引用，解释过滤可流水而排序、hash build会形成阶段边界。 → 分块嵌套循环理路分块嵌套循环连接Block nested-loop join · BNLJ · Nested-loop join按有限外块重扫内表，证明每份匹配恰好输出一次，并展示重复键与页数取整如何改变成本和外侧选择。 → 分区hash理路分区哈希连接与倾斜退路Grace hash join · Partitioned hash join · Hash join以同键同分区和完整重复链证明bag正确性，精确计算分区尾页、哈希内存开销与热键无法递归拆散的边界。 → 排序归并理路排序归并连接与重复键组Sort-merge join · Merge join · Duplicate-key join groups先有序再按同键组作笛卡尔配对，给出四帧实现、重复组溢写退路和线性扫描成本的准确适用条件。 → 相关列估计理路查询基数估计与相关列Cardinality estimation · Predicate selectivity · Correlated predicates · Join cardinality estimation从精确频数恒等式区分均匀、包含与独立假设，用同一重复数据和内存阈值反例追踪估计错误。。

按需补课：不熟页单位时读外存模型理路外存 / I/O 模型External-memory model · I/O model · Aggarwal–Vitter model只计大小为 B 的数据块在容量为 M 的内存与外存之间传输次数的两层存储模型。；不明白可变记录如何定位时读槽页理路数据库记录与槽页Slotted page · Slot directory · 数据库槽目录用页内槽目录稳定定位可移动记录，逐字节核算插入、删除、压缩与记录扩长的空间和标识边界。；算不清列投影宽度时读行列布局理路行存、列存与延迟取列Row store · Column store · NSM · DSM · Late materialization通过同一八行四列数据核算行列布局的扫描和重建成本，区分逻辑行对应、压缩与物理读取单位。；不懂run和归并帧分配时读外存排序理路外存排序External-memory sorting在 I/O 模型中以块传输而非 CPU 比较次数衡量海量排序。；用索引却漏了堆访问时读B+树覆盖与回表理路B+ 树B+ tree · B-plus tree将全部记录保存在等深叶层、以内部路由键和叶链同时支持单键与范围访问的多路搜索树。。

持久化小支线：槽页 → pin、latch与dirty理路数据库缓冲池：pin、latch与脏页Database buffer pool · Pin count · Page latch · Dirty page把页的驻留资格、短期结构保护和持久化状态分开，给出不会提前复用帧或越过WAL的完整刷新轨迹。 → steal/no-force理路Steal/No-force 缓冲管理Steal/no-force buffer management · Steal and no-force policies以未提交页能否提前写回和提交页是否必须立即写回两条独立轴，推导恢复所需的 UNDO 与 REDO 能力。 → WAL理路预写日志Write-ahead logging · WAL规定数据页落盘与提交确认前必须先持久化相应日志，使崩溃后的撤销和重做拥有可靠依据。，之后接已有稳定日志到第二次重启。

进阶分支：连接顺序DP理路连接顺序动态规划与物理属性Join order dynamic programming · Selinger optimization · Interesting orders明确搜索空间、子集状态与成本充分性，完整填三表连接表，并用有序子计划反例说明何时不能每子集只留一个方案。回答如何搜索；LSM理路LSM树：有序段、压实与读路径Log-structured merge tree · LSM tree · SSTable compaction · Memtable以带序号更新实现字典，完整追踪memtable、不可变有序段、tombstone、Bloom过滤和安全发布压实结果的条件。与Bloom理路Bloom FilterBloom filter用多个哈希位置共享位数组实现无假阴性的插入式近似成员查询，并允许可控假阳性。回答另一种物理读写路径。已有查询语义到连接规模继续研究集合AGM与WCOJ，这里不替换其证明。

入口自测：两份同值行与三份匹配行，bag内连接有几份？128B页装64B记录，一页几条？答案是6份、2条。若把第一题回答为1，先读bag定义；若第二题忘了预留字段和元数据，先读本任务的资源合同。

固定输入与成本合同 ​

R(k,v,x,y)按原页为：

1. (1,A,1,1)，(2,B,1,1)
2. (1,A,1,1)，(3,C,0,0)
3. (2,D,1,1)，(4,E,0,0)

S(k,w)按原页为：

1. (2,u)，(1,v)
2. (2,u)，(3,w)
3. (1,x)，(5,y)
4. (4,z)，(2,t)

查询按k内连接，输出(k,v,w)。x,y只用于后面的筛选实验。无NULL、DISTINCT、并发更新或输出排序要求。

每页有效载荷128B；输入使用64B固定槽，含元数据和可供hash链使用的预留指针。输出使用128B槽，等价于本教学实现为一对输入记录预留的固定物化空间，未用字节也占槽；所以一页一份输出。这是共同记录格式，不是最紧凑编码或真实系统典型宽度。若改用更窄输出，应对三个计划一起重算，不能只改其中一个。

每阶段至多4个数据帧，另有64B固定控制区：例如两个8B桶头，六个4B有界游标/计数索引，以及24B标志或临时标量。它只为本例小规模设计；一般表规模、桶数和游标数必须重新核算。排序原位处理帧，写已有帧不另借第五帧。每个计划冷启动、输入已落盘、临时文件不跨计划复用；一次整页读或写计1，CPU、设备随机/顺序差、日志与元数据I/O另计。

题目 ​

1. 给完整输出bag，区分不同值种数和出现份数。分别写出三个算法为什么每份出现对只输出一次
2. 用R作BNLJ外侧，列每块产生的输出数、输入读数和峰值帧数；再换方向，判断“外表总选页少的”是否成立
3. 用k mod 2作Grace分区，列四个文件内容与页数。核对3(P+Q)能否直接使用，画每阶段帧分配
4. 先分别排序并物化R、S，再归并。列run成本、每个同键组大小和输出数；说明R重复组为何能装入两游标与输出之外仅剩的一帧。若同键组扩大到100条，给正确退路
5. 计算x=1 AND y=1的独立估计与真实基数，并计算原join的均匀NDV估计。指出本小例能否单凭筛选误差证明BNLJ扫描轮数变化
6. 用P=7、pageLSN=10、flushedLSN=10起步，T更新为9、日志40、commit50。给pin/latch/dirty轨迹，以及未稳定commit但页已写、稳定commit但页未写两种重启答案
7. 进阶：加T(k)={(1),(2)}，按逐记录比较次数而非I/O计费，填左深顺序DP；再解释一个较贵有序子计划为何可能不能丢掉

完整答案：bag与三种执行 ​

共同结果与证明接口 ​

输出(k,v,w)	重数
(1,A,v)	2
(1,A,x)	2
(2,B,u)	2
(2,B,t)	1
(2,D,u)	2
(2,D,t)	1
(3,C,w)	1
(4,E,z)	1

八种值、12份输出。按键复核2×2+2×3+1×1+1×1=12。出现对证明不依赖值彼此不同：BNLJ为每份R唯一外块配对所有S；hash让每份出现唯一入分区，同键不分离，并在桶内保留完整列表；SMJ为每个同键组枚举完整笛卡尔积。三者各自不漏、不多一份，故输出bag相等。算法内部输出次序可以不同。

BNLJ ​

R前两页组成四记录外块，产生键1的4份、B/键2的3份、键3的1份，共8。R最后一页外块产生D/键2的3份、键4的1份，共4。读R3页、S两轮8页，输入读11；2帧外块+1帧S+1帧输出=4。输出再写12页，总23。

以S外侧则4页分两块，各读R3页，输入4+2×3=10，总22。差异来自向上取整，较小外表经验不是本例精确最优规则。F=3时R外侧读15，F=5能完整保存R而只读7，展示内存台阶。

Grace hash ​

• R奇：(1,A),(1,A),(3,C)，3条占2页
• R偶：(2,B),(2,D),(4,E)，3条占2页
• S奇：(1,v),(3,w),(1,x),(5,y)，4条占2页
• S偶：(2,u),(2,u),(4,z),(2,t)，4条占2页

先用1输入+2分区输出帧，读7写8。再每轮用2帧R分区表示+1帧S+1帧输出，读四文件共8页。成本7+8+8=23，加输出12为35。原始R3页被拆成两个半空尾页的文件，共4页，故3×7=21漏掉2次临时I/O。hash桶碰撞还要比较原键；同键过热时改用组内BNLJ，而不能无限递归相同键。

Sort-merge ​

排序阶段R读3写3，S读4写4，各自一次形成一个run，共14。归并阶段R键1,1,2,2,3,4；S键1,1,2,2,2,3,4,5。R最大重复组2条=1帧；两游标+R组+输出=4帧。产生4、6、1、1份输出，共12。这个具体输入两侧7页都被读取，归并读7；输入/临时合21，输出后33。

一般归并P+Q是上界，某侧先耗尽时可以跳过另一侧尾页；这里k4匹配位于S最后页，所以读尽。若R组100条装不下，先物化同键组并释放游标帧，再组内BNLJ，计临时写读及恢复边界页；不能继续宣称7页线性账本。

完整答案：估计、恢复与进阶 ​

两类统计误差 ​

x和y各为1的概率2/3，独立预测6×4/9=8/3条，实际4。真实P(y=1|x=1)=1。过滤前join的NDV近似是6×8/max(4,5)=9.6，真实12。过滤后真实join10，若用8/3行、过滤后NDV2与S的NDV5预测，则得64/15。

按2条/页，ceil((8/3)/2)=2，ceil(4/2)=2，本例筛选误差没有改变BNLJ页数与轮数。另取100行、10行x=y=1，独立估计1而真实10；2帧build只能装4条，就会把“能内存处理”预测成错误。完整spill成本仍须知道probe及分区，不能由这两个行数单独推断。

从驻留到稳定 ​

fetch P使pin=1；X-latch下追加日志40、改P=9/pageLSN40、dirty=true，再释放latch，pin仍1所以不可替换。unpin到0后仅获得候选资格。教学刷新者取内部pin及X-latch，冻结同一版本，先确认flushedLSN≥40，再稳定写P，成功才清dirty，最后释放latch/pin。任一步失败保留dirty或错误状态，不能报告帧已安全复用。

若commit50尚未稳定就崩溃，磁盘P可能9，但T为loser，原位undo还原7。另一次独立运行若commit50已稳定且已确认，磁盘仍7，恢复redo至9。崩溃丢失pin/latch不能改变winner/loser。先读LSN40、后让页变60、再写60却只刷到40的刷新顺序违法，必须冻结或重查同一版本。

三表DP ​

T只保留键1、2各一份，RS=12、RT=4、ST=5、RST=10。逐记录比较成本为：先RS再T，48+24=72；先RT再S，12+32=44；先ST再R，16+30=46。最小44，但这不是44次I/O。

每子集只保留一个最便宜方案，需要未来只依赖该子集所声明属性。无序子计划10、后续排序100；已有序子计划13、后续0，此时13优于110。需分别保留interesting order状态。左深DP也未穷尽bushy树，搜索空间限制要写在“最优”前面。

延伸核对 ​

外排旧页的九页四帧账本是36；最终趟直接交给聚合则外排27，相比完整排序再扫描的45省18，摘要输出另计。bag旧页六行外部分区聚合输入/临时11、输出2，合13；每组(n,s)只保存一份状态。B+树旧页的覆盖/回表例是4个索引页加0、4或6个堆页，辅助可见性缺页另计。

LSM的A={(a,1,10),(b,2,20)}与B={(a,3,11),(b,4,DEL),(c,5,30)}完整压实，在无历史快照且没有外部更旧覆盖版本时，得到a=11、c=30。不能只压实B就删DEL；Bloom也必须包含墓碑键。新段先稳定，manifest按崩溃原子发布合同切换，再回收旧文件；崩溃前后必须能选完整旧/新版本。

可下载DB-4复算程序，运行Python标准库即可得到bag、三计划I/O、估计、DP和故障断言。程序只验证列出的有限模型与样本，不能替代正文不变量证明，也不模拟真实设备、事务并发或任意SQL。

参考入口 ​

算法来源与模型条件按各知识页的参考资料读取：CMU15-445/645 Fall2025存储、缓冲池、排序聚合、连接和优化讲义；System R、Volcano、LSM与ARIES原论文。DB-4记录格式、数据、调度和数字是本任务自行定义与复算的教学实例，不是某产品实测。