The last good reason for an rdb: the return of the attribute

This is part three in my “no stinking rdbs” trilogy.  In part one I argued that you might not need rdbs and in part two I provided a TorQ pack to help you do without them.  If you haven’t read these two posts I’d recommend giving them at least a quick skim, as in this post I’m going to build on the arguments made there.

I’ll start on something of a tangent: I recently listened to a podcast about the new runtime for k4, l.  First of all I have a deep respect for these guys putting together a podcast that’s made it so far on such an incredibly niche topic.  It’s interesting listening for dorks like me.  I was reminded listening to this episode of how much of the appeal of kdb+, and this whole family of languages, is their purity, their succinctness, and how much thought fits in such a small space.  This is why I enjoy them too.

One thing that has always bothered me, though, is we take a language like kdb+ and layer complex architectures on top of it.  More and more processes, and complex interlocking relationships between them.  We take a language where you can often hold a whole program in your head, and build architectures on top so complex you often can’t.

The one gap

In the last two posts the core of my argument was that you might not have to sacrifice much performance to get simpler architectures.  Honestly, I would probably sacrifice more performance than most in the name of simplicity,  but I still stopped short of arguing that no-rdb architectures should be the default.  The main reason being the index: rdbs can have attributed (indexed) columns, live data on disk cannot.  There are many queries where this doesn’t matter for performance, but there are some where it matters a lot.

Before I go further I should be clear what attributes I’m talking about here.  The attributes that really matter for performance in kdb+ are `p# and `g#.  These two are very similar in nature to “traditional” database indices: they build an actual index structure alongside the data (`s# and `u# are less like indices and more like properties of the data).  And `p# requires the data to be sorted, so isn’t useful for live data.  So from here on out when I refer to indices or attributes I generally mean `g#.

So why can’t we keep on-disk attributes on append?

The attribute flag sits in the file header; the index it points at is a footer, after the data. Every append would move both of its ends.  kdb+’s answer is to silently drop the attribute rather than rewrite a structure other processes have mapped.  And you cannot simply put it back yourself.  It comes back with a different start, a different size and a different end, so any reader mapping it now has three separate ways to be wrong. As it stands `g# is just not an appendable structure on disk.

So could you design an index that is appendable on disk? In principle, yes, plenty of other similar databases have.  The natural way to do it would be to separate the index into a separate file, away from the data.  The problem isn’t so much creating the structure as integrating it with the rest of kdb+.  It would have to be understood by every surface in kdb+ that currently knows what an attribute is:

• the where-clause
• grouping and aggregation
• aj
• the .Q machinery
• meta
• etc.

You would likely have to hack into each of these separately and it would get messy pretty fast, and you’d lose the thing that makes attributes worth having: that they’re invisible, and every query just gets faster without being rewritten.

An in-memory index over data on disk

So what can we do here, how do we get appendable attributes for on-disk data?  Well, it turns out we can combine two things:

• Columns in memory with attributes are appendable.  In memory the attribute is stored differently and maintained when you append data.  The process owns this memory, it isn’t mapping it from disk
• And when you use .Q.MAP[] kdb+ builds an internal nested dictionary .Q.pm which maps each partition of each table to a list of individual memory-mapped columns from disk, that is exposed to the user and can be modified

Here is the key observation: each .Q.pm slot is just a map of column names to the memory-mapped vector from disk, but nothing requires each of these columns to be mapped from disk: we can swap them out for columns resident in the process’s own memory.  We can splice in one attributed in-memory column into a table that’s otherwise entirely memory mapped from disk.  And because we’re composing the table itself from a combo of in-memory and mapped data, it’s completely transparent to the core engine.  No lookup layer, no re-written queries, and all the performance wins.

What you end up with is an in-memory index over bulk data on disk. That’s much closer to how other databases work: the index lives in its own structure, separate from the data, and gets cached in memory when it’s hot. kdb+ is the unusual one in welding the index into the same file as the column. Everything stays in the page cache and is shared between processes, except the indexed column.

We’ve now added this feature to our no-rdb starter pack as a flag usememattr that you can easily switch on and off.  The copied attributed column is derived from the disk file itself each flush, appending only the new rows (the delta). No second source of truth, no writer changes, no IPC.  Indexed columns come from sort.csv the same file EOD already uses to place `p#, so live and historical indexing stay in lockstep by construction.

For now this option defaults to off and is opt-in per process, as it’s somewhat experimental. It’s worth noting at this point that .Q.pm is not mentioned on the in the kdb+ documentation at all, so we’re heavily leveraging an undocumented feature.  KX also don’t recommend .Q.MAP on compressed data.  This is probably worth a post of its own, so we’ll try to follow up on this.

Does this really work?

All of these numbers come directly from the TorQ no-rdb pack, so you can easily reproduce them yourself, or see more detailed numbers in the attached README.  As you can see this almost completely eliminates the rdb’s performance advantage.  That’s the real takeaway here, so let’s say it again: if you bring the attributed columns into memory like this you get essentially full rdb performance, while only paying the cost of keeping those columns (and their attributes) in memory.  So full rdb performance for a fraction of the rdb memory cost, and we still have the option of running additional db processes without the new flag, keeping the essentially free scalability mentioned in the first two posts.

As covered in the last two posts, the main reason to reach for an rdb over on-disk data was the index. If you’re happy to leverage .Q.pm as described here, that last objection is now solved. If you take advantage of this to build no-rdb architectures, what you get back is a system about as small as the language that runs it: one core process type, one database, and an architecture you can still hold in your head, with minmal performance cost.

Try it

I’m certainly not claiming this is the one correct way, as I said in my previous posts one of the real strengths of kdb+ is its architectural flexibility, but I think with this option the default deserves serious re-examinination. Feel free to download our pack and try it out. Let us know what you think!