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:
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.
