0

I really don't know which StackExchange site this belongs on. It didn't seem to match the "on-topic" list of DBA.SE or SO.SE ... so please let me know if I should move it. I also couldn't find a similar question but am happy for this to be a duplicate so I can close it.

I have been writing SQL for almost 10 years but I've recently become interested in how database engines work at a much lower level. As a very basic test of my understanding, I have begun to implement my own table-based storage system.

I've been reviewing the SQLite page structure and I haven't been able to understand how the internal structures of a database storage engine can efficiently handle new columns added to a table. Ignoring all of the other moving parts, I am curious what actually happens when a new column is added to a database table and how the underlying storage changes.

Let's say for example, that Page 5 is a table page and contains the data for a table called User. This table has a primary key column called id and a 250-byte wide string column called email. This particular page has only 125 bytes of free space left available to it, so inserting a new record would push the new data into a new page (lets just say Page 6).

Now let's say I want to add a new column for some sort of non-nullable hash column to the User table that has enough room for 200 bytes. How does the engine efficiently store this new column?

If your storage engine assumes that each row is stored one after the other, then the engine will need to shift possibly large chunks of data around to fit this new column into the underlying storage. Page 5 would likely very quickly require the last few rows at least to be bumped somewhere.

The other option might be to bulk-move data between pages while also adding the new column to eac row.

Can anyone explain this process to me? There is probably something obvious I have missed in the source material.

1

It Depends...

If you are really interested in all of the possible ways find yourself a book on database engines, something like An Introduction to Database Systems

The Dumb Way

Treat every record as an exact length record, with each column being located at some bit-offset and consuming some X bits of the record. You could pack this record tight, or align each column to some byte boundary.

When you add, remove, or modify a column, every record has to be loaded converted to the new data shape and saved. This should be done within the current transactional scope.

Noticing an Optimisation

There are some columns that do not need all of their bits when set in particular states. For example a nullable field. It would be especially wastefull to allocate 4K bytes to a fixed string column that is nullable when the field is set to null for a record.

It would be nice if the record had a variable length. That when there was a fixed length string, the 4K bytes would be allocated, but when it was null, only a single bit indicating nullness was used.

Non-Null D:
AAAAABBBBBCCCCCCCDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDE

Null D:
AAAAABBBBBCCCCCCCDE

This does complicate loading records as you cannot just jump to a calculated offset. You would need to scan a page of memory serially, or use a page header with a list of record start offsets in the page.

This does not change the logical problem of adding, removing, or modifying columns. Although you could treat every column as nullable at the implementation level. This would then mean that turning on nullability on a column is free (you were already paying for it), and turning it off would be a simple check to see if any record is currently set to null.

Finite State and Partitions

We can take the optimisation further by noticing that certain fields are highly repetitive:

  • Boolean
  • Integers
  • Strings

Often the data stored in these columns in these records is similar if not identical across many records. In terms of search efficiency it makes sense to co-locate these records within the same memory pages, as it makes them easier to find, and to ignore.

As these records have these commonalities we could choose to not duplicate the identical data accross each record, but to just store the variable portion.

Given:

//Logical Records
(true, false, 123, "His Jaw")
(true, false, 124, "His Leg")
(true, false, 126, "His Eye")
(true, false, 129, "His Bow")

We could describe it as:

//Partition Header
(true, false, 120 + _, "His " + _)

//Partition Records
(3, "Jaw")
(4, "Leg")
(6, "Eye")
(9, "Bow")

This is still 4 records, all of the similarities have been extracted into a page header, and each variant identifies the difference between it and that header.

This complicates parsing as the exact records are no longer exactly stored, but they can still be recovered.

Adding, Removing, and modifying columns is still problematic. The partition must still be updated. However the update might not affect each variance, but the header (say drop the first column or insert a new column).

Logical Table vs Stored Record

Now we can actually do something about the adding, removing, and modifying of columns. The last observation shows that, how the table data is stored does not have to directly match the logical table schema, its allowed to be different as long as the logical record can be reconstructed.

What this means is that a partition need only have some extra meta-data stored with it, about what each physical column corresponds to in the logical table. Where possible each logical column would have some default logical state.

//Logical Table
//| Logical Name  | type        | Internal Name | Default Value
( (Runnable,        bool,         A,              false)
, (ContinueOnError, bool,         B,              true)
, (FlagOnFailure,   bool,         C,              true)
, (SerialID,        int,          D,              - ) //- No Default value, must be specified
, (RelatedEntry,    int?,         E,              null)
, (Label,           varchar[200], F,              null)
)

//Partition Header
( A  , C    , D      , F         )   //logical column names
(true, false, 120 + _, "His " + _)   //common data in partition

When removing a logical column:

  • only those partitions that define it need to be updated.
  • all the other partitions need no change

When modifying a logical column:

  • changing the type only affects partitions whose sub-type needs changing
    • converting a null to null is a noop
    • converting a string to a string of a longer length is a noop.
    • converting an integer to a string may require some computation
    • converting a longer string to a shorter string requires certain partitions are truncated.
  • changing the logical order of a column is just an update to the logical table definition
  • changing the name of the column is just an update to the logical table definition
    • assuming that you have used a stable internal column name

When adding a logical column:

  • if it has a well known default value, then it is just an update to the logical table definition
  • otherwise each record will need to be updated to store a correct value for the record, which may repartition the data to optimise for commonalities.

And this is just the top of the possible ways to encode a logical table.

SQLite

The approach that SQLite takes is pretty similar to what I've just describe, keeping the logical layout separate to how each record is physically stored. Its only when the record has to be changed that it actually rewrites the data.

And just as a note, database engines prefer to not do in place updates. It affects the engines ability to perform concurrent queries, and also has some nasty implications for transactional consistency. What you will generally find is that the entire memory page is rewritten into one or more new memory pages, which are flushed to disk along with a similarly updated table index. This allows older queries to still use the old representation of the data, and new queries will use the new representation. Eventually the old unused pages are garbage collected and reused as blank space for later transactions.

  • Thank you for this answer! I'll need to read it again tomorrow morning when my brain is refreshed, but this does seem to answer my question. I wasn't aware that page flushes weren't in place - this is certainly news to me. It makes a lot of sense to do it that way though because I've been trying to think about how data would expand across page boundaries and everything I could come up with resulted in lots of data shifting around each page. You've certainly given me a lot to think about - thank you very much! – Simon Whitehead May 6 at 14:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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