為何小表驅(qū)動(dòng)大表箱亿？

數(shù)據(jù)庫(kù)最傷神的是數(shù)據(jù)庫(kù)連接曹傀。

1.建立2次連接产场，每次進(jìn)行上百萬(wàn)的數(shù)據(jù)集的查詢

2.上百萬(wàn)次的連接每庆，每次進(jìn)行2個(gè)數(shù)據(jù)集的查詢

left join 的時(shí)間開(kāi)銷類似于笛卡爾積痢士，相當(dāng)費(fèi)時(shí)，如果關(guān)聯(lián)字段是索引字段鳞贷，可以減少時(shí)間復(fù)雜度履植，但是還是非常費(fèi)時(shí)。

left 的優(yōu)化：首先悄晃，mysql都是使用（Nested Loop ）循環(huán)套嵌的方式實(shí)現(xiàn)join，這里包括兩個(gè)部分：驅(qū)動(dòng)表結(jié)果集作為條件連接被驅(qū)動(dòng)表X凿滤，被驅(qū)動(dòng)表根據(jù)驅(qū)動(dòng)表結(jié)果查詢數(shù)據(jù)集Y妈橄。時(shí)間復(fù)雜度（X*Y），這里的第二部分是數(shù)據(jù)庫(kù)內(nèi)部的操作翁脆，涉及io眷蚓，cpu等的操作很少，而且可以使用索引優(yōu)化反番。第一部分是表的連接沙热，這里是需要時(shí)間的，時(shí)間復(fù)雜度罢缸，CPU篙贸，io操作等都耗費(fèi)比內(nèi)部操作更多的時(shí)間。所以枫疆，以少的實(shí)際結(jié)果集（where篩選后）驅(qū)動(dòng)大的結(jié)果集爵川，大的結(jié)果集使用索引，這種方式能夠最大層度的減少時(shí)間復(fù)雜度息楔。也就是永遠(yuǎn)使用小的結(jié)果集驅(qū)動(dòng)大的結(jié)果集寝贡。

這里規(guī)定join連接單次總用時(shí)為m1，被驅(qū)動(dòng)表一次查詢使用時(shí)間為m2;則總的查詢時(shí)間為：

X*m1+Y*m2;這里的m1大于m2則 X相對(duì)于Y越小值依，結(jié)果越小;

B平衡樹的索引結(jié)構(gòu)圃泡，三種索引的速度以及覆蓋范圍排序: 1覆蓋索引>= 2聚集索引>3非聚集索引。 1和2中大于的部分不是速度愿险，而是適用范圍颇蜡，1覆蓋索引能夠根據(jù)業(yè)務(wù)自定義，而2基本都是主鍵，適用性不強(qiáng)澡匪，但是覆蓋索引占用內(nèi)存比較大熔任，這個(gè)是一個(gè)限制條件。

索引總共分為三種唁情，聚集索引疑苔，非聚集索引，覆蓋索引

非聚集索引會(huì)先找到聚集索引的唯一主鍵甸鸟，然后根據(jù)聚集索引查找值惦费，例外的是覆蓋索引（多列索引）：查詢列在索引列中，不需要再到聚集索引中查找一遍抢韭。

沒(méi)有主鍵（聚集索引）的表加數(shù)據(jù)堆薪贫，數(shù)據(jù)堆是通過(guò)使用索引分配圖（IAM）頁(yè)來(lái)維護(hù)的。當(dāng)在數(shù)據(jù)堆上創(chuàng)建了非聚簇索引時(shí)刻恭，葉級(jí)中包含了指向數(shù)據(jù)頁(yè)的行標(biāo)識(shí)符瞧省。行標(biāo)識(shí)符指定記錄行的邏輯順序，由文件ID鳍贾、頁(yè)號(hào)和行ID組成

nested join

嵌套循環(huán)連接將驅(qū)動(dòng)表(外表)和被驅(qū)動(dòng)表(內(nèi)表)進(jìn)行join鞍匾，讀取外表的每一行，和內(nèi)表進(jìn)行比較操作骑科，數(shù)據(jù)庫(kù)一般將建有索引的表作為內(nèi)表橡淑。

通過(guò)偽代碼可以看到，執(zhí)行主要分三步：

選定驅(qū)動(dòng)表

選定另一張表為內(nèi)表

將驅(qū)動(dòng)表中每一行和內(nèi)表中的記錄逐一進(jìn)行匹配

hive

hive存儲(chǔ)基于hdfs咆爽，計(jì)算主要是基于mapreduce框架梁棠。

連接類型

map side join

如果join中有一張表較小，這種情況下斗埂，可以使用map join符糊，不需要進(jìn)行reduce操作。

select?/*+ mapjoin(b) */

a.key

, a.value

from?a

join?b

on?a.key?= b.key

如果join的表在join列上進(jìn)行了分桶蜜笤，一張表的桶數(shù)是其它表的倍數(shù)濒蒋，這種情況下，相關(guān)桶之間在map端進(jìn)行join操作把兔，稱為bucketized map-side join,通過(guò)如下參數(shù)開(kāi)啟

? -- 方法一

? set hive.optimize.bucketmapjoin = true;

map join執(zhí)行步驟：

本地工作：在本地機(jī)器讀入數(shù)據(jù)沪伙，在內(nèi)存中建立hash表，然后寫入本地磁盤并上傳至hdfs县好。最后將hash表寫入分布式緩存中

map任務(wù):將數(shù)據(jù)從分布式緩存中讀入內(nèi)存围橡，將表中數(shù)據(jù)逐一和hash表匹配。將匹配到數(shù)據(jù)進(jìn)行合并并寫入hdfs中

無(wú)reduce任務(wù)

common join(reduce side join)

若兩種表都較大在map端無(wú)法緩存進(jìn)內(nèi)存缕贡，此時(shí)只能在reduce端進(jìn)行join

如果多張表中用同一列進(jìn)行join操作翁授，那么hive會(huì)將其轉(zhuǎn)成一個(gè)map/redcuce job

謂詞下推(Predicate Pushdown)

原理

對(duì)于left join拣播，先給出如下定義:

保留行表:outer join中返回所有行的表，如left outer join中的左表收擦，right outer join中的右表

空供應(yīng)表：如果和主表沒(méi)有匹配上返回空值的表贮配，如left outer join中的左表，right outer join中左表

join過(guò)程中謂詞：寫在join過(guò)程中的過(guò)濾條件

join后謂詞：寫在where條件中的過(guò)濾條件

存在如下反向規(guī)則:

Join過(guò)程中謂詞不能推移到保留行表

join后謂詞不能推移到空供應(yīng)表

正向解釋下：join過(guò)程中的過(guò)濾條件可以推移到空供應(yīng)表上塞赂，where 過(guò)程中的條件可以推移到保留行表泪勒。

=