CMU Database Group · 1:23:43 · https://www.youtube.com/watch?v=VkP_yLM5KBU
1. <Untitled Chapter 1>
0:05 official members bounce bust off the Chrome realize it's real hell what we call Home official members bounce bust off the Chrome realize it's real hell where we from the ins side one I Vision fat licks and M Clips the Chrome will make the average imitator do back flips you like a [Music]
0:27 pistol all right uh quickly for everyone again in in the class the the things on that's on the docket for everyone here uh homework two homework two is going to be due uh this coming up Sunday on the 22nd and then project one will we do a week after on the following Sunday on on the 29th
0:48 and then as I post on Piaza we'll have a recitation for project one tomorrow night at 6 p.m. that'll be over Zoom but we're going to record it and post it on on Piaza afterwards and as I said on Piaza I encourage you to at least start looking at project one that way when you show up to the recitation you can ask questions like that are more meaningful because you've looked at the code and you're asking things that you don't understand rather than like you know what what's a header file right stupid things like that okay any questions about homework 2 or project
1:21 one uh I know that someone's ranking very higher in the leaderboard congrats to that person and again you get extra credit if you rank higher than everyone else and there's I think up to the top 10 we'll give extra credit
1:31 okay uh additional things that are optional that you can attend if you can't get enough can't get enough of databases so starting next Monday on the 23rd uh we have somebody from influx B one of the the the the project committers for uh Apache data Fusion is going to give an overview of of of that sort of framework that that library that you can use to build systems um and then the following we actually have the inventor of data Fusion give a talk but he's now at Apple uh on a Excel that they built for spark called Data Fusion Comet that uses obviously data Fusion it replaces the the Java runtime basically the execution engine in Java or sorry execution engine in spark that's written in Java with a with data Fusion which is written in Rust and it's optimized uh
2:16 better optimizing the Java stuff and then uh again so this is all in two weeks and then on Tuesday October 1st the database group here we'll have be having a a weekly meeting on Tuesday at 12: PM in Gate 6501 and we're having somebody from Oracle uh I think they're calling in over Zoom to give a talk uh about about some of the stuff they've been working on
2:38 okay so there's big news this week in databases I if anybody caught it guess what it is the founder uh of Oracle Larry Elson is now the the second richest person in the world now he actually checked right before class he went back down he's now third right but but there was a brief moment he he was second cuz the oracle stock Surge and and he he outranked Jeff Bezos again Jeff Bezos really should be first but he got divorced and he gave half money back you know to Mackenzie
3:08 right but whatever Larry also has he's been divorced four times but actually his second wife sold her because he it was the first year or second year he started Oracle back in the 70s she sold her uh her stock for Oracle back to Larry Elson for
3:24 $500 right so so I'm gonna miss on that one anyway uh again he's the he's the third richest person in the world all paid for by databases he owns a Hawaiian island and like a a good one right A big one Lai uh it's all pay for by datab bases and that's why you guys are here okay again so these are all optional uh if you want to go beyond the course okay
3:47 so to recap what we've talked about so far in in the in the weeks in this in the early beginning of the semester right again we started at the bottom we talked about the disc management then we went above that last class we talked about the buffer manager how how we're going to keep track of the pages we're bringing from dis into memory and then now it's time to start doing something with those pages right we know how they're going to be organized they know how we know how to put data in them now it's actually time to build the execution engine to interpret what those those pages are are storing and run queries and store data and do do all the things you expect a database system to do for us so for the the next couple weeks we're going to focus on what what we call it access methods uh and these are going to be the internal components
4:27 of the system that's going to allow us to as it sounds access data or access the the the pages we want that we're storing and derive meaning from them and we're going to first first talk about the data structures we're going to use that can be represented by the dis pages that we're bringing back uh bringing you know from dis into memory and so today's class we're going to be talking about hash tables which will be unordered data structures and these going to be used all throughout the system for various things and then on Monday's class next week we'll talk about trees uh in particular the B+ tree right these are going to be data structures that that can preserve The Ordering of of values or keys we're going to want that for obvious reasons because we want to know where things are sorted how to do ranking and other stuff okay so again we're we're in the middle part of the system now and now we're going to start building more complex things on the basic Primitives that we we've constructed so far in the previous
5:18 lectures so we'll first talk about the background what a hash table is and why it matters uh then we'll briefly talk about hash functions what they are we're not a uh it's obviously not a crypto class it's is not a lowlevel algorithms class we don't really care what hash function we want to use uh we'll just pick whatever they consider the best one and I'll show you how to figure that out and then we'll talk about two types of hash tables static hashing schemes where you assume the or the the data structure
5:44 has a fixed number of elements that are key key value pairs that it can store and then we'll talk about a dynamic hashing scheme that allows a be hash table that can grow uh most time you're going to grow up not down like instead of shrinking but we'll talk about how to do shrinking one of them as well the idea is incrementally grow your your your system over time or sorry your data structure over time to accommodate more
6:04 data and then we have at the end of uh today's class the last 10 minutes we'll have a speaker from relational AI who unfortunately the the co-founder supposed to come this week to our to our visit day uh from Monday and Tuesday but he uh he couldn't make it because of other issues so but they're they're going to give a talk today about what they're doing and I will say as a spoiler relational AI is going to be a weird system uh it's it's pretty far out there much different than what you normally think of in a day system and I think they're really doing some cool things um who here has ever heard of data
6:36 log nobody okay so data log will be a alternative to SQL to represent uh to to run write queries over data and I think they translate SQL to data log and then data log is allows you to do certain things that you can't really do easily in SQL um and it's often times use in like hardcore modeling but again these guys uh they're really smart and talk about some real cool stuff that they're doing
7:00 okay so this sort of obvious database systems we need data structures right we need them for basically every part of of the system so obviously internal metadata we'll see this when we keep track of like the page page directory right that's basically some kind of data structure that allows us to say for given page ID where to go find it we T how in index organized tables we could actually have the data structure itself be the way we represent data like having the leaf nodes in our tree structure be the place where where we're going to store tupal values or tupal we're going to need these for temporary data structures and this is going to seem like kind of crazy but like it often times when you run a query you're actually going to build a big hash table
7:41 do something real quickly on it and then immediately throw it away so we need to have data structures that we can tear up and throw down very quickly and we see we'll see some optimizations how to handle those and then last one is probably what you're most familiar with using them for table indexes like for it's given some key Either the primary key or a secondary key one key or multiple Keys together we want to be able to do a mapping from that to to find a
8:03 tupal and some of the indexes it'll be the the record ID that we talked about before will be the value of of the index like I do a key look up I get to the leaf node now I have the the record ID that I can then jump to the page that has the data I want in some SEL like my SQL for example the value actually is going to be for secondary indexes the primary key so you do a secondary key look up in the index get to the bottom now you get the primary key do a another look up in the primary key Index right from a data structure perspective it doesn't really matter uh what what it's actually storing but again index is going to be very important for us and we'll start covering them more in next
8:40 class so if we're now going to build our system from scratch and decide what we want our data structures to do we want to think about what are the design goals we need to have in our in our system
8:50 right so how are we going to lay out the data structure in memory or in these disc pages so that we can do efficient access on them right we obviously want to avoid NP complete problems or Solutions uh but in some cases it you know the the complexity might actually be pretty
9:07 bad and again as I said before we may choose certain data structures that in memory might be the most most may not be the most efficient way to do it but because we could be reading something from disk and we want to maximize squential access that is actually the right data structure to do the spoiler is going to be the B+ Tre is actually works for both in memory and and disk that's why it's the best uh but again we'll cover that next class
9:30 then the next thing we need to worry about is how are we going to allow multiple threads or workers or processes in our database system access this data structure at the same time without causing problems for ourselves and then we we'll cover this next class more but there'll be basically two types of problems there's physical layout problems or physical Integrity problems where two threads are trying to write to the same thing at the same time and they collaborate each other there's like a dangly pointer and then you seg fault and crash because you follow a pointed to nowhere but there'll be later in the semester about logical problems where
10:01 two threads try to insert the same key at the same time What should happen should I have duplicate Keys should one of them fail and how do I handle that or say I insert something somebody else comes and deletes my key I come back and try to read my key again should I see it
10:16 right that's a logical issue we'll cover we'll cover later on right and then uh in two weeks we'll talk about for we'll start off talking about how to do single threaded data structures I'll sprink on a little bit about latching as we go along but there'll be a whole lecture just how to make these things thread safe uh in two
10:34 weeks all right so hashtable is a uh should not be uh should not be a foreign concept to anybody here uh since it's upper level course you probably encounter these in in in other CS classes but the the higho idea is that it's going to implement what we call an associative unordered associative array that's going to map keys to values I I said we can use this hash table in different parts of the system so the keys and values could vary depending on the context of how it's being used right it could be something for internal metadata could be the actual table indexes and therefore the keys are related to tupal in the in the tables
11:07 for our purposes here today it doesn't matter but I'll talk a little bit about how we handle uh different Corner cases with them so it's going to going do a mapping key to values and it's going to rely on this hash function to compute some offset or some location in the hash table for a given key and that location is going to be either the exact location of of the has the key that we want or at least get us hopefully close to it where we can then search around and figure out where where's that where's where's the key that that we actually
11:38 want and so because it's unordered because this hash function uh is is basically taking any arbitrary B bite array running through this hash function and then you come out with this random number you're basically making this be completely random
11:55 IO right at least at least in the first step of jumping into the hash table with the hash function right so instead of like in a order preserving data structure like a tree right where things are sorted based on you know the key values or the keys right where I can sort of loop through scan through the data structure and find things in the order I expect them this hash was really making things completely random and this is going to be useful for us because it'll handle skew hopefully least your half function hopefully handle skew where now you can have sort of the data laid out evenly distributed throughout the data structure and there's a lot of benefits of having uh having that having that randomness
12:29 so the space complexity of our hash tables are going to be o n for NS that's the number of keys that we need to store and then the uh time complexity is going to be on average 01 meaning like in most cases I I do my I do my look up into my hash table and I get I find exactly the thing I'm looking for right in worst case scenario though it's going to be o n meaning I have to look at every single key to find the thing I'm looking for or discover that the thing I want is is not there
13:01 so again if you take an algorithm's course all the theory guys are salivating over o1 right think oh yeah that's great let me go do that right but in reality you know there's a constant factor involved in this and we actually going to care about them so what I mean by that is like if our hash function is super super slow like it takes 100 milliseconds to compute the hash then we jump into the hash table yeah it's 01
13:21 but like 100 milliseconds is a long time right that that's a couple disc iOS so even though the complexity uh the time complexity is is in our favor we'll see B plus trees where they're log in but like we we're going to still make sure that we Implement everything as efficient as
13:39 possible right because constants equal money right if if you're running a large system you're you know an expensive Hardware you don't want things to be slow all right so this like a really basic static hash table and this is sort of motivate why we're going to do the things uh and do more complex schemes that we'll talk about in the rest of the lecture so let's say that we just have a giant array um where we know Ahad a Time the number of keys that we have let's say we have n keys and we just have this giant array with uh with just for you know every possible key uh we could have we just have a pointer to some
14:15 location uh you know on a page or in memory that has the the the data we want and we won't worry too much just yet what what actually we're pointing to but you assume this is this is the key and followed by some value like that's that's again that's the associate array in of a hash table mapping keys to
14:35 values does this work technically yes right this is a good idea though you're shaking head no why you said uh if I think you're saying if you have a sparse number of keys like like the you could have one to a bill but if you only have two keys you still have to store a billion entries because you don't know what keys be showing up yep that's one problem yes could like the hash of a key could clash with other has ofy so he said if uh the hash of a key could he said Clash have a collision
15:16 collide with another one right but assume again assume I have I know exactly have n values right and I could have one slot for every single possible value right so you wouldn't have a collision yes uh if resize the whole array you have to redistribute everything she says if you have to resize the whole array whole array you you have to redistribute everything no why right because I could just if I have now n you know 2 N I just have 2 N down here and then I don't there anybody up above that's not a
15:45 problem think this like the identity function like for given say again there just integers the integer that of my key just tells me what all set to go to and then I have a pointer to go find thing I want
15:57 yes says not friendly to cash why he says if the um it's not it's not friendly to C cash the CPU cache I'm assuming or actually doesn't matter that that the you're saying that the the when you do the key look up then you have to follow that pointer now you're jumping to some other location that may not be local to where you did First Look up yeah that is a problem but we're going to have that problem for other hash tables as well it's unavoidable all right so there's basically three assumptions that are that are not always realistic that why this sort of simple static hashable aren't going to work
16:41 first is that me it's obvious is that I'm assuming I know the number of keys ahead of time right and then as she said well what if you resize well you could you know just double things uh or add add more spaces as you need but it's very rare that you know exactly the number of keys and the domain of those keys ahead of
16:57 time right right and so as he pointed out it could be I have two keys out of a billion possible values but I have to allocate a billion possible slots now and I'm it's I'm wasting space so of related to he was saying that you could have keys collided and I said in the case if I assume that well he said you could have collisions on keys and I said well if you assume they're unique it's not a problem but but it's not always going to be
17:21 unique right just think of like doing lookups on uh you know people taking this course if I just try to find all the people in 44 5 645 there's a bunch of you students here you could potentially have Collide on on those same
17:34 keys and then the other one is this this is more theoretical but uh I'm assuming that I have this magic identity function that can map me exactly to the exact location for a given key just the the the a unique location in my in my my slot array Point array uh and no matter what the value is I can always guarantee that and so if they're integers yeah you just take the identity that's easy but how do I handle strings how do I on variable length
18:01 strings right so this would be called it was called a perfect hash function I know Jes is doing some research in this area but you basically have to mean some extra metad data extra metadata it's never truly perfect but a perfect hash function would be for any unique key you get a unique hash value right it shows up in the theory in practice you it's not easy to do and no system does
18:23 it right so that means that we'd have two keys that you just look at the bits of those keys they're going to be different but I run through my hash function they're going to come back with the same hash value and I have a collision I have to handle that
18:35 yes bad assumtion says y assumption to a bad assumption so what if I so if I have um say you have uh say you have a database that has uh a list of users people and then you have phone numbers right and so that phone number table has a far and key reference to your user ID but now you can have multiple phone numbers so now if I try to say for a given user ID give me their phone number
19:01 if you have multiple phone numbers then then I can't have in this this example here I would have two you know two things to point to for number two but I can't do that in this in this example so A hashtable ATS core is comprised of two pieces that are going to handle all these these issues that we just talked about the first as I said is this hash function that's going to be a uh be able to to map some large key space like any AR you know arbitrary string or or float time stamp whatever you want and it's going to map it to a a smaller domain and it's typically going to produce a fixed length value like a 32-bit integer or a 64-bit
19:40 integer so when we decide our how what hasch marks you want to use we'll just see next next slide right there's going to be this trade-off between we want it to be really fast as I said we don't want something to take hundreds of milliseconds to computer hash but then again we don't want something to have a high Collision rate meaning for two distinct keys I get back the same hash value
20:00 right what's the fastest possible hash function you can have what that identity even faster than that zero zero yeah or one right no matter what key I give you I give you back one the Collision rate is terrible
20:17 right but it's going to be fast because that's going to be hanging out in in CP registers right so we want some there's obviously the two extremes we want something in the middle and then the the the second design decision is going to be what we call the hashing and this is going to be the protocol that we're going to use to handle conflicts or key collisions right you have two distinct Keys hashing to the same location in your hash table what do we do and again there'll be this trade-off between uh we just have this really large hash table with with a bunch of slots uh where we could put keys in and then if it's really big it's very unlikely that we would have Collision but then now that means we need to store a lot of memory
20:56 uh or store a lot of disc have use a lot of disc space to store this giant hash table thing and the other end extreme would be we only have a hashtable with one slot and everything collides into that we have to deal with that you know it's it's less storage but the compute is going to be much higher so this is like classic computer science the storage versus compute trade-off here and we and depending on our environment depending on our Hardware we want to maybe choose one scheme versus
21:18 another okay so we're going to go through both of these uh in in the in for hashing scheme we'll discuss this again in context of static hash cables we have fixed size and then we'll see Dynamic hashing Hash Hash tables where you can scale up and
21:33 down all right so as I said a hash function at this core is just going to be some for some input key we've return back some energy representation of that key it's usually 32 or 64 bits right so this is the nice advantage that's taking arbitrary bite array that's the key and coming back with a fixed length
21:51 value and as I said we want something that's going be fast we want something to have a low Collision rate we don't care about any crypto graphic properties of the hash function we're using so if you're familiar with like sha 256 or sha 1 uh these things are very expensive we don't want to use them because we don't we're not leaking any information right this is a hash function we're using internally for our database system it's not you know someone's already given the database system that we're building
22:18 their data they're going to trust us to operate on it so our hash function is you know doesn't need to be it's not exposing anything to the outside world you don't build a hash table and show it to everyone right so we don't need any of these things we just want something that has the nice Collision rate versus uh
22:35 speed so good news is that we don't need to design a hash hash function for ourselves there's a lot of available out there written by really smart people that we can just exploit and and use on our database system and this is what nearly all dat systems postgress uses I think rolls their own for historic reasons but most modern systems are not going to write their own hash function
22:54 and so this is just sort of a menu of the things you could possibly pick the way to sort of think about this is that murmur hash was sort of the the one of the the the first of these new generation hash functions that care about speed um that sort of came out 2008 and then both Google and Facebook and other big tech companies kind of made their own versions of these things that have different properties um the in general the the state-ofthe-art one that you almost always want to use is going to be the XX hash from from Facebook and it's by this guy who created this D standard uh compression algorithm there I think up to version three and there's different flavors of of XX hash but this this is going to be the one you're going to want to use in just in
23:36 general so if you want to if you if you're curious to know what kind of other hash functions are out there uh there's this GitHub repo I think written by the M hash guy called Smasher and it's basically a micro Benchmark that can looks at all possible different hash functions that are out there on the internet and runs them through his torture test and measures how how good they are uh the Collision rate and how fast they they go and then so in the read me here he sort of has the ranking list of the uh the latest one so this is as of today so Rabbit Hash is apparently the fastest one and then XS low three low that's that's the XS one there that's the second fastest and again this just trade off between the Collision rate and the uh and the um and the speed
24:19 XX has is usually the right one in most those situations so that's it that's all you need to know about hash functions use something that already exists we're done right we're dat people though we care about though actually the data structure
24:33 inside so static hashing scheme that we're going to talk about uh we two variants called linear probe hashing and cucko hashing and these be also categorized as what are called open addressing hash tables right and that just means that the location of a of a key that we're putting into a hash table
24:51 is open meaning it doesn't always have to be at the exact same location every single time and so we're going talk about linear prop hasing which the most common one and then cuckoo hashing will be an extension of this there's a bunch of different variants over over the decades that people have tried to build to make better H static hash tables uh that we're not going to cover in this class we'll cover in the advanced class
25:10 like Robin Hood hashing hobscot hashing Swiss tables I think that's Google has something on this as well um right there all going to be variants of this and it's really come down to being when it comes time there's this a collision what do I do right do I move out whatever is in the space I want or do I do I look somewhere else to go at a high L that that's the variations that they all they're all trying to have right but linear prob hashing is going to be the most simplistic one and so the the tricky thing about linear prop passing or at least when you try to Google and understand what's going on there's the linear probe hashing that I'm talking about and there's linear probing refers to how you're going to probe into it meaning you're just going to scan linearly there's also quadratic probe hashing there's other variant of that
25:53 and then at the end of the class we'll talk about linear hashing which is different than the linear probe hashing table uh which is because a dynamic scheme but to make you understand there two distinct approaches to handling hash
26:08 tables all right so linear prop hashing it's it's it's the most simplistic thing you can have it's a giant array of slots that are fixed length where we can store data key value Pairs and so we'll take our hash function for our given key hash it hash the key then mod n by the number of slots we have our hash table that's going to give us some starting point to jump into this giant array and then we start looking for a free slot to put something in or the key that that we're looking
26:39 for so again the hashing seems going to VAR in how you handle conflicts so if I hash my key I land into my to the slot array and the the space is occupied because I'm trying to insert something then I'm just going to scan down in sequential order until I find the next free slot then I insert my key there the the inverse of that if I'm trying to do a look up on something I hash it mod n land at the slot array
27:04 scan down literally and look at every single key value pair to I find the what I want or I find an empty slot in which case I know that the key I'm looking for isn't there that's it we we'll go through an
27:18 example uh this is what you get I would say in I think python gives you this when you get a when you get a as for a dictionary I'm pretty sure you get this dat structor but this this thing is widely used in in a lot of systems especially when you're doing hash joints which we'll cover later there most people are going to build build something like this because it's so simple and it's actually really fast so the one thing we need to keep track in our hash table is this this this load factor which basically the percentage of the the hash table that is occupied uh the slots that are
27:47 occupied and every system will have different uh thresholds but it basically says the load factor is if I go above some threshold then I'm going to consider it being full right say like 70% load Factor then I'm going to stop whatever I'm doing on this hash table if I need to still insert things into it make a new hash table that's double the size of my current one and then scan through the old hash table rehash all the keys and put them into the new one that's how you do resizing
28:15 in these these data structures and obviously that sucks because like now you're blocking all your threads while you're just doubling the size of it and this is what the dyamic hashing schemes will try to avoid but often times if you if you can try to estimate the the number of keys you need to put into it then uh then you can try to avoid
28:32 this right post tries to do this every D when you're doing a hash hash join you have to build a hash table it tries to estimate the number of tupal that's going to get come up from the from the bottom of the query plan from whatever table or that you're scanning and based on that estimate then it sizes your hash table if it gets it wrong it has to stop double the size and and load it all back in but again by sizing it uh correctly hopefully you'll avoid that this goes back to what I was saying before like in the most extreme case we just have this infinite size hash table we would never have to do this block and
29:01 resize but because we we live in reality we we have to size it something and we want to try to be not too conservative because we don't want to resize but not too big because we don't want to waste memory that we could be using for other
29:14 things all right so let's look at an example here so again so say these are all the keys I'm G want to deal with and this is this is our hash table here just uh you know array of slots where we key value pairs so if I want to insert a I again I hash it I mod n where n's the number of of slots that I have in my hash table I jump to some offset in this case here I see that it's empty because say the very beginning the hash table is empty and I'm going to store my my key value pair and we'll cover the next slide what the key value pair is but let's say we're going to store the original key in there because we need to know when we start scanning is this the same key that I'm looking for right so you still need the key and then the value will be whatever payload or whatever what we're actually trying to
29:56 store all right so now I want to insert B same thing hash it mod n and then I jump to this this top top slot here it's empty I can go ahead and insert my my I go ahead insert uh key
30:07 B now I if I do I want to insert C when I hash it I land to that slot where a is is currently occupying so I I can't store anything in there because a is already in there so now I'm just going to have a cursor scan through the the hash table until I find the next free slot then I can go ahead and insert C
30:28 and you can think of this as a circular buffer meaning if I get to the bottom slot here and again I can't can't find a free slot I just loop back around and start over now obviously that means I need to keep track of where I started to avoid getting stuck in infinite Loop but as I said you would set the load factor to be like 70 80% to avoid ever having to have an infinite
30:49 Loop so now I insert d d goes where C is can't can't go there scan down the next three SL is right below insert e e wants to go where a is can't go there go down can't go where C is go down can't go where D is go down and then I find my my free slot there and I insert it and let's let's just put F at the bottom here same as
31:09 before pretty easy right any questions yes isn't this like complicate retrieval though does does this complicate retrieval yeah like if I want to get I don't know say the value at C but C to like a make the so his question is does does this complicate retrieval because if I want to get C say C's already in here I hash it I land where a is I do myy now that's why I have to store the key there now I compare C with a a doesn't go C so I keep scanning aha now the next slot I find C right but say I'm looking for you know q i hash where a is I compare Q to a not there compare to C to a not there keep going now I find my empty slot therefore I know that Q cannot be in this hash table because if it exists did I would have seen it
31:59 you know in in the previous slots yes question is how do you handle deletions we'll come to that in a second again for some depending on where you're using this in the data system like a hash joint you're not going have deletes you just insert insert insert read read read then throw it away but yes we need to handle Del we'll give that in a second yes how is this a good idea because I see like every collection happen you get like
32:29 like like worst case worst case yes how this a good idea yeah because again if I size my hash table reasonably and I have a you know okay load Factor then I'm not going to have to do the end scan I'll maybe be so many jumps away it Simplicity is actually part of its advantage and
32:48 again I'm just showing sort of this diagram on PowerPoint but these would be potentially backed by dis pages but now I if I'm just doing a sequential scan if I have to go to dis I'm doing smal scan on on continuous Pages for the hash
33:03 table right in practice you know you actually I don't know the number of how many hops you have to do to find what you're looking for but again there's other variations we won't get into where like Robin Hood hashing um will actually can swap the order of things you say uh if one key is farther away than it would should have been than than my key I can swap the order so it's always kind of closer to where it should be right
33:28 seems like a clever idea it actually is often slower because Simplicity make makes a huge difference here okay so what are these key value pairs what what are the ACT entries well there's two cases right the easiest case is when the key is fixed length and the value is fixed length like a 30 bit integer with a 302 bit integer then I can easily store that in my uh in my hash table because it's always going to be fix length all sets meaning when I hash it mod End by the number of slots I'm going to land exactly where I need to be right and optionally if I want to try to speed things up I could store the hash that I computed when I inserted the key inside of the the the the key value pair as well right because as I'm scanning through say it's like uh 30 bit integer hashes but then like 128 byte
34:23 strings it's way faster to do that string uh integer comparison than look at the strings so if I have the hash that'll you know that'll I can easily check whether something are are equivalent to each other if they are I still have to check the whole keys but if they're not I know that the whole keys will never match so I just skip
34:41 it right compute versus storage I'm spend spend a little storage space to store the hash in the hash table but I you know my lookups can potentially go faster to handle VAR length Keys you basically have to have a whole separate table a temp table
34:58 that's storing the the thing you're actually trying to represent right so temp table would be private to the query or whatever actually is running this so we don't to have all this extra mechanisms uh for like recovery uh we would have for for regular data tables
35:13 um in some cases you know we can have an optimized version of this and it could just be also we piggy back off of the existing page infrastructure we have so I'm not showing this as a slot of page but it could just be a slot of page
35:24 right it could just also point back to the the the original Tu itself not not necessarily you can't do that if you're doing joins but the key would just be the hash that we have and then the value is going to be the record ID so both will be fixed length so that'll handle our our offset jumps into the array and then the record ID is just a pointer as we said before a reference to where to find the the whole
35:48 data so again having the hash is part of the key I can do a quick comparisons to see whether the key I'm looking for hashes to Hash that I see and if not then I don't need need to follow the pointer if it does then I need to go look down so it's not it seems like it'd be terrible because you're jum following this pointer for every single entry but it's not that bad in practice because the hashes will will not
36:09 match all right so let's handle his question how do you do deletes let's say I delete C so again doing delete is the same thing as doing a lookup I first hash the key that I'm trying to delete that do my offset jump into the slot array I land where a is a doesn't equal C that's not what I want keep scanning down then I find C now I have a match right and I blow away the tub or blow away the entry in the hash
36:36 table he's shaking his head no yes why so he said and he's correct that if now I have this this empty space in here well I said that I was scann through when I'm trying to do lookups to see you know to try to find my key soon as I find an empty slot then I know that the thing I'm looking for isn't there so now if I have this empty slot here and I scan uh I scan for d i look do try to do look up on d d is going to Hash to this location it's empty says oh my search is done you don't have what I want but in reality it's it's right below where I wanted
37:20 it all right so there's two approaches to handle this one is just to do movement so you take all the keys that are below you in the slot array from the entry just deleted and you rehash them and slide them
37:35 up right you're shaking head no good idea bad idea why why is a bad idea he says you to re rehash everything yes it's expensive it's not good and this does solve our problem now when we do a look at a d it's going to it's going to find what we want but as he said this is super expensive all right and we have to rehash everything and and we don't want to do this and in some cases too we have things like B over here like say whatever reason it it it hatched to a new location we have to slide it down right so yeah the the the blast radius of doing this optimization
38:11 or doing this this this adjustment could be very expensive and therefore I'm not aware of any system that actually does this better approach is use tombstones so all we need to do now when we delete d right or sorry delete C we'll put a little marker here that says that this thing has been deleted
38:33 logically and so now when anybody comes along and does a scan like I do look up in D it lands to this location sees the tombstone says yeah it's empty but treat it as if it something was actually there it's not my key uh least at least it could have been new key but it's not the key you're looking for right now so then I just scan down through like like I was doing before right
39:00 so this handles now the case where if I want to put something in there again if I see the the tombstone it's okay for me to treat this as empty and I can put something there and that doesn't fou up any of the ordering guarantees that we'd have under linear
39:15 probing so this is the most common approach now again some systems when they have linear probe hash tables they don't actually Implement deletes because you don't need them in some cases but if you do need to handle deletes uh logical tombstones would be the right way to do this
39:33 yes this question is how do you treat tombstones as part of the load Factor uh you would treat that actually a good question I don't don't know uh if again if you would have to you you probably have to treat it as part of an occupied space because you have to jump through it
39:52 um and often times you don't actually want to store the the the tombstone as part of the the entry here because how would you do that you have to store an extra bit to say this thing been log deleted and then now that files up with alignment that we talked about before so a more common approach is either within the page where the the slots being stored for in the hash table or even a global uh uh data structure where you just keep track of like here's all the metadata about my my hash table and I check that first before I maybe go make any decisions about what I'm looking at inside the hash table so I can have a separate bit map that says for this slot location is it empty or
40:31 not yes con when when I say garbage collection I mean what sorry uh yeah so yes I say you made dber col yes if you if you want to keep reusing the if you're not going to throw the hash table and and it's meant to be stick around for a long time somebody needs to go through look at all the Tombstones and then free up the space and then potentially move things around
41:02 yes okay so the other thing we got to handle is non-unique keys right you'd have two two two records have the exact same keys but are pointing to different values which is common in secondary indexes so the easy way to do this or one way to do this is to do separate link lists right so you have the you have your regular hash table doing ler probing but the value now is going to be a
41:27 or some reference to some other uh value list and then now when I do a look up for a given key I follow that follow that pointer get the value list and then do either sequential scan if it's unsorted or if they're presorted I can do binary search on that right but I have to follow something and do look at somewh El to see whether the the value that I want is available or if I want all the values I just you know iterate over that
41:51 list but this again this requires now additional infrastructure in our system to maintain these these these uh extra pages so that's not this isn't that common the alternative approach is to have just cheat treat redundant Keys as uh ignore them just treat them as unique Keys even though they're not really and depending on what operation I'm doing I have to be make sure I I uh get all the entries for given key and not just maybe the first one so the idea is like again you just ignore that they're unique uh and when I do an insert into them I just do the scan as as I did before and find the next free slot and insert it into
42:36 it then now if someone says give me all the give me all the values for key XYZ I got to scan through until I find all the xyz's until I get to the first empty slot and then therefore I know I won't have any X XYZ keys in
42:51 there so the second approach uh is is kind of more wasteful because you're storing the key multiple times right XYZ over and over again have a billion entries for it I have to have billion copies of XYZ in my hash table versus this the one up here I only store it once but then the downside is again I have to maintain this these extra value list yes so we the key for second time just treat it as there's a cision this question when we store the same key the second time do we treat it as a collision yes does that mean we need
43:23 to right I I insert a new XY say iert a new XYZ I hash into here I it's not a free slot I skip skip skip skip keep scanning then maybe the free slot's right here then iert XYZ wouldn't the search be quite expensive says the question is wouldn't the search be quite expensive yes but like again depending on the size of my hash table I might be
43:47 okay all right so I'm quickly clue uh go through some optimization you can do this is more on implementation side so instead of having a general purpose hash table uh where it can handle any possible key type and and and whatnot you could actually have specialized through either C++ templating or
44:04 handrolled uh optimized versions to handle keys of different sizes right and maybe you maybe pack things in Pages differently maybe maybe you compress them in way one ways versus other right if you know the types ahead of time and you try to do the most common things like here's a bunch of integer keys or integer values you can have optimized versions of these click house does this click house has 20 different versions of hash tables in their system for all the different possible types it's very
44:30 impressive next one you can store separate metadata or store the Met as as a separate array or separate hash table so I said before like you you could have this sort of this additional data structure that keeps all track of all the metadata about what's in your hash table you check that first before you maybe check something in in the the full hash table and that way if something's not in the first the first uh the first data structure you know won't be in the larger
44:54 one and the last one is to uh if if you if you don't want to blow away the the hash table every single time and reallocate all the memory if you want to be able to reuse it from one quer to the next you want a quick and efficient way to basically zero zero out the contents of that hashtable without having to go through it and overwrite everything so and click house does this as well so they basically maintain a version number
45:17 for the hash table and then the pages for or slots are located or even inal slots so if I know that I'm done with this hash table I'm using it for the next query I just increment the the the version number by one now when I do any look up in my hash table if the slot version number doesn't match my table version number I know it's from the older version and I can treat it as
45:39 empty so there's a really great blog article uh from The Click house guys written by that guy that person over there that discuss all the very optimizations they do in Click house and it's very impressive and this of all the systems that I've seen that publicly talk about what they're doing in hash tables click house does the most like like I think PR has two hash tables all right they have
46:01 20 all right so A variation is this is going to be CUO hashing and the idea here is that it's going to be an alternative to having do squential scans to find the next free slot or find the key that I'm looking for what we're going to do instead is have multiple hash functions when we do our look up in our hash
46:20 table hash the key multiple times the different hash functions they're all going to jump to different locations and I use that to find a free slot or find the key that I'm I'm looking for now the challenge is going to be well what if I want to insert something I hash it multiple times and all all the slots are are occupied well now you're just going to steal one of the slots from somebody else make them come out and go back into the data structure so now all your lookups and deletions are guaranteed 01 because you'll have to Hash multiple times but it's going to be one lookup to find the thing you're looking for you going to be there or not there you never have to scan but the penalty is going to be when you do inserts now may be bouncing back and forth taking things in and out until you find enough free free
47:02 slots so the only system that I know that does this is a accelerator for db2 out of IBM called db2 Blue uh it's in the paper that they talk about but it's it's probably used in other systems I'm just not aware of and then turns out the best open source implementation of a kouu hash table came from Dave Anderson at CMU uh it was written by an undergrad several years ago almost a decade ago uh he still maintains it the last commit was like 3 weeks ago uh even though we graduated um and I think Dave said Google uses their implementation a lot in other internal things all right so let's see how what it looks like again so say now I want to put a into uh put key a into my my hash table say I just have two hash functions I think the default is in cucko hash the cucko hash impation is three you can have any any arbitrary number and of course there's a tra up between how many hashing you're hashes you're Computing but this case here I Hash A once uh
47:57 twice using different hash functions they're both going to map to different locations in in my slot array and then I flip a coin and pick whatever one I want to use the table's empty I'll use the first one now put insert B same thing hash it twice I get two locations here the first hash function mats me to where a is so that space is being occupied so I can't use that so I just use the second one because that's empty yes
48:27 if flip a coin or pick the first it doesn't matter the first one is open yeah his question is would you actually compute the both hash functions simultaneously or you just compute the first one check it's empty you could just do it in in serial order like that yes it doesn't matter for visualization purpos I'm to show like we're looking at
48:49 both all right B goes again B wants to go in can't go to the first hash function because that's occupied by a so we go to the first pace so now insert C the first hash function takes us to where a is the second hash function takes us to where C is so both spaces are occupied so in this case here again I don't think it matters it doesn't matter uh it doesn't matter whether you pick one versus the other but let's say it's going to pick the where B is the second hash function so it's going to CL
49:15 be over the head take its slot and kick it out of its house right and now C is inserted but now we got to put we got to put uh we got to put B back in So B comes out out since we know that it was hashed in with a second hash function right either we just hash both of them and see and keep track of this you wouldn't actually want maintain extra metadata but so we know so we're going to Hash it again uh for both them we'see that the second one takes us where we just came from so we got to Hash it from the first one that takes us now to where a was remember we saw that before when we inserted it but now again since we know that we got taken out uh we got to find a new home it's going to go steal a slot goer inserts itself there a pops out we hash it again and now it finds a a free
50:02 slot so now when we do a get right again you can do this sequentially or you do it parallel doesn't matter uh we're going to H you know hash B twice look at both locations until we find the the key that we actually want yes why do we not function weed for key so that we don't have to hash everything uh like multiple times for each has function
50:27 her question is why did I say we don't want to store what hash function we use to get us a location in there because again compute versus storage I have a billion entries I got to store now you know some bites to say uh you know what hash function I use is this not worth
50:44 it yes yes so he points out he's correct if now say going back here if I do Hash a back in and there's some other key here and now I know I try to put uh you know a got kicked out before so both hash functions are in you're pointing to things that are occupied You' be stuck in infinite Loop and you have to break out of that keep track of that and then double the size of the hash table and and start everything back in
51:14 yes okay no free lunch here but it's in practice the you know we're making the trade-off we're making uh inserts more expensive but our lookups are going faster so like do we just keep this question is do you keep a counter you just keep track you could keep track of where did I start what slot that I started if I see it again then I know I'm an infinite
51:40 Loop okay so uh 30 minutes left actually 20 minutes left all right so let's go through this the the damic hash tables I think maybe we'll have to roll over to ler hashing next class but we at least covered chain hashing and extendable hashing all right so the all the hash tables uh that we just talked about so far you have to know the number of keys ahead of time um but again you may not always know that and you want to be able to to to grow and so the these Dynamic
52:11 hash tables the idea is that they're going to increment and resize themselves without having to rehash everything and load it into a second hash table so the most common one that you're probably most familiar with is chain hashing I think this is what you get when you get a hash map in Java in the jdk and then exal hashing ler hashing are more Advanced
52:29 Alternatives so chain hashing is you basically have now the a slot array uh that you're going to you hash into and that's going to point to the beginning of this link list or this chain of buckets where we can insert uh insert key value Pairs and so now when I want to do a lookup I hash myself into the slot array that gives me a pointer to the beginning of this link list and now I I sequentially scan it till I find the key that I'm looking for
52:56 right and if I need to insert something and there's no more space in that chain I just add a new bucket and append it to the end of it right so this thinging can grow infinitely and we'll see how to how to handle that uh in extendable hashing linear hashing but again the idea is pretty pretty straightforward so again I have my bucket pointers my slot array uh I do want put a a hash inside this this gives me that pointer to the beginning of my link list I go ahead and insert a
53:22 now I want to put on B same thing Hash Hash into my bucket pointers I jump into a a beginning with link list iert an a same thing with C goes there I put D now in this case here you obviously would would have more than two slots in a bucket but for visualization purposes assume that's the case so in this case here this bucket is full so I'm going to have basically I'm going to create a new bucket and keep tracking this first one that the pointer to to to the next one in the chain so if I as I scan through looking for the key I'm looking for if it's not in this one but I I pointed to another bucket then I got to follow along that and get that
53:59 right same thing for e and so forth so in this case here this is going to equally penalize um uh inserts and lookups because we have to follow these pointers whereas like in cucko hashing we were making inserts F sorry inserts slower but lookups faster right everyone everyone has sort of pay the same cost in with these cases a simple optimization we can do and we'll see this later on when we talk about hash joints is that in this bucket pointer thing I could still I still to maintain a pointer to the beginning of the hash table but I can put a filter data structure in front of this that tells me whether the key exists in my bucket
54:34 chain right because now basically I'm partitioning the key space Within These these bucket chains so for this filter here I could have a a sort of a data structure that says does this key even exist yes or no can't tell me where it is right but it teally does it exist in my set so now when I do a lookup I check the filter first if the filter says no it doesn't exist then I don't even bother following the pointer and look at anything
55:02 else right we're do we're to use this or this filter will be essentially be a balloon filter we'll cover that next week what that's going to be but think of that going proba a data structure that that can tell me does something exist or not really fast again we'll cover that
55:19 later so in the case of the the chain hash table as I said it can the chain can grow infinitely right it has no mechanism no way to say this chain this grows forever and that' be terrible obviously because if I have really high skew where everything's hashing to one uh to one chain then it's just squential scan or linear scan to find anything right that's the worst case end that we talked about before so extendable hashing is going to be a technique that's going to allow us to incrementally split our buckets when chains go too too long and then rebalance things without having to rehash everything that we saw before
55:57 and linear hashing will be another technique as well so this technique is not that common it dates back from the I think the 80s um the only two systems that I know that implement this is the gnu dbm think of this as like a embedded key Value Store you could have in your application similar to like rock DB uh right just key value interface and then asri DB is a was a sort of a big data uh system for like hdfs or World um that came out of UC Irvine I think couch base now uses um but from their their documentation they're using extendable
56:32 hashing all right so it's going to be just like before we had this the The Bucket List uh or sorry these pointers here they're going to point to buckets but now we're going to maintain some extra meta metadata to keep track of how do we examine the data that a a that that a slot's going to point to so there's going to be this Global uh sort of This Global bit counter that's going to say What's the maximum number of bits we would have to examine to figure out
56:59 in our hashes where where we need to go and then for the Simplicity reasons we're also going to maintain these local counters that says for this given chain of buckets here's how many bits you had to look at to get to them right so you see we've already inserted some data the first one is going to be only one bit the bottom two are going to be two
57:17 bits and so what does that mean so that means that again when I hash my key I'm going to get back an integer it's just much you know 32 bits and I'm going to look at uh those bits to tell me what slot position do I want to look at in in my uh pointer array so in this case here the first two uh entries I'm only going to look at the first bit so both of these guys are going to point to that one at the top uh because that has the local bit of
57:44 one right these these ones down here I'm going to use the full maximum number of bits set by the global counter and that I'll look at both them and they're going to hatch to two different locations so now what is what's going on here the slot array could have multiple entries point to the same the same bucket and that's
58:05 okay so here's how to do a look up I do a look up on a i hash it mod it uh so I hash it get get some bit bit array and then look at my Global counter and it tells me how many bits I need to look at and then now when I I examine those two bits that's going to tell me what position I'm at in my slot array and that gives me the pointer where the The Bu pocket chain is for for for this
58:30 key all right so now I'm doing a put again look at my uh Global counter it's set to two so when I do a put I look at the first two bits that tells me that I want to go to one zero I follow that pointer it takes me to this bucket chain and I go ahead and insert my entry in
58:48 there do it another time let's put C in again look at the first two bits tells me what location and I want to look at I follow that pointer and that takes me to this bucket and now the bucket's
59:01 full so I need to overflow it I need to allocate more space for it uh but the way we're going to do this it's going to be localized to just this portion of the of of the of the hash table and I don't need to rebalance any of the other bucket
59:16 chains so I'm going to increase my Global counter to three expand out this slot array or this point array that's cheap right that's a bunch just you know it's a it's a uh just a bunch of 32bit pointers or 64-bit pointers that thing's not really big so so resizing that and copying things over is not a big deal and then now I want to add my new new um my new my my new bucket chain and then I'm going to look and look at all the bits as they go along and that's going to point to the different locations so going back here
59:50 again these guys here that that one at the top that's still only using one bit right so if the first bit is zero in my position in the slot array they're going to point to that first that first
1:00:02 chain right then the second one uh for this one we're still looking at two bits so that goes down here but then anyone that has three bits all right they're going to point to to different locations then I can go ahead and and insert the uh insert
1:00:24 C so again I moved things around or sorry I readjusted the uh the hash table without having to rehash everything and because this going back here because this thing overflowed right instead of having just adding another bucket behind it in the chain as we did in chain hashing I said I'm going to overflow it make split it split its Keys into two different buckets but and I just update the slotter without updating all the other
1:00:53 uh without updating all the other but yes is a reason question reason yeah that's that's a mistake yes uh z00 Z should point to going back here yeah should point to point to the top one right yeah so in the first bit the first bet is zero they all should be pointing to the top one here thank you for fine I'll fix that right and then the next one is is uh when it's what is it uh one one all point to the bottom one and then we have one z0 and one Z one right those two are distinguished
1:01:34 they point to separate separate chains thank you his question what would happen if the first bucket overflowed so you would just You' split it and then now since the local counter is one it's it counter would go to two
1:01:54 so now you have two buckets and you would have uh 001 sorry 01 would go to one bucket and 0 zero would go to another another bucket yeah so when you split a bucket you rehash everything that that's inside that bucket but because it's it's not an arbitrary length ver uh bucket chain it's not a it's not a major uh major operation so you're sort of advertising the rebalancing across multiple queries
1:02:28 I'm rushing this but we can we can cover this again on uh on Monday there's more questions all right the other alternative approach is do linear hashing and this is actually what what postest does um they call the dinina hash in the source code um and actually the the reason why postest has this data structure um because the woman who was a p student at Berkeley she wrote it this hash table and put it in to to post grass and then she had a startup called
1:02:55 uh sleepy cast software that made Berkley DB that used the same sort of hashtable idea right and then Oracle bought them uh and and you know now Oracle owns it but all right so this is a bit more complicated but what's going to happen is that we're going to maintain this extra this extra we call a split pointer that's going to tell us what's the next bucket that we want to split and this going be different than extandable hashing extandable hashing was anytime a bucket over overflowed
1:03:23 became full I split that bucket and only that bucket extendable hashing sorry linear hashing is be different where I'm going to split whatever I'm pointing at with my split pointer which may not necessarily be the the the bucket that overflowed the idea is that eventually I'll get to that bucket that overflowed and rebalance
1:03:44 things right it's almost like doing this a random splitting but over over longer periods of time everything balances out and everything will get uh you know will get get split so we're going to maintain multiple hash table hashes to figure out what's the right bucket we need to look at for a given key again based on where our split pointer is pointing at and then there's other things we can deal with like when should we actually overflow is just when when we run out of space in our page uh if if if it's uh if for one page if we have 10 pages you know that are in our chain then we overflow right you
1:04:19 different systems can you can do different things the idea is again we want to localize the resizing of our hash table to just some portion of it which may not be the one that overflowed but that's okay so again we have our bucket pointers that pointing to different locations right and these are numbered in in squential order and then we have the split pointer that's again point to what's the next bucket chain that we're going to over we're going to split
1:04:44 whenever we overflow and so we'll have a hash function that says uh for given key you run through the hash function and then mod at n where 's the number of of of of bucket pointers we have at the time that this we instantiated this hash table so we have four entries here so we take the key and mod mod by
1:05:03 four all right so now I'm going get on six right I just take my first hash function that I have moded by four and I get two and then I find the key I'm looking for right so that just looks like the chain hashing that we saw before nothing
1:05:17 fancy if I want I want to put 17 I hash it mod by four gives me the offset of one but now when I go to that chain I see that the bucket is full so I need to overflow so I'll create a new bucket just did in my chain hash table extended out and then iert
1:05:36 17 but now I need to have my split pointer instantiate the uh a splitting procedure to rebalance or to to to split whatever it's actually pointing at so in this case here it's pointing at zero so I need to go and and split zero even though again it didn't overflow it still has free space this is just how the algorithm works
1:05:56 so now what I'm going to do I'm going to add a new entry to my my bucket Point array Sor right and then I'm going to mod uh make a new hash function we're going to mod by 2N because it's double the number that I had before so I had four entries before and eventually I'm going to have eight entries so the reason why we we can do 2 end because we're going to Hash this key first see whether it's it's Bel above or below where our split pointer is located at if it's below it we just need this hash function it's if it's yeah if it's above it we just need the first hash function if it's below it we need the one down
1:06:26 below and then we the split pointer will keep going down until we reach whatever the ENT whatever the the length of n was when we stated the hash the hash function so in this case four so once we get past three we then loop back around and start start all over
1:06:41 again so let's see what this looks like okay so now we have a new entry four we're going to create a new new new chain here a new bucket then we go through and all the entries that were in the the the the bucket that we split we need to Hash them now by the second function so hash 8 mod by 8 it's zero so it stays where it's current located hash 20 mod 8 we get four that's now going to land down here and we go ahead and insert 20 down there so do a delete up there and then do an insert and 20 down
1:07:13 below and once this this rebalancing is done again just for the one chain that we split we move our spit pointer down by one now when I do a look up on 20 right 20 uh mod 4 gives me zero zero is above my uh my split pointer yes sorry it's above if it's above the split pointer you got to look at the second one if it's below you know it hasn't been split yet so you can just use the first hash function so in this case here I would mod uh you know hash by 20 mod by four I get zero zero is below where one is uh so now I got to Hash it again and then now I get four and then I can find the key that I want
1:07:55 other case I get say do look up a nine hash by four I get one one is where the split pointer is pointing at so I know it hasn't been split yet so therefore I only need the first hash function and I find the thing that I'm looking for and I'm
1:08:09 done all right so this again seems bizarre that you're splitting things that aren't the what you know what you want to be you're not splitting the thing that overflows you're splitting whatever you're pointing at but again eventually we will get to that and everything will work out just
1:08:29 fine all right so in the sake of time let me quickly just talk about deletes deletes basically says if I if I recognize that I'm deleting entry and now the the the the the bucket is empty and I'm below my split pointer then I can Theory I just I just clean it up throw it away and then move the split pointer back
1:08:49 up right and it's a localized chain all right so just to finish up so the these are hasht be important data structures that export o1 lookups for us and I said they're going to use all throughout the data system in in different ways you can use them for table indexes and we'll look at examples next week but in practice this is not what you're going to use because they're not going to support range queries you can't do things less than greater than you can only do equality predicates there something equals something in my hash table and furthermore I can I have to have all the keys in order to do my lookup so my index is on AB I can't do a lookup and a hash index without AB because otherwise I can't hash to the
1:09:31 location right whereas in a b+g we'll see we can do partial key lookups so when you call create index in in a database like this 99% of the time you're going to get you're going to get a B+ tree right which you're really getting something in post grass you would declare what data structure you want to use but in post grass you can actually say using hash you can tell I want to use a hash table
1:09:52 and it's going to use the the the linear hash table that we were talking about at the end okay all right I realized I was rushing this again but we we can I'll recap everything on on uh on Monday so starting next week on Monday again we'll talk about order preserving trees and we're really going to focus hard on the B+ tree because it is the best data structure of all time right tries are not bad tries are pretty good too but guess what you can put your tries in your B+
1:10:18 tree right you can do everything with it okay all right yeah thank you Andy thank
2. Jump to
1:10:23 you all for having me uh this will be quite the pet cleanser from hashmaps I apologize in advance uh so my name is Nico I lead the backand team at relational AI where we deal with query optimization and materialized views and incremental view maintenance and all kind of fun stuff like that and I'll try to give you a bit of a flavor of like what relational AI is is all about all right uh our thesis uh is that the next generation of Enterprise apps will be intelligent and that can mean everything or nothing I guess uh for us intelligent
1:10:55 applications uh apply models of the real world to data um and they do that in order to improve decision- making and take action automatically and that is what distinguishes them from like uh business intelligence and Reporting and all these kind of like backward looking things uh and it's really about like putting the data to work and actually take action in the in the real world uh and so the need for this kind of like repeatable high quality decision- making I guess is kind of unlimited and so we believe that every business will need like as many of them as they can get um and developing and putting them into production quickly is is critical and so to give you some kind of sense of like what uh decisions these intelligent
1:11:38 intelligent applications will first help make and then later make themselves we're thinking about stuff like which users are committing fraud here uh should I open a new Warehouse if so where should I do that uh what is the optimal maintenance schedule right like I have an optimization problem given my current real situation
1:11:56 on the ground and all of that intelligent applications are supposed to handle uh but we see that software complexity like so many other things is holding back intelligent applications and here we're really talking about complexity not in the ASM totic sense the Big O sense but rather as the things that make a system hard to understand uh and uh we believe that at the end of the day uh this complexity really grows with three things that is State control and
1:12:25 the overall volume of code that you're dealing with and that's because State basically the more State your system keeps the more scenarios you have to consider to understand how your system is behaving and the more control Logic the more explicit control logic you have uh the more kind of paths through that state space you have to consider in order to understand what's going on and then the more uh uh the more code you have to describe all this stuff it just compounds these problems right if you have your millions of lines of code then then all of this will be if you had like
1:12:56 100,000 lines of code um and so uh the headlines here are kind of inspired by a relatively well-known paper called out of the tarpet uh and we at relational AI we really believe that uh the things that get you into this tarpit of software complexity are architectures where the uh inputs into the system and the implications of that of those inputs are both part of the system State and they're managed explicitly and really like the simplest example of this if you imagine you have like a chat application
1:13:28 and you need to model all those messages and whether the message is read or not or whatever uh and then a very common thing you see is like people basically keep a counter of like the unread messages right and now whenever a new message pops in or user takes an action you have to update both the state about the messages and the state of the counter right and that's like caus all kinds of fun things in web applications
1:13:51 and it basically doesn't scale to any in any kind of real world uh application this explicit managing uh of implications and in these architectures business logic also tends to be hidden behind like layers and layers of boiler plate and JavaScript apis and all that stuff and so uh we think of these AS application Centric architectures which really just means that even though all these applications are working of more or less the same data the data that is coming into a business each of these applications kind of comes up with their own slightly Divergent interpretation of the data and so the things that get you out of this tarpet uh are systems where
1:14:30 um only the actual inputs form your state and all the implications of those inputs are automatically derived by the system through reasoning and reasoning for us is just the principled application of rules and other kinds of models in order to derive new information from your input and in such a system the business logic should be as much as possible declarative and focused on what is true about your business bu rather than focusing on like how to compute those things and so we and other people call these kind of architectures
1:15:01 data Centric which again means a lot of things to a lot of people but the key thing here is that the data and the interpretation the semantics are kept close close together and so my colleagues at relational AI we see this in the wild at many companies and many of my colleagues have helped build these kind of systems successfully at at uh places like Amazon and into it and and whatever yeah
1:15:25 all right uh but the problem with this is that uh uh if you have a data Centric architecture the problem is data doesn't really like to move anymore and it just keeps a creating workloads and it keeps a creating processes for governance and budgeting and that's really a problem if you're trying to start a database company and so we want to help our customers build intelligent applications right where their data is today and for us that's Snowflake and so relational AI is built on top of snowflake and it runs in the snowflake data Cloud called container services uh and from from that environment we inherit security
1:15:57 governance billing infrastructure all these things that are really hard to replicate um uh as a startup okay so uh if we want to build a system to help our customers deal with all this complexity we really kind of have to manage our own internal complexity right and this is where we believe that database theory has something unique to offer to us as system engineers and there's many examples of where this kind of connection happens at relational Ai and I'm just trying to give you like a flavor an example example um that that I really like and so the example that I picked here is the idea of query classes
1:16:32 uh basically we need a strategy so that we don't go insane when users throw like arbitrary real world business logic at us right we're no longer talking about like simple SQL queries this is really kind of complex business logic and database Theory gives us the Frameworks
1:16:46 uh with which we can like understand those queries based on by looking at the variables in the query and by looking at the relations that tie those variables together and each of those query classes that we can identify is backed by like a body of theoretical results and that means if you know the class you immediately know uh many relevant things like can this be parallelized will this scale can I incrementally maintain this without blowing up this kind of stuff
1:17:13 right and so we use Query classes uh to drive our evaluation strategy as a whole right so uh for example a couple of years back we had to ask ourselves like okay how will we evaluate and maintain arbitrary queries over like many terabytes of data uh and for us query classes are the way right like we look at the query we understand the class it belongs to and we try to break it up into subqueries from simpler classes
1:17:37 until we hit one that is low enough that we know how to scale it right and so in our case uh we try to boil everything down to a a class of queries known as prefix joints uh and um we connect those prefix joints with the distributed sorting algorithm and both of these Primitives have the distinction that they are very scalable and they are latency tolerant and for us as a database that is built natively on the cloud and works with data in Blob storage this property of being latency tolerant is extremely helpful uh and so
1:18:08 this is kind of what drives uh our strategy there and then another interesting way in which this kind of like Theory framework for thinking about the queries that users throw at us helps us with is to keep the optimization problem trackable right because I mentioned that we're making this promise that people can throw uh they can focus on like uh describing their business logic and we will pick the best algorithm for the job and and optimize
1:18:33 uh uh their logic uh but that's of course a very hard problem and it's hard way Beyond like all the typical things about join ordering and cardinalities and all that stuff right like there's so many questions do you focus on astics or do you focus on the time it takes you to optimize uh the the query do you focus on finding the best possible plan for a single query or you focus on finding something that is reusable in many different situations you focus on evaluating from scratch versus incremental maintenance there's so many uh so many different dimensions um and so what we can do is that if we know a class the class that the query Falls in
1:19:11 uh we can pick um deterministically a canonically good plan this might not be the best possible plan for that query but it is a known good plan under some uh wellth thought out cost model uh and we can offer that plan for the op to the optimizer for consideration right and so that way we don't hurt the quality the optimizer can always overrule the decision but it reduces effort uh it improves the robustness of the optimizer
1:19:36 decision uh and it also helps explain why a query is performing the way that it's performing or why the optimizer made a specific Choice um and so uh uh this is really kind of like something to to break that problem down into something that is more manageable where you where where you don't have a cost optimization problem with an infinite number of of Dimensions all right and so uh to summarize this
1:20:03 um uh the first takeaway here is that we think that software complexity is really holding back uh these new intelligent applications and we want to fight that with data Centric architectures where the semantics the interpretation of the data is very close to the data itself we don't want users to spell out the implications of new data they they should let the system do the reasoning and they should reduce code volume with declarative languages as much as possible right we want to let the system figure out the best algorithm to use for the job the second takeaway here is that data has gravity that we found that out the hard way and uh it won't come to you you have to go to where the data already is uh and the final takeaway uh is that systems in theory in our experience
1:20:47 really like need each other right they keep each other grounded systems Engineers can easily change like random unconnected benchmarks and theorists can easily like go off into space and so um in particular ideas like these query classes and these Frameworks help us make this like general purpose system that we're building tractable uh because an architecture that is efficient under some cost model that might not be the most realistic one usually beats an architecture that is not efficient under any uh cost model and so these kind of principles guarantees and invariants
1:21:18 that database Theory kind of um occupies itself with they are really what keep the system going uh at scale and with lots of people working on it all right and with that I'm done thank you so much get in touch if you like and if you want to learn more about the system my former colleague Martin he gave a long talk here at CMU about two years ago that you can find on YouTube awesome thank you all right we time for one
1:21:44 question are you still guys taking SQL and then coing it into Julia and then compiling that no uh we're not taking SQL uh so we have our own declarative language and uh we provide different front ends for that so people can basically uh uh create these queries in pyel uh that's our python our python interface and it boils down to our own internal language called Rel uh and so SQL for us is more like another interface language it's not what we compile to and do you compile real to Julia or the systems written in Julia
1:22:16 yes yes so we we no longer are an exclusively compiled uh evaluator we also uh do interpretation but we are still written in Julia yes do you support data log anymore or is that that that was logic blocks uh well like our internal uh uh target language um uh when basically all the higher order um features of the real language are compiled away that basically is datalog with like aggregations and all that stuff and recursion but we don't expose it that much got it awesome all right let's thank him
1:22:48 again thank you so much yeah I realize you can't you can't see the people applauding for you m I need something refreshing when I get finished manifesting too cold a whole bowl like Smith and Wesson one court and my thoughts hip hop related write a rhyme in my pants intoxicated lyrics are quicker with a simple Mo lier since I'm mer City Slicker bra waves are picker Rhymes I create rotate at a we too quick to duplicate F A bre at a skate mik at fah when I hold it real tight then I'm in flight then we ignite Blood starts to Bo you I heat up the party for you let my girl from me and my mic down with oil Rec still turn with third de burn from one man I heat up your brain give it a suntan so just cool let the temperature
1:23:34 rise to cool it off with s eyes [Music]