[BLOG] Building a bitemporal index, part 2: Bitemporal Resolution

[jarohen]

I hereby coin "Henderson's Tenth Law":

"any sufficiently complicated data system contains an ad-hoc, informally-specified, bug-ridden, slow implementation of half of a bitemporal database".

(with apologies to Greenspun, obviously)

In this blog, we dive into the heart of XTDB's temporal engine, and understand the performance and efficiency gains you get when your database fundamentally understands how real-life data behaves over time, rather than trying to replicate the same in a traditional SQL database, using extra columns, history tables, triggers, etc etc.

https://xtdb.com/blog/building-a-bitemp-index-2-resolution

For part 1 - a pragmatic tour of how data tends to behave over time - see #4399

Cheers,

James

[nicchristeller]

Very interesting read, thank you!

I'm interested in how users of xtdb manage to (efficiently) find an upper bound for "valid time" for the append-only log when "out of order" data is considered.

To follow your example, let's say I had a data source reporting some "version" as it changes over time (a "snapshot" of the value at specific times). All we receive from the source is the version and the timestamp at which that version was checked and reported to be valid.

I'd imagine the "sensor data" use-case described in Part 3 would have similar data.

measurement_time	version
T1	1
T3	3

Meaning we know that the thing was at version 1 at T1, and version 3 at T3.

In your append only log, it sounds like we might see

system_from	valid_time	version
T1	T1 → ∞	1
T3	T3 → ∞	3

But now at T4 we receive the data

measurement_time	version
T2	2

My confusion is that this measurement makes no claim as to its validity period.

The measurement taken at T2 should be "valid" until the next measurement.

So the below log is not correct.

system_from	valid_time	version
T1	T1 → ∞	1
T3	T3 → ∞	3
T4	T2 → ∞	2

Instead, version 2 should have a valid range of T2 → T3 only. Which means it needs to be inserted with a _valid_to set explicitly.

There's certainly nothing stopping us from looking up what this upper-bound should be at insert time. But now this temporal-aware logic is pushed into the application. And if I'm writing a batch of data, I now have to search both within the batch as well as within the data on disk to find what _valid_to should be.

I'd love to hear your thoughts on this - is there a way that my application wouldn't have to be aware of such cases, and could just blindly insert the data without any reads? Have I misunderstood something here?

[nicchristeller]

Thanks for the thoughts @refset!

My question I think is more from the usage perspective, but it is interesting to hear more about the implementation!

My example above is that there are 3 data packets: version=1 @ T1, version=2 @ T2, and version=3 @ T3. But I can't see how my application can avoid temporal-aware logic if I don't have guarantees on in-order processing of these packets (in this example, the row for version=2 is received only at T4 after the row for version=3).

you shouldn't normally need to be concerned about setting _valid_to explicitly

I think I am required to set _valid_to for such "out of order" data, not just for performance but for correctness:

• For INSERTs: "By default, the document will be inserted for valid-time between now and end-of-time".
• But in my example I explicitly do not want the value (version=2) inserted at T4 to be valid till end-of-time.
  • (I want it to be valid until the next row [in valid time] becomes valid).
• So, I must set _valid_to on the row inserted at T4, otherwise the row inserted at T3 (version=3) is completely superseded.

So when thinking about this issue, I was hoping there could be some way to express this ("I want it to be valid until the next row [in valid time] becomes valid") natively on INSERT in xtdb, so that my application wouldn't need to understand the temporality.

[refset]

Ah, sincere apologies @nicchristeller I failed to read and digest your actual question 🙈

It's a good question though! The short answer is that such a transaction statement does need the _valid_to supplied explicitly and literally - otherwise the rest of the timeline gets clobbered, as you correctly noted. Right now there's no means of expressing the update you're looking for in a single statement (or multi-statement transaction).

Ideally it might at least be possible to run a SELECT subquery within an INSERT that can retrieve the right _valid_to but our DML doesn't support subqueries like that currently.

Can you say more about your use case? Particularly, how these data source versions are generated and why they end up out of order in the first instance? I'm struggling to imagine how that workload comes to be. Or at least a workload where the roundtrip through the application layer isn't a good idea anyway (e.g. one-off corrections due to some bad ETL pipeline)

In the extreme case you could consider modelling such data using separate rows altogether (different IDs), as it sounds like the definition of 'current version' may actually be ambiguous, and the system may need to capture and represent that ambiguity.

[nicchristeller]

My example was just following that from the blog.

However my experience with various ELT data pipelines is that such "out of order" data has various causes or use cases, e.g.

• data sources with poor delivery guarantees (e.g. data packets from vehicles sending over 4g)
• "back filling" historical batches of data after more recent data has already been processed
• as you mentioned, precise data corrections after mistakes are noticed

Frankly I haven't dealt with many cases where such data doesn't need to be considered.

But yes, as mentioned in the OP it's not like these can't be supported at the application layer.

Hypothetically I could imagine an INSERT operation in a bitemporal DB to allow _valid_to to be set to any of (end of time, specific value, unknown) where that last option is handled as per my wish above ("valid until the next row [in valid time] becomes valid").

Personally I'm handling this in my current work by setting only a _valid_from on write (similar to how xtbd writes only a _system_from). It means I can support out-of-order data (because the _valid_to is implicit and calculated at read time), but means I lose some other features (e.g. I can't specify an explicit _valid_to for data, but this isn't something I've found I need).

[refset]

Thanks for the explanations. Leaving _valid_to as implicit/derived was actually how XTDB v1 was working at one point, but it greatly complicates everything (especially 'corrections'). I vaguely recall Richard Snodgrass argued clearly in favour of having explicit _valid_to but I don't have a specific reference to hand (no doubt it is discussed somewhere within https://www2.cs.arizona.edu/~rts/tdbbook.pdf)

Adding optional "until changed" semantics (a.k.a. "valid until the next row [in valid time] becomes valid") on top of our logical model should be very possible (not sure if we would add DML syntax for it 🤔), but it will require reads to resolve valid-tos regardless (still, better than a roundtrip to the application!). Although the underlying storage model is relying on a similar "until changed" view of the world, I don't think the work of the resolution step for valid-to can be skipped.

[nicchristeller]

Point-in-time corrections are straightforward, e.g. "this specific row previously had an incorrect value".

But corrections of the form "this value should have been X between these dates" are definitely complicated.

I'll have to do some more reading. Thanks for your responses, it has been interesting!