Databases – what you need to know

 

What is an index? 

Indexes are a data structure that allows us to skip the tedious task of checking every table row and that decrease the look-up time of requested data. 

 Indexes require additional costs of storage, memory, and keeping data up to date (slower writes),. 

Like an index in the back of a textbook, it helps you get to the right page.  

(I am not a great fan of the book analogy, it quickly falls apart when we dig deeper into database indexes, but it is the easiest way to introduce the topic.) 

Why do we need indexes? 

Small amounts of data are manageable but, (think of an attendance list for a small class) when the amount of data gets larger (think a birth registry for a large city) then not so easy to manage. Everything that used to be quick gets slower, too slow. 

How would your strategy change to find something on 1 page vs. thousand pages of names? Take a second and think. 

No matter what you come up with some database has implemented almost all the good strategies you can come up with at some point. As they grow, systems collect and store more data. 

We need indexes to help us get the relevant data we need as quickly as possible. 

 

So how to store this data logically based on how you would search it. Meaning e.g. to search the list by name you might sort the list by the first name. There are a few issues with that strategy. I will pose these questions: 

1. What if you only know the initial? 

2. What if you only know the last name? 

3. What if there are many people with the same first name 

4. What if you want to search the data in multiple ways? 

5. How would you deal with adding new data to the list? Is that fast? 

6. How would you deal with updates? 

Regardless of your original strategy we definitely need a way to maintain some order in the data so that we can quickly get to the additional, relevant but unordered data (more on that soon) 

+─────+─────────+──────────────+ 

| id  | name    | city         | 

+─────+─────────+──────────────+ 

| 1   | Mahdi   | Ottawa       | 

| 2   | Elon    | Mars         | 

| 3   | Jeff    | Orbit        | 

| 4   | Klay    | Oakland      | 

| 5   | Lebron  | Los Angeles  | 

+─────+─────────+──────────────+ 

A Small table that is easily read from disk quickly. 

The underlying data is spread around storage with no order and might be allocated randomly. Nowadays, most production servers come with Solid State Disk SSDs, but there are some cases where you would want (HDD) spinning disks. 

SSD vs. HDD 

Reading that small amount of data into memory is fast and relatively trivial to scan. What if the data we are searching across can't be cached entirely in the available memory? or the time to read all the data from the disk takes too long? 

 

Large Table that doesn't fit entirely in memory and is spread across disk. 

So here is where most developers go – “I have seen this problem before; we need some dictionary (hash map) and a way to get to the specific row we are looking for without having to scan the slow disk, reading tons of blocks to see whether  the data we need is there.” 

These are called index leaf nodes which are given a specific column to index, they can store the location of the matching row(s). 

 

These index leaf nodes are the mapping between the indexed column and where the corresponding row lives on the disk. This gives a quick way to get to a specific row when you reference it by indexed column.  

Scanning the index can be much faster since it is a compact representation (fewer bytes) of the column by which you search. It saves you time reading a bunch of blocks looking for the requested data and is much more convenient to cache, to further speed up the entire process. 

Blocks 

The benefits are twofold:  

• it allows us to read the index leaf nodes both forward and backward  

• and also to quickly rebuild the index structure when we remove or add new rows since we are just modifying pointers. 

Linked List 

Since these leaf nodes aren't arranged physically on disk in order (remember pointers maintain the sorting in the doubly linked list), we need a way to get to the correct index leaf nodes. 

Balanced Trees (B-Trees) 

Structural difference BTrees vs. B+Trees 

You might wonder where you made a massive error to find yourself reading about B-Trees you hated from school. These things are boring, but they are powerful and worth understanding. 

B+Trees allows us to build a tree structure where each intermediate node points to the highest node value of its respective leaf nodes. It gives us a clear path to find the index leaf node that will point to the necessary data. This structure is built from the bottom up so that an intermediate node covers all leaf nodes until we reach the root node at the top. This tree structure gets its name balanced because the depth is uniform across the entire tree. 

B-Tree vs. B+Tree 

 

How B+Trees are used in RDBMSs 

Logarithmic Scalability 

Developers are aware of the exponential growth of data and, ideally, your company's valuations. But unfortunately, the scale of data often works against you, and balanced trees are the first tool in your arsenal against it. 

Depending on the number of items the intermediate nodes can reference (M) plus the overall tree (N) depth, we can reference M to the N objects. 

Here is a table illustrating the concept with an M value of 5. 

Tree Height (N)	Index Leaf Nodes
3	125
4	625
5	3125
6	15625
7	78125
8	390625
9	1953125

As the number of index leaf nodes increases exponentially, the tree height grows incredibly slowly (logarithmically) relative to the number of index leaf nodes. 

 This coupled with balanced tree height, allows for almost instant identification of relevant index leaf nodes that point to actual data on disk. 

……….. a beautiful sight! 

What is a transaction? 

A transaction is a unit of work you want to treat as a single unit. Therefore, it has to either happen in full or not at all. Most systems don't need to manage transactions manually, but there are situations where increased flexibility is instrumental in achieving the desired effect. Transactions mainly deal with the I in ACID, Isolation. 

What is ACID? 

These can be done automatically for you so you aren't even aware they are taking place, or you can create them manually like so: 

-- Manual transaction with commit.  

BEGIN; 

SELECT * FROM people WHERE id =1; 

COMMIT or ROLLBACK; 

We will focus on the time between BEGIN and COMMIT or ROLLBACK and what happens to various other transactions acting on the same data. 

COMMIT/ROLLBACK 

All manual transactions either end in successful COMMIT. or ROLLBACK. 

• COMMIT durability persists in the changes made by the current transaction. 

• ROLLBACK undoes the changes made by the current transaction. 

When you are not manually managing transactions, and when all queries within a transaction are completed successfully, those are COMMITTED. If there is any failure, then the changes during that transaction are ROLLED BACK to ensure the atomicity of the entire action. 

Several read phenomena can occur in these isolations, and understanding these is essential to debug your systems and also to understanding what kind of inconsistencies your system can tolerate. 

Non-repeatable reads 

 

Non-repeatable reads example 

As in the image above, non-repeatable reads occur when you cannot get a consistent view of the data between two subsequent reads during your transaction. In specific modes, concurrent database modification is possible, and there can be scenarios where the value you just read can be modified, resulting in a non-repeatable read. 

Dirty reads 

 

Similarly, a dirty read occurs when you perform a read, and another transaction updates the same row but doesn't commit the work, then you perform another read, and you can access the uncommitted (dirty) value, which isn't a durable state change and is inconsistent with the state of the database. 

Phantom reads 

 

Phantom reads are another committed read phenomena, which occurs when you are most commonly dealing with aggregates. For example, you ask for the number of customers in a specific transaction. Between the two subsequent reads, another customer signs up or deletes their account (committed), which results in you getting two different values if your database doesn't support range locks for these transactions. 

Range Locks 

Range locks are best described by illustrating all the possible lock levels. 

1. Serialized Database Access — Making the database run queries one by one—terrible concurrency, the highest level of consistency, though. 

2. Table Lock — lock the table for your transaction with slightly better concurrency, but concurrent table writes are still slowed. 

3. Row Lock — Locks the row you are working on even better than table locks, but if multiple transactions need this row, they will need to wait. 

Range locks are between the last two levels of locks; they lock the range of values captured by the transaction and don't allow inserts or updates within the range captured by the transaction. 

Isolation Levels 

 

4 Isolation levels for SQL Standard 

The SQL standard defines 4 standard isolation levels these can and should be configured globally (insidious things can happen when we can't reliably reason about isolation levels). 

REPEATABLE READ 

REPEATABLE READ  sets the table for the remainder of the isolation levels. This isolation level ensures consistent reads within the transaction established by the first read. This view is maintained in several ways; some affect the overall system's performance, while others don't. 

See the graphic above; once we do our first read, that view is locked for the duration of the transaction, so anything that happens outside the context of this transaction is of no consequence, committed or otherwise. 

This isolation level protects us from several known isolation issues, mainly non-repeatable and dirty reads. It does have minor data inconsistency that is locked to a specific view of the database; so keeping transactions as short-lived as possible is beneficial. 

SERIALIZABLE 

This operating mode can be the most restrictive and consistent since it allows only one query to be run at a time. 

All types of reading phenomena are then no longer possible since the database runs the queries one by one, transitioning from one stable state to the next. There is more nuance here, but the gist is more or less accurate. 

It is essential to note in this mode to have some retry mechanism since queries can fail due to concurrency issues. 

Newer distributed databases take advantage of this isolation level for consistency guarantees. CockroachDB is an example of such a database. 

READ COMMITTED 

This isolation mode is different from REPEATABLE READ in that each read creates its own consistent (committed) snapshot of time. As a result, this isolation mode is susceptible to phantom reads if we execute multiple reads within the same transaction. 

READ UNCOMMITTED 

Alternatively, the READ UNCOMMITTED isolation level doesn't maintain any transaction locking and can see uncommitted data as it happens, leading to dirty reads. The stuff of nightmares... in some systems.