Query Processing in Data Management

• The lecture is about Information and Data Management, specifically towards query processing.

Relational Model Recap

• A relation is a set of tuples sharing the same domains.
• Domains are sets that describe potential values for a tuple at a specific position.
• Tuples (or vectors) are ordered and finite sequences of values.

SQL Query Language Recap

• SELECT extracts data from a database.
• Clauses define the operations to perform on the database
• SELECT clause specifies which columns to include in the result and applies functions (sum, avg, etc.). This is called Projection
• DISTINCT clause removes duplicate rows from the result.
• FROM clause computes the Cartesian Product or Join over specified tables.
• WHERE clause selects tuples that satisfy a given condition
• GROUP BY clause groups tuples with matching values in specified columns
• HAVING clause filters grouped tuples based on a condition.
• ORDER BY clause sorts the result

Today's Agenda

• The plan is to start with a high-level overview of query parsing, optimization and execution.
• Another database query language is relational Algebra (RA).

Query Processors

• Query processors are responsible for handling database queries.
• A DBMS includes a transaction manager, a query processor, and a storage manager.
• A query processor sits between queries (from an application) and the DBMS
• Disks and the operating system work together to access the Storage Manager.

Query Preprocessing

• Queries undergo a series of preprocessing steps before evaluation.
• The query processor transforms the query into application programs, object code, embedded DML precompiler or DML compiler, DDL interpreter, data query evaluation engine and storage manager, connected via DB API

Query Processing Steps

• Query processing involves translating a query into relational algebra, optimizing the algebra expression, and executing the plan.
• Evaluation engines generate the query result which then pass through the parser and translator, a query optimizer, evaluation engine, and Statistics/Access Paths for data

Query Answering

• Queries are stated in a high-level, declarative database language (e.g., SQL).
• DB language mapped to relational algebra for further processing.
• The query translates into a low-level execution plan.
• Expression that can be used at the physical level of the file system for relational databases i.e. physical relational algebra
• Physical relational algebra extends relational algebra with primitives for searching internal data structures.

Parser and Translator

• Queries are translated to an internal form
• Translation involves a declarative DB language expressing "what should be found," and queries are evaluated in various ways
• Scanner tokenizes the query into keywords, table names, attributes, etc.
• Parser checks syntax and verifies relations, attributes, and data types.
• Result of scanning/parsing is to either obtain an executable query or an error.
• Translation into relational algebra is necessary for evaluating the query and serves as the exchange format between DBMS components
• Algebra allows for symbolic calculations, therefore query optimization
• Operators can be annotated with execution algorithms
• Evaluation primitives refer to a specific operator

Evaluation Primitives

• Evaluation primitives refer to a specific operator
• Tuple scan operators
• Tuple selection operators
• Index scan operators
• Various join operators
• Sort operator
• Duplicate elimination operator

Translating queries

• Relational algebra is important in SQL queries

Relational Completeness (Codd's Theorem)

• Establishes equivalence between Relational Algebra and Tuple/Domain Calculus
• Relational Algebra is a variable-free language
• Tuple/Domain Calculus (equivalent to first-order logic) is a logical language with variables and quantification.
• Relational completeness
• Query languages equivalent in expressive power to Relational Algebra
• It helps to identify the expressive power of a query language
• It doesn't mean that any database query can be expressed in this language

Query Execution

• Query optimization determines order of relational algebra operators with an operator tree.
• Algorithms evaluate each single relational algebra operator
• An evaluation plan annotates expressions with a detailed strategy.
• Operators are measured through real time and abstract costs
• Cost is determined via the number of disk accesses (or CPU time, networks)
• Disk accesses are the predominant factor, and have an average seek costs multiplied by number of seeks, also read and write block costs

Query Optimization

• Query Processor uses a Query Optimizer at its core
• Translation into relational algebra creates first query plan
• Query optimizer transforms naive query into an efficient plan
• includes choice of physical operators, sequence & grouping
• Plan is then annotated and handed over to evaluation engine

Optimization Rewrites

• Query optimizers rewrite canonical plans into more efficient evaluation plans
• It does this through query rewriting, cost estimation and evaluation plan generation
• This involves physics, schema and statistics in the cost model

Query Preparation

• Basic mapping converts declarative queries into a suitable internal format.
• Keywords are replaced by respective operators, maintaining relations, attributes, and conditions such as with SQL:
• SELECT becomes Project
• FROM maps to Cartesian Product
• WHERE turns into Selection

Operator Trees

• Evaluation plans use tree-shaped sequences of relational algebra operators. These have:
  • Leaf nodes as relations
  • Internal nodes as operator with one or many children

Summary & Relational Algebra

• SQL queries are translated into an abstract operator tree, represented by relational algebra statements.
• Algebra equivalence transforms the tree using heuristics or cost-based optimization.
• Same semantics, different costs.
• Algorithm operators will be replace the original operators
• SQL Explain statements can show a DBs operator tree, including what is really used

Brief History of Relational Algebra

• Made popular by Edgar Frank "Ted" Codd in 1970
• Theoretical foundation of relational databases
  • Describes how to retrieve information from relations
  • Lead to the development of SQL i.e. tuple/domain calculi
• Relational algebra helps understand optimization of queries

SQL vs. RA

• SQL
• Declarative, describes desired results without detailing computation steps
• RA
• Procedural, shows step-by-step procedure for result computation

Relational Algebra

• Algebra allows building expressions by applying operators to operands.
• There is the ability to study symbolic manipulation
• Algebra of arithmetics uses operators such as * +/ and constants like 15
• Operands contain variables to stand for relations (with constants)
• Relational algebra helps optimize dbs

RA Basics

• RA can be categorized via: * elementary, new relational, additional operations
• Elementary: * set algebra: union, intersect, difference or cartesian product
• Then there are the relational types, i.e. renames, projections and selections
• With all sorts of joins, division, etc as additional types

Example Relations Schema

• Examples use Student, Course, and Exam tables with defined schemas.

Example tables - Student

• Student includes student number and attributes

exam has student, course, plus resulting numeric grade

Quick Meta Discussion: Metadata - Data

• Data, it includes structural and semantics

Before Starting with RA Operators

• Each operator uses either a unary expression or some bi-nary algebra operand
• It returns a result to a relation instance withing a closed mathematical sytem

RA Selection

• It applies a boolean predicate to select tuples (rows) with it's conditions
• Use a connection of operand clauses with boolean constants

Selection (σ) examples

• Includes example for female students in Student
• Includes example of course exams with number over 3 in Exam

Natural Joins to Relations

• Can use selection to set natural equals on relations
• It shows the student and the classes they are in through their relation

RA - Rename ρ

• Renames avoids conflict of names and gives explicit names to relation
• The operator breaks a large RA into smaller subexpressions.
• To make a clearer distinction, can use arrows

Exclamation for RA

• Renaming creates aliases in querie

RA - Cartesian product ×

• It makes new combined relations by combinin each tuple/relation with another

This new relation is useless, but a proper selection is actually a join

Cartesian products

• Selecting result combined can be achieved with these

Theta Joins

• Combines tuples from source relations that are commonly related through the boolean
• There is often also an inner or normal join
• To specify join types, and show two attribute having the shame domain

Equi-join

• Joins using equality conditions
• It may only have equality statements between attributes - so, a theta but equal

Natural Join

• Joins the equal values, or joins with equality on same attributes, is most used join operator

Operator Precedence

• Unary - selection, projection
• Binary - cross product, Cartesian Order: 1) Unary 2) Cross and Joins 3) Union/minus 4) Intersection