Database Stats

I just landed a large commit in gSuneido to add database stats (metadata) and use them for query optimization. (It probably should have been multiple commits, but I kept thinking I almost had it finished. Typically, I was 90% finished for quite a long time!)

A while ago I had implemented several algorithms/data structures to use for this:

• HLL (HyperLogLog) for cardinality (the number of distinct values)
• KLL (Karnin, Lang, Liberty) for approximate quantiles used to determine the size of ranges of values (my blog post)
• SS (Space Saving) for most frequent values (top-k) aka "heavy hitters"

The first question is which table columns do you gather stats for? All of them would be too much data and much of it unused. We only need stats for commonly used columns on large tables. So the first step is to use an SS sketch weighted by table size to track these "hot" columns. This can be accumulated in memory and periodically written to disk. It could go in the database itself, but I chose to write it to a text file to keep it separate.

The next question is when do you actually collect the data stats? The obvious time for Suneido is during compaction (usually weekly) which has to process all the data anyway. So it reads the text file of hot columns and for each one collects HLL, KLL, and SS.

To avoid overhead (and complexity) I chose not to try to update the stats with data updates. This means the stats can get slightly out of date, but generally one week's changes do not substantially affect the statistics on big tables.

Once we have the stats we can actually do the functional part of this whole setup - use them to help with query optimization, in particular to help choose indexes for WHERE clauses. I ended up overhauling this part of the code so it could cleanly incorporate the extra information.

One thing that wasn't clear at first was how you actually use the HLL, KLL, and SS data to estimate a fraction of the data. This depends on whether the WHERE clause is a single value or whether it's a range. Ranges are simpler - they just use the quantiles. I collect 50 quantiles to give 2% precision. So, for example, if a range covers 3 quantiles, it's 6% of the data.

Single values are a little more involved. First you check SS to see if it's one of the known most common values. If so, that gives you the approximate count and therefore the fraction of the table. If it's not a common value, we calculate the "tail" after subtracting the common values and assume it's 1/N of the tail, where N is the total number of distinct values (from HLL) minus the number of heavy hitters (from SS).

Despite this age of AI, I ended up writing quite a bit of this code the old-fashioned way, by hand. Mostly that was because I was unclear how parts of it should work, which meant I couldn't tell an AI what I wanted. I reverted to working it out as I wrote and rewrote the code. Parts where it was clear what was needed (and explainable) I got AI to write. Even then I refactored most of the AI-written code.

As usual the code is on Github.