hash join 读书笔记

hash join必须使用cbo（因此必须表分析）

NLJ：
根据连接键，把小表的每一行，和大笔的每一行做对比。 一般情况下会对大表连接键上建index。
成本计算：读小表的行+（小表的每一行×读取大表的行）

NLJ：

根据连接键，把小表的每一行，和大笔的每一行做对比。一般情况下会对大表连接键上建index。

成本计算：读小表的行+（小表的每一行×读取大表的行）

SMJ:
读取小表和大表读的行，根据连接键排序，然后根据排序后的数据集（小表的和大表的）合进行连接。
理想状态：2个表的排序操作都能在内存进行
常规情况：2阶段进行：
          1.sort run阶段：数据读取到内存，排序，写出到临时表空间。直到所有的row sourse完成排序。
          2.merge阶段：之前每次写到临时表空间的数据（即sort run）被重新读入到内存，进行merge。
成本计算：读取小表的行+写小表的run sort到temp表空间+
          读取大表的行+写大表的run sort到temp表空间+
          cpu对小表和大表的排序消耗

SMJ:

读取小表和大表读的行，根据连接键排序，然后根据排序后的数据集（小表的和大表的）合进行连接。

理想状态：2个表的排序操作都能在内存进行

常规情况：2阶段进行：

1.sort run阶段：数据读取到内存，排序，写出到临时表空间。直到所有的row sourse完成排序。

2.merge阶段：之前每次写到临时表空间的数据（即sort run）被重新读入到内存，进行merge。

成本计算：读取小表的行+写小表的run sort到temp表空间+

读取大表的行+写大表的run sort到temp表空间+

cpu对小表和大表的排序消耗

join连接中的并行机制：
能在NLJ和SMJ中使用。并发查询的执行计划是一个树形结构（DFO），每个树上的DFO节点是一个sql操作过程，并且能把该操作过程能指派到一个query slave进程中。

1 2	join连接中的并行机制：能在NLJ和SMJ中使用。并发查询的执行计划是一个树形结构（DFO），每个树上的DFO节点是一个sql操作过程，并且能把该操作过程能指派到一个query slave进程中。

Hash Join：
用在条件为等号的环境下，hash连接的效率要比SMJ和NLJ要高（如果索引的blevel比较高），且hash join不要求一定要有索引。
hash join的基本算法是在内存中建立hash table，小表叫做build input，理想状态下，build input在内存中；大表叫做probe input。
在实际的情况下，build input不一定能完全放在内存中，此时，和probe input一样，build input的溢出部分，会在磁盘上用hash函数分割成小的不连续的分区。
hash连接分2个阶段进行：
1.partitioning阶段：即在内存中存放build input，若放不下，则和probe input一样，在磁盘上利用hash函数将input分割成小的不连续的分区。
1.join阶段：在相同的键值上，将build input和probe input的分区进行一一配对，并且join。
以上的hash连接的算法也叫grace join。

hash算法的限制：该算法是假设hash之后连接值倾斜度（skew）不高，使得每个partition上保持大约相同数量的rows。但是事实上不可能保证每个partition有大约相同数量的rows。

hybrid hash join是在oracle 7.3之后应用的比较高效的hash算法，它是在grace join的基础上，尽量在内存在搭建build input。
但是由于不可能在每个partition中保证相同的rows，后来有出来一些技术如bit-vector filtering、role reversal和histograms。我们将在后面的章节讲到这些技术。
分区的数量，我们叫做fan-out。fan-out太多会导致partition较多，从而影响IO，但是如果fan-out太少又会造成数量较少的大partition，这些大partition无法放在hash内存中。因此选择一个合适的fan-out和partition 大小，是hash join调优的关键。

当partitioning之后，build input或者probe input如果在内存中无法放下，hash table的溢出部分将会做nested-loops hash join。
hash table是由部分（在内存内的）build input partition和所有的probe input连接构成。剩余的不在内存中的build input将通过迭代的方式继续获取，直到所有的build input被迭代完。

hash join 规则：
假设有2个表：
S = { 1, 1, 1, 3, 3, 4, 4, 4, 4, 5, 8, 8, 8, 8, 10 }
B = { 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 8, 9, 9, 9, 10, 10, 11}
首先会根据hash_area_size确定小表是否能做build table。如果build input不能完全的在内存中，那么build input就被会分区，分区的数量我们称为fan-out，
fan-out是由hash_area_size和cluster size决定的，cluster size是指分区中还没被写出到临时表空间的连续块的数量。
cluster size=db_block_size * hash_multiblock_io_count，hash_multiblock_io_count在oracle9i中是隐含参数
hash算法会把S和B表的连接列分成不连接的桶（bucket），桶也叫做分区（partition），hash算法是尽量的减少数据的倾斜度，使得数据尽量均匀的分布。

以上面的S表和B表为例，如果我们简单的假设hash算法是取余，则：
S的分区为:{0,1,3,4,5,8}
B的分区为:{0,1,2,3,8,9}
经过这样的分区之后，只需要相应的分区之间做join即可（也就是所谓的partition pairs），如果有一个分区为NULL的话，则相应的分区join即可忽略。即他们可以在0,1,3,8上做连接。
相应的如果我们用SMJ或者NLJ，在连接上的消耗要高很多。

当build input被读入hash area内存准备进行分区的时候，build input表中的唯一列值被作为连接键构建起来，即所谓的位图向量（bitmap vector）。
按照上面的例子，bitmap vector为：{1,3,4,8,10}。
bitmap vector用来决定在partitioning 阶段和大表（probe input）进行连接的时候，哪些行是需要的，哪些是不需要的，不需要的将被丢弃，这就是我们上面说的bit-vector filtering技术。
当对B表进行分区时，将每一个连接键上的值与位图向量相比较，如果不在其中，则将其记录丢弃。在我们这个例子中，B表中以下数据将被丢弃
这个例子中，B表中以下数据将被丢弃{0,0,2,2,2,2,2,2,9,9,9,9,9}。

当第一个S分区和B分区做完连接后，需要将第i个S分区和B分区读入内存中做连接，此时会根据分区的大小，自动的选择哪个做build input，哪个做probe input。这就是动态角色转换技术，即我们前面所说的role reversal。

Hash Join：

用在条件为等号的环境下，hash连接的效率要比SMJ和NLJ要高（如果索引的blevel比较高），且hash join不要求一定要有索引。

hash join的基本算法是在内存中建立hash table，小表叫做build input，理想状态下，build input在内存中；大表叫做probe input。

在实际的情况下，build input不一定能完全放在内存中，此时，和probe input一样，build input的溢出部分，会在磁盘上用hash函数分割成小的不连续的分区。

hash连接分2个阶段进行：

1.partitioning阶段：即在内存中存放build input，若放不下，则和probe input一样，在磁盘上利用hash函数将input分割成小的不连续的分区。

1.join阶段：在相同的键值上，将build input和probe input的分区进行一一配对，并且join。

以上的hash连接的算法也叫grace join。

hash算法的限制：该算法是假设hash之后连接值倾斜度（skew）不高，使得每个partition上保持大约相同数量的rows。但是事实上不可能保证每个partition有大约相同数量的rows。

hybrid hash join是在oracle 7.3之后应用的比较高效的hash算法，它是在grace join的基础上，尽量在内存在搭建build input。

但是由于不可能在每个partition中保证相同的rows，后来有出来一些技术如bit-vector filtering、role reversal和histograms。我们将在后面的章节讲到这些技术。

分区的数量，我们叫做fan-out。fan-out太多会导致partition较多，从而影响IO，但是如果fan-out太少又会造成数量较少的大partition，这些大partition无法放在hash内存中。因此选择一个合适的fan-out和partition 大小，是hash join调优的关键。

当partitioning之后，build input或者probe input如果在内存中无法放下，hash table的溢出部分将会做nested-loops hash join。

hash table是由部分（在内存内的）build input partition和所有的probe input连接构成。剩余的不在内存中的build input将通过迭代的方式继续获取，直到所有的build input被迭代完。

hash join 规则：

假设有2个表：

S = { 1, 1, 1, 3, 3, 4, 4, 4, 4, 5, 8, 8, 8, 8, 10 }

B = { 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 3, 8, 9, 9, 9, 10, 10, 11}

首先会根据hash_area_size确定小表是否能做build table。如果build input不能完全的在内存中，那么build input就被会分区，分区的数量我们称为fan-out，

fan-out是由hash_area_size和cluster size决定的，cluster size是指分区中还没被写出到临时表空间的连续块的数量。

cluster size=db_block_size * hash_multiblock_io_count，hash_multiblock_io_count在oracle9i中是隐含参数

hash算法会把S和B表的连接列分成不连接的桶（bucket），桶也叫做分区（partition），hash算法是尽量的减少数据的倾斜度，使得数据尽量均匀的分布。

以上面的S表和B表为例，如果我们简单的假设hash算法是取余，则：

S的分区为:{0,1,3,4,5,8}

B的分区为:{0,1,2,3,8,9}

经过这样的分区之后，只需要相应的分区之间做join即可（也就是所谓的partition pairs），如果有一个分区为NULL的话，则相应的分区join即可忽略。即他们可以在0,1,3,8上做连接。

相应的如果我们用SMJ或者NLJ，在连接上的消耗要高很多。

当build input被读入hash area内存准备进行分区的时候，build input表中的唯一列值被作为连接键构建起来，即所谓的位图向量（bitmap vector）。

按照上面的例子，bitmap vector为：{1,3,4,8,10}。

bitmap vector用来决定在partitioning 阶段和大表（probe input）进行连接的时候，哪些行是需要的，哪些是不需要的，不需要的将被丢弃，这就是我们上面说的bit-vector filtering技术。

当对B表进行分区时，将每一个连接键上的值与位图向量相比较，如果不在其中，则将其记录丢弃。在我们这个例子中，B表中以下数据将被丢弃

这个例子中，B表中以下数据将被丢弃{0,0,2,2,2,2,2,2,9,9,9,9,9}。

当第一个S分区和B分区做完连接后，需要将第i个S分区和B分区读入内存中做连接，此时会根据分区的大小，自动的选择哪个做build input，哪个做probe input。这就是动态角色转换技术，即我们前面所说的role reversal。

总体说来，hash算法为如下步骤（以下考虑的是hash area size不够大，需要写出到磁盘的情况）：
1.决定fanout的数量，即分区的数量。分区数量×cluster大小<=内存中能用的hash area比例×hash area size大小
2.读取S表，根据内部的hash算法（我们暂时称作hash_fun_1），将连接列上的值map到分区。在此步骤，还利用另一个hash函数（我们称作hash_fun_2）产生另一个hash值，和连接键一起存放。该值将在后续的构建hash table中用到。
3.为S表的独立的连接键形成的bitmap向量
4.根据partition的大小排序，使得尽量多（也就是尽量小的partition进入内存。这也就是之前要根据partition大小排序的原因）的分区放入内存来构建hash table。如果内存不够放下所有的parittion，则输出到temp segment上）。
5.利用之前的hash值，构建S表的hash table。
6.读取B表，根据位图向量过滤，如果通过hash算法后B的值与位图向量比较不在其中，则丢弃该行。
7.将过滤后B表的行，利用内部的hash_fun_1和连接键，形成partition。
8.如果B表的行能在内存中形成分区，就利用内部的hash_fun_2执行连接，并且形成合适的hash桶。
9.如果不能在内存中形成分区，则将S的分区、连接键、B表的剩余行写出到磁盘。
10.从磁盘中读取未处理的S表和B表的分区。利用内部hash_fun_2值，构建hash table，在构建时将使用动态角色转换技术。在第一次循环中，优化器将先使用小表做build input，大表做probe input，角色转换技术仅在第一次循环后使用。
11.如果probe input或者build input中（已经经过角色转换了）较小的那个还是不能放入到内存中，则将读取较小的那个build input到内存chunk中，并且循环的和probe input做hash 连接。这我们叫做nested hash loops join。

总体说来，hash算法为如下步骤（以下考虑的是hash area size不够大，需要写出到磁盘的情况）：

1.决定fanout的数量，即分区的数量。分区数量×cluster大小<=内存中能用的hash area比例×hash area size大小

2.读取S表，根据内部的hash算法（我们暂时称作hash_fun_1），将连接列上的值map到分区。在此步骤，还利用另一个hash函数（我们称作hash_fun_2）产生另一个hash值，和连接键一起存放。该值将在后续的构建hash table中用到。

3.为S表的独立的连接键形成的bitmap向量

4.根据partition的大小排序，使得尽量多（也就是尽量小的partition进入内存。这也就是之前要根据partition大小排序的原因）的分区放入内存来构建hash table。如果内存不够放下所有的parittion，则输出到temp segment上）。

5.利用之前的hash值，构建S表的hash table。

6.读取B表，根据位图向量过滤，如果通过hash算法后B的值与位图向量比较不在其中，则丢弃该行。

7.将过滤后B表的行，利用内部的hash_fun_1和连接键，形成partition。

8.如果B表的行能在内存中形成分区，就利用内部的hash_fun_2执行连接，并且形成合适的hash桶。

9.如果不能在内存中形成分区，则将S的分区、连接键、B表的剩余行写出到磁盘。

10.从磁盘中读取未处理的S表和B表的分区。利用内部hash_fun_2值，构建hash table，在构建时将使用动态角色转换技术。在第一次循环中，优化器将先使用小表做build input，大表做probe input，角色转换技术仅在第一次循环后使用。

11.如果probe input或者build input中（已经经过角色转换了）较小的那个还是不能放入到内存中，则将读取较小的那个build input到内存chunk中，并且循环的和probe input做hash 连接。这我们叫做nested hash loops join。

hash join的成本计算：
1.最简单的情况，hash area足够大能放下S表分区后的所有的build input：
cost（HJ）=read（S）+build hash table in memory（cpu）+read（B）+perform in memory join（cpu）
如果忽略cpu的成本，cost（HJ）无限接近于 read（s）+read（b）

2.当hash area（后面用M表示）不够大，不能容纳build input，S，它将会写出到磁盘。当然了，表B也会写出到磁盘：
total cost 无限接近于 cost（HJ循环1）+cost（HJ循环2）
其中cost（HJ循环1） 无限接近于 read（S）+read（B）+write（（S-M）+（B-B*M/S））
即上述2至9步。

由于HJ循环2使用了nested hash loops join，hash join的算法处理Si和Bi分区。当每个build input的chunk被读取时，probe input将被多次读。
因此cost（HJ循环2） 无限接近于 read（（S-M）+n×（B-B*M/S））
即上述10至11步。
n为进行nested hash loops join的次数，n一般在10以上，也就是需要构建的partition大于10倍的hash area。

hash join的成本计算：

1.最简单的情况，hash area足够大能放下S表分区后的所有的build input：

cost（HJ）=read（S）+build hash table in memory（cpu）+read（B）+perform in memory join（cpu）

如果忽略cpu的成本，cost（HJ）无限接近于 read（s）+read（b）

2.当hash area（后面用M表示）不够大，不能容纳build input，S，它将会写出到磁盘。当然了，表B也会写出到磁盘：

total cost 无限接近于 cost（HJ循环1）+cost（HJ循环2）

其中cost（HJ循环1）无限接近于 read（S）+read（B）+write（（S-M）+（B-B*M/S））

即上述2至9步。

由于HJ循环2使用了nested hash loops join，hash join的算法处理Si和Bi分区。当每个build input的chunk被读取时，probe input将被多次读。

因此cost（HJ循环2）无限接近于 read（（S-M）+n×（B-B*M/S））

即上述10至11步。

n为进行nested hash loops join的次数，n一般在10以上，也就是需要构建的partition大于10倍的hash area。

hash join 读书笔记

一条评论

回复 bamuta 取消回复

hash join 读书笔记

相关文章

031 study note-startup instance

NBU培训杂记

9i和10g的plan table

一条评论

回复 bamuta 取消回复