Rhizomes - CRUD

CRUD

So far I have deliberately concentrated on Aggregate Read performance of databases, as that is where I experience most day-to-day database performance problems.

Create Record:

The creation of a new record must add one or more bytes (or increase the value of the last byte) on all of the Rhizomes associated with that record’s values. (One Rhizome per ‘column’ of data being written. The tails of these Rhizomes can be (at worst case) considered to be randomly distributed across the systems drives.

This each write of a n-column record will cause at least n random writes. This is comparable with a traditional database, assuming that half the columns are indexed.

Also, any Cache Rhizomes whose criteria apply to this record must also be modified.

As a rule of thumb, consider a Create operation on a Rhizome based Database to be 1-2x more resource intensive than on a traditional database.


Read Record:

A read of a particular record is equally as fast with Rhizomes as with a traditional database. (There is a tree of values for each Rhizome, analogous to a traditional database’s indexes.) If the read conditions are represented by a Cached Rhizome, performance will be orders of magnitude faster.


Read Multiple Records:

As with the example before, aggregating is typically 10^5 times faster with Rhizomes (on the first request) and 10^8 times faster subsequently. Similar performance can be gained using data-cubes on a traditional database, but these require setup, updating, and tuning.


Update Record:

Rhizomes, because of their linear nature, *cannot* be updated. Any updates must be performed as deletes and creates.


Delete Record:

Deleting a record means removing it’s entry from each Rhizome in which it occurs. To delete the entry from the Rhizome, the following (or preceding) addition has to be made equal to the sum of it and the deleted addition, then padded will nulls.

add:3, increment:x10, add:4, add:8, add:2, …

Deleting the record indicated by the add:4 required changing the Rhizome to:

add:3, increment:x10, add:12, some nulls, add:2, …

Deleting is therefore inefficient and Rhizomes will benefit from having their nulls removed when they become too ‘holey’ (>40%?). This is efficiently done spindle-to-spindle on a multi-spindle system.

Performance of deletions is comparable to traditional databases, which also have to perform several random writes to remove index entries.

Records

So far I have made no mention of records. I have assumed that finding which IDs are matches for a particular query is the main aim here.

I propose (though have neither implemented nor tested this) that Cache Rhizomes are created with Multipart Encoding (nothing to do with MIME).

Formerly, we assumed that each number retrieved from a Rhizome was the increment to the next record whose index matched the Rhizome’s value (or condition).

If we instead interpret interleaving numbers as (integer references to) the values then we have something very close to a clustered index. Again, the challenge here is for the Rhizome Manager to efficiently manage which Clustered Cache Rhizomes to keep or cull.

Records can be stored (as references to symbols) in a very efficient manner. The implementation is trivial.

Rhizomes of Rhizomes

Q: How do I get to the 1,000,000,042nd number in Rhizome?

A: *Only* by reading 1,000,000,041 numbers.

Therefore I propose a system of Rhizomes of Rhizomes.

These contain the offsets of selected numbers.

In this case Rhizome A has 10^9 entries.

If I make a new Rhizome B, which indexes Rhizome A, every 1,000 (or so*) entries, I can get there in between 1,000th and a 500th of the data it would have otherwise taken.

I can the make a new Rhizome C, which indexes Rhizome B, it comes down to between 1,000,000th and a 500,000t,h of the data.



* The 1,000th number might not start on a byte. (It could be in the middle of an instruction to increment.) Therefore it may not have an offset. So we might store the offsets of the 1,004th, the 2,000th, the 3,005th and the 4,000th numbers instead.