Query Planning and Optimization Part II

This is part 2 on the lecture of Query Optimization. The more complicated part is using a cost model to evaluate the amount of work we have to do for a particular query plan before we even actually run it. Use a model to estimate cost of executing a plan and evaluate multiple equivalent plans for query and pick the one with the lowest cost. It's basically a greedy Algorithm. 

This article's agenda is Plan Cost Estimation, Plan Enumeration, and Nested Sub-Queries because this is a NP-hard problem. Our cost model is a way to approximate how long it will take to execute a query. We want to use an algorithm for less memory. These are all a proxy to determine how much data we will pass from one operator to the next. The way to get the most accurate information is to actually estimate the query plan, so we need a way to approximate this, this is what the cost model is going to do. The thing we use for this is the internal statistics catalog. This will help collect the information in regards to how the table will look like. Some systems can run in CRON jobs, and some other systems do a piggy back, or have triggers, etc. 

Manual Invocations are ANALYZE, ANALYZE TABLE, etc. The database Maintains the following: 
NR, which is number of Tuples in R and V(A, R) which are the number of distinct values for attribute A. The selection cardinality SC(A,R) is the average number of records with a value for attribute A given NR/V(A,R); however, things are not that simple, since we can't assume that we have uniform data. This is just an assumption, since the real world doesn't work this way.

Say we have a simple table, and if I have a lookup where id = 123 the cardinality = 1 when the predicate is unique. However, once I get range conjunctions, I have to be able to combine these in different ways. 

SELECT * FROM people WHERE val > 1000

SELECT * FROM people WHERE AGE = 30 AND STATUS = 'Lit' 

The selectivity of a single predicate, which is a function for a given a predicate is the fraction of the tuples that qualify. Assume for people column we have 5 unique columns 0-4. 

sel(A = constant) = SC(P) / NR

SC is the select count.

sel(A >= a) / (Amax - Amin) = (4 - 2) / (4 - 2) = 1/2 given everyone has occurence of 1 of each age from 0, 1, 2, 3, 4. 

sel(not P) = 1 - sel(P)

sel(age != 2) = 1 - (1/5) = 4/5 

The selection cardinality for P is 1 so the negation is the boundaries beside that. It's time to start combining together these predicates in more complex ways. 

This is a good representation of conjunction vs disjunction. 

CONJUNCTION: 

sel(P1 ^ P2) = sel(P1) ^ sel(P2)

sel(age = 2 ^ name LIKE 'A%')

DISJUNCTION: 

sel(P1 V P2) = sel(P1) + sel(P2) - sel(P1 ^ P2) 

Again assuming that selectivities are independent. 

We multiply 2 clauses together to result in the combined cardinality.

Let's say we have a database with 2 entries, the make and the model. If with uniformity, then we consider a database of automobiles with 100 models and 10 makes, and have the query (make = "Honda" AND model = "Accord") and with independence and uniformity, the selectivity is 0.001. But since honda ONLY makes accords the selectivity is 1/100 which is 0.1. 

MySQL and PostGres can't do this. Our formulas are nice, but we can assume that data is uniformly distributed. 

However, there's a lot of variable in terms of a histogram, like follows: 

We can get histograms into buckets, so now they just have the aggregate values. 

Now, the way to get an estimate is looking to see what bucket the sought out value is and then we estimate the range based on the occurance and dividing the count by bucket size. 

Last thing we do is to use quantiles. We try to split the buckets as evenly as possible to have more accurate estimations on what is in the buckets. 

When I am running a transaction, I want to minimize the amount of work I want to do because I am putting locks on tuples.

Another alternative instead of using these additional data structure is maintaining a sample of the table and deriving our subsystems from the sample. 

Modern DBMSs also collect samples from tables to estimate selectivities. We update samples when the underlying table changes significantly. 

 We need a way to figure out how to shed work and cut off query plan in order to make this problem more tractable. 

For single relation plan, the hardest problem we have to deal with is picking our access method. We pick the best access method, and then do the predicate evaluation of ordering. Simple heuristics are often good enough for this and Online Transaction Processing are especially easy. 

Sargable is search argument able and this means that it's an index that would have the best selectivity, becuase that will lead us to the result really quickly. 

Things get harder for joins, since the number of alternative plans grow as the nubmer of joins increases, so the fundamental decision is that only left-deep join trees are considered and modern DBMSs do not make this consideration anymore. 

The first thing we're going to do is to enumerate all the different orderings for multi-relation query planning. For each of those, we can enumerate all the join operations, then I can enumerate all the possible query plans I can have. 

We can use a technique called dynamic programming to make things more tractable and break things down to smaller/more discrete problems. 

We can enumerate at the logical level all different orderings of the tables we can possible join. We solve the smaller problems first, and at the very end we will combine everything together. 

For each node, we're just going to pick whatever path has the lowest cost. 

Optimal cost example: 

Hopefully if you understand things, then you can see that you can apply more sophisticated setups.

First, enumerate all the possible Joiner rings, ore relation orderings. Prune the plans with enumerate join algorithm choices. 

Then we enumerate access method choices, and we keep fanning out having more and more options, and tyhen we use dynamic programming to figure out what the cheapest path is. 

So, we enumerate relation orderings, enumerate join algorithm choices, and enumerate access method choices. X is cross product, and does not need any condition to join. the JOIN element does. 

Also, for each join, I can also do an S-Loop Join or a Hash Join. 

Then, we enumerate access method choices, in which we can do a sequential scan or index scan. 

Finally, we use the dynamic programming technique to figure out what the cheapest path is. 

PostGres has the Genetic Optimizer as well (Genetic Query Optimizer) which means if you have a query less than 12 tables, it uses the system R approach, else it uses the genetic algorithm since it can deal with a larger searchspace. 

At a high level, this works as your standard genetic search algorithm.

The first generation, I just enumerate the query plan, and for each of these I compete the cost. Throw away the one with the lowest cost, and now I do random flicks of the "genes" or the components of the query plan to do new query plans. Find the one with the lowest cost, throw away the highest cost, random mixup, and keep generating in this manner. 

You're not seeing exactly what's the best, you're walking in a random moon space and you're hoping that you are landing on something reasonable. For a Walmart table, you don't want to store everything so if we do I have a join "Find me the best item in the state of Hawaii where this item is in the clothing category...". For query optimizers, people always claim the number of joins that they can support. 

Let's finish up with the nested sub-queries. It's not like a join because it's a sub query. We gotta be smart with how we are going to evaluate it in terms of every single tuple in the outer query. We can also rewrite things for more efficiency.  

Nested sub-Queries: Rewrite

SELECT name FROM sailors AS S 

    WHERE EXISTS (

        SELECT * FROM reserves AS R

            WHERE S.sid = R.sid 

                AND R.day = '2018-10-15'

)

SELECT name

    FROM sailors AS S, reserves AS R 

WHERE S.sid = R.sid 

    AND R.day = '2018-10-2015' 

For decomposition, for each sailor with the highest rating, find the sailor id with the earliest date. 

SELECT S.sid, MIN(R.day) 

    FROM sailors S, reserves R, boats B

    WHERE S.sid = R.sid 

        AND R.bid = B.bid

        AND B.color = 'red' 

        AND S.rating = (SELECT MAX(S2.rating) FROM sailors S2) 

    GROUP BY S.sid

    HAVING COUNT(*) > 1

The first approach is to take the nested block and substitue values below (SELECT MAX(rating) FROM sailors)), in this case we could rewrite it in order to fill out the values that we actually need.

This is what we're going to talk about for query optimization for the rest of the semester.