SQL 挑战/谜题 : Given a stack trace - How to find the top element at each point in time?

Question

• 我的现实生活用例是 merge nested ranges 。 我画了一些草图，然后我看到了堆栈 PUSH 和 POP 操作的开始和结束范围之间的相似之处。我明白解决了这个问题也就解决了原来的问题。

<小时/>

• op 列实际上可以从问题中删除。当val为NULL时，则为POP操作，否则为PUSH操作。

<小时/>

谜题

表 stack_trace 包含以下列:

• i - 表示时间点的整数值。
• op - 2 种可能的操作:I(“入”/“推”)和 O(“出”/“弹出”)。

• val - 通过“in”/“push”操作插入的值或“out”/“pop”操作插入的值。

  目标是找出每个时间点 (i) 堆栈顶部的值是多少。

例如

(NULL 值在这里表示为空格)

数据:

i   op  val 
--  --  --  
1   I   A   
2   I   B   
3   O
4   I   C
5   O    
6   O   

所需结果:

i   top_of_stack_val
--  ----------------
1   A
2   B
3   A
4   C
5   A
6   

要求

• 解决方案应该是单个 SQL 查询(子查询也可以)。
• 仅允许使用以下子句:SELECT、FROM、WHERE、GROUP BY、有、排序依据。
• 不允许使用WITH子句(CTE - 通用表表达式)。
• 不允许使用 T-SQL、PL/SQL 等。
• 不允许使用 UDF(用户定义函数)。
• 不允许使用变量。

示例数据

create table stack_trace
(
    i       int
   ,op      char(1)
   ,val     char(1)
)
;

insert into stack_trace (i,op,val) values (1,'I','A');
insert into stack_trace (i,op,val) values (2,'I','B');
insert into stack_trace (i,op,val) values (3,'I','C');
insert into stack_trace (i,op,val) values (4,'I','D');
insert into stack_trace (i,op,val) values (5,'I','E');
insert into stack_trace (i,op)     values (6,'O');
insert into stack_trace (i,op)     values (7,'O');
insert into stack_trace (i,op)     values (8,'O');
insert into stack_trace (i,op,val) values (9,'I','F');
insert into stack_trace (i,op)     values (10,'O');
insert into stack_trace (i,op,val) values (11,'I','G');
insert into stack_trace (i,op,val) values (12,'I','H');
insert into stack_trace (i,op)     values (13,'O');
insert into stack_trace (i,op)     values (14,'O');
insert into stack_trace (i,op,val) values (15,'I','I');
insert into stack_trace (i,op,val) values (16,'I','J');
insert into stack_trace (i,op,val) values (17,'I','K');
insert into stack_trace (i,op,val) values (18,'I','L');
insert into stack_trace (i,op,val) values (19,'I','M');
insert into stack_trace (i,op)     values (20,'O');
insert into stack_trace (i,op,val) values (21,'I','N');
insert into stack_trace (i,op)     values (22,'O');
insert into stack_trace (i,op,val) values (23,'I','O');
insert into stack_trace (i,op)     values (24,'O');
insert into stack_trace (i,op,val) values (25,'I','P');
insert into stack_trace (i,op)     values (26,'O');
insert into stack_trace (i,op)     values (27,'O');
insert into stack_trace (i,op,val) values (28,'I','Q');
insert into stack_trace (i,op,val) values (29,'I','R');
insert into stack_trace (i,op)     values (30,'O');
insert into stack_trace (i,op)     values (31,'O');
insert into stack_trace (i,op)     values (32,'O');
insert into stack_trace (i,op)     values (33,'O');
insert into stack_trace (i,op)     values (34,'O');
insert into stack_trace (i,op)     values (35,'O');
insert into stack_trace (i,op,val) values (36,'I','S');
insert into stack_trace (i,op)     values (37,'O');
insert into stack_trace (i,op)     values (38,'O');
insert into stack_trace (i,op,val) values (39,'I','T');
insert into stack_trace (i,op,val) values (40,'I','U');
insert into stack_trace (i,op)     values (41,'O');
insert into stack_trace (i,op,val) values (42,'I','V');
insert into stack_trace (i,op,val) values (43,'I','W');
insert into stack_trace (i,op,val) values (44,'I','X');
insert into stack_trace (i,op)     values (45,'O');
insert into stack_trace (i,op)     values (46,'O');
insert into stack_trace (i,op,val) values (47,'I','Y');
insert into stack_trace (i,op)     values (48,'O');
insert into stack_trace (i,op)     values (49,'O');
insert into stack_trace (i,op,val) values (50,'I','Z');
insert into stack_trace (i,op)     values (51,'O');
insert into stack_trace (i,op)     values (52,'O');

所需结果

i   top_of_stack_val
--  ----------------
1   A
2   B
3   C
4   D
5   E
6   D
7   C
8   B
9   F
10  B
11  G
12  H
13  G
14  B
15  I
16  J
17  K
18  L
19  M
20  L
21  N
22  L
23  O
24  L
25  P
26  L
27  K
28  Q
29  R
30  Q
31  K
32  J
33  I
34  B
35  A
36  S
37  A
38  
39  T
40  U
41  T
42  V
43  W
44  X
45  W
46  V
47  Y
48  V
49  T
50  Z
51  T
52  

Answer 1

这是一个很好的谜题。

由于我的主要 DBMS 是 Teradata，我使用分析函数为其编写了一个解决方案(需要 TD14.10+):

SELECT dt.*,
   -- find the last item in the stack with the same position
   Last_Value(val IGNORE NULLS)
   Over (PARTITION BY pos
         ORDER BY i) AS top_of_stack_val
FROM 
 ( 
   SELECT st.*,
      -- calculate the number of items in the stack
      Sum(CASE WHEN op = 'I' THEN 1 ELSE -1 end) 
      Over (ORDER BY i
            ROWS Unbounded Preceding) AS pos
   FROM stack_trace AS st
 ) AS dt;

这个解决方案也适用于 Oracle，但 PostgreSQL 和 SQL Server 不支持 LAST_VALUE 的 IGNORE NULLS 选项，并且模拟它非常复杂，例如参见 Itzk本甘的The Last non NULL Puzzle

编辑:事实上，它并没有那么复杂，我忘记了 Itzik 的第二个解决方案，老背驮技巧;-)

Martin Smith 的方法适用于所有四种 DBMS。