Lezione 9
SQL is a declarative language so when you write an sql query you are not telling the computer in which order do the operation and what algorithm use for the query. In pratice, an SQL query:
SELECT * FROM STUDENTS WHERE REGION='UK';Is transformed by the relational DBMS into an extended relational algebra expression:
We seen very different possibilities: primary file structure, presence or not of an indexing, range partition. How selective is this query? How many tuples do i expect? Is it a sorted field or not? Is it indexed or not? dense, sparse? Everything we studied so far is to execute restrictions.
Query Optimizer
The name is misleading because it seems like it gives you the optimal exection plan. But this is not true, it just gives you a reasonable plan very quickly. It is surely better than random execution but it doesn’t guarantee you that it’s the optimal one. The reason is that there are too many choices to explore and ti is unfeasable from computational point of view to explore them all.
The query optimizer chooses the operator, the order of the operators and the algorithms used in for execute your query. The first optimization happens at relational algebra level. Let’s see an example:
In this case i first join all students, then apply restriction region=UK then i calculate average vote. But this is not efficient.
A simple way to improve it is by changing the order of the operation. If i:
- first restrict students
- then i join exams
- then calculate average I will join less tables thus reducing execution time.
Greedy Approach in Relational Algebra
Even in relational algebra you cannot explore all the possibilities. So the rule of thumb is a greedy approach: do first the operations that reduces the size (restrictions) of the table and the result of intermediate tables. And so last the operations that increase the table. Usually, the JOIN operation is the last i should do (if feasable), while restriction should have priority.
That’s not the only thing that the optimizer does for you. It also have to choose the algorithms used to implement these operators. So we will see the algorithms used for the main operation. Thanks to this we will understand what are the options that the optimizer has to optimize a query.
Relational Algebra Note with pointer to that note
Strategies for Query Processing
Restriction
On Restriction algorithms
A search algorithm is used for restrictions. We already saw in previous lessons all the different possibilites from linear search to indexing using
-Tree, clustering or bitmap
The cost of restriction (
- NET=1. It will costs me NP/2
- NET = K, then NP. It’s enough that you have to look for two tuples and you need to do a full scan
Sorting fields:
- NET=1. It will costs me:
. - NET=k. If K < BFR, then again it is
Indexing:
- Non sorted, NET=1. B+ index h+1 (h to the leaves, +1 to read the data).
- If it is sorted you have still
but is smaller because you have sparse index for each page. - NET=k - If it is not sorted you pay
.
Cardenas Formula: This year it will not be explained, skip it if you find it in the exercise. By the end it doesn’t make any different. It will be something like
The cost of reading data depends on the file structure and indexing or not. The worst case is full scan.
Projection
Projection is an operation that we indicate with the following syntax:
Think if your data is stored row wise in multiple pages. What happens?
Students has a record size of R (say
It will costs me a full scan to read all the table, then after projection the data becomes smaller. As conseguence of this, the BFR of the projection will be higher. The total cost will be:
Projection on non unique values field
If we just use region, what happens?
Relationa Algebra is Set based, so we don’t have repeated values in set. If there are like 4 region, i will get 4 values. As conseguence of this, i should scan the entire table and pay a full scan plus the
- BFR for indexes unsorted file
- Number of different values Ofcourse, here the problem is how do you remove duplicate, from an algorithmic point of view.
- Quadratic full scan is not efficient
- Sorting data and then scan taking only the first is usually a good choice But in this case, we are not working in primary storage memory (RAM). We are working on secondary storage memory (DISK) and we need to use a special sorting called Sort Merge. In secondary storage memory, we are sorting pages and we want to reduce the number of I/O operations. This is also called External Sorting.
Let’s see how does SORT MERGE is used:
Sort Merge Algorithm for External Sorting
General Idea
- Sort small subfiles called runs
- Merge sorted runs, creating larger subfiles that are merged in turn.
- Repeating until you have no more runs to sort
The sort-merge algorithm requires buffer space in main memory, where the actual sorting and merging is performed.
We indicate with
Special case: file fit entirely in main memory
Usually we don’t have problem when the entire file fit into the main memory and we don’t need this algorithm. If
Sort Merge Algorithm
Sort Step
Let’s consider a
Until now, the costs of I/O operations is
Merge Step
The next step is called the merge step. We define the degree of merge as “the number of sorted subfiles that can be merged in each merge step”. This value depends on the buffer size. In our example, i have three available pages so i can merge three times for run.
What happens is that runs are loaded into main memory and a parallel scan is done on them. In my example i can merge three runs at each step.
At the end of the first substep, i will merge 3 runs, so i will end up with 9 pages sorted. At the next step i can still merge three times, so i will have
Cost of the algorithm The general cost for sort merge is
The first term represents the number of pages access for the sorting phase. The second term represents the number of block access for the merging phase. During each merge pass, a number of disk blocks approximately equal to the original file pages
Join
Join is the most expensive operation because you increase the size of the table and that’s where you have many choices for the algorithms. Join are the weak link of relational systems and it’s one of the why people tend to avoid these. But we will see that in the right situation not only the join can become linear but also sub-linear. It depends on the algorithms and specific situation.
Say i have a student table and an exam table. By definition
Join and Cartesian Product
Join is a subset of cartesian product of two tuple.
Ok match each students with each student, so cartesian is all versus all. So it will be
Selectivity for Join operation
Joins have a selectivity, much like restriction. But selectivity of joins is equal to:
Where
For what concern the algorithm, let’s stick with definiton of joins. To know which algorithm would i use to check the join?
Nested Loop Join
The simpliest naive solution is the nested loop join. In SQL queries there are no nested loop, but on a lower level actually there are.
For each students
for each exam
if students.matricola == exam.matricola then join
end for
end for
It costs me
Block Nested Loop Join
So instead of do a cicle on tuples, i could do a for cicle on pages. Once i read i page, i get all the tuples stored in that page ofcourse. Say i have a buffer size of three pages. I scan parallely students and exams. So i do a full scan of exams table for each page of students table. This costs me:
which is much much lower than
The best choice is to check the lower value.
Bigger Buffer Size
We can do better quite easily, if we have more pages on the buffer. Say i have
The cost of join scales linearly with buffer size. The more memory you have the less operations you have to do to improve the join. If you have a big buffer, the second term will become a very low value.
Hash Join
To understand hash join thinks that you wants to store these two tables using an hash primary file structure. So how much will it costs me to store the students using an hash primary file?
(Aggiungi card su anki esempio professore matricola modulo tre per lezioni di laboratorio.)
The costs of using will be:
So it will be:
Special Case - Buffer Size bigger than File
Let’s consider a case where the Buffer Size is bigger than the number of pages required to store a file.
The more ram you have, the more efficient the join.
Counterintuitive Join Cost
If we follow the definion of Join, it’s a quadratic operation, but in practice the cost of joins becomes linear or sublinear.
Single Loop Join
If we have Index, instead of matching each students for each exam, we will just use the index instead of the entire exam. Ofcourse we should consider also the selectivity of the index.
- Disadvantages with indexes selectivity
Usually, a foreign key is a good candidate for building an index. Let’s consider this case: we have built an index on the matricola field of exams.
First i load all the students, then i just have to do an index search for all matching records that satisfies the condition
. It costs me: .
Lezione 10
Execution Plan
An execution plan for a relational algebra expression represented as a query tree includes information about the access methods available for each relation as well as the algorithms to be used in computing the relational operators represented in the tree.
By viewing the query execution plan one can observe whether the database itself thinks that design choices, such as materialized views and indexes, are likely to be.
Consider the following query in relational algebra:
The tree representation would be:
Aggregation
|
Restrict
|
JOIN
/ \
student exams
Simple optimization with empirical rule of reducing size of the intermediate table
We could do a simple optimization like explained in Query Optimizer The optimized query becomes:
Swapping parenthetis, instead of joining all the students we join just the italian students so you get a dramatic reduction of the intermediate table size.
From a tree point of view, here’s what happens:
AGGREGATION
|
JOIN
/ \
Restrict exams
|
student
We see here that we taked down the restriction.
Example naive execution plan
This is not an execution plan because algorithms and data structures are missing.
- Aggregation could be done using Sort Merge. , it costs me
- The Join could be initially done with a Block Nested Loop Join, and it would cost me
- Restriction is just
assuming there are 10 NDV in region.
Aggregation (sort merge) [2NP(1+log(2NP)
|
JOIN (BNLJ) (NP_S+(NP_E*NP_S)/(BS-1))
/ \
(NP/10)Restrict exams (NP_E)
|
student (NP_S)
Further improving performance in previous example
Here are some other idea we can apply from previous lessons.
- Sort Exams by Matricola
- Do a Single Loop Join instead of the BNLJ. To do this, build an index on the matricola field, so the costs would go down to
, or even if the index can be pre-loaded in the buffer.
Usually the index is a small number of pages, i pay
- Materialized Views: in this case, it would costs me 1 page and i don’t suffer much from outdated data because the average of a vote usually has small deviation.
This is from a theoritical point of view, but not these options are all available. Usually the optimizer is closed source. There are also some customization but depends on the dbms.
Query Execution Plan Hints
Hints are programmer directives to an SQL query that can change the query execution plan. For example in Oracle:
SELECT AVG(VOTE) /* Use Index ...As the name suggets, these are just hints nad the optimizer isn’t forced to follow your suggestion. How to trick the optimizer: For each field of the table the database keeps some statistics like: selectivity of a query, number of idfferent values, number of times an index is used and so on. These statistics are used by the optimzer to make a suboptimal execution plan, but they are stored in a table in a database table. You can overwrite these statistics and fool the optimizer.
In most software you can get an execution plan for you system. They also give you an estimate cost of the estimation.
Example of Execution Plan in Microsoft SQL
- 📖 Learn Microsoft
From Right to Left, bottom to top we see: - IX_PersonPhone_Phone_ is name of the index used. The index is “NonClustered” so it’s a dense index. The cost is displayed in percentage. In the case of this restriction the cost is only 2% because we exploit the index
- Hash match - Inner Join: this is a very quick inner join because the size of the intermediate table is small. Costs 1%.
- Right Outer Join: this is one of the most expensive operations: 13%. We need to Join tables from PersonPhone and CountryRegion.
- We have then another Hash Match with a Right Outer Join: Costs 0%, this is probably done exploiting linear or sublinear algorithms for join
- hash match right outer join Cost: 18%, this is the “critical point”, it’s the operation that costs the most. It’s the last join so it will consider a lot of tables, with a lot of fields because of the previous joins.
Usually, the graphical execution plan is not free, like in Oracle. Where with a non-free version you get an EXPLAIN command, that returns a table not as easy to read as the graphic
Resume of costs
- Restriction cost depends from the primary file structure, indexing and so on.
- Projection cost is almost always a full scan, unless when you have duplicate to remove. In that case you need the Sort Merge Algorithm
- Join costs depends on the algorithms used, in some particular cases the costs can be reduced to linear or sublinear scan.
- The remaining operations like grouping and set operations (union, intersection, minus) are implemented with sorting, so they require too the Sort Merge Algorithm
Serve un puntatore magari ad una nota con le operazioni principali in relational algebra.
Pipelined vs Materialized query
Execution of a query can happens in two ways:
- Pipelined
- Materialize
In pipelined queries, you execute all the operations in main memory and you get the results on the disk at the end. In materialized queries, you do one operation, then save the intermediate result on disk, and then you do the next operation, and so on.
Advantages and disadvantages
- 📖 Fundamentals of Database Systems 7th Edition Chapter 18.7
Exercises
Same with table two:
First question: how many block required for a B-index on City Fields? City Fields is on the other table, so let’s do an index for example on Volume.
Index on volume: B-Tree Index. Is volume a sorted field? No is not sorted. Because if it was sorted the index were sparse. But as it is not sorted, it is dense. So BTree Dense.
Selectivity: 1/50.000. So NDV=50.000
We always assume equidistribution and so the number of repreated for each different value is
We would have multiple pointers for the same value in the index. So you have to decide and we have to decide (one value multiple pointers) what technique would you use?
1 value corresponds to multiple pointers. How to manage this situation?
The preferable solution is the first one because we waste less memory if we do this way.
Now we have to compute the BFR of the index.
To comput the fan out we have to do all the computations.
This is a B Tree, the fan out is the same in the innter node and the leaves. THe structure of the nodes in the index is:
U is the level of emptiness of the page, the minimum is 0.5. B is the page size so we know is 4096. Replacing values here i have:
Remember to get the trimmed value because you can’t get half page. So this is basically a binary tree, each node has at most two childs.
Now i can answer the question.
The total size of the three is
Let’s see a query:
Index choice q1
SELECT DISTINCT CATEGORY FROM SoldProductsVolume NATURAL JOIN Stores WHERE euro>50000 AND City='Napoli';Frequency: 3000/day.
Euro has a selectivity of 1/500.000.
The selectivity of euro more than 50.000 is:
The second condition is City from Napoli. How many different cities i have? 30.000.
THe selectivity is:
Let’s look at q2 City=‘Rome’, so 1/30.000
At this point you can already answer to the first question. In theory everything is the same, two different restriction. You could build a index on euro, one on city or a composite index on euro and city. But in practice an index on euro is useless. A combined index is useless for the same reason. And if you build the index on City you can exploit the same index on both queries.
What is the most convenient index to build? an index on city Which are the access costs with and without each candidate index? Now we have to compute the costs of the query.
We first draw the tree:
Projection
|
Join
/ \
Select(euro) Select(City)
| |
T1 T2
But for the second , i will have 1/3 which is one page, so the entire table fit into the main memory so we can just do a linear scan.
Do variations with questa traccia. Change fields, change the query and try to solve it. We will start other topics. At the beginning of may we may have the mid-term. probabilmente tra il 14 e il 16.>)