In my previous article, I discussed database transactions and ACID properties.
Now, let's understand how databases actually store data.
Whenever we create a table and insert records, we see the data in rows and columns. But how is this data stored on disk? Does the database read one row at a time? How does it know where a particular row is stored?
Let's learn the following topics in this article:
- Tables
- Row ID
- Pages
- Disk I/O
- Heap
- Indexes
- Row-oriented and column-oriented storage
1. Tables
We know that a table contains rows and columns.
For example, consider an employee table.
| emp_id | name | salary | language |
|---|---|---|---|
| 1 | Anu | 10000 | English |
| 2 | Sam | 20000 | Telugu |
| 3 | John | 30000 | Hindi |
| 4 | Ravi | 40000 | English |
| 5 | Harry | 50000 | Telugu |
This is how we logically see the data.
But internally, databases store these records in pages on disk.
Before understanding pages, let's see what a Row ID is.
2. Row ID
A Row ID is an identifier used internally by a database to locate or reference a row.
It is different from the primary key we define in a table.
For example, emp_id is the primary key in our employee table. But databases may also maintain their own internal row identifiers.
In PostgreSQL, we have a system column called ctid, which tells us the physical location of a particular row version.
SELECT ctid, * FROM employees;
The result might look like:
| ctid | emp_id | name |
|---|---|---|
| (0,1) | 1 | Anu |
| (0,2) | 2 | Sam |
| (0,3) | 3 | John |
| (1,1) | 4 | Ravi |
| (1,2) | 5 | Harry |
Here, (0,1) means the row is at page 0, item position 1.
Unlike a primary key, ctid is not permanent. It can change when a row is updated or moved.
3. Pages
A page is a fixed-size block used to store and read data.
For example:
- PostgreSQL generally uses 8 KB pages.
- MySQL InnoDB generally uses 16 KB pages.
Let's assume each page can hold three employee records.
Page 0
| emp_id | name | salary |
|---|---|---|
| 1 | Anu | 10000 |
| 2 | Sam | 20000 |
| 3 | John | 30000 |
Page 1
| emp_id | name | salary |
|---|---|---|
| 4 | Ravi | 40000 |
| 5 | Harry | 50000 |
In reality, the number of rows a page can hold depends on their sizes and the space used for page metadata.
One important thing is that the database generally reads data in pages, not as individual rows directly from disk.
Suppose we need the record with emp_id = 2.
If Page 0 needs to be fetched from disk, the database reads that page into memory. Since the page also contains records 1 and 3, those records are available in the same page.
4. I/O (Input/Output)
I/O refers to reading data from or writing data to storage.
When a database needs a page that is not already in memory, it has to read it from disk.
Disk access is generally slower than accessing data from RAM.
So databases try to minimize unnecessary I/O operations.
Let's take an example.
Suppose we have 1,000 records, and each page holds 10 records.
Then we need approximately 100 pages to store those records, ignoring some storage overhead.
Now suppose we want to find a particular record but don't know which page contains it.
The database may need to read multiple pages until it finds the required record.
Reading 100 pages is more expensive than reading just one page, especially if those pages are not already in memory.
Does every query read data from disk?
No.
Databases also use memory to cache pages.
For example, PostgreSQL uses a memory area called Shared Buffers. The operating system also maintains a page cache.
When a page is read for the first time, it may need to be fetched from disk.
If the same page is needed again and is still cached in memory, the database may be able to access it without another physical disk read.
This reduces I/O and improves performance.
5. Heap
In PostgreSQL, ordinary tables use a storage structure called a Heap.
A heap is a collection of pages containing the actual table rows.
For example, the employee table might have:
Heap – Employees
| Page | Records |
|---|---|
| Page 0 | Anu, Sam, John |
| Page 1 | Ravi, Harry |
| Page 2 | Priya, Kiran, Rahul |
| Page 3 | Sneha, Arjun, Meena |
The actual data of the table is stored in these pages.
The important point about a PostgreSQL heap is that rows are not maintained in any particular order based on a column.
For example, even if we insert records in the order 1, 2, 3, 4, 5, we cannot assume that they will always remain physically stored in that order.
Now suppose we want to find an employee whose ID is 100.
Without knowing the location of that record, PostgreSQL may need to examine many heap pages to find it.
For a table with millions of records, this can require a lot of data to be read.
Databases maintain separate structures called indexes, which help locate records more efficiently.
6. Index
An index is a separate data structure that helps the database find the location of required records.
For example, suppose we create an index on emp_id.
The index keeps employee ID values along with references to their corresponding rows.
A simplified example:
| Employee ID | Row Location |
|---|---|
| 1 | (0,1) |
| 2 | (0,2) |
| 3 | (0,3) |
| 4 | (1,1) |
| 5 | (1,2) |
Here, the row location tells us which heap page and item contain the record.
Instead of checking every heap page, the database can use the index to find the required location.
Indexes are also stored in pages on disk. So reading an index can also involve I/O.
One commonly used index data structure is a B-tree.
An index doesn't replace the heap in PostgreSQL. It is maintained separately and contains information that helps locate the actual table records.
I'll cover indexes, B-trees, and how queries use indexes in more detail in a separate article.
7. Row-Oriented Database
In a row-oriented database, the values belonging to the same row are stored together.
PostgreSQL and MySQL InnoDB are examples of row-oriented databases.
Let's take our employee table.
| id | name | salary | language |
|---|---|---|---|
| 1 | Anu | 10000 | English |
| 2 | Sam | 20000 | Telugu |
| 3 | John | 30000 | Hindi |
| 4 | Ravi | 40000 | English |
In row-oriented storage, the data is organized approximately like this:
Page 0
[1, Anu, 10000, English]
[2, Sam, 20000, Telugu]
Page 1
[3, John, 30000, Hindi]
[4, Ravi, 40000, English]
The values of each employee are stored together.
Let's consider three queries.
Query 1: Find an employee's name
SELECT name
FROM employees
WHERE id = 2;
The database needs to find the row where id = 2.
Suppose there is no index on the ID column.
The database starts scanning the table pages.
First, it reads Page 0 and checks the employee IDs in that page.
It checks the first row, where id = 1. Since this is not the required ID, it moves to the next row.
The next row contains id = 2, so the database finds the required employee.
Since the row contains all the columns together, it can directly get the name Sam from that row.
If the record were not in Page 0, the database would continue checking the next pages until it found the matching row.
If an index is available and the database chooses to use it, it can locate the required row without scanning every table page.
Query 2: Fetch all employee details
SELECT *
FROM employees
WHERE id = 2;
Here, we need all columns of one employee.
Row-oriented storage is useful because all the values belonging to that row are stored together.
Query 3: Calculate the total salary
SELECT SUM(salary)
FROM employees;
Here, we only need the salary column.
But in row-oriented storage, salary values are stored along with the other columns of each employee.
So, when reading the table pages, the database may also bring unnecessary data into memory.
For a large table containing many columns, this can result in more data being read than we actually need.
This is one limitation of row-oriented storage for analytical queries.
8. Column-Oriented Database
In a column-oriented database, values belonging to the same column are stored together.
Let's consider the same employee table.
Instead of storing complete rows together, the data is organized by columns.
Each column can be divided into multiple blocks depending on the amount of data.
For example, let's assume each block holds two values.
ID column
Block 0: [1:1001, 2:1002]
Block 1: [3:1003, 4:1004]
Name column
Block 0: [Anu:1001, Sam:1002]
Block 1: [John:1003, Ravi:1004]
Salary column
Block 0: [10000:1001, 20000:1002]
Block 1: [30000:1003, 40000:1004]
Language column
Block 0: [English:1001, Telugu:1002]
Block 1: [Hindi:1003, English:1004]
Here, 1001, 1002, etc., represent row IDs.
For example, Sam:1002 and 20000:1002 belong to the same employee.
This is a simplified representation. Actual column-oriented databases may use row positions or other methods instead of storing an individual row ID with every value.
Column-oriented databases store values in column blocks, often in compressed form.
Let's use the same three queries.
Query 1: Find an employee's name
SELECT name
FROM employees
WHERE id = 2;
The database needs the ID and Name columns.
Assuming there is no index or other information to locate the value directly, it searches the ID blocks until it finds 2:1002.
Now it knows the row ID is 1002.
Next, it accesses the Name column and finds Sam:1002.
So the result is Sam.
Here, the database accesses two different columns to get the result.
Query 2: Fetch all employee details
SELECT *
FROM employees
WHERE id = 2;
Here, we need every column.
First, the database finds 2:1002 in the ID column.
Then it retrieves the corresponding values from the other columns using row ID 1002.
- Name:
Sam:1002 - Salary:
20000:1002 - Language:
Telugu:1002
Since values are stored column-wise, the database may need to read multiple column blocks to get the complete employee record.
This can involve more work compared with retrieving a complete row from row-oriented storage.
Similarly, updates or deletes involving several columns may require more work because the values are stored separately. Some column-oriented databases handle this using update or delete markers.
Query 3: Calculate the total salary
SELECT SUM(salary)
FROM employees;
Here, we only need the Salary column.
The database can read only the Salary blocks:
Block 0: [10000, 20000]
Block 1: [30000, 40000]
There is no need to read the Name, ID, or Language columns.
This reduces the amount of data read.
Column-oriented storage is very useful for queries involving aggregations over large numbers of records.
Compression
Column-oriented databases can also achieve better compression.
For example, suppose we have 1 million employee records, and many employees have the same language or department.
Since the values of a particular column are stored together, repeated values can be compressed efficiently.
In row-oriented storage, different data types and values are stored together as part of each row, so this type of compression may not be as effective.
9. Row-Oriented vs Column-Oriented Storage
| Row-Oriented | Column-Oriented |
|---|---|
| Stores data row by row | Stores data column by column |
| Good for reading complete records | Good for reading selected columns across many records |
| Generally efficient for frequent inserts and updates | Small updates can be more expensive |
| Commonly used for OLTP | Commonly used for OLAP |
| Aggregations over a few columns may read unnecessary data | Aggregations can read only the required columns |
| Compression is generally less effective | Often achieves better compression |
| PostgreSQL, MySQL InnoDB | Amazon Redshift, Google BigQuery, ClickHouse |
OLTP (Online Transaction Processing) usually involves frequent inserts, updates, deletes, and fetching individual records.
For example, creating an order, updating customer details, or retrieving a particular employee.
OLAP (Online Analytical Processing) usually involves queries that process many records, such as calculating total sales, generating reports, or finding average salaries.
Both types of databases can execute these operations. The difference is in how their storage is organized and the workloads they are generally optimized for.
Top comments (0)