We've spent the first couple of lectures starting at the bottom of the system architecture and working our way up. We've discussed data storage, bringing the pages into memory, and having policy when it's time to evict something. We're going to talk about 2 data structures, the Hash tables and the Trees.
Data structures are used all throughout the database management system. The next thing we can use it for is the core data storage for the database itself, we can organize it to be a hashTable, or Tree Data structure, and have the values of the database to just be Tuples. There's internal meta-data core data storage, temporary data strucutre, and table indexes.
Data Organization is how we layout data structure in memory and the information, and how to enable multiple threads to access data structure at the same time without causing problems is concurrency. Today we think of the physical integrity of the data structure. We need to be able to map arbitrary keys to arbitrary values.
A hash table implements an unordered associative array that maps keys to values. It uses a hash function to compute an offset into the array from which the desired value can be found. Money cares about constant values. Hash functions can be used but some hash functions can be twice and 3x as fast as other functions so this is extremely important.
There are several hash tables you can build. We're not gonna discuss how we decide what index to pick, etc, or you pay a lot of money for human database administrators to do this for you (they get paid well!). The simplest hash table is an array where every single offset correspond to a given element, mod the key by the number of elements to find the offset in the array. In practice, we'll need to store pointers to where a particular hash table key is found.
We have to assume that we know exactly the amount of elements ahead of time, and we have a perfect hash function that if k1 != k2 then hash(k1) != hash(k2) assuming that there's no collision. How do we make a hash table such that we won't have to make any of these assumptions?
Hash functions take key and maps it to an integer value in a smaller domain. We need to trade off between being fast and collision and handle key collisions after hashing. Static hashing is approximation of the size of the keystore, and dynamic hashing. Combination of Hash Function and Hashing Scheme is Hash table.
A hash function is taking a key and spitting back a 32-64 bit integer. There can be SHA=256 or ND5. SHA-256 is reversable and ND5 is a one-way hash. We don't want to use a cryptographic hash for tables, we want something that is fast and has a low collision rate.
At the smallest level CRC does the fastest. Here's the evaluation of certain Hash Functions:
After 64 bytes city hash and farm hash switch to a different algorithms.
There are several hashing schemes, Linear Probing Hashing, RobinHood Hashing, and Cuckoo Hashing. In some cases, you can guess what things are with query processing to do joins in the Hash Table. If hash table gets too full, we have an infinite loop, meaning that we have to increase the size of the hash table/double and taking all the keys in the first hash table and copy them into the second one.
You can have a giant table of slots, and need to use that function to jump to a hashset. Linear probe hashing resolves collisions by linearly searching for the next free slot in the table, to determine whether an element is present and store the key in an index. So, what we do is jump down to the next hash position.
This actually is a circular buffer, and loops back araound as well. Let's say we delete. There's 2 ways to handle delete, add a tombstone, to consider the slot occupied (there's no data here, but not an empty slot, let me jump down to the next one. The problem with this is you need to clean up afterwards. Alternatively, we can realize an empty slot and just move everybody up one then this way we can land exactly where you want to go. We might have to move earlier characters or hashes though so it's just hard to look into the right place. Most people just utilize tombstones.It's probably the easiest way to account for deletes. We might have to move b to a non contiguous part as follows:
For non-unique key is to store values in separate storage areas, or we store duplicate entries together in the hash table.
Robinhood hashing was proposed in 1985 that no one really paid attention to and showed up on hacker news and people are now trying to. Robinhood is based on the folklore tale, and we're going to have "poor keys" steal slots from "rich keys." Poor vs rich is the number of positions you should have been away from when you first hashed into the hash table. Each key tracks the number of positions they are from the optimal position on the table. On an insert, a key takes the slot of another key if the first key is further away from the optimal position than the second key.
Let's say A and B are in optimal positions, and now we want to place the C hash value. Unfortunately, C is colliding with A and since the distance between positions is 0, then what happens is we put C after A and increment the count to 1 (nonideal but whatever).
Now C has 1 and if D = 0, we make D go down the corresponding slot.
Now if E we want to insert, in A, E's counter is 2 so 2 is considered more poor than D, then it steals the slot than D because it is "poorer" than D. Now we insert D down and update its counter to be 2.
Overall, now we're more balanced. We set priority to the "poorer" people. This is why it is called "RobinHood.".
Another approach is called cuckoo hashing, having multiple hash tables and deciding which hash table to insert our key. Cuckoo hashing is named after a cuckoo clock and cuckoo bird steals itself from one nest to another. Lookups and deletions are O(1) because only one location per hash table is checked. See a table.
On insert, check every table and pick anyone that has a free slot. If no table has a free slot, evict the element from one of them and rehash it to find a new location. Most people use 2 hash tables. We have same hash function with different keys, so it produces a new value.
We hash and we mainly want to go to the slot that is empty.
However, some times, you need to figure out what process you want to kill. We can just flip a coin and insert randomly and then hash B with the first hash function and insert it. If there's conflict we rehash until all of the conflict is gone.
The problem with this is that this can have cyclic behaviour and you can get stuck in an infinite loop. This is where you resize the hash table.
All of the hash tables were static hash tables, meaning I need to know approximately the size of the number of keys I want to store ahead of time so I allocate it large enough to minimize collisions and don't have infinite loops. Otherwise, we'll have to rebuild the table to shrink in size, etc.
Can dynamic hash tables resize itself on demand without having to rebuild the entire thing?
Chained hashing is a hash table with a linked list of buckets with values that are part of the same key. We can maintain a linked list of buckets for each slot in the hash table and resolve collisions by placing all elements within the same hash key to the same bucket. Insertions and deletions are generalizations of lookups.
We can chain hashing approach where we split buckets instead of letting the linked list grow forever, so multiple slot locations can point to the same bucket chain and reshuffling bucket entries on split and increase the number of bits to examine.
Here 00 and 01 map to the same bucket because the first bit is the same but 10 and 11. The global counter is how many bits you need to look in and the local counter is to understand how did you get to the location where you're at. Here's an example of the hash:
Let's insert C if first 2 bits are 10 but now we don't have free entries in the bucket. So what do we do? We split the bucket and examine 3 for the global counter. This operation is cheap because this is just an array of pointers. We subsequently restructure and remap.
After we reach the page we just do linear scanning. This is called extendible hashing. Linear scan is super cheap instead of reading it from disk.
We also have linear hashing. One problem with extendible hashing is we double the size of the slot array. When resizing, I have to take a latch on it before computing anything else. We can localize to just be whatever the bucket that overflowed. We maintain something called a split pointer, that keeps track of the next bucket to split, and then incrementally increase the size of the slot array. For linear hashing we can do hash1(key) = key % n.
What happens if there are no more free slots?
How do we solve this issue? We insert into the new table!
Buckets mean that if you dont split to overflow things would balance out. When the pointer reaches the last slot, delete the first hash function and move back to the beginning. We need to hash past the demarcation line. I could leave the page alone and empty it but if we want to reclaim. memory, I bloe away the bucket, blow away the pointer, and move the split pointer back by 1, and then reclaim the memory. Hash function should be deterministic, so the same key should always produce the same hash. When you decide to do an overflow, maybe you don't want to do exactly at the moment. People that spent a lot of tie making insert go fast, deletes are harder because sometimes you it might be better to rebuild the entire index.
When you call createindex, you mostly get B+ tree, which is the greatest data structure of all time! Every data system follow the B+ tree implementation. They'll differ on how to store and do things and do storages.
So in summary:
A database managment system uses various data structures for many different parts of the system internals. There's internal meta-data which keeps track of information about the database and system state.
Core data storage can be used as the bae storage for tuples in the database. DBMS can build data structures on the fly and table indexes are auxillary data strucutres making it easier to find specific tuples. We have to figure out:
1. How to organize data
2. How to enable multiple threads to access data.
A hash table implements an array data type that maps particular keys to values. It has O(1) operation complexity and O(n) storage complexity. A hash function helps to match a larger key into a smaller domain. A hashing scheme helps handle the key collisions after hashing. We need to consider the tradeoffs between reducing collisions and increasing the space complexity.
Hash Functions take a key as an input and returns an integer representation of that key. DBMS does not want to use cryptography hash function.
Static hashing is the one where the size of the hash table is fixed. Means if DBMS runs out of storage space then it has to rebuild it from scratch with a larger table, and we want to avoid collisions as much as possible.
Linear probe hashing linearly searches for the next free slot in the table.
Robin Hood Hashing tries to reduce the maximum distance of each key from optimal position and steals slots from "rich" keys to give them to "poor" keys. Cuckoo hashing has tables with different hash algorithms, and check every element and pick any of them that have a free slot. If non has free slot evict the element and keep hashing to find a new location. These are STATIC HASHING SCHEMES.
Now let's talk about some new Hashing strategies. Chained hashing resolves colission by placing elements with the same hash key into the same bucket. This hash table can grow infinitely. Then, we got extendible hashing, splitting buckets instead of letting chains grow forever. We move the bucket entries on split and increase the number of bits to find entries inside of the hash table. If local depth is lower than the global depth the new bucket is added to the existing array. Else DBMS doubles the size of the slot array to accomodate the new bucket and increments the global depth counter. Then we got linear hashing, maintaining a split pointer that contains the next bucket to split. No matter whether this pointer is pointing to the pointer it always splits. Split pointer by adding new entry and create new hash function when bucket overflows, but if function maps to slot applied by previous pointer, apply new hash fucntion. When pointer reaches last slot, deleted the original hash fucntion and replace it with the new hash function. The database always splits and maintains a split pointer in that perspective. These are DYNAMIC HASHING TECHNIQUES.
Comments
Post a Comment