Blocker Distance Query: SQL to Find the Nearest Blocking Obstacle for Each Entity

Question

## Problem

You have a table of entities (e.g., robots) at positions on a 1D track, and a table of blockers (obstacles) also at positions. For each entity, find the nearest blocker that is directly ahead of it (i.e., at a strictly greater position), and return the entity ID, blocker ID, and distance.

```sql
-- entities:  id INT, position FLOAT
-- blockers:  id INT, position FLOAT

SELECT
    e.id         AS entity_id,
    b.id         AS blocker_id,
    b.position - e.position AS distance
FROM entities e
JOIN blockers b ON b.position > e.position
QUALIFY ROW_NUMBER() OVER (
    PARTITION BY e.id
    ORDER BY b.position ASC
) = 1
ORDER BY e.id;
```

**Example:**
```
entities: (1, pos=2), (2, pos=7)
blockers: (A, pos=5), (B, pos=10), (C, pos=3)

result:
  entity 1 -> blocker C (pos 3), distance 1
  entity 2 -> blocker B (pos 10), distance 3
```

## Follow-ups

1. What SQL construct replaces `QUALIFY` in databases that do not support it (e.g., older MySQL)? Write the equivalent using a subquery.
2. How would you extend this to find the nearest blocker in either direction (min absolute distance)?
3. What index on `blockers.position` makes this join efficient at scale?
4. How would you adapt this to 2D positions, finding the nearest blocker within a 45-degree cone ahead of each entity?

Blocker Distance Query: SQL to Find the Nearest Blocking Obstacle for Each Entity

Question Details

Full Details

Topics

More from Uber