SQL Challenge/Puzzle: Given a stack trace - How to find the top element at each point in time?

Question

• My real life use-case was to merge nested ranges. I've drew some sketches and then I saw the resemblance between ranges starting and ending to stack PUSH and POP operations. I understood that solving this problem will also solve the original problem.

---

• The op column can actually be removed from the question. When val is NULL then it is a POP operation otherwise it is a PUSH operation.

---

The Puzzle

A table, stack_trace ,contains the following columns:

• i - Integer value that represents a point in time.
• op - 2 possible operations: I ("in"/"push") and O ("out"/"pop").

• val - The value inserted by the "in"/"push" operation or NULL for "out"/"pop" operation.

  The goal is to find what was the value at the top of the stack, at each point in time (i).

e.g.

(NULL values are represented here as empty spaces)

data:

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

required result:

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

Requirements

• The solution should be a single SQL query (sub-queries are fine).
• Only the following clauses are allowed: SELECT, FROM, WHERE, GROUP BY, HAVING, ORDER BY.
• The use of WITH clause (CTE - Common Table Expression) is not allowed.
• The use of T-SQL, PL/SQL etc. is not allowed.
• The use of UDF (User Defined Functions) is not allowed.
• The use of variables is not allowed.

Sample data

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');

Required results

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

This is a nice puzzle.

As my main DBMS is Teradata I wrote a solution for it using Analytical functions (needs 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;

This solution works for Oracle, too, but PostgreSQL & SQL Server don't support the IGNORE NULLS option for LAST_VALUE and emulating it is quite complicated, e.g see Itzk Ben-Gan's The Last non NULL Puzzle

Edit: In fact it's not that complex, I forgot Itzik's 2nd solution, the old piggyback trick ;-)

Martin Smith's approach will work for all four DBMSes.

Answer 2

Personally I doubt that you will end up finding SQL that you can just use in all of SQL Server, Teradata, Postgres, and Oracle and that has acceptable performance if the table is at all large.

A SQL Server solution (demo) would be as follows

SELECT i,
       SUBSTRING(MAX(FORMAT(i, 'D10') + val) OVER (PARTITION BY Pos ORDER BY i 
                                                     ROWS UNBOUNDED PRECEDING), 11, 8000)
FROM   (SELECT st.*,
               sum(CASE WHEN op = 'I' THEN 1 ELSE -1 END) 
                  OVER (ORDER BY i ROWS UNBOUNDED PRECEDING) AS pos
        FROM   stack_trace st) t1
ORDER  BY i;