Introduction

I’m reading Database Internal, and will write stuffs i have already learnt here:

DB basic

Four Properties

SQL Databases would require ACID, but not all properties are stricly follow:

  • ACID stands for Atomicity, Consistency, Isolation and Durability

  • Atomicity means each transaction is atomic, if one of the query of the transaction fail it all fail all rollback to the state where transaction hasn’t started

  • Isolation means the isolation between concurrent transactions (actually not concurrent if we not allow), here’re issues and level of isolation:

    • Dirty read: means a query read a value that never existed (that was being changed in another transaction, but that transaction FAILED to commit).
    • Unrepeatable read: the same query in 1 transaction return different results, mean there was another transaction SUCCESS committing the change of values that the other query is currently reading, leading different query result.
    • Phantom read: read value that no longer exist (a query read value from a record, that record then being deleted in another concurrent transaction, result the query read value that no longer exist)

    These issues, not all bad, it just bases on our tolerance about data access consistency, if we allow these issues to happen, then it’s no longer an issue at all.

    But if we want to eliminate them, here’s some option:

    • Only read value that has been committed, so if a concurrent transaction commit midway, it can be read. This can be done by versioning, just read the value with the current version, when it is committed the version got updated, happy life. I fixes the bad read, the others remain, kinda obvious since the phantom read, we will never know if it is deleted lol.
    • Only read value that is committed before the current transaction start, so no longer unrepeatable read :D
    • Or just get rid of all concurrent stuff and serialize all the transactions instead so boom no race conditions would ever appear.

    And it is obviously, the execution time would get worse through each level.

  • Consistency, as long as Atomicity and Isolation is guaranteed, this is likely hold. It’s about the all the data store in DB, follow the rule that we set, like the foreign keys: there must be a value with the same in the reference table, or unique on key where no key is duplicate,… This is considered as the weakest property among all 4, since it based on user preference not DB itself.

  • Durability: whatever happens committed data stays there.

As said, this is preferred properties for a standard functional DB, but not all DB holds, especially with special usecases.

DB tools

Transaction manager: coordinate transactions, schedule, track their smallest step. The schedule and coordination itself is very interesting one, that related to optimizing transaction processing.

Lock manager: the name itself tells the purpose, it would manage all the locks, and we all know that on a specific place, there would just be only at most transaction holding a lock.

Cached page: This is interesting and new, cached page besides using as a normal cache (the most recent access data), it also be used to cache the latest change on data, so if other operations read the updated data right after it can read right from the cache (the cache page now consider “dirty”), after the cache page is evicted (due to many reasons, like the memory is not enough space for a new cache page so it has to evict an old page), the data on that cache page got flushed (sync) to disk, so this is one-way sync. It store the latest of data changes :D

Log manager: I thought it was a log like usual, is used to backing up data and restore. Yeah it does, but for cached page :), that makes sense, since the DB itself already sasistfied the Durability, so as long as the data is settle down on the physical storage, it stay persistent no matter what. For the log manager, it would log the cached page, so in case some DB crashes, since cache itself is in memory, so it is not stable if error arrive, so the log manager is there to restore the cache. it can also be used to rollback aborted transaction.

DB mechanism

This not gonna be written in any order.

Data deleted (in data file)

After a data (record, column,…) is processed as deleted, it is not actually deleted, instead it got a flag with metadata, called tombstone, that data got shadowed. And after a “while” it would eventually be deleted by garbage collection.

Why “while”? The GC is not something that runs randomly, it would run after no any consistent snapshot (of tables) refer to that data, and why the data should still stay alive until the GC arrived? The previous sentence might just reveal that, there maybe other place still accessing that data, so instantly delete is not recommend as it would lead to read corruption - bad read. Also the GC process the deletion in batch, which save much time than doing the delete repeatly.

Also deleting data in file, let think it as byte, that would require offset changing, that would affect other data, and takes time for the system to reorganize everything which is expensive operations, batch them is clearly the better approach. Marking them a metadata would just append so it is way more efficient.

Although, GC in different DBs would behave differently.

Copy-on-write

This means the data is immutable, and to update the immutable data - we do a deep copy of it and have the modification here instead. Not every DB uses it, but it actually kinda benefit with some few notes:

  • So it separation of concern, the reader, still read the immutable version, while the new one still being written by writer, so basically no race condition ever.
  • It does require extra spaces for storing copy of the data, though the old version will be cleaned up afterwards (similar to above section), but in a write-heavy usecase this might lead to OOM (out of memory), be careful tho, apart from that it is great balance read-write usecases.

WAL: Write Ahead Log

What’s this, i see it is very familiar, ah yes it does related to the mechanism of the cache page, the changes stays on memory first, then apply to disk later. Instead of write through which would directly write to disk on every data change, WAL is a log, yes, have all the operations ordered sequentially on a piece of data change, the change would be reflect on the cache in memory, but the log itself, is in disk (not storage disk). So what does this tell? The process would be follow: the operation update -> being append to WAL & reflect on the cache page -> after the cache is evicted (due to no more space for a new cache and new cache page is comming), the data on the cache would be flush (sync) back to the disk, actually the disk would read the WAL for better reliability, since WAL is on disk and cache is not.

So this is one kind of Log manager we have in the first section.

Indexing

For standard, indexing mechanism using B-tree structure, there also B+ tree (with actually all major DB uses this but they just said B-tree, so i guess B+ tree is the standard B tree now).

B-tree, but not deep dive in mechanism since we already knew about it

So each node, is designed to fit in a disk page, so access a B-tree node is access to disk page already.

B+ tree

For the concept, it is B-tree, but the leaf nodes are linked with each other like a linked list (from left->right). This enables significant better performance for range search.

The another importance piece here is the all data lives on the leaf nodes, internal nodes are just used for search key, that means we no longer can stop the finding on internal node and access disk page directly, instead, since the leaf nodes are the one holding holding the reference to actual data, the value of the internal node, will be copied into the leaf node also. Here’s an example:

Index would have multiple kinds: Single index - most easy to understand, Composite index (multiple field in an index),

How index on non-number work? Like the order of non-number, with text it would be based on the first letter order like so, based the sort algorithm.

UUID indexing is fucking bad cuz it is pure randomness and no ordering available, if uuid then no index as it is useless.

Primamry Index and Secondary Index

Basically Primary Index is index on the PK. And Secondary Index are indexes that not the Primary Index :).

Secondary index leaves, usually contain the PK value along with the secondary key.

How composite index work

Composite index, works just like the single index with scale. Let say we have

INDEX (user, status, created_at)

then the B-tree would be: the the created_at is grouped by status, and status is grouped by user. That means if we do query:

WHERE status = "success" AND created_at > '2026-01-01'

this won’t able to use the index just set up above, since the user should be there to tell which status cluster it need to look at, so it go full scan anyway, as when status grouped by user can be success or any other value, without user grouping the query gonna need to full scan the table to see which row has status = success

That composite works best in cases where the first column in the index exists (and at the first order of the query), with any of the column exist in the index (respect the order) and no skipping layer, that means for this cases, it would be:

  • WHERE user = 1
  • WHERE user = 1 and status = "pending"
  • WHERE user = 1 and status = "pending" and created_at > '2026-01-01'

Although there is case WHERE user = 1 and created_at > '2026-01-01', this one first it would do the narrow data by the user index, then scan all the possible status for the created_at, so the index is partially used.

That said, selecting the order for composite index is crucially important, it needs to reflect the usecase (query) is used frequenly, else it is a big waste.

Covering index

For composite index, we actually can just do the index for some fields of the table, if we have composite of 2 fields out of 10 fields of a table, then a SELECT * with the condition include both fields in the index (with correct order as above), the index would just still return the ‘id’ (reference) to the correct row, not actually return the full data of matched row after the index searching. So basically, the SELECT * query would make the engine:

  1. Search the index to get ref to rows (since it cannot get the full data from unindexed columns/fields)
  2. Go to the corresponding rows to fetch the full row, that is call table lookup - which is a RANDOM read. That obviously take some time to do all that, but just in the case where the SELECT requires more columns than in the index, let say if it just SELECT user, status then the data is returned right after the first step. And with the more rows matched, there would be more table lookup - and obviously more random reads, that at somepoint the process of retreving data post index is significant longer than a sequential scan from the beginning, and the query optimizer would just choose the sequential one instead of index.

So how to eliminate the 2nd step, especially if that query, is a hot one that get execute a lot lot? Composite index on all fields of the table? If we do that then it would have no benefit that a no-index-at-all table, and put more overhead on WRITE operations. We have convering index, where it still use search key from the composite index as indexes, but in the leaf node it no longer just store the indexed fields, but also other fields, these fields just exist in the leaf node, not in the internal nodes where search key live.

Index drawbacks

While index is awesome for READ (if set up correctly), it does impact the WRITE (insert, update, delete,…), where each WRITE operations on a field that is indexed would require to update ALL the B-tree indexes, since a value being changed or create would perform some the tree transformations, and update the pointer of the current one to the new memory address.

A single WRITE request may end up to multiple WRITE requests because of indexing. Operations that make the number of row in the table change (insert, delete) would make all the indexes in that table, update. And you may think update not get harmed? It does, and worse, since the update operation is not actually override the old value to the new one, it actually delete the old one and insert the new value.

This mean index put overhead for WRITE operations, nothing is free in term of optimization.

Also, index does consume a lot of spaces, it create a B-tree for the whole table for each index.

How to use index correctly and efficient?

Use wisely, know what your exact usecase. Don’t overuse index, at somepoint the optimizer would just use the sequential scan instead of any indexes since it see no benefits from index.

Buffer management (aka Caching)

Most of the details already covered in the first section (Cached page), so here just list out some other stuffs that i discovered after reading more:

  • There is some page got pinning in the cache, means it would not be evicted until it no longer pinned. These pages are ones have high probability to be access. The action pin the page, called locking page in cache.

Log manager

Mostly about WAL mechanisms, just something else:

  • There would be a checkpoint, the name says it all, it serves as an indicator to tell the engine up to which moment the transactions are persitted, and it would perform the operation apply from that point of log.
  • There would be process call sync checkpoint where it flushes all dirty pages to the disk, this operation is done async so it won’t prevent new transaction being appended to the log. A sync checkpoint is not considererd complete until all dirty pages in the end_checkpoint are flushed.

Page replacement (cache page evict algorithm):

  • FIFO
  • LRU
  • CLOCK: basically set each page status with 1 is currently be referenced, 0 means not. It is a round buffer so the iterator going circular, checking if a page:
    • is 1 and still being referenced -> keep it as is
    • is 1 but not currently being referenced -> set to 0
    • is 0 but now being referenced -> set to 1
    • is 0 and not being referenced -> append in evict candidate list Pretty simple, yet efficient
  • LFU: Least Frequenty Use

Database locking mechanism

As I understand, there will be some kind of transactions require a DB lock (.e.g delete a table, a column,…). For the concept, locking means at that point only that transaction can be run for that area to avoid race condition, this would be very sensitive transactions. There are multiple lock mechanisms, which suitable for each kind of requirement. TBD

Concurrency Control

  • Optimistic:
    • This split the transaction execution into 3 phases: read, validation, write, this includes retry mechanism (for read, if the validation step fail), this is non-blocking, but it takes time for retrying.
    • The read phase would determine all the set of read and write oprerations needed for the transaction - know which field it would read or write, turns them in two set.
    • In the validation phase it would compare the read and write sets of each concurrent transactions, to see if there is any conflict (like the issue of isolation we already knew). If there is conflict, one of them (transaction) would be clear all the read write set and start the read phase again.
    • If no conflict found for the transaction during the validation step, it will be committed.
  • Multi Version: This uses version to determine if the current value of a field is the latest one or not, just pretty much it.
  • Pessimistic: This approach allows transactions to run freely and check the conflict and resolve the fly (can use locks). One lock-free approach is using timestamp ordering - involving changing the schedule, involves the max_write_timestamp and max_read_timestamp for each value. As I understand, the max_write_timestamp denotes the latest commit for the current value, so if operation tries to read the value with older timestamp than that it is invalid. So what’s the max_read_timestamp denote here? Does it show when was the current value was read most recently? I think so. Yes it does, and the write transaction using that, to show if a write transaction T with timestamp ts write to the value, if its max_read_timestamp > ts, it means there was some reader already read the old version of the value (and may not committed), which having T execute here would make uncommitted read transaction becomes invalid, so it is better to abort T and retry later if all transaction reading the value has been committed.

Schedule

A schedule contains list of operations needed to execute a set of DB transactions. A schedule is considered complete is when all the operations used for execute the transactions in it. The schedule is correct if it final complete operation list == the inital operation list (don’t care about order).

Page file

How DB actually stores and reads data

Normalization

Know when to normalize a table to other table with FK for better querying and organization