SQL query to show the full minimal timeline of two tables

[Akeboshiwind]

What we're building 📋

Requirements:

• Show every device with its active config_layer (if any) across all time periods
• When multiple config_layers overlap, use the most recently inserted one
• Include periods where device exists but no config_layer applies (these should show null)
• Handle all edge cases: device before config, config before device, gaps between configs

Input: Two bitemporal tables

• devices - entities that exist over time
• config_layers - configuration that can override device defaults, with device_id foreign key

Expected output: Complete timeline showing which config (if any) applies to each device at every point in time

Why not just FULL OUTER JOIN? 🤔

You might think "just do a FULL OUTER JOIN between device and config_layer" - but that misses a crucial piece!
A FULL OUTER JOIN only gives you periods where either a device exists or a config_layer exists, but it doesn't handle the gaps properly.

Consider device 1: it exists from 2024-01-01, but config layer 'a' only starts at 2024-01-02. There's a period [2024-01-01,2024-01-02] where the device exists but has no config layer - FULL OUTER JOIN would miss this entirely because it's not looking at the temporal segments, just the overlapping records.

Same issue with device 3: it has gaps between config layers where the device exists but no config applies. We need those null config_layer periods in our results!

That's why we need to build the time segments first, then join everything onto those segments.

---

I've setup various scenarios here:

Setup

-- Device that exists before the config_layer
BEGIN READ WRITE WITH (SYSTEM_TIME = DATE '2024-01-01');
  INSERT INTO device RECORDS {_id: 1};
COMMIT;

BEGIN READ WRITE WITH (SYSTEM_TIME = DATE '2024-01-02');
  INSERT INTO config_layer RECORDS {_id: 'a', device_id: 1};
COMMIT;

-- Device with no config_layer
BEGIN READ WRITE WITH (SYSTEM_TIME = DATE '2024-01-03');
  INSERT INTO device RECORDS {_id: 2};
COMMIT;

-- Device with multiple overlaps
BEGIN READ WRITE WITH (SYSTEM_TIME = DATE '2024-01-04');
  INSERT INTO device RECORDS {_id: 3};
COMMIT;

BEGIN READ WRITE WITH (SYSTEM_TIME = DATE '2024-01-05');
  INSERT INTO config_layer RECORDS {_id: 'b', device_id: 3, _valid_to: DATE '2024-01-06'};
COMMIT;

BEGIN READ WRITE WITH (SYSTEM_TIME = DATE '2024-01-07');
  INSERT INTO config_layer RECORDS {_id: 'c', device_id: 3, _valid_to: DATE '2024-01-08'};
COMMIT;

-- config_layer before device
BEGIN READ WRITE WITH (SYSTEM_TIME = DATE '2024-01-09');
  INSERT INTO config_layer RECORDS {_id: 'd', device_id: 4};
COMMIT;

BEGIN READ WRITE WITH (SYSTEM_TIME = DATE '2024-01-10');
  INSERT INTO device RECORDS {_id: 4};
COMMIT;

-- overlapping config_layer
BEGIN READ WRITE WITH (SYSTEM_TIME = DATE '2024-01-11');
  INSERT INTO device RECORDS {_id: 5};
COMMIT;

BEGIN READ WRITE WITH (SYSTEM_TIME = DATE '2024-01-12');
  INSERT INTO config_layer RECORDS {_id: 'e', device_id: 5};
COMMIT;

BEGIN READ WRITE WITH (SYSTEM_TIME = DATE '2024-01-13');
  INSERT INTO config_layer RECORDS {_id: 'f', device_id: 5, _valid_to: DATE '2024-01-14'};
COMMIT;

Here's our query (Play):

SETTING DEFAULT VALID_TIME ALL
WITH interesting_boundaries AS (
  -- 1️⃣
  -- NOTE: All of these are full scans...
  SELECT device._id AS device_id, device._valid_from AS boundary_time FROM device
  UNION ALL
  SELECT device._id AS device_id, device._valid_to AS boundary_time FROM device WHERE device._valid_to IS NOT NULL
  UNION ALL  
  SELECT cl.device_id AS device_id, cl._valid_from AS boundary_time FROM config_layer AS cl
  UNION ALL
  SELECT cl.device_id AS device_id, cl._valid_to AS boundary_time FROM config_layer AS cl WHERE cl._valid_to IS NOT NULL
), time_boundaries AS (
  -- 2️⃣
  FROM device
  CROSS JOIN interesting_boundaries AS b
  WHERE device._id = b.device_id, device._valid_time CONTAINS b.boundary_time
  SELECT DISTINCT device._id AS device_id, b.boundary_time
), time_segments AS (
  -- 3️⃣
  FROM time_boundaries AS t1
  LEFT JOIN time_boundaries AS t2 
    ON t1.device_id = t2.device_id
    AND t2.boundary_time > t1.boundary_time
  SELECT 
    t1.device_id,
    PERIOD(t1.boundary_time, MIN(t2.boundary_time)) AS segment
)
-- 4️⃣
FROM time_segments AS ts
LEFT OUTER JOIN device
  ON device._id = ts.device_id
    AND device._valid_time OVERLAPS ts.segment
LEFT OUTER JOIN config_layer 
  ON config_layer.device_id = ts.device_id 
    AND config_layer._valid_time OVERLAPS ts.segment
SELECT 
  device._id AS device_id,
  config_layer._id AS config_layer_id,
  ts.segment AS valid_time,
  -- 5️⃣
  ROW_NUMBER() OVER (
    PARTITION BY device._id, ts.segment
    ORDER BY
      -- Most recently entered (you should probably use a `created_at` here)
      config_layer._system_from DESC,
      -- Disambiguate by _id
      config_layer._id
  ) AS rn
WHERE rn = 1
SELECT * EXCLUDE rn
ORDER BY device_id, LOWER(valid_time)

It's chunky, but I challenge you to come up with something similar (or do it better without XTDB)!

These are the results it produces:

device_id	config_layer_id	valid_time
1	null	[2024-01-01,2024-01-02]
1	'a'	[2024-01-02,]
2	null	[2024-01-03,]
3	null	[2024-01-04,2024-01-05]
3	'b'	[2024-01-05,2024-01-06]
3	null	[2024-01-06,2024-01-07]
3	'c'	[2024-01-07,2024-01-08]
3	null	[2024-01-08,]
4	'd'	[2024-01-10,]
5	null	[2024-01-11,2024-01-12]
5	'e'	[2024-01-12,2024-01-13]
5	'f'	[2024-01-13,2024-01-14]
5	'e'	[2024-01-14,]

---

Step by step we:

1. Gather all the interesting dates
2. Filter for those that are related to our device
3. Figure out all the minimal time segments for each device
4. Join our segments onto our device & config_layers
5. Figure out which of our config_layers to use (in this case: of the ones that overlay, the last inserted)

[jarohen]

neat case study @Akeboshiwind 👌

When multiple config_layers overlap, use the most recently inserted one

This is a data-modelling smell in XTDB, a sign that that valid-time isn't being used correctly - you're effectively trying to re-create XT's entity timeline resolution but in user-space. Instead, try to migrate that table s.t. the history of each entity represents the correct current state of your config-layer at each point in time.

Specifically, from your data model (which I'm aware is extracted and cut down so might not be possible IRL), I would model config_layer with its _id as the device-id (i.e. device and config_layer become 1:1 - this is a key assumption of mine, so if that doesn't hold in practice, ignore this whole comment 😅), and use the previous cl._id as a new field (config, say).

If you also want the valid-time periods for which there is no config layer, I'd create a config_layer record when the device is created, so that you can inner-join - PATCH this so that, if the config_layer does already exist, it doesn't override any existing data.

  -- Device that exists before the config_layer
  BEGIN READ WRITE WITH (SYSTEM_TIME = DATE '2024-01-01');
    INSERT INTO device RECORDS {_id: 1};
    PATCH INTO config_layer RECORDS {_id: 1};
  COMMIT;

  BEGIN READ WRITE WITH (SYSTEM_TIME = DATE '2024-01-02');
    INSERT INTO config_layer RECORDS {_id: 1, config: 'a'};
  COMMIT;

  -- Device with no config_layer
  BEGIN READ WRITE WITH (SYSTEM_TIME = DATE '2024-01-03');
    INSERT INTO device RECORDS {_id: 2};
    PATCH INTO config_layer RECORDS {_id: 2};
  COMMIT;

  -- Device with multiple overlaps
  BEGIN READ WRITE WITH (SYSTEM_TIME = DATE '2024-01-04');
    INSERT INTO device RECORDS {_id: 3};
    PATCH INTO config_layer RECORDS {_id: 3};
  COMMIT;

  BEGIN READ WRITE WITH (SYSTEM_TIME = DATE '2024-01-05');
    INSERT INTO config_layer RECORDS {_id: 3, config: 'b', _valid_to: DATE '2024-01-06'};
  COMMIT;

  BEGIN READ WRITE WITH (SYSTEM_TIME = DATE '2024-01-07');
    INSERT INTO config_layer RECORDS {_id: 3, config: 'c', _valid_to: DATE '2024-01-08'};
  COMMIT;

  -- config_layer before device
  BEGIN READ WRITE WITH (SYSTEM_TIME = DATE '2024-01-09');
    INSERT INTO config_layer RECORDS {_id: 4, config: 'd'};
  COMMIT;

  BEGIN READ WRITE WITH (SYSTEM_TIME = DATE '2024-01-10');
    INSERT INTO device RECORDS {_id: 4};
    PATCH INTO config_layer RECORDS {_id: 4};
  COMMIT;

  -- overlapping config_layer
  BEGIN READ WRITE WITH (SYSTEM_TIME = DATE '2024-01-11');
    INSERT INTO device RECORDS {_id: 5};
    PATCH INTO config_layer RECORDS {_id: 5};
  COMMIT;

  BEGIN READ WRITE WITH (SYSTEM_TIME = DATE '2024-01-12');
    INSERT INTO config_layer RECORDS {_id: 5, config: 'e'};
  COMMIT;

  BEGIN READ WRITE WITH (SYSTEM_TIME = DATE '2024-01-13');
    INSERT INTO config_layer RECORDS {_id: 5, config: 'f', _valid_to: DATE '2024-01-14'};
  COMMIT;

You can then use XT's built in OVERLAPS and period-intersection (*) as follows:

SETTING DEFAULT VALID_TIME ALL
SELECT d._id device_id,
       c.config AS config_layer_id,
       d._valid_time * c._valid_time AS valid_time
FROM device d
  JOIN config_layer c
    ON d._id = c._id
      AND d._valid_time OVERLAPS c._valid_time

which I can confirm returns the same results as your original setup 🙂

Again, depending on your real-world scenario, you might be even able to inline the config field in the device table?

HTH!

James

[refset]

Just spotted that QuestDB has a SPLICE JOIN which seems relevant https://questdb.com/docs/reference/sql/join/#splice-join

SPLICE JOIN is a full ASOF JOIN. It will return all the records from both tables. For each record from left table splice join will find prevailing record from right table and for each record from right table - prevailing record from left table.

[refset]

Relevant paper: Extending the kernel of a relational DBMS with comprehensive support for
sequenced temporal queries - plus the related project: https://tpg.inf.unibz.it/demo (by Jensen and others)

They introduce a few new bits of SQL syntax, crucially including LEFT PERIOD JOIN that I think could boil your original formulation down to:

SETTING DEFAULT VALID_TIME ALL

SELECT 
  device._id AS device_id,
  config_layer._id AS config_layer_id,
  valid_time,
  ROW_NUMBER() OVER (
    PARTITION BY device._id, valid_time
    ORDER BY 
      config_layer._system_from DESC NULLS LAST,
      config_layer._id
  ) AS rn
FROM (
  device 
  LEFT PERIOD JOIN WITH (_valid_time, _valid_time) AS (valid_time)
  config_layer 
  ON device._id = config_layer.device_id
) x
WHERE rn = 1
ORDER BY device_id, LOWER(valid_time);

If we added our own LATEST BY modifier to LEFT PERIOD JOIN (to handle conflicts) it could cut it down further still:

SETTING DEFAULT VALID_TIME ALL

SELECT 
  device._id AS device_id,
  config_layer._id AS config_layer_id,
  valid_time
FROM (
  device 
  LEFT PERIOD JOIN WITH (_valid_time, _valid_time) AS (valid_time)
    LATEST BY _system_from
  config_layer ON device._id = config_layer.device_id
)
ORDER BY device_id, LOWER(valid_time);