CMU Database Group · 1:28:00 · https://www.youtube.com/watch?v=nhlpwmOBEiE
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 lcks and M Clips the Chrome will make the average imitator do back flips you like a [Music]
0:27 pistols So today we're going to continue on the discussion uh this will be the last lecture on the the storage layer the bottom layer of of the database system so we're going talk about the different ways of representing data the storage models and then how to how to optimize it further through the compression before we get to that uh you have two things came out today uh homework 2 has been released and that'll be due on Sunday September 22nd and that's basically three questions uh multiple choice and you'll submit those in grade scope and then we've just posted uh project one is live the right is on the website and then I think the code and the announcement on PIAA has been released as well and so there'll be a recitation at 6 p.m. next next Wednesday on Project one so I we advise you to at least get started on it now
1:14 look over the write up it's very um it's very thorough what you'll need to do and that way when you go to the recitation isn't like what's the buff manager it's prob be like hey you know how do we get started how how do we approach to this what does this class mean how does this work together right so you want to come up the recitation with you know questions about like you know insightful questions because you've already get gotten started okay and so the lecture on the buffal manager will be Monday's class next week um so you but it's obvious what it is we keep alluding to it it's the thing that moves uh data Pages back and forth between dis and
1:46 memory and then I mentioned also last class uh on uh on Monday and Tuesday next week we'll have we're having our visit day from all the industry Partners um so Monday will be uh research talks we'll be there all day and then we'll come here and have class and then we'll go back and then Tuesday morning will be info sessions and then we just got confirmation right before the class that confluent will make it so we're trying to figure out what time that'll be so so some of you asked to meet confluent U there'll be info session with them as well okay and again if you're in this class or if you have friends that taken 445 6:45 before or 7:21 uh everyone's invited to come to this all
2:25 right all right so last class we were discussing uh again continuing our discussion on the what what the Storage level or storage layer of the D system is going to look like and we were contrasting what we just talked about in the third lecture of this sort of tupal oriented architecture with sloted pages and then we said hey here's some alternative approaches actually storing data the log structured approach where you're just appending uh all the changes and deletes and then uh you know it make the rights go faster but the reads go slower and then index organized storage would was basically saying instead of having these uh this heat file where things are unordered we're actually going to use an order data structure typically a B+ tree and just have the leaf nodes be the data
3:07 itself so all these approaches that that from the last two lectures these are going to be useful for uh for workloads that are right heavy mean you're doing lot insert update deletes or upserts right you're make it's a you're making a lot of changes to the database and you want that to work as efficiently as possible but then there's this whole other workload that you kind of did in homework one where it was readon queries
3:34 because you're basically running analytical operations analytical queries to try to derive new information from the existing data that you have and in in in those kind of queries we don't care about making the inserts updates and deletes as fast as possible we care about making the the select queries run as fast as possible so that's what today is about today is about understanding how can we store data in such a way that we make select go faster than we could otherwise in the slotted Pages or the lsms or the index
4:05 storage so first you know understand you know what it means to make analytical queries go faster we going to spend a little time high quick quickly discuss here's sort of the rough category of what database workloads look like um and put it into terms so that when we use
4:20 those terms later in the semester you'll know what I mean then we'll talk about the storage models and again this is the way to represent tupal and then if we'll see from the column store approach how we can rely on compression
4:30 to to speed things up further make things smaller and then we'll finish up again with a talk from Star tree which is going to be a analytical database system that's going to use the column Source off that we're talking about uh in in this lecture
4:44 okay so a very loose categorization of database workloads uh is can be roughly described in these three terms the first is called allp or online online transaction processing and this will be workloads applications that want to ingest new information from the outside world if you're a new startup this is typically what you end up building first like you build a website to take you know people put stuff in and and you want to store in the database
5:12 right those are running update insert insert update delete queries that are taking changes from the outside world and you want to store it in in your database so these are going to be typically uh more right heavy than the the other other ones we'll see in a second the thing to note about is that the the queries that we're going to run in workload are going to be they're not going to touch a lot of data at a time
5:35 so what I mean by that is if you ever think like when you go on Reddit or Hacker News or you buy something on Amazon right you fill out some forms you click some buttons and Records those changes the amount of data it's actually storing when you do those operations is pretty small right when I buy something on Amazon I put things in my cart you know it's inserting a record in some cart table somewhere and then I make a purchase it updates my payment information updates delivery information
6:01 right I'm inserting a small amount of data to do you know to make that purchase now the entire Amazon database is massive right because it's everything anyone's ever bought since the beginning you know since since beginning of time so that that database itself is going to be huge but the amount of data I'm inserting or changing is quite small and that's typical in in
6:21 LP so contrast this now with olap ol AP or online analytical processing this is where we have an existing data set we have an existing database and we want to extrapolate new information from it right I said before this is what data scientists are typically doing um right you have you're trying to derive new things or new patterns or information that you didn't have before from the data you've already collected from the old TP system so these queries are typically going to be more complex than you do in the old TP or old TP uh systems right allb systems like go get Andy's account
6:57 right do select star from account where where username equals Andy the amount of the query is quite simple but analytical could be something like compute the most the what what find the item that the the customers have bought the most when it's uh when it's a day in September in this city at this temperature at this time of day and they have other sort of features characteristics about we want to we we want to break it down on right and typically you'll be joining a bunch of other tables when you run these
7:27 queries and then the last one one is sort of a marketing term although oap was as well but it's sort of sort of uh it's in the uh it's in the vernacular now so people don't remember that how it came about but this is a Gartner term from a few years ago it's basically saying that there's some workloads where you want to do some LP and you want to do some olap at the same time and can you design a system that can try to accommodate both in actuality most applications are going to look like this anyway right like you you'll do some ulp stuff then maybe there's some queries that'll that you know extract new information but you know there's a couple systems that that claim their ASAP system because they want to try to do both things at the same
8:04 time so the if you start to think about the the workloads on these two axises uh you know first the x-axis here is it right heavy versus read heavy and then are the queries of the operations going to be simple complex you can s of think of like a quad chart like this where ootp is down in this corner we're going to be doing not always right heavy workloads but more right heavy than olap so we do bun more inserts update and deletes but the quer is we're going to be uh executing are going to be simple
8:30 and they're only touch a small amount of data then olap would be in this other other quadrant up here where the queries are going to be more more complex than oldp but they're mostly going to be read only and so the reason why I was saying that this olap term was a marketing term in the 90s so so most databases up until uh late the late 90s were just you know oldp was a category but everything was basically oldp because most businesses most people that running databases you just needed needed to collect information and only later on did people start wanting to be do more complex analytics on it so in the in the 9s
9:05 there was this guy named Jim Gray uh a very famous database researcher he vented two-phase locking and a bunch of other stuff we'll cover the rest of the semester he won the touring award in databases in in '96 um well he wrote this paper in like 93 94 where he's like hey here's this new category workload it's called online analytical processing it's called olap um but then it turned out he was being paid by a company that was trying to Brand olap system so you had to retract it um but the name still
9:32 stuck and then HT would be sort of here in the middle right but if you say if you tell somebody I'm running an OTB system they'll roughly know what you mean if you say you're running olap system they'll roughly know what you mean
9:42 nowadays so to delve deeper now and to what these workflows look like and what how storage can affect them uh let's use a really simple database schema sorry yes so how do you measure the complexity of a query this question is how do you measure the complexity of a query just terms of like think of the number of joins how many tables am I accessing how many Aggregates I'm doing it's it's not there's no scientific measurement but like select star where name equals Andy
10:06 that's pretty simple but select star or name equals Andy and join in this and join join join join so forth and do an aggregation and a window function and CTE that would be more complex okay y yes in the
10:19 back uh the question is what are these other quadrants like what would be a right heavy complex workload and this is not exact it's not exact signs here the lines are blurry so you might have a more complex uh you could have
10:35 a I don't really bring up transactions but you can imagine other uh that I could be right heavy but doing uh complex transactions like I want to update a billion records in a transactionally safe manner just read heavy read read only comic queries o laap doing bu of Rights on small amount of data simple quer ISP
10:56 like that that dichotomy enough is enough to understand what two systems you want to choose all right so this this sample uh datab scheme we're going to use is actually derived from Wikipedia like Wikipedia as far as I know is still written in PHP it's it runs off MySQL the one massive MySQL cluster so you can go it's open source you just go download their myql files and see what the schema looks like this this is a rough approximation of it so I have three tables I have uh user accounts pages and revisions and revisions has a far key reference to the user ID that made the revision and the far key reference to the page that that it corresponds to um
11:34 and for to speed things up the page uh table actually has a for key reference back to the uh to the revision that which is be the latest one so if I'm trying to look up the latest version of of a of a page I just follow that forign key
11:49 right so just remind us again that the relational model doesn't specify anything about how uh we we have to store data in a table or tups right and there's nothing about the relation model says we have to store the the data for a single tupal all within the same page
12:07 right we saw that last class when we talked about overflow Pages if I have a really large barar I could store that in a separate page and just have a pointer to it right but again as as I said at the end of last class you when you think of a database you probably think of like an Excel spreadsheet where like all the values for a single row are continuous one after another and the problem is going to be if we build a system based on that that sort of the Assumption it's not going to be the most efficient for some of the workloads in particular for the oap
12:35 workloads so if you take the Wikipedia schema uh and you want to run simple OTP uh queries on it it would sort of look like this right so if I want to get the latest page for uh so latest revision for a page I'm just doing a simple join on page and revisions and following that revision forign key to get the latest one so it's like doing a a single Tuple look up on the pages and a single Tuple look up on revisions and we we can next to that join pretty efficiently we'll cover that later or if I'm going to uh do an update query this is keeping track of the the last Tim stamp when somebody logged into a given account or if I need to insert a new revision right it's just inserting to that that uh the table with all all the
13:16 values for overlap it would look something like query the more complex overlap query look something like this so I'm only doing a single scan on user account but now I need to do an aggregation on the uh Define when somebody logged in with the with the host name that ends with. goov
13:35 this is actually a real example from uh a scandal a few years ago where because all of the uh provision history in Wikipedia is public uh they found that there was like for people in Congress they like their admins or staff were actually going and updating uh the Wikipedia records logging in on government computers and you see the.gov you know host names um and so that's obviously illegal you can't do that so this query would help you find these things right so in this case here even though again I'm only scanning one table
14:05 but I I I'm scanning just basically I need to access two columns the host name and the last login but I need to see all the tupal in order to find the ones that end end with. goov and then group them by you know the month that they logged in
14:22 right so a database system storage model is going to specify how we're going to physically organize TS on on dis and in memory and as I as I said before depending on how we do it like a row store versus a column store that's going to have a significant difference Performance Based on what workload we want to
14:41 run so the canonic approach most people think about when think about database storage would be called the Nary storage model or NSM is sort of the academic term V said row store it's the same thing decomposition storage model storage model or DSM or column store would be uh the more common term it's another approach and then we'll cover this last one called hybrid or or Ps uh which is going to look a little bit like the NSM look a little DSM and get still get the benefits of both of
15:10 them so as I already said the the NSM or the the the Nar storage model is where you store almost all the attributes all the values for a tupal are just contiguous each other in the same page right and this is going to be great for OTP as I said before because most of the time in LP uh workloads I'm accessing a small number of tbbl like typically one like if I'm doing a primary key look up and I'm typically going to need all the attributes for that uh you know in that query for that Tuple right I select star query from table where and you know username equals Andy the star is obviously getting all the attributes so I want all of the the two the all the values for that
15:54 Tuple uh you know return back to the client so if they're contous with each other then I just jump to one page ignoring overflows jump to the offset in that page based on the slot array or however I'm storing it and just do a M Copy and get all that data out that are right next to each other right I don't need to jump around to different locations in
16:12 memory and as you said before the the the datab page sizes are typically going to be you know some constant of the the harbor size and so again if everything fits in a single page it's one read to go get the data that I need right for for most of these queries
16:29 so this is just a a re-editing what we talked about before again what the the storage is going to look like again we're assuming we're doing tube oriented storage with slot a page slot uh uh slot arrays and so we just have this header with these slot arrays and then as we scan through and add our our data we're just appending it to the end and now I'm Shing that every record is going to have some header in front of it right this is where you would start the null bitmap that says what attributes are null or not and so as as I scan down and just insert all this data in from from this table right I'm just filling it up one after another and just you know add adding points in the slot
17:07 array so again if I want to go select star from where username equals Andy I I have some data structure that gets me to this page and then I jump to some offset and I just read all the bits that come after that and that's going to be all the data that I need and I don't need to jump anywhere
17:22 else so if we go back and do a simple query uh on our our Wikipedia database right select start from user account where username equals Andy or whatever and then you know check check the password ignoring how I find the the the record I want based on the username right we'll cover that uh in two weeks or next week uh in in lectures eight and nine right there's some index data structure that's going to give me a record ID for a given username then now with that record ID I go to the page directory it tells me what page my data is in I then look in the header find the the the slot offset find the slot AR slot entry that has the offset I want I jump there M Copy everything out and I'm
18:03 done all right if I want to do an insert again that's easy to do look at my page directory it tells me where a page has empty empty slot and I just jump that off set and just write all my bits
18:18 out right this is easy or this is perfect for a rose store but if I run now my analytical query on this now you see why this is going be problematic so in this case here my wear Clause says we're host name like uh you know uh
18:53 wildcard.com so what do I need to do I need to scan through uh the slot array find all the offsets for the tupal that are in the in the page jump to each offset then then jump to the offset within that tupal of where the host name starts then do my do my evaluate my predicate my wear Clause then jump to the next one and repeat it and that's just for the wear Clause now for all the tles that match I want to run my aggregate so now I need to look at the last
19:24 login uh entry and comp you know extract out the month and compute uh an aggregation on that ignoring we'll ignore how we we'll compute the aggregation that's that's in a few weeks but let's assume there's a hasht while maintaining in memory that I'm I'm updating this counter right it's pretty simple right but now what what do I need to access I need to access all of these these attributes over here now I can do this as I'm while I'm accessing the host name like I'll check the host name if it matches then I'll do the aggregation
19:51 portion so I don't have to loop back a second time but I'm still have to you know still going through each Tu of one by one and jump into these offsets so what's the big problem with this approach for this
20:06 query I got this big block of data here for these three attributes and I didn't need them for this query but because all the attributes and Nary storage are packed together all the the values for tup are packed together they come along for the ride when I go fetch this page
20:22 right because again it's block oriented storage I got to go get the entire database page bring it in memory even though there's a bunch of data in it I don't I don't actually need for this query so this is one of the key problems we're going to have with uh with a rast store when we want analytics because it's G to be all this useless
20:41 IO so NSM the the the rore the advantage is going to be it's really great for for inserts updates and deletes anytime I'm updating a small amount of data this is fantastic because it's going to be one page right uh and and I'm done it's great for queries I need to get the entire tubal and he select star query uh which you shouldn't write anyway but like there's a lot of them uh then all my data will be right right together and then we can use other techniques like index or storage to you know do keep everything in sorted order so the physical layout of the data is actually good for queries as well but as I showed that it's going to be bad for scanning large portions of a table uh especially when I only need to subset of the attributes if I have to look at all the attributes and all the data uh so for all the attb for all the tup com store will help for certain things but you know in the end day you got to read everything so but if I'm most of the queries are going to do a
21:35 subset as we showed before I'm jumping around to different offsets in memory and that's going to suck from a CPU perspective because now you have a bunch of branching uh and that you know in in Direction that's going to make things slower and then what we'll cover later in this this class will be we're not not going to be able to compress this data very well because we have a bunch of uh attributes with different value domains
21:57 that are all be intermixed and that's not going to be ideal for uh a compression scheme I'll explain what that is in a second so any questions so far like why R stores are bad for analytics it's pretty obvious once you see
22:12 it so the alternative is going to be the decomposition storage model or DSM and this is what you would DSM is the sort of academic term but everyone just refers to these as column Stores um and there is a exact DSM definition and most column stores going to be using the Pax model which will'll cover in a second but they're Loosely you know at a high level they're basically the same so the DSM is basically instead of storing all the attributes together uh for a given
22:38 Tuple uh you know continuously in in a page we're going to store all the values for All tuples For One attribute continuously in a page right so instead of having the host name followed by the last login I'll sore all the host names for all the tupal together contiguously and then have another set of pages that for all the the last login attributes for all the tuples together in a
23:03 page so again the relational model gives us that physical logical and physical data Independence where logically I'm defining a table uh as a bu of attributes and columns but I'm not specifying how I'm physically storing it so the database system if it's a column store can say okay well I'm a column store system you told me it's that their table wants to be you know has these columns but I'm going to split them up and store them in separate locations and then when your query comes back and says you know give me all those ATT back I'm going to stitch the two back together to make it look as if it was always stored
23:33 together right and we hide that entirely from from from the application so if we go back to our simple example here uh for the first column on column A that'll just be stored in in a separate page or set of pages all the values for column a right and there'll be a header that says here's what column here's what's in this page here's some you know check sums or whatever else you want to store there'll be a null bit map that's stood at the header as well that's for all the
24:01 tupal uh uh sorry yeah for all the values of for all the tupal so instead of having a separate bit map header per tupal now it's on a per column basis but I know what offset in my bit map correspond to what offset in value and what T that corresponds to what logical tup that corresponds to and then I had the same thing for for the other two columns here and again I'm showing these as one page you can imagine this be could be multiple pages
24:31 so if I go back to our our query before so this is what our original page looked like under the rastore model right we we had a bunch of tubil we had a header at the beginning of the tubal and then we had all the attributes and then once we have to get the last attribute then the next tupal starts so now what I'm going do is split this up based on columns and store these now all in in separate
24:51 pages right so there'll be a user ID page or Pages username last log and so forth then here I have the host name page and again we have a header tells me some metadata about what's in this page column it corresponds to some check some information or compression information and then I just have all the host name values so now when I run that same query we had before was the first step is to evaluate the wear Clause uh and so I only the wear Claus is only accessing the host name so I only need to access this one page again assuming everything fits in one page I go access this host name I start at the beginning and now I just rip through this and apply my my wear Clause to find the thing I'm looking
25:30 for so what you're going to end up with now is a bunch of matching offsets right just saying here here's the TU that that were the value evaluated to true for this predicate so I keep track of those offsets which we'll cover in a few weeks and then now when I want to then evaluate the the aggregation I just bring in the last login page because that's again that's the only column I need and then now I know where the offsets were from that matched to the host name I know those are the the those are the last Logans I want want to consider in my my
26:02 aggregation so again this simple example where there there's only six pages in the database I went from in a rower having to read all the pages to now only having to read uh two of them or a third of it and if you assume that again always think in in really large scales I have billions of pages or pedabytes of data
26:23 and either the disc is really slow and it takes a long time or I'm paying for the access to dis like if you're running in the cloud you pay you know pay Amazon every time you look something up an S3
26:32 then this is a huge win so not only my queries run faster they're going to run cheaper as well so is this clear so this seems like a no-brainer idea now actually who here has heard of column stores before this class less than okay barely 5% 10% right this seems obvious though right that like of course if you're doing an analytics you want to sort like this the idea is actually really old it goes back back to the 1970s but it was in this obscure Swedish military tech report uh for like a file system this system called caner that nobody paid attention to and then that DSM paper I showed you before that came out in like
27:11 1984 um and it wasn't really till like the 2000s when people said oh yeah this is actually a really good idea we should we should store analytical data analytical data as column stores so it took a while for this idea to come along and now it's just it's common place and it's used everywhere right because again the winds are so big
27:30 all right so I was kind of hand wav you back here right when I said we run our wear Clause we find our matches and then now when we bring in the last login we have a way to to know where the corresponding matches are in the host name to match the corresponding matches in or the values we care about in the last login page so how are we doing
27:51 that so there's basically two approaches one is that we just use fixed length offsets for all the values within a column and we just know that logically the Tuple at you know Tuple one is that offset one at each of these columns and because the values with each column will always be fixed length like there'll always be 32-bit integers or 64 bit integers or whatever then we know how to do that simple arithmetic to go find the the offset that we want to get the value we need for a given tupal we care
28:24 about that this is the most common approach and pretty much everyone does this in the early days of Comm stores about the the mid 2000s it was still kind of up the air how to do this and the alternative approach was basically to store a tuple ID with every single value within a column and then have some additional data structure that says if you want if you want attribute or S if you want Tuple one here's how to jump it into the that offset in the different Columns of different
28:51 types right there was a system I want to say is data was data algro which was bought by Microsoft that was basically contorting A rad store system to make it look like a com store like this Microsoft paid I I think pretty sure it was Data Lego that did this but even so when Microsoft paid $200 million for data legro within three months they realized the code was garbage and they threw it all away um and that was actually J's adviser told him to do that
29:17 um anyway so I got put put this Mark up here don't do this right but I wanted to tell you you could do it this way this is going to be the most common approach using fix allets how do you hand variable question is how do you handle Vari length next slide yes absolutely yes all right so integers floats dates they're all fix length that's fine how do you handle the bar chars the texts and the blobs right
29:45 so the way this you basically do this is that you want to convert everything into fixed length and the way we're going to do that for varchars is to use basically dictionary en coding all right if you're very familiar with compression algorithms basically doing some VAR dictionary coding you're taking a arbitrary string and instead storing that string in the column you're going to store a a a number an integer a dictionary code that maps to that that that string so I have a separate data structure that keeps all my strings and and the mapping from codes to to the actual original values and then in my columns I'm just going to store the the the the integers and now everything's fixed length and we're all
30:29 happy and in some some file formats like think uh I always get this wrong this park and orc talk about in a second one of them does dictionary en coding for everything no matter what the data actually is so everything ends up being 3 bit integers in the columns or 64-bit integers uh and then one of them only does it for the
30:48 strings right so that solves that problem because because now we just do the simple arithmetic and uh because we know it's going to be 32 bit energer codes we just jump to whatever allet we want to find the data we need
30:59 we'll cover that more in in a second all right so in the in the DSM the column store it reduces the amount of IO uh for for queries that only need access a subset of the attributes of a of a table because we're only reading the data we we actually need we're not bringing in things because it comes along for the ride we're only reading exactly what we
31:22 want it's also going to let us ex queries more faster is because because we not jumping around to different offsets in memory uh we basically can access strides of memory uh sequentially and that's the best thing for a modern super scaler CPU
31:39 right the Intel x86 wants you to execute a bunch of instructions one after another and not have branching not have jumps so I can if I build my system correctly which we'll cover in a second or cover in a few weeks I can rip through that that column store and not have any indirections or or or branches because I'm just going through exactly like value after value after value and doing the same operation running the same wear claws over and over again and that's the best thing for for modern
32:06 CPUs and then we'll talk about later in the in the this lecture we can get better compression because now the the value domain for a bunch of data that's contiguous in a column store is all going to be the same it's going to be all bunch of zip codes that are going to be integers and I I can compress those very very well
32:22 yes data compression breaks the offsets okay this question is does data compression break the allets you mean if you run like gzip or zip or Snappy when when you say compression what do you mean well we're going to cover this in a second but like it'll make it clear like so if you if you so yes if you just take like Snappy or gzip or whatever your favorite compression algorithm off the shelf yeah absolutely we're not going to do that we're the database we we do it
32:54 ourselves okay we'll come back to that all right what's the obious downside of this well again it's if I my reads are going faster what's going to get slower any any update operations any wres because now I have to take for an insert that shows up I got to then split it up a bunch of attributes and write it off to a bunch of different locations so I have a thousand attributes in my table I got to write out a thousand Pages for inserting one one Tuple that
33:20 sucks so Pax will will will solve that uh problem a little bit but in some systems what they actually do is that the have basically what looks like a log structured system as a as a as a rip buffer that you do all your insert ups and deletes into and that's basically a row store then in the background instead of compacting it like we talked about before uh where you're making SS tables and so forth the the compaction part is really installing it into the column store and you do that you do that in the
33:49 background right some systems like Oracle they'll have the row store that you normally would have in regular Oracle that does all your OTP is a row store really fast and then they actually make a separate copy of the database in memory that's actually in a column store
34:04 so when a query shows up they say oh you want to do analytics and it's the data you want is actually in in the inmemory column store I'll route your query to that and so you don't change any the application you don't say I want to go to the row store or the column store the database system figures that out for you and hides it underneath the covers and you get all the benefits of a column store but still have fast
34:23 LP right so there's different bunch of different ways to to to to introduce the idea of column storage into a database system some systems are dedicated entirely to be a column storage some systems have it as a sort of supplemental storage or additional
34:40 storage okay so column stores are great sort of pure column stor is great if you only access say one one column um but it's that is pretty rare most the times you want to access a couple columns not all the columns right I think postc lets you have 16,000 columns per table um it's a hardcoded limit in the code uh Oracle famously has a has a thousand column limit um the reason why is because it used to be 100 because somebody hardcoded that in in the 90s
35:14 and in the early 2000s somebody said well that's dumb let's make it let's make it bigger so they changed it to a thousand and they had they had mainly changed a Cod uh and was such a pain that they they they told me they never want to change it again uh you think they would have made it something big than a thousand when when they did all the retrofitting but I they didn't know why the person did it that way anyway so most of the queries are going to access some subset of the columns and so if now we're a pure column Store everything's in completely separate pages then yes we're going to have to go fetch all those pages uh and you know that we need and bringing them
35:48 in so what we really want is as I said almost a hybrid approach where we are getting the benefits of a column story where things are now the attributes for a column are sorted continuously across for multiple tupal but they're still physically close to each other such that I can bring pages in and yes may maybe getting some data that I don't actually need but it's not as bad as as a as a pure roast
36:14 store so this is what the Pax model does uh Pax and sort partition attributes across um this was the paper claims or the author of this paper used to be the datab professor at CMU before I started when she left went to epfl uh the reason I'm here is because she left and went to Switzerland she's brilliant but this was the the last chapter of her of her PhD thesis uh at Wisconsin uh and her her PhD advisor was also G's PhD advisor but this basic idea here is that we're going to have instead of within a sort of a table we'll have these sort of mini blocks or larger blocks I don't ter block they're called Rog are larger regions of data where within that will store things as uh as as columns but the the data within for a single Tuple will still be relatively close to each
37:05 other this's make more second more sense in a second right the idea is that we want the we want to get the benefit of a column store but still get the benefit of spatial locality that the data for a single T pool are is close to each
37:17 other and so I was saying before most systems they say they're a column store they're really going to be doing this or if you use these open source file formats like paret orc and arrow they're going to be doing packs and sometimes you'll see it in their literature that they refer to it as
37:32 packs so what we're going to do is we're going to horizontally partition the the tupes into to row groups I think par calls them row groups or call them something else uh but it's basically some some some number of of of of tupal and then within the tupal in the row group now we're going to vertically partition them into column chunks so that say we have a a Pax file here and this is say this is model off of something like Park and orc and so
38:03 important thing to understand that Park and orc are read only file immutable file formats meaning like I write it once and I never go back and update it so the way it works is that there isn't a header for the metadata it's always going to be in the footer because as I'm creating all my my row goups to fill up the file I keep track of what I'm putting into it and then when the file's done when you finish it off you put all the things you've collected into to the header sorry the footer so if you want to open up one of these files you look in the footer first and that tells you what's be up above right whereas like in
38:31 postgress systems we talked about it's always going to be in the header because they're dynamically updating these things all right so we now uh take the we take the first three tupal in this table and we're going to combine them to be in our row group and every row row group is going to have metadata like the header from from the page it's going to tell us what's in it and then within this row group we're going to write out all the data for the First Column and then we're done then write out all the data for the second column and then so forth to all the TU all right or sorry all the columns and then we're done and then now we're just going to do the same kind of partitioning for the the next three tbal and that's going to be stored as a separate row
39:09 group so the row group size is going to be different than what we typically think about in in a in you know the some multiple of 4K 8K like the pages we saw before right again these are immutable files that going to be used for analytics so the row group is going to be quite large I think the default in uh par is 128 megabytes orc is going to be a million tupes no matter what the size is always it's always a million tupes
39:34 right but the idea is that if I'm going out to S3 and going getting this this uh going get a row group I can do you know 8 megabyte chunk reads from S3 and I get this whole thing and then all the data that I need for any one tupo is going to be
39:49 there so you can actually see the this a presentation from datab bricks the internal organization of a of a of of a parquet file and again there's the row groups there's column chunks and then there's the pages themselves and the default can be one megab Pages because again you're doing analytics you don't want to read single Pages at a time that's four kilobytes or 8 kilobytes you want to read large strides of data because you want to bring those into memory and rip through
40:14 them okay so again it's like the PX is basically saying I have some data that's uh it's is as a column store but the the values for the same T are going to be close to each other and you can say oh is 120 Meg by is that you close I mean modern in modern systems yes it's not going to fit in L3 is not true anymore uh AMD will sell you a CPU that has like 800 G or 800 megabytes of L3 cache which is insane um but like still it's it's it's it's much bigger than uh than you know 4 48
40:52 Kobes all right so if we say that iio is the main bottleneck for and I did was system we the read data from disk you know whether it's a local disc or S3 um then we need a way
41:03 to and column store is going to allow us to reduce the amount of useless IO that we're doing right so we've already say we a pure com store we've already got it down to be just bringing in fetching from disk the bare minimum we need to actually execute the query so how can we make this thing go faster if we're already retrieving the minimum amount of data we need well what we want to do now is for the data we do have to read from disk let's increase the amount of useful information or number of Tu we're getting from any any IO that we're
41:31 incurring and this is where compression is going to help us so think of like if an uncompressed page I can read 10 tupal a compressed page will allow me to read 20 tupal inside of it and the classic trade-off is going to be uh you know compute versus storage or compute or speed versus compression ratio right I can have a very very aggressive compression rate uh scheme and that that's going to be reduced the the storage size quite a lot but now when I want to go read the data direct to my query I got to unpack it and that's going to be really
42:03 expensive right think of like a uh you know modern video Codec they get great compression ratios they they get really small file sizes and you can you know barely notice the difference uh but it requires you know Modern Hardware to decode them versus like you know MP3s from the 1990s right that's that's pretty simple
42:23 now so we're willing to make the tradeoff in some cases depending on our environment and our workload that yes we'll pay a higher CPU cost to execute queries but that's offset by the reduction of the of reading less data from physically in disk right and in some cases we'll see that we actually can operate directly on compressed data without having to decompress it and again it's why we want the datab system do this all this for us so we have three goals for a de compression scheme in our datab system the first one is the the question he brought up is well if I'm saying in order to have these these fixed length allets in my my my columns to be able to jump the two BS very quickly if I start bringing in compression doesn't that break all that
43:03 well again if you're using off-the-shelf compression scheme yes but we're going to implement compression ourselves inside inside the system in some cases we actually want to postpone or delay uh actually decompressing data for as long as possible as we execute queries right if I if I have a billion tupal that's all compressed and I I I'm doing a look up and I want to find one tupal right there's there's you know like a needle and Hast stack problem I want to be able to rip through that that a billion tupal keeping it keeping it compressed find the one thing that I want then decompress that one one tupal
43:38 versus like decompressing the 1 billion tupes just to find the one thing all right this technique is be known as late materialization uh we can do this for other things like if we if if it's a if if it's a column store uh we don't want to have to go Stitch the two together at the very beginning uh if we if we know that we can throw away a lot of data so we'll keep everything keep you process that one column and only get the other columns until later up in the query plan we'll cover that more in a few weeks but the idea is again just you want to delay as much as possible doing useless work or doing un
44:14 avoid doing unnecessary work the last one is that should it be obvious that we want to be doing what is called a lossless compression scheme what does that mean in the Contex databases you don't lose data right so if I compress data and then I decompress it I should get the exact same data exact same bits right and the reason why obvious that you don't want to use a lossess scheme something like MP3 or MP4 where you you you are taking advantage of how humans perceive music and and and and videos where you can throw away a bunch of bits things you don't need about because humans AR going to detect it
44:52 when it comes to data in a database people will notice if you know the bank account has the wrong number or money goes missing right so we don't want to be doing uh a lossy scheme any lossy compression you want to do has to be done by controlled by a human so think of like if I have a application that's storing the temperature in this room every second
45:13 and so I let this application run for a year so I have a Year's worth of data of what the temperature is for this room at 1 second granularity do I'm really going to care about maybe again that that exact 1 second granularity for you know a year from now what the temperatures right now no maybe I could aggregate it together into 1 minute or 10 minute chunks so I have the rough average what the temperature was within 10 minutes but I don't I don't have exact values anymore that's an example of a lossy scheme and that's not something you want the databases will do it for you if you ask them but it's not something they'll they'll just do
45:47 automatically all right so there's different gr lar to what we can we can compress we're going to focus on the the first one and the and the last one the uh the these two are are they exist but less common like acate level compression would be like in if I have an overflow page in like in postgress I can compress the Overflow page for that one value with that single attribute um but like for talk about today you know that kind of stuff is we're not going to you can't really anything specialized with that so we're talk about Block Level compression
46:20 and and Comm level compression and we use Block Level compression as the straw band to see uh again not the pick on you like to bring up his example what would what you can do with this and then why it's not going to allow us to do everything you know achieve all the goals we showed in the last slide of uh you know doing the late materialization and trying to keep things compressed as long as possible whereas the column level compression will be implemented by the datab system and we'll we'll get the best performance for
46:45 it so I'll say also too uh Block Level compression will be more common in oldp systems and row stores and we'll see how my seal does it in a second Tu level compression can be done in in Seal server and then there was a system called tarch which was a fork a Rox DB that
47:04 uh uh who the the Tik Tok people bought what's Tik Tok bite dance yeah so bite dance bought that company but they they could do two level compression for lsms um for attribute level compression we talked about postgress and in the toast stuff um but pretty much every column store system every every system that's doing packs is going to be doing uh some type of col Lal compression and like the park and and orc formats give you
47:28 that so let's look at a naive compression scheme based on blocks and so it's pretty pretty easy we have a block we have a page we want to write out the dis we'll just run it through your favorite compression algorithm before we write it out so it's sit own dis in compressed
47:44 form uh you can use lzo lz4 the the the snappy is is is a modern variant from Google based on lz4 Z standard is what's considered the stateof theart now from from Facebook um I think it's from the same guy that wrote XX has but this is if you're using compression scheme uh you want to use Z standard it's considered the best right now it's the best like tradeoff between like performance and compression ratio
48:09 and then Oracle has their own proprietary thing which I think they still use called OIP um because because they patent everything um so again trade offs just look before we're going to care about what's the cost of decompressing and compressing um and then what's the overhead of you the storage base but we also need care about now how we're when we're acting depress things and how does that fit into our buffer pool because as he was saying now our Pages might be different sizes and not going to fit easily into that scheme we talked about before where everything has to be always the same page
48:41 size this is how so this is how my seal does it so if you have a compressed page um it's going to be of of four possible sizes either one two four 8 kilobytes and if you're if you're less than whatever the next one up they just Pat it out so if you're like 3.8 kilobytes they'll pad you out with with a bunch of zeros to make you be four kilobytes that allows them to do again use fixed length all sets to jump to the different pages that you
49:07 need and then they're also going to have this this mod log space at the at the header of the page that they can use to absorb rights without having to decompress things so again this idea of log structure storage is showing up a bunch of different places and this is another example of it it's basically that log structure thing we talked about before where here's all the the puts and deletes that I've made to things that are in the page
49:28 so now if I have a read query that comes along and wants to access this page uh sorry say say do a write query so on to write to this page if it's a say an insert then I can just put the entry into the mod log without decompressing it and then doing the
49:44 insert right if it's a read followed by a write if I'm updating you know someone's bank account adding one to it then yeah I got to go read it decompress it and then do the update but if it's if it's a blind right I can just do the update directly to it
49:58 and then now if someone come along and wants to read it if the read could be handled by the mod log like if I insert Tuple Fu and then someone reads looks and wants to read tup Fu if I can find EX the answer I want my mod log I keep it compressed but if I need to access something that's that's not in the mod log or I have to derive something that's that can't be computed from the mod log
50:18 then I have to decompress it and then now it'll expand out into the standard 16 kilobyte page that that my SQL has and it and then at that point they're basically just replaying the mod log and applying the changes into the page so that when it gets gets written out we'll compress it back up the mod log becomes empty and then I write it back out to dis in that
50:39 form all right is this a good idea or a bad idea raise your hand think is a good idea nobody raise your hand think is a bad idea why what if it's right heavy he says what if it's right heavy
51:05 uh what what do you write much inserts yeah the will be and we have to constantly P modif LS the comp page right so he says if it's uh if it's bunch of inserts then you're going to keep just pend into the mod log and and it explodes up right but you could be clever about it and say okay well I'll
51:27 um I uh when I create a new page I'm it's going to be uncompressed so I'll just insert into the page as it was before and don't pay the overhead of of updating mod log I don't know what my SQL does but they might be doing
51:41 that anybody else why it's a bad idea I actually think it's a good idea right uh my post can't do this right uh my dis guys is smaller the the data I'm fetching in is is now smaller uh I'm getting more you know more bang for the buck I'm getting more tupal for every for every IO that I'm doing right
52:05 uh this is a good idea uh again there's extreme cases where if it's like if it's you know read file by WR or right file by read like where I'm just compressing decompressing over again yeah that'll suck but in general uh most workloads are going to be read heavy even even in rore and if I can answer them using uh compress data then fantastic and again there's there be some metadata in the header that says like how many tbos are active inside this so if I if I just want to select count star of getting the number tbes in a in a in a in a table I can in theory just read that out from the the header
52:41 and not have to decompress it so it's not great though obviously for uh for doing you know the late materialization we want to do because I I uh in order to read anything inside it I always have to decompress it potentially right and the the compression ratio is not going to be that great either because it's a it's a row store so all the values within it are going to be from different domains right there's different attributes zip codes phone numbers email addresses
53:12 right the compression algorithm that really you know the best case for compression algorithm is like a bunch of zeros right because K says all right have have a zero followed by you know 10 you know a billion times that you can compress that really really well if it's a bunch of random data like random bits that that that won't compress as well right if you try to take a movie file and run it through zip it's not going to compress it at all or
53:33 barely right and then as I said before the data system can't derive any meaning about what's actually in the data ignoring the mod log piece because it doesn't understand what the compression algorithm did to the data right if I run Snappy or Z standard they're doing some variant of dictionary en coding but the the data Cent doesn't know how to interpret what the dictionary en coding the the dictionary that that was generated by that that compression algorithm it's considered an opaque
54:00 box so we again as I said before what we really want to be able to do is have the D operate directly on compressed data without decompressing it because it's in charge of the compressing yet and it knows how it compressed it and knows how to extract information that it needs in some cases right so I save a really simple table it has a name and a salary
54:19 I run it through some compression a not saying what it is right but say it's some variant of dictionary compression and I've converted all the names into to uh and salaries into simple two character uh strings so if my query shows up select star from users were name equals Andy ignoring indexes right to assume I have the sequential scan I do some kind of databased magic not saying what it is yet and I convert the string input string to Andy into the same code that I used to represent it here and then now my query is basically doing a name look up where you know query name equals xx
54:53 and I know XX corresponds to Andy because I did that mapping and go find exactly the data that I need so I didn't have to decompress these other tupal to to find my match I just operated the the query directly on the compressed
55:05 data so this is what we're going to want to do in a column Source system if we control everything if we control how things are being oppressed and not let you know some third party Library do it for
55:16 us but this is only going to work again at the column level because now we're going to have all the values for for a given attribute are just one after after another which are typically always going to be in the same
55:28 domain right Json breaks all that but we can ignore that all right so I'm going to do a quick run through of the most common compression schemes uh and they might have slightly different names I'm try to cover them for different systems might call them different things but these are all going to be uh con to compression schemes that the DAT can employ and be aware of in its execution engine when it runs queries to know how to access the data without decompressing
55:55 it so again some of these you might have covered in other classes but we'll see how we can do this in the context of databases so uh one of the common ones is called run length encoding the idea here is that if we see the same value repeated one after another in in a column instead of just repeating that value over and over again we'll just store the value once store what offset we are with within our column and then store the number of times that values appears right we basically convert it to a to a
56:24 triplet we can get a a huge win for this if we sort our our if we sort our table based on on on the column we want if the the table sorted based on the uh the column want do run length and coding on because now we could have all the values that are you know with this all the TBL the same value appear in the same location sorting is kind of tricky because again now I need to make sure that my offsets all match so if I sort
56:48 if I sort my table I have two columns I have to sort it uh the First Column you know the and then come up with the new offsets and then I have to make sure sure that the the second column there also get moved around as well so what might be the best sort sorting uh what might be the best way to get the best compression scheme is to sort this column first might actually be the worst way for sorting the other column so datab systems have ways to to try to figure out how to sort things the best but we we'll we'll ignore that so say a real simple table has eight tupes it has some ID like a person ID or something
57:20 and then there's a flag that says whether someone's dead or not right we're ignoring nulls you're either dead or not dead yes or no right but you can see here it's it's intermixed with the different values so in some cases I do have some repetition so I'll just convert those into what the value was what the offset is and what the length
57:41 is right in this case here it's yes or no it's Boolean 01 if I have larger values I could basically store that as an enum and say and just map them to 01 so that in in my my rle encoded pieces or the triplets I'm just storing what the enum value is but for Simplicity you ignore
57:59 that right so in this case here we're actually not getting a huge win uh because these triplets are actually larger than uh what the original original data was because again as I said they're intermixed but now for but a query like this like you know count the number of people that are dead and group I whether they're dead or not I can just rip through the compressed data
58:20 and just count up the number of times the the repeated values and that'll produce my answer real quickly I can get better compression though if I sort it um right because that'll avoid these issues where like it's it flips back from the you know not dead dead not dead if I sort them then all the dead people go first followed by the the non-dead people and then now my compressed data only has two entries two Triplets of just the dead people and the Not Dead people and then the number of times they each
58:50 appear so think of like again in other columns like keeping track of the sex people right it's a small number of values if I sort based on that then I can represent a billion people with just a small number of triplets that's a huge huge reduction in
59:06 size and we'll see how rle can be used in other compression schemes uh like you compress data once and then you compress it again with rle and you get uh you know even bigger win the next compression schem is called bit packing uh some I think it's called bit shaving sometimes in on systems but the basic idea here is that if you recognize that all the values within a column are much smaller than what the max value could actually be then you don't need to
59:35 store a bunch of bits for you know unused data within each within each value right this is very common right so people say you know when you declare your table you know are these attributes are Define as an INT well that's a four byte integer but if all my values are are less than 16 16 bits I don't need to store the all those extra extra empty bits because they're nothing but a bunch of zeros right so say a bunch of values like this again it's a 30 bit integer
1:00:02 but all the values are really small less than than 200 then the the total size is 26 bits but the all this data here I don't need so if I if I can recognize this then I do bit packing where I just store the the the the significant bits that actually matter that distinguish one value to the next and I can press it down significantly so I went from 2 bits to 64 bits to store this
1:00:28 data and you just do bit shifting to put it back in the right form when it comes time to do whatever operation you need yes going back to the prev ring um if we store different column like assum AUM store and we store different colum differ does that mean that if we want to get
1:00:51 one have to ID so the question is if I'm if I'm doing um if I'm doing rle for example on different columns then how do I Stitch the original tool back together you'd have to go through and and use the triplet to decide okay if I if I materialize this if I expanded it out the 2x want would be would be at what Offset you basically again Tre treating the r as a log to say here's I got to go back to the original form but you want to you want to avoid having to again materialize all the empty extra bits
1:01:24 unnecessarily okay the next scheme is uh or one problem with with with the bit packing is that you can have outliers uh and so you have to use a technique called patching uh in in Amazon red shift they call this mostly encoding it's basically bit packing but when you H when you recognize there's there's some some tup that have a value that doesn't fit in your bit pack your bit pack version you basically put a little marker in it and like a special bit sequence and say okay well the the the value for this two this offset it's actually not really here you got to go jump to this auxiliary table to go find it so you could rip through the column
1:02:08 uh do your processing throw you know ignore any of the uh any of the outlier values and then just go back and get the original value that you need the larger value so you get you still get the win of uh bit packing but you can handle the outliers so this example here again the original data was 26 bits
1:02:26 but with the the bit pack scheme plus the the table to keep track of the um the outlier it's 122 bits I'm showing toy examples here but again thinking in terms of billions billions of tbos next technique is do bitmap en coding and the idea here is that instead of storing the the values over and over again within a column I'll maintain a separate bit map for each possible value that that could occur and just have a one or a zero based on whether that t that offset is set to that particular
1:03:00 value right so again if I have the is dead uh column here that instead of storing again yes no over and over again I can just have a bit map for all the yeses a bit map for all the Nos and then I just know how to jump to the offset that I want to determine what the actual value
1:03:17 is right so again the original data was 64 bits but with the bit map we can get it down to 16 bit 16 bits when this when does this not work when the when the cality is high I have a lot of values have a lot a lot of bit Maps right so if you look at a toy example like I have a table of of customers and there's there's a a zip code attribute there's about 43,000 ZIP codes in United States so if I'm using bit map en coding I would have to have a bit map a separate bit map for every single possible zip code and if I have 10 million tupal then those bit maps are going to be 10 million you have 10 million bits in them so the original data just to store 10 million 30-bit integers is 40 megabytes but to store uh
1:04:04 43,000 ZIP uh bit Maps uh for 10 million entries is 53 gigabytes so in some cases this actually would be a terrible idea right the other problem with bitmap encoding too is every time I insert a new Tuple I got to make sure that I I pen it to the end otherwise I have to go you know inject it in the middle and then move all the bits down and that could be expensive
1:04:27 now this is a gross generalization no system should not store you know store bit maps in this way just roll bits there's actually compressed bit maps that are really useful for Spar sparse data sets called and the most popular one is called roaring bit Maps um it's basically like you you only expand out the bit map and have the true bits uh or keep track of the bits for when you have a lot of data within a region I think like sort of doing Lazy expansion of the bit map but run bit maps are used in a a lot of systems uh in today and it's uh it's actually be used in Pino which is what star tree is is going to be based on we'll talk about in a
1:05:07 second all right let me through these these last ones to make sure you understand that and then I want to talk about dictionary en coding is the most important one Delta encoding is basically keeping track of some uh some starting point and identifying that all the values that appear after that one particular value are just small increments or decrements of that so instead of throwing the value the whole the absolute values over again I just say how much am I different from the one value that that appeared before me or some starting point so if I'm keeping track of of temperatures at different times at different minute offsets right the time is always going to increment by one minute and the and then the temperature is not going to widely fluctuate massively within you know one minute right the it's not going to go from 99 degrees to0 degrees in a minute
1:05:51 least most cases so in this case here I use this as my starting point the the first entry and then all the data that comes after are just uh plus or minus from the previous value right so I can compress this even further with rle because what do I have here I have a bunch of plus ones repeated over and over again right so I can take this column after I've Delta uncoded it and then just run r on it and compress it even further and the DAT system keeps track of this all for you underneath the covers to recognize I know what the encoding scheme is for this data and how to unpack it uh if need be
1:06:27 so in this example here again I went from 320 bits for the original data just for this column here down to 96 bits so in this example here the Delta en coding is always mean that the increment from the the previous entry there's another one technique that's similar called frame of reference encoding it's basically saying that there's some Global value that I have within the column and then all the values within the column are just are the Delta from that so my point here is like it's the starting point and then everyone's a Delta before but I could use this as the starting point and then and then this would be plus one plus 2 plus 3 plus 4
1:07:00 right but it's the basic same basic idea all right the last one real quickly is dictionary en coding uh I probably should start with this first because it's the most common one um but but most of you should have countered this in in other CS classes but the basic idea here is I want to replace frequently occurring values with some integer code that I can use represent it and I'll have maintain this dictionary this mapping table that says for that dictionary code code here's what the original value
1:07:27 is in most systems actually nearly all systems it's going to be a single attribute will have a single value meaning they don't look at if I have uh value a followed by value B in in two continuous tubes I can convert that to a single dictionary code that represent those two tbil it's usually going to be one value Maps uh one Code maps to one value and we need a dictionary scheme that can can decode and encode quickly for us and ideally we want to expose that to the rest of the system so that for some queries we can operate directly on the dictionary and never have to actually look at at the compressed
1:08:01 data so let's say we have a simple table a bunch of names again all we're going to do is replace these VAR length data in in this field here this in this column with these dictionary codes uh and in this case here I've also sorted the dictionary based on the values for themselves so now the the the values going to have the same Le graphical ordering as the soorry the dictionary codes have the same graphic ordering as the original data and the reason why I want to do this because there's a bunch of tricks I can do to run queries more efficiently if I know that you know Andy appears before jigesh therefore I would know that the value of of Andy the dictionary code Andy 20 should appear before 30 so I again don't have to go back and decompress things in order to figure out what's going
1:08:49 on so for queries like this select star from table where name Like A and D well since I'm to do the wear Clause I'm only operating on on name ignoring this the star part of it um I can just convert this into a between Clause between 10 and 20 because again my dictionary codes follow the same ordering as the uh as the original data so now I can actually this query by just looking at the at the dictionary table and never actually even go back to the original original data so if I have a billion tupal but only 100 dictionary codes and my query can be answered directly on the dictionary I just I don't have to read 1 billion
1:09:28 tupal yes where's this actually question is where's the dictionary stored it' be in the header of of of the pages or we like in in case of par we saw the row groups it goes in there so there's other so some queries again you can you can uh in this case here if I actually have to get the original value back I got to go in the columns but if it's like give me all the distinct names in this case here I can just do that directly on the dictionary
1:09:56 yes how do we make sure like say we do the match a and d uh exactly mat code from 10 to 20 not like going back here so question is how do I how do I convert this named like a andd into between 10 and 20 yeah how do you like specify the R so so the user want to specify the DAV is basically writing this for us the way it works is that I know that this is the dictionary for this for this column so let me just run the where A and D where sorry where name like a and d and I go through the values here they're in sorted order and I stop when when I find something doesn't match uh like if I get to jig NES then I know that nothing after that could ever match my wear claw
1:10:40 so now I know it should just be between 10 and 20 so I basically scan do a sequential scan of the dictionary find the matches for my starting point and then my end point and because it's sorted we can exploit that
1:10:57 okay um to finish up all right the main takeway from this class should be there's this distinction and there's pros and columns between a row store and column stores and then if you're doing anal system you want to you basically want to be in a column store but it's typically going to be stored as as a under the Pax model um in the early 2000s mid 2000s there were people try to contort row store systems into column stores and do a bunch of store extra data structur to try to make it look like a column store at the end of the day like all that went away and everybody wants to do you you want a system that operates directly on you know columnar data and we saw that because we're staring things in columns all the values are going to be the same or the domains going to
1:11:36 be much smaller for a single column than than than intermixing rows uh that there's a bunch of compression tees we can do uh to get to improve the storage size improve query performance and in some cases we don't have to De decompress things to to answer
1:11:54 queries all right right so this this finishes off the lecture for the uh for storage how to repr things on disk when we start now on Monday next week we then talk about okay when I have these pages in disk I bring in the memory what does that look like how do I manage that and how do I control that again and that was that's what project one will be based on okay
2. Jump to
1:12:17 uh my my name is Sean uh I'm a PMC and committer of a pat p project as well as co-founder of star Tre which is like the company uh trying to wrap up uh apino for assess uh solution so for this talk I'm just trying to uh start with like all the apino like technical things and
1:12:40 why we build it and uh some uh just like high high level architecture uh kind of things so no not really share I should [Music] yeah okay so but for this talk I'm just talking about three things first thing is like what we're doing we're doing uh the real time olab so real time uh so olab is for uh online uh uh analytics um platform it's not really like the traditional transactional databases it's more on the uh analytical workload so the differences here is like for all the queries uh what we want want to solve is like for a big kind of data scanning and your quy is always like probably touch every row of your uh database that's uh the typical workload for analytical uh analytical things uh that that is very different from the workload or the query pattern of the transaction
1:13:44 databases so here we are having some use cases like user facing analy at LinkedIn for example if you open LinkedIn you you will see this H in my profile and all those things start being like like uh computed for like all your viewing history for like past like couple months all those kind things so all all those kind queries are like serving directly from Pat Pino and we're also trying to like keep up all the fresh freshness
1:14:11 data uh similarly uh we will get uh use cases like uh the yeah one more thing was mentioning here is like the query QPS is actually very high it we we're serving like mod 10,000 cores per second and we also want to ensure the latency
1:14:29 is very uh minimal it's like P99 latency is like smaller than 100 millisecond which means that you can actually quy uh the database at the when you open the browser uh your your your your your profile so another use case is like for Uber Eats right so whenever you order something we want to quickly Shue the restaurant owners that okay your Revenue goes up and also here is like with Within your uh delivery kind of radius
1:14:57 here is like all the performance of like traffic uh how people are ordering the supply demand all those kind of numbers so Uber is like very sensitive to their uh data freshness so we we tend to like provide like a super uh tight kind of uh ingestion for them to inure everything is up to date uh another use cases here is like for all the bsiness metrics uh and normal detection uh use cases this is like for like companies
1:15:28 like doing uh uh business uh metrics and trying to analyze their business performance and meanwhile they want to debug or if something goes wrong they want to figuring out why something goes wrong and they want also want to root cause uh uh their issues um the last one is for like all those kind of like internal dashboard R so everyone want to know like how is my business or how are uh any of of those numbers means right so they they need a lot of this kind of like data visualization and uh you have like an analytical databases which is powering all those kind of dashboard so
1:16:06 uh why real time right so this is because of like uh uh from the uh industry perspective the value of the data is actually um is is is like more as about like if you have a lot of data then you do agregation you do machine learning you can actually uh drill down lot of like what are the pattern of the data that that kind of value is like super valuable to like business owners and uh also people trying to figuring out the user behaviors but uh but meanwhile there will also be like for individual events the value is like um
1:16:43 decreasing based on the uh time uh that has been vanished right so think of like if there's a fraud detections someone like just SW your credit card you want Bank to like immediately detect that instead of like telling you something goes wrong like in a day or two right so this kind of things is like single events uh as soon as possible that's the value and for aggreg events uh as much as the data you you have you you get a lot of
1:17:13 value so that's kind of like we see the industry trend for like analytical work Cloud people are trying to like pushing more real time data into for for analytics and also like people tend to like put in the analytical workload and also present all those things to the users we call it like user facing analyst it means that we are actually uh use users data as to uh as a product to fit into like the applications right so now you can see like every application is very smart it's all like changing based on your user behavior and your like uh user
1:17:52 events so this is like uh just don't don't look at this is like just a use case requirements which uh try to demonstrate that people are trying to uh more on the data freshness and the quut is like very important once this is like user facing once you want more user to use the application or try to like use the database then you actually tend to have like hundreds thousands or even Millions kind of cores per second that that's kind of the the the level of the
1:18:22 uh overcloud that we are dealing with uh so what is the part Pino what we are building is like the fastest uh the fastest real time olap databases which which tend to provide like very high suut and extremely low latency uh and very high like concurrency ques for the industry so here are like a different uh industry like uh uh users that are powered by a PP no you can see it's um spread from like retailer banking uh
1:18:55 uh s of food Logistics Logistics okay now I'm going to give a very high level architecture so in terms of like uh the Pino Pino things so we are splitting Pino into like a realtime server and the offline server this is like where we keep all the data and then we have like a DI store we call the segment store usually we use cloud since for for example like S3 to back up all the data
1:19:22 and then we have something called the controller which uh internally is for like all the clust management as well as the data management so providing all the rest API for um uh all the management cost for the realtime data it's coming from for example Kafka or clis those kind of the real time uh data source and then we can uh quickly uh write data into the realtime server and indexing it and meanwhile we will persist the data to the D store as well from uh the batch or the the offline kind of servers they are serving like more like long long
1:20:03 persisted data and all those data will be like computed or injested through something called minion which is uh kind of like the uh workload the the the processor kind of workload thing it's is you can think of this is like similar to like spark or this kind of workers that can do more things like indexing uh uh build build build the
1:20:29 uh the the the the pre-aggregates all those kind of things happening there so this is kind of like how we are uh keep all the data passes and then we have something called Pino broker which is uh going to handle all the
1:20:43 queries so this is like uh pretty much like all the deployment looks like so from the uh table and the data perspective what we are doing is like we're uh splitting one table into uh many data trunks which we which we called as Pino data segments uh data segments is nothing but just like a group of the columns uh that has been placed and that's kind of like your data and but meanwhile we we we're going to add like a lot of index uh which is going to speed up uh the queries this is kind of like uh the philosophy
1:21:21 engineering philosophy that par Pino project is working on is is trying to adop adopt is like we want to work smart it's unlike like the traditional analytical kind of uh engine working on like okay I want to scanning things super fast uh we are also working on like a lot of indexing trying to see okay how we can try to minimize the data scanning and try to either like find out okay here are the data trunks with the data uh are the are the data you have to okay or we can actually do a lot of things like pre agates which will uh like uh for the uh very frequent query you actually don't need to compute things like again and again right so this is like how we can uh make uh the the the the data the database the query engine more uh more smart and then it will help in terms of like getting uh way higher suput and also like once the data source uh the data size is growing
1:22:24 you you will also get like very good performance so this is kind of like the different uh kind of uh indexing types we have like invert index sort sorting index range index also things like for geospatial kind of things so we also do like indexing so that you don't really need to calculate latitude longitude for all the queries but something like if you draw a polygon we actually know like like a lot of things uh here are the points already inside it and one more thing here we want to like emphasize is like the the trade off of the star index which is like some something very unique P know uh internally we're building something like a pre-aggregates right so think of like you you have some you you have SES like sum good buy those kind of things you can either uh do it in key Value Store basis it's like okay I Compu
1:23:18 all the let's say country equal us and BR equal Chrome and I compute all the sum numbers and that will be like the key value kind of lookup that's we that's what we call as like materialized VI or your pre-aggregates uh so in terms of like the algorithm um complexity is like 01 right you just do a look look up but let's say if you just have a raw table then you want to compute this you actually to scan the entire table and then to to compute this number right so it means that your Laten is very high uh but you don't need to keep all the all the all the detail numbers so so you can actually do a TR so so traditionally if you want to use materialized view it's like uh well nothing right but uh we build something called a star index which allows you to actually do the tradeoff based on like your storage
1:24:10 requirement uh you can actually achieve uh some uh lower latency with certain number of the uh space usage uh this is some some some like you actually be at any point point of this uh sliding uh lines so with this kind of things we actually uh for example The Who for for the LinkedIn who view profile use cases it was actually buil on this materialized view with a key Value Store
1:24:39 uh to serving the 1,000 ques per second we were actually on like 1,000 machines to solve that but once we have pan we can actually uh serve like 5,000 ques per second with only 75 type some type of the machine so this is like the uh engineering kind of architecturing uh what we are doing is like we have database we also want to ensure this thing is very easy to plugable uh and also like very easy to be like extens
1:25:12 tensible to like other systems or for contributors to write their own code so we make this kind of plugable architecture so if you look at here like we have multiple like SPI in terms of like uh you have data you have pin segment SP which means that you can plug in your own kind of data structure or storage format and then you have pin qu SPI me meaning that you can uh have your own kind of implementation
1:25:40 of your career engine if you if if you want uh this is uh something that we are building recently we call it multi-age query engine it's like to support the different types of the joints and uh but since Pino like a super fast kind of cor engine we actually do a lot of heris stics especially for like uh data
1:26:02 especially for the joining use cases we try to like collocate the data so that from the join perspective you don't have to like do any uh do do much like a cross node kind of uh exchange uh but a lot of things come just happen
1:26:17 locally sh I gotta cut you off okay time all right we have time for one question so he forgot to mention Pino which SED that LinkedIn like this something they built internally uh to against do user facing analytics uh LinkedIn actually built a lot of interesting systems Kafka came out of LinkedIn right and then became confident and then Pino is sort of the the other more famous one that came out of LinkedIn as well so let's give give him Round of Applause thank
1:26:49 you and yes and so the uh Nia and Jackie are coming next week uh and so yeah that be Monday and Tuesday so please stop by and talk to them okay all right sh yeah what's that well the slides we posted I mean yeah we can post the slides yes okay all right all right guys have a good weekend and I'll see you everyone on Monday okay I need something refreshing when I get finished manifesting to cold a whole B like Smith and Weston one court and my thoughts hip hop related write a rhyme in my pant
1:27:20 intoxicated lyrics are quicker with a simple Mo licker since I'm a city slicker play waves are picker rhes I create rotate at a rate too quick to duplicate feel a breze at a skate miks at fah when I hold it real tight then I'm in flight then we ignite but starts to boil I heat up the party for you let my girl R me and my mic down with oil Rec still turns with third de Burns for one man I heat up your brain give it a sunt to just cool let the temperature
1:27:50 rise to cool it off with s eyes m