============================================================================
CS 346 Fall '98 - Prof. Widom - Handout #9
LECTURE NOTES - Query processing lecture #1
============================================================================
Steps in database query processing
----------------------------------
Query string --> Parser
Query tree --> Checker
Valid query tree --> View expander
Valid tree w/o views --> Logical query plan generator
Logical query plan --> Query rewriter (heuristic)
Better logical plan --> Physical query plan generator (cost-based)
Selected physical plan --> Code generator
Executable code --> Execution engine
Running example
---------------
Student(ID, Name, Major) // ID is key
Course(Num, Dept) // Num is key
Taking(ID, Num) // (ID,Num) is key
Query to find all EE students taking at least one CS course:
SELECT DISTINCT Name
FROM Student, Course, Taking
WHERE Taking.ID = Student.ID
AND Taking.Num = Course.Num
AND Major = 'EE'
AND Dept = 'CS'
Parser
------
Produces tree representation of the query string:
Checker
-------
Verifies query tree against database schema:
- All tables in FROM clause exist
- All columns of tables exist
- No ambiguities in table references or unqualified attribute
references (table names usually added at this point)
- All comparisons, aggregations, etc. are type-compatible
View expander
-------------
Suppose Student is actually a view:
StudName(ID, Name)
StudMajor(ID, Major)
CREATE VIEW Student AS
SELECT StudName.ID, StudName.Name, StudMajor.Major
FROM StudName, StudMajor
WHERE StudName.ID = StudMajor.ID
Original query becomes:
Or "flattened":
Logical and physical query plans
--------------------------------
- Both are trees representing query evaluation
- Leaves of the tree represent data
- Internal nodes of the tree are "operators" over the data
- Logical plan is higher-level and algebraic
- Physical plan is lower-level and operational
- Logical plan operators correspond to query language constructs
- Physical plan operator correspond to implemented "access methods"
Logical plan operators
----------------------
- Extended relational algebra
- Leaves of logical plans are table names
- Basic operators: SELECT, PROJECT, CROSS-PRODUCT, UNION, DIFFERENCE
- Abbreviations: NATURAL-JOIN, THETA-JOIN, INTERSECT
- Extensions: RENAME, AGGREGATE/GROUP-BY, DISTINCT (+ others)
Logical query plan for running example query (3-way cross-product):
Using 2-way joins instead of 3-way cross-product:
Logical plan generation
-----------------------
Usually there's a straightforward mapping from a valid parse tree to a
"naive" logical query plan. The logical plan may then be rewritten to
a "better" one.
Push selections down in previous example:
Physical plan operators
-----------------------
- Leaves of physical plans are usually table names, sometimes indexes
or other information.
- Access methods for single tables:
* TABLE SCAN
* INDEX SCAN W/O CONDITION
* CONDITION-BASED INDEX SCAN
- Join methods:
* NESTED-LOOP JOIN (various algorithms/improvements)
* SORT-MERGE JOIN
* HASH JOIN (various algorithms)
- Other important operators:
* SORT
* GROUP
* AGGREGATE (may be combined with GROUP)
* UNION, EXCEPT, INTERSECT
- Operators often merged with other ones:
* SELECTION (APPLY-PRED)
* PROJECTION
* DISTINCT
- In a distributed system:
* SHIP
- In a parallel system:
* EXCHANGE
Possible physical plan for running example query:
Another possible physical plan:
Physical plan generation
------------------------
There are lots and lots of possible physical query plans for a given
logical plan. The physical plan generator (sometimes called "physical
plan enumerator") tries to select the one that will be "optimal",
usually with respect to response time or in some cases throughput.
=> This is the meatiest part of query processing!!!
Code generator
--------------
Translates physical query plan tree into executable code. Very
system-specific -- some systems may instead use a query plan
interpreter.
Some terminology
----------------
"Query processing" = entire process
"Query optimization" = rewriter + physical plan generator
"Query compilation" = entire process through code generation
"Query execution" = execution engine
Coming up
---------
- Query rewriting
- Passing information between physical operators
- Cost metrics for physical query plans
- Physical query plan enumeration
- Reducing the search space
- Further optimizations
Exercise
--------
Consider the following modification of our running example:
Student(ID, Name, Major) // ID is key
Course(Num, Dept) // Num is key
Took(ID, Num, Quarter) // (ID,Num) is key
Query to find all EE students who took at least one CS course in the
fall quarter 1998:
SELECT *
FROM Student, Course, Took
WHERE Took.ID = Student.ID
AND Took.Num = Course.Num
AND Student.Major = 'EE'
AND Course.Dept = 'CS'
AND Took.Quarter = 'Fall98'
Suppose:
- The DBMS supports NESTED-LOOP JOIN, SORT-MERGE JOIN, and HASH JOIN
- Each table can be accessed either with a TABLE SCAN or a
CONDITION-BASED INDEX SCAN (assume all relevant attributes are
indexed)
- For simplicity assume initially that the system will not perform a
NESTED-LOOP JOIN using an index on the inner relation's join attribute
Note: join associativity matters
Q: How many possible physical query plans are there for this query?
A:
Q: What if the system also supports NLJ with inner index?
Case (a): System can exploit 2 indexes on a table
Case (b): System can't exploit 2 indexes on a table
