If someone asks you how databases work, ask them to read this article

array mergeSort(array a)
   if(length(a)==1)
      return a[0];
   end if

   //recursive calls
   [left_array right_array] := split_into_2_equally_sized_arrays(a);
   array new_left_array := mergeSort(left_array);
   array new_right_array := mergeSort(right_array);

   //merging the 2 small ordered arrays into a big one
   array result := merge(new_left_array,new_right_array);
   return result;Copy the code

SELECT PERSON.*
FROM PERSON
WHERE PERSON.person_key IN
(SELECT MAILS.person_key
FROM MAILS
WHERE MAILS.mail LIKE 'christophe%');Copy the code

mergeJoin(relation a, relation b) relation output integer a_key:=0; integer b_key:=0; while (a[a_key]! =null and b[b_key]! =null) if (a[a_key] < b[b_key]) a_key++; else if (a[a_key] > b[b_key]) b_key++; else //Join predicate satisfied write_result_in_output(a[a_key],b[b_key]) //We need to be careful when we increase the pointers if (a[a_key+1] ! = b[b_key]) b_key++; end if if (b[b_key+1] ! = a[a_key]) a_key++; end if if (b[b_key+1] == a[a_key] b[b_key] == a[a_key+1]) b_key++; a_key++; end if end if end whileCopy the code

Which algorithm is best?

If you have the best, there’s no need to have so many types. This question is difficult because there are many factors to consider, such as:

• Free memory: If you don’t have enough memory, say goodbye to powerful hash joins (at least fully in-memory hash joins).
• The size of two data sets. For example, if a large table joins a small table, a nested loop join is faster than a hash join because of the high cost of creating a hash. If both tables are very large, then the CPU cost of nested loop joins is very high.
• Index or not: With two B+ tree indexes, the smart choice seems to be to merge the join.
• Whether the results need to be sorted: Even if you are working with unsorted data sets, you may want to use a more expensive merge join (sorted) because when you finally get sorted results, You can concatenate it with another merge join (or perhaps because the query implicitly or explicitly requires a sorting result with operators like ORDER BY/GROUP BY/DISTINCT).
• Whether the relationship is sorted: A merge join is the best candidate.
• Tablea.col1 = tableb.col2 Inner connection? Outer join? Cartesian product? Or self-join? Some connections do not work in certain environments.
• Data distribution: If the data for join conditions is skewed (such as joining people by their last names, but many people have the same last name), hash joins can be a disaster because the hash function will produce hash buckets that are very unevenly distributed.
• If you want the join operation to use multithreading or multi-process.

For more detailed information, read the documentation for DB2, ORACLE, or SQL Server.

Simplified example

We have examined three types of join operations.

Now, let’s say we want to join five tables to get all the information about a person. A person can have:

• Multiple mobile numbers
• A number of E-mails
• Multiple addresses (ADRESSES)
• Multiple bank accounts (BANK_ACCOUNTS)

In other words, we need to get the answer quickly with the following query:

As a query optimizer, I have to find the best way to handle the data. But there are two problems:

• What type does each join use? I have three options (hashing, merging, nesting) and may use 0, 1, or 2 indexes (not to mention multiple types of indexes).

• In what order is the join performed? For example, the following figure shows the possible execution plan for four tables with only three joins:

Review images

So here’s what I might do:

• 1) Use database statistics in a rough way to calculate the cost of every possible execution plan and retain the best one. However, there are many possibilities. For a given sequence of join operations, each join has three possibilities: hashing, merging, and nesting, so there are 3^4 possibilities in total. Determining the order of the join is a binary tree arrangement problem, with (2*4)! / (4 + 1)! The possible order. I’m going to end up with 3 to the fourth times 2 times 4 factorial for this rather simplified problem. / (4 + 1)! Possible. Terminology aside, that’s 27,216 possibilities. If you add 0,1, or 2 B+ tree indexes to the merge join, the possibilities become 210,000. Did I tell you that this query is actually quite simple?

• 2) It would be tempting for me to yell and quit the job, but then you won’t get the results, and I need the money to pay my bills.

• 3) I try only a few execution plans and pick the one with the lowest cost. Not being Superman, I can’t figure out the cost of all the plans. Instead, I can arbitrarily choose a subset of all possible plans, calculate their costs and give you the best plan.

• 4) I use smart rules to reduce the number of possibilities There are two kinds of rules: I can use the “logical” rule, which removes useless possibilities but does not filter out a large number of possibilities. For example: “The inner relation of a nested join must be the smallest data set.” I accept the fact that instead of looking for the best solution, I dramatically reduce the number of possibilities with more aggressive rules. For example: “If a relationship is small, use nested loop joins, never merge or hash joins.”

In this simple example, I ended up with a lot of possibilities. Real world queries also have relational operators like OUTER JOIN, CROSS JOIN, GROUP BY, ORDER BY, PROJECTION, UNION, INTERSECT, DISTINCT… That means more possibilities.

So how does the database work?

Dynamic programming, greedy algorithms and heuristic algorithms

Relational databases try many of the approaches I just mentioned, but the optimizer’s real job is to find a good solution in limited time.

Most of the time, the optimizer doesn’t find the best solution, it finds a “good” one

For small queries, it is possible to take a rough approach. But there is a way to avoid unnecessary computation in order to allow even moderately sized queries to take a rough approach: dynamic programming.

Dynamic programming

The idea behind these words is that many execution plans are very similar. Take a look at these plans below:

Review images

They all have the same subtree (A JOIN B), so instead of calculating the cost of the subtree in each plan, calculate it once, save the result, and reuse it when it encounters the subtree again. In more formal terms, we have an overlap problem. To avoid double-counting partial results, we use mnemonics.

For computer geeks, here’s an algorithm I found in the tutorial I gave you earlier. I don’t offer explanations, so only read it if you already know dynamic programming or are proficient with algorithms (I warned you) :

For large queries, you can also use a dynamic programming approach, but add additional rules (or heuristics) to reduce the likelihood.

• If we analyze only one specific type of plan (for example, left-deep tree, see), we get n*2^n instead of 3^n.

Review images

• If we add logical rules to avoid schema schemes (like “If a table has an index for a given predicate, don’t try to join the table, do the index”), we reduce the number of possibilities without doing too much harm to the best scenario.As =has, to=too
• If we add rules to the process (like “join operations precede all other relational operations”), we can also reduce a lot of possibilities.
• …

Greedy algorithm

However, when the optimizer is faced with a very large query, or in order to find the answer as quickly as possible (when the query is not fast enough), it applies another algorithm called the greedy algorithm.

The principle is to plan queries in a progressive manner according to a rule (or heuristic). Under this rule, the greedy algorithm gradually searches for the best algorithm by first processing a JOIN and then adding a new JOIN according to the same rule at each step.

Let’s look at a simple example. For example, for A query with four joins on five tables (A,B,C,D,E), we use nested joins as the possible JOIN method for simplicity, following the “use the least cost JOIN” rule.

• Start directly from one of the 5 tables (e.g. A)
• Computes each join with A (A as inner or outer relation)
• It is found that A JOIN B has the lowest cost
• Calculate the cost of each result JOIN with “A JOIN B” (” A JOIN B “as inner or outer relation)
• It is found that “(A JOIN B) JOIN C” has the lowest cost
• Calculate the cost of each JOIN with the result of “(A JOIN B) JOIN C”…
• “(((A JOIN B) JOIN C) JOIN D) JOIN E)”

Since we start arbitrarily with table A, we can apply the same algorithm to B, then C, then D, then E. Finally, retain the lowest cost execution plan.

This algorithm, by the way, has a name: the nearest neighbor algorithm.

All details aside, with a good model and an N*log(N) sort, the problem is easily solved. The complexity of this algorithm is order N log(N), compared to order 3^N, which is completely dynamic programming. If you have a large query with 20 joins, that means 26 vs 3,486,784,401, a big difference!

The problem with this algorithm is that we make the assumption that we can find the best way to join the two tables, keep the join result, and join the next table to get the lowest cost. But:

• Even between A, B and C, A joins B at the lowest cost
• (A JOIN C) JOIN B may be better than (A JOIN B) JOIN C.

To improve this situation, you can use greedy algorithms based on different rules multiple times and keep the best execution plan.

Other algorithms

[If you’ve had enough of algorithms, skip to the next section. It’s not important for the rest of the article.] [Translator’s note: I want to skip this part too.]

Many computer science researchers are interested in finding the best execution plan. They often seek better solutions to specific problems or patterns, such as:

• If the query is a star join (a multi-join query), some databases use a specific algorithm.
• Some databases use a specific algorithm if the query is parallel. …

Other algorithms are also being studied to replace dynamic programming algorithms in large queries. Greedy algorithms belong to a large family of algorithms called heuristics, which, based on a rule (or heuristic), save the method found in the previous step and “append” it to the current step to further search for a solution. Some algorithms apply the rules step by step based on specific rules but do not always retain the best method found in the previous step. They are collectively called heuristic algorithms.

Genetic algorithms, for example, are a way to:

• A method represents a possible complete query plan
• Each step preserves P methods (i.e., plans) instead of one.
• 0) P plans are randomly created
• 1) The lowest-cost plan is retained
• 2) These best plans are mixed together to produce P new plans
• 3) Some new plans were randomly rewritten
• 4) Repeat steps 1, 2, and 3 T times
• 5) Then, in the last loop, get the best plan from P plans.

The more loops, the better the plan.

Is this magic? No, it’s the law of nature: survival of the fittest!

PostgreSQL implements genetic algorithms, but I can’t find out if it uses them by default.

Other heuristic algorithms are used in the database, such as “Simulated Annealing”, “Iterative Improvement”, “two-phase Optimization”… . However, I do not know if these algorithms are currently used in enterprise databases or only in research databases.

If you want to learn more, this research paper introduces two more possible algorithms “A survey of algorithms for join sorting problems in database query optimization”, you can read it.

Real optimizer

[This paragraph is not important and can be skipped]

However, all of the above wordy stuff is very theoretical, I’m a developer not a researcher, and I like concrete examples.

Let’s take a look at how the SQLite optimizer works. This is a lightweight database that uses a simple optimizer, based on greedy algorithms with additional rules, to limit the number of possibilities.

• SQLite never reorders tables with the CROSS JOIN operator
• Use nested joins
• External joins are always evaluated sequentially
• …
• Versions prior to 3.8.0 used the “nearest neighbor” greedy algorithm to find the best query plan and so on… We’ve seen this algorithm before! What a coincidence!
• Starting with version 3.8.0 (released in 2015), SQLite uses the “N nearest neighbor” greedy algorithm to search for the best query plan

Let’s look at another optimizer in action. IBM DB2 is similar to all enterprise databases, and I discuss it because it was the last database I really used before switching to big data.

After reviewing the official documentation, we learned that the DB2 optimizer allows you to use seven levels of optimization:

• Use greedy algorithms for joins
• 0 — Minimal optimization, using index scans and nested loop joins, avoiding some query rewriting
  • 1 – Low level optimization
  • 2 — Fully optimized
• Use dynamic programming algorithms for joins
• 3 — Medium optimization and rough approximation
  • 5 — Fully optimized, using all techniques with heuristics
  • 7 – Fully optimized, similar to level 5, but without heuristics
  • 9 — Maximum optimization, regardless of overhead, considering all possible join orders, including cartesian products

You can see that DB2 uses greedy algorithms and dynamic programming algorithms. Of course, they don’t share their heuristic algorithms, because the query optimizer is the database’s bread and butter.

DB2’s default level is 5, and the optimizer uses the following features:

• Use all available statistics, including frequent-value line trees and quantile statistics.
• Use all query rewrite rules (including materialized query table routing, Materialized Query table routing), except for computationally intensive rules that apply in rare cases.
• Simulate joins using dynamic programming
• Limited use of composite inner relation
• Limited use of cartesian products for star schemas involving lookup tables
• Consider a wide range of access methods, including list prefetch, index ANDing, and materialized query table routing.

By default, DB2 uses a dynamic programming algorithm constrained by heuristics for join permutations.

(GROUP BY, DISTINCT…) Handled by simple rules.

Query plan cache

Because creating a query plan is time consuming, most databases keep the plan in the query plan cache to avoid double-counting. This is a big topic because the database needs to know when to update outdated plans. The idea is to set an upper limit, and if a table’s statistical change exceeds the upper limit, the query plan for that table is removed from the cache.

Query executor

At this stage, we have an optimized execution plan, which is then compiled into executable code. Then, if there are enough resources (memory, CPU), the query executor executes it. Operators in the plan (JOIN, SORT BY…) It can be executed sequentially or in parallel, depending on the executor. To get and write data, the query executor interacts with the data manager, which is discussed in the next section of this article.

Data manager

Review images

In this step, the query manager performs the query, needs data from tables and indexes, and makes a request to the data manager. But there are two problems:

• Relational databases use a transaction model, so when someone else is using or modifying data at the same time, you can’t get at that part of the data.
• Data extraction is the slowest operation in a database, so the data manager needs to be smart enough to get the data and store it in memory buffers.

In this section, I haven’t looked at how relational databases handle these two issues. I won’t go into how the data manager gets the data, because that’s not what matters (and this article is already long enough!). .

Cache manager

As I said, the main bottleneck for databases is disk I/O. To improve performance, modern databases use a cache manager.

Review images

The query executor does not take data directly from the file system, but asks for it from the cache manager. The cache manager has an in-memory cache, called the buffer pool, from which data can be read to significantly improve database performance. It’s hard to put an order of magnitude on this, because it depends on what kind of operation you want:

• Sequential access (e.g., full scan) vs. random access (e.g., access by row ID)
• To read or write

And the disk type used by the database:

• 7.2K / 10K / 15K RPM disk
• SSD
• RAID 1/5 /…

I’d say memory is a hundred to a hundred thousand times faster than disk.

However, this leads to another problem (databases always do…). The cache manager needs to get the data before the query executor uses it, otherwise the query manager has to wait for the data to be read from a slow disk.

The proofs

This problem is called prereading. The query executor knows what data it will need because it knows the entire query flow and also knows the data on disk through statistics. Here’s how it works:

• When the query executor processes its first batch of data
• The cache manager is told to preload the second batch of data
• When you start processing the second batch of data
• Tell the cache manager to preload the third batch of data, and tell the cache manager that the first batch can be purged from the cache.
• …

The cache manager stores all of this data in the buffer pool. To determine whether a piece of data is useful, the cache manager adds additional information (called latches) to the cached data.

Sometimes the query executor does not know what data it needs, and some databases do not provide this capability. Instead, they use either a speculative prefetch (for example, if the query executor wants data 1, 3, 5, it is likely to ask for 7, 9, 11 soon) or a sequential prefetch (where the cache manager simply reads a batch of data and then loads the next batch of continuous data from disk).

To monitor prefetch performance, modern databases introduce a measure called buffer/cache hit ratio, which shows how often requested data is found in the cache rather than read from disk.

Note: A poor cache hit ratio does not always mean that the cache is working badly. Read the Oracle documentation for more information.

A buffer is just a limited amount of memory, so it needs to remove some data in order to load new data. Loading and clearing the cache requires some disk and network I/O costs. If you have a query that is executed frequently, it is inefficient to load and erase the query results each time. Modern databases use a buffer replacement strategy to solve this problem.

Buffer replacement strategy

Most modern databases (at least SQL Server, MySQL, Oracle, and DB2) use the LRU algorithm.

LRU

LRU stands for Least Recently Used algorithm. The principle behind LRU is that the data kept in the cache is Recently Used, so it is more likely to be Used again.

Illustration:

Review images

For better understanding, I’ll assume that the data in the buffer is not locked by the latch (that is, can be removed). In this simple example, the buffer can hold three elements:

• 1: The cache manager (CM for short) takes data 1 and puts it into an empty buffer
• 2: CM takes data 4 and puts it into a half-load buffer
• 3: CM takes data 3 and puts it into a half-load buffer
• 4: CM uses data 9, the buffer is full, so data 1 is cleared because it is the last recently used data 9 is added to the buffer
• 5: CM uses data 4, which is already in the buffer, so it becomes the first recently used one again.
• 6: CM uses data 1, the buffer is full, so data 9 is cleared because it is the last recently used data 1 is added to the buffer
• …

This algorithm works well, but there are some limitations. What if a full table scan is performed on a large table? In other words, what happens when the table/index size exceeds the buffer? Using this algorithm will clear all data previously in the cache, and fully scanned data is likely to be used only once.

To improve the

To prevent this, some databases add special rules, such as those described in the Oracle documentation:

“For very large tables, a database usually use direct path to read, namely direct load block […], to avoid fill the buffer. For medium size table, the database can be used to directly read or cache read. If you choose to read cache, database, to the end of the block in the LRU prevent to empty the current buffer.”

There are also possibilities, such as using an advanced version of LRU called LRU-K. For example, SQL Server uses LRU-2.

The idea is to take more history into account. Simple LRU (that is, LRU-1), which only considers the data that was last used. LRU -k? :

• Consider the last KTH use of the data
• The number of times the data is used adds weight
• A batch of new data is loaded into the cache, and old but frequently used data is not cleared (because of the higher weight).
• But this algorithm does not retain data that is no longer in use in the cache
• So if the data is no longer used, the weight value decreases over time

Calculating weights costs money, so SQL Server just uses K=2, which is a good value for performance and an acceptable overhead.

For more in-depth knowledge of LRU-K, read an earlier research paper (1993) : LRU-K page Replacement Algorithm for database disk buffering

Other algorithms

There are other algorithms for managing caches, such as:

• 2Q (LRU-K like algorithm)
• CLOCK (LRU-K like algorithm)
• MRU (the latest algorithm used, using LRU with the same logic but different rules)
• LRFU (Least Recently and Frequently Used, Recently and Frequently Used)
• …

Write a buffer

I only talked about read caches — preloading data before use. It is used to store data and to brush to disk in batches rather than write to disk one by one, resulting in many single disk accesses.

Keep in mind that buffers hold pages (the smallest unit of data) and not rows (logically/the way humans are used to viewing data). A page in the buffer pool that has been modified but not written to disk is a dirty page. There are many algorithms to determine the best time to write dirty pages, but this problem is highly relevant to the concept of transactions, which we’ll talk about next.

Transaction manager

Last but not least, the transaction manager, we’ll see how this process ensures that each query executes within its own transaction. But before we begin, we need to understand the concept of ACID transactions.

“I ‘m on the acid”

An ACID transaction is a unit of work that guarantees four properties:

• Atomicity: A transaction is “either all done or all cancelled”, even if it runs for 10 hours. If the transaction crashes, the state goes back to before the transaction (transaction rollback).
• Isolation: If two transactions A and B are running at the same time, the final result of transaction A and B is the same regardless of whether A ends before/after/during B.
• Durability: Once a transaction commits (i.e., executes successfully), data is saved in the database regardless of what happens (crashes or errors).
• Consistency: Only valid data (according to relational and function constraints) can be written to the database. Consistency is related to atomicity and isolation.

Review images

You can run multiple SQL queries to read, create, update, and delete data within the same transaction. Trouble arises when two transactions use the same data. The classic example is A remittance from account A to account B. Suppose there are two transactions:

• Transaction 1 (T1) takes $100 from account A and gives it to account B
• Transaction 2 (T2) takes $50 from account A and gives it to account B

Let’s go back to the ACID property:

• Atomicity ensures that no matter what happens during T1 (server crash, network outage…) , you can’t have $100 withdrawn from account A but not given to account B (this is A data inconsistency state).
• Isolation ensures that if T1 and T2 occur at the same time, eventually A will lose $150 and B will get $150, as opposed to other outcomes such as A losing $150 and B only getting $50 because T2 partially erased T1 (which is also inconsistent state).
• Persistence ensures that T1 does not disappear into thin air if a database crash occurs as soon as IT commits.
• Consistency ensures that money is not generated or lost in the system.

[The following parts are not important and can be skipped]

Modern databases do not use pure isolation as the default mode because it incurs a significant performance cost. SQL generally defines four isolation levels:

• Serializable (Serializable, SQLite default mode) : Highest level of isolation. Two simultaneous transactions are 100% isolated, and each transaction has its own “world.”
• Repeatable Read (MySQL default mode) : Each transaction has its own “world”, except for one case. If a transaction executes successfully and new data is added, this data is visible to other ongoing transactions. However, if a transaction successfully modifies a piece of data, the result is not visible to the running transaction. Therefore, the isolation between transactions is broken only for new data and remains isolated for existing data. For example, if transaction A runs “SELECT count(1) from TABLE_X” and then transaction B adds A new item to TABLE_X and commits it, the result will not be the same when transaction A runs count(1) again. This is called phantom read.
• Read Committed (Oracle, PostgreSQL, SQL Server default mode) : Repeatable Read + new isolation break. If transaction A reads data D, and data D is then modified (or deleted) and committed by transaction B, the change (or deletion) to the data is visible when transaction A reads data D again. This is called non-repeatable read.
• Read Uncommitted: The lowest level of isolation, Read Committed + new isolation breaks. If transaction A reads data D and then data D is modified by transaction B (but not committed and transaction B is still running), the modification is visible when transaction A reads data D again. If transaction B rolls back, then the second read of data D by transaction A is meaningless because it is A modification made by transaction B that never happened (rollback already happened). This is called dirty read.

Most databases add custom isolation levels (such as PostgreSQL, Oracle, SQL Server snapshot isolation) and do not implement all the levels in the SQL specification (especially the read uncommitted level).

The default isolation level can be overridden by the user/developer when establishing a connection (with a simple addition of one line of code).

Concurrency control

The real problem with ensuring isolation, consistency, and atomicity is writing to the same data (add, delete, delete) :

• If all transactions just read data, they can work simultaneously without changing the behavior of the other transaction.
• If (at least) one transaction is modifying data read by other transactions, the database needs to find a way to hide the changes from the other transactions. Furthermore, it needs to ensure that this modification operation is not erased by another transaction that cannot see these data modifications.

This problem is called concurrency control.

The simplest solution would be to execute each transaction sequentially (that is, sequentially), but this would not scale at all and would be inefficient with only one core working on a multi-processor/multi-core server.

Ideally, each time a transaction is created or cancelled:

• Monitor all operations for all transactions
• Check if parts of two (or more) transactions conflict because they read/modify the same data
• Rearrange operations in conflicting transactions to reduce conflicting portions
• Execute the conflicting parts in a certain order (while non-conflicting transactions are still running concurrently)
• Consider the possibility that the transaction will be cancelled

In more formal terms, this is a scheduling problem for conflicts. More specifically, this is a very difficult and CPU expensive optimization problem. Enterprise databases cannot afford to wait hours to find the best schedule for each new transaction activity, so they use less than ideal methods to avoid wasting more time on conflict resolution.

Lock manager

To solve this problem, most databases use locking and/or data versioning. This is a big topic, and I’m going to focus on locking, and a little bit of data versioning.

Pessimistic locking

The principle is:

• If a transaction requires a piece of data
• It locks the data
• If another transaction also needs this data
• It has to wait for the first transaction to release that data and that lock is called an exclusive lock.

But using an exclusive lock on a transaction that only reads data is expensive because it forces other transactions that only need to read the same data to wait. Hence another type of lock, the shared lock.

A shared lock looks like this:

• If A transaction only needs to read data A
• It assigns A “shared lock” to data A and reads it
• If the second transaction also needs to only read data A
• It assigns A “shared lock” to data A and reads it
• If the third transaction needs to modify data A
• It places an “exclusive lock” on data A, but must wait for the other two transactions to release their shared lock.

Similarly, if an exclusive lock is placed on a block of data, a transaction that only needs to read the data must wait for the exclusive lock to be released before a shared lock can be placed on the data.

Review images

The lock manager is a process that adds and releases locks, internally stores lock information in a hash table (the key word is locked data), and knows what each piece of data is:

• The lock that was added by the transaction
• Which transaction is waiting for data to unlock

A deadlock

But using locks can lead to a situation where two transactions are forever waiting for a piece of data:

Review images

In this figure:

• Transaction A places an exclusive lock on data 1 and waits to acquire data 2
• Transaction B places an exclusive lock on data 2 and waits for data 1 to be acquired

This is called a deadlock.

When a deadlock occurs, the lock manager chooses to cancel (roll back) a transaction in order to eliminate the deadlock. It was a tough decision:

• Killing transactions with the least amount of data modification (thus reducing rollback costs)?
• Kill the shortest duration transaction because users of other transactions wait longer?
• Killing transactions that can end in less time (avoiding a possible resource famine)?
• Once a rollback occurs, how many transactions are affected by the rollback?

Before making a selection, the lock manager needs to check for deadlocks.

A hash table can be thought of as a graph (see figure above) in which a loop indicates a deadlock. Because the checking loop is expensive (the graph of all the locks is huge), it is often solved in a simple way: by using timeout Settings. If a lock is not added within the timeout period, the transaction enters a deadlock state.

The lock manager can also check to see if a lock will become deadlocked before attaching it, but this is expensive to do perfectly. So these prechecks often set ground rules.

Two pieces of lock

The simplest way to achieve pure isolation is to acquire the lock at the beginning of a transaction and release it at the end. That is, you must wait to make sure you have all the locks before the transaction starts and release the locks you hold when the transaction ends. This works, but a lot of time is wasted waiting for all the locks.

A faster approach is the Two-Phase Locking Protocol (used by DB2 and SQL Server), where transactions are divided into Two phases:

• Growth phase: transactions can acquire locks, but cannot release them.
• Shrink phase: Transactions can release locks (for data that has already been processed and will not be processed again), but cannot acquire new locks.

Review images

The principle behind these two simple rules is:

• Release locks that are no longer in use to reduce wait time for other transactions
• Prevent the occurrence of inconsistencies when the data originally acquired by a transaction is modified after the transaction has started.

This rule works fine, with one exception: if the transaction is cancelled (rolled back) after modifying a piece of data and releasing the associated lock, and another transaction reads the modified value, the value is rolled back. To avoid this problem, all exclusive locks must be released at the end of the transaction.

Say a few words more

Of course, real databases use more complex systems, involving more types of locks (such as intention locks, Intention locks) and more granularity (row-level locks, page-level locks, partition locks, table locks, tablespace locks), but the principles are the same.

I will only explore purely lock-based approaches; data versioning is another approach to this problem.

Version control looks like this:

• Each transaction can modify the same data at the same time
• Each transaction has its own copy (or version) of the data
• If two transactions modify the same data and only one modification is accepted, the other will be rejected and the related transaction will be rolled back (or re-run)

This will improve performance because:

• Read transactions do not block write transactions
• Write transactions do not block reads
• No extra overhead of a “bloated and slow” lock manager

Data versioning performs better than locking in every respect except when two transactions write the same data. However, you will soon find that disk space is a huge drain.

Data versioning and locking mechanisms are two different perspectives: optimistic locking and pessimistic locking. There are pros and cons to both, and it all depends on the usage scenario (read more or write more). For data versioning, I recommend this excellent article on how PostgreSQL implements concurrency control for multiple versions.

Some databases, such as DB2 (up to version 9.7) and SQL Server (without snapshot isolation) use locking only. Others like PostgreSQL, MySQL and Oracle use a hybrid locking and mouse version control mechanism. I don’t know if there is a version-only database (let me know if you do).

A reader told me:

Firebird and Interbase use unlocked version control.

It’s interesting how versioning affects indexes: sometimes unique indexes duplicate, index entries exceed table rows, and so on.

If you have read the section on different levels of isolation, you know that increasing the isolation level increases the number of locks and the time a transaction waits to be locked. This is why most databases do not use the highest level of isolation (serialization) by default.

Of course, you can always look it up in the documentation of a major database (like MySQL, PostgreSQL or Oracle).

Log manager

We already know that to improve performance, databases store data in memory buffers. But if the server crashes when the transaction commits, the data that is still in memory at the time of the crash is lost, which breaks the persistence of the transaction.

You can write all the data to disk, but if the server crashes, only part of the data may end up being written to disk, breaking the atomicity of the transaction.

Any changes made to the transaction must either be undone or completed.

There are two ways to solve this problem:

• Shadow copies/pages: Each transaction creates its own copy of the database (or copies of parts of the database) and works based on this copy. If an error occurs, the copy is removed; Once successful, the database immediately uses a trick of the file system to replace the copy with the data and then discard the “old” data.
• Transaction log: A Transaction log is a storage space where the database writes information to the Transaction log before each write so that if a Transaction crashes or rolls back, the database knows how to remove or complete pending transactions.

WAL (write-ahead logging)

Shadow copies/pages create a lot of disk overhead when running large databases with many transactions, so modern databases use transaction logging. Transaction logs must be kept on stable storage, and I won’t dig into storage techniques, but at least RAID disks are a must in case of disk failure.

Most databases (at least Oracle, SQL Server, DB2, PostgreSQL, MySQL, and SQLite) use the Write-Ahead Logging Protocol (WAL) for transaction Logging. The WAL protocol has three rules:

• 1) Each change to the database generates a log record, which must be written to the transaction log before data can be written to disk.
• 2) Log records must be written in sequence; If record A occurs before record B, A must precede B.
• 3) When a transaction commits, the commit order must be written to the transaction log before the transaction succeeds.

Review images

This is done by the log manager. In simple terms, the log manager sits between the cache Manager and the Data Access Manager (which writes data to disk), Each UPDATE/DELETE/CREATE/commit/ROLLBACK operation is written to the transaction log before writing to disk. Easy, right?

Wrong answer! We’ve covered so much that by now you should know that everything about databases is cursed with the “database effect.” Okay, seriously, the question is how to find a way to log while maintaining good performance. If the transaction log is written too slowly, the whole thing slows down.

ARIES

In 1992, IBM researchers “invented” an enhanced version of WAL called ARIES. ARIES is more or less used in modern databases, not necessarily the same logic, but the concept behind AIRES is everywhere. I put the invention in quotes because, according to the MIT course, the IBM researchers “simply wrote best practices for transaction recovery.” AIRES paper was published when I was 5 years old, I don’t care about those sour scientists of the old gossip. In fact, I mention this allusion as a way to lighten your mood before moving on to the last technical point. I have read a great deal of this ARIES paper and find it very interesting. I’m only going to talk briefly about ARIES in this section, but I strongly recommend that if you want real knowledge, you read that paper.

ARIES stands for Algorithms for Recovery and Isolation Exploiting Semantics.

The technology has a twofold goal:

• 1) Log while maintaining good performance
• 2) Fast and reliable data recovery

There are several reasons why a database has to roll back a transaction:

• Because the user cancels
• Server or network failure
• Because transactions violate database integrity (such as a column with a unique constraint and a transaction adding duplicate values)
• Because of a deadlock

In some cases (such as a network failure), the database can resume transactions.

How is that possible? To answer this question, we need to understand the information stored in logs.

The log

Each transaction operation (add/delete/change) generates a log, which consists of the following contents:

• LSN: a unique Log Sequence Number. The LSN is assigned in chronological order *, which means that if operation A precedes operation B, the LSN of log A is smaller than the LSN of log B.
• TransID: ID of the transaction that generates the operation.
• PageID: indicates the position of the modified data on the disk. The smallest unit of disk data is a page, so the location of the data is the location of the page on which it is located.
• PrevLSN: Link to the last log record generated by the same transaction.
• UNDO: cancels the operation. For example, if the operation is an update, UNDO will either save the value/state of the element before the update (physical UNDO) or reverse the operation to the original state (logical UNDO) **.
• REDO: The method of repeating this operation. Again, there are two ways: either save the element value/state after the operation, or save the operation itself for repetition.
• … For your information, a ARIES log also has two fields: UndoNxtLSN and Type.

Further, each page on disk (the one that holds data, not the one that holds logs) records the last LSN to modify that data.

*LSN allocation is actually more complicated because it relates to how logs are stored. But the idea is the same.

** ARIES only uses logical UNDO because dealing with physical UNDO is too messy.

Note: As far as I know, PostgreSQL is the only one that doesn’t use UNDO and instead uses a garbage collection service to delete older versions of data. This has to do with PostgreSQL’s implementation of data versioning.

To better illustrate this, here is a simple logging illustration, which is created by querying “UPDATE FROM PERSON SET AGE = 18;” We assume that the query was executed by transaction 18. [translator’s note:]

Review images

Each log has a unique LSN, and logs linked together belong to the same transaction. Logs are linked in chronological order (the last log in the linked list is generated by the last operation).

Log buffer

To prevent logging from becoming a major bottleneck, the database uses log buffers.

Review images

When the query executor asks for a change:

• 1) The cache manager stores the changes in its own buffer;
• 2) The log manager stores the related logs in its own buffer;
• 3) At this point, the query executor considers the operation complete (so it can request another change);
• 4) Then (soon) the log manager writes the log to the transaction log, and an algorithm decides when.
• 5) Then (soon) the cache manager writes the changes to disk, and an algorithm decides when.

When a transaction commits, it means that steps 1, 2, 3, 4, 5 for each operation of the transaction have been completed. Writing a transaction log is fast because it simply “adds a log somewhere in the transaction log”; Writing data to a disk is even more complicated because you need to “write data in a way that can be read quickly.”

STEAL and FORCE policies

For performance reasons, it is possible to complete Step 5 after commit, since it is possible to restore transactions with REDO logs in the event of a crash. This is called the no-force policy.

The database can choose a FORCE policy (such as step 5 must be completed before commit) to reduce the load on recovery.

Another problem is choosing whether the data is written step by step (STEAL policy) or whether the buffer manager needs to wait for the commit command to write all at once (no-Steal policy). The choice between STEAL or no-steal depends on what you want: fast writes but slow recovery from UNDO logs, or fast recovery.

To summarize the impact of these strategies on recovery:

• STEAL/ no-force requires UNDO and REDO: high performance, but more complex logging and recovery processes (like ARIES). Most databases choose this strategy. Note: I have seen this in several academic papers and tutorials, but have not seen it explicitly stated in official documentation.
• STEAL/ FORCE only requires UNDO.
• No-steal/no-force only needs REDO.
• No-steal /FORCE requires nothing: worst performance and a huge amount of memory.

About the recovery

Ok, we have nice logs, let’s use them!

Let’s say the new intern crashes the database (first rule: It’s always the intern’s fault). You restart the database and the recovery process begins.

ARIES has three phases for recovering from a crash:

• 1) Analysis phase: The recovery process reads the entire transaction log to reconstruct the timeline of what happened during the crash, determine which transaction to roll back (all uncommitted transactions are rolled back) and which data to write to disk during the crash.
• 2) Redo stage: This level starts with one of the log records selected from the analysis and uses Redo to restore the database to its pre-crash state.

In the REDO phase, REDO logs are processed in chronological order (using LSN).

For each log, the recovery process needs to read the disk page LSN that contains the data.

If LSN (disk pages) >= LSN (logging), the data was written to disk before the crash (but the values have been overwritten by some operation after the log, before the crash), so nothing needs to be done.

If LSN (disk pages) < LSN (logging), the pages on disk will be updated.

REDO is done even for transactions that are being rolled back, because it simplifies the recovery process (although I’m sure modern databases don’t do this).

• 3) Undo phase: This phase rolls back all transactions that were not completed at the time of the crash. Rollback starts with the last log for each transaction, and UNDO logs are processed in reverse chronological order (using PrevLSN for logging).

During the recovery process, the transaction log must pay attention to the operation of the recovery process so that the data written to disk is consistent with the transaction log. One solution is to remove logging generated by cancelled transactions, but this is too difficult. Instead, ARIES logs compensation logs in the transaction log to logically remove logging for cancelled transactions.

When a transaction is cancelled “manually”, either by the lock manager (to eliminate deadlocks), or simply because of a network failure, the analysis phase is not needed. There are two memory tables for which REDO is required and which UNDO is required:

• Transaction table (holds the state of all current transactions)
• Dirty page table (holds what data needs to be written to disk)

These two tables are updated by the cache manager and transaction manager when new transactions occur. Because they are in memory, they are destroyed when the database crashes.

The task of the analysis phase is to rebuild the above two tables with the information from the transaction log after the crash. To speed up the analysis phase, ARIES introduces the concept of a check point, which is to write the contents of the transaction table and dirty page table, along with the last LSN, to disk from time to time. In the analysis phase, only the logs after the LSN need to be analyzed.

conclusion

Before writing this article, I knew how big the topic was and how time consuming writing such an in-depth article would be. I turned out to be overly optimistic, and it actually took twice as long as I expected, but I learned a lot.

If you want a good understanding of databases, I recommend this research paper, Database Systems Architecture, which has a good introduction to databases (110 pages) and can be read by non-computer professionals. This paper has helped me to make a writing plan for this paper. It does not focus on data structure and algorithm like this paper, but more on the concept of architecture.

If you read this article carefully, you should now know how powerful a database can be. Given the length of the article, let me remind you of what we learned:

• B+ tree index Overview
• A global overview of the database
• An overview of cost-based optimization with a special focus on join operations
• Overview of buffer pool management
• Overview of Transaction Management

But databases contain more clever tricks. For example, I did not address the following thorny issues:

• How do I manage database clusters and global transactions
• How do I create a snapshot while the database is running
• How to store (and compress) data efficiently
• How to Manage Memory

So, when you have to choose between a problematic NoSQL database and a rock-solid relational database, think twice. Don’t get me wrong, some NoSQL databases are great, but they are still young and address specific concerns of a small number of applications.

Finally, if someone asks you how databases work, you don’t have to run away. Now you can answer:

Review images

Or, let him or her read this article.