Kaushik's Notes

Sequential vs index vs bitmap index scan

10 min read

Understanding Table Scan Methods in Databases

When a database executes a SQL query, it needs to retrieve data from tables. The method it uses to access this data significantly impacts query performance. Here are three common scan methods: Sequential Scan, Index Scan, and Bitmap Index Scan.

Example Scenario

Let’s use the following employees table and indexes for our examples (syntax is generally PostgreSQL-like):

CREATE TABLE employees (
    id SERIAL PRIMARY KEY,
    name VARCHAR(100) NOT NULL,
    department VARCHAR(50),
    salary INT,
    hire_date DATE,
    is_active BOOLEAN DEFAULT TRUE,
    country VARCHAR(50)
);
 
-- Create some indexes
CREATE INDEX idx_employees_salary ON employees (salary);
CREATE INDEX idx_employees_department ON employees (department);
CREATE INDEX idx_employees_is_active ON employees (is_active);
CREATE INDEX idx_employees_country ON employees (country);
CREATE INDEX idx_employees_dept_salary ON employees (department, salary);
 
-- Populate with some sample data (conceptual)
-- Imagine millions of rows in this table for a realistic scenario.
INSERT INTO employees (name, department, salary, hire_date, is_active, country) VALUES
('Alice Smith', 'Engineering', 70000, '2020-01-15', TRUE, 'USA'),
('Bob Johnson', 'Marketing', 65000, '2019-03-01', TRUE, 'Canada'),
('Charlie Brown', 'Engineering', 90000, '2021-07-22', TRUE, 'USA'),
('Diana Prince', 'HR', 50000, '2018-05-10', FALSE, 'UK'),
('Edward Nygma', 'Finance', 120000, '2017-11-01', TRUE, 'USA');
-- ... and many more rows

1. Sequential Scan (Full Table Scan)

Explanation

A Sequential Scan reads every single row from the table, one by one, from the beginning to the end. It then evaluates each row against the conditions in the WHERE clause of the query.

When It’s Used

  • No Suitable Index: If there are no indexes on the columns used in the WHERE clause, or if the existing indexes cannot be effectively used for the given query conditions (e.g., using a function on an indexed column without a functional index).
  • Small Tables: For very small tables, the overhead of reading the entire table sequentially can be less than the overhead of using an index (which involves reading parts of the index and then potentially random access to table rows).
  • Low Selectivity / High Percentage of Rows: When the query is expected to retrieve a large percentage of the table’s rows. In such cases, reading all data blocks sequentially can be more efficient than performing many random I/O operations that an index scan might incur for a large number of rows. The database optimizer estimates the cost, and if most rows match, a sequential scan is cheaper.
  • COUNT(*) without a WHERE clause: Often, SELECT COUNT(*) FROM table; will result in a sequential scan if there isn’t a very small, covering index.

Pros

  • Simple and straightforward.
  • Efficient for small tables.
  • Can be efficient if a large portion of the table needs to be accessed.

Cons

  • Very inefficient for large tables if only a small number of rows are needed.
  • Can lead to high I/O and CPU usage for large tables.

Query Example for Sequential Scan

-- Querying on a non-indexed column or a condition that matches many rows
SELECT name, salary
FROM employees
WHERE hire_date > '2022-01-01';

Reasoning: If hire_date is not indexed, or if a very large number of employees were hired after this date, the database might opt for a sequential scan. Similarly, a query like SELECT * FROM employees WHERE name LIKE '%son%'; (leading wildcard) would also likely result in a sequential scan as standard B-tree indexes can’t efficiently handle leading wildcards.

2. Index Scan (or Index Seek / Range Scan)

Explanation

An Index Scan uses an index to locate specific rows in a table. The database traverses the index structure (commonly a B-tree) to find entries that match the query conditions. These index entries contain pointers (e.g., Row IDs or CTIDs in PostgreSQL) to the actual data rows in the table heap. The database then uses these pointers to fetch the required rows.

  • Index-Only Scan: A special, more efficient type of index scan occurs if all the columns requested by the query are present within the index itself. In this case, the database can skip the table heap for pages marked all-visible in the visibility map (set by VACUUM), saving I/O. The index doesn’t store MVCC visibility, so for other pages Postgres still checks the heap; on a frequently updated table Heap Fetches in EXPLAIN ANALYZE can be high.

When It’s Used

  • High Selectivity: When the query conditions are highly selective, meaning they retrieve a small number of rows relative to the table size.
  • Indexed Columns in WHERE Clause: The WHERE clause contains conditions on columns that have suitable indexes.
  • Equality and Range Predicates: For conditions like column = value, column > value, column BETWEEN value1 AND value2, column IN (val1, val2), or column LIKE 'prefix%' on indexed columns.
  • ORDER BY on an Indexed Column: If the query orders results by an indexed column, an index scan can retrieve rows in the sorted order, avoiding a separate sort step.

Pros

  • Very fast for retrieving a small number of rows from a large table.
  • Can avoid sorting if the index order matches the ORDER BY clause.
  • Index-only scans are extremely efficient.

Cons

  • “Tipping Point”: If the index scan needs to retrieve a large number of rows (low selectivity), it can become less efficient than a sequential scan. This is because it might involve many random I/O operations to fetch data from the table heap for each indexed row, which can be slower than sequentially reading all blocks.
  • Requires suitable indexes to be created and maintained (which adds overhead to write operations like INSERT, UPDATE, DELETE).
  • Index structure itself consumes disk space.

Query Example for Index Scan

-- Querying with a highly selective condition on an indexed column
SELECT id, name, department
FROM employees
WHERE salary = 120000;

Reasoning: The salary column has an index (idx_employees_salary). If only a few employees have a salary of 120000, the optimizer will likely use an index scan on idx_employees_salary to quickly find these employees and then fetch their id, name, and department from the table.

-- Index-only scan example (if supported and applicable)
SELECT department, salary
FROM employees
WHERE department = 'Engineering' AND salary > 80000;

Reasoning: The idx_employees_dept_salary covers both department and salary. If the database can satisfy the query by only reading this index (without going to the main table), it will perform an index-only scan.

3. Bitmap Index Scan (and Bitmap Heap Scan)

Explanation

The Bitmap Scan approach typically involves a sequence of operations, often seen in PostgreSQL execution plans. Let’s break down the key components:

  • Bitmap Index Scan: * This is the initial step where the database scans a specific index (e.g., idx_employees_department for department = 'Engineering'). * Instead of fetching the table rows directly (like a regular Index Scan would for each found entry), it generates a bitmap in memory. * This bitmap is a data structure that indicates which table pages (or sometimes individual rows, depending on granularity) contain rows matching the index condition. A bit is set for each page/row that qualifies. * Multiple Bitmap Index Scans can be performed if there are multiple conditions on different indexes. For example, one for department = 'Engineering' and another for country = 'USA'.

  • BitmapAnd Scan / BitmapOr Scan: * If multiple Bitmap Index Scans were performed (because of multiple AND or OR conditions on different indexes), the resulting bitmaps need to be combined. * A BitmapAnd Scan takes two or more bitmaps and performs a bitwise AND operation on them. The resulting bitmap will only have bits set for pages/rows that were marked in all the input bitmaps. This is used for AND conditions (e.g., department = 'Engineering' AND country = 'USA'). * A BitmapOr Scan takes two or more bitmaps and performs a bitwise OR operation. The resulting bitmap will have bits set for pages/rows that were marked in any of the input bitmaps. This is used for OR conditions (e.g., department = 'Marketing' OR salary > 100000). * These operations are very efficient as they work on compact bitmap structures in memory.

  • Bitmap Heap Scan: * This is the final step where the actual data rows are retrieved from the table (the “heap”). * It uses the final, combined bitmap (produced by one or more Bitmap Index Scans, possibly followed by BitmapAnd/BitmapOr operations). * The database iterates through the table pages. If a page is marked in the final bitmap, that page is read from disk (if not already in memory). * The rows within that page are then checked against the original query conditions to retrieve only the relevant ones. * A key advantage is that pages are read from the table heap in physical order (or close to it), which can be more efficient than the potentially random I/O pattern of fetching individual rows scattered across the table, especially when a moderate number of rows are being retrieved.

In summary, the process often looks like this:

  1. One or more Bitmap Index Scans create initial bitmaps.
  2. If multiple bitmaps exist, they are combined using BitmapAnd Scan or BitmapOr Scan.
  3. The resulting bitmap is used by a Bitmap Heap Scan to fetch the actual rows.

When It’s Used

  • Multiple Conditions on Different Indexed Columns: When a query has multiple conditions in the WHERE clause connected by AND or OR, and these conditions apply to different indexed columns.
  • Moderately Selective Conditions: When individual index conditions are not highly selective (i.e., they match a moderate number of rows), but their combination (using AND) becomes more selective.
  • OR Conditions on Different Indexes: Bitmap scans are particularly good at handling OR conditions across different indexes.
  • Low Cardinality Columns: For columns with a small number of distinct values (low cardinality) where a standard B-tree index scan might still retrieve many row pointers scattered across the table.
  • When the optimizer estimates that fetching rows in table-page order (guided by the bitmap) is more efficient than many random accesses from standard index scans.

Pros

  • Efficiently combines results from multiple indexes using bitwise operations on bitmaps.
  • Good for queries with AND/OR predicates on different indexed columns.
  • Can convert many random I/O operations into more sequential I/O for table access, improving performance for moderately selective queries.

Cons

  • Overhead: There’s an overhead in creating the bitmap(s). If the number of matching rows is very small, a direct index scan might be faster.
  • Dense Bitmaps: If the bitmap is very “dense” (meaning a very large percentage of rows/pages match the conditions), a sequential scan might be chosen by the optimizer instead, as the benefit of the bitmap diminishes.
  • The bitmap itself consumes memory. Large bitmaps for very large tables can be an issue.

Query Example for Bitmap Index Scan

-- Querying with multiple conditions on different indexed columns
SELECT name, salary, department, country
FROM employees
WHERE department = 'Engineering' AND is_active = TRUE AND country = 'USA';

Reasoning: Here, we have conditions on department (indexed by idx_employees_department), is_active (indexed by idx_employees_is_active), and country (indexed by idx_employees_country). The database might perform:

  1. A Bitmap Index Scan on idx_employees_department for department = 'Engineering' to create bitmap1.
  2. A Bitmap Index Scan on idx_employees_is_active for is_active = TRUE to create bitmap2.
  3. A Bitmap Index Scan on idx_employees_country for country = 'USA' to create bitmap3.
  4. Combine these bitmaps using bitwise AND: final_bitmap = bitmap1 AND bitmap2 AND bitmap3.
  5. Perform a Bitmap Heap Scan using final_bitmap to retrieve the matching rows from the employees table.

Another example with OR:

SELECT name, salary, department
FROM employees
WHERE department = 'Marketing' OR salary > 100000;

Reasoning: The database could create one bitmap for department = 'Marketing' (using idx_employees_department) and another for salary > 100000 (using idx_employees_salary), then combine them with a bitwise OR, followed by a Bitmap Heap Scan.

Note: The actual execution plan chosen by a database optimizer depends on many factors, including table statistics (size, data distribution, cardinality), index availability, query structure, and database configuration parameters. Using EXPLAIN (or EXPLAIN ANALYZE in PostgreSQL) is crucial for understanding how a specific query is being executed.

Graph View

Backlinks