Vinyl math

Definitions:

n - total number of tuples stored in vinyl
D - total amount of data stored in vinyl
Mm - memory quota of vinyl in-memory index
Mp - memory spent by page indexes
M = Mm + Mp - total memory quota of vinyl
A = D / n - average tuple size
R - average amount of data in one range
nr = D / R - number of ranges in vinyl
T - average amount of data in in-memory index when it is dumped to disk (new run size)
k - maximal number of runs in one range
p - average number of tuples in page
P = p * A - average amount of data in page
np = D / P - total number of pages in vinyl

Range/run sizes

When in-memory index achieves size T it's dumped to disk to make a new run. When number of run reaches k, they are all merged into one run. If the result run size if greater than R, the range is split to make two ranges. Let's calculate:

Ramp - read amplification, the number of reads (actually of size P)
   from disk that is enough to make a random point select.
   Obviously Ramp = k.
Wamp - write amplification, the amount of data the engine actually writes
   to disk against the amount of useful data that the engine stores

When a range is merged the engine writes R data, and number of runs in the range becomes 1. Merge process will be restarted after dumping (k - 1) more new runs of useful size T. So we can calculate

Wamp = R / T / (k - 1)

Let's remember, what is T. It's a memory limit for one range, and the total limit of memory is Mm

T = Mm / nr = Mm * R / D

So

Wamp = R / (Mm * R / D) / (k - 1) = D / Mm / (k - 1)

That means that if we constantly limit the memory of vinyl and the number of runs in range, the write amplification will grow with the amount of data stored in vinyl. And the time needed to fill up a database of size D will be proportional to D^2

To make Wamp constant we must provide more memory for engine or/and increase average number or runs in range (increasing Ramp proportionally) when database size increases.

That also means that actual R limit does not affect any complexity of read / write.

Run/Page sizes

When a run is written to disk it is split into pages. For every page minimal and maximal keys are stored in page index, that is stored in memory. During search in run normal case is when we read one and only page from disk.

Page index stores two tuples (min and max) in memory for every page, so

Mp = 2 * np * A = 2 * D * A / P = 2 * D / p

Goal 1: We want that every select reads a constant amount of data from disk.

This is simply achieved by fixing desires size if page X in engine settings. But in this case amount if memory needed for page indexes will be proportional to average tuple size. I.e. for every byte of data on disk we'll need such an amount of memory for page indexes:

Mp / D = 2 * A / P = 2 * A / X

Goal 2: We want to limit the amount of memory needed for page to make it at least proportional to D. So we set Mp / D = Y = constant in engine settings, for example Y = 0.05 = 5%.

In this case we just set p = 2 / Y. But average read size from disk will depend on average tuple size:

P = p * A = 2 * A / Y

Goal 3: We want some average behaviour between goal 1 and goal 2

We could let user set both X and Y options and try to make both as true as possible.

P = z * X
Mp / D = 2 * A / P = z * Y
P / X = 2 * A / P / Y
P^2 = 2 * A * X / Y
P = (2 * A * X / Y) ^ 0.5
p = P / A = (2 * X / A / Y) ^ 0.5
P * p = 2 * X / Y

So we could stop writing page and start another when (number of bytes written) * (number of tuples written) reaches threshold 2 * X / Y