Time travel in a database: a Cozo story

You have built a social network. The only thing your users can do on the network is to update their “mood”. For example, user “joe” may be “moody” yesterday, and “happy” today. How is this reflected in the database? In CozoDB, this can be stored in the following relation:

:create status {uid: String => mood: String}

The equivalent SQL for Postgres is

create table status (
    uid text primary key,
    mood text not null
)

Your home page is very simple: it is a gigantic page containing the moods of all the users all at once. To generate it, you run the query:

?[uid, mood] := *status{uid, mood}

select uid, mood from status

And when users want to update their status, you run:

?[uid, mood] <- $input
:put status {uid => mood}

update status 
set mood = $1 
where uid = $2

Simple enough. Now scientists come to you and want to buy your data for their study of the fluctuation of moods during the pandemic. Of course, you know that their real motive is nefarious, so you promptly show them the door. And then start banging your head against the door. Why have you thrown away the history, the most valuable part of your data? WHY?

So you borrow a time machine from a future you and travel back in time to warn the former you. “It’s simple to fix”, the former you says:

:create status {uid: String, ts default now() => mood: String}

create table status (
    uid text not null,
    ts timestamptz not null default now(),
    mood text not null,
    primary key (uid, ts)
)

Of course, now there is no way users can delete their accounts anymore, all they can do is send you more and more updates. Very useful feature!

Now, to generate your homepage:

?[uid, mood] := *status{uid, mood, ts}, ts == now()

select uid, mood from status
where ts = now()

Disaster! The homepage remains forever blank, no matter what the users do!

The problem is that when you generate your homepage, you can only collect data that were inserted in the past. And for past data, the condition ts == now() is never true!

After a lot of fumbling, you find that the following query works:

candidates[uid, max(ts)] := *status{uid, ts}
?[uid, mood] := candidates[uid, ts], *status{uid, ts, mood}

with candidates(uid, ts) as (
    select uid, max(ts) from status
    group by uid
)
select status.uid, status.mood from status
inner join candidates on status.uid = candidates.uid and status.ts = candidates.ts

You first find out what are the timestamps for the latest status for each user, and then use the user ID together with the timestamps to collect the moods.

Now travelling back to a particular time in the past is easy:

candidates[uid, max(ts)] := *status{uid, ts}, ts < $date_ts
?[uid, mood] := candidates[uid, ts], *status{uid, ts, mood}

with candidates(uid, ts) as (
    select uid, max(ts) from status
    where ts < $1
    group by uid
)
select status.uid, status.mood from status
inner join candidates on status.uid = candidates.uid and status.ts = candidates.ts

The cost of time travel

Your social network becomes a runaway success, and the scientists are happy too! As time goes on, however, you notice performance problems, and it gets worse each day.

What’s happening? After all, your network caters only for the students on a certain campus, and even if everyone signed up, there would only be 10,000 users at most. After digging into your data, you notice that some (most?) of your users are hyperactive and update their mood every five minutes during their waking hour. Even though you have only run your service for three months, some of them have already accumulated over 10,000 mood updates!

So for the front-page generating query:

candidates[uid, max(ts)] := *status{uid, ts}
?[uid, mood] := candidates[uid, ts], *status{uid, ts, mood}

with candidates(uid, ts) as (
    select uid, max(ts) from status
    group by uid
)
select status.uid, status.mood from status
inner join candidates on status.uid = candidates.uid and status.ts = candidates.ts

you are doing a full scan of your data to get your results. For 10,000 users and 1,000 updates each (we use the mean number of mood updates, so it’s 1,000 instead of 10,000), that’s 10 million rows. And next year it will become more than one billion rows, since time ticks and you are thinking of expanding your service to other communities.

Dreamy indices

Your investor suggests the “enterprisey” thing: pre-computing the front page and updating it periodically instead of calculating it in real-time. Being a hacker with a big ego, you detest all things “enterprisey” and ask yourself: “is there anything better that can be done?” Your friend, who works in finance, suggests time series databases. “It can handle data from the stock market quite well, so surely it is good enough for your data!” “Just index your data by the timestamp!” Well, unlike stock market indices, your data is sparse: it is not collected at regular intervals for all users in unison. Are you going to materialize these implicit rows so that every time a user updates her mood, everyone else also gets an automatic update? Your cloud provider is very welcoming of this idea and urges you to sign up for their proprietary time series database. Your investor is also kind of supportive since it would make you an instant “big data” company, but worries about whether you can secure additional funding in time to cover the costs. You, ever calm, make some back-of-envelop estimates and give up the idea.

Your investor still wants to talk to you over the phone, but you become very annoyed and go to sleep, clouded in anxiety.

In your dream, you come to a dark, Harry-Potteresque library, with dusty shelves neatly lined up, and on the shelves were … files for the mood of your users at different times, meticulously arranged. The tree backing your database has taken physical form! You walk mechanically to the first shelf, like a robot, and start to collect the mood of every user at midnight some days back.

“Aaron, 2022-09-01, 15:31, too early.”

“Aaron, 2022-09-01, 15:33, still too early.”

…

“Aaron, 2022-12-24, 23:59, still too early.”

“Aaron, 2022-12-25, 00:34, well it’s past the time we want, so the previous item contains the mood.” (The mood is “festive”, by the way.)

“Aaron, 2022-12-25, 00:42, we don’t need this anymore.”

“Aaron, 2022-12-25, 00:47, we don’t need this anymore.”

…

“Aaron, 2022-12-27, 12:31, why are we still looking at Aaron, by the way?”

…

“Bean, 2022-11-27, …”

Two things irked you. First, you are going through the data in the wrong direction, so after you have gone past the expected date, you have to go back and look at the previous record. This is especially annoying since some users signed up only today, and the previous record is someone else’s. Second, you are walking a tree, so why can’t you jump to the next user when you know you are done with a user?

As if triggered by these thoughts, the books pour out of the shelves to form a tornado, swirl all over the library, and after a while return to the shelves. “I have to do this all over again,” you gruntle and walk to the first shelf. But something has changed: you can now directly jump to the beginning, and the records are in a different order, ascending by the user, as before, but descending by the timestamp:

“Aaron, 2022-12-27, 03:38, too late, let’s jump to the book past Aaron, 2022-12-25, 00:00.”

“Aaron, 2022-12-24, 23:59. Now this book contains the required mood for Aaron.” “Let’s now jump to the book past Aaron at the BIG BANG.”

“Bean, 2022-12-24, 23:11, this is already the correct book for Bean, lucky! Now let’s go past Bean at the BIG BANG.” “I wonder what happened to Mr Bean since Christmas Eve?”

…

Suddenly, you wake up. You rush to your computer and write down what you saw, in code.

Back to reality

Eventually, your social network takes over the world and changes it fundamentally, with the simple schema in CozoScript:

:create status {uid: String, ts: Validity default 'ASSERT' => mood: String}

the query for the present:

?[uid, mood] := *status{uid, mood @ 'NOW'}

and the query for historical moments:

?[uid, mood] := *status{uid, mood @ '2019-12-31T23:59:59Z'}

Obviously, there are no longer any SQL translations.

The story ends here. It is the story of the new time travel feature in Cozo v0.4. We have also added a part in the tutorial giving you hands-on experience.

But what about performance?

Real databases care about performance deeply, and at Cozo we do. So let’s do some performance tests, with the same Mac Mini as before: it runs MacOS 13.0.1, has Apple M1 CPUs with 4 performance cores and 4 efficiency cores, 16GB of memory and a pretty fast NVMe SSD storage. We only test against the RocksDB backend for simplicity.

We generated many relations, all of which contain data for 10,000 users. The ‘Plain’ relation stores no history at all. The ‘Naive’ relations store and query history using the naive approach we described in the story. We generated different versions of the naive relations, containing different numbers of mood updates per user. Finally, the ‘Hopping’ relations store and query history using the dream approach we described earlier.

The historical timestamp for the queries is chosen randomly and the results are averaged over many runs.

First, we want to know how history storage affects point query throughput, measured in queries per second (QPS):

Type	# updates per user	QPS	Performance percentage
Plain	1	143956	100.00%
Naive	1	106182	73.76%
Naive	10	92335	64.14%
Naive	100	42665	29.64%
Naive	1000	7154	4.97%
Hopping	1	125913	87.47%
Hopping	10	124959	86.80%
Hopping	100	100947	70.12%
Hopping	1000	102193	70.99%

As we can see, for 1000 updates per user, the naive approach has a 20x reduction in throughput compared to the no history approach. The hopping approach, on the other hand, maintains more than 70% of the original performance.

To be fair, for the simplest kind of point query where you know the complete key and the timestamp and want the result for only a single user, there is a better way to write the query so that the naive approach can achieve a similar performance to the hopping one. We deliberately wrote our query in a way to avoid this optimization, since this optimization may not always be possible, depending on the query.

Next, let’s look at aggregation results where we must go through all users. Now we measure latency instead of throughput:

Type	# updates per user	Latency (ms)	Slowdown ratio
Plain	1	2.38	1.00
Naive	1	8.90	3.74
Naive	10	55.52	23.35
Naive	100	541.01	227.52
Naive	1000	5391.75	2267.53
Hopping	1	9.60	4.04
Hopping	10	9.99	4.20
Hopping	100	39.34	16.55
Hopping	1000	31.41	13.21

Now the naive approach scales badly. For a query that takes only 2ms in a plain relation, it takes more than 5 seconds in a relation with 1000 historical facts per user. The hopping approach, on the other hand, keeps the time complexity under control. Notice that it performs better in the relation with 1000 historical facts per user than in the relation with only 100. This is not a random fluctuation: it occurs consistently no matter how we test it. We guess that the RocksDB backend does something different when a certain threshold is passed.

Nonetheless, it is important to note that there is at least a 3x slowdown no matter how you store the history, even if you only have one historical fact per user. This is the minimal cost of time travel. And this is why Cozo does not automatically keep history for every relation regardless of whether you need it: our philosophy is “zero-cost and zero-mental-overhead abstraction”.

Before we end, let’s remark that some people maintain that data is naturally immutable and hence should always be stored immutably. We do not take this view. Use immutability and time travel only when you really need it. Are we simply collections of data in an immutable database, operated by Laplace’s daemon, perhaps? I hope not, and modern physics certainly says no, no matter how you look at it: whether it is the collapse of the wave function or the dance at the edge of chaos. So immutability is an illusion, or at best a platonic fantasy that we created so that we can make better sense of the world. That’s OK, since we can only understand the world by projecting our models onto the world. Just don’t become the slaves of our own creation and let it slow us down.