sql挑战/难题：如何合并嵌套范围？

os8fio9y 于 2021-06-28 发布在 Hive

关注(0)|答案(3)|浏览(288)

这个挑战基于一个涉及ip范围的实际用例。
我提供的解决方案是基于我之前介绍的堆栈跟踪挑战。每个范围开始被视为推操作，每个范围结束+1被视为弹出操作。

挑战

我们有一个范围的数据集，其中每个范围都有一个起点、终点和一个值。

create table ranges
(
    range_start     int         not null
   ,range_end       int         not null
   ,range_val       char(1)     not null
)
;

一个范围可以包含另一个范围或跟随另一个范围，但不能等于另一个范围或与另一个范围相交。
这些是范围之间的有效关系：

(1)           (2)           (3)           (4)
---------     ---------     ---------     -------- -----------
---                 ---        ---

这些关系无效：

(5)                (6)
-------        --------       
-------              --------

我们的初始范围以图形形式显示时，可能会如下所示（字母表示范围值）：

AAAAAAAA  BBCCCCCCC
 DDE   F   GGGGG
   H       IIII
             J

目标是获取初始范围集，并根据以下规则创建一个新的范围集：
包含的范围将覆盖包含范围的相应子范围。
当以图形方式显示所请求的结果时，可能如下所示

ADDHAAAF  BIIJIGCCC

要求

解决方案应该是单个sql查询（子查询也可以）。
不允许使用t-sql、pl/sql等。
不允许使用自定义函数。

数据样本

AAAAAAAAAAAAAAAAAAAAAAAAAAAA  BBBB    CCCCCCCCCCCCCCCCCCCCCCCCC
DDDE  FFFFFFFF    GGGGGGGGG               HHHHHHHH    IIIIIII
JJ      KKKLLL       MM NN                              OOOOO
            P                                              QQ

insert into ranges (range_start,range_end,range_val) values (1  ,28 ,'A');
insert into ranges (range_start,range_end,range_val) values (31 ,34 ,'B');
insert into ranges (range_start,range_end,range_val) values (39 ,63 ,'C');
insert into ranges (range_start,range_end,range_val) values (1  ,3  ,'D');
insert into ranges (range_start,range_end,range_val) values (4  ,4  ,'E');
insert into ranges (range_start,range_end,range_val) values (7  ,14 ,'F');
insert into ranges (range_start,range_end,range_val) values (19 ,27 ,'G');
insert into ranges (range_start,range_end,range_val) values (43 ,50 ,'H');
insert into ranges (range_start,range_end,range_val) values (55 ,61 ,'I');
insert into ranges (range_start,range_end,range_val) values (1  ,2  ,'J');
insert into ranges (range_start,range_end,range_val) values (9  ,11 ,'K');
insert into ranges (range_start,range_end,range_val) values (12 ,14 ,'L');
insert into ranges (range_start,range_end,range_val) values (22 ,23 ,'M');
insert into ranges (range_start,range_end,range_val) values (25 ,26 ,'N');
insert into ranges (range_start,range_end,range_val) values (57 ,61 ,'O');
insert into ranges (range_start,range_end,range_val) values (13 ,13 ,'P');
insert into ranges (range_start,range_end,range_val) values (60 ,61 ,'Q');

请求的结果

（空值在这里表示为空格）

JJDEAAFFKKKLPLAAAAGGGMMGNNGA  BBBB    CCCCHHHHHHHHCCCCIIOOOQQCC

range_start range_end range_val
----------- --------- ---------
1           2          J
3           3          D
4           4          E
5           6          A
7           8          F
9           11         K
12          12         L
13          13         P
14          14         L
15          18         A
19          21         G
22          23         M
24          24         G
25          26         N
27          27         G
28          28         A
29          30         
31          34         B
35          38         
39          42         C
43          50         H
51          54         C
55          56         I
57          59         O
60          61         Q
62          63         C

可选添加最后一行：

sql Hive sql-server teradata oracle

来源：https://stackoverflow.com/questions/40021020/sql-challenge-puzzle-how-to-merge-nested-ranges

3条答案

按热度按时间

6pp0gazn1#

该解决方案基于我前面介绍的堆栈跟踪挑战。每个范围开始被视为推操作，每个范围结束+1被视为弹出操作。
在性能方面，您可能会注意到两个内部分析函数如何使用相同的窗口，因此在一个步骤中执行。

teradata公司

select      new_range_start
           ,new_range_end

           ,last_value (range_val ignore nulls) over 
            (
                partition by    stack_depth
                order by        new_range_start ,range_start ,range_end desc 
                rows            unbounded preceding
            )                                                                   as new_range_val

from       (select      new_range_start
                       ,range_val
                       ,range_start
                       ,range_end

                       ,sum (case when range_val is null then -1 else 1 end) over 
                        (
                            order by    new_range_start, range_start ,range_end desc  
                            rows        unbounded preceding
                        )                                                                   as stack_depth

                       ,min (new_range_start) over
                        (
                            order by    new_range_start ,range_start ,range_end desc
                            rows        between 1 following and 1 following

                        ) - 1                                                               as new_range_end

            from        (           select range_start     ,range_start ,range_end ,range_val              from ranges
                        union all   select range_end   + 1 ,range_start ,range_end ,cast (null as char(1)) from ranges
                        )
                        r (new_range_start,range_start,range_end,range_val)
            )
            r

qualify     new_range_end >= new_range_start

order by    new_range_start
;

甲骨文

select      new_range_start
           ,new_range_end
           ,new_range_val                       

from       (select      new_range_start
                       ,new_range_end

                       ,last_value (range_val ignore nulls) over 
                        (
                            partition by    stack_depth
                            order by        new_range_start ,range_start ,range_end desc 
                            rows            unbounded preceding
                        )                                                                   as new_range_val

            from       (select      new_range_start
                                   ,range_start
                                   ,range_end
                                   ,range_val

                                   ,sum (case when range_val is null then -1 else 1 end) over 
                                    (
                                        order by    new_range_start, range_start ,range_end desc  
                                        rows        unbounded preceding
                                    )                                                                as stack_depth

                                   ,lead (new_range_start) over
                                    (
                                        order by    new_range_start, range_start ,range_end desc 
                                    ) - 1                                                            as new_range_end

                        from        (           select range_start     as new_range_start ,range_start ,range_end ,range_val              from ranges
                                    union all   select range_end   + 1                    ,range_start ,range_end ,cast (null as char(1)) from ranges
                                    )
                                    r 
                        )
                        r
            )
            r

where       new_range_end >= new_range_start

order by    new_range_start
;

sql server/postgresql/hive

select      *

from       (select      new_range_start
                       ,new_range_end
                       ,min (range_val) over
                        (
                            partition by    stack_depth,new_range_val_group_id
                        )                                                       as new_range_val                       

            from       (select      new_range_start
                                   ,new_range_end
                                   ,range_val
                                   ,stack_depth

                                   ,count (range_val) over 
                                    (
                                        partition by    stack_depth
                                        order by        new_range_start ,range_start ,range_end desc 
                                        rows            unbounded preceding
                                    )                                                                   as new_range_val_group_id

                        from       (select      new_range_start
                                               ,range_start
                                               ,range_end
                                               ,range_val

                                               ,sum (case when range_val is null then -1 else 1 end) over 
                                                (
                                                    order by    new_range_start, range_start ,range_end desc  
                                                    rows        unbounded preceding
                                                )                                                                as stack_depth

                                               ,lead (new_range_start) over
                                                (
                                                    order by    new_range_start, range_start ,range_end desc 
                                                ) - 1                                                            as new_range_end

                                    from        (           select range_start     as new_range_start ,range_start ,range_end ,range_val                           from ranges
                                                union all   select range_end   + 1 as new_range_start ,range_start ,range_end ,cast (null as char(1)) as range_val from ranges
                                                )
                                                r 
                                    )
                                    r
                        )
                        r
            )
            r

where       new_range_end >= new_range_start

order by    new_range_start
;

赞(0）回复(0）举报 2021-06-28

rggaifut2#

oracle解决方案：

with l as ( select level lvl from dual connect by level < 66 ),
     r as ( select range_start r1, range_end r2, range_val v, 
                    range_end - range_start + 1 cnt 
              from ranges ),
     t1 as (select distinct lvl, 
                   nvl(max(v) keep (dense_rank first order by cnt) 
                              over (partition by lvl), '*' ) m
              from l left join r on lvl between r1 and r2 ),
     t2 as (select lvl, m, case when lag(m) over (order by lvl) <> m then 0 else 1 end mrk 
              from t1),
     t3 as (select lvl, m, lvl - sum(mrk) over (order by lvl) grp from t2)
select min(lvl) r1, max(lvl) r2, nullif(min(m), '*') val
  from t3 group by grp order by r1

输出符合要求。我的英语很差，所以很难解释，但让我们试试： l -数字发生器， r -数据来源 ranges 以计算的距离， t1 -为每个等级找到最小距离的值， t2 -添加标记，指示范围是否开始， t3 -添加下一个用于分组数据的列。

赞(0）回复(0）举报 2021-06-28

dsf9zpds3#

oracle解决方案2

WITH borders AS /*get all borders of interval*/ 
  (SELECT DISTINCT DECODE(is_end, 0, range_start, range_end) AS border 
                  ,is_end 
   FROM   ranges r, 
          (SELECT 0 AS is_end FROM dual UNION ALL 
           SELECT 1 AS is_end FROM dual)), 
 interv AS  /*get all intervals*/ 
  (SELECT border + is_end AS beg_int 
         ,lead(border) over(ORDER BY border, is_end ) 
           - lead(DECODE(is_end, 0, 1, 0)) over(ORDER BY border, is_end) AS end_int 
   FROM   borders 
   ORDER  BY 1) 
 SELECT i.beg_int 
       ,i.end_int 
       ,(SELECT MAX(r.range_val) keep (dense_rank FIRST ORDER BY r.range_end - r.range_start) 
       FROM ranges r 
       WHERE i.beg_int >= r.range_start AND i.end_int <= r.range_end) AS range_val   
 FROM   interv i 
 WHERE  beg_int <= end_int OR end_int IS NULL 
 ORDER  BY i.beg_int;

添加不带自联接的解决方案：编辑：修复缺陷。

WITH intervals AS 
  (SELECT DECODE(is_end, -1, range_val, NULL) AS range_val 
         ,DECODE(is_end, -1, range_start, range_end) AS border 
         ,is_end 
         ,- (SUM(is_end) over(ORDER BY DECODE(is_end, -1, range_start, range_end), is_end, (range_end - range_start) * is_end)) AS poss 
         ,(range_end - range_start) * is_end AS ord2 
   FROM   ranges r 
         ,(SELECT -1 AS is_end FROM   dual UNION ALL 
           SELECT 1  AS is_end FROM   dual)), 
 range_stack AS 
  (SELECT border + DECODE(is_end, 1, 1, 0) AS begin_int 
         ,lead(border) over(ORDER BY border, is_end, ord2) 
           + DECODE(lead(is_end) over(ORDER BY border, is_end, ord2), 1, 0, -1) AS end_int 
         ,last_value(range_val ignore NULLS) over(PARTITION BY poss ORDER BY border, is_end, ord2) AS range_val 
   FROM   intervals) 
 SELECT begin_int 
       ,end_int 
       ,range_val 
 FROM   range_stack 
 WHERE  end_int >= begin_int 
        OR end_int IS NULL;

赞(0）回复(0）举报 2021-06-28

我来回答

sql挑战/难题：如何合并嵌套范围？

挑战

要求

数据样本

请求的结果

3条答案

teradata公司

甲骨文

sql server/postgresql/hive

相关问题

热门标签

最新问答