2
\$\begingroup\$

I have to store some temporal meta data used primarily in bulk processing of a time-series (sensor measurements).

Each value of this meta data is valid for a potentially half-open range of time.
These valid time ranges can be set up ahead of time, and changed for past periods of times.
This is basically the SQL 2011 "Application-time period tables".

The query performance in this case is a lot more important than the update performance.

I haven't found any existing implementations for PostgreSQL that deal with modifying existing ranges in this manner.

I've tested my implementation below, and it seems to work. Since this is not a trivial algorithm (at least for me), I would appreciate a few more eyeballs on this.

For review:

  • Any edge cases I've overlooked?
  • Is my use of ... FOR UPDATE is adequate to prevent deadlocks? Is it even necessary?
  • Any obvious code smells, missed opportunities?

The table:

CREATE EXTENSION btree_gist;

CREATE TABLE temporal_data (
  id serial PRIMARY KEY,

  data_pos int NOT NULL,
  data_val int NOT NULL,
  valid_range tstzrange NOT NULL,

  EXCLUDE USING gist (data_pos WITH =, valid_range WITH &&),
  EXCLUDE USING gist (data_pos WITH =, data_val WITH =, valid_range WITH -|-),
  CHECK (lower_inc(valid_range) AND NOT upper_inc(valid_range))
);

Set data:

CREATE AGGREGATE my_range_merge(anyrange)
(
  sfunc = range_merge,
  stype = anyrange
);

CREATE OR REPLACE FUNCTION set_data_for_range(
  changed_data_pos int,
  new_data_val int,
  new_valid_range tstzrange) RETURNS void AS $$
DECLARE
  containing_range temporal_data%ROWTYPE;
  extended_range tstzrange;
  skip_to_insert boolean := false;
BEGIN

  -- No need to modify anything: the range is already covered
  IF EXISTS (
    SELECT 1 FROM temporal_data
    WHERE data_pos = changed_data_pos
      AND data_val = new_data_val
      AND valid_range @> new_valid_range
  ) THEN
    RETURN;
  END IF;

  PERFORM 1
  FROM temporal_data
  WHERE data_pos = changed_data_pos
  AND valid_range && new_valid_range
  OR (valid_range -|- new_valid_range AND data_val = new_data_val)
  FOR UPDATE;

  -- Delete anything that will completely be overwritten
  DELETE FROM temporal_data
  WHERE data_pos = changed_data_pos
    AND valid_range <@ new_valid_range;

  -- Resize containing range (if exists) that only extends in one direction (data_val != new_data_val)
  UPDATE temporal_data
  SET valid_range = valid_range - new_valid_range
  WHERE data_pos = changed_data_pos
    AND valid_range @> new_valid_range
    AND (valid_range &< new_valid_range OR valid_range &> new_valid_range);

  IF NOT FOUND THEN
    -- Split up containing range (if exists) that extends in both directions (data_val != new_data_val)
    SELECT * INTO containing_range
    FROM temporal_data
    WHERE data_pos = changed_data_pos
      AND valid_range @> new_valid_range;

    IF FOUND THEN
      UPDATE temporal_data
      SET valid_range = tstzrange(lower(valid_range), lower(new_valid_range))
      WHERE id = containing_range.id;

      INSERT INTO temporal_data (
        data_pos,
        data_val,
        valid_range
      ) VALUES (
        changed_data_pos,
        containing_range.data_val,
        tstzrange(upper(new_valid_range), upper(containing_range.valid_range))
      );

      skip_to_insert := true;
    END IF;
  END IF;

  IF NOT skip_to_insert THEN
    -- Delete overlapping and adjacent ranges with the same value, and extend the input range to cover them
    WITH original_ranges AS (
        DELETE FROM temporal_data
        WHERE data_pos = changed_data_pos
          AND data_val = new_data_val
          AND (valid_range && new_valid_range OR valid_range -|- new_valid_range)
        RETURNING valid_range 
      )
    SELECT my_range_merge(valid_range + new_valid_range)
    INTO extended_range
    FROM original_ranges;

    -- Resize overlapping ranges with different values
    UPDATE temporal_data
    SET valid_range = valid_range - new_valid_range
    WHERE data_pos = changed_data_pos
      AND valid_range && new_valid_range;

  END IF;

  INSERT INTO temporal_data (
    data_pos,
    data_val,
    valid_range
  ) VALUES (
    changed_data_pos,
    new_data_val,
    COALESCE(extended_range, new_valid_range)
  );

END;
$$ LANGUAGE plpgsql;

Clear data:

CREATE OR REPLACE FUNCTION clear_data_from_range(
  changed_data_pos int,
  cleared_valid_range tstzrange) RETURNS void AS $$
DECLARE
  containing_range temporal_data%ROWTYPE;
BEGIN
  -- No need to modify anything: the range has no value
  IF NOT EXISTS (
    SELECT 1 FROM temporal_data
    WHERE data_pos = changed_data_pos
      AND valid_range && cleared_valid_range
  ) THEN
    RETURN;
  END IF;

  PERFORM 1
  FROM temporal_data
  WHERE data_pos = changed_data_pos
  AND valid_range && cleared_valid_range
  FOR UPDATE;

  -- Delete anything that is completely in the cleared range
  DELETE FROM temporal_data
  WHERE data_pos = changed_data_pos
    AND valid_range <@ cleared_valid_range;

  -- Resize overlapping ranges that only extend in one direction
  UPDATE temporal_data
  SET valid_range = valid_range - cleared_valid_range
  WHERE data_pos = changed_data_pos
    AND valid_range && cleared_valid_range
    AND (valid_range &< cleared_valid_range OR valid_range &> cleared_valid_range);

  -- Split up containing range that extends in both directions
  IF NOT FOUND THEN
    SELECT * INTO containing_range
    FROM temporal_data
    WHERE data_pos = changed_data_pos
      AND valid_range @> cleared_valid_range;

    IF FOUND THEN
      UPDATE temporal_data
      SET valid_range = tstzrange(lower(valid_range), lower(cleared_valid_range))
      WHERE id = containing_range.id;

      INSERT INTO temporal_data (
        data_pos,
        data_val,
        valid_range
      ) VALUES (
        changed_data_pos,
        containing_range.data_val,
        tstzrange(upper(cleared_valid_range), upper(containing_range.valid_range))
      );
    END IF;
  END IF;
END;
$$ LANGUAGE plpgsql;

Example usage:

SELECT set_data_for_range(0, 0, '["2018-05-24 00:00:00","2018-05-24 00:30:00")');
SELECT set_data_for_range(0, 1, '["2018-05-24 00:30:00","2018-05-24 01:00:00")');
SELECT * FROM temporal_data ORDER BY valid_range;

SELECT set_data_for_range(0, 0, '["2018-05-24 00:30:00","2018-05-24 00:40:00")');
SELECT * FROM temporal_data ORDER BY valid_range;

SELECT set_data_for_range(0, 1, '["2018-05-24 00:10:00","2018-05-24 00:20:00")');
SELECT * FROM temporal_data ORDER BY valid_range;

SELECT set_data_for_range(0, 0, '["2018-05-24 00:10:00","2018-05-24 00:20:00")');
SELECT * FROM temporal_data ORDER BY valid_range;

SELECT clear_data_from_range(0, '["2018-05-24 00:50:00","2018-05-24 00:55:00")');
SELECT * FROM temporal_data ORDER BY valid_range;

SELECT set_data_for_range(0, 0, '["2018-05-23 23:55:00","2018-05-24 03:00:00")');
SELECT * FROM temporal_data ORDER BY valid_range;
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.