Query Execution I

 

Let's table about query execution, but let's mostly talk about operators, query, etc. The operators are arranged in a tree and the data flows from the leaves of the tree up towards teh root. The output of the root node is the result of the query. 

SELECT R.id, S.cdate

FROM R JOIN S

ON R.id = S.id

WHERE S.value > 100

We'll talk about processing models, access methods, and expression evaluations, applying the "where" clause to certain tuples. We're putting everything together to be able to execute a query.

A processing model specifies how a database system is going to execute a query plan. There are 3 main approaches we can do, each with different tradeoffs and different performance implications. 

1. Iterator Model

2. Materialization Model

3. Vectorized/Batch Model 

Let's first discuss the iterator model, which is called the volcano model or the pipeline model. 

On each invocation, the operator returns either a single tuple or a null marker if there are no more tuples. The operator implements a loop that calls next on the children to retrieve the tuple. This is a pipeline or a process to perform an operation. The Next() function are for loops which are iterating over the output of the child operator. 

For every emit we're passing out a tuple as invokation of next. 

At the very beginning if we call next we go to the next value and iterate through. If I call next() again, I know how to pick up from where I have before. Now, we want to call next() on its child which is the Join operator, which has 2 phrases and operators. For ecery emit function we are passing out a single tuple for the invocation of next(). At child.Next() then we go to the next where we build the hash table, and then emit in right.next and then go to t in S and emit(t). These series of operators which can operate in order, is called a pipeline. 

We keep calling next and if I go down and traverse and produce an output I know where to pick up where I left before. Then there's a JOIN operator. I call Next() on the left child is that where I want to populate Hash table, which now invokes the next on its child operator (R), which has own for loop that emits a tuple. For every emit, it emits tuples to go up, and then process all the tuple until there is a null pointer. It's called the iterator model because it's just all cursors iterating through the tuples 1 by 1. After we finish on the left side, we go on the right side, and we emit tuples up one by one. Then we do the probe, and then we emit that to the parent. 

If a join/tuple matches then we can pass things all the away up the the parent which is produced as an output tuple. 

Some operators don't allow use to do pipelining all the way up, these are called pipeline breakers. I have to build a hash table and this is a pipeline breaker, since I can't continue up the tree if the entire hash table is built. Limit clauses are super easy to do so if I call next() 10 times to get 10 tuples I'm done and will no longer need to do anything else. 

The next approach is the materialization model, where each operator dumps all the tuple it needs coming out all at once. The DBMS pushes hints to avoid scanning too many tuples can send either materialized row or a single column. Each operator processes its input all at once and then emits it output all at once. The output can either be whole tuples of a single column. Each operator all the tuples come all out at once. We don't want to pack way more data more than actually needed. It's all the values for the single column for all tuples. 

Now we have this "return" value in the output buffer, or a list of all of the tuples. We get the operators invoked, then build hash table, then go down the right side, and percolate for the data that we need going up before going up and getting all of the tuples. Once spitting back the "buffer" for all of the tuples, I never go back and ask for more. 

Materialization is fantastic for OLTP workloads (Online Transaction Processing, concurrently), because lower execution and few function calls. It's not good for OLAP (Online analytical processing) queries with large intermediate results. This is where the vector tuples come into play. This is the vectorization level, which is similar to the iterator level, but operate on a vector of tuples rather than a single tuple, an d the batch of tuples depend on what the hardware looks like. It's like the iterator model, where each operator implements a Next function in this model. 

Each operator emits a batch of tuples instead of a single tuple. It's like the iterator model, but inside of the kernel functions we have the output buffer and check to see if the output buffer is larger than the size that we want to emit and if it is emit to the tuple and once we need everytrhing in the batch we shove it up and process. 

There's 2 approaches:

Approach 1: Top to bottom

- Start with root and "pull" data up from its children. Tuples are always passed with function calls. 

Approach #2: Bottom to Top

- Start with leaf nodes and push data to their parents and allow tighter controls of caches/registers in their pipelines. 

Sequential scanning is really just a bunch of for loops inside of the operators. An access method has 2 approaches, which are either reading the data from an index or reading it from a table. There are 3 basic approaches which are the sequential scan, the index scan, and the bitmap scan. 

For scan we go over each page, do whatever we want to do with the page, and them emit them up to the next operator when done. 

Sequential scan is the worst thing that a Database Management System can do to execute a query. Now ways to make scans go faster are zone maps, late materialization, and heap clustering. Zone maps give information on pages to allow us to figure whether to give access to them or not. For every single page on the table, we have some metadata derived from that page giving the information of the values inside of the page for a given attribute. It has precomputed aggregate of the values within the page. DBMS checks the zone map first and then decides whether it wants to access the page or not. Companies such as Oracle and Cloudera use these maps. However, you need to maintain zone maps to make sure everything is in sync, since I don't want to look at a zone map and say "I don't have a match", while in fact, I do.

Next optimization is Late Materialization. We can pass offsets or column ids to allow us to go get the actual data we want. Typically the operator output would be the entire tuple. My query plan in the pipeline, the first thing I need for the filter operator is the a column, pass from stuff from A column, so then afterwards, I don't need to pass along A. So instead, I'll just pass along offsets, then I can get the B column to do the join, and then doing average, then I go to disc to get C, then get the final result. 

Last thing is heap clustering, scanning around the leaf nodes, then going to fetch the data in sequential order.

Now how do we do index scan? The basic idea is we want to identify the index on the table that will allow us to find the data that we need. Which index to use depends on the attributes in the index, attributes the query references, the attribute value domains, predicate composition, and whether the index has unique or non-unique keys. 

Let's look through an example.

Say we have a query:

SELECT * FROM students

WHERE age < 30

AND dept = 'CS'

AND country = 'US'

The index used depends on what the values of the data will look like in the entry table. Going through age makes the index scan essentially useless. 

Index 1 is age and index 2 is scan. If there are 99 people under the age of 30 but only 2 people in the CS department, we need to specialize this thing based on this decision.

What happens if both indexes are a good idea? If the database system can recognize both can help a lot, I want to do probes on both of them, get the results, compute the sets of record ids using each matching index, combine these sets using query predicates, and retrieve the record and any remaining predicates.

How would we be able to derive an approximation of which index is better?

If there are multiple indexes that DBMS can use, we compute sets of record ids, combine these sets, and retrieve the records and applying any remaining predicates. All the major database systems builds a bitmap where every bit corresponds to a record (a bitmap) and combine them to do bit manipulations. 

The beauty of SQL is you don't actually have to know how things work completely. 

The set intersection can be done with bitmaps, hash tables, or Bloom Filters. 

The last thing for access methods is retrieving tuples in ther order that appear in an unclustered index is inefficient. The DBMS can first figure out all the tuples that it needs and then sort them based on the Page ID. 

Retrieving tuples in the order hat appear in unclustered index is inefficient. Before doing lookups, I scan along get record ids, and sort them with their page ids, and then process all the tuples inside the page before I move on to the next one. This is the beauty of the relational page. If you care about order in a specific page, you're going to have to write a specific ORDER-BY clause. Sometimes if pages are resorted, you might get a different result for the same query, and that's okay.

 How do I maintain a clustered index? Either reshuffle everything or store things in MySQL DB or use the data structure. This is why most databases that are cluster organized are not the default. In ORDER BY, I have to see all the tuples to see what the global sort order is. 

ORDER BY is a pipeline breaker, I don't know the complete sort order of the records until I see all of the records. A pipeline breaker says you cannot proceed up in the query plan until you get all the tuples you need. For example, I cannot select top 10 tuples until I have everything ordered properly. 

We know all these properties ahead of time because we know exactly what the query plan is and does in this case. 

The last thing to talk about is : how do we evaluate predicates? We will represent the WHERE clauses as an expression tree and all the nodes of the tree represent different expression types including comparisons (=, <, >, !=), Conjunction (AND), Disjunction (OR), Arithmetic Operators (+-*/%), Constant values, and tuple attribute references. 

Prepared statements is a way to fill in a query template, with a placeholder that helps values that gets substituted in runtime. Let's say I have a big application, a desktop, phone, supercomputer. If we are trying to execute more complex operations, we have a whole thing called server-side program logic on how we're going to execute a query. There's tradeoffs in whether we put something in database code or application code. 

We need to have some contexual information on what's going on in the query to invoke this expression. We need to know current tuple, what our input parameters are for a query, and then need some information about the schema of the tuple we're processing. 

We start at the root (=), call evaluate, and go down to each of the leaf notes to move value up. We retrieve S value from current tuple which is 1,000. But now DFS and Parameter at Offset(0) is 999 and constant value of 1 produces 1 and I evaluate 999 + 1 (1000) and shove it up for the equality predicate, and in this way, we will successfully match specific tuples up with its predicates. 

What I'm describing is what the database system will use to implement expressions and it's going to be slow. The high-end systems don't do this. But instead we use Just-In-Time (JIT) compilation. Assume we had a crappy system where we traverse it. What we instead want to do if compiling exactly the predicate that you want to evaluate for a given tuple. Now I can write constant values in instructions. That's way faster than traversing a tree to look for expression times. Try to evaluate the expression directly, try to "strip down" to be exactly what the predicate wants to do. This is what the high end systems, such as postgres-12, does. 

Not only we get the predicate to instructions, we will compile an entire query plan as a set of instructions to be able to do things on the fly. The main takeaway is that the same query plan can be executed multiple ways, depending on things, and the Iterative Top-Down approach is the most common. In most scenarios we want to use an index scan over sequential scan. Expression trees are flexible but slow. Review now, because now we're going to teach how to build an entire system. Next article on databases will be on Parallel Query Execution.