Scale By The Bay 2021 : Russell Spitzer, Multi Dimensional Clustering with Z Ordering

Scale By The Bay 2021 : Russell Spitzer, Multi Dimensional Clustering with Z Ordering

Recording: Scale By The Bay 2021 : Russell Spitzer, Multi Dimensional Clustering with Z Ordering

all right well hi everybody out there today we're going to talk a little bit about multi-dimensional clustering and apache iceberg with z ordering i know that's a lot of different technologies but we're going to kind of walk through all of them it's really mostly going to be a talk about the ideas behind this technology and why we care about multi-dimensional clustering in the first place um to start with let's just talk a little bit about who i am why you should care what i have to say about anything which you probably shouldn't but in case you're still tuned in i used to be a big apache spark a cassandra person i did a lot of work on the apache spark cassandra connector that was done at datastax when i used to work there now i work at apple and i'm an apache iceberg contributor so i spent a lot of time thinking about how to get iceberg faster and one of the things we've been thinking about a lot lately is adding z ordering uh two apache iceberg suite of other capabilities now there's a lot of reasons behind that but the main goal here is that we want to improve file skipping performance inside of battery iceberg now if you aren't familiar with apache iceberg it's a data lake data table format which basically lets you represent many files on disk as a relational data set that you can do transactions on and work on and all that so why do we care about file skipping let's let's just break it down really simply the really big problem in big data is that there's data and there's a lot of it and the big problem here is that hard drives are slow and life is short we have to store things we have to read things all the time and usually the best thing we can do to improve performance of any big data system is just read less data so the thing we want to do almost all of the time when we're planning out big data systems is figure out how can we read as few files as possible to answer a given user query so how do we think about this well let's take for example a completely unpartitioned table filled with nice parquet files so here's a table i've got here it's got three columns one is job one is x one is y pretty boring let's say that i've got just some random job that's writing data into this table it's coming from some streaming source so my arcade files that i'm writing are more or less all kind of mixed up okay so here's an example file i just wrote oh wrote a file it has metrics in it now little did you know the metrics in each parquet file tell you uh the min and max value of each of the columns in that file so this is really useful for people who are trying to plan queries because you can tell right off the bat whether or not a certain file is going to be relevant to your query but let's say that my job is writing data basically randomly so every single iteration that writes a new file basically writes a new file with the exact same bounds because it's basically putting in randomly distributed data in the whole range of possible values that it could be getting in a batch so i end up with a bunch of files that from the metric perspective look exactly the same now they might have different values for other columns or something like this but in this example i'm saying that each one has a min and max value that's exactly the same for every column so this is really bad and this is really bad because now whenever i want to do a query i have to look at every single file that's in my table so for example let's say i just want to select where job is equal to 1 and x is equal to 20. well if i do that i have to check every file which possibly would have x equal to 20 and that is every single one of these files okay so i i have not gained anything from these metrics so what do we do next well the next thing that most people do is we start adding partitioning now if we have a logical grouping that always makes sense for our queries we can then logically group up files and it looks a little bit like this so let's say that we're going to just partition our table on that job column because let's say job is just something that we always ask for data within a single job we're never asking for data amongst many jobs we're really just always looking at one job okay we're doing a little bit better here let's say we write out all of our files now our writer now is going to be smart and it's going to put all of the files with a single job value inside of the partition of that job value okay so our data is organized a lot better now so now when i do that same query if i say i look for where job is equal to one and x is equal to 20 the very first thing i can do is they partition prune i can basically say there's only one partition that has any data files that could possibly match my query so there we go i've cut out two thirds of the data just by doing this one little partitioning change now the problem here is that that x equals to 20 predicate that filter is not really helpful still because every one of my files still spans the whole gamut of values that's possible for x goes from zero to a hundred this isn't good but can we make this better within the system and the answer to that is yes we can do that with sorting now before we get into the order ordering and things like that let's just talk about just a normal hierarchical sort let's say i just sort the data based on a column now in particular in this example i'm going to take my data and i'm going to sort it on just the x column okay so sorting the data on the x column means that all the files i produced i'm going to take and rewrite such that they have an exclusive set of x values so one is 0 to 33 the next is 33 to 66 the last is 66 to 100 and ignore the fact that i missed the inclusive exclusive operator on those greater thans you understand what i'm doing here now when we do our same query we're going to be a lot better off okay so we have all these partitions that have now been have their data ordered inside of them when we do a query select where job equals 1 and x equals 20 now only a single file matches our first step of pruning out the partitions illuminates two-thirds of the things here and then having that x predicate now is really beneficial when i look at my per k file because i know that that part k file only one per k file has the possibility of having an x value equal to 20. now the problem with this is that once i've done this sorting you'll notice that the y column basically has remained the same this is given an example where we assume that for every x value there's still a pretty wide and random distribution of y values which means that if i'm looking for a specific y value i know i'm in big trouble because i don't actually get any benefit unless i include a predicate on x there's no way i can get really any benefit from a predicate on why so our sorting is effective but it's really just a kind of singular dimension thing or unless you have very specialized data where you know that you're always going to sort or you're always going to restrict on a a sorted column before another sort of comes so for example if you sort by time and then after that by customer if you always query on time and customer you'll be pretty good off but if you ever want to do a query just on customer then you're sorting based on time is going to make everything really bad for you okay so how do we kind of get past this problem well the the answer is we need to invoke a little bit of math we need to sort a lot smarter than we're currently sorting so that's where it enters space filling curves so i don't want to go through the real math definitions of all of this because it's complicated and i don't know all the terminology well myself but a good way to think about this is we basically are just trying to draw a line over our data we want to formulately draw a line over our data and then number each pieces of data as we go through that line so let me just go exactly through what that looks like here we've got this nice set of data we have x going from one to four we have y going from one to four and then we're going to just draw a line over it so uh here's the line i feel like drawing today i'm going to just go from the top left corner go all the way to the right go down one and i'm going to go all the way to the left just going to cover the entire domain of possible x and y values down to left now i'm just going to draw this nice little line then i number all of my things i've now drawn a space filling curve over my domain of x and y and then numbered my data points so for this particular curve point number one is the far upper left point number 13 is the lower right so this curve is really fun you know i enjoy drawing lines a lot of fun to do we get to like draw little doodles and be happy about it but this line is not actually helpful for our quarrying case so the main problem with this is that it's not a locality preserving curve okay the key thing we want here is something that's called locality preserving what do i mean by that what i mean is that i want this line to basically have a short distance between values that are close in two-dimensional space okay so what does that mean let's take two points for example here let's say we're looking at the difference between uh x equal to one y equal to three and x equal to one y equal to four okay these two spaces are only one space away in two-dimensional space but on my z-order or on my space filling curve that i've drawn here which is not as the order curve on the curve that i've drawn here they're actually a full six squares apart from each other so this is a pretty big difference not exactly what i was going for here okay so how can we make this better i will sorry why is this bad this is bad because because it doesn't preserve uh locality if i then group this up into files we're going to end up with files that keep data that's not really closely related in the same file in fact if we build four exactly spaced files here imagine each file can only hold four data points we basically get four files that look like this and we basically just reinvented hierarchical sorting so this is like not a good curve to use because we end up with the exact same problem we had before we've ended up sorting our data on one column and ignored all of the important information that's in the other column that might help us make data that's more closely clustered on both dimensions so again if we did our query here we've actually in no way benefited as long as we're doing a query on x we only benefit from queries on y okay so this is this is just an example of what one of these curves can look like and basically the game we're going to be trying to play which is we're basically trying to draw a line that goes very close in two dimensions um while still going through every single data point in our domain so enter z order curves so it's called z order curve so it looks like a z we're basically going to draw these little z's all through our data this is a kind of uh recursive pattern and the larger your domain is the larger these become and this is very different than our previous line you'll notice that this line actually preserves locality pretty well in a lot of cases so now those two points that we looked at before x equal to 1 3 and y equals sorry x equal to 1 y equal to 3 and x equal to 1 y equal to 4 are now only separated by a single square they would be number one and number three so imagine i take that same file setup again and i make four files based on this line instead of four files that are spread out amongst one dimension of my data i get four files that are clustered on both dimensions so for example i'm going to make a file that's where x is greater than one x is less than two i'm going to get one uh sorry well i guess the best way to look at this it's hard when i'm not in person and i can't point at these things very well but you can imagine there's the upper left quadrant there's the upper right quadrant there's the lower left quadrant and the lower right quadrant and all of those basically get their own file now so this is a lot better because now if i want to query on x or y i can actually be selected so this is really cool because now if i do a query for example if i'm looking for x equals to two i have to check two files and if i check uh these sorts of things so basically on x or y we can be selected we can cancel out files we can skip files there are other curves for example a hilbert curve which is another example of a space filling locality preserving curve looks a little bit like this but basically serving the same purpose basically in all of these cases of space filling curves in terms of of data search and data data uh helping performance of data lakes and things like that we're basically looking for lines that go through our data and get multiple dimensions close together in a one-dimensional line so this is another cool little algorithm you'll notice it does the exact same thing on my trivial toy example and just to show this in action let's imagine that we're doing a query of where x equals three we only hit two of these files uh same thing if i look for just y i only hit two of the files i basically made it so that instead of only being selective on one dimension like a normal hierarchical sort would be i'm selective now on both dimensions and if i combine them both at the same time if i have where x equals something y equals something i still get the same benefit because it will still only be in a single file okay so that's what these kind of look like on this very weird little trivial domain i made where x goes from just one to four and y goes from one to four so this becomes more complicated when we extend that domain to allow more values and here's just some pictures of what that looks like but the key thing i want you to see in this photo is that when we have sorted our data this way we get these locally collected pieces of the of the domain so you can basically see in both of these graphs that there's a repeating pattern that happens over and over and captures like small quadrants of the space up into a localized zone and that's really all we want here we just want to make sure that our data uh looks all nice and clustered like this now this actually extends out to multiple dimensions but of course becomes more and more difficult and the more dimensions you add now obviously i just made a fake little trivial example and i showed basically how this can benefit a completely dense domain but what if we don't have that kind of domain like let's say that we have these two columns but they don't actually have values for every combination of x and y so let's just take a little look at uh what might happen so starting with let's let's assume that we we just don't know the right number of files to make here say say that we have to just make three files instead uh things are going to end up actually look uh a little weird but we still get benefits because of the curve um but there's something else that we can do here to actually make this work a little bit better and that's we can actually use the z values themselves when we're planning our queries now for example let's say that we take one of those two divisions that i have here we know that each one of these files now that we've created these three weird looking files has a min and max z value so they have a min and max x value a min max y value and they also have a min and max z value the highest curve value and the lowest curve value if we can transform the filters in our query into z value based filters then we can also use that when we're coring our data so this is really useful so let's say for example that we're missing a few pieces of data in our files uh so we're missing uh in this particular example whatever would fill in at x equals to two y equals two and x equals to one y equals to one so we've got two holes here we end up making three data files and the x and y ranges are exactly the same as if those pieces of data had been there because they just look at the min and max values in each one um but we have a big difference here we have a big difference in this z column because each of them has this separate range of z values so let's start by just using a little query that looks like this we're looking for x is less than x is greater than 2 less than 3 y is greater than sorry y is greater than 1 y is less than 2. now if we look at this there's only two files that could possibly match this without considering our z values our bottom two files are the only ones that have x values within that range and also have y values within that range but we can do better if we also use our z values when we're planning so how do we do that so if we look at the box that is surrounded by x is less than 2 y is less than x i'm really bad at saying inequalities today x is greater than two and x is less than three y is greater than one y is less than two we draw a little box in our data and you'll notice within this box of values that we're actually looking for we can check what the z values are and we can see that the min z value within this box is 10 and the max z value within this box is 15. now we've got more information to actually do our query planning with if we know that the z value has to be between 10 and 15 well now all of a sudden what used to be two files that we have to check is now only one file now i've indicated here in uh highlighted in white that basically there's only three possible data points that match the z value constraint so if we add that together you'll see that if i'm looking for z between 10 and 15 i can't check the second file and i can't check the first file because we know there are no z values within that range there so this basically lets us save a whole lot of time and skip an additional file so ideally what we want to be doing here is not only organizing our data based on this z value curve but also storing our z value as another piece of file metric that we can use to query plan with so that's basically our goal for our implementation inside of iceberg now we have to ask the question how do we actually compute these curves how do we actually apply them to real world data so this is where it becomes a little more complicated so to generate a hilbert curve you have to do some matrix math luckily there is a really nice paper out called programming the hilbert curve which was then translated by david moton into a java library so you can actually see this and do the math that actually generates a hilbert curve but basically in that case you have to say how many bits wide your domain is and it basically will draw a curve within the bit field for z curve for a z value curve it's actually a much easier representation to draw this line all you have to do is interleave the bit representations of your columns except there's a small caveat to that it's not just the bit representations because we know that modern computer types are a little more complicated than just being lexically let's alexa graphically ordered bytes so for example an integer starts with a sine byte which all of a sudden means that all of your negative numbers end up being larger than all of your positive numbers so what we really need is to be able to interleave the representation of the bytes as if they were a lexigraphically ordered type so um i wrote a little description here which i'll read again uh we would like to interleave the bytes of lexographically orderable representations which mirror the semantically orderable representation so we want to make byte representations that are lexigraphically ordered we can compare them uh highest bit to lowest bit but they have to have the same ordering as the original data type would have had so this is a little bit more complicated and this is where some of the tricky stuff comes in so we also want to make sure that these represent representations end up being very dense over the space that we're drawing the curve but i'll just go over some quick examples of how we can get these kind of transforms at least at a very simple level so the key thing to remember here is we don't really care about our mapping being one to one the only important thing is that if we give two for example integers we want the two integers that are if those two integers are different where one is greater than the other then the byte representations that we create must have the same relationship if they don't then we won't actually be able to build a accuracy order so for a lot of types this is actually pretty uh pretty straightforward so for example those signed integers i was talking about are actually sortable except for that first sine byte so in the case of an ordered representation a signed integer all you have to do is really flip that sign byte and then all of a sudden your negatives come before your positives and all of your data is correctly sorted now you can do similar but slightly more complicated things to floats and to strings except at strings we end up with another problem now our strings can be any number of bytes long and what we really want is to be able to compare the most important bytes with the most important bytes of another column so with strings basically one of the cheap ways to get around this is to just truncate them to a certain length and say you're only going to care about that certain depth but in the future what we'd really like to do for all of this and this is something we're currently debating in the community about how we're going to implement these in the future is how we can bound these functions so that they're actually representative of the data that they were clustering so that we can hopefully get a nice representation that fits well with the data that actually got the order now how are we going to actually use this inside of iceberg so the current implementation that we've been doing and we've been prototyping with basically complex uh adds this into our rewrite data file command so if you're familiar with iceberg one of the cool things iceberg has is the ability to automatically sort your data and reorder and bin pack your data together to get more optimal performance than querying so like i showed at the beginning that hierarchical sort sort of thing is already an automatic feature that you can use inside of iceberg so we're basically going to take that same logic which can hierarchically sort data and instead write a sort expression based on rc order curve and then have the data sorted on that instead so basically we'll basically take the same we take the same command and then we put in a z order function instead of a hierarchical sort expression and then we get our data sorted so i know this was a lot of talk about z order curves not a lot of talk about iceberg and i'd be glad to talk a lot about that uh in the q a but there's a lot of work left to be done on this implementation and also the discussion of how we're getting it done and i would be uh remiss if i didn't tell everyone that apache iceberg is an open source project and everyone is welcome to contribute uh check us out at https icebergapache.org or on-site our slack there is an apache iceberg slack which is invite uh which is available to anybody the invite link is on our main page and if anyone has questions about iceberg or doing this kind of space filling curves i'd be glad to take those questions you