Basic SELECT Queries and Projection

A query in the relational model asks for a subset of the rows (selection) and a subset of the columns (projection) of one or more tables, optionally transformed by expressions. In relational algebra these are two independent operators:

SQL's `SELECT-FROM-WHERE` block realizes both at once: ```sql SELECT [DISTINCT] column_expr_1 [AS alias_1], column_expr_2, ... FROM table_or_tables WHERE predicate; ``` The `FROM` clause names the source relation(s) — for now, think of a single table; multi-table `FROM` clauses correspond to a Cartesian product and are properly explored under Joins in SQL. The `WHERE` clause is a predicate: a boolean-valued expression evaluated independently for each row of the source, built from comparison operators (`=`, `<>`, `<`, `>`, `<=`, `>=`), boolean connectives (`AND`, `OR`, `NOT`), pattern matching (`LIKE`), range and membership tests (`BETWEEN`, `IN`), and null tests (`IS NULL`). The `SELECT` clause is the projection list: a sequence of column references or arbitrary scalar expressions (arithmetic, string functions, `CASE` expressions) that determines the shape of the output, evaluated only for rows that survived the `WHERE` filter. Crucially, relational algebra projection is set-based — Π always removes duplicate tuples. SQL, however, models tables as multisets (bags) by default, so plain `SELECT` preserves duplicates; you must explicitly write `SELECT DISTINCT` to get true set semantics. This divergence between the algebra's mathematical purity and SQL's pragmatic bag semantics is one of the first places students' mental models need correcting, and it has real performance consequences: `DISTINCT` is not free — it forces the engine to detect and remove duplicate rows, typically via a sort or hash pass, adding a nontrivial cost that plain projection does not incur.

The written order vs. the logical evaluation order

SQL queries are written `SELECT ... FROM ... WHERE ...`, but the standard defines their meaning via a logical processing order that starts with `FROM`: 1. FROM — construct the source relation (for a single table, just that table; for multiple tables, the Cartesian product, refined later by `JOIN ... ON`). 2. WHERE — evaluate the predicate against each row of the FROM-result; keep only rows where it evaluates to `TRUE`. 3. SELECT — evaluate the projection list's expressions against each surviving row, producing the output columns. 4. DISTINCT (if present) — eliminate duplicate output rows from the projected result. This ordering is why you cannot reference a `SELECT`-list alias inside the same query's `WHERE` clause in standard SQL: at the point `WHERE` is logically evaluated, the `SELECT` list has not been computed yet. It also explains why aggregate functions and computed aliases behave the way they do once `GROUP BY` and `HAVING` enter the picture (foreshadowed, not covered, here).

Predicate evaluation: three-valued logic

A `WHERE` predicate does not simply return `TRUE`/`FALSE` — SQL uses three-valued logic (3VL): `TRUE`, `FALSE`, `UNKNOWN`. Any comparison involving a `NULL` operand (e.g. `salary > 50000` when `salary IS NULL`) evaluates to `UNKNOWN`, not `FALSE`. The `WHERE` clause keeps a row only if the predicate evaluates to `TRUE` — rows yielding `UNKNOWN` are discarded, exactly like `FALSE` rows, but they are not logically equivalent, which matters once you combine conditions with `NOT` or `OR`. Truth tables for 3VL (T = true, F = false, U = unknown): ``` AND | T F U OR | T F U NOT ----+--------- ----+--------- ---- T | T F U T | T T T T -> F F | F F F F | T F U F -> T U | U F U U | T U U U -> U ```

Step-by-step execution model

```pseudocode function EXECUTE_SELECT(table, predicate, projectionList, distinct): sourceRows = READ_ALL_ROWS(table) # FROM clause filteredRows = [] for row in sourceRows: # WHERE clause result = EVALUATE_PREDICATE(predicate, row) # returns TRUE, FALSE, or UNKNOWN if result == TRUE: filteredRows.append(row)

# FALSE or UNKNOWN rows are dropped projectedRows = [] for row in filteredRows: # SELECT clause outRow = [] for expr in projectionList: outRow.append(EVALUATE_EXPRESSION(expr, row)) projectedRows.append(outRow) if not distinct: return projectedRows # bag semantics, duplicates kept

# DISTINCT: duplicate elimination (conceptually a sort or hash pass) seen = HASH_SET() result = [] for row in projectedRows: key = HASH(row) if key not in seen: seen.add(key) result.append(row) return result ``` ```pseudocode function EVALUATE_PREDICATE(predicate, row):

# handles comparisons, AND/OR/NOT, IS NULL, LIKE, BETWEEN, IN

# returns one of {TRUE, FALSE, UNKNOWN} per three-valued logic match predicate: case Comparison(left, op, right): lval = EVALUATE_EXPRESSION(left, row) rval = EVALUATE_EXPRESSION(right, row) if lval is NULL or rval is NULL: return UNKNOWN return APPLY_OP(op, lval, rval) # TRUE or FALSE case IsNull(expr): return TRUE if EVALUATE_EXPRESSION(expr, row) is NULL else FALSE case And(p1, p2): return AND_3VL(EVALUATE_PREDICATE(p1, row), EVALUATE_PREDICATE(p2, row)) case Or(p1, p2): return OR_3VL(EVALUATE_PREDICATE(p1, row), EVALUATE_PREDICATE(p2, row)) case Not(p1): return NOT_3VL(EVALUATE_PREDICATE(p1, row))

# ... Between, In, Like handled as sugar over Comparison/Or ``` A production query engine never literally does a full table scan followed by a full-row filter loop — the query optimizer rewrites this logical plan into a physical plan that may use an index to jump directly to qualifying rows, push the projection earlier to shrink intermediate row width, or evaluate `DISTINCT` via sorting so duplicates become adjacent. The pseudocode above describes the logical semantics that any physical plan must reproduce exactly, regardless of the shortcuts it takes.

Time complexity. Let $n$ be the number of rows in the source table and $k$ the number of columns projected.

• A full table scan to evaluate `WHERE` against every row costs $O(n)$ predicate evaluations, each $O(1)$ or $O(p)$ where $p$ is the number of atomic conditions in the predicate — so scan-based filtering is $O(n \cdot p)$.
• If an index exists on a column used in an equality or range predicate, evaluation can be sped up to $O(\log n + m)$ where $m$ is the number of matching rows (a B-tree index lookup plus retrieval), which is why indexing is central to query performance — a topic developed alongside physical query processing.
• Projection itself, absent `DISTINCT`, is $O(n \cdot k)$: for every surviving row, compute $k$ output expressions. It is a linear pass, no comparison between rows required.
• `SELECT DISTINCT` requires detecting duplicate output rows. The two standard strategies are:
• Sort-based: sort the $m$ projected rows by all output columns, $O(m \log m)$, then scan once to drop adjacent duplicates, $O(m)$. Total $O(m \log m)$.
• Hash-based: insert each row into a hash set keyed by its full column tuple; average $O(m)$ expected time (assuming a well-behaved hash function and no adversarial collisions), $O(m)$ space for the set.

So plain projection is linear, but `DISTINCT` adds an $O(m \log m)$ or expected-$O(m)$ overhead and $O(m)$ auxiliary space — never assume `DISTINCT` is "free," especially over large intermediate results.

Space complexity. A streaming execution of `WHERE` + `SELECT` needs only $O(1)$ extra memory per row (or $O(k)$ for the current output row buffer) if the engine can emit rows as they are produced — this is the basis of pipelined query execution. `DISTINCT`, by contrast, needs $O(m)$ space to hold the hash set or to materialize the sort, because duplicate detection is inherently non-local: you cannot know a row is a duplicate without remembering rows you've already emitted.

Correctness argument. The semantics of `SELECT-FROM-WHERE` is correct by definition once the logical evaluation order is fixed, so "correctness" here means proving that any physical execution strategy produces the same bag of output rows as the canonical logical order. The key invariant a query optimizer must preserve is: > Predicate soundness invariant: a row $r$ appears in the WHERE-filtered set if and only if `EVALUATE_PREDICATE(predicate, r) = TRUE` under three-valued logic, evaluated using the original row's column values (not partially transformed ones). Any rewrite — pushing a selection below a projection, using an index instead of a scan, reordering conjuncts in an `AND` — is valid only if it preserves this invariant for every row. This is why, for example, a query optimizer may freely reorder the conjuncts of `WHERE a AND b` (evaluating `b` first if it's cheaper) as long as it correctly implements 3VL `AND`, but it may not silently treat `x > 5` as `FALSE` when `x` is `NULL` — that would violate the invariant and change which rows are kept versus discarded in queries involving `NOT`.

Tradeoffs. Bag semantics (plain `SELECT`) is faster and cheaper because no duplicate-detection pass is needed, but it can return misleading results when the caller actually wants distinct answers (e.g., "which departments have at least one high earner?" run without `DISTINCT` may repeat a department name once per qualifying employee). `DISTINCT`, conversely, gives set semantics but costs an extra sort/hash pass and forces the engine to fully materialize the projected result before it can guarantee no duplicate will appear later — this can break pipelining and increase memory pressure on large result sets.

Consider a table created (per SQL Data Definition and Schema Creation) as: ```sql CREATE TABLE Employee ( id INT PRIMARY KEY, name VARCHAR(30), dept VARCHAR(20), salary INT ); ``` with contents:

Run: ```sql SELECT dept, salary FROM Employee WHERE dept = 'Sales' AND salary > 60000; ```

Step 1 — FROM: the source relation is all 6 rows of `Employee`.

Step 2 — WHERE: evaluate `dept = 'Sales' AND salary > 60000` per row using 3VL.

Row 5 is instructive: even though its `dept` comparison alone is `FALSE`, note `AND` with `UNKNOWN` still yields `FALSE` here (from the 3VL `AND` table: `FALSE AND anything = FALSE`), so it is correctly excluded regardless of the salary being unknown.

Step 3 — SELECT (projection onto `dept, salary` for the 3 surviving rows):

Notice `91000` appears twice — rows 3 and 6 are different employees (Carla, Farid) but project to an identical `(dept, salary)` pair. Plain `SELECT` (bag semantics) returns 3 rows, with a duplicate.

Step 4 — add DISTINCT: ```sql SELECT DISTINCT dept, salary FROM Employee WHERE dept = 'Sales' AND salary > 60000; ``` Now a duplicate-elimination pass runs over the 3 projected rows (sort or hash on `(dept, salary)`), collapsing the two `('Sales', 91000)` rows into one:

Result: 2 rows. This single example demonstrates the full pipeline — FROM (6 rows) → WHERE (3 survive, with a correctly-handled `NULL` case) → SELECT (3 projected rows, one duplicate pair) → DISTINCT (2 final rows) — and shows concretely why `DISTINCT` is a separate, costed operation rather than an automatic property of projection.

`SELECT-FROM-WHERE` with projection is the operation executed, in some form, by essentially every application that touches structured data: a web server rendering a user's order history runs a filtered, projected `SELECT` against an orders table; a business intelligence dashboard issues thousands of such queries per hour against a data warehouse; an object-relational mapper (ORM) like Hibernate or Django's ORM translates method calls into exactly this SQL skeleton behind the scenes. Every relational database system — PostgreSQL, MySQL, Oracle, SQL Server, SQLite — implements this logical evaluation order as a hard constraint on its query optimizer, and every query plan visualizer (`EXPLAIN`) shows, in some form, the scan-filter-project-dedupe pipeline traced above. Understanding this skeleton is also the prerequisite for reading and writing more advanced constructs: a `JOIN` (see Joins in SQL) is really just an extended `FROM` clause feeding the same `WHERE`/`SELECT` pipeline; `GROUP BY` (see Aggregation and the GROUP BY Clause) inserts a grouping step between `WHERE` and `SELECT`; and `UNION`/`INTERSECT`/`EXCEPT` (see Set Operations in SQL) combine the outputs of multiple such pipelines using true set semantics, echoing the `DISTINCT` mechanics introduced here.

Ask the tutor: How does adding a `JOIN` change the FROM-WHERE-SELECT evaluation order and the complexity analysis you just learned?