CMU15445 Lecture 11 Joins Algorithms
时间
2022.02.27
为什么需要join
由于为消除table中信息的冗余，我们会采取normalize来使得数据库table的设计符合一定范式，但是之后需要使用join来重建原来的tuple
一般使用inner equijoin,inner equijoin连接两张表中key相同的tuple。其他join算法可以通过该算法调整得到
什么是multi-way?应该是多个表join
Join算法需要考虑
Output
Cost Analysis
相比与内存读取与cpu计算，磁盘I/O的时间数量级更大，所以使用磁盘I/O作为cost metric
用笛卡尔积加谓词筛选实现join非常低效
三种Join算法
nested loop join
outer table是指外循环表，inner table是指内循环表
nested loop join为什么差劲
simple nested loop join
block nested loop join
buffer少
更多的buffer
尽量多缓存内表，因为外表总是要被刷新，除非缓存能够完全放下外表？但是尽量缓存外表与内表是一样吧，不一样，这里M < N，并且不论多放外表还是内表，外表都是读M次，但是如果多放内表，可以减少读外表的次数,
index nested join
Sort-Merge Join
当两个表的join 属性都一样时，这时会退化为block nested join
？按照索引一般就是顺序，比如B+树的range 查找
Hash Join
两个步骤：
- build
构建hash - probe
点查询
布隆过滤器更快？hash table需要把bucket读进来，也就是O(1)hash之后还要O(n)遍历
这里指的是n个页一般需要消耗sqrt(N)个frame？这里假定了一个hash的桶的大小不能超buffer pool的大小，也就是B，限定一个桶的最大为B，可以使得一次就能够操作完一个桶。下面的fudge factor(容错因子)，考虑了需要更大表的情况，也就是ha是不均匀的情况，并且这里是 materialization的hash表，那么hash表的桶中存的就是tuple本身
这个1'''应该是要和1' 1'' 1'''都match吗
因为存在collision，所以可以做进一步partition
hash表的大小与数据库table一致，那么读table花了(M + N),把hash表写到disk花了(M + N),因为hash表的空间复杂度大概是O(n),n就是数据库table的大小
如果可以知道outer table的大小，甚至可以进一步优化hash join
对于olap型的数据处理，也就是数据量大，hash join一般优于sort join，但是对于两种情况sort join更优：
- non-uniform data指的是构建hash表时，碰撞厉害的数据？****
- query中还存在sort谓词
数据库一体机是针对应大数据环境下的海量数据分析存储而设计的高性能主机;集服务器、存储器、管理应用软件等于一体,整体性能预先调优,免去传统数据中心的...，我理解的是一个针对特定目的的软硬件定制机器