Find the Next Non-NULL Row in a Series With SQL

Spread the love
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  
  •  

I’ve stumbled across this fun SQL question on reddit, recently. The question was looking at a time series of data points where some events happened. For each event, we have the start time and the end time

timestamp start end
———————————–
2018-09-03 07:00:00 1 null
2018-09-03 08:00:00 null null
2018-09-03 09:00:00 null null
2018-09-03 10:00:00 null 1
2018-09-03 12:00:00 null null
2018-09-03 13:00:00 null null
2018-09-03 14:00:00 1 null
2018-09-03 15:00:00 null 1

The desired output of the query should be this additional count column:

timestamp start end count
——————————————-
2018-09-03 07:00:00 1 null 4
2018-09-03 08:00:00 null null null
2018-09-03 09:00:00 null null null
2018-09-03 10:00:00 null 1 null
2018-09-03 12:00:00 null null null
2018-09-03 13:00:00 null null null
2018-09-03 14:00:00 1 null 2
2018-09-03 15:00:00 null 1 null

So, the rule is simple. Whenever an event starts, we would like to know how many consecutive entries it takes until the event stops again. We can visually see how that makes sense:

timestamp start end count
——————————————-
2018-09-03 07:00:00 1 null 4 — 4 Rows in this event
2018-09-03 08:00:00 null null null
2018-09-03 09:00:00 null null null
2018-09-03 10:00:00 null 1 null

2018-09-03 12:00:00 null null null — No event here
2018-09-03 13:00:00 null null null

2018-09-03 14:00:00 1 null 2 — 2 Rows in this event
2018-09-03 15:00:00 null 1 null

Some observations and assumptions about the problem at hand:
No two events will ever overlap
The time series does not progress monotonously, i.e. even if most data points are 1h apart, there can be larger or smaller gaps between data points
There are, however, no two identical timestamps in the series
How can we solve this problem?
Create the data set, first
We’re going to be using PostgreSQL for this example, but it will work with any database that supports window functions, which are most databases these days.
In PostgreSQL, we can use the VALUES() clause to generate data in memory easily. For the sake of simplicity, we’re not going to use timestamps, but integer representations of the timestamps. I’ve included the same out-of-the-ordinary gap between 4 and 6:

values (1, 1, null),
(2, null, null),
(3, null, null),
(4, null, 1),
(6, null, null),
(7, null, null),
(8, 1, null),
(9, null, 1)

If we run this statement (yes, this is a standalone statement in PostgreSQL!), then the database will simply echo back the values we’ve sent it:

column1 |column2 |column3 |
——–|——–|——–|
1 |1 | |
2 | | |
3 | | |
4 | |1 |
6 | | |
7 | | |
8 |1 | |
9 | |1 |

How to deal with non-monotonously growing series
The fact that column1 is not growing monotonously means that we cannot use it / trust it as a means to calculate the length of an event. We need to calculate an additional column that has a guaranteed monotonously growing set of integers in it. The ROW_NUMBER() window function is perfect for that.
Consider this SQL statement:

with
d(a, b, c) as (
values (1, 1, null),
(2, null, null),
(3, null, null),
(4, null, 1),
(6, null, null),
(7, null, null),
(8, 1, null),
(9, null, 1)
),
t as (
select
row_number() over (order by a) as rn, a, b, c
from d
)
select * from t;

The new rn column is a row number calculated for each row based on the ordering of a. For simplicity, I’ve aliased:
a = timestamp
b = start
c = end
The result of this query is:

rn |a |b |c |
—|–|–|–|
1 |1 |1 | |
2 |2 | | |
3 |3 | | |
4 |4 | |1 |
5 |6 | | |
6 |7 | | |
7 |8 |1 | |
8 |9 | |1 |

Nothing fancy yet.
Now, how to use this rn column to find the length of an event?
Visually, we can get the idea quickly, seeing that an event’s length can be calculated using the formula RN2 – RN1 + 1:

rn |a |b |c |
—|–|–|–|
1 |1 |1 | | RN1 = 1
2 |2 | | |
3 |3 | | |
4 |4 | |1 | RN2 = 4

5 |6 | | |
6 |7 | | |

7 |8 |1 | | RN1 = 7
8 |9 | |1 | RN2 = 8

We have two events:
4 – 1 + 1 = 4
8 – 7 + 1 = 2
So, all we have to do is for each starting point of an event at RN1, find the corresponding RN2, and run the arithmetic. This is quite a bit of syntax, but it isn’t so hard, so bear with me while I explain:

with
d(a, b, c) as (
values (1, 1, null),
(2, null, null),
(3, null, null),
(4, null, 1),
(6, null, null),
(7, null, null),
(8, 1, null),
(9, null, 1)
),
t as (
select
row_number() over (order by a) as rn, a, b, c
from d
)

— Interesting bit here:
select
a, b, c,
case
when b is not null then
min(case when c is not null then rn end)
over (order by rn
rows between 1 following and unbounded following)
– rn + 1
end cnt
from t;

Let’s look at this new cnt column, step by step. First, the easy part:
The CASE expression
There’s a case expression that goes like this:

case
when b is not null then

end cnt

All this does is check if b is not null and if this is true, then calculate something. Remember, b = start, so we’re putting a calculated value in the row where an event started. That was the requirement.
The new window function
So, what do we calculate there?

min(…) over (…) …

A window function that finds the minimum value over a window of data. That minimum value is RN2, the next row number value where the event ends. So, what do we put in the min() function to get that value?

min(case when c is not null then rn end)
over (…)

Another case expression. When c is not null, we know the event has ended (remember, c = end). And if the event has ended, we want to find that row’s rn value. So that would be the minimum value of that case expression for all the rows after the row that started the event. Visually:

rn |a |b |c | case expr | minimum “next” value
—|–|–|–|———–|———————
1 |1 |1 | | null | 4
2 |2 | | | null | null
3 |3 | | | null | null
4 |4 | |1 | 4 | null

5 |6 | | | null | null
6 |7 | | | null | null

7 |8 |1 | | null | 8
8 |9 | |1 | 8 | null

Now, we only need to specify that OVER() clause to form a window of all rows that follow the current row.

min(case when c is not null then rn end)
over (order by rn
rows between 1 following and unbounded following)

The window is ordered by rn and it starts 1 row after the current row (1 following) and ends in infinity (unbounded following).
The only thing left to do now is do the arithmetic:

min(case when c is not null then rn end)
over (order by rn
rows between 1 following and unbounded following)
– rn + 1

This is a verbose way of calculating RN2 – RN1 + 1, and we’re doing that only in those columns that start an event. The result of the complete query above is now:

a |b |c |cnt |
–|–|–|—-|
1 |1 | |4 |
2 | | | |
3 | | | |
4 | |1 | |
6 | | | |
7 | | | |
8 |1 | |2 |
9 | |1 | |

Read more about window functions on this blog.

X ITM Cloud News

Emily

Next Post

Beware of Hidden PL/SQL to SQL Context Switches

Sun Nov 24 , 2019
Spread the love          I recently stumbled upon a curious query on a customer’s productive Oracle database: SELECT USER FROM SYS.DUAL Two things caught my attention: The query was executed many billions of times per month, accounting for about 0.3% of that system’s load. That’s 0.3% for something extremely silly! I don’t […]
X- ITM

Cloud Computing – Consultancy – Development – Hosting – APIs – Legacy Systems

X-ITM Technology helps our customers across the entire enterprise technology stack with differentiated industry solutions. We modernize IT, optimize data architectures, and make everything secure, scalable and orchestrated across public, private and hybrid clouds.

This image has an empty alt attribute; its file name is x-itmdc.jpg

The enterprise technology stack includes ITO; Cloud and Security Services; Applications and Industry IP; Data, Analytics and Engineering Services; and Advisory.

Watch an animation of  X-ITM‘s Enterprise Technology Stack

We combine years of experience running mission-critical systems with the latest digital innovations to deliver better business outcomes and new levels of performance, competitiveness and experiences for our customers and their stakeholders.

X-ITM invests in three key drivers of growth: People, Customers and Operational Execution.

The company’s global scale, talent and innovation platforms serve 6,000 private and public-sector clients in 70 countries.

X-ITM’s extensive partner network helps drive collaboration and leverage technology independence. The company has established more than 200 industry-leading global Partner Network relationships, including 15 strategic partners: Amazon Web Services, AT&T, Dell Technologies, Google Cloud, HCL, HP, HPE, IBM, Micro Focus, Microsoft, Oracle, PwC, SAP, ServiceNow and VMware

.

X ITM