Building a Bitemporal Index (part 1): A Taxonomy of Bitemporal Data

Our latest XTDB release is probably the biggest yet in the 2.x early-access programme - through a significant change to our underlying indices, we now have vastly improved support for time-series data.

XTDB has (until this point) largely targeted "systems of record" - applications where preserving the full history of data, including both when facts were recorded and when they were valid in the real world, is essential. These systems demand traceability, auditability, and the ability to answer questions like "what did we know, and when did we know it?".

Throughout this time, though, we’ve had a number of users ask us about whether XT was a time-series database - to the extent that we’ve thoroughly polished our explanation of "how a bitemporal system-of-record has very different write/access patterns to time-series data". After a while, though, if enough people mention it, you really have to ask yourself whether you’re doing the right thing.

So we did - and after many hours in front of a whiteboard, I’m really pleased to announce that XT will now additionally handle time-series shaped data!

This post is the first of a three-part series explaining the analysis that went into this change, as well as the implementation required to both performantly index and query this data. In particular, this post outlines a taxonomy of bitemporal data, and how we evaluated potential solutions; subsequent posts will expand further on our eventual solution.

Why do you need to use a database with bitemporality baked in anyway?

One of our main differentiators in XTDB is that we’ve built a database that, from day one, pragmatically understands the practical implications of temporal data - how it’s written, and how it’s queried.

SQL:2011 has been great in bringing bitemporality to a wider market, but it’s a standard that is very much constrained by the history of relational databases. It is no doubt a monumental effort to retro-fit this to existing databases - both for end-users adding temporal columns to existing tables, and for database implementors trying to make this efficient in decades-old C codebases.

If you (again, either as an end-user or a database implementor) are doing it manually, you tend to have an otherwise normal table with four extra columns: valid_from, valid_to, system_from and system_to.

When you insert into/update these tables, you need to ensure that you’ve updated the affected rows correctly - it is no longer just a case of inserting a row, or updating the value in a single column. You have to identify the current row, update its system_to, duplicate the row to reflect the fact that, in the past, you thought that this row would be valid forever, and then insert your new row:

> SELECT _valid_from, _valid_to, _system_from, _system_to, title, family_name
> FROM people FOR ALL VALID_TIME FOR ALL SYSTEM_TIME
> WHERE _id = 'maria';

 _valid_from |  _valid_to  | _system_from | _system_to | title | family_name
-------------+-------------+--------------+------------+-------+-------------
 2025-04-01  | ¤           | 2025-04-01   | ¤          | Miss  | Smith
(1 row)

> -- some time later (congratulations Maria!)
> UPDATE people SET title = 'Mrs', family_name = 'Jones' WHERE _id = 'maria';

> SELECT _valid_from, _valid_to, _system_from, _system_to, title, family_name
> FROM people FOR ALL VALID_TIME FOR ALL SYSTEM_TIME
> WHERE _id = 'maria';

 _valid_from |  _valid_to  | _system_from | _system_to | title | family_name
-------------+-------------+--------------+------------+-------+-------------
 2025-04-01  | 2025-04-12  | 2025-04-01   | ¤          | Miss  | Smith
 2025-04-12  | ¤           | 2025-04-01   | 2025-04-12 | Miss  | Smith
 2025-04-12  | ¤           | 2025-04-12   | ¤          | Mrs   | Jones
(3 rows)

When you query these tables, you need to efficiently filter out data that doesn’t match the period of time that you’re interested in; when you join between temporal tables, you need to ensure that facts from both tables were true at the same time.

It won’t surprise you to know that XTDB, as a bitemporal-aware database:

doesn’t actually perform this rigmarole on INSERT/UPDATE - we simply append the novelty as an event.
chooses a more efficient representation to store this data (i.e. without needless row duplication)
uses its built-in understanding of the distinction between current and historical data to partition data on disk, in such a way that we spend barely any time filtering out historical data for as-of-now queries.

Next time you’re designing history tables, implementing triggers, or writing views to achieve this, consider: maybe there’s an easier way!

What does bitemporal data look like, in practice?

Before embarking on such a significant change, we decided to enumerate our evaluation criteria, in order to assess potential solutions against each other.

Query filters

Our first dimension here was query filtering: what filters do queries tend to employ, and which ones should we prioritise?

We further split this into 'content' filters and 'temporal' filters. We identified the following content filters, ordered here by selectivity:

Primary Key (PK) - one row
Unique/near unique key - e.g. lookup by email, ~1 row
'Selective attribute' - e.g. filter by town in the UK, N/1000 rows
'Unselective attribute' - e.g. filter by region of the world, N/6 rows
Full table scan - N rows

In this iteration, we didn’t go much further into the implications of content filtering, because we already have reasonable support - this is one to further optimise in a future release.

For temporal filters, we identified the following:

Both valid-time (VT) and system-time (ST) as of now
VT as of a certain time, ST as of now
VT within a time range/all time, ST as of now
ST as of a certain time
ST range/all-time

Here, unlike the content filters, these are very much ordered in terms of priority - both because the overwhelming majority of queries against a database are in category 1, but also because the latency requirements of the latter categories tend to be much more relaxed compared to the earlier ones - audit/analytical queries vs more transactional queries.

Notably, too, there is an asymmetry between valid-time and system-time - system-time is nearly always queried as-of-now, in order to query the data 'as best known' (even if we’re interested in what we currently know about the past). When users query into the system-time past, they are explicitly asking for the state of the world without corrections - "what did we know at that time?" - whereas querying at system-time as-of-now is asking for the corrected history.

(There is also an asymmetry in what users are allowed to do with valid-time and system-time - system-time is fixed by the database and cannot be modified by users; valid-time can be overridden by users to the time that the fact was valid in their business domain.)

Update characteristics/'personas'

Depending on the use case, temporal data can vary hugely in terms of how it is updated in practice - we needed some way of comparing different solutions and understanding their impact on each of these use cases.

We settled on three main questions:

Cardinality: how many distinct entities are there? what’s the growth rate (i.e. how many new entities do we insert)?
Updates: how many times is each entity updated, over its lifetime?
Bitemporality: what’s the validity of a given version of each entity?

More generally, we have two assumptions:

Most data is inserted at valid-time ≈ system-time - if they’re not exactly equal, there’s usually only going to be a short delay between a fact becoming valid in the real world and it entering the database.
Data is rarely updated at the same valid-time more than once or twice. This most often happens when some data has been erroneously inserted (a typo, maybe), and then quickly corrected - how many mistakes can you make inserting one piece of data?!

Ok, let’s take a look at the cases:

User profiles/employee records

Cardinality: moderate, slow-growing
Updates: Not loads, most of them valid from now until corrected (now → ∞)
Some retroactive and scheduled updates

Trade/order data (also social media posts/tweets/Xits/whatever they’re called these days)

High, fast growing cardinality
Updates form a state machine:
- updates biased towards recently inserted entries, each update has VT = now → ∞
- eventually reach a final state which then remains valid indefinitely

IoT readings

Low/moderate and relatively static cardinality - we advise that users represent each sensor (for example) as one entity with one primary key.
Very high update frequency (still VT ≈ ST though)
Each version entered with a very short, bounded VT period (maybe even 1µs). To get previous readings of a sensor, you then make use of the valid-time history - e.g. SELECT * FROM readings FOR VALID_TIME AS OF ? WHERE _id = 'sensor-id'.

Pricing feed data

Similar to IoT readings: low/moderate and relatively static cardinality. In this case, we’d recommend each stock ticker (for example) having its own entity with a primary key (e.g. the history of the MSFT share price would be contained in one entity).
Very high update frequency
In contrast to IoT readings, each new price would be valid until corrected (now → ∞) - just that each version is expected to be quickly superseded by the next one.

Static reference data

Probably the least taxing of the lot - low and static cardinality, low update frequency.
Frequently access + small → likely to be fully cached

Go on then - what cases have we missed? 😅

Coming up…

In part two, we’ll talk about how we avoid storing the fully materialized bitemporal state - an algorithm we refer to as 'bitemporal resolution'.

In part three, we’ll talk about how we partition the data in object storage so that we can quickly rule out as much data as possible when querying a bitemporal table.

Please do come join us in the comments!