So today's focus is on how to actually then build the second major component of a query optimizer of how to actually do estimations on what we think the system is going to actually do when it executes a query, like how much it is going to cost us to execute the query. So yeah, so this is not working. So the reason why we have to do this is to be sort of obvious, when we talked about the cost-based search models from the last two classes, I said that this is sort of black magic box thing that's going to tell us that here's what the expected cost of executing this particular query is. And again, it's an internal cost. It's not something that's meaningful outside of the database system. I mean, you can't take MySQL's cost model, have it spit out a number, and then take Postgres' cost model and take that number and then make a comparison, right? This is completely dependent on the implementation of the system, and it's really just meant for us to be able to say, this query plan is better than this other query plan for some reason which we'll describe going forward in this lecture, and therefore, that's what I want to use, right? So the other thing important to understand, too, this is also independent. This cost model is independent of the search strategies we talked about last time, meaning whether we're doing top-down or bottom-up, it doesn't matter. At the end of the day, we still need a cost model that still needs to make predictions about whether one plan is better than another. So if you're going to build a cost model, how would you actually do it? Well, there's a couple of different things you can include in it. So the first is the physical cost. So these would be what is the hardware actually going to do when it executes the query, right? How many CPU cycles? How many cache misses? How much data are you going to read from disk? This is obviously dependent on the machine that you're running on and its hardware configuration because as we saw in a couple of different examples, whether you're using a Xeon CPU or a Xeon Phi, those CPUs have very different characteristics and therefore, the performance of your algorithms or your query could vary depending on what hardware it is. So this is usually pretty tricky to do because of that reason, because it's hard to actually have build models based on all different possible hardware configurations that could exist. The next approach is to do what I'll call logical costs and these are where we're basing their cost estimates on what the operators in a query plan are going to actually do at a logical level. So a physical level would be, again, I read this many blocks from disk. A logical level would be, I'm going to read this many tuples from the table or my join operator is going to spit out this many tuples after the join or my scan is going to filter so many tuples. So for these, this is going to be independent of what algorithm we're actually using in our query plan. So this is only looking at the logical operators and the physical operators. This should be sort of obvious. If I'm doing a nested loop join versus a hash join, at the end of the day, both algorithms should generate the exact same result, the same number of tuples, because otherwise I have problems in my implementation. And so therefore, we don't care whether, for logical estimates, we don't care about whether it's one algorithm versus the other. So the tricky thing is going to be, and what was in the paper that you guys read about and we'll talk about going forward, is you're obviously going to need to be able to estimate accurately what the output of an operator is going to be because that's going to be fed as the input for the next operator. So in order to say, the number of tuples I'm going to read into this operator and therefore generate this much output, I need to know what came below me in the query plan. And that, again, that's going to be the hardest thing we have to do. And the last one is going to be sort of algorithmic calls, sort of asymptotic complexity of the operators. And this is where it actually matters whether we're doing a hash join or a nested loop join or index scan versus a sequential scan. And again, for these ones, we can just sort of have weights that's being able to say, oh, the hash join is X times better than a nested loop join and therefore prefer that. But there are obviously some scenarios where the nested loop join would be better. So as we'll see as we're going along, and actually I'll show the next couple of slides, what we're primarily going to do for an NMRI database is going to be a combination of these two. For this one up here, you can do it, but it's hard. And this is another good example of the difference between the commercial database systems and the open source database systems. So at the talk, the Redshift talk on Monday, if you went to that, Ippercratus mentioned that the query optimizer in their system is notoriously difficult and they've spent a lot of money fixing it up at Amazon. And it's way better than any of the open source ones that are out there. It's sort of commercial grade or enterprise grade. Because the enterprise guys are going to include all of these things. Open source guys probably just include to these two guys. So for a disk-based database system, the most obvious thing that we care about is the disk, right? It's the end of the day that that's the most expensive thing, right? Feeding, getting things off of a spinning disk hard drive or SSD. So in this world, the CPU costs are not negligible in the sense of we can ignore them. But if your cost model only includes how many blocks of data that I read and write from disk, that's probably going to get you 90% of the way there, right? Who cares what you actually do when you bring the data into memory? I guess it's getting from disk is the most expensive thing. Now, obviously, it's less of an issue on modern SSDs. But definitely, if you have a spinning disk hard drive, taking account of the difference between sequential IO versus random IO is a big difference. And a lot of times, again, you see in a disk or in a database system, especially older ones, they use algorithms that are designed to optimize the amount of sequential IO you're doing, right? So the important thing that I understand about in a disk-based system is that the database system is going to have complete control over what's in memory, over its buffer pool management. Assuming you're not using Mmap, which we can discuss later, we know exactly, in our databases, we know how we're actually bringing blocks in. We know how we're writing blocks out. We know what algorithm we're using to decide what data is cold, what data we want to evict, right? So we have complete control over this, and we can include this in our calculations in our cost model. We know how, if we're going to give this amount of memory in a buffer pool to run this query, and therefore it has to read this amount of data, whether that's sequential versus random IO, we can then take that account into our cost models to make estimations of what we think the query is actually going to do, all right? So I would say this is, what I'm describing here is how you would do this on a single node disk-based database system if you're a distributed database, just replace the word disk with network, right? That's basically the same thing, and you have the same issues. So I want to a quick example of what Postgres does. The reason why I always like to use Postgres as an example for describing how real system actually implements this is that, in my opinion, it's almost like a textbook definition or implementation of a database system. If you take any introduction class, you take the textbook we use in that, and the way they describe the algorithms in the textbook is exactly how it's actually implemented in Postgres. So for Postgres, they're going to use a combination of CPU and IO costs that are going to be weighted by these what are called magic constant factors, magic weights. And the reason why you do this is basically you just say, because it's dependent on what the hardware actually can do. So they'll say sequential IO will be x times faster, x times better than random IO, and memory IO will be x times faster than sequential IO, right? So in this environment, they are obviously targeting in these sort of default configuration a database that's on disk, and therefore you don't have a lot of memory. So again, they want to use that in their cost model to account for what's actually going on. But the tricky thing is they expose this to you as an administrator. You can actually tune these weights for you, right? So the default is the memory is 400x faster than reading from disk, and then sequential IO is 4x faster than random IO. So you can go in the documentation to see how you change these costs. But then they had this nice little warning here that basically says, if you start mucking around with these, you could have problems, right? Because again, these are highly dependent on what the actual workload is and what the data looks like, and what your hardware actually looks like. It's really hard to get this right, right? So most people don't tune these things because they don't know what you're doing, and you don't want to cause regressions on some portion of your workload. Even if you have a commercial system does, we can look at what DB2 does in their system. Of all the three major systems, DB2, SQL Server, and Oracle, DB2 is actually the most open about discussing what their query optimizer does and what their cost model actually does, right? There's no, as far as I know, there's no major publications from Oracle or SQL Server that talks about what they do, right? We just sort of know some things based on talking to people there. But IBM is actually pretty good about discussing this. And this call comes from a presentation from Guy Lohman, who was the guy that invented the starboard stuff that we talked about two classes ago. So the DB2 cost model is a combination of all of these things. So first of all, they're gonna look at what the database actually looks like. So the schema, and they collect on the tables, the columns, or any indexes.  If it's a distributed system, and they're gonna use that to essentially generate the weights that I was showing you in the last slide for progress, so progress you have to set these weights manually. DB2 tries to figure this out for you and tries to be real fine grained based on what your hardware can actually do. But then also, when you actually start doing cost estimation for the query that shows up, they just don't look at your query in isolation by itself. They also account for what other things are running at the same time. And then use that to determine what the effect of those concurrent operations are on for your particular query. Like if you're running by yourself, then you know you take all the memory in the world and you run really fast.  So therefore, they take that into consideration when they estimate the cost for your query plan. Right, so again, this is just, it's way more sophisticated than what any of the open source guys do. And the Postgres one, as far as I know, at least the lesson I looked is much better than the MySQL one. It's probably the best open source. It probably is the best open source query optimized and cost model that's out there today, at least a year ago when I looked. I don't can't think of anybody else that got better. All right, but we care about MMA databases. So what do they do? So from looking at the documentation and the manuals of the major MMA database systems, as far as they can tell, everyone does what I'm describing here. So basically, the disk is gone, so you don't care about disk IO. Yes, you have to write to the log, but that's incidental, right? That doesn't affect whether you choose one particular query plan versus another, like if I update a table, who cares? The disk is not considered in the cost of that, of writing up the log record, right? So at the end of the day, all of the MMA databases are going to do a combination of primarily how many tuples are being processed by an operator, and how many tuples they're generating. And some basic weights to say hash joins are better than nest loop joins. But the number of tuples in and out is the major factor. The reason why you can't actually do anything more fine-grained or account for how much memory I'm going to be able to use for my query in the same way you could in a disk-based system is because we have no control over actually the cache management of our systems. That's all done by the CPU, and the CPU, we can provide hints to it, we can prefetch things, we can try to pin things in our caches. But at the end of the day, the CPU decides on its own what gets moved in and out of the cache. So we don't even bother with any of that. So we just try to estimate how much data as my operator is going to read and write. And it turns out that ends up being a, we'll say, a reasonable estimation of what the CPU resources I'm going to use to run my query. And this also says also, this is not also accounting whether I want to run a one thread versus a hundred threads, right? That's sort of a separate policy that's different than what we're trying to do here, and that's sort of almost like a mission control or resource management for the system. So typically, as far as I know, you don't see that in accounting for the cost model, and that sort of happens after the fact. Again, if you have it, even if you're an in-mary system like a MemSQL, since they're distributed, again, go back to the last slide, they care about the network, so they have to account for that. And not so much, and this still matters, but the network is the major factor. All right, so I want to give an example of what was a sophisticated cost model from the 1990s done in small-base. It actually does some of the things that we talked about with DB2. So what they would have is they would have this sort of two-phase approach where as the today's developers were building the systems at the company that were building small-base, they would try to identify what are all these low-level primitives that occur during query execution. Whether or not they're primitives in the same way, they're not really in vectorized primitives where you have those for those. But it's like low-level things like I read an index or I write to a tuple. So they generate these low-level operations and then they create these micro-benchmarks that allow them to sort of simulate each of these different operations. So then now at runtime in your system, when you deploy small-base, they would take all these micro-benchmarks, run them when you turn the system on, collect some profile information about how fast your machine is. And then in the cost model, when you look at a query plan, you count up the number of these low-level operations or primitives that they're doing, multiply by the micro-benchmark results that you collected, and then that's how they're determining what the cost of executing a query plan is. So for again, small-base was this early memory database system prototype out of HP Labs. HP Labs then spun it off as a separate company called Times 10, and then Times 10 got bought by Oracle in 2006. And it still exists today, you can download it. The old system used to beat it, we haven't tried it against our new system yet. The Oracle primarily sells it as like a CPU cache or sorry, an in-memory cache for the main Oracle like flagship database, but you can still run this as a standalone system. But as far as I know, again, by looking at the documentation, what they did in the 19, like this paper in the 1990s, they don't do in the real system today. They still do, they do what I've described before, they just estimate what the number of tuples in and out for an operator is. This approach is similar to BOGO MIPS, if you know what that is in Linux. When you boot up Linux, they run this little micro-metric called BOGO MIPS that tries to approximate how fast your CPU is, and they use that for timings decisions for interrupts and scheduling. If you ever look at slash proc slash CPU info, you'll see like here's my Intel CPU, here's the model number, here's my cores I have. There'll be a little entry called BOGO MIPS. And he used that as an approximation of how fast your CPU is. So I said that the most important thing we're gonna care about is the number of tuples in and number of tuples out or processed by an operator. So now we gotta figure out how we're actually gonna be able to estimate that. So the way we're gonna do this is that we're gonna try to estimate the selectivity of an operator, which is gonna determine the percentage of the tuples that are fed into it, it's the percentage of the tuples that will then be admitted as output. So if I'm given 100 tuples and my selectivity is 10%, then I'm gonna admit 10 tuples. So the way you traditionally do this in a database system is you're gonna just model this as the probability of whether a predicate will be satisfied for a particular tuple. And so the way we can generate now these probability estimations is through a combination of these different techniques. So we have domain constraints, this would be something like if we know the value range ahead of time of a particular attribute, like if it's an enum field, we know that the cardinality is fixed. We can rely on pre-computed statistics that we can generate and put into our data blocks and our tables. We talked to us before, we talked about compression, these are like zone maps. So I can pre-compute aggregations for different columns in a block. And then when I wanna figure out what's the likelihood that my operator's gonna match or my predicate's gonna match a tuple within a block, I can look at the zone maps and maybe derive some early information, like a minimax value. We can also use histograms or approximations, which I'll talk about in a second, and then we also do sampling. So there's no one of these is better than another, like you kinda wanna use a combination of all these things if you can to try to estimate selectivity. The more information you can get, the better. So the number of tuples that we're gonna be, and a processing is gonna combination, the number of tuples that we're gonna process will be dependent on three different things. So first is obviously the access method that we're using to read tuples from the table. If it's a sequential scan, then we're gonna potentially look at everything unless we push down the limit clause. If it's an index scan, then we can need more fine grain and look at the subset of the total key space. Then we have actually the distribution of the values of the database attributes. This is where the estimation stuff is gonna come into play to let them know for a given predicate, what's the likelihood of probability that I have values and that would satisfy that. I mean, of course, then also what are the actual predicates themselves, right? If I'm doing a quality predicate on a unique column, then I know my selectivity is gonna be one over the number of tuples that I have, because the only one attribute can match. But now if I just start doing a range scan, then this becomes more problematic to try to estimate this, right? So the main takeaway is that for simple queries like something equals something, we can do a reasonably good job for matching that. If you start throwing in inequalities, throw in range scans, throw in disjunctions, then it becomes really hard. And again, the more data you can get, the better. So one approach, again, in the intro class, we teach you how to generate histograms, right?  And it computes some kind of histogram based on what values it actually sees. So again, that's the standard technique. What's been sort of more prevalent in recent years is to generate, instead of exact histograms, to generate what are called sketches, which are these approximate data structures that can give you a hint about what is contained in the data. So think of this as the bloom filter is an approximate data structure, because it can give you false positives, but it'll never give you false negatives. And it won't tell you what values or keys are actually in the bloom filter. If you just ask it whether something exists, it'll give you a true or false. So these sketches are a little bit more complicated, rather than giving you simple true and false, they can actually tell you values that could exist, right? But again, you could have false positives. Actually, some of these I don't know whether you get false negatives as well, right? So there's a bunch of different kind of sketches that people can use, right? The reason why I bring this up was a few years ago, we had the CEO of Splice Machine come and give a talk in the intro class. And he's see me alum, he's on the Board of Advisors for the Dean. And he was here in February. And he made this comment about when he was talking about their query optimizer and their cost model was they did the textbook way initially, where they just build histograms first. And they use the standard algorithms equations to try to do estimations on the selectivity of predicates in their operators. But then they end up using this sketching library from Yahoo, that did these approximations, right? So you get error bounded estimates to be able to say like, this is what I think it's gonna be and here's my confidence about what I'm telling you. And they said that when they switched to using these sketches instead of histograms, the accuracy of their predictions and the robustness of the query optimizer, primarily because of the better cost model, the difference was quite significant. So I think they said in the old system when they were using histograms, they could do the cost model would be okay up to like 10 tables per query, like a 10 table join. But when they added this, then I think they could go up to like 75 tables. Which is, again, it's not I'm saying that's the right metric to use to determine the quality of your cost model. But that was sort of anecdotal evidence that suggested that using sketches was better than histograms. And in our old optimizer in the old system, we ended up using histograms as well. But, sorry, we ended up using some of these sketches as well. But we never vetted it. We never actually measured how much better it actually was. And again, this approach I think is also used in commercial systems. The other main technique to generate estimations about the selectivity are to do sampling. The basic idea here is that rather than look at these sketches or the histograms and try to approximate what the selectivity is, let me actually just take a subset of the tables I'm accessing, run my query on that, or run my scan with predicates on that, and then determine what my selectivity is. And then assume that my sample is a good approximation of what the total table actually looks like. And then now I have better knowledge about making my choices in my cost model. Right, so there's basically two approaches to do this. It's like online versus offline. So the offline approach is you in the background every so often you generate this read only copy of the table that you sort of put aside and then you do a measure sample and you use that in your cost model to predict this selectivity of your predicates, right? And then you have this sort of this background job that looks and say, says well, how much of my data has changed? And then if it's above some threshold, then I go back and refresh my sample.  And obviously this becomes tricky because you're trying to do a cost estimation for running your query, but now you actually run something of the query, some subset of the query on the table and that could end up being slow. And then you also don't want to slow down other transactions or queries that are running at the same time. So you want to make sure you run this and read uncommitted without updating any latches or locks to avoid interfering with anybody else. So the way to think about doing the sampling thing is I have my where clause rather than doing any joins. I just pick out the predicates from my where clauses or our join clauses and I just run that on the tables themselves to compute this. Of course now this becomes hard if you have joins cuz now the selectivity of the join is tough to compute unless you start joining things. So the extent in which people use different systems, use sampling aggressively will vary. And this is where we get into the commercial systems are doing something that they don't really talk about publicly so it's hard to know what they're actually doing. But I know in the case for the paper you guys read, I think they mentioned some paper. SQL Server performs the best. SQL Server is doing a combination of histograms or approximations plus sampling. Okay, so any questions about this? So we're using this to figure out we have to use either histograms, sketches, or sampling to figure out the selectivity of these predicates. And then we can use that to compute the cardinality of our operators, which is then the amount of data that's being generated as the output. And the reason why I want to know what this is cuz that is then being fed as the input to our next operator. And the problem's gonna be that the more inaccurate our estimates are for the cardinality of the selectivity of our predicates in these operators, at the lower parts in the tree, then that's gonna get amplified as you go up. Cuz if I'm off of the bottom leaf node, as I go up that error gets carried over and now it becomes even more off. Again, this is what you saw in the paper you guys have read. So the textbook way you would actually compute the cardinality is by modeling the selectivity, as I said, as a probability. And then you make the following three assumptions about those probabilities to be able to compute what the cardinality is gonna be, the selectivity is gonna be, right? And again, so I would say this is what I'm describing here is what we teach you in the interruption class.  And hopefully they would say to the caveat like, this goes real wrong real quick, but people still do this, right? Cuz there's nothing else, right? The only way to get the exact cost of a query is actually to run the query. But that's actually super slow, so you can't do that. So you make these assumptions, you make these sort of trade-offs in the accuracy just to be able to get something that works reasonably well. So the first assumption we're gonna make in many cases is that we're gonna have a uniform distribution of values in our attributes. Meaning the probability that a given attribute appears in my column is the same for all values. Of course we know that this is not true, right? More people live in New York City than in Montana. So I can't assume that the zip codes in Montana have the same probability of occurring for people, a people database than people in New York City. All right, the way you typically get around this is to maintain a separate data structure for what are called heavy hitters. The thing of this is just like a little hash table on the side that says, here's the top 10 or top 20 values that occur in my column. Cuz more times than, I'm more likely to query those values. And therefore I can go do a look up in this heavy hitter table and get more accurate estimates. But then everything else is assumed to be uniform. The next is that we're gonna assume that all our predicates are independent. Again, we're modeling these as probabilities. So that means we can actually multiply them together and that's gonna produce the true selectivity of our predicates. Of course, that's not gonna work. We'll see that in the next slide. And the last one is that we're gonna assume that the join keys for interrelations that we're trying to join on will always exist in the outer relation, right? This obviously doesn't work, and if you start doing left outer joins or red outer joins, this becomes problematic. But again, this is another major assumption that people have in their cost model. So let me show an example of how this all goes bad. In this great little vignette of this sort of simple problem that, again, that was in a blog order from Guy Logan. But I like this cuz it illustrates exactly all the problems that you have when you make all those assumptions. So say you have a simple database, keeping track of cars. And you have in your database, you have ten different models, like Tesla, Honda, Ford, so forth. And then, sorry, ten minks, Tesla, Ford, Honda, Toyota. And then you have a hundred different models. So Ford Escort is a model or a Toyota Corolla is a model. So you have a hundred of those. So if you have a query now that says, where make equals Honda and model equals a cord, right? So you have a conjunction and two equality predicates. If you make the independence and uniformity assumptions from the last slide when trying to estimate the selectivity of this predicate, right? Then you're gonna end up with one over ten because we have ten minks, right? So it's an equality predicate. So it's Honda, it can occur once, so it's one out of ten. And we multiply that by one over a hundred. Cuz again, we have a hundred different models and a cord is one model. So it's one over a hundred. So in this case here, the selectivity is estimated to be 0.001. But in reality, we know that Honda is the only one that makes them the cord. So it's not this, it's not one over ten times one over a hundred. These comms are actually correlated. If you have a cord, then you have a Honda cord, right? So the true selectivity is one over a hundred. So again, that independence assumption that from the last slide is gonna make us be an order of magnitude off in our estimations. And then again, now if I start saying if I'm order of magnitude off at the selectivity of some lower operator, and I feed that now into another operator, who's also gonna be another order of magnitude off, then I'm really screwed, right? So the way to solve this problem, and as far as you know, this feature only exists in the commercial systems. This is due to what are called column group statistics. Or you're basically telling the database system that these columns are correlated, and therefore it should maintain statistics about them. And when it computes the selectivity during its cost model estimates, it should treat them as being correlated, right? And don't assume that they're independent, right? So again, basically the way it works is like the DB has to comment and tell the data system, hey, these two columns are correlated. And then if the system supports that, then they can update their cost model appropriately. Again, only DB2 and Oracle do this, because as far as I know, MySQL and PostgreSQL don't do this, and none of the other major open source systems do this. Now you may be thinking why does this, why is this manual, right? Why does the DBA have to tell the DB system? And I think that's why. Why can't we do this automatically? Cuz it's hard, right? Like, think about how to figure this out. In this example here, it's super easy, right? Cuz I only have 10 makes and 100 models. But I have a billion tuples, and I have a really wide table with a thousand columns. Now I gotta go look for every single unit combination of different columns. Look at all different possible values that can occur, right? This thing's gonna blow, the search base is just massive. So this is why you can't do this automatically. Now, there may be ways to approximate this automatically. But again, as far as I know, no major system can do this automatically for you, you have to tell it ahead of time. We can talk offline about whether deep nets help with this. There are people looking into this now, but nothing exists yet. All right, so let's look now about how these simple examples can really foul us up, right? When we start throwing in joins into our query plan. So here we're doing a simple three-way join on ABC or AID equals BID, AID equals CID. And then BID has a filter where the ID is greater than 100, all right? So assume here we have a, there's a filter predicate, a filter operator in between the B and the join, right? For simplicity reasons, I'm just showing the filter being done down here, right? So the first thing we need to do is compute the cardinality of the access methods that are retrieving tuples from the tables, right? For A and C, there's no filter. So therefore, the cardinality of the operator that's scanning A and C is just the number of tuples that are in the table. I mean, that's easy for me to compute, I can get that from the catalog. For B, it's gonna be the number of tuples that are in B, multiplied by the selectivity of our predicate here, all right? So then now we're gonna feed up the output of these scan operators into our join, so now we need to be able to compute the cardinality of our join operators. So what's gonna happen here is that if I, if these guys, if this thing is bad, A and C is simple, right? Cuz there's no filter. But if this thing's wrong, then now I'm feeding in the incorrect number of tuples into this join operator. And then now I gotta figure out what the selectivity of these two attributes are. Assume I don't have a foreign key, assume that these guys aren't correlated, like I know nothing about them. So now I gotta figure out for every single value that exists in A, for A, A.ID, how many values are gonna match that in BID? And I try to figure this out in my histograms, but that's gonna be hard. So then now I take the output of this estimate. Now that's gonna be fed into this estimate here, this join. This thing is just reading the table, so that's super simple. So now I have the same problem that I have before. Now I gotta figure out, well, what's the likelihood that a tuple that matched AID equals BID here will exist and get fed up into this thing, and then also be able to match on C.ID, right? So again, I get that wrong, this gets wrong, and then this gets even more wrong, right? So this is what we're dealing with, it's just like the math, it's not in your favor here, regardless of whether we're treating these things as probabilities or as not, these estimates are always gonna get wrong and it gets worse as we go up. So again, you were to see this in the join on our benchmark in the paper you guys read, the more tables you add, the more bad it gets, right? For this reason here, because we're just throwing errors on top of errors up in the query plan. All right, so the paper I had you guys read came from the hyper team in Germany. And it was an evaluation of how accurate are the sort of the cardinality estimates in operators for a variety of different database systems. And then they wanted to use that to figure out the just how bad things actually can get, how all for you are from actually the real time. So the paper does not tell you how to build a cost model. It's sort of roughly sketched out how to do this here. But it's just showing you what happens when the s's in your cost model go wrong. And then they sort of propose some sort of design principles of building a database system is sort of what you should focus on and make the system more robust to deviations or errors in your cost models. So in the paper, they propose a new benchmark code, the JOB, the join order benchmark. So in this one, it's actually based on I think the IMDB data set, so the movie website. So and this is a real data set. So the tables are actually going to have skewed based on a real world distribution, right? And like TPCH and TPCC, these have uniform distribution where everything, the likelihood of one attribute occurring is the same for all, sorry, like one value occurring for a given column, it's the same for all values. And the join order benchmark has actually real skew in it. So they're going to generate a bunch of different queries that are going to join more and more tables and then they want to be able to measure what the cost model thinks the selectivity is going to be of the cardinality of the operators and compare that with what the real data actually looks like, right? So for this, the way they're going to use this is that they're going to load the data in once and then they're going to run Analyze, which again, that fires off the background job to actually go scan all the table and let the system compute whatever statistics that I want to compute. That's the best case scenario. There's no updates, I load the data in and I run Analyze. And again, they want to see in this best case scenario how wrong things get. So I want to show this one graph here because this is the most important one here. And so the way to understand this is that the y-axis is how far away you are from being exactly accurate in the cardinality estimations. So this middle line here is when you're perfectly accurate. And then if you're above this, then you're overestimating if you're below this, then you're underestimating, right? And then the x-axis is the number of tables that they're joining in the query here, right? So the first thing to point out is that everyone, the overall trend seems to be that everyone is underestimating, right? As you add more tables, everyone sort of starts to go down, right? All right, so again, what is that from? Well, that, as we showed in that when we talked about those assumptions. If you assume that things are independent, then I assume my selectivity is going to be way less than it actually is. So that's why they're all underestimating from what the actual value should be. So the first one to point out is this one guy here actually does reasonably well up to about three or four tables, right? And across all of these, they had the most tightest balance from being 100% accurate versus all the other ones. The three systems here are essentially all have the same trends. But the balance will vary. Right, again, as you add more tables, the estimation gets worse. And then at six tables, it's really bad. Then you have this middle guy here who's just way off right away. It is okay with two tables, and then after that, it's underestimating way more than everyone else. So I think in the paper, they tell you that the first one and the last one are Postgres and Hyper, right? And I think I spoke at last time of who is the best one here, right? Let me take a guess what this one is. Microsoft SQL Server, okay. Let me take a guess what these other two ones are. Which one's Oracle? This one here? You said it was this one? All right, raise your hand if you think Oracle is this one. Raise your hand if you think Oracle is this one, okay? And then we need a last system, take it, DB2, okay. So you think this is DB2, this is Oracle? Okay, there you go. So, let's focus on SQL Server. So SQL Server does, it's Cascades, but again, the cost model is independent of whether or not you're doing Cascades or bottom up, right? But they're doing sampling, they're doing histograms, all right? And it's just, SQL Server's just really good. In my opinion, I consider it to be of these three systems here. I think it's the, at least what they've talked about publicly, in my opinion, it's the most state-of-the-art leading edge system, right? Oracle and DB2 are good, they're not bad systems, it's just, I feel like SQL Server, based on what they've talked about publicly, it seems like this thing is way farther ahead than everyone else. Again, I would say for all database systems, open source and commercial, SQL Server probably has the best query optimizer, and it shows here. But let's now look into see a little more detail about what actually happens when you get correct estimates. So for this one, they're going to instrument Postgres 9.4, and the way to understand this graph here is that the x-axis is what the percentage of the queries that they're going to execute are within the, or how much slower are they from the actual execution of the query itself, right? So if you, sorry, how much, let me just sort of, they instrumented Postgres, and they made it so that rather than using histogram to estimate the cardinality of an operator, they modified the system so that this, whatever function it says, go estimate what the cardinality is, they replace that with a magic oracle that always gives them back exactly the correct answer every time, right? So the way to read this is it's how far they are from what the real estimate is going to do versus what the query performance will be if you have the exact estimates versus what if you use the built-in cost model, whether it's making approximations. So if you're in this band here, 0.9 to 1.1, means that the performance of the query using the approximations is roughly the same of what you get when you have the exact result. And then over here, you're getting way, way, way slower as you go in this direction. And then this is what percentage of the queries and the total number of queries that they gave into the system fit into these different buckets here, right? So this shows you that when you're using estimations, that 60% of the queries are 1.1 or great more time slower than the queries when you have the true cardinal, the exact estimations here, right? And so what's going on is because Postgres is underestimating the cardinality of its operators. It thinks that the number of tuples that it's going to pass from one operator to the next is less, is lower than it actually is. And they use these cardinality estimates to size the hash table for when you do a hash join, right? Or decide whether you even want to do a hash join at all, right? If you're only going to access a small number of tuples and a join, then a nested loop join is super fast. Because you don't have to set up a hash table, you don't have to build it, you don't probe it. Just do these two little for loops on like four tuples, and the outer table and the inner table, that's as fast as you're going to ever get. So Postgres ends up because it's underestimating the cardinality of its operators to say, you're operating one with ten tuples, nested loop join, right? And then it starts running and it says, shit, this is not ten tuples. But by that point, the query plan is baked, right? You can't switch back to do the hash join, right? Why not? That one you'd have to do adaptive query processing, right? So you have to be able to say, my query optimizer made a mistake. Go back and rerun the optimizer and get a new plan based on something, based on what data I've seen so far. But nested loop join and hash join get the same result. Say it again? And nested loop join and hash join get the same result. His statement is the nested loop join and the hash join get the same result. Right, but like, so you could do it the way, actually, one way to do this is that if I see now the as, if I see that I have, I thought I was going to have like ten tuples. So now I have one billion tuples coming in. Before I even start the nested loop join, I could say, don't do nested loop join, switch over, do a hash join. You could do that in some ways. It depends on how they're pipelining tuples, but they don't. It's an engineering thing, right? It's sort of like once the optimizer makes the decision, they go with it. Now, adaptive query processing or optimization is when you say, I think the optimizer made a mistake, go back and re-generate a query plan and now you have to get into this world of like, do I throw away all the data I've processed so far and start up from scratch? Or can I come up with a new query plan that can use some of the data I've already processed and just continue with that? That would essentially do what you're proposing. But as far as I know, Postgres doesn't do that. I don't know actually what SQL Server and Oracle do. I think they throw everything away and start over. You primarily do that for join ordering. Switching between nested loop and hash join. There's no reason you could do it. I mean, Postgres doesn't do it. I think for engineering reasons. Okay, so in this case here, again. Things are running slower because a lot of queries end up being nested loop joins when they really should be hash joins. So the next thing they did was, in Postgres, you can pass a flag to say, sorry, yes. So the leftmost part in this graph is that some queries actually run faster and even false, kind of like this, than true one. Yes, but I don't know why. Okay, I don't know. We can ask Victor, I don't know. It was to error one way, error the other way, the error is handled like, two wrongs make a right, two wrongs make a right. Okay, it's just noise, I don't know what you're saying. Like the error from the first thing fed into error in the second part. Which turned out to be really good. Got it, okay. So he said the error for the first join operator fed into the first join overestimated, the second join that it fed into underestimated, and then that came out to be exactly correct. Now why this is running 0.3 faster, I don't know. But it's pretty low amount, it's one or two percent. All right, so what I'm saying here is that the first assessment of why things are running slower is because it's picking nested loop join when it's picking hash join. So in Postgres you can pass a flag in your session, like you open up the terminal and you can say set no merge join or something like that or no nested loop join. You can tell the optimizer to not even consider a nested loop join for your query. So in this case here, it only considers a hash join. But now you still see that you're still getting worse performance, right? Then where you should be if you have two cardinalities, right? It did help, right? Few queries are getting picked as nested loop join, but still some queries are still running slower. In this case, it turns out that in this version of Postgres, they were using the cardinality estimates from the operators to decide how to allocate the hash table when you do the hash join, right? So you say, I'm gonna do 100, I have my cardinality is 100. So make sure I have a hash table that has 200 slots to put things in. And so if you undersize the hash table, what happens is that as we talked about, you end up with these really long, I think they were doing a bucket hash table. So you have these really long bucket chains that essentially becomes a sequential scan every single time you do a probe, right? So, again, if you had correct estimates about what the cardinality was, then you could say, all right, my hash table needs to be this big, if my data set's coming in, it's gonna be this big. And then you don't worry about these long sequential scans. So to prove that this was actually the case, okay, this was Postgres 9.4. Then in Postgres 9.5, they had the ability to dynamically resize the hash table if your estimates go wrong. So they back ported that feature from Postgres 9.5 into 9.4. And they re-ran the same experiment. And now you see that there's more queries that are actually getting closer where you should be if you have the true cardinality, right? So this is a good example of showing that it's not just picking whether one operator should be a hash join versus a nest loop join. It's actually what you're actually doing in that operator can be greatly affected by the estimation that your cost model's making, right? So Victor then, he and I were talking about this, and he sent me sort of a synopsis of what he thought were the most important things that came out of this experiment or the study that he did. And the first is that they felt that having an accurate cost model from your query optimizer ended up actually being, in some cases, more important than having the fastest engine in the world, right? Like, who cares that we can do SIMD processing or query compilation and all the other tricks that we talked about the entire semester?  When we actually throw real-world data at it, then we're just gonna get crushed. So being able to pick up the join order is probably the most important thing from all of this. The other thing they found was basically that the cardinality estimates are always gonna be wrong. So when you actually implement the operators in your system, you wanna have them be adaptive enough to not, or adaptive so they don't have to rely on estimations coming from the query optimizer. Cuz you just assume that's gonna be wrong, and as the data comes in, you wanna be able to adapt whatever it is your system's doing to account for the actual data that it's actually seeing. So you'd be able to resize the hash table automatically, rather than just taking whatever the cost model gives you and just fixing the size to be exactly that. And we're doing this now in our own system. We haven't pushed it to the master branch yet. This is in the separate LLVM branch. But we can reorder like predicates. So some predicates are more selective than others. The cost model might think that you wanna execute your predicates in this order, we can then shuffle things on the fly as we see real data. The other things that he said that, and you sort of see this in design about in Hyper, is that having an engine that can do fast sequential scans and fast hash joins may actually end up being better than having all of these sort of fancy indexes to do joins and lookups, right? Cuz the more indexes you have and the more complex the estimations have to be for your cost model. So rather than try to account for any of this, you just say, screw it, I'm gonna sequential scan everything and just rip through the data really fast and who cares whether an index would help me here. For analytical queries, I maybe agree with this for some things, maybe not for others, right? I have mixed feelings about this one. The last one he says that trying to have a more accurate cost model, like using the microbenchmark stuff that I talked about at the very beginning, like trying to profile the hardware and include that in your estimations. They felt that that was a waste of time. Just having better cardinality estimations is the most important thing. So that means having better statistics, better sketches, whether you're throwing deep nets in there or not. We could talk about that separately. But getting this right is more important than having sort of more fine grained accuracy of what the hardware section can do, okay? So I thought these were pretty useful, right? Again, some of these we've adopted in the design of our system, other ones not so much. All right, so the last thing I wanna talk about, and this will lead us into what we'll talk about on Monday, is this project from IBM from, I guess this point, 2001. So 18 years ago for this thing called Leo. So you may be thinking, and it's sort of what he was sort of suggesting earlier, is that if my cost model is gonna make these estimates and they're gonna be wrong, then as I run my query and I see the data is actually completely different, can I just fix myself? Or can I just possibly also go fix the estimates, right? And this is what IBM was trying to do with this thing called the learning optimizer. So the idea would be that my query shows up, I run it through my query optimizer, the cost model generates estimates about what it thinks the data looks like. I then run that query, and then now I observe are the estimations about the cardinality and the selectivity of my predicates. Is that matching what I'm actually seeing in the real data? And then when the query finishes, they check to see whether the estimations differ from the real data. And if they differ, then they try to feed back the real data back into the optimizer, so that when the next query shows up, they can rely on the data they've already collected from the previous query, right? So this seems like this would solve this problem, right? It's like, our system is wrong, we run the real data, see what actually happens. The, I would say that every DB2 administrator that I've ever talked to and I ask them about this, that they always say that the first thing they do when they install DB2 is they turn all this off, because it never worked. And we had Oracle has something similar to do memory management, like automatic memory manager for the buffer pool manager. And we talked to some DVAs a few weeks ago, and they're like, yeah, we turn that off immediately. Like all this automated stuff, n***, right? So I never found out why, I've heard there was some engineering difficulties at IBM to get this thing to actually work the way they wanted to work, and fit into the rest of the system correctly. I think this didn't work because of engineering reasons, and it's a shame because it seems like this would solve our problems. But because of this, I think a lot of people, a lot of these, a lot of commercial systems have been hesitant to adopt similar techniques, just because this thing sort of fell apart. But this then leads us into what we're going to talk about on Monday, of like the sort of revival, or not a revival, but a continuation of a long history of trying to do automated tuning in database systems to sort of alleviate some of these difficulties, right? So now what's in vogue is machine learning, and the people trying to apply machine learning to these problems. But it actually goes back into the 1970s. People have been working on this problem for a long time. So this is just sort of one example of this that didn't work. Okay, so the main takeaway today is that for an MRE database, being able to estimate the number of tools that we're going to process per operator is going to be for us a reasonable approximation of what the extrusion cost of a query is going to be. Of course, now that means that in order to estimate the number of tools you're going to process per operator, you got to know what the cardinality is of your children operators. And then as we showed, things can go bad pretty quickly. And so I think the way Microsoft does the cost estimations is using how many channels sampling and sketches is the right way to do this. And we tried doing this in our own database system, but we never vetted it to determine whether it was actually accurate. And what will happen is in the summer when we bring over the old optimizer from Peloton into the new system, we're probably not going to bring over the cost model, we will start with a simple cost model that basically says, if I have an index, my cost is zero, if I have a sequential scan, my cost is one. That's the simplest cost model you could ever have. That won't handle join ordering for us, but at least that'll get started on being able to pick indexes, okay?


Hey, this is Christian Buckley with another MVP Buzz Chat. I'm here talking with Jonah. Hello. Yeah. Hi, Chris. Really great to be here today. For those that don't know you, why don't you introduce yourself, what you do, and where you're located? Yeah. Sure. My name is Jonah Anderson. I work as a software engineer and IT consultant at a forefront consulting company here in Sweden. That's what I do as my day-time job, and I code. I'm a .NET developer and I love coding with Microsoft Azure. Yeah. Remind me, your MVP, is it Developer Technologies? No. It's Microsoft Azure. Azure. Okay. Yeah. Excellent. It's funny as a Microsoft partners, like I talk Azure numbers every day, not the details of the technical aspects of it, but as a partner, I mean it's a huge part of my day, co-sell activities and talking about Azure consumption with customers in our own organization, and so it's just become part of the daily grind, always talking about Azure. Yes. But I actually aim also to have Developer Technologies because I also love programming, like maybe create content for C-Sharp or .NET which is also really good and helpful for other developers. So I'm not sure. I think it's possible to have two categories. It is. There are some that even have three. I can't fathom the amount of content and activities that you have to be able to hold down three. But yeah, actually, yeah, it's interesting that there are more and more that have MVPs that have two and for those that aren't aware, I mean to become an MVP, I mean obviously there's a black box of a process, like there's no one way like, hey I've done all these things that therefore give me an MVP award. It's up to Microsoft's discretion, but typically it's a lot of blogging, a lot of speaking at online and in-person events, it's a lot of involvement with your local community, all those things, and I'll let you get into your experience. So think of that as doubling that volume, speaking a lot on multiple topics to be able to earn that dual MVP, but it's pretty impressive feat for people that are able to do that. Yes. It's not my ambition right now, maybe in the near future, but right now I'm satisfied to have the MVP award for Microsoft Azure. So as you said as well, I didn't know actually, I started sharing and public speaking and blogging about Microsoft Azure. It's just about like for the past year, that's why I got the MVP award. And to be honest, I didn't know that Microsoft MVP award existed until someone who interviewed me in the podcast, had a friend that worked in Microsoft said, that Jonah, you're already doing MVP stuff. You should be an MVP. And like someone in Microsoft just nominated me, I submitted all the contributions that I've been doing for the past years. And it takes a process, takes time. And there's an interview, there's right. Yeah, that's right. And then you have, it's not just about contribution. I know that you've been an MVP for many, many years. I've seen your MVP profile and you have a lot of great content. And I found out after I talked to, I had an interview that being an MVP is not about sharing content, it's also your passion to help the community. And that's what I love and what I'm passionate about. So it's just like the MVP award is like a token of what I've been doing. So I'm really happy. Yeah, well, it's, and I've said this again and again. It's that, and I think when you and I were talking last time, we kind of said the same thing is that, you know, we would do the same things whether or not we had the MVP. Like I really enjoy this process of going and learning about things and then sharing what I've learned about that. I love doing like this interview series. I love hearing what other people are doing, novel approaches to the same technology. So even I'm, my MVP is in Office Apps and Services. So I started as a SharePoint MVP in Office 365. And now teams, I do most of the content around teams and all of that. It's all around collaboration technology, which is such a broad topic, even when you talk Azure, such a broad topic of focus areas within Azure, what you do. And so it's, it's not surprising. I'm sure we'll see, like that'll get divided two years from now. There might be, you know, five new very specific focus areas within Azure, for example, I just randomly pick that number. I don't have any insight of you. Someone will ask me, but it's like, what five areas do you have you heard are going to be split, you know, Azure split it to like, no, I randomly picked that number. I just, as an example. Yeah, I agree with you. It's Microsoft Azure is a very broad, like technology, like as a developer working with Azure, it's also like a lot of things to learn, to choose from. That's why when it comes to certifications because they also recently cleared the Azure developer associate certifications and the fundamentals, it is important to choose what kind of role-based certifications that you want to have that will help you in your day job. So, yeah. Well, that's part of what's fun too. I mean, there's a lot of opportunity for anybody. For somebody who's saying, hey, I'd love to find out more and become an MVP. I've had a number of people that said, oh, it's my goal to become an MVP. I was like, well, that's great to have the goal. But these were people that, in fact, one person in particular I'm thinking of who said that two, three years, he was trying to become an MVP and where he actually came at the end of that process and said, you know, he was very active in leading this user group, was part of the board there, became the president of the user group, was consulting on it, was speaking at, you know, events every month, writing a lot and doing all that. And he said, you know, I've just realized that I don't care if I ever get the MVP. It's been so rewarding. The connections that I've made, it's helped my career and do kind of all those things. And like, I'm not kidding, a month later, he got his MVP. So he was surprised by, he didn't realize he was still, he had had the interview and all of that, but still there was the selection process. It doesn't mean that, hey, you've been interviewed, you've provided the last year of all the activities. There still has to be an opening that has to be, the timing of it could change. And so it was great to see that happen. But I think that's kind of the point. What he realized is that the benefits of doing, of being part of the community, that's what it's really all about.  And yeah, it's great to have the access and this other community thing that has the recognition around it. But the greater benefit comes from just participating in the community. Yeah, I agree with you. It's not just like collaborating and sharing knowledge and feeling empowered by the entire community, but it's also you yourself, like as you speak, as you share, as you blog, you learn as you share about Azure, as you share about your knowledge to others. So it's like a two-way and it's really, really great. And before I got the award, I, a few people already told me that you're already an MVP for us, Jonah. So when I was waiting for the process, like for the decision, I was like, I'm going to continue what I've been doing because I love what I do, just like your friend. So yeah. Well, so what's the, so what is the kind of the latest things that are going on in Azure? Like what are you passionate about right now? What are, what are kind of the topics that you're speaking on and writing on? Yeah, lately, especially for the past months, I've been speaking a lot about serverless, developing serverless with Azure functions, specifically with durable functions, where you as a developer focus on creating some, creating event-driven solutions and functions as a service through Microsoft Azure, using your favorite programming language. And for my case, it's C-Sharp and .NET because that's where what I do is the daily job. So I've actually, in April this year, I've spoken seven public talks online. And I think half of them are all about Azure functions. And lately, I've been also developing Azure functions or durable functions in different patterns because there are different patterns that that technology can solve. Like you can perform like stateful functions and run it parallel and you get the result. So I'm trying to work a project where I can develop it with integrations with different APIs like send grids, Twitter and like a Cosmos DB. And lately I've been posting a lot about it and some of my contacts, new contacts at LinkedIn, they're interested to get to have a content about how to protect your serverless functions with Azure Key Vault. So that, I haven't tried that. So I'm learning that so I can share. That's very cool. So what kind of customer solutions are you developing with these? Yeah, it's actually, you mean for Azure functions? Yes. Yes, it's a function as a service. So it's actually like specific to the backend part of your application. So if you want to connect, it's mostly use, it's not suitable for all type of business requirements. It actually depends on your backend service talking to APIs. And like, I don't want to get too technical on this talk. But I can share some links. Well, I noticed it's interesting we have people that aren't working with Azure and to understand some of the business requirements that drive some of this kind of development. So what are the customers actually asking for? The customer doesn't line up and just say, well, would you like you to go and develop a solution using Azure functions? But it may be expand on the types of customer solutions that you work on that you're building as you use this technology for. I think it's more useful when you want to create a backend service that connects to the APIs. But as for the business part, it's actually like depends on like, for example, if you want to create a function as a service within Azure, but you want your developer team not to think too much about infrastructure because Azure is taking care of that. And the one of the advantages of serverless in the business scenario is that you can pay as you go and it creates productivity for your development team. And you can scale out and off the scale. And the advantage of that is actually you can create long running processes in your application. So it is something that you integrate with existing applications or new applications. And it's like Azure functions empowers it. It depends on what you need. I hope I explained it in a way that you understand. I'm sorry. It's all right. Some of the other events you've been participating in, do you have anything else going on this year? Are you doing any in-person? Do you have anything on the calendar for the year? Like what's the outlook in your part of the world? Yeah, for the past year I've been doing it virtually, but I submitted some proposals for in-person talks. But I'm not sure how it will be considering the pandemic that we have right now. But I really missed traveling and meeting the community. Well, that's the hardest part about that. Even with like I have my first back face in-person event. It's a hybrid event, but it will be in August. And I think things are fairly opening up here in the US. So I think it's not a question. Like it'll happen. It'll still, it's yet to be seen. Here's an event that typically brought in 400 or 500 people in this annual event. Last year there was about 100 that were in-person. And so whether we get back up to the 400 to 500 number or not is a question. And then there's one that I'm sure will be bigger. It will be in Las Vegas in December. But those are the two main ones that I'm looking to go and do. So I'm sure you're in the same way. Very anxious to get back and see actual life human beings. Yeah, I have a question. We're talking about public speaking in person. Have you been in Europe to do some public speaking? Or do you do it from time to time? Because I would love to meet you in person and listen to your talks. So I usually, for the last 10 years, I'm probably over in Europe five or six times a year for different events. So yeah, my last time there was the European SharePoint Conference was in Prague in December of 2019.  So I was on the road in January. And then I did an event in February of 2020. So yeah, I hope to get back over there. Then obviously, I mean, the other thing we're waiting for is a new MVP. One of the, it is a huge perk is the MVP summit on campus over in Redmond. It's fantastic experience. And if nothing more, for those that haven't been an MVP and are interested, I mean, one great thing about it is, you know, we all kind of congregate on campus there. It'll be interesting to see if they do another hybrid or if they do, it's been online the last two times, but whether they do a hybrid event and include people that are remote as well as the in-person activities. I suspect that's going to be the direction that Microsoft goes, that they can include more people who still can't travel but have the in-person activities. But it's almost like being at university. So while you're surrounded by the people that are part of your area, your focus area, so for me, you know, SharePoint, OneDrive, Teams, Yammer, kind of all the products that are the collaboration related things. But you have the opportunity, like I did, the last time we were in person, to go sit in an Azure session, to go and sample these other sessions, meet other MVPs in other areas, and interact with the Microsoft product teams. It's just, it's fantastic. So highly recommend that. Yeah, I would love that. Hopefully my first summit will be in person because I'd like to meet many great people that I follow already, like even before I became an MVP. I like learning from experts. And it would be nice to meet all of them and you, meeting you as well. And I have a question for you. It's like I've been interviewing you as well. Yes. You've been an MVP for many, many years, like so you've been to summits many times, you gain a lot of close MVP friends for the past years being an MVP? Oh yeah, for sure. I mean, it's a great networking vehicle. Again, it's depending on your area of focus. And even, I mean, you'll probably get to know the other Azure MVPs, but you'll start to meet people.  And so I've been, this will be my, with this rule cycle, it'll be 10 years that have been an MVP. And of course I had plenty of friends that were MVPs prior to that. And I was at Microsoft prior to that and knew some MVPs while I was a Microsoft employee as well. So I see the familiar faces, but, and there's also the thing where, and I'm sure you'll experience this plenty too, is that where I know people's faces from their Twitter profile picture, or their, you know, I know them from online activities, but then I remember it was like, I've never actually met you in, you know, in the physical form. So it's great to have those, those interactions. But yeah, you can't walk away from an event like that without just a handful of new business cards and contacts. And I mean, I, there are people that I'm, I've remained friends with that I met like that first year. So yeah, it's, it's a great, it's a great experience. It is a great experience in rewarding to meet great people. And that's one of the most rewarding things of being an MVP. You get the connections that you meet, the stories that you hear from different people and you learn from. Exactly. Well, well, typically people who become MVPs, we are super connectors. We are people that love to network. And if I don't know the answer to the question, like I know several people that probably know the answer. And I'm happy to put somebody in touch with those people. Having said that, there are those people that will attempt to abuse that, that process. But yeah, so, so people who have a legitimate, hey, I'm looking for help in a certain area, or I have these questions, it's like, please reach out.  And again, I'm happy to point people towards the people within my network who might be able to solve that problem, answer that question. But it's like at the end of a presentation. You know how this is. We just say if there are any questions, and then it's silence in the room. And we like to joke and say, it's because my presentation was so succinct, and I've answered all questions. Like no, it's, you know, don't feel bad about that. Some people are shy, but feel free to, here's how you email me, find me on social media, but reach out afterwards. And always happy to make new connections that way. Yes, I agree. That's really great that we can connect with others. And I would like, related to that, I would like to share that when I was a girl or a young kid, I was actually very shy. We're talking of shyness. So I used to hide behind my mom when it comes to public speaking and schools and presentation. But for some strange reasons, when I started working and became adult, I learned to like, I learned to get out from my closet and share what I have to say. And I don't have experience with public speaking like professionally, like went to school for that. But I usually speak from the heart and what I know. So that's why that's when you feel confident when you speak from your heart. Because sometimes when you read by like, if you memorize too much, that's when you forget. Yeah. Yeah.  And I don't feel that way. So I'm a strange breed. But for me, so many years ago, over 20 years ago, 20 years ago, I was in a band. I was a singer for a band. So I think being on stage and we played every weekend for a couple of years. I mean, we were sometimes twice, you know, Friday and Saturday nights. And I think being up in front and singing, you know, songs that you wrote and lyrics that you wrote, that just kind of burned off the stage fright for me. And so getting up and talking about technology, again, about things that you're passionate about, things you're excited to go and share. And I tell stories when I, when I present. And so I'm not nervous when I'm sharing, when I am passionate about what I'm, you know, had personal experience about. Yeah, I agree. Because that's how you connect with your audience, with the people that are listening to you through by being genuine and sharing a story that they can learn from also. Like it can be, like it doesn't have to be a perfect talk about a specific topic. It's just like as long as you share your knowledge, maybe a mistake's learned from a bad experience. Or for example, I had a tech talk where in, I think in December, one of the talks that I had was, I shared my lessons learned from a migration that I did from an old dotnet migration to Azure. So I had that experience and I shared my lessons learned and what, what I should have done in that situation that I shared to others. So it was like a talk that was popular and it was good to talk it because it's like from the real experience. Yep. You know, it's funny. I just made me think too that I, so I gave a presentation a couple years back. I was down in Melbourne, Australia. And just as I was getting started, I had like went through like my title slide, slide that had my contact information and picture on it. And then like the table, like the contents of what I was going to cover in the session. And then the screen went blank. My laptop went blank. What happened was the video card in my laptop failed. So we couldn't, we couldn't get it back.  And so we spent about five to seven minutes fidgeting, trying to figure out what's going on.  We're 10 minutes into it already. I said, so I just, well, technical team was poking at it. I just started going through. I knew the material enough. And so I gave, I gave that entire presentation for an hour on memory, but like this, I knew the stories that I wanted to tell about it and the experiences and the major points around that.  I'm like, you'll get the slides. I'll make them available once I'm able to retrieve this.  It's like, that was fantastic. Like I got so much out of that. And that again, it speaks to, we sometimes, you know, you can close your eyes to whatever's showing on the screen and get the points from the, from the speaker, from the presentation. And I mean, if you can, not that I ever want to do that again. But you did conquer the challenge. You deserve the standing evasion and that. For people to get the value out of that, of what I intended to do even with the visuals up in place. I mean, that was very rewarding for me. So that wasn't anything. I don't look at that as the, hey, my skills as a speaker. Like I limped through that, but it does speak to your passion comes through knowing your material and the points that you want to communicate. And then I answered a lot of questions as I was talking and people were asking questions. It was more of a conversation, which I think personally, the best presentations are more of a conversation than they are. Hey, let me just dictate this information. Yeah, I agree. I agree with you. And I never want to do that again. Yes, but, but if ever it happens again, you know, we can control technical problems. Then if ever it happens again, you have the experience to conquer it again. Yeah, well, hopefully it's not. So that's always the danger. If you have a presentation that is heavily demo centric, like what do you do then? I understand. I, one of my recent talks, I usually do presentation first and then do demos and show my code project. And when I was presenting, my code didn't work when I did live demo. And it was like inside of me it felt kind of embarrassing that I had to say sorry to the audience and then the organizer or the host said, you don't have to say sorry for technical problems. Yeah, so that's one of the things I learned. People have become more understanding too, but think because think about it, like everybody is doing the web meetings. And so everybody with the volume that we're doing, everybody has been through the technical issues now. So I think there's a lot more empathy out there for that. And so that's again, if you're making it more of a conversation, it's more of here's what we did. I mean, I actually, I love when that happens, not. I know it's painful for the person presenting, but when that kind of stuff happens, we're like, hey, they're human after all. Yes, I agree. I agree. We work them up in our minds to be these superheroes that they know they can answer any question. But I also, that's why I also appreciate when people say, it's like, you know, that's a great question. I have no idea what the answer is, but let me, let me go figure this out. Let's take that offline or let's go see who we can ask to get the answer to that. So don't attempt to answer, just guess something, but to honest about, yeah, not knowing something. That's okay. That is really, really great advice. Yeah. Well, there's so much that I don't know. I'm, I'm, I can honestly say there's so many things I don't know. I think we all, we, every day is a learning opportunity for all of us. Like we think we know everything, but there's a lot of new things to learn from, from the technologies that we have and from others, the new people that we meet. Yep. Exactly. Well, Jonah, really appreciate your time talking today. It's great to connect with you and get to know you. And for people that want to find out more about you, what are the best ways for them to reach you to find you? Yeah, to connect with me, they can find me on LinkedIn. My name is Jonah Anderson there, and I'm also on Twitter, CJ Kodare. And I also have a website, JonahAnderson.Tech, so you'll find everything there. And yeah, thank you so much, Christian, for having me here. And really great talking with you. You too. And of course, the links and everything will be over on my blog at BuckThePlanet.com, as well as in the description here for the YouTube video and out on the podcast. So thanks so much for participating. I hope to see you at an event soon. Yeah, same here. Yeah, thank you so much.


So, everybody needs air conditioning. It's 120 degrees out here daily to support everybody's mission. We clean the filters, the coils, inspect the fans, ensure the board's clean, and every component's looking like it's supposed to. Just doing an operational check of the unit and verifying the unit's performance. A lot of people that need air conditioning, we provide that by doing preventative maintenance on about 10,000 air conditioners, whether they be environmental control units, like what's behind me here, or split units and package units. Out here we provide support for maintaining common equipment, food and perishable items, medical equipment, and then your sleeping quarters. So, if there's a difference in air, HVAC was there. Stay cool.


Everybody forced here ripping 21 22 Don Russ optic basketball choice five bucks number one Random team style you can always check the results of late in sports cards calm. Good luck. Everybody here. We go All right, one auto per box you get a red and green which is not numbered per box a Choice red to 88 to red rated rookies. I think and a silver if I'm not mistaken one hollow two exclusive choice prisms High-risk how reward break right here a little amount of car and silver T. What was Malik Beasley? Go T wolves got a Kings optographs red choice Nate Archibald none numbered Kings were the first hit red and green rated rookie Alper and Shen goon Nice one Rockets. These are not never but these are the One a box red and green nice Shen goon. You go clippers rated rookie red key on Johnson 14 of 88 A nice one clips color match rated rookie red Aaron Wiggins thunder and Isaiah Jackson Pacers. These are not numbered. They're so close to me another red. I think the other ones a little brighter They're very crazy. If not, maybe the same. I don't know But the rated rookies will always be two red on the back and then the middle it might not be radar You know I'm making me something else silver look at Donchich Mavericks Cavaliers Evan Mobley rookie red choice optographs Nice hit Cavs Trying to read here Rudy Rudy with the Cavs. Congrats on the hits. We'll get a mag for you Cavaliers red and green Darius Garland. Nice Starland Dang dang next to him Just I think that might just be the car. I think it's just a mojo parallel with the car design Okay. Yeah, that's not a thing. I thought it looked like it was for a second. There you go Cavs Looks like it. Well, there's no there's no bend in it. No, that's just the dude's whoever's defending him. That's their arm Okay, see it. That's their arm back in gold Paul George One of eight clippers Congrats on the PG-13 What a box Clips man also had the key on in the first box Crazy man clippers crushing it Pete Shen and Choice rated rookies Kate Cunningham. There you go Pistons and a Joe Weisskamp That was a crazy good box Congrats to the Cavs. Congrats to the Clippers Darvish got out of it. Silver Hawks Trey young Ice Trey Mavericks auto Willy Kali Stein optographs choice red non-numbered Red and green Pistons rated rookie Luca Garza Another Clippers numbered card 11 of 88 Brandon Boston jr. Every single numbered card has been a clipper so far Clean sweep on the numbers 11 of 88 Brandon Boston. Okay. You gotta do side-by-side here. Next one is rated rookie red Non-numbered Scotty Lewis. That's the same right? How do you differentiate your Hornets and a David Johnson rated rookie for the Rockets? Careful with buying these cards in eBay guys Make sure you're not under or overpaying on something silver net James Hardin Lakers rookie optographs Austin Reeves Not a number. You've got a red and green Rockets Kenyon Martin jr. And a non-clipper Heat Jimmy Butler 73 of 88 on the red choice. There you go Matt Miami Chase deal with the heat red Jimmy Butler color match Choice rated rookies Sunsy Aldama Grizzlies and a Josh Getty Thunder Last box No way illegal. Don't you say those words? You don't know Sun silver Deandre Aiden Grizzlies optographs red choice Tyus Jones Green Dragon Blazers Norman Powell on the short print love the green dragon. Oh another Devin Booker 52 of 88 that was a bonus card then. Oh No, that's in place of the red and green never mind never mind. That's a place of the red and green Those are sick either way Devin Booker 52 of 88 sons got lost here six cards. I got lost man Nick's rated rookie Quentin Grimes and a magic rated rookie Franz Wagner Pretty good break that'll do it everybody. We've got some more of those coming up next


In this video we're going to talk about the LU factorization of a matrix. Now suppose we have a matrix A which is M by N, it does not necessarily have to be a square matrix, any size of matrix is appropriate here. So let A be an M by N matrix which has an echelon form which can be obtained solely by replacement row operations. So we can get from A to its echelon form which we're going to call the echelon form U, it'll have the same dimensions that A does of course, and if we can get there with only using replacement row operations, then there's going to exist another matrix L which is going to be M by N, this one is a square, such that A will factor as L times U where what conditions can we expect for the matrices L and U? Will U will be an echelon form of A that we obtained from these row replacements? And also L is going to be a lower unit triangular matrix. So remember that what that means, lower triangular means that everything below the main diagonal will be, well everything above the main diagonal will be zero I should say. So unit triangular means we'll have ones along the diagonals, we can have anything else we want below the diagonal, whatever, but we'll have zeros above the diagonal. So we get this unit lower triangular matrix and in particular the numbers that are going to be below the one diagonal there is going to come from the replacement operations we do. So whenever you do a row replacement where row I is replaced with row I plus C row J, you're actually going to put a negative C inside of the IJth position. So the numbers below the diagonal here come from these row replacements. And the argument on why this factorization exists and this is called the LU factorization, not a very clever name but it's what's commonly referred here, the proof behind the LU factorization really comes from the elementary factorization we had done in the previous lecture. So when computing an echelon form of a matrix the scaling operation I just want to mention is never actually needed. When you look at Gauss-Jordan elimination, scaling is not required until the backwards phase. The forwards phase does not require scaling whatsoever. Sometimes interchange might be necessary in the forward phase but like we said for this for this theorem here we're making the assumption that interchange is not necessary and I'm just making the point that scaling matrices is never necessary to get into echelon form. So suppose that A reduces to an echelon form U without any interchange whatsoever. Then there's going to be some sequence of elementary row operations. So they're going to be replacement operations that transforms A into U and let's say there's P many of those. Now each and every one of those row operations will correspond to an elementary matrix. So let's say that the first elementary row replacement corresponds to the matrix E1, the second one corresponds to E2, the last one corresponds to Ep until eventually we see that we have this factorization that Ep times Ep minus 1 all the way down to E2 E1 times A is going to equal U. Now if we multiply by the inverse matrix on the left side we can move this product of elementary matrices to the right hand side and we end up with the statement that A equals the inverse of the product of all those elementary matrices times U. Then of course if you take the inverse of a product the shoe sock principle comes into play.  That will reverse the order of each of the elementary matrices so now E1 shows up first then E2 and then Ep's at the end but we take inverses of each and every one of these things. Now the inverse of a elementary matrix is an elementary matrix and in particular if you have an elementary matrix of replacement type its inverse will be a replacement type and that's why we have an inverse C that shows up here because we perform the operation we added C times row J well because of the shoe sock principle you can actually be taking the inverse of C and so then we're going to define L to be the product of all of these elementary matrices. Now if you have in the forward phase if you are doing an elementary operation which is replacement this is going to put a number below the main diagonal because you're taking a row from above and adding a multiple of that to a row below so each and every one of these elementary matrices is going to be a forward phase replacement matrix that these are all going to be unit lower triangular matrices and as we talked about previously the product of a unit lower triangular matrix will likewise be unit lower triangular and I shall also mention the inverse of the unit lower triangular matrix is a unit lower triangular matrix therefore the product of of these elementary matrices L is going to also be a unit lower triangular matrix and the coefficients the scalars inside of that matrix are going to be determined exactly by these elementary row operations we talked about here so the reason why it's so often important to go through proofs of mathematical statements is that the proofs illuminate on why it's true and it often gives us clues on how it is true that is it gives us the proof here actually gives us an algorithm for computing the LU factorization of a matrix so the first thing to do is to compute you know to start with your matrix A and you're going to row reduce it to find your echelon form using only uh not backwards phase what why is that saying that we need to be doing forward phase uh row replacement operations uh no interchange no scaling whatsoever so row reduce A into U once and then key track the row operations you did and while what when you get to U then you go back and you can look through the row replacements you did and so for each time you do the replacement row i transforms into row i plus c row j you're going to put a negative c in the ij position and honestly i do this at the same time and i want to show you in an example how we can do this so consider the following four by five matrix A we're going to work over mod 11 in this example uh switching the field from the real numbers to the complex numbers to the finite field zp or any other field it doesn't really make any difference on how this calculation is going to go so because the matrix A has four rows the uh the matrix L is going to be four by four uh and then the matrix U will also be four by five the echelon form will have the same shape that A does L though will just be the number of rows because we're on we're multiplying on the left of U so it needs to be four by four so what i'm going to do over here is you're going to see to the left the sequence uh we're going to see the sequence of reduction from A to U now U just has to be any echelon form and so we're going to grab grab U to be the first echelon form um that as we broke reduce A right here L is going to be this four by four matrix and what we know about L is the following it's unit lower triangular so we have ones along the diagonals it's lower triangular so everything above the diagonals is going to be zero the stuff that's below the diagonals we don't know what those are yet so we're going to determine that through our row reduction here so this right here is just our original matrix A unaffected so the first thing we do to row reduce it again no interchange nothing like that's possible here we're going to first put a pivot position in the one one spot and then we have to get rid of all the numbers below so how are we going to get rid of the seven that's down here well to get rid of uh to get rid of the seven what we would have to do is we have to take seven divided by two we're going to subtract row one from row two in that regard but what is seven over two working mod 11 uh we could say add 11 to seven that would give us 18 over two which reduced to nine mod 11 so we're going to take row two minus nine times row one that's going to take care of the seven that's below uh the next one how do you get rid of the two right here that's pretty easy you're just going to take two minus two so we'll take row three minus row one and then for the for the five right here together the five we have to take row four minus five divided by two row one but what is five halves just like the seven i'm going to replace the five with five plus 11 which is 16 over two that reduces to eight and so we're going to subtract eight times row one to cancel those things out there and these this this observation here is critical because we have row two minus nine row one we're going to add a nine in the two one position we're taking the opposite of the negative nine we have right here uh because we're taking row three minus row one we're going to put a positive one in the three one position because again we take the the additive inverse of this coefficient and lastly because we have row four minus eight times row one we're going to put a positive eight right here if you always think of your replacements row i minus c times row j if you think of that way then you're always going to put a c inside of your matrix the opposite of the sign you have right there so now we actually have to go through these calculations right here uh so notice that if we go through this negative nine when you're working mod 11 is the same thing as plus two row two plus two which is a little bit easier in terms of multiplication so i'm going to take row one and times it by two um so two times two is four notice that seven plus four is 11 that's what's going to cancel out right here uh we're going to take four times two which is eight six plus eight is 14 uh subtract 11 you're going to get a three then we're going to plus 20 right there two times 10 is 20 23 um if you take away 22 you're going to end up with a one uh five times two is 10 plus three plus three is 13 so track 11 would be two and then lastly for the second row you're going to get two times nine which is 18 plus one is 19 if you track 11 from that you get eight all right so that's how that row simplifies uh doing the next one here we're just going to subtract row three from a row we're going to subtract from row three row one so we get a minus two sets of zero uh we're going to get six minus four which is at two we're going to get seven minus 10 which is negative three which is the same thing as eight mod 11 we're then going to get one minus five which is negative four which is the same thing as seven and then eight minus nine that gives us a negative one which is the same thing as 10 mod 11 and then for this one right here uh row four minus row eight again multiply by eighth a little bit bigger than i want to do right now so we're going to do row four um we can replace negative eight of course with plus three three row one and so let's take two times three which is six notice five plus six is 11 aka zero uh you're going to take four times three which is 12 plus zero which is 12 you can subtract 11 from that get a one uh 10 times three is 30 37 if you subtract 33 from it you're left with a four four times sorry five times three is a 15 plus eight uh that's going to give us 23 reduces to one mod 11 and then the last one nine times three is 27 plus one is 28 but subtract 22 from that and that leaves us six behind so that's the first level of row reduction so then we're going to move our pivot to the uh to the 22 position right there and so now we have to get rid of the numbers below it again no scaling no interchange going on right here so if we just focus on the the replacements we got rid of the two and the one that's below this thing right here so to do that we got to get rid of the two so we're going to take row three minus two over three row one but then we think of how do you write two thirds as a fraction mod 11 well two over three you could add 11 to the top uh that's going to give you 13 over three that's not divisible by three so let's add 11 again so we get 24 over three that's an eight and so we're going to take row three minus eight times row two what that tells us in terms of l is that if we take row three minus eight times row two that means in the two three spot excuse me in the three two spot you're going to put a positive eight and then the next thing right we have to do we have to get rid of this one right here how do we get rid of the one well we have to take row four minus one over three row two but one third how we write that in mod 11 is one third we could write as 12 thirds added 11 to the numerator and that becomes a four so we're going to take row four minus four times row two whoops and so that we're therefore we're going to put a positive four right here because we're subtracting four now in terms of multiplication if you want to make life a little bit easier like we saw before eight we could replace with a three row three plus three times row two like so so we're going to take the third row times everything by three so if you take three times three it's a nine two plus nine is 11 so that should cancel out you're going to take eight plus three which is also 11 so you're going to get another zero right there two times three is six seven plus six is 13 which reduces to two mod 11 and then eight times three is 24 plus 10 is 34 which if you subtract 33 you get a one right there um four row four minus four row two i actually think four is a small enough number to do multiplication by my head simplify i'm just kind of keep things easy here um so we're going to take three times negative four which is going to be negative 12 if you add one to negative 12 you get negative 11 which will give you 11 will zero right mod 11 and then you're going to take four minus four notice that also cancels out to be zero uh you're going to take two times negative four which is negative eight plus one is a negative seven which if you add 11 to that you get plus four and then eight times negative four is negative 32 we add six to that that should give us well and if you don't like negative 33 of course or negative 32 be aware that if you added 33 to that that just gives you a one six plus one is seven so we get the reduced form right there and so then the last step to do right here is we then move our pivots to the 33 position we got to get rid of the four below it so we're going to take row four minus two times row three uh notice in this situation you have to take four divided by two and as usual integers that's a two right there no big deal whatsoever so to take to take row four minus two times row three we're going to put a plus two in the four two position right we're taking the opposite of the number we see right here now notice we have constructed our matrix l we filled in the lower diagonal the lower triangular region by using the coefficients from the row replacements now to finish this thing off we're going to oops we're going to take two times four two times two which is negative four excuse me then we're going to get negative two right there so that ends up giving us a five in that position a zero right here and so let's them record what we have if we copy down the echelon form that we've built because this matrix now is the matrix U we're going to copy that down and we copy down exactly as we have it so the first row is identical two four ten five nine the second row zero three one two eight the third row zero zero zero two one and then the last row which we just modified zero zero zero zero five so you just bring down the echelon form exactly how it is that's U and then the matrix L which we were building up here we bring it down on the left L for left there I mean it's actually for lower triangular but that's fine and so it's going to be unit lower triangular so you can see the lower triangular region right here and the coefficients are exactly what we wrote down nine one eight eight four two just like we saw right here and this gives us the this gives us the the L U factorization of a matrix so without any without any scaling or interchange you rover doosh your matrix A into echelon form that gives you your U and then keeping track of the row replacements you do put their inverses inside of the columns going one by one by one through it and that'll construct your matrix L which we see right here and we have the L U factorization