12.3
设关系$r_1(A,B,C),r_2(C,D,E)$有如下特性：$r_1$有$20000$个元组，$r_2$有$45000$个元组，一块中可容纳$25$个$r_1$元组或$30$个$r_2$元组。估计使用以下连接策略计算$r_1✕r_2$需要几次块传输和磁盘搜索：
分析：$r_1$需要$20000/25=800$个块，$r_2$需要$45000/30=1500$个块，
假设我们的内存有$M$页，当$M>800$时，两个关系都能放到内存里，下列所有的算法代价为：$ b_s + b_r$，大约需要$2300$个块存取。
下面考虑$M\leq800$的情况。
嵌套循环连接
答：当使用$r_1$作为外部连接时，
总共需要$20000*1500+800$即$30000800$次块存取
当使用$r_2$作为外部连接时，
总共需要$45000*800+1500$即$36001500$次块存取
块嵌套循环连接
答：当使用$r_1$作为外部连接时，
总共需要$\lceil \frac{800}{M-1} \rceil*1500+800$次块存取
当使用$r_2$作为外部连接时，
总共需要$\lceil \frac{1500}{M-1} \rceil*800+1500$次块存取
归并连接
答：算上排序的成本
$$
B_s=1500(2\lceil{log_{M-1}(\frac{1500}M)}\rceil+2)+800(2\lceil{log_{M-1}(\frac{800}M)}\rceil+2)
$$
此时总成本为$B_s+1500+800$次块存取；散列连接
答：假设结果不溢出。
由于$r_1$较小，我们使用$r_1$ 作为构建关系，使用$r_2$作为探测关系。
当$M> \frac{800}M$时，
可以使用递归分区，总共需要进行$3*(1500 + 800)= 6900$次块存取
当$M\leq\frac{800}M$时，
总共需要进行$2*(1500 + 800)⌈log_{M-1}(800)-1⌉+ 1500 + 800$次块存取。