Finding overlapping times in SQL

Exploring MySQL

This post is inspired by the LeetCode problem: link.

Problem statement:

SQL table has log in info of different users. Recorded info includes:

• User ID

• IP Address

• Log In Time

• Log Out Time

We have to identify users that are logged in from different IP addresses at the same time. The idea is - users that are logged in from different IP addresses at the same time have compromised log in credentials.

Visual summary of the problem statement:

Fig. 1: User log ins from different IP addresses.

In the above example, User 1 logs in from three different IP addresses at three different times. Log in times from IP addresses 1 and 2 are non-overlapping and therefore, are considered valid. However, log in times from IP addresses 1 and 3 are overlapping and are invalid.

Solving the problem - by finding overlaping times:

To solve the problem, we need to find overlaping times. If the logged in time periods of the same user from different IP addresses overlap, then we have an invalid log in (or, an instance of compromised user log in credential).

The scenerios for same user’s log in from different IP addresses are shown below (where, left time refers to the first instance of a user’s log in and right time refers to subsequent instances of the same user’s log in).

Fig. 2: Allowed non-overlaping times (green colored) and non-allowed overlapping times (red colored). Left time refers to the first instance of an user’s log in. Right time refers to subsequent instance(s) of the same user’s log in from a different IP address.

Red time periods are overlapping log in time periods - if such instances happen from different IP addresses, then the user’s credentials are compromised. Green time periods are non-overlaping and are valid entries.

Finding overlapping times:

The logic behind finding overlapping times can be graphically summerized as below:

Fig. 3: Logical conditions to identify overlapping times.

LogInfo table entries:

account_id	ip_address	login	logout
1	1	2/1/2021 9:00	2/1/2021 9:30
1	2	2/1/2021 8:00	2/1/2021 11:30
2	6	2/1/2021 20:30	2/1/2021 22:00
2	7	2/2/2021 20:30	2/2/2021 22:00
3	9	2/1/2021 16:00	2/1/2021 16:59
3	13	2/1/2021 17:00	2/1/2021 17:59
4	10	2/1/2021 16:00	2/1/2021 17:00
4	11	2/1/2021 17:00	2/1/2021 17:59

MySQL query to identify users with invalid logins:

SELECT DISTINCT l.account_id
FROM LogInfo l, LogInfo r
WHERE l.account_id = r.account_id  AND l.ip_address <> r.ip_address AND (l.login <= r.login AND l.logout >= r.login)

Explanation:

A closer inspection of the logical conditions in Fig. 3 shows that the two conditions (conditions in left shaded box vs. right shaded box) are mirror images. Since we are getting cartesian product of the same table, only checking for one condition (i.e., condition either in the left shaded box or right shaded box) should be enough.

---

After solving this problem, I came across an easier way to get overlapping time:

SELECT DISTINCT l.account_id 
FROM LogInfo l, LogInfo r
WHERE l.account_id = r.account_id  AND l.ip_address <> r.ip_address AND l.login BETWEEN r.login AND r.logout 

Who knew a simple BETWEEN is powerful enough!