目錄

0 問題描述

1 位圖思想

2 案例實戰(zhàn)

3 小結(jié)

---

0 問題描述

在工作中，我們往往使用array_contains()函數(shù)來進行存在性問題分析，如判斷某個數(shù)是否在某個數(shù)組中，但是當表數(shù)據(jù)量過多，存在大量array_contains()函數(shù)時，就會存在一定性能問題，為了優(yōu)化該函數(shù)的性能，本文主要利用位圖的方法來代替array_contains()函數(shù)。

1 位圖思想

? ?在本文之前讀者需要先了解位圖的概念及位圖的一些性質(zhì)，本文關(guān)于位圖的概念不再重復(fù)。假如我們有如下需求，如下圖所示，我們想判讀數(shù)字2,5,7是否在數(shù)組[1,2,3,5,6]中時，如果用位圖我們應(yīng)該怎么做？通過兩個位圖相與就可以求出交集，通過下圖可以看出bitmap1&bitmap2，可以求出交集2和5在數(shù)組中，因此關(guān)于此性質(zhì)，我們可以得到判讀存在性問題時，我們只需要構(gòu)建兩個位圖與，結(jié)果有值不為0則為存在，那么問題來了，如何通過SQL的形式去構(gòu)建呢？

? ?

相比大家對8421碼比較熟悉，如1111，如下圖所示

上述的式子我們可以進行如下等價

1111=15=1*2^0 + 1 * 2^1? +? 1 * 2^2 +? 1 * 2^3?<=> 1 << 0 + 1 << 1 + 1 << 2? + 1 << 3

因此我們構(gòu)建數(shù)組?[1,2,3,5,6] 在位圖中反應(yīng)即為：

存在記為1，不存在記為0，即序列?01101110

那我們?nèi)绾斡肧QL語言反應(yīng)上述表達式呢？根據(jù)前面的等價轉(zhuǎn)換，我們知道要反應(yīng)01101110序列

即為：01101110=1*2^1 +?1*2^2 + 1*2^3?+ 1*2^5?+ 1*2^6 = 1 << 1 +?1 << 2?+?1 << 3 +?1 << 5?+?1 << 6。因此只要我們數(shù)據(jù)庫中支持位移運算，就可以等價上述表達式。那么我們怎么判斷數(shù)字2是否在上述數(shù)組中呢?數(shù)字2的位圖根據(jù)以上推導(dǎo)，我們可以很快得出 1 << 2,而是否存在，只需要兩者之間進行與運算即可，即：(1 << 2) &( 1 << 1 +?1 << 2?+?1 << 3 +?1 << 5?+?1 << 6),計算過程如下：

? ?01101110
& ?00000010
————————————————
? ?00000010 ? ?=2
?

?總結(jié)上述規(guī)律，我們得出如下判斷公式：

假設(shè)判斷某個num是否在數(shù)組[a,b,c,d]中時，可用如下公式：
if{

? ?(1 << num) & (1 << a + 1 << b ?+ 1 << c + 1 << d) = num
? ?then true
? ?else false

};

上述操作對應(yīng)不同數(shù)據(jù)庫操作符不一樣，如何hive中使用shiftleft函數(shù)，doris中采用bit_shift_?left()函數(shù)，greenplum中直接為 <<操作符。

2 案例實戰(zhàn)

如下2張表tbl1,tbl2，假設(shè)表數(shù)據(jù)量很大，判斷tbl2中的col1字段是否在表tbl1中對應(yīng)的id num字段中。

具體SQL如下：

select  t1.id, col1,case when (1 << col1) & num ) = col1 then true else false end true_or_false_flgfrom tbl1 t1
left join
(select id ,sum(1 << num) numfrom tbl2group by id ) t2
on t1.id = t2.id

讀者在遇到相關(guān)問題時，可以根據(jù)自己具體的場景進行等價變換，這里只是拋磚引玉說明具體使用方法、

3 小結(jié)

? 本文主要闡述了如何利用位圖思想優(yōu)化array_contains()函數(shù)的方法，在具體業(yè)務(wù)中得到了較好的性能提升，當表數(shù)據(jù)量比較大，且利用array_contains()函數(shù)比較多時候，性能提升明顯，利用計算機底層位移運算減少了開銷。