Sorting and Aggregations
Where we're at is that we know how to store things on disks, in pages, onto memory, and then we talk about how to access them (indexes or sequential scans). Now, we want to execute queries, SQL queries, generate query plans from them, and then see how we are going to execute them.
The operators are arranged in a tree, and data flows from the leaves of the tree up towards the root. The output of the root node is the result of the query. We are scanning on the leaf nodes and moving tuples closer towards the operator to do whatever it wants to do. We feed A to join operator and scanning B will feed into join operator, and producing output that would get to the projection operator. This is a high level of what I want to do, like a direct translation of the relational algebra. Here's the sample query and the query plan:
SELECT A.id, B.value
FROM A, B
WHERE A.id = B.id
AND B.value > 100
We cannot assume that a disk-oriented DBMS fits entirely in memory, and we need to use the buffer pool to implement algorithms to spill the disk.
Data flows from the leaves of the tree up towards the root, and the output of the root node is a result of the query. We are going to use buffer pool to implement algorithms needed to spill the disk and maximize the amount of sequential access.
It's obvious why we need to sort and the tuples in the relationships are inherently unsorted.
Tuples in a table have no specific order, but queries want to retrieve tuples in a specific order. DISTINCT supports duplicate elimination, and GROUP BY supports aggregation.
Bulk loading sorted tuples in a B+ tree will most likely be faster. If data fits in memeory, then we can use a standard sorting algorithm called quick sort. In the worst case scenario, we're having 1 I/O calls per change to the dataset. We want to make design decisions that will maximize the amount of sequential I/O to help speed. We can use quick sort if fits in memeory, otherwise we need to use technique aware of the cost of writing out data to the disk.
We have external merge sort as a method. This is a divide-and-conquer sorting algorithm that splits the data set into separate runs then sorts them individually. Phase 1 is sorting, which sort blocks of data that fit in main memory then write back the sorted blocks to a file on disk. Phase 2 is merging, which combine sorted sub-files into a single larger file.
A 2-way merge sort description is below. The data set is broken into N pages, 2 in this circumstance. The DBMS has a finite number of B buffer pages to hold the input and the output data. Here are the passes and stuff.
Pass 0 read every B pages of the table into memory. It sorts pages into runs and write back to the disk. Those were the 2 steps, denoted below.
The other passes #1, 2, 3 recursively merges pairs of runs into runs twice as long and use 3 buffer pages, 2 for input pages, and 1 for output. I'm done once I reach the end.
Number of passes is 1 + ceil(log2(n)) while the total IO cost is 2N x (Number of passes). For every pass, I'm reading every record, every key I'm trying to sort exactly once.
Even with more buffer space availably it does not effectively utilize them...
In double buffering optimization, we prefetch the next run in the background and store it in a second buffer while the system is processing the current run, reducing the wait time for I/O requests every time by continuously utilizing the disk. This is using a bunch of background tasks.
Let's evaluate the complexities of the general sort. We have B - 1 output buffers, since we can virtually only write to one output buffer at a time.
That's external merge sort. The exact details with how you actually implement this will vary from system to system.
Now we can learn about a new concept, only that this one uses B+ trees for sorting. The sort and join algorithms are always the most expensive things to do. B+ trees maintain a sort order for the keys in a data structure.
We can use this to accelerate sorting by retrieving tuples in desired sort order by simply traversing the leaf pages of the tree. However, it only works if we have a clustered B+ tree.
A clustered index means that the physical location of the tuples on our pages will match the sort order defined in the index. For example, with an index on key foo, among the pages, the tuples will be sorted in pages based on that order or 'foo'. Doing a sort doesn't require an external merge sort. Traverse through left most page, then retrieve all tuples from the leaf pages. This is better than external sorting since there is not computational cost, and all the disk access is sequential.
However, this is the worst possible thing to use to attempt to generate a sort order for an unclustered B+ tree. We chase each pointer to page that contains the data. This is almost always a bad idea, because the page isn't in memory since I need to go to disk get the page, and we don't have any sequential order and thus cannot store consecutive or predictable options in the cache.
For sorting, we filter all the tuples WHERE and then remove columns by cid and finally we finish by sorting. Finally, we eliminate duplicates.
So Filter, Remove Columns, Sort, and Eliminate Duplicates.
Query select
SELECT DISTINCT cid
FROM enrolled
WHERE grade IN ('B', 'C')
ORDER BY cid
The whole goal of all of this is to remove as much useless stuff as possible. If sorted, I can do one pass initially, and then eliminate the duplicates afterwards.
Hashing is a better alternative in this scenario, which only need to remove duplicates. Hashing also eliminates the need for ordering. Hashing can also be computationally cheaper than sorting.
So, we're going to populate an ephemeral hash table and when we do a lookup, then for each record, check if there is already an entry in the hash table. See if distinct, then discard duplicate. However, for the GROUP BY, we have to perform an aggregate computation. We need to be smarted other than simply spilling all the data to the disk.
The external hashing aggregate has 2 steps. The first step is partition which divides tuples into buckets on the hash key. The second part is rehashing, where we can build an in-memory hash table for each partition and compute the aggregation.
The first phase is using the first hash function (any hash function) to split things up. Because the hash function is deterministic, that means that tuples with the same key won't land in the same partition. Partitions can be "spilled" to disk via output buffers in order to start filling out the next page.
I'm going to hash this course id for every single tuple, and this means if we want to do elimination, I know that the tuples that have the same key are now in the same partition. We filter, remove columns, then run it through our hash function and then write it out to all the partition pages.
Here is the diagram, courtesy of Carnegie Melon.
SELECT DISTINCT ci
FROM enrolled
WHERE grade IN ('B', 'C')
At this phase, all I'm doing is partitioning, and it's like I'm blindly putting things to the pages and I'm writing them out.
Comments
Post a Comment