Core Components of Databases

DBMS architecture

This lesson discusses the core components required for a DBMS operation. The fine details of each DBMS implementation will vary, but generally, the core components remain the same.

Query processor

The query processor is responsible for receiving the user input and translating it into an execution format suitable for the execution engine. The query processor includes two submodules:

• Query parser

• Query optimizer

Query parser

The query parser reads the user input and translates it into an Abstract Syntax Tree (AST), which serves as an intermediate representation of the query for execution. This process involves parsing, tokenization, syntax validation, semantic analysis, and tree construction. AST is a syntactic representation of the user input in a hierarchical structure..

The illustration above gives an example of AST for the SQL query SELECT first_name, last_name FROM users WHERE user_id = 1.

• The medium blue boxes indicate leaf nodes, also called tokens, of the AST.

• The light blue boxes are internal nodes of AST, which eventually lead to leaf tokens.

Query optimizer

The query optimizer reads the AST from the query parser and arrives at an imperative optimized plan to execute the user input. It uses internal statistics such as data cardinality, placement, and local and remote execution costs to arrive at multiple execution plans.

An execution plan is a sequence of steps in the form of a directed dependency graph executed in a specific order to complete the user input. The query optimizer picks the most economical execution plan based on the internal statistics from multiple execution plans and passes it on to the execution engine.

Execution engine

The execution engine receives the execution plan from the query processor and executes it to fulfill the user input.

The execution engine coordinates with the storage engine to access and manipulate the data stored in the database and maintain the data's integrity and durability. The execution engine is also responsible for orchestrating the execution plan across distributed nodes in a distributed database.

Storage engine

The storage engine is the core module of DBMS. It is responsible for handling the storage and recovery of data in the database and facilitating access and manipulating data in the filesystem.

Transaction manager

The transaction manager is responsible for coordinating one or more operations on the data structures part of the storage structures module. It ensures that the entire sequence of operations is either executed successfully or rolled back, leaving no partial updates.

This guarantee allows end users to work with the assumption that the database will always be consistent before and after the execution of database operations. The transaction manager leverages the lock manager and the recovery manager to ensure that the visible data is always consistent with what the end user expects.

Lock manager

The lock manager is responsible for holding lock objects on database entities for currently executing database operations and ensures that concurrently running processes do not overwrite each other's values. This provides consistency and predictability.

The lock manager employs a data structure called a lock table to hold locks on database entities. The lock table is essentially a hash table that uses the hash of the entity identifier as the key. The value is a linked list of transactions that want to operate on database entities.

The transactions can request an exclusive write lock or shared read lock on database entities. Depending on the type of lock, the lock manager will either grant the appropriate access to the transaction or queue them up for execution.

The illustration above demonstrates an example of a lock manager data structure.

• The dark blue boxes indicate the database keys used to look up actual records on the database. Locks are acquired on the database keys.

• Medium blue circles indicate that the transactions have locks on the database keys. Only one transaction can acquire a lock on a given database key at any time.

  • Transaction T1 has a lock on the database key 1.

  • Transaction T3 has a lock on the database key 5.

  • Transaction T4 has a lock on the database key 3.

• Light blue circles indicate the transactions that are waiting for a lock on the database keys.

  • Transaction T2 is waiting for a lock on the database key 1.

Storage structures

Storage structures are the data structures laid out on the disk or memory for storing data for efficient retrieval and manipulation.

There are several on-disk data structures such as B-tree, B+ tree, and LSM; Similarly, there are several in-memory data structures such as hash index and bloom filter. The files stored on the filesystem can be data files or index files.

Data files are the primary files that store actual data records, and index files are additional metadata that act as a fast lookup pointer to data files. Multiple index files can point to a single data file, allowing for multidimensional lookups.

Cache manager

A block is the smallest data unit that an operating system can read from and write to a file. Since the operating system supports multiple devices, the block size can vary from one device to another. Therefore, the operating system exposes a virtual block called page, which are fixed size units irrespective of the underlying device used to mitigate varying block sizes.

Reading and writing to disk on every operation is expensive. To avoid this, DBMS provides a cache manager (also called a buffer manager) to cache disk pages in the main memory for faster lookups and to reduce disk access requests. First, the operating system loads the requested page into the main memory. Then, the operating system fetches subsequent requests for the same page from the main memory, which is called a cache hit. However, the buffer manager maintains a finite memory for caching disk pages. Therefore, when a page is requested, and the corresponding page is not in the main memory, it is called a cache miss.

Eventually, the buffer manager runs out of finite memory, and existing pages must be removed from the buffer manager to accommodate new pages. This process is called cache eviction. Several algorithms cater to efficient cache eviction policies, such as LRU and LFU.

Recovery manager

The recovery manager maintains an append-only data structure that stores every write operation applied to the DBMS in a log file for recovery. The recovery manager serves as a persistent intermediate store for all write requests.

Every page written is persisted in the main memory, referred to as the dirty page. All the dirty pages are batched and asynchronously synced with the disk for durability. Dirty pages are considered clean pages after they are flushed to disk. Every write request is also appended to a disk-resident append-only data structure before the client successfully completes the write in order to prevent data loss of dirty pages in the case of a crash or system restart.

The log file can then be used as a checkpoint to recover the data for the dirty pages. Finally, the operating system flushes all the dirty pages to disk and discards uncommitted transactions on system restart before making the system available for subsequent writes and reads.

Catalog

The catalog is a metadata store containing schema definitions of various database objects and indexes, users and their roles, and statistical information such as index cardinality and data placement.