Introduction
A SQL query describes the result you need, but the database must choose algorithms to produce it. Filtering rows, returning columns, sorting results, and calculating totals each involve different kinds of work.
These operations are called selection, projection, sorting, and aggregation. Understanding their main execution methods helps explain why similar-looking queries can have very different costs.
Selection: Finding Matching Rows
Selection keeps rows that satisfy a condition. In SQL, this commonly corresponds to WHERE.
SELECT *FROM employeesWHERE department = 'Engineering';Two common access methods are:
Method | How it works | Often useful when |
|---|---|---|
Table scan | Examines records and tests the condition | No suitable index exists, or many rows qualify |
Index access | Uses an index to locate candidate entries | The condition matches a useful index and narrows the data sufficiently |
During a scan, the database typically reads table pages and evaluates the condition for their records.
With suitable index access, it can locate matching entries more directly. If the index lacks required columns, additional row lookups may be necessary.
A B+ Tree can support equality and range conditions. Hash-based access primarily supports equality searches.
An index is not always the cheaper option. When most records qualify, scanning pages can cost less than performing many separate lookups.
Projection: Returning Required Columns
Projection chooses which attributes appear in the result.
SELECT departmentFROM employees;For ordinary SQL projection, the database can read each qualifying record and emit the requested column. Duplicate values remain.
For example, departments might be returned as:
department |
|---|
Engineering |
Finance |
Engineering |
Classical relational projection removes duplicates. SQL requires DISTINCT when that behavior is wanted:
SELECT DISTINCT departmentFROM employees;Two common duplicate-elimination techniques are:
Hashing: Track values already encountered and emit each distinct value once.
Sorting: Arrange values together, then retain one representative from each equal group.
If a suitable index already contains the required values, it may reduce table access or provide useful ordering.
Requesting fewer columns can reduce result size and intermediate processing. It does not necessarily reduce the number of table pages read in a row-based storage system.
Selection vs Projection
Sorting: Producing Ordered Results
Sorting arranges records according to one or more keys.
SELECT employee_id, salaryFROM employeesORDER BY salary DESC;In-Memory Sorting
When the required data fits in the available sort memory, the database can sort it in RAM.
A comparison-based sort typically requires approximately O(n log n) comparisons for n records, although actual algorithms and optimizations vary.
External Merge Sort
External Merge Sorting
When the data exceeds the available memory, the database may use external merge sorting:
Read a portion that fits in memory.
Sort it and write a sorted run to temporary storage.
Repeat for the remaining input.
Merge the runs into the required order.
If too many runs exist to merge at once, additional merge passes may be needed. Temporary reads and writes add to the cost.
A suitable ordered index can sometimes avoid a separate sort. A query combining ORDER BY with a small LIMIT may also use a top-N technique that retains only the best candidates.
Sorting is not always a separate execution step.
Aggregation: Calculating Summaries
Aggregation combines values to produce results such as counts, sums, and averages.
SELECT department, COUNT(*) AS employee_countFROM employeesGROUP BY department;The database must associate each employee with the correct department group and maintain its count.
Two common algorithms are hash aggregation and sort-based aggregation.
Hash Aggregation
The database uses a hash table whose entries represent groups.
For each input record, it:
Computes the group’s hash.
Locates the matching group, checking the actual grouping values.
Updates the aggregate state.
For COUNT(*), that state includes a counter. For AVG(salary), it can include a running sum and a count of non-null salaries.
Hash aggregation does not require sorted input. However, many groups or large aggregate states can exceed available memory and require spilling or partitioning.
Sort-Based Aggregation
The database processes records ordered by the grouping columns.
Records belonging to the same group appear together, allowing the database to accumulate a group’s result before moving to the next group.
If the input is not already suitably ordered, a sort may be required first. An index or an earlier operation may provide that ordering.
GROUP BY does not guarantee output order. Add ORDER BY when the displayed order matters.
Hash vs Sort-Based Aggregation
How These Operations Work Together
Consider:
SELECT department, COUNT(*) AS employee_countFROM employeesWHERE salary >= 50000GROUP BY departmentORDER BY employee_count DESC;A simplified data flow is:
Stage | Required work |
|---|---|
Access and selection | Find employees earning at least 50000 |
Column handling | Retain values needed for grouping and counting |
Aggregation | Count qualifying employees in each department |
Sorting | Arrange department counts from highest to lowest |
The database might scan or use an index for selection, then choose hash or sort-based aggregation.
Sorting by the calculated count generally requires ordering the aggregate results; an index on the original department column does not directly provide that order.
Actual plans can combine operations or process them in parallel.
What Determines the Algorithm?
The optimizer considers more than the SQL keywords:
How many records are expected to qualify.
Which indexes and input orderings are available.
How many distinct groups are expected.
How much memory is available.
Whether intermediate results may spill to storage.
Execution plans reveal the selected methods. Where actual measurements are available, compare estimated and observed record counts, memory use, and temporary-storage activity.
Summary
Selection commonly uses scans or indexes, while projection returns required columns and may use hashing or sorting for duplicate elimination. Sorting can happen in memory, through external merging, or sometimes be avoided using existing order.
Aggregation commonly uses hashing or ordered processing. The best combination depends on the data, available access paths, and memory, so execution plans are essential for understanding the work behind a query.
Be the first to add a comment.