Take the 2-minute tour ×
Database Administrators Stack Exchange is a question and answer site for database professionals who wish to improve their database skills and learn from others in the community. It's 100% free, no registration required.

I have some data that changes over time. To represent this, my tables have a valid_range column that stores the time-range when the row was valid. Here I'm using a range of ints to simplify things.

CREATE TABLE person (identity_id INT, first VARCHAR, middle VARCHAR, last VARCHAR, valid_range INT4RANGE);

-- optional, prevents overlapping valid_ranges. create the btree_gist
-- extension for it to work
ALTER TABLE person ADD CONSTRAINT temporal_pk EXCLUDE USING GIST (
  identity_id with =,
  valid_range with &&
);

INSERT INTO person VALUES
  (1, 'Jane', NULL, 'Doe', '(,1)'),
  (1, 'Jane', 'BirdMan', 'Doe', '[1,)'),
  (2, 'John', NULL, 'Doe', '(,)');

I have a report over this data that uses DISTINCT. By filtering on the valid_range column, I can get the results of the report as the were at different times.

SELECT DISTINCT ON (last) *
FROM person
WHERE valid_range @> 0
ORDER BY last, first;

 identity_id | first | middle | last | valid_range 
-------------+-------+--------+------+-------------
           1 | Jane  |        | Doe  | (,1)

SELECT DISTINCT ON (last) *
FROM person
WHERE valid_range @> 2
ORDER BY last, first:


 identity_id | first | middle  | last | valid_range 
-------------+-------+---------+------+-------------
           1 | Jane  | BirdMan | Doe  | [1,)

This all works well. The tricky part now is that I need to query the 'history' of the report. In this case, I need to know that the middle name changed to 'BirdMan' at time 1. Without DISTINCT, this is easy -- just remove the valid_range @> condition. This doesn't work with DISTINCT, because we'd only get one row back, not the entire history.

SELECT DISTINCT ON (last) *
FROM person
ORDER BY last, first;

-- not helpful
 identity_id | first | middle | last | valid_range 
-------------+-------+--------+------+-------------
           1 | Jane  |        | Doe  | (,1)

In order to implement this correctly, my first instinct was to reimplement DISTINCT, which feels hostile to relational algebra, with something more friendly. This is possible with an antijoin where we join the row that removes us from the report.

SELECT a.*
FROM person a
LEFT JOIN person b ON (a.last = b.last and a.first > b.first)
-- antijoin to replace DISTINCT. b is the row that took precedence in the
-- report, so a is only in the report if no other row took precedence.
WHERE b.last IS NULL
   AND a.valid_range @> 0; -- or 2, etc

At first glance, this even works for history:

SELECT *
FROM person a
LEFT JOIN person b ON (a.last = b.last and a.first > b.first);


-- the rows that have the second half of the columns are the ones that are
-- invalid.
 identity_id | first | middle  | last | valid_range | identity_id | first | middle  | last | valid_range 
-------------+-------+---------+------+-------------+-------------+-------+---------+------+-------------
           1 | Jane  |         | Doe  | (,1)        |             |       |         |      | 
           1 | Jane  | BirdMan | Doe  | [1,)        |             |       |         |      | 
           2 | John  |         | Doe  | (,)         |           1 | Jane  | BirdMan | Doe  | [1,)
           2 | John  |         | Doe  | (,)         |           1 | Jane  |         | Doe  | (,1)

However, this doesn't actually work. Here are some test cases.

DELETE FROM person;
INSERT INTO person VALUES
  (1, 'John', NULL, 'Doe', '(,)'),
  (2, 'Jane', NULL, 'Doe', '[1,)');

Here, first the report uses John, then at time 1 he's replaced by Jane (because her name comes first in alphabetical order).

SELECT *                   
FROM person a
LEFT JOIN person b ON (a.last = b.last and a.first > b.first);

 identity_id | first | middle | last | valid_range | identity_id | first | middle | last | valid_range 
-------------+-------+--------+------+-------------+-------------+-------+--------+------+-------------
           1 | John  |        | Doe  | (,)         |           2 | Jane  |        | Doe  | [1,)
           2 | Jane  |        | Doe  | [1,)        |             |       |        |      | 

Hmm. The first row isn't actually completely invalid, even though it has a matching b. a's valid range is actually determined by 'subtracting' b's valid range:

SELECT a.identity_id, a.first, a.middle, a.last, a.valid_range - COALESCE(b.valid_range, 'empty') AS "valid_range"
FROM person a
LEFT JOIN person b ON (a.last = b.last and a.first > b.first);


 identity_id | first | middle | last | valid_range 
-------------+-------+--------+------+-------------
           1 | John  |        | Doe  | (,1)
           2 | Jane  |        | Doe  | [1,)

Exactly what we need. There are some problems though. Subtracting ranges doesn't always work: [0,5) - [1,2) produces two ranges as a result: [0,1) and [2, 3). This is nasty because it means a single row from our join needs to produce 0, 1, or 2 rows in the history. This is possible, but it's not pretty.

a also isn't always invalidated by a single row. Different rows can invalidate it at different times. Now consider this data:

DELETE FROM person;
INSERT INTO person VALUES
  (1, 'Jane', NULL, 'Doe', '(,1)'),
  (1, 'Jane', 'BirdMan', 'Doe', '[1,)'),
  (2, 'John', NULL, 'Doe', '(,)');


SELECT *, a.valid_range - COALESCE(b.valid_range, 'empty') AS "calculated_valid_range"
FROM person a 
LEFT JOIN person b ON (a.last = b.last and a.first > b.first);


 identity_id | first | middle  | last | valid_range | identity_id | first | middle  | last | valid_range | calculated_valid_range 
-------------+-------+---------+------+-------------+-------------+-------+---------+------+-------------+------------------------
           1 | Jane  |         | Doe  | (,1)        |             |       |         |      |             | (,1)
           1 | Jane  | BirdMan | Doe  | [1,)        |             |       |         |      |             | [1,)
           2 | John  |         | Doe  | (,)         |           1 | Jane  | BirdMan | Doe  | [1,)        | (,1)
           2 | John  |         | Doe  | (,)         |           1 | Jane  |         | Doe  | (,1)        | [1,)

Now our left join is producing more than we expected -- John is in the history twice, because he's invalidated by different rows at different times. If we only consider a single Jane record at a time, it looks like John will actually appear in the result, which is never true.

I left out a small detail -- our LEFT JOIN condition actually also includes a a.valid_range && b.valid_range condition, to filter out rows that were never valid at the same time.

How do we get the history for a report that uses DISTINCT?

Some miscellaneous ideas I've had:

  • GROUP BY a.*; and array_agg(b.valid_range). Do the subtraction of every b.valid_range from a.valid_range in application code.
  • Try to join again to get every invalidating row. This doesn't work because there can be an arbitrary number of them.
  • Figure out another with to express DISTINCT with relational algebra.

Another test case:

DELETE FROM person;
INSERT INTO person VALUES
  (1, 'John', NULL, 'Doe', '(,)'),
  (2, 'Jane', NULL, 'Doe', '[1,2)');

-- desired output
 identity_id | first | middle | last | valid_range 
-------------+-------+--------+------+-------------
           1 | John  |        | Doe  | (,1)
           2 | Jane  |        | Doe  | [1,2)
           1 | John  |        | Doe  | [2,)
INSERT INTO person VALUES
  (3, 'Alice', NULL, 'Doe', '[4,5)');

-- Desired output. John actually needs 3 entries in the history!
 identity_id | first | middle | last | valid_range 
-------------+-------+--------+------+-------------
           1 | John  |        | Doe  | (,1)
           2 | Jane  |        | Doe  | [1,2)
           1 | John  |        | Doe  | [2,4)
           3 | Alice |        | Doe  | [4,5)
           1 | John  |        | Doe  | [5,)

We can use array_agg in our join to get a list of all the times the base row is invalid:

SELECT a.identity_id, a.first, a.last, a.middle, a.valid_range, array_agg(b.valid_range) AS "invalid_ranges"
FROM person a
LEFT JOIN person b ON (a.last = b.last and a.first > b.first AND a.valid_range && b.valid_range)
GROUP BY a.identity_id, a.first, a.last, a.middle, a.valid_range;


-- We have each row along with an array of the times were it's invalid! If
-- we could just subtract each of the invalid_ranges from valid_range, and make a
-- row for each result, we'd be done.
 identity_id | first | middle | last | valid_range |  invalid_ranges   
-------------+-------+--------+------+-------------+-------------------
           1 | John  |        | Doe  | (,)         | {"[1,2)","[4,5)"}
           2 | Jane  |        | Doe  | [1,2)       | {NULL}
           3 | Alice |        | Doe  | [4,5)       | {NULL}

Would UNNEST or LATERAL JOIN help us at all here?

share|improve this question
    
If you want history, doesn't the simple work?: SELECT * FROM person ORDER BY identity_id, lower(valid_range); –  ypercube May 1 at 18:29
    
In short, I can't make what exactly you are after. Instead of what does not work, can you add in the question what output exactly you want from the sample rows you have? –  ypercube May 1 at 18:34
    
No, that would include history for rows never included in the report (because they were never distinct). Also it would included history for rows that were in the report at some time, but all the time. –  Gavin Wahl May 1 at 19:39
    
The second-to-last sql block gives the desired output (but calculated in the wrong way), and the last sql block would be correct if the last two rows (where the join condition matched) were removed. –  Gavin Wahl May 1 at 19:45
    
What should be the result if John is (,) and both Jane and Alice have [1,2)? –  ypercube May 1 at 22:08

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.