17

Context

This question pertains to the low-level implementation details of indexes in both SQL and NoSQL database systems. Actual structure of the index (B+ tree, hash, SSTable, etc.) is irrelevant as the question pertains specifically to the keys stored inside a single node of any of those implementations.

Background

In SQL (e.g. MySQL) and NoSQL (CouchDB, MongoDB, etc.) databases, when you build an index on a column or JSON document field of data, what you are actually causing the database to do is create essentially a sorted list of all those values along with a file offset into the main data file where the record pertaining to that value lives.

(For simplicity sake, I may be hand-waving away other esoteric details of specific impls)

Simple Classic SQL Example

Consider a standard SQL table that has a simple 32-bit int primary key that we create an index on, we will end up with an index on-disk of the integer keys sorted and associated with a 64-bit offset into the data file where the record lives, e.g.:

id   | offset
--------------
1    | 1375
2    | 1413
3    | 1786

The on-disk representation of the keys in the index looks something like this:

[4-bytes][8-bytes] --> 12 bytes for each indexed value

Sticking to standard rules of thumb about optimizing disk I/O with filesystems and database systems, let's say you store keys in 4KB blocks on disk, which means:

4096 bytes / 12 bytes per key = 341 keys per block

Ignoring the overall structure of the index (B+ tree, hash, sorted list, etc.) we read and write blocks of 341 keys at a time into memory and back out to disk as needed.

Example Query

Using the information from the previous section, let's say a query comes in for "id=2", the classic DB index lookup goes as follows:

  1. Read the root of the index (in this case, 1 block)
  2. Binary-search the sorted block to find the key
  3. Get the data file offset from the value
  4. Look up the record in the data file using the offset
  5. Return the data to the caller

Question Setup...

Ok, here is where the question comes together...

Step #2 is the most important part that allows these queries to execute in O(logn) time... the information has to be sorted, BUT you have to be capable of traversing the list in a quick-sort manner... more specifically, you have to be able to jump to well-defined offsets at-will to read in the index key value at that position.

After reading in the block, you have to be able to jump to the 170th position immediately, read the key value and see if what you are looking for is GT or LT that position (and so on and so on...)

The only way you would be able to jump around the data in the block like that is if the key values sizes were all well-defined, like our example above (4-bytes then 8-bytes per key).

QUESTION

Ok, so here is where I am getting stuck with efficient index design... for varchar columns in SQL databases or more specifically, totally free-form fields in document databases like CouchDB or NoSQL, where any field you want to index can be any length how do you implement the key values that are inside the blocks of the index structure you build your indices out of?

For example, let's say you use a sequential counter for an ID in CouchDB and you are indexing tweets... you'll have values that go from "1" to "100,000,000,000" after a few months.

Let's say you build the index on the database on day 1, when there are only 4 tweets in the database, CouchDB might be tempted to use the following construct for the key values inside of the index blocks:

[1-byte][8-bytes] <-- 9 bytes
4096 / 9 = 455 keys per block

At some point this breaks and you need a variable number of bytes to store your key value in the indexes.

The point is even more glaring if you decide to index a really variable-length field like a "tweet_message" or something.

With the key's themselves being totally variable length, and the database having no way to intelligently guess at some "maximum key size" when the index is created and updated, how are these keys actually stored inside the blocks representing segments of the indices in these databases?

Obviously if your keys are variable sized and you read in a block of keys, not only do you have no idea how many keys are actually in the block, but you have no idea how to jump to the middle of the list to do a binary search on them.

This is where I am getting all tripped up.

With static-typed fields in classic SQL databases (like bool, int, char, etc.) I understand the index can just pre-define the key length and stick to it... but in this world of document data stores, I am perplexed how they are efficiently modeling this data on disk such that it can still be scanned in O(logn) time and would appreciate any clarification here.

Please let me know if any clarifications are needed!

Update (Greg's Answer)

Please see my comments attached to Greg's answer. After a week more of research I think he has really stumbled upon a wonderfully simple and performant suggestion that in-practice is dead-easy to implement and use while providing big performance wins on avoiding the deserialization of key values you don't care about.

I have looked into 3 separate DBMS implementations (CouchDB, kivaloo and InnoDB) and all of them handle this issue by deserializing the entire block into the internal data structure before searching the values inside their execution environment (erlang/C).

This is what I think is so brilliant about Greg's suggestion; a normal block size of 2048 would normally have 50 or less offsets, resulting in a very small block of numbers that would need to be read in.

Update (Potential Downsides to Greg's Suggestion)

In order to best continue this dialog with myself, I realized the following downsides to this...

  1. If every "block" is headed with offset data, you couldn't allow the block size to be adjusted in the configuration later down the road as you might end up reading in data that didn't start with a header correctly or a block that contained multiple headers.

  2. If you are indexing huge key values (say someone is trying to index a column of char(8192) or blob(8192)) it is possible that keys do not fit in a single block and need to be overflowed across two blocks side by side. This means your first block would have an offset header and the second block would just immediately begin with key data.

The solution to all of this is having a fixed database block size that is not adjustable and developing header block data structures around it... for example, you fix all block sizes to 4KB (typically the most optimal anyway) and write a very small block header that includes the "block type" at the beginning. If its a normal block, then immediately after the block header should be the offsets header. If its an "overflow" type, then immediately after the block header is raw key data.

Update (Potential awesome up-side)

After the block is read in as a series of bytes and the offsets decoded; technically you could simply encode the key you are searching for to raw bytes and then do direct comparisons on the byte stream.

Once the key you are looking for is found, the pointer can be decoded and followed.

Another awesome side-effect of Greg's idea! The potential for CPU time optimization here is big enough that setting a fixed block size might be worth it just to gain all of this.

2
  • For anyone else interested in this topic, Redis's lead dev was running into this exact issue while trying to implement the defunct "disk store" component for Redis. He originally opted for a "big enough" static key size of 32-bytes but realized the potential for problems and instead opted to go with storing the hash of the keys (sha1 or md5) just to have a consistent size. This kills the ability to do ranged queries, but it does balance the tree nicely FWIW. Details here redis.hackyhack.net/2011-01-12.html Jan 21, 2012 at 19:08
  • Some more info I found. It looks like SQLite has a cap on how big the keys can get or it actually truncates the key value at some upper bound and puts the remainder in an "overflow page" on disk. This can make queries for huge keys horrific as the random i/o doubles. Scroll down to the "B-tree pages" section here sqlite.org/fileformat2.html Jan 22, 2012 at 21:00

1 Answer 1

9

You can store your index as a list of fixed-size offsets into the block containing your key data. For example:

+--------------+
| 3            | number of entries
+--------------+
| 16           | offset of first key data
+--------------+
| 24           | offset of second key data
+--------------+
| 39           | offset of third key data
+--------------+
| key one |
+----------------+
| key number two |
+-----------------------+
| this is the third key |
+-----------------------+

(well, the key data would be sorted in a real example, but you get the idea).

Note that this does not necessarily reflect how index blocks are actually constructed in any database. This is merely an example of how you might organise a block of index data where the key data is of variable length.

4
  • Greg, I haven't picked your answer as the defacto answer yet because I am hoping for some more feedback as well as doing some more research into other DBMSs (I am adding my comments to the original Q). So far the most common approach seems to be an upper bound cap and then the rest of the key in an overflow table that is only checked when the full key is needed. Not that elegant. Your solution has some elegance to it that I like, but in the edge case where keys blow our your page size, your way would still need an overflow table or just not allow it. Jan 22, 2012 at 21:24
  • I ran out of space... In short if the db designer could live with some hard limits on key size, i think your approach is the most efficient and flexible. Nice combo of space and cpu efficiency. Overflow tables are more flexible, but can be aweful for adding random i/o to lookups for keys that constantly overflow. Thanks for the input on this! Jan 22, 2012 at 21:26
  • Greg, I have been thinking about this more and more, looking at alternative solutions and I think you nailed it with the offset header idea. If you kept your blocks small you could get away with 8-bit (1-byte) offsets, with bigger blocks 16-bit would be safest even up to 128KB or 256KB blocks that should be reasonable (would assume 4 or 8byte keys). The big win is how cheap and fast you can read in the offset data and how much deserialization you save on as a result. Excellent suggestion, thank you again. Jan 24, 2012 at 3:14
  • This is also the approach used in UpscaleDB: upscaledb.com/about.html#varlength Feb 17, 2016 at 8:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.