1 00:00:00,012 --> 00:00:04,770 Okay, so we talked about algebraic optimization and then we talked about 2 00:00:04,770 --> 00:00:09,127 decorative languages on top of the algebra. 3 00:00:09,127 --> 00:00:14,567 in order to simply expression and in order to avoid specifying to the computer 4 00:00:14,567 --> 00:00:20,148 exactly how to do that. Right, we want to leave that open and let 5 00:00:20,148 --> 00:00:25,580 the database figure that out. But we stopped at what I call logical 6 00:00:25,580 --> 00:00:28,021 optimization. And what I want to talk a little bit 7 00:00:28,021 --> 00:00:31,778 about the physical level optimization. And what I mean by this is that even 8 00:00:31,778 --> 00:00:34,576 after you specify we hinted at this last time. 9 00:00:34,576 --> 00:00:37,663 That even after you specify the order operations, we haven't yet specified 10 00:00:37,663 --> 00:00:41,545 every detail needed, in order to actually evaluate the query. 11 00:00:41,545 --> 00:00:45,052 Okay, and let me give an example of that. So here is a simplified version of a 12 00:00:45,052 --> 00:00:48,639 query we looked at last time. Where we say for every order, we want to 13 00:00:48,639 --> 00:00:53,020 find all the corresponding items that were part of that order. 14 00:00:53,020 --> 00:00:55,170 And that's it. Last time we had an extra condition. 15 00:00:55,170 --> 00:00:57,879 Oops, I'm actually pointing with the mouse but you can't see that 'cuz I'm on 16 00:00:57,879 --> 00:01:01,218 the wrong screen so. [SOUND] So for every order find the 17 00:01:01,218 --> 00:01:05,963 corresponding items that match. And in last time we had another predicate 18 00:01:05,963 --> 00:01:09,840 down here, and this time I've taken that out. 19 00:01:09,840 --> 00:01:13,410 And so the algebraic plan that this translates into is very simple. 20 00:01:13,410 --> 00:01:16,960 Its just a joint of the two tables, and that's it. 21 00:01:16,960 --> 00:01:18,850 So you think we're done right, we're going to join order an item in or 22 00:01:18,850 --> 00:01:21,432 finished. Or we gotta specify how we're going to do 23 00:01:21,432 --> 00:01:23,231 that joint. And so let me tell you about a couple of 24 00:01:23,231 --> 00:01:26,736 options here. So one, in sort of very high level 25 00:01:26,736 --> 00:01:32,835 pseudo-code, looks like this. We could say for each record I in item, 26 00:01:32,835 --> 00:01:39,108 and for each record o in or-, in order. Check to see if those two records agree 27 00:01:39,108 --> 00:01:45,270 on the order field, on the order attributes, and if so, return it. 28 00:01:45,270 --> 00:01:48,540 And that's, that's a 6 a that's a join result. 29 00:01:48,540 --> 00:01:50,932 Okay. You know they match. 30 00:01:50,932 --> 00:01:55,006 So, fine. Another option is for each record I and 31 00:01:55,006 --> 00:02:01,290 item, insert that record into some sort of data structuring. 32 00:02:01,290 --> 00:02:05,188 Here I'm going to call it a hash table. I'm not to concerned about what exactly 33 00:02:05,188 --> 00:02:08,626 that, that is. And then second, for each record o and 34 00:02:08,626 --> 00:02:12,652 order go look up the corresponding records in that data structure that we 35 00:02:12,652 --> 00:02:17,820 found or that we built and return all the matching pairs. 36 00:02:17,820 --> 00:02:20,147 Okay. And if it is actually a hashtable that 37 00:02:20,147 --> 00:02:23,739 we're talking about. Then this look up could be pretty 38 00:02:23,739 --> 00:02:25,180 efficient. Right? 39 00:02:25,180 --> 00:02:29,092 It could be constant time, amortized constant time. 40 00:02:29,092 --> 00:02:32,044 Right? And so now this one says well, for every 41 00:02:32,044 --> 00:02:36,830 record and item, go scan every single record in order. 42 00:02:36,830 --> 00:02:41,440 And so we have kind of a in squared complexity going on here. 43 00:02:41,440 --> 00:02:45,609 And here we say, well, for every record in item, put into a data structure. 44 00:02:45,609 --> 00:02:49,107 And then after that, for every record in order, go look up those records in a hash 45 00:02:49,107 --> 00:02:53,200 table. And indeed if this is constant time, 46 00:02:53,200 --> 00:02:56,994 amortized, then this is sort of a linear time algorithm. 47 00:02:56,994 --> 00:03:01,430 So there's two different ways. So I argue that there's two different 48 00:03:01,430 --> 00:03:03,485 ways to implement this joined, and both of these are valid. 49 00:03:03,485 --> 00:03:07,975 Okay, so which one is faster? Well, I've sort of hinted that perhaps 50 00:03:07,975 --> 00:03:12,270 option 2 is faster, but in practice it may or may not be. 51 00:03:12,270 --> 00:03:15,564 And so, you know, I would, I would pause here and ask the class to answer the 52 00:03:15,564 --> 00:03:19,239 question but since it's over video I can't do that. 53 00:03:19,239 --> 00:03:21,709 I'll give you a moment to think about that. 54 00:03:21,709 --> 00:03:25,129 But I want you to think about why one, why this one in particular, might be 55 00:03:25,129 --> 00:03:30,682 faster in some cases than this one, even though it seems like it should never be. 56 00:03:30,682 --> 00:03:34,770 Okay, let's see an example maybe in a second. 57 00:03:34,770 --> 00:03:38,570 So leaving, leaving that question hanging open. 58 00:03:38,570 --> 00:03:42,490 I want to make the point that you have access to this underlying algebra. 59 00:03:42,490 --> 00:03:46,710 This isn't something that's, all that's, purely sort of theoretical, alright. 60 00:03:46,710 --> 00:03:50,274 This is, this is something that you can use, tomorrow if you work with databases 61 00:03:50,274 --> 00:03:53,605 at your job. For example in this particular product 62 00:03:53,605 --> 00:03:57,007 Microsoft SQL Server, and in fact all the products you're going to use the same 63 00:03:57,007 --> 00:04:00,972 sort of mechanism. But you can explain a query and that will 64 00:04:00,972 --> 00:04:05,576 give you access to some form of this algebra that I've been talking about. 65 00:04:05,576 --> 00:04:11,860 Okay, so if you take a query and here, I've changed the scheme yet again. 66 00:04:11,860 --> 00:04:14,648 This table, this Reuters is one you'll be working with in the homework. 67 00:04:14,648 --> 00:04:20,306 I ran a query here and I've explained it in what shows what the sequel management 68 00:04:20,306 --> 00:04:25,144 studio gives back to me is a little algebraic tree, kind of like the ones 69 00:04:25,144 --> 00:04:32,250 I've been drawing here, just, you know, in PowerPoint. 70 00:04:32,250 --> 00:04:36,085 Okay, and so this one says, a hash mash is going to be used to implement this 71 00:04:36,085 --> 00:04:39,974 joining conditions. This one's kind of a complicated joining 72 00:04:39,974 --> 00:04:42,900 condition, for a reason I'm not going to explain right now. 73 00:04:42,900 --> 00:04:46,410 But it has two leaves, and they did join with this thing called a hash mash inter 74 00:04:46,410 --> 00:04:49,685 join. Okay, so this very much like the hash 75 00:04:49,685 --> 00:04:53,120 table example I gave on the previous slide. 76 00:04:53,120 --> 00:04:54,760 But, I want you to take a look at something. 77 00:04:54,760 --> 00:04:59,446 So here I've taken the exact same query, but I've added an extra condition where 78 00:04:59,446 --> 00:05:03,929 I'm only looking for words equal to parliament. 79 00:05:03,929 --> 00:05:07,640 I probably should explain this scheme a little bit. 80 00:05:07,640 --> 00:05:09,810 So the Reuters set gives you term frequencies. 81 00:05:09,810 --> 00:05:19,020 You have three columns, doc ID, or let's just say doc, term, and frequency. 82 00:05:19,020 --> 00:05:22,782 How, and the frequency is how often that term appears in that document. 83 00:05:22,782 --> 00:05:25,586 Okay? And so this is the, the table you'll be 84 00:05:25,586 --> 00:05:26,963 looking at. Right. 85 00:05:26,963 --> 00:05:31,184 And so here what I've said is, I'm looking for pairs of terms that that that 86 00:05:31,184 --> 00:05:37,680 co occur in a single document, is the, is the previous query I was looking at. 87 00:05:37,680 --> 00:05:41,019 And now I've said, well look, I don't want all pairs of document, or all pairs 88 00:05:41,019 --> 00:05:45,468 of terms, I only want terms that co-occur with the term parliament. 89 00:05:45,468 --> 00:05:50,394 Right so perhaps a lawyer, a co-occurs with parliament frequently. 90 00:05:50,394 --> 00:05:55,500 So I'm looking for all the, all the terms co-occur in some document with parliament 91 00:05:55,500 --> 00:06:00,090 is what this period is expressing. Okay? 92 00:06:00,090 --> 00:06:04,092 So now, what I want you to notice though when I explain this query I get a 93 00:06:04,092 --> 00:06:08,857 different, physical plan. The logical plan looks the same. 94 00:06:08,857 --> 00:06:12,385 It's still got scan, scan an a join, but the algorithm to compute the join has 95 00:06:12,385 --> 00:06:16,886 changed an now it's this nested, this thing called nested loops. 96 00:06:16,886 --> 00:06:20,832 And then nested loops corresponds, exactly to, this pseudo code here. 97 00:06:20,832 --> 00:06:25,062 That's why they call it nested loops, the outer loop, an the inner loop. 98 00:06:25,062 --> 00:06:29,790 So it's exactly the same thing. And so we chose to do this nested loops 99 00:06:29,790 --> 00:06:34,620 plan even though we argued that it was an in-squared algorithm, and it probably 100 00:06:34,620 --> 00:06:40,222 wouldn't be chosen very often. So why was it in this case? 101 00:06:40,222 --> 00:06:45,699 So, if you think about it. The, one of the sides of this drawing is 102 00:06:45,699 --> 00:06:50,736 only dealing with those terms. Or with the, with the occurrences of the 103 00:06:50,736 --> 00:06:55,512 term parliament in a document, which is a very small relation. 104 00:06:55,512 --> 00:06:59,170 And so it's a very small relation, and this nested loops algorithm could be 105 00:06:59,170 --> 00:07:02,887 very, very efficient and faster than dealing with the overhead of actually 106 00:07:02,887 --> 00:07:09,150 constructing this hash this hash table, or constructing some data structure. 107 00:07:09,150 --> 00:07:11,017 Okay. So the main take away here as oppose to 108 00:07:11,017 --> 00:07:14,836 the details a, are, is that different physical algorithms are appropriated at a 109 00:07:14,836 --> 00:07:18,940 different times. And that this decorative language and 110 00:07:18,940 --> 00:07:22,645 thanks to the declarative languages and thanks to algebra optimization, the 111 00:07:22,645 --> 00:07:26,660 programmer doesn't have to worry about any of that. 112 00:07:26,660 --> 00:07:29,678 They don't have to make that choice. Okay, so this is a very, very powerful 113 00:07:29,678 --> 00:07:31,690 idea. You just expressed the query and the 114 00:07:31,690 --> 00:07:35,810 database does the rest. Alright. 115 00:07:35,810 --> 00:07:37,884 So, fine. And just to point out, this is not just 116 00:07:37,884 --> 00:07:41,502 something you need to SQL server you can generate these kinds of algebraic plans 117 00:07:41,502 --> 00:07:45,959 in Postgre by using explain. And in fact they look kind of nicer, and 118 00:07:45,959 --> 00:07:49,717 here's these hash joints again. This actually shows you, whoops excuse 119 00:07:49,717 --> 00:07:52,755 me, this shows you where it's building a hash table, as in step one, and then 120 00:07:52,755 --> 00:07:56,350 probing it would be step two. And same thing here. 121 00:07:56,350 --> 00:08:02,224 And this is another operator that we didn't talk about where you are, say 122 00:08:02,224 --> 00:08:08,454 you're going to, count all the records that match them the for [LAUGH], count 123 00:08:08,454 --> 00:08:15,980 all the members of some group, I'll put it that way. 124 00:08:15,980 --> 00:08:20,390 And so the hash here is on group ID. And you can apply aggregate functions to 125 00:08:20,390 --> 00:08:22,388 the rest of it. But I shouldn't give such a high-level 126 00:08:22,388 --> 00:08:25,180 view of that without talking about it more, so let me skip that altogether. 127 00:08:25,180 --> 00:08:28,530 Okay. So fine. 128 00:08:28,530 --> 00:08:31,410 So the algebra really does exist, you can look at it directly just by using the 129 00:08:31,410 --> 00:08:34,090 keyword explain, and I advise you to do so. 130 00:08:34,090 --> 00:08:36,043 If you work with databases, you should be using explain all the time to try to 131 00:08:36,043 --> 00:08:38,910 understand what's going on. Alright. 132 00:08:38,910 --> 00:08:43,809 another point I'll make is just that, this matters, this is not from, directly 133 00:08:43,809 --> 00:08:48,820 from SQL, and in fact is not from a commercial database. 134 00:08:48,820 --> 00:08:54,110 It's from some research that we do in my group, but the point is the same here. 135 00:08:54,110 --> 00:08:57,498 These are actually different physical plans for the exact same query. 136 00:08:57,498 --> 00:09:00,781 And in fact, here I'm doing something in parallel, so there's actually no number 137 00:09:00,781 --> 00:09:04,815 of processors being applied. And so, as you go from four to 16 138 00:09:04,815 --> 00:09:08,366 processors, things go down a little bit, not as much as we'd like, actually, they 139 00:09:08,366 --> 00:09:13,274 should be going down quite a bit. But the point is that each one of these 140 00:09:13,274 --> 00:09:16,650 plans is doing a very different amount of time. 141 00:09:16,650 --> 00:09:20,469 Well, these two are kind of the same, but the difference is pretty important. 142 00:09:20,469 --> 00:09:23,605 And so ignoring these opportunities and sticking with only the plan that the 143 00:09:23,605 --> 00:09:26,495 programmer specifies would be a big mistake. 144 00:09:26,495 --> 00:09:29,870 Okay. And then another illustration of this 145 00:09:29,870 --> 00:09:32,970 that's a little bit hard to stare at but let me, let me give it a whirl to try to 146 00:09:32,970 --> 00:09:37,114 explain what's going on here. This is by, some very nice work by 147 00:09:37,114 --> 00:09:41,610 Haritsa et al, and VLDB 2010, but there's a whole series of papers on this work. 148 00:09:41,610 --> 00:09:45,496 But they tried to visualize the space of possible query plans, and so what the two 149 00:09:45,496 --> 00:09:49,195 axes are here, this is all for a single query. 150 00:09:49,195 --> 00:09:53,650 But the parameters to that query are changing. 151 00:09:53,650 --> 00:09:57,896 And so this in fact says something about the supplier account balance. 152 00:09:57,896 --> 00:10:01,796 And this is a parameter on sort of the extended price, and they change the value 153 00:10:01,796 --> 00:10:06,820 of these parameters in the query. So imagine the same syntax, the same 154 00:10:06,820 --> 00:10:11,443 select star from something, something, where some condition equals extended 155 00:10:11,443 --> 00:10:16,390 price and some other condition equals account balance. 156 00:10:16,390 --> 00:10:20,044 And just by varying those 2 knobs, you get this really rich tapestry of 157 00:10:20,044 --> 00:10:24,284 different plans being selected by the optimizer. 158 00:10:24,284 --> 00:10:26,020 So each color in this space represents a different query plan, a different 159 00:10:26,020 --> 00:10:27,790 algebraic query plan, selected by the optimizer. 160 00:10:27,790 --> 00:10:35,035 Okay and so I think the take away here is that there is a very complex decision 161 00:10:35,035 --> 00:10:42,520 being made by the data bases and necessarily so. 162 00:10:42,520 --> 00:10:44,570 They actually, you know, these, these different plans actually matter. 163 00:10:44,570 --> 00:10:46,850 They don't show that here. But you can actually show that this 164 00:10:46,850 --> 00:10:50,150 choice of plan tends to, the databases tend to do a pretty good job of finding 165 00:10:50,150 --> 00:10:54,330 the right plan. And that, you know, I argued in the last 166 00:10:54,330 --> 00:10:57,130 slide that this can actually matter, that the difference in the, in the time, can 167 00:10:57,130 --> 00:11:03,041 be pretty significant. Okay, so leaving this kind of complexity 168 00:11:03,041 --> 00:11:11,000 up to the programmer, is, can be a big source of loss. 169 00:11:11,000 --> 00:11:13,620 Right, hiding this complexity is a, is a huge huge huge win.