Algorithms for Selection, Projection, Sorting, and Aggregation

4
0

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 employees
WHERE 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 department
FROM 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 department
FROM 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

Selection vs Projection

Sorting: Producing Ordered Results

Sorting arranges records according to one or more keys.

SELECT employee_id, salary
FROM employees
ORDER 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 Sort

External Merge Sorting

When the data exceeds the available memory, the database may use external merge sorting:

  1. Read a portion that fits in memory.

  2. Sort it and write a sorted run to temporary storage.

  3. Repeat for the remaining input.

  4. 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_count
FROM employees
GROUP 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:

  1. Computes the group’s hash.

  2. Locates the matching group, checking the actual grouping values.

  3. 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

Hash vs Sort-Based Aggregation

How These Operations Work Together

Consider:

SELECT department, COUNT(*) AS employee_count
FROM employees
WHERE salary >= 50000
GROUP BY department
ORDER 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.

CS Core

Read Similar Blogs

Comments0