使用 impala 按范围连接表的有效方法

Question

我有以下 table 第一个 (Range) 包括值范围和附加列：

row  | From   |  To     | Country ....
-----|--------|---------|---------
1    | 1200   |   1500  |
2    | 2200   |   2700  |
3    | 1700   |   1900  |
4    | 2100   |   2150  |
...

From和To是bigint并且是互斥的。 Range table 包含 180 万条记录。附加 table (Values) 包含 2.7M 条记录，看起来像：

 row     | Value  | More columns....
 --------|--------|----------------
    1    | 1777   |    
    2    | 2122   |    
    3    | 1832   |    
    4    | 1340   |    
    ...

我想创建一个 table 如下：

row      | Value  | From   | To    | More columns....
 --------|--------|--------|-------|---
    1    | 1777   | 1700   | 1900  |
    2    | 2122   | 2100   | 2150  |   
    3    | 1832   | 1700   | 1900  |   
    4    | 1340   | 1200   | 1500  |   
    ...

我使用 BETWEEN 完成上述任务，但查询永远不会结束：

VALUES.VALUE between RANGE.FROM and RANGE.TO

我需要对 table 分区或 Impala 进行更改吗？

Answer 1

以下解决方案的主要思想是将 theta 连接（非等值连接）替换为等值连接，这将导致良好的分布 + 高效的本地连接算法。

范围 (-infinity,infinity) 被分割成 n 长度的部分。
范围 table 中的每个范围都与其相交的部分相关联。

例如给定 n=1000，范围 [1652,3701] 将与部分 [1000,2000)、[2000,3000) 和 [3000,4000) 相关联（并且将有 3 个记录，每个部分 1 个）

               1652              3701
               |                 |
               -------------------

-------------------------------------------------------
|        |        |        |        |        |                
0        1000     2000     3000     4000     5000

以相同的方式，值 table 中的一个值与包含它的范围相关联，例如2093 将与范围 [2000,3000).

相关联

2 个 table 之间的连接将基于代表该部分的值，例如[1652,3701] 和 2093 将加入 [2000,3000)

部分

create table val_range (id int,from_val bigint,to_val bigint);

insert into val_range values
    (1,1200,1500)
   ,(2,2200,2700)
   ,(3,1700,1900)
   ,(4,2100,2150)
;   

create table val (id int,val bigint);

insert into val values
    (1,1777)    
   ,(2,2122)    
   ,(3,1832)    
   ,(4,1340)
;

set n=1000;

select      v.id
           ,v.val
           ,r.from_val
           ,r.to_val

from       (select  r.*
                   ,floor(from_val/${hiveconf:n}) + pe.i    as match_val

            from    val_range r
                    lateral view    posexplode
                                    (
                                        split
                                        (
                                            space
                                            (
                                                cast
                                                (
                                                    floor(to_val/${hiveconf:n}) 
                                                  - floor(from_val/${hiveconf:n}) 

                                                    as int
                                                )
                                            )
                                           ,' '
                                        )
                                    ) pe as i,x
            ) r

            join    val v

            on      floor(v.val/${hiveconf:n})    =
                    r.match_val

where       v.val between r.from_val and r.to_val

order by    v.id        
;

+------+-------+------------+----------+
| v.id | v.val | r.from_val | r.to_val |
+------+-------+------------+----------+
|    1 |  1777 |       1700 |     1900 |
|    2 |  2122 |       2100 |     2150 |
|    3 |  1832 |       1700 |     1900 |
|    4 |  1340 |       1200 |     1500 |
+------+-------+------------+----------+

Answer 2

我运行遇到了与 IP 地址和 GeoIP 数据库类似的问题。范围连接非常慢，但是通过“桶”连接，然后使用运行ge 条件（where）进行优化。

select
    g.country_iso_code,
    count(1) as cnt
from access_log as a
join geoip as g
  -- number of IPv4 addresses: 2**32 ==> 10 digits
  -- max network size: 2**23 ==> 8.3M ==> 7 digits 
  --   check with: select max(net_end-net_start) from geoip
  on round(a.int_ip, -7) = round(g.net_start, -7) -- <<== Step 1. bucket IP addresses
where a.date between "2021-12-01" and "2021-12-31"
  and a.int_ip between g.net_start and g.net_end  -- <<== Step 2. refine
group by g.country_iso_code
order by cnt desc

int_ip是转换成整数的IPv4 IP地址。例如。 192.168.1.1 是 3232235777。net_start 和 net_end 类似表示。

如果允许一些不准确，那么您可以将四舍五入减少到 -6、-5、... 数字，这将加快执行速度，但大型网络可能会被错误分类。

使用 impala 按范围连接表的有效方法

Effective way to join tables by range using impala

sql

hive

between

impala