一、傳統(tǒng) join 算法

lookupJoin 是 join 查詢的一種，傳統(tǒng) join 算法為：

1. ?遍歷?A 表，讀取一條數(shù)據(jù) r

2.? 遍歷 B 表，對于每條數(shù)據(jù)，與 r 進行 join 操作

3. ?重復(fù) 1、2 操作，直到 A 表遍歷完所有數(shù)據(jù)

二、lookupJoin

現(xiàn)有的 lookupJoin 流程為：

1. ?遍歷 A 表，讀取一條數(shù)據(jù) r

2. ?通過 join key 以及數(shù)據(jù) r 構(gòu)造 B 表數(shù)據(jù)取值范圍

3. ?通過構(gòu)造的取值范圍對 B 表進行讀取操作，將讀取出的數(shù)據(jù)與 r 進行 join 操作，返回結(jié)果

通過這樣的做法，join 可減少對 B 表全表掃描的操作，提升執(zhí)行效率。但是執(zhí)行 lookupJoin 操作的前提是在 B 表中存在 join key 的索引，否則無法對 B 表構(gòu)造取值范圍。

三、分布式 lookupJoin

1. ?分布式 lookupJoin 介紹：

以往 KaiwuDB 集群在執(zhí)行 lookupJoin 操作時，會提取 A 數(shù)據(jù)，根據(jù) A 表數(shù)據(jù)發(fā)送 scan 請求去別的節(jié)點讀取數(shù)據(jù)。這樣會導(dǎo)致大量結(jié)果數(shù)據(jù)集中在 A 表分布的節(jié)點，沒有充分利用多節(jié)點并行執(zhí)行的優(yōu)勢。

現(xiàn)在，我們將 A 表數(shù)據(jù)提前通過 hash 重分布路由到多個節(jié)點再并行執(zhí)行 lookupJoin 操作；這樣不僅可以提高執(zhí)行效率，還可以使結(jié)果集在多個節(jié)點按照 hash key 預(yù)分布。

如圖 1 所示，執(zhí)行 select * from a join b on a.a = b.a 的操作時 B 表中有 join key 的索引 b_a_idx，改進后單節(jié)點 lookupJoin 變?yōu)槿?jié)點執(zhí)行 lookupJoin 操作，并且使 join 結(jié)果集按照 join 列在節(jié)點間 hash 分布。

2. ?分布式 lookupJoin 對分布式執(zhí)行產(chǎn)生的效果：

分布式 lookupJoin 可以使 join 結(jié)果集按照 join 列在節(jié)點間呈現(xiàn) hash 分布，大大提高了集群節(jié)點算力利用率，減少 hash 重分布的次數(shù)，縮短整體 query 執(zhí)行時間。

如圖 2 所示，在圖 1 的基礎(chǔ)上把 join 結(jié)果與 C 表再進行 join 查詢：select * from a,b,c where a.a=b.a and a.a = c.a ，模擬復(fù)雜查詢場景。由于在分布式 lookupJoin 查詢后，數(shù)據(jù)按照 join key 已經(jīng)在三節(jié)點上 hash 分布了，所以在執(zhí)行與 C 表的 join 操作時，只需要 hash 重分布 C 表的數(shù)據(jù)，減少了 hash 重分布的次數(shù)，提高了執(zhí)行效率。

3. ?分布表的 lookupJoin：

分布表是一種特殊表，表中數(shù)據(jù)按某列的 hash 值分布在各個節(jié)點上，如果分布表的分布列與 hash join 列正好一致，在執(zhí)行分布式 lookupJoin 時可以直接在各個節(jié)點并行執(zhí)行 lookupJoin，省去了 hash 分布的操作。