Module 10: Query Evaluation

Overview

The Two-Tier Architecture

Also called the client/server architecture.

• Application:
  • User interaction: query input, presentation of results.
  • Application-specific tasks.
• Database Server:
  • DDL evaluation.
  • DML compilation: selection of a query plan for a query.
  • DML execution.
  • Concurrency control.
  • Buffer management: rollback and failure recovery.
• File System:
  • Storage and retrieval of unstructured data.

Query Evaluation

Steps in evaluating a query \(Q\):

1. Parsing, view expansion, and type and authorization checking of \(Q\).
2. Translation of \(Q\) to a formulation \(E_Q\) in the relational algebra.
3. Optimization of \(E_Q\):
   • Generates an efficient query plan \(P_Q\) from \(E_Q\).
   • Uses statistical metadata about the database instance.
4. Execution of query plan \(P_Q\):
   • Uses access methods to access stored relations.
   • Uses physical relational operators to combine relations.

Considerations:

• How relations are stored, that is, physically represented.
• Choice of physical relational operators to answer complex queries.
• How intermediate results are managed.

Relational Algebra

Relational Algebra: Overview

Idea

Define a relational algebra (RA) consisting of a set of operations on the universe \(\mathcal{U}\) of finite relations over an underlying universe of values \(D\) of a database instance \(\mathbf{DB}\).

\[ (\mathcal{U}; R_0, \dots, R_k, \times, \sigma, \pi, \cup, -, \text{elim}, c_1, c_2, \dots) \]

Constants:

• \(R_i\) relation name (one for each relation name in a signature \(\rho\))
• \(c_i\) constant (one for each constant in \(\mathbf{D}\))

Unary operators:

• \(\sigma\) selection (removes rows)
• \(\pi\) duplicate preserving projection (removes columns)
• \(\text{elim}\) duplicate elimination

Binary operators:

• \(\times\) cross product
• \(\cup\) multiset union
• \(-\) multiset difference

Relational Algebra: Syntax

Definition

Given a database signature \(\rho = (R_1 / k_1, \dots, R_n / k_n)\) and a set of constants \(\{c_1, c_2, \dots\}\), a relational algebra (RA) query is an expression \(E\) given as follows:

\[ \begin{aligned} E &::= R_i \\ &\quad | \; c_j \\ &\quad | \; \sigma_{\#i = \#j}(E_1) \\ &\quad | \; \pi_{\#i_1, \dots, \#i_m}(E_1) \\ &\quad | \; \text{elim } E_1 \\ &\quad | \; E_1 \times E_2 \\ &\quad | \; E_1 \cup E_2 \\ &\quad | \; E_1 - E_2 \end{aligned} \]

We write \(\text{Eval}(E, \mathbf{DB})\) to denote the table computed by evaluating the RA query \(E\), and \(\text{Cnum}(E)\) to denote its arity.

Relational Algebra: Semantics

• The semantics of \(\text{Eval}(E, \mathbf{DB})\) is given by appeal to the range-restricted relational calculus with multiset semantics defined in Module 4. In particular, we write:

  \[ \text{Answers}(Q, \mathbf{DB}) \]

  to denote the answers to RC query \(Q\) over \(\mathbf{DB}\).

• We also assume the following, where arity \(n\) and RA subquery \(E_i\) will be clear from context:

  1. \(S_i\) is a table with arity \(\text{Cnum}(E_i)\) and extension \(\text{Eval}(E_i, \mathbf{DB})\).
  2. \(\bar{x}\) is short for variables \(x_1, \dots, x_n\).

Relation name (for \(R_i / n \in \rho\)): \(\text{Eval}(R_i, \mathbf{DB}) = \text{Answers}(\{\bar{x} \mid R_i(\bar{x})\}, \mathbf{DB}), \text{ where } \text{Cnum}(R_i) = n.\)

Constant: \(\text{Eval}(c) = \text{Answers}(\{(x) \mid x = c\}, \mathbf{DB}), \text{ where } \text{Cnum}(R_i) = 1.\)

Selection: \(\text{Eval}(\sigma_{\#i = \#j}(E_1), \mathbf{DB}) = \text{Answers}(\{\bar{x} \mid S_1(\bar{x}) \land (x_i = x_j)\}, \mathbf{DB}),\) \(\text{where } \text{Cnum}(\sigma_{\#i = \#j}(E_1)) = \text{Cnum}(E_1).\)

Projection: \(\text{Eval}(\pi_{\#i_1, \dots, \#i_m}(E_1), \mathbf{DB}) = \text{Answers}(\{(x_{i_1}, \dots, x_{i_m}) \mid \exists x_{i_{m+1}}, \dots, x_n. S_1(\bar{x})\}, \mathbf{DB}),\) \(\text{where } \text{Cnum}(\pi_{\#i_1, \dots, \#i_m}(E_1)) = m \text{ and } (i_1, \dots, i_n) \text{ is a permutation of } (1, \dots, n).\)

Duplicate elimination: \(\text{Eval}(\text{elim } E_1, \mathbf{DB}) = \text{Answers}(\{\bar{x} \mid \text{elim } S_1(\bar{x})\}, \mathbf{DB}),\) \(\text{where } \text{Cnum}(\text{elim } E_1) = \text{Cnum}(E_1).\)

Cross product: \(\text{Eval}(E_1 \times E_2, \mathbf{DB}) = \text{Answers}(\{(\bar{x}, \bar{y}) \mid S_1(\bar{x}) \land S_2(\bar{y})\}, \mathbf{DB}),\) \(\text{where } \text{Cnum}(E_1 \times E_2) = \text{Cnum}(E_1) + \text{Cnum}(E_2).\)

Multiset union: \(\text{Eval}(E_1 \cup E_2, \mathbf{DB}) = \text{Answers}(\{\bar{x} \mid S_1(\bar{x}) \lor S_2(\bar{x})\}, \mathbf{DB}),\) \(\text{where } \text{Cnum}(E_1 \cup E_2) = \text{Cnum}(E_1).\)

Multiset difference ("EXCEPT ALL"): \(\text{Eval}(E_1 - E_2, \mathbf{DB}) = \text{Answers}(\{\bar{x} \mid S_1(\bar{x}) \land \neg S_2(\bar{x})\}, \mathbf{DB}),\) \(\text{where } \text{Cnum}(E_1 - E_2) = \text{Cnum}(E_1).\)

Alternative "NOT EXISTS" semantics: \(\text{Eval}(E_1 - E_2, \mathbf{DB}) = \text{Answers}(\{\bar{x} \mid S_1(\bar{x}) \land \neg(S_1(\bar{x}) \land S_2(\bar{x}))\}, \mathbf{DB}),\) \(\text{where } \text{Cnum}(E_1 - E_2) = \text{Cnum}(E_1).\)

Note: Multiset difference with the alternative semantics can be used when translating subqueries in SQL conditions.

Expressiveness

Range-restricted RC queries with multiset semantics have at least the expressiveness of RA queries. For the other direction, we have the following.

Theorem (Codd)

For every domain-independent RC query, there is an equivalent RA expression. Thus, RA is a relationally complete query language.

An outline of translating range-restricted RC queries to RA queries:

\[ \begin{aligned} \text{RCmap}(R_i(x_1, \dots, x_k)) & = R_i \\ \text{RCmap}(\varphi \land x_i = x_j) & = \sigma_{\text{Vmap}(x_i) = \text{Vmap}(x_j)}(\text{RCmap}(\varphi)) \\ \text{RCmap}(x_i = c_j) & = c_j \\ \text{RCmap}(\exists x_i.\varphi) & = \pi_{\text{Vmap}(\text{Fv}(\varphi) - \{x_i\})}(\text{RCmap}(\varphi)) \\ \text{RCmap}(\varphi_1 \land \varphi_2) & = \text{RCmap}(\varphi_1) \times \text{RCmap}(\varphi_2) \\ \text{RCmap}(\varphi_1 \lor \varphi_2) & = \text{RCmap}(\varphi_1) \cup \text{RCmap}(\varphi_2) \\ \text{RCmap}(\varphi_1 \land \neg \varphi_2) & = \text{RCmap}(\varphi_1) - \text{RCmap}(\varphi_2) \end{aligned} \]

1. Must ensure \(\text{Fv}(Q_1) \cap \text{Fv}(Q_2) = \emptyset\) for \(\land\) case, and...
2. Must define \(\text{Vmap}\), an appropriate mapping of variables to column positions.
3. Need to add a top-level elim and projection to the RA expression.

Relational Algebra: Implementation

The multiset semantics of RA enables implementations of its operators that mostly avoid the need to store intermediate results.

Idea

An implementation for an RA operator provides a cursor OPEN/FETCH/CLOSE interface.

In particular, any implementation of an RA operator:

1. Implements the cursor interface to produce answers.
2. Uses the same interface to get answers from its children.

Providing at least one physical implementation for this protocol for each operator enables evaluating RA queries.

Example: An implementation of selection in an object-oriented language could be as follows.

// select_{#i=#j}(Child)
        OPERATOR child;
        int i, j;

public:
    OPERATOR selection(OPERATOR c, int i0, int j0)
    {
        child = c;
        i = i0;
        j = j0;
    }

    void open() { child.open(); }

    tuple fetch() {
        tuple t = child.fetch();
        if (t == NULL || t.attr(i) == t.attr(j))
            return t;
        return this.fetch();
    }

    void close() { child.close(); }

This implementation is fully pipelined since it requires a constant space overhead.

Note

❗

Concept Explanation from ChatGPT:

Fully pipelined execution means query operators process and pass tuples directly to the next operator without storing intermediate results. Each operator fetches data on-demand and streams it dynamically, reducing memory usage and improving efficiency. This approach is fast and resource-efficient but may not work for blocking operations like sorting.

A fully pipelined implementation exists for most of the other operators as well.

• constant:

  First fetch returns the constant; next fetch fails.

• cross product:

  Simple nested loops algorithm.

• duplicate preserving projection:

  Eliminate unwanted attributes from each tuple.

• multiset union:

  Simple concatenation.

• multiset difference:

  Nested loops algorithm that checks for a tuple in the inner loop.

  WARNING: The multiset difference implementation only works with the alternative semantics.

• relation name:

  A simple file scan of the primary index (an artifact of standard physical design) for the relation.

• duplication elimination:

  Remember tuples that have been returned.

The implementation just sketched will work, but plans will be inefficient.

Efficiency can be improved in a number of ways:

1. Use concrete (usually disk-based) data structures for efficient searching, e.g., choosing a Btree for the primary index (more on this following).
2. Use better algorithms to implement the operators based on SORTING or HASHING.
3. Rewrite the RA expression to an equivalent expression enabling a more efficient implementation (topic of next section):
   • remove unnecessary operations such as duplicate elimination
   • apply "always good" transformations, heuristics that commonly work
   • perform cost-based join order selection
   • introduce STORE operations using memory to factor computation of common subexpressions

Relation Names and Indexing

Standard Physical Design

A standard physical design for a relational schema defines the following for each relation name \(R\):

1. A primary index for \(R\) materializing its extension as a concrete data structure.
2. Zero or more secondary indices for \(R\) materializing projections of the primary index for \(R\) as concrete data structures.

A materialization of a relation adds an additional record identifier (RID) attribute to the relation.

Secondary indices usually include the RID attribute of the primary index in their projection of \(R\).

We add an index scan operation to RA: \(\sigma_\varphi(\langle \text{index} \rangle)\), where \(\varphi\) is a condition supplying search values for the underlying data structure.

Assuming \(k = \text{Cnum}(\langle \text{index} \rangle)\) and \(\varphi\) is the condition "\(\#i = c\)", an index scan is equivalent to:

\[ \pi_{\#1, \dots, \#k}(\sigma_{\#i = \#k+1}(\langle \text{index} \rangle \times c)). \]

Query Optimization

Finding an optimal plan is computationally not feasible; an optimizer looks for reasonable query plans.

Query Optimization: General Approach

• Generate all physical plans equivalent to the query.
• Choose the plan with the lowest cost.

All physical plans equivalent to the query?

• Cannot be done in general: Undecidable if a query is (un-)satisfiable (equivalent to an empty plan)
• Very expensive for even conjunctive queries: Selecting the best join order
• In practice:
  1. Consider only plans of a certain form (restrictions on the search space).
  2. Focus on eliminating really bad query plans.

The plan having the lowest cost?

• How do we determine which plan is the best one?
  • Not possible to run the plan to find out.
  • Instead, estimate the cost based on statistical metadata collected by the DBMS on database instances.
• Next unit: Reviews a simple cost model based on disk I/O, with the following assumptions:
  • Uniformity: All possible values of an attribute are equally likely to appear in a relation.
  • Independence: The likelihood that an attribute has a particular value (in a tuple) does not depend on the values of other attributes.

Cost Estimation

A Simple Cost Model

• For a materialized relation \(R\) with an attribute \(A\), we keep:

  • \(|R|\): The cardinality of \(R\) (number of tuples in \(R\)).
  • \(b(R)\): The blocking factor for index \(R\).

  Note

  ❗

  Concept Explanation from ChatGPT:

  The "blocking factor" \(b(R)\) in this context refers to the number of tuples from the relation \(R\) that can be stored in a single block or page of memory or storage. It helps in estimating the cost of accessing and processing data by determining how many blocks or pages are required to store and retrieve the entire relation \(R\).

  It is typically calculated as:

  \[ b(R) = \frac{\text{Block size (in bytes)}}{\text{Tuple size (in bytes)}} \]

  If the blocking factor is high, it means more tuples can fit in a block, reducing the number of I/O operations needed.

  • \(\text{min}(R, A)\): The minimum value for \(A\) in \(R\).
  • \(\text{max}(R, A)\): The maximum value for \(A\) in \(R\).
  • \(\text{distinct}(R, A)\): The number of distinct values of \(A\).
  • Based on these values, we estimate the cost of physical plans.

Strategy 1: Use Primary Index

• Selection of \(N\) tuples from relation \(R\) using a clustered primary index has a cost of \(2 + \frac{N}{b(R)}\).

Strategy 2: Use Secondary Index

• NOTE: In the query plan, \(\#3\ell\) refers to column \(3\) of the left argument of the nested cross product operator \(\times\).
• Selection of \(N\) tuples from relation \(R\) using an unclustered secondary index has a cost of \(2 + N\).

Strategy 3: Scan the Primary Index

Selection of \(N\) tuples from relation \(R\) by an exhaustive scan of its primary index has a cost of \(\frac{|R|}{b(R)}\).

Cost of Other Relational Operations

Costs of physical operations in block reads and writes:

• Selection

  \[ \text{cost}(\sigma_{\varphi}(E)) = (1 + \epsilon_{\varphi}) \text{cost}(E) \]

• Nested Loop Join (\(R\) is the outer relation):

  \[ \text{cost}(R \times S) = \text{cost}(R) + \left(\frac{|R|}{b}\right) \text{cost}(S) \]

• Nested Index Join (\(R\) is the outer relation, \(S\) is the inner relation, and B-tree has depth \(d_S\)):

  \[ \text{cost}(R \times \sigma_{\varphi}(S)) = \text{cost}(R) + d_S |R| \]

• Sort-Merge Join:

  \[ \text{cost}(R \bowtie_{\varphi} S) = \text{cost}(\text{sort}(R)) + \text{cost}(\text{sort}(S)) \]

  where

  \[ \text{cost}(\text{sort}(E)) = \text{cost}(E) + \left(\frac{|E|}{b}\right) \log\left(\frac{|E|}{b}\right) \]

Size Estimation

Cost estimation requires an estimate of the size of operation results.

Selectivity estimates for a condition \(\sigma_{\varphi}(R)\) are defined as:

\[ \text{sel}(\sigma_{\varphi}(R)) = \frac{|\sigma_{\varphi}(R)|}{|R|} \]

An optimizer estimates selectivity using simple rules based on its statistics:

• \(\text{sel}(\sigma_{A = c}(R)) \approx \frac{1}{\text{distinct}(R, A)}\)
• \(\text{sel}(\sigma_{A \leq c}(R)) \approx \frac{c - \text{min}(R, A)}{\text{max}(R, A) - \text{min}(R, A)}\)
• \(\text{sel}(\sigma_{A \geq c}(R)) \approx \frac{\text{max}(R, A) - c}{\text{max}(R, A) - \text{min}(R, A)}\)

For Joins:

• General join (where \(\varphi\) is an equality on column with attribute name \(A\) of \(R\) and \(B\) of \(S\)):

  \[ |R \bowtie_{\varphi} S| \approx |R| \frac{|S|}{\text{distinct}(S, B)} \]

  or equivalently:

  \[ |R \bowtie_{\varphi} S| \approx |S| \frac{|R|}{\text{distinct}(R, A)} \]

• Foreign key join (e.g., \(\texttt{ACCOUNT}\) and \(\texttt{BANK}\) where \(\varphi\) is \(\texttt{bank} = \texttt{name}\)):

  \[ |R \bowtie_{\varphi} S| = |R| \frac{|S|}{|S|} = |R| \]

Many joins are foreign key joins, like this one.

More Advanced Statistics

A simple model for cost estimation was presented. In practice, more complex models are used, including:

• Histograms to approximate non-uniform distributions
• Correlations between attributes
• Uniqueness (keys) and containment (inclusions)
• Sampling methods
• Etc.

"Always Good" Transformations

• Push selections:

  \[ \sigma_{\varphi}(E_1 \bowtie_{\theta} E_2) = \sigma_{\varphi}(E_1) \bowtie_{\theta} E_2 \]

  for \(\varphi\) involving columns of \(E_1\) only (and vice versa).

• Push projections:

  \[ \pi_V(R \bowtie_{\theta} S) = \pi_V(\pi_{V_1}(R) \bowtie_{\theta} \pi_{V_2}(S)) \]

  where \(V_1\) is the set of all columns of \(R\) involved in \(\theta\) and \(V\) (similarly for \(V_2\)).

• Replace products by joins:

  \[ \sigma_{\varphi}(R \times S) = R \bowtie_{\varphi} S \]

These rewrites reduce the space of plans to search.

Join Order Selection

• Joins are associative: \(R \bowtie S \bowtie T \bowtie U\) can be equivalently expressed as:
  1. \(((R \bowtie S) \bowtie T) \bowtie U\)
  2. \((R \bowtie S) \bowtie (T \bowtie U)\)
  3. \(R \bowtie (S \bowtie (T \bowtie U))\)
  4. Try to minimize the intermediate result(s).

• Moreover, it is important to decide which of the subexpressions is evaluated first.

  • e.g., cost of nested loop join is not symmetric.

  Note

  ❗

  Concept Explanation from ChatGPT:

  This point implies that while the join expressions are mathematically equivalent due to the associative property of joins, their costs can differ significantly depending on the order of evaluation and the size of intermediate results.

Summary

Relational algebra serves as the foundation for efficient SQL implementation by:

• Providing a connection between the conceptual and physical levels.
• Expressing query execution in manageable pieces.
• Allowing the use of efficient algorithms and data structures.
• Offering mechanisms for query optimization through logical transformations, including simplifications based on integrity constraints.

Key points:

• Database performance relies heavily on the physical database design.
• Understanding the basics of query evaluation aids in making sound physical design decisions.
• Performance is also highly influenced by transaction management (covered in the next module).