Copyright © 2016 Ramez Elmasri and Shamkant B.

Navathe
 CHAPTER 18

Strategies for Query Processing

Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe

Introduction
 DBMS techniques to process a query
 Scanner identifies query tokens
 Parser checks the query syntax
 Validation checks all attribute and relation names
 Query tree (or query graph) created
 Execution strategy or query plan devised
 Query optimization
 Planning a good execution strategy

Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 18- 3

Query Processing

Figure 18.1 Typical steps when processing a high-level query

Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 18-4
18.1 Translating SQL Queries into
Relational Algebra and Other Operators
 SQL
 Query language used in most RDBMSs
 Query decomposed into query blocks
 Basic units that can be translated into the
algebraic operators
 Contains single SELECT-FROM-WHERE
expression
 May contain GROUP BY and HAVING clauses

Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 18- 5

Translating SQL Queries (cont’d.)
 Example:

 Inner block

 Outer block

Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 18- 6

Translating SQL Queries (cont’d.)
 Example (cont’d.)
 Inner block translated into:

 Outer block translated into:

 Query optimizer chooses execution plan for each

query block

Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 18- 7

Additional Operators Semi-Join and
Anti-Join
 Semi-join
 Generally used for unnesting EXISTS, IN, and
ANY subqueries
 Syntax: T1.X S = T2.Y
 T1 is the left table and T2 is the right table of the
semi-join
 A row of T1 is returned as soon as T1.X finds a
match with any value of T2.Y without searching for
further matches

Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 18- 8

Additional Operators Semi-Join and
Anti-Join (cont’d.)
 Anti-join
 Used for unnesting NOT EXISTS, NOT IN, and
ALL subqueries
 Syntax: T1.x A = T2.y
 T1 is the left table and T2 is the right table of the
anti-join
 A row of T1 is rejected as soon as T1.x finds a
match with any value of T2.y
 A row of T1 is returned only if T1.x does not match
with any value of T2.y

Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 18- 9

18.2 Algorithms for External Sorting
 Sorting is an often-used algorithm in query
processing
 External sorting
 Algorithms suitable for large files that do not fit
entirely in main memory
 Sort-merge strategy based on sorting smaller
subfiles (runs) and merging the sorted runs
 Requires buffer space in main memory
 DBMS cache

Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 18- 10

 Figure 18.2 Outline of the sort-merge algorithm for external sorting
Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 18-11
Algorithms for External Sorting (cont’d.)
 Degree of merging
 Number of sorted subfiles that can be merged in
each merge step
 Performance of the sort-merge algorithm
 Number of disk block reads and writes before
sorting is completed

Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 18- 12

18.3 Algorithms for SELECT
Operation
 SELECT operation
 Search operation to locate records in a disk file
that satisfy a certain condition
 File scan or index scan (if search involves an
index)
 Search methods for simple selection
 S1: Linear search (brute force algorithm)
 S2: Binary search
 S3a: Using a primary index
 S3b: Using a hash key
Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 18- 13
Algorithms for SELECT Operation
(cont’d.)
 Search methods for simple selection (cont’d.)
 S4: Using a primary index to retrieve multiple
records
 S5: Using a clustering index to retrieve multiple
records
 S6: Using a secondary (B+ -tree) index on an
equality comparison
 S7a: Using a bitmap index
 S7b: Using a functional index

Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 18- 14

Algorithms for SELECT Operation
(cont’d.)
 Search methods for conjunctive (logical AND)
selection
 Using an individual index
 Using a composite index
 Intersection of record pointers
 Disjunctive (logical OR) selection
 Harder to process and optimize

Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 18- 15

Algorithms for SELECT Operation
(cont’d.)
 Selectivity
 Ratio of the number of records (tuples) that satisfy
the condition to the total number of records
(tuples) in the file
 Number between zero (no records satisfy
condition) and one (all records satisfy condition)
 Query optimizer receives input from system
catalog to estimate selectivity

Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 18- 16

18.4 Implementing the JOIN
Operation
 JOIN operation
 One of the most time consuming in query
processing
 EQUIJOIN (NATURAL JOIN)
 Two-way or multiway joins
 Methods for implementing joins
 J1: Nested-loop join (nested-block join)
 J2: Index-based nested-loop join
 J3: Sort-merge join
 J4: Partition-hash join
Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 18- 17
 Implementing the JOIN Operation
(cont’d.)

Figure 18.3 Implementing

JOIN, PROJECT, UNION,
INTERSECTION, and
SET DIFFERENCE by
using sort-merge, where R
has n tuples and S has m
tuples. (a) Implementing
the operation

Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 18-18

Implementing the JOIN Operation
(cont’d.)

Figure 18.3 (cont’d.) Implementing JOIN, PROJECT, UNION, INTERSECTION, and

SET DIFFERENCE by using sort-merge, where R has n tuples and S has m tuples.
(b) Implementing the operation

Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 18-19

Implementing the JOIN Operation
(cont’d.)

Figure 18.3 (cont’d.) Implementing JOIN, PROJECT, UNION, INTERSECTION, and

SET DIFFERENCE by using sort-merge, where R has n tuples and S has m tuples.
(c) Implementing the operation

Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 18-20

Implementing the JOIN Operation
(cont’d.)

Figure 18.3 (cont’d.) Implementing JOIN, PROJECT, UNION, INTERSECTION, and

SET DIFFERENCE by using sort-merge, where R has n tuples and S has m tuples.
(d) Implementing the operation

Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 18-21

Implementing the JOIN Operation
(cont’d.)

Figure 18.3 (cont’d.) Implementing JOIN, PROJECT, UNION, INTERSECTION, and

SET DIFFERENCE by using sort-merge, where R has n tuples and S has m tuples.
(e) Implementing the operation

Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 18-22

Implementing the JOIN Operation
(cont’d.)
 Available buffer space has important effect on
some JOIN algorithms
 Nested-loop approach
 Read as many blocks as possible at a time into
memory from the file whose records are used for
the outer loop
 Advantageous to use the file with fewer blocks as
the outer-loop file

Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 18- 23

Implementing the JOIN Operation
(cont’d.)
 Join selection factor
 Fraction of records in one file that will be joined
with records in another file
 Depends on the particular equijoin condition with
another file
 Affects join performance
 Partition-hash join
 Each file is partitioned into M partitions using the
same partitioning hash function on the join
attributes
 Each pair of corresponding partitions is joined
Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 18- 24
Implementing the JOIN Operation
(cont’d.)
 Hybrid hash-join
 Variation of partition hash-join
 Joining phase for one of the partitions is included
in the partition
 Goal: join as many records during the partitioning
phase to save cost of storing records on disk and
then rereading during the joining phase

Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 18- 25

18.5 Algorithms for PROJECT and
Set Operations
 PROJECT operation
 After projecting R on only the columns in the list of
attributes, any duplicates are removed by treating
the result strictly as a set of tuples
 Default for SQL queries
 No elimination of duplicates from the query result
 Duplicates eliminated only if the keyword DISTINCT
is included

Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 18- 26

Algorithms for PROJECT and Set
Operations (cont’d.)
 Set operations
 UNION
 INTERSECTION
 SET DIFFERENCE
 CARTESIAN PRODUCT
 Set operations sometimes expensive to
implement
 Sort-merge technique
 Hashing

Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 18- 27

Algorithms for PROJECT and Set
Operations (cont’d.)
 Use of anti-join for SET DIFFERENCE
 EXCEPT or MINUS in SQL
 Example: Find which departments have no
employees

becomes

Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 18- 28

18.6 Implementing Aggregate
Operations and Different Types of JOINs
 Aggregate operators
 MIN, MAX, COUNT, AVERAGE, SUM
 Can be computed by a table scan or using an
appropriate index
 Example:

 If an (ascending) B+ -tree index on Salary exists:

 Optimizer can use the Salary index to search for the
largest Salary value
 Follow the rightmost pointer in each index node
from the root to the rightmost leaf
Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 18- 29
Implementing Aggregate Operations and
Different Types of JOINs (cont’d.)
 AVERAGE or SUM
 Index can be used if it is a dense index
 Computation applied to the values in the index
 Nondense index can be used if actual number of
records associated with each index value is stored
in each index entry
 COUNT
 Number of values can be computed from the index

Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 18- 30

Implementing Aggregate Operations and
Different Types of JOINs (cont’d.)
 Standard JOIN (called INNER JOIN in SQL)
 Variations of joins
 Outer join
 Left, right, and full
 Example:

 Semi-Join
 Anti-Join
 Non-Equi-Join
Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 18- 31
18.7 Combining Operations Using
Pipelining
 SQL query translated into relational algebra
expression
 Sequence of relational operations
 Materialized evaluation
 Creating, storing, and passing temporary results
 General query goal: minimize the number of
temporary files
 Pipelining or stream-based processing
 Combines several operations into one
 Avoids writing temporary files
Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 18- 32
Combining Operations Using
Pipelining (cont’d.)
 Pipelined evaluation benefits
 Avoiding cost and time delay associated with
writing intermediate results to disk
 Being able to start generating results as quickly as
possible
 Iterator
 Operation implemented in such a way that it
outputs one tuple at a time
 Many iterators may be active at one time

Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 18- 33

Combining Operations Using
Pipelining (cont’d.)
 Iterator interface methods
 Open()
 Get_Next()
 Close()
 Some physical operators may not lend
themselves to the iterator interface concept
 Pipelining not supported
 Iterator concept can also be applied to access
methods

Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 18- 34

18.8 Parallel Algorithms for Query
Processing
 Parallel database architecture approaches
 Shared-memory architecture
 Multiple processors can access common main
memory region
 Shared-disk architecture
 Every processor has its own memory
 Machines have access to all disks
 Shared-nothing architecture
 Each processor has own memory and disk storage
 Most commonly used in parallel database systems

Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 18- 35

Parallel Algorithms for Query
Processing (cont’d.)
 Linear speed-up
 Linear reduction in time taken for operations
 Linear scale-up
 Constant sustained performance by increasing the
number of processors and disks

Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 18- 36

Parallel Algorithms for Query
Processing (cont’d.)
 Operator-level parallelism
 Horizontal partitioning
 Round-robin partitioning
 Range partitioning
 Hash partitioning
 Sorting
 If data has been range-partitioned on an attribute:
 Each partition can be sorted separately in parallel
 Results concatenated
 Reduces sorting time
Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 18- 37
Parallel Algorithms for Query
Processing (cont’d.)
 Selection
 If condition is an equality condition on an attribute
used for range partitioning:
 Perform selection only on partition to which the
value belongs
 Projection without duplicate elimination
 Perform operation in parallel as data is read
 Duplicate elimination
 Sort tuples and discard duplicates

Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 18- 38

Parallel Algorithms for Query
Processing (cont’d.)
 Parallel joins divide the join into n smaller joins
 Perform smaller joins in parallel on n processors
 Take a union of the result
 Parallel join techniques
 Equality-based partitioned join
 Inequality join with partitioning and replication
 Parallel partitioned hash join

Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 18- 39

Parallel Algorithms for Query
Processing (cont’d.)
 Aggregation
 Achieved by partitioning on the grouping attribute
and then computing the aggregate function locally
at each processor
 Set operations
 If argument relations are partitioned using the
same hash function, they can be done in parallel
on each processor

Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 18- 40

Parallel Algorithms for Query
Processing (cont’d.)
 Intraquery parallelism
 Approaches
 Use parallel algorithm for each operation, with
appropriate partitioning of the data input to that
operation
 Execute independent operations in parallel
 Interquery parallelism
 Execution of multiple queries in parallel
 Goal: scale up
 Difficult to achieve on shared-disk or shared-
nothing architectures
Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 18- 41
18.9 Summary
 SQL queries translated into relational algebra
 External sorting
 Selection algorithms
 Join operations
 Combining operations to create pipelined
execution
 Parallel database system architectures

Copyright © 2016 Ramez Elmasri and Shamkant B. Navathe Slide 18- 42