Query Planning and Optimization

 Today we're going to talk about query optimization and query planning. Given that SQL is declarative the query would indicate what answer that they want us to compute and it's not telling us how we're actually supposed to compute this (hash join vs nested loop join, etc.) It's up for us now inside of the database system to take that SQL query and figure out the most efficient way to execute it. 

There can be a big difference in performance-based on what plan is used. Remember, SQL is declarative, user tells DBMS what answer they want not how to get the answer. The idea of the query optimizer goes back to the 1970s, when the first paper on the relational model was written there were 2 groups of people who tried to implement it saying that "This is the right way to actually build software/relational database management systems. The group in Berkeley was called Ingress. 

Back then people argued that "There's no way a database system can take a language and generate a query/write a query by hand. Everyone writes in high-level language and compilers translate this language to Assembly language. Such is the case of IBM's system R. 

We can use static rules. The idea here is to look at our query plan and a portion of the query matches the pattern, then we fire a rule that does a transformation of a query plan to make it more optimal. The important thing to understand about these rules is that we may need to look at the database system catalog to see what such a database looks like and understand what do underlying tables actually look like, but we never have to actually look at the data itself. 

The alternative is a cost-based search instead of not looking at the data, this one we have to look at the data in some way. We're going to use a cost model to approximate the execution cost of many different plans. The cost model of estimation is super hard and the way we enumerate the plans is also true. So it's a Evaluate multiple plans and pick the one with the lowest cost. 

As an overview, we have an application and send a request to the SQL query, called the SQL rewriter, having transformation rules that allow us to rewrite the SQL in certain ways. The Parser converts the SQL into a syntax string which then subsequently passes to a Binder. Binder converts the named objects to some type of internal identifier. The binder will then emit a logical plan (which says at a high level what the query wants to do). It doesn't say how we're actually going to do that, which is the physical plan passed onto the Tree Rewriter (which is more common than the SQL environment. To the Tree Rewriter we go to the catalog to see what those attributes look like. We finally pass the logical plan, schema info, and cost model all to the optimizer. The optimizer then passes a physical plan, what we actually execute. 

Parser-binder-optimizer is the standard pipeline. 

The tree writer feeds into the Query Optimizer which is a combination of schema information as well as the estimates that this cost model provides us. In the logical plan, the optimizer generates a mapping of logical algebra expressions to the optimal equivalent physical algebra expression. Physical operators define a specific execution strategy using an access path, depending on the physical format of the data that they promise and not always a 1:1 mapping from the logical area to the physical area. 

Query Optimization is the hardest part about database systems and it is extremely hard. IBM invented this stuff in the 1970s. If you are good at this you're going to pay a ton of money. People are looking at employing Machine Learning to improve the accuracy and efficacy of optimizers. 

Relational Algebra Equivalences are the core element that will allow us to those estimations. The core underlying concept that we're going to take advantage of when doing query optimization is that we understand relational algebra and we can permute these relational algebra equations and still produce the same result. 2 relational algebra expression are equivalent if they generate the same set of tuples, and DBMS can identify better query plans without a cost model, called query rewriting. 

We want to reduce the amount of work we have to do in the JOIN operator, so we'll just do the filter early. This is the general idea of what we're trying to do here. 

Here's the query:

SELECT s.name, e.cid

    FROM student AS s, enrolled AS e

WHERE s.sid = e.sid

    AND e.grade = 'A'

Some things are expensive to compute, but there's things called user-defined functions, and I can have the expression invoke a function that can be any arbitrary code, does some kind of computation, then subsequently comes back. 

So let's go through these operators and see what kind of optimizations to apply for the relational operators for the plan. For example, we can simplify a complex predicate. 

(X = Y AND Y = 3) -> (X = 3 AND Y = 3)

Let's say that we want to find a student older than 99 years. This is virtually improbable so in this case we will apply the age predicate first, determining based on the order of all of the predicates. So we'll apply the most selective filter first. 

We want to minimize the amount of data we have to copy going from one layer to the next. 

I'm going to show you a bunch of examples of how different database systems can rewrite certain query plans. The first thing we need to rewrite is stupid predicates or unnecessary predicates. For example this statement:

SELECT * FROM A WHERE 1 = 0; 

It can skip this entirely to just produce an empty result right away. 

This just selects everything from A: 

SELECT * FROM A; 

We also eliminate this: 

SELECT A1.* 

    FROM A AS 1 JOIN A AS A2

        ON A1.id = A2.id.

This just says join A on A, which is nonsense basically. 

SELECTING COUNT: 

SELECT count(*) FROM actor; 

How to explain Select: 

EXPLAIN QUERY SELECT * FROM actor WHERE 1 = 0 \G

Oracle doesn't support boolean, so we write NULL IS NULL to confirm and evaluate the expression as true. 

However, EXPLAIN QUERY SELECT * FROM actor WHERE 1 = 0 \G represents machine code. 

The relational Algebra Equivalences for joins are commutative and associative. 

R ⨝ S = S ⨝ R

(R ⨝ S) ⨝ T = R ⨝ (S ⨝ T)

The number of different ways we can do a join when we have n tables to join is 4^n. You know it's a large number when it has a name. The cost model estimates how much work we have to do in system in CPU, Disk, Memory, and Network, and it is too expensive to run every possible plan to determine this information. A cost model will allow us to approximate how many tuples will be read/written.

In Mongo DB it is primitive: Fire up all the queries pick the fastest and cache this and use this method every time.  

We can maintain internal statistics about what our tables look like and we maintain metadata and what the tables look like. How we actually maintain this information varies between different systems. We call ANALYZE function call the data, and then look up what the distribution looks like.