So today's class is about sorting and aggregation, and as usual we're going to start with a few administrative things. So first thing is homework number two is going to be due this coming Sunday, October 3rd as usual at 11.59pm. Remember there are no late days. You can't use any of your extension days for homework, they're just for the projects. And project number two is out now and it's going to be due Sunday, October 17th. There will be a Q&A session tomorrow, Thursday, September 30th from 5pm to 6pm, and if you check the Piazza post it'll have the zoom link and all that information in there. So one final thing I just want to put on your radar, the midterm exam is going to be Wednesday, October 13th, that's in class during the normal class time. And we'll release more details about the format and everything by the beginning of next week. So the topics that are going to be covered are just everything that we've covered so far up to the midterm in the class. So everything is fair game up until the midterm. Okay so last class we were kind of talking about index concurrency control and we ran out of time at the end so I just want to pick up where we left off and finish off the last little bit from that lecture and then we'll move on to the main topic today which is, as I said, sorting and aggregation. So I kind of recall the piece we were talking about specifically was B plus tree concurrency control where we want to allow multiple threads to read and update a B plus tree at the same time.  If we have a lot of cores in our system we can utilize all of that parallelism to concurrently operate on the B plus tree at the same time but we need to be careful to protect against these two types of problems that can come up. So again one is that we have two concurrent threads modifying the contents of a single node for example like a leaf node at the same time and another is that one thread might be traversing the B plus tree structure while another is doing some reorganization operations that could be splitting nodes, merging nodes, rebalance kind of stuff. So we ended last time with this observation that the first step in our latching algorithm to protect the contents of the B plus tree was that we were always going to take this right latch on the root node of the tree every single time so no matter what right we wanted to do we always had to first latch the root node but as you scale up to more threads this can become kind of a performance bottleneck because remember the right latch is exclusive so no other threads can acquire a latch while the root node is right latched so kind of the whole tree is locked up and everyone's blocked at least until the modifying thread is able to release this root node latch so kind of a better latching algorithm takes into account the following assumptions so most modifications to a B plus tree will not require a split or emerge so instead of assuming that there's going to be a split or emerge we want to sort of optimistically traverse the tree using read latches or remember read latches are going to let other threads who also want to acquire read latches come in and get those latches so we can have multiple concurrent threads with read latches but only one single thread with a right latch at any given time on a node so kind of the intuition is that especially for the higher levels of the tree there will be very few rebalancing operations now in a lot of the examples we've showed you know the nodes are relatively small they have two or three elements each so obviously for you know illustration purposes that's good because it can let us show rebalancing but as you scale up to you know larger trees imagine I don't know a million or a billion elements most of the modifications are going to be taking place at the bottom layers of the tree so the leaf nodes or you know the inner nodes that are only a few few layers up from the leaf nodes so kind of the that's the intuition here that we can kind of optimistically traverse the tree just getting the read latches to protect kind of our our path or traversal through the tree but not not intending to right latch things and then of course if we if we kind of guess wrong and we actually do need to propagate these these rebalance operations up the tree then you just you know abort your operation and start over at the beginning acquiring now you know you need to acquire right latches so you can kind of just repeat repeat the traversal so kind of how does this work compared to the original algorithm we talked about so you know search is the same as before there's no difference there in certain delete as I said we're going to set the latches the same as for search to get to the leaf until we get down to the leaf node and then we're going to set the right latch so all latches are reads all the way down to the leaf and then we set a right latch on leaf node so if the leaf is not safe remember we define safe last time as it's it doesn't need to split or merge so there's enough room or keys to accommodate whatever change you're going to make so when you get down to the leaf node you you ask is this safe if it is then you're done that's great you have the right latch on it if it's not safe then you kind of have to to start over from the root and traverse down getting right latches so that's why we call this optimistic we optimistically assume that we have we're not going to need the right latches all the way down the tree versus pessimistically acquiring those those latches as we descend the tree so we'll just look at two two examples here quickly so this is example two from the previous examples where we where we did this kind of delete when delete key 38 so again here instead of taking the right latch on the root node we're going to take this read latch and just you know descend descend of the tree as usual taking taking read latches all the way until we get to the bottom here we acquire this right latch and we say okay we're we want to delete this this key 38 here H doesn't need to coalesce so we're safe we're done we achieve the same thing that we did taking these right latches down the tree just using the read latches so we can you know do our deletion and then we're we're all set there so this is it is example four also from the previous examples where this time I'm going to insert a key 25 so again we'll we'll use the new read latching algorithm to descend the tree until we get to where the key 25 needs to insert and we see okay here we need to split F so we have to restart and re-execute the transaction for the insertion from the root node this time acquiring right latches because we figured out okay we have to split this node we're going to need to to rebalance on some of the the upper levels so does anyone have any questions about either of these two examples okay so this other thing that that we can point out is that in all of the examples we showed so far both in the last class with the pessimistic right latching and in this example here with the optimistic read latching is that all of the threads have been acquiring the latches in this top-down fashion so remember in the the hash table examples we always have the threads accessing the hash table in a forward scan you know the linear probing hash table you just scan forward in the table until you wrap around and go back to the top so they're always scanning in the same direction they're always acquiring latches in the same direction and in this case also for the B plus tree we've always been acquiring latches starting from the root node and then as we we traverse down the tree so that that kind of has allowed our algorithmically to prevent deadlocks because recall there's no sort of deadlock detection or deadlock prevention the only thing we can do is avoid deadlocks through this kind of careful algorithm design so one of the other operations we talked about on the B plus tree was this idea of a leaf node scan so you traverse down to the leaf node where you want to start your scan and then we have these pointers the sibling pointers we can traverse across the leaf node layer to get a range of values that you're looking for so now what we have to think about is okay if we have threads potentially acquiring latches from the top of the tree coming down and also threads potentially scanning along the leaf node layer we have to be careful that we don't run into a situation where we have a deadlock so we'll see a few just simple examples of this come up so let's just do a simple leaf node scan here with one thread so t1 wants to find all keys that are less than four so what we're gonna do is just start here at the root figure out which leaf node we need to get to to find the keys less than four and then we want to scan now across the leaf nodes to to find our range and similar to how we were taking latches on going down the tree and kind of this log lock latch coupling or latch crabbing algorithm where you don't release the latch on the node you currently hold until you have the latch on the one that you want to go to next we're gonna do the same thing kind of in this this leaf node scan so here we don't want to release the latch on the C leaf node before t1 gets the latch on the B leaf node so that's great we got the latch and now we can move over here and release the latch on C because we're kind of doing in this coupling way where we always have you know the current latch in the next latch that we want to get so let's get a little more complicated here we can now add in these two threads that are executing at the same time so again thread one still wants to find all of the keys less than four and thread two wants to find all of the keys greater than one so you know let's say they start at roughly around the same time they're they both get the read latch on the root node that's fine there's no problem there and then they're going to move down to each of their respective leaf nodes where they need to start scanning so now you have thread one that wants to scan backwards from four and thread two that wants to scan forwards from one so you're going to run into this situation here they can you know release their latches on the root node because they have their leaf node that they're on now and now they want to come over and acquire a latch on the other's leaf node so what do we think is going to happen here yes so the question is it a is it a read write latch or just a regular retake let's assume it's a read write latch just like all the other ones that we had so you can either get it in in read mode or write mode okay so yes that's correct there's not going to be a problem both t1 and t2 can get the read latch on each other's leaf nodes because you know as we saw before and we've discussed before there's no problem in this compatibility matrix if two threads want to both acquire a read latch at the same time so kind of they're both going to get the read latch on each other's leaf nodes and then you know they can release the latch that they hold once they switch in that way so this example works out but if we have now arbitrary readers and writers at the same time you can pretty easily run into these kind of deadlocks as you are acquiring latches in now not just a top-down fashion they can be you know in an arbitrary fashion so again the important thing to remember is that latches don't support deadlock detection or avoidance the only thing we can do is through like carefully designing the algorithms and the data structures to prevent these sorts of things from happening so in the previous example here you know we could ensure or mandate that for example you can't scan in the reverse direction across leaf nodes we're only going to allow scans in the forward directions that would kind of be one way of preventing deadlocks here so kind of the key takeaway that we need to remember is that there's there's no kind of higher level deadlock detection or management it's just in in the algorithm and data structure design we have to be careful to avoid deadlocks in in our our data structure traversals so just to wrap up with the index and currency stuff generally making data structures thread safe is is notoriously difficult in practice it's really hard to do you really have to pay attention to figuring out if there are cases where you can run into potential concurrency errors or deadlocks or that kind of stuff and and engineer around them and again we mostly focused on hash tables and B plus trees but the same high level techniques can be applicable to other data structures and we're not going to really talk about any more in this course but you could imagine you know generalizing these same sorts of ideas to arbitrary tree structures for example so before we move on to the main topic for today are there any questions about the the concurrent index stuff okay so let's just take a step back and look at kind of the core status so we've we've talked about a lot of different layers of this stack here representing the different components of the DBMS and today we're going to be talking about or at least start talking about how to execute queries using the DBMS components that we've discussed so far so we're at this operator execution layer in the stack right now we've already talked about the disk manager we've already talked about the buffer pool we've already talked about you know different access methods and index structures they can speed up accessing the the the data in the database so now we're going to really be focusing on the the different individual operators that we want to provide to the the query interface and over the course of the next four lectures we're going to be talking about these three topics so specific operator algorithms how we're going to implement individual operators different query processing models so how do we you know string these operators together to execute a query or like a SQL query and then different runtime architectures that have trade-offs for different you know workloads or situations so just at a high level the the thing that we're going to be executing is called a query plan so in a query plan the operators are going to be arranged in a tree structure technically it's a directed a cyclic graph but just for our purposes you think about it as like a tree structure so here we have this really simple SQL query as just you know selecting some values from two tables you're doing a join between the two tables and we're applying a filter condition on this b value so the kind of way to think about this and we'll talk more about this in later lectures as we talk about the query processing models but the way to kind of think about this at a high level is that data is going to flow from the leaves of this query plan tree so in each case we have a and b at the bottom that's just a scan of the tables a and b so data is going to flow from the leaves of this query plan tree up to operators in the inner nodes and then all the way up to the root of the tree whatever the root of the tree is going to be the output of the query plan so kind of here we have this scan over a scan over b the output from the scan over b is going to go to this selection operator that's going to filter out some values based on the selection condition then those two inputs are going to go to the join we're going to join them together and then finally do a projection to just return the two attributes that we want so this is how it's going to work at a high level and as I said we'll kind of go into the details of how exactly this is implemented in a couple classes so the important thing to remember here is that just like we can't assume that a table is going to fit entirely in memory we also can't assume that the the query results or even the intermediate results of these different operators we saw in the query plan in the last slide we can't assume that they're going to fit entirely in memory so the the point of the disk oriented dbms that we've been talking about building is that it kind of gives the the user the application the impression that you know all of the data can be processed in memory even though the data might exceed memory so we're going to rely again on our on our buffer pool that we've talked about and you've implemented in a project we're going to rely on that buffer pool mechanism to implement the different algorithms that we need in order to spilt disk and again it's important to remember that we're going to prefer algorithms that maximize the amount of sequential IO so this is important because of how how disk accesses work sequential IO remember is more more efficient than random IO and just at a high level I mean you may have taken an algorithms course learn about things like sorting that kind of stuff but what we're going to talk about here is different than how you may have studied algorithms in the past because you know where we talk about the time complexity of an operation like a hash table has 01 time complexity or something or a you know a search or sort has a n log n time complexity but I mentioned in one of the previous lectures that the important thing to care about is the constant that goes along with that time complexity because again if you have a an 01 look up in a hash table that goes to memory that's okay it's cheap to access memory relative to an 01 access and a hash table that goes to disk every single hash table accesses to disk it's going to be really slow even though you know the theoretical time complexity is 01 so there's another good example of why the DBMS needs to think carefully about managing its own memory and file IO we don't want the OS to do that or something and why we have to kind of design these algorithms to take into consideration the different disk accesses because we can have you know better you know caching and prefetching policies than just an OS I might have because it doesn't know exactly what types of operations we're trying to perform so the two things that we're going to talk about today are the external merge sort which is basically is disorting algorithm for out of memory sort so large in memory sort and different aggregation operations so we're going to see kind of how these like high level strategies can be designed around like a divide and conquer algorithm we'll see how we can apply it to two different types of operators so this is also going to segue into the next class where we'll talk about an alternative to sorting which is hash based methods so what are some different reasons why we need to sort well in previous lectures I have and continue to make a big deal out of this idea that the relational model or sequel is a set or multi-set algebra so it's unsorted so there's no inherent relationship or order between different tuples in our in our tables so why do we care about sorting order some examples of when we might need to sort our our data none okay well the first and kind of most obvious one is that queries may request explicitly that the tuples that we return in our results that our answer are sorted in a specific way so if the sequel query specifies kind of an order by clause they say okay I want the output result that you're getting sorted by a particular attribute or set of attributes then the dbms is going to need to take care of that we're going to need to sort it in that particular order so that's one example of when we might care about sorting the data another situation is that you know even if the query doesn't explicitly specify some order so even if the user doesn't care what order they get the results back in there are times when we may still want to perform sorting of the data in the database in order to speed up or perform different algorithms so these are just a few examples I've given here there are many others where you can apply the same idea but for example if you want to do some sort of duplicate elimination so you just want all of the distinct values in a particular table it's trivial to support this duplicate elimination if you have the data sorted so you know sort the data in a particular order as you're scanning through you can see consecutive values can be removed from the the output answer because you know you just saw that value previously so you can kind of skip through the results in that way again we talked about bulk loading sorted tuples into a B plus tree it's much faster to do that than to do insertions from the root node and follow the usual insertion algorithm so you kind of do this bulk loading but it requires that the data is sorted so if you want to build a B plus tree in this bulk load fashion then you have to first sort your your tuples and then build it from the leaf nodes up and finally we'll see in this this lecture an example of how you can use sorted data to speed up aggregations and implement a group by so you want to get an aggregate grouped by some value the first step in that pipeline can be to sort the data and then perform the aggregation and we'll see how that works in a couple slides so again I mentioned this a few slides ago but I just want to reiterate that if the data fits in memory then you just use any standard sorting algorithm quicksort you know any of the other million sorting algorithms that there are pick your favorite one you can use it it doesn't matter because everything's in memory everything's going to be fast but the problem again is that if the data does not fit in memory then we're going to need to use some kind of algorithm that knows about the fact that we're going to be writing to and reading from disk so we have to know okay in advance here's how much working room I have in memory and I'm going to be able to read in this many pages into my buffer pool and then I have to kind of write them out in an intelligent way when my buffer pool fills up so that's kind of the whole idea behind this external merge sort algorithm that we're going to talk about today so as I mentioned external merge sort is basically a divide and conquer algorithm we're going to split up your data into these separate pieces called runs and then you're going to sort each of those runs individually and then the last step and this is the the merge phase is to combine them back into longer sorted runs so you know the two basic phases we have are sorting where we sort individual chunks of data that are going to fit in memory so we read the data and work on it in memory sort it and then we're going to write out the sorted chunks to a file on disk and then phase two the merging phase we're going to combine sorted runs until into larger sorted chunks so the term run or sorted run is basically just the list of key value pairs so again the key is the attribute or attributes that that we're going to use for the sort order whatever we're sorting by it could be you know primary key it could be like a date I want all the data ordered by date or something so it's whatever we're using to impose the sort order on the tuples the second piece is the value so here you have as in many cases two choices you can either you include the entire tuple in the sorted run and this is called early materialization or you can include just the record ID in the sorted run and that's called late materialization so the first example here early materialization basically um if we're sorted by key so the keys are ascending key one key two etc we're co-locating the tuple data directly in the sorted run with the keys so this early materialization because we're doing this proactively we're putting all the data right with the keys where they need to be the alternative of course is this late materialization idea where instead of storing all of the tuple data we're just going to store the key along with the pointer that's just a record ID that's going to tell us where to go at the end to reconstruct the tuple and we'll talk about the different reasons why we may prefer one over the other it may have to do with the data storage model you have so we talked a little bit about whether you have a row store or a column store that's one reason why you might prefer one over the other there are also cases where for example if you're doing a lot of filtering or something it may be or filtering at later stages it may be beneficial to use this late materialization so you don't have to do a lot of extra copying so we'll see some examples later where one of these methods might be preferred over the other but for now we're just going to assume we're not going to factor this trade-off into the the algorithms that we're talking about so let's start with the simplest most basic example which is the two-way external merge sort and then later we'll generalize it to a k-way sort so two is basically meaning the number of runs that we're going to merge into a new run for each pass so at any given pass in the algorithm we're only ever going to be taking in this example two runs and then merging them into a single larger longer run so we're going to break the data up into end pages imagine a table broken up into end pages and the dbms is going to have a finite number of buffer pools buffer pool pages b that we're going to use to hold the input in the output so you know this is something we need to know ahead of time in the dbms the amount of memory we have to work with to do our sorting and it's it's typically configurable there are configuration options in postgres mysql whatever to figure out you know you can as the database administrator say here here's how much memory you should have available to to do these types of operations so we'll kind of go through an example here imagine we have a dataset with two just for now just two pages stored on disk and we want to do this two-way external merge sort so the the first pass we'll call pass number zero is going to be to read all b pages of the table into memory and we're going to sort the pages into runs and then write them each back up to disk so for now let's just assume we have one one page in our buffer pool and we're going to read them in one at a time and do this this sorting so let's first read in page number two it's going to go into our buffer pool in memory we're going to do this nice sort we can do it in place even so we don't we just need that one free slot in the buffer pool now we have this sorted run and then we're going to write it back out to disk in this new page here so we have the original one unchanged it's still unsorted however it was previously now we have this new intermediate result that we've materialized somewhere on disk that's the the sorted version of page number two so now the next step is we have to read in page number one again do our sort so we get the sorted version of page number one the sorted run and then we write that out to disk so now the next step in the subsequent pass is that we're in a recursively merged pairs of runs into runs that are each twice as long so we're going to take each of these individual pages and merge them into now pages that are or runs that are two pages long so in order to do this this step uh what's the minimum number of buffer pool pages that we're going to need here yes so the answer is three that is correct and it is because we are going to need one for each of the input pages and then one for the output so we have the two pages that are coming in in our two-way external merge sort and then we need one page left over to write the the merged page out and then we're going to write that to disk so the way this is going to work again is we're going to read in these two pages here we're going to have our result page we're going to write that out first uh so once that page fills up from the the first two pages because uh you know we have two pages uh we're only going to be able to fit some portion from each of those pages into this output page so we're going to write that part of the run out so that's the first page of the run and then we're going to reuse that same buffer pool slot we're going to fill it up with the remainder from the two pages in the second page of the run so kind of the the the whole way this works is if we had more pages you know we just keep kind of repeating the process recursively until we get one single run at the end so kind of what we can see maybe a more concrete example here of how that works um in each pass we're going to be reading and writing every page in the file so in terms of the total number of passes in the total iocos well the total number of passes we need our log two or the ceiling log 2n plus one and the plus one is that first initial pass number zero that we did will resort each each page individually so I think it might vary in Wikipedia or in different textbooks if you see whether or not they include that first sort pass but we'll include it here so it's the first sort sort pass plus the log because again we're doing it we're splitting it into recursively into these these uh merging two pages together at a time so we have the ceiling log 2n and then the total iocost because on on each pass we need to read and write every page of the file we're going to end up with 2n times the number of passes in terms of ioc so just as a concrete example of how this works um let's say we have these pages here that we want to sort so each page contains two values and the last thing is just we'll say like a an end of file character to let us know that we're done there um so again what we're going to do on pass number zero is we're going to read each of these pages in and sort them individually so uh we can get get all of our values sorted um for for the next merging phase so in this case you know some of the pages are already sorted like the three the first page three four it's already in sorted order so we don't really need to do anything the second page goes from six two it gets flipped to two six uh etc all the way across so now the next stage is to get to this pass number one we're going to merge each of the one page runs into two page runs so we can just you know take uh consecutive pairs here and merge them together so the first one we're going to merge these two together and the way we're going to do that is we're going to look at the minimum or lowest value in each of these pages so in this case we're going to see you know the the smallest value from the right page it's going to be two so that's going to go in our first slot then we move the pointer over and we say okay now I have three and six so three is smaller so three is going to go into the the the um run page that we're going to write out so now we can you know kind of repeat the process uh and fill out all of these pages in the same way writing out a page as soon as we fill it out so in this first this the case of the first two pages when we merge them together we filled up the page with two and three uh we write that out and now we clear it and we have uh four and six come in to fill out the second page of the two page runs so this process continues all the way down we get to pass number two and now we merge them into four page runs and finally we merge it into one final eight page run at the end and that's the entire thing sorted so this is kind of like a divide and conquer strategy where you split up the file into these smaller runs and then we recursively merge them together to get a final sorted result so are there any questions kind of at a high level about this uh how this algorithm works this here uh yes that should be answer I think the b b was for the size of the buffer pool right and and this is um we're talking about the the number of pages in the tables then yes sorry are there any other questions about this or errors that I've made in the slides those are also welcome yes so the the question is um are these are these merge phases being performed sequentially or do you have multiple threads running concurrently working on it the answer is so for simplicity for everything we're going to discuss here let's just assume one thread for now so as soon as you know we finish the first two we're going to move on to the next two however uh you could and in fact I a lot of systems do uh partition up the the work into multiple threads so of course you know if you have let's say you're working on the the two page runs you want to merge the one page runs into two page runs you could have each thread you know take two individual pages to to do the merging right and that those can work independent of each other and then as you get you know further and further down you have to be careful about you know you can't you can't use as many threads as you get further down in this in the number of passes so for now we're just going to assume one thread doing all this you could split it up but then again also if you have multiple concurrent threads running you also have to think about the resource utilization so for example we've we've said okay we're going to have just for now two buffer pool pages assigned one for each of the inputs and then one for the output now if you have in this case let's say four-way parallelism you now have four times the number of buffer pool pages assigned so you need to think about trading off the the parallelism versus the amount of you know extra resources you need to support that level of parallelism so again to to reiterate the two-way external merge sort is only going to require three buffer pool pages in order to perform the sorting so b equals three so again two input pages and one output page but you know three pages is pretty restrictive that seems relatively small if we have four kilobyte pages that's not very big in terms of today's main memory so you know in a lot of cases you have b is greater than three you have more buffer pool space to work with so what we need to do is figure out how to leverage that buffer space without having the the worker thread that's doing the sorting have to block on disk IO because kind of we're we're reading in these pages and then we're writing them out we need to figure out how to do it in a way such that we're not blocking on disk IO waiting around for for the pages to get right into the more buffer pool resources that we have so the way we're going to do this is what's called double buffering this is an optimization of the previous algorithm where basically we're just going to prefetch the next run in the background somehow either you know there's some other thread that's doing the prefetching or you could issue from the worker thread a prefetch request for the next run that you know you're going to need and basically we're just going to fetch that next run and we're going to store it in a in extra buffer buffer pool slot so here we're reading in page one from disk into our buffer pool in memory and now let's say again it's doing its work it's sorting doing what it needs to do there and while that's happening in the background what we can be doing is also fetching this page number two which we also know we need to sort into the buffer pool to kind of mask that that disk IO so we can get it loaded and ready to work on as soon as we're done working on the first page there so now that that page is done we can move on to this next one and start sorting it right away it's already in memory we don't have to wait for a separate disk IO request to get that page in so kind of you can you can generalize this as far in advance as as you want if you have you know a sufficiently large buffer pool you can prefetch as many runs ahead as you want since you know the order that you need to work on them in so you can kind of mask it in arbitrarily complex disk arbitrarily expensive disk access so are there any questions about this optimization here yes so the question is do you throw away the intermediate pages that you write on disks or the sorted sorted runs that you write on disk as soon as you're done with them or do you keep them around so technically you don't need them anymore as soon as you've done what you need to do with them you can throw them away as soon as the query result is returned you can get rid of them but sometimes there may be reasons to keep them around maybe it's a query that gets executed frequently so you can kind of keep this intermediate result around and and you think of it sort of like caching so you can keep this this intermediate computation that you've done stored somewhere in a special cache so that way if you have another query that would benefit from accessing it or even is you know the exact same query you can go back and and re-scan your intermediate results so you don't have to go start from scratch again but from a from a like correctness point of view there's no reason to keep keep the intermediate results around as soon as the the query is done executing yes so the question is what if your memory system is able to return sorted pages to you so you mean like so like a hardware acceleration or in memory computing that would be nice i guess the the same problem is that if you you're only you're only getting sorting at the level of the page right so you still need to even if you can sort in the hardware i assume it doesn't have to go through the cpu or whatever but if you can sort in the hardware or in the memory then you you still need to do this kind of merge phase right to get the longer run so i guess you could accelerate the the sort part of it but each individual page would be sorted but then you still need to merge them together into a longer run okay so the the general external merge sort is kind of this generalization where you have some number b of buffer pages rather than just the the two pages that we're working with and what we want to do is on every on each pass we're going to we're going to work with these b buffer pages at the same time so in the first pass we're going to produce n divided by b ceiling sorted runs each of size b so then on subsequent passes we're going to merge b minus one runs to do this k-way merge we're going to take all these pages now b of them and we're going to merge all at the same time into a single run so in this case the number of passes that we end up with is given here and the total i o cost is still again two n times the number of passes that we have because again we're reading and writing all of the pages on every single pass so an example of how this works is pretty straightforward just basically let's say we're going to determine how many passes it's going to take to sort 108 pages with five buffer pool pages so our our inputs are n equals 108 and b equals five and you know kind of we can go through each of the how the passes work so in the first one we're going to produce 22 sorted runs of five pages each the last of these it's uneven the last the last run is only going to be three pages long on pass number one we're going to end up with six sorted runs of 20 pages each and again because it's uneven the last one's going to be eight pages long on pass number two we're going to end up with two sorted runs the first one's going to have 80 pages and the second one's going to have 28 pages then the last pass we're going to have the whole file sorted of 108 pages so again we end up with we can figure out using this formula how many how many total passes we're going to need so are there any questions kind of about how how to generalize the two-way merge sort into this k-way merge sort okay so the next thing to think about is we've talked about B plus trees in the past and they maintain the data in sorted order and we also looked at you know how we can kind of scan B plus trees to get a sorted result from the leaf nodes of the B plus tree so it's natural that rather than doing this this sort merge sort thing if we already have the data stored in some kind of sorted data structure like a B plus tree index then it makes perfect sense to to leverage that in order to accelerate our sorting so there are two cases that we kind of talked about in the the B plus tree lecture they apply the same here so there's either a clustered B plus tree which is the data is stored in sorted order in pages based on whatever the clustering attribute is usually it's like the primary key but it's stored in whatever order the physical tuples are stored in pages in whatever order the whatever the sort order is the other case is the unclustered B plus tree which remember can be you know completely out of order it just gives us some kind of data structure built on some non-primary sort attribute so we'll look at the first case first we have here a table that's stored in a clustered B plus tree and again we're going to traverse to the left most leaf page just like we did in the the previous version we want to get a scan of the the tuple pages and since they're in sorted order we're going to get nice sequential access here we're going to be able to access all of the tuples in their exact sorted order first we look at page 101 then page 102 etc because this is already maintained in sorted order and it's it's guaranteed by the B plus tree so this is always going to be better than than that external sorting algorithm because there's no computational cost here we just we already know it's in sorted order we can just scan forward in in a sequential scan with sequential disk IO so the if your if your query optimizer in your dbms knows this and it knows that you have a clustered B plus tree index on on the data then it can kind of choose whether it makes sense to to execute a some kind of sorting operation or if it knows it's already in sorted order it can just return a scan over the the sorted root data so the other case is this unclustered B plus tree and as you may have guessed you're going to end up with really bad IO access patterns it's going to be random access because basically you have all of these pointers pointing all over the place in your base data and it's going to to have completely random IO patterns so in general you're going to end up with one disk IO per per record in your B plus tree there so this is going to be really bad because now we're doing you know for every single record we're doing a disk IO rather than in the sort sort merge join we can or sorry rather than the sort merge sort phase I will talk about the sort merge join next next class but in the the merge sort phases we can constrain how many passes we have to do and we can figure how much disk IO we need to do so I also mentioned that you can use sorting to as a as a precursor step to implementing an aggregation basically the way it's going to work is we're going to collapse values for a single attribute from from multiple tuples into a single scalar value so that's what the aggregation does it takes these groups of attributes grouped by some key that you want to group by and then it compacts them into a single scalar value I think like maximum average sum that kind of stuff so again I I sort of mentioned earlier there are two different choices that we have sorting or hashing first one to talk about sorting but I'll give you a small spoiler hashing is going to be better in in a lot of cases so there are some instances where sorting might be preferred but but hashing is going to be better in a lot of cases we'll start first with talking about sorting because it's it's a little bit easier to think about and we've kind of talked about the the prerequisite algorithms that you need to get there so just as a simple example let's let's take distinct so imagine that we just want to get all of the distinct course IDs from from this enrollment table where some student got either a B or C in the course so we just want only only the the course IDs where some student got one of those grades and we want to order it let's say by course ID so it has the sort property it would be beneficial here for us to sort them so we can we can give the results back in sorted order so the first step that we're going to do and this this will come up again in our discussion of query optimization and query planning but the first thing you pretty much almost always want to do is remove useless data as early as you can in the plan so we have this table here there is one one tuple in there where the the student got a grade of a in the course so we want to filter that out as early as we can in the plan so we don't have to you know work on that in our subsequent operators we're going to have to include it in our sort because it's not going to be in our result set so it's just wasting our time trying to sort something that we don't we don't care about so we want to filter things out as early as possible so we apply this selection predicate where grade in B or C then we want to remove the columns we're not going to need so the only column we have in our select clause is select distinct CID so we only are going to need the CID column in our result set so again kind of going along with this idea of removing as much unnecessary data as possible we want to apply our projection here to get rid of the other two columns that we don't need so now we're left with just the CIDs and then the final the final step in the sorting aggregations obviously to sort so we're going to take the CIDs that we have after the first two steps and we're going to sort them in this ascending order and now what we're going to do is just essentially one final scan through the sorted result in order to remove duplicates so we'll start at the beginning we see okay we see 15 445 as we're scanning forward we see okay there's another I just saw that 15 445 I don't need this next one so we'll get rid of it you can kind of scan forward in this way checking if the current key that you're looking at is the same as the last key you just saw if it is you can get rid of it otherwise you kind of added to your result set so this is kind of the high level idea of how sorting aggregation works are there any questions about this okay so let's talk about some alternatives to sorting so what if we don't need the data to be ordered so in the last example there was the order by clause at the end that said okay we want this result produced in this particular order now let's just say we just want the result back we don't care so an example is like if we're forming groups in a group by statement and we don't care what order they're in that doesn't require ordering or if you're removing duplicates and again you don't care there's no order by clause you don't care what order you get the results back in so an alternative that we can use in these cases is hashing and it's going to be a better alternative in these scenarios than than doing the the full sorting and because it can end up being computationally cheaper than having to sort the input to the the later operators in the query plan so basically the way that we compute a hash or perform a hashing aggregation is to build some kind of ephemeral hash table as the dbms is scanning the table so for each record we're going to check whether there's already an entry in the hash table if we're doing a distinct operation then you know if we if we hash the key go look in the hash table already exists we can just throw it away we don't need it because we already know it's in the hash table if we're doing a group by and for now let's assume that the the aggregation function is going to be commutative and associative so something like sum or min max that kind of stuff we can just perform the aggregate computation so some kind of incremental aggregation imagine like a sum you know if i want to sum all of the values together for a particular key then i can just go and for each each each time i hash the key and find that key in the hash table i just add the value to the running sum until i get to the end and i have the total sum if you have other aggregates like median or something then you have to do something different but we won't talk about those here so if everything fits in memory the same with the sorting then this is easy you're done i mean you just use one of the hash tables that we talked about before you use your favorite hash table whatever it's all going to fit in memory you'll be fine there won't be a problem but again if the dbms has to spilled the disk then we need to be more careful about how we manage our our i o and how we manage our operations so this algorithm is going to be called an external hashing aggregate or aggregation operation and basically it's it's split into these two phases so in phase number one it's going to be the partition phase and what we're going to do is divide up the tuples into these different buckets based on their their hash the hash of their key and then while we're doing the partitioning we're going to write them out to disk when each of our partitions gets full so once that's all done that's one pass through the data in the next phase phase number two the rehashing phase we're going to build an in-memory hash table for each partition and compute the aggregation over that partition and then there'll be a final phase where we merge our our intermediate hash tables into one final hash table for the result so kind of it's the it's the same high level idea of this divide and conquer approach as the external merge sort and it's going to help us through our partitioning it's going to help us maximize the the sequential i o that we're going to perform to and from disk and we'll see why in a second so again phase one just to dive down a little further the partitioning phase we're going to use some hash function h1 to split the tuples up into partitions separate partitions that are restored on disk and a partition is just one or more pages that contain the set of all the keys with the same hash value produced by h1 and then kind of they're spilled to disk in the same way that we were doing the spilling of the output buffers for the the sort where we you know as soon as we as soon as we filled up a buffer for the output we wrote that out to disk and then we had we reused the buffer to fill out the rest of it so kind of as soon as the output buffer fills up we can write it out to disk so again assume that we have b buffers here and we're going to use b minus one buffers for the partitions and then one buffer for the input so the kind of the key idea is that the same value from or the same key from different tuples are going to hash into the same partitions we'll get all of the the same keys with the same hash co-located in a partition and it's kind of like the opposite of doing the sorting operation so in the sorting operation we had one input buffer and then you know b minus one output buffers in this sorry we have sorry i reversed that in this case we have one input buffer and b minus one output buffers in the other case the k-way sort we have b minus one input buffers and one output buffer so we can see an example of kind of how this phase number one works again we have the same query here except i removed the order by so we're just getting all the distinct cids that meet this case same table and again we're going to do the same thing we're going to filter as early as possible to remove the rows that i don't need and then we're going to remove the columns we don't need and then when we get to this partition part at the end remember this is this where we're going to do the sort but instead here we're going to do the partitioning so we're going to pass the keys through this h1 function and it's going to route us to these b minus one partitions so in this case we can see all the 1545 keys end up in the the first page there and then they i think that the the first two pages are part of the same partition so all of those keys end up in in those partition that partition there and then the bottom page is a separate partition so that fills up separately so we kind of pass it through this h1 hash function and it splits them up into these different partitions so again kind of this one is filled up so we have the the overflow values in there so now in this phase number two rehashing phase for each of those partitions that we created on disk we're going to read it into memory and build an in-memory hash table based on some second hash function h2 so this is just separate from the original h1 hash function that's going to give us a low a hash offset into our in-memory hash table that we're building and we're going to go through each bucket of the hash table to bring together matching tuples so imagine just for now for simplicity that our our hash table is going to fit in memory you can have the same kind of buffering idea that we had with our you know external or extendable hash table that where you can you know build it up incrementally and spill pages to disk but for now just assume it's a really simple linear probing hash table so like I said we're assuming that the the hash results going to fit in memory but it in the general case doesn't have to now the second phase rehash again we have the same setup here we have these partitions so these are the the partitions or buckets that are produced by phase number one we have the first buckets there and then we we want to do a scan through these each of these buckets and build this in-memory hash table so we're going to pass them through h2 as we iterate over each page stored in these buckets we're going to pass them through the h2 hash function to populate this in-memory hash table and we're going to build up the values and put them in there remember again we're just looking for the distinct cid values so if we hash in and we find a duplicate key in this in-memory hash table then we just throw it away because we don't need we don't need duplicate we just want all of the unique keys in the hash table so kind of we we build up this in-memory hash table from this first partition here and then when we're done with it we can immediately add them to our final result and we can do this because we know that there's it's not possible for any of the keys that are in any of the other phase one buckets or partitions to show up again so we're not we never have to backtrack and look at previous partitions because all of the partitions are disjoint we have we have completely disjoint partitions that we produced in phase number one so as soon as you know we're done looking at the pages in this first partition we can write out this hash table to our result set we're done with it those keys are never going to come up again in later partitions so we can go down here to one of these later partitions and we see okay we're going to run it through hash two and build up our new hash table we can get rid of the the previous one we've already written it out to our final result then when we're done here looking at at the pages in later partitions we can just add that to our final result so are there any questions about how this this two phase partition hashing works okay so just to reiterate the first phase is the partitioning phase where you kind of build up these disjoint partitions the second phase the rehashing phase where you build this final hash table at the end for each partition so what have we achieved here in doing this well we've taken you know the the giant hash table that we would have had to build otherwise over all of all of the keys instead we've broken it down into these smaller disjoint hash tables which has taken the random IO from the giant hash table that we would have had to build and and given us now sequential IO since the partitions can each be read in sequentially and we can write out the final result sequentially so we've avoided this kind of big giant random IO hash table and we've turned it into smaller sequential IO operations so that's that's the the key idea behind splitting it up into this partition and rehash phases okay so if you that that was getting the distinct keys in this case if you want to do some kind of aggregation called hash summarization basically um during the rehash phase we're going to want to store uh output values of the form the group by key whatever key we're grouping by and then the running running aggregate that we're computing so we're going to insert a new tuple into the hash table we first go to see if there's a matching group by key if there is that's great we just take whatever the value is let's say it's the current running sum we add whatever our our value is to it and then we're done otherwise if the group by key doesn't exist then we need to insert the group by key and then our our starting running value so kind of just as an example of how this would look let's say now we want to get the average gpa grouped by course so kind of the the process is similar we're going to do the phase one partitioning into disjoint buckets and then we're going to run them each through their their individual building up their individual hash functions hash tables and then merge all these results into the final hash table so we get kind of this key value output where the key is the the group by key so in this case course ID in the value in order to get the average we need to keep track of the count and the sum so it's the count of the number of values that that match the key and then the sum of those values so you you can think about this kind of you know the different running totals most of them are easy the minimum value is just the minimum one you've seen so far max is the maximum you've seen so far sum is just adding them all up and count is obviously just count but for the average we're going to keep around both the count upfront and the sum so we can compute it in this kind of online fashion so then once we have this we're going to take those those running values and convert them into our final result just by dividing the the sum that we've computed by the count and that gives us the average so are there any questions about kind of how this process works okay so just kind of wrapping up there's kind of this tradeoff that we have between sorting algorithms versus hashing algorithms it's subtle and depends kind of on a few different things like I said the data layout if you have a row store or entry store versus a column store depends on the workload that you're running and it depends on the the data distribution for example you know if you have data sitting around on on disk there are different decisions you might make if you know that your data is already sorted or mostly sorted then that may make you choose the sorting algorithm over a hashing algorithm but different tradeoffs like that so there are different reasons why you might prefer one or the other in in each case and that's going to be the job of the query optimizer that we're going to talk about later later in the semester about making those sorts of decisions and tradeoffs to execute queries and again kind of we've we've already discussed the optimizations for sorting so kind of the the chunking or the buffered IO into large blocks to amortize the the costs and this double buffering idea where you're doing prefetching to keep your cpu utilized while you have disk IO going on in the background so you're not stalled on disk IO so kind of we've talked about all the optimizations for for sorting and we've started talking a little bit about some of the optimizations for hashing but in the next class we're specifically going to be talking about join operators and that's where some of the more advanced optimizations for the the hashing based approaches will come up so that's it for today and i will see you next time the bees are set to grab a 40 to put them in your snap snacks and take a sip and wipe your lips to my 40s getting more i'm out he gots the tip drink a drink a drink and then i burp after i slurp ice cube i put in much work with the bmt and the e-drub get us a sanai brew on the dump


So this is connect-disployed version 2. Thank you guys for coming out. So early on a Sunday, I actually survived the con and made it to the end of the thing. So this is version 2. It did version 1 last year. Anybody here for that talk? You want to show up? Cool. Excellent. Thank you guys for coming back. So version 1 was just the connect plus one security tool and what we're doing this year is the connect plus 20 security tools or 20 tools in general to run a scenario. So our scenario is going to be we're using a real time 3D first person shooter game environment to collect the contents of a garbage file off of a server. So that should sound familiar to some of you, to most of you. So let me cover just a little bit about the architecture. We're going to run right into it because there's no slides. It's all demo. So everyone needs to, while I'm doing this, say a quick little prayer to whatever demo God you believe in to make sure that this thing actually functions. I've been testing it all week. That's the bad part about doing a talk on Sundays that you spend the entire time like practicing and working on your talk and making brand new mistakes so that you're nervous as hell when you actually find a good chance to do it. So that's my state right now. So architecture wise, everything's on this laptop. So the version 1, the big differences here were that it was Blender using Metasploits RPC server to talk to Metasploit, only Metasploit. But you know, when you want to talk to Snored and Nessus and Edercap and MAP and all those other guys, there's no RPC server for that. So I wrote an asynchronous, multi-threaded XML RPC server that Blender is talking to that then talks to all the external tools. And again, everything's on this laptop. There's a couple VMs that we're going to use as our victim systems. And there's one external function to go out to the Internet and you'll see that later on. So let's let's run right into it here. Give me just a second to get this. Okay. We've got the connector. Let me get myself all calibrated. And you should be seeing and you are seeing the Blender screen interface. And that's just taken a little bit to start up because it's got some large, large sound files. And he's the process connected, exploit initiated. Okay. Let's run it and actually, let me just leave it like that for now. It's showing the debug stuff up in the top. But we'll we'll deal with that for now. I could restart it, but we'll lose some output in some later scenes. So this is the default room where you start off on. And the main gestures are the same as last year for you guys who saw this. So you lean forward, you move forward in the room, you lean to the right, you move to the right, you lean to the left, go that way. And if you rotate your hips, you'll turn, turn around in the room. So this was meant to be patterned after the, the room in a matrix, you know, like the training room, big white room kind of thing where then they, the big cabinets full of guns came shooting in. So that's the first gesture that we're going to do to bring in the way that we get to the other rooms in there and actually start our, our attack scenario looking for this, this garbage file. So last year also the big differences are last year, every gesture was like when the gesture fired, it didn't, when I made the gesture it did, there was no delay. So you run the risk of when you're hooked up to 20 different things, causing some serious chaos. So this year the gestures, there's a little bit of delay before they happen. And there's an indication that you're actually causing something. So if you continue to do it, you will cause something to happen. So I'm going to raise my hand in like a help gesture. And I want you to notice the lights that show up on there to indicate that you're about to, you're about to do something. So put my hand in the thing, the lights light up, they're going to turn green when the gesture fires and in comes our cabinet full of ammo essentially that we've got. So we're going to start off our attack against this fictitious company by going into the wireless room. So you go into a room just by putting your hand into the cabinet. Now we're in the wireless room. Scanning in the wireless room is of course the first thing to do is scan for access points. So we're going to run IWList scan just by doing their scanning gesture, which is like scanning the horizon. And then we should be scanning initiated from our mind. So this will take a little bit here. And let me just cop to something. There's obviously no access points here on stage.  It'll be a real man and hack it live on stage. And I thought twice about that. And I thought, well, if I did that, I'm sure you guys would hack it before I ever got a chance to. So these are real live access points. They're just not real live access points here on stage. So this is real live output. It's just sort of think of it as a cooking show, you know, and they always have a lasagna in the oven that's already been cooked. That's exactly this scenario. It's just same real live output. And I should explain what these things are. So when I thought about how to represent an access point, when I was a kid, we had this little toy that was like a plastic bubble on a little wood platform with wheels on it and a stick.  I'm sure some of you guys have played with or have seen the same thing. And to me, that's what an access point is. It's like a little thing that's trying to self contain its packets, but they fly all over the place. So these are kind of purposely messy and they're dropping packets all over the place. So the way you target things in connect display, of course, is with a fireball. So we're going to shoot a fireball at this Quest 1824 access point. And the other construct here is that we use the walls in the various rooms to help interface with stuff. Because you can't just do gestures for everything at some point in time. I mean, acting tools are text oriented at some point in time. You got to deal with text. So the left most part is always a context. The right most part is menu options. There are always context sensitive menus. So like in this case, we've selected access points so I can choose to dump the packets of that, which of course is the first stage I'm going to attack. So if you've noticed now the packets out of that Quest 1824 are coming to me rather than going where it was they were going prior to that. And so again, obviously we're not really pulling packets down off an access point, but we are going to use a pcap file that was the result of this exact process. And so when it's done, it shows you some pcap files that you've got to choose from. And we're going to choose this top one up here. And we're going to run error crack against it and see if we can crack the Web key out of this 1824. So it knows we've chosen a pcap file. It doesn't know which access point we want to crack. So there's no option to do it. So we're going to target it again. Just shoot another fireball and it gives us the option to crack web with with pcap. So that's what we're going to do. Choose that menu option. It doesn't do much because it doesn't take very long to get it. But if it works, it's going to show the key as part of the access point itself. Refreshing access points. Oops. So hopefully you can see there's now a little key icon on the on that particular access point denoting that we've got we've got access to that particular network. So we're done in this room. That's all we need to do for wireless hacking that get this access to the network that we're going to that we're going to use. And let me let me set something up here by well first I want to see if this works. Of course, there's Twitter because it can't be a security person without having some sort of access to Twitter. And the reason I want to go in here is that later on we're going to come back here and actually get some hashtags for connect us boy. So if you want to tweet something about connect us boy now's the time to do it. And we'll come back later and see what what you guys said or what there is to see gathering tweets. So this is just some tweets out of my timeline. So what this is done is gone grabbed 20 or visit 10 10 I guess tweets just out of my timeline. And of course the way you see things and it tried to replace the the icons in real time with whoever happens to be out there. And you can see the first one it missed. But let's see who that is.  And it shows up on the on the on the outside of that. Oops, I got a bug where sometimes you can go through walls. Let's see one more and then we'll get out of here. Oh yeah, the good old daily show. Okay, let's go back to the home, but we'll come back to Twitter in a little bit. So if you want to show up there tweet something about about connect us boy. And one more thing I wanted to show you before we kind of move on to there. There's a perch. What I'm calling a perch anyway, that gets you kind of an overview of the entire world. So this is the world of connect us boy version to you can see all the rooms at once. And you kind of lord over top of them, if you will. And so the you can see that first room over there was the room we started. We got the wireless access room. We got the Twitter room. And then the reason I want to show you this this room over here, just in the kind of a far right hand corner is the snort room. So snorts role in this whole thing is to kind of be our visibility monitor, right? So instead of usually snorts what the defensive guys use. In this case, the attacking guy is going to use it to let us know, are we tripping anything? Do we, you know, if based on what we've done, are we showing up on someone's radar? And we'll go in the snort room a little later after there's some more stuff. But you can see there's kind of a rotating barrel that refreshes itself every 30 seconds. There's more, there's a barrel per category of alerts. So the four alert categories in snort, we're only going to worry about the top three. So if, if you see a red, really fast rotating barrel in snort, you know, you've done something that's going to trip somebody's IDS signatures. So that, that's the idea behind that. So let's get out of the perch and back into the home. And we're going to go into a end map and take a look at this network that, that we just got access to from the wireless access points in that. So we have a list of networks to get an idea of what we can, we can see. And so we got a couple different points here. I'm obviously not going to attack myself. This middle one is Defcon. I don't want to attack that. I'm going to attack 100.0, which is our, our victim VMs here. Let me do it again. I should get the little tick sound every time you select something just to let you know that you picked it. And again, it's kind of purposefully slow there. I mean, I'm, I'm delaying gestures on purpose just to make sure that you're not accidentally picking a menu option without meaning it. So that's, that's why it's changing color and delaying and all that stuff. So this is running an end map scan against that network. Collecting in map data. And it didn't take long at all because end maps quick, especially on a local box, which is good for us. So what this did was run, go out and run end map against that, that cider mask and pull back all the data in an XML file, parse the XML file, spit out some, some representations of computers, run it through graph viz and then made a graph for us of the trace route of that network. Obviously, it's not a very large network. It's only got three boxes, but you get the idea, right? So you get a graphical view of the network that you're dealing with and you get some hosts out in the room. They're scrolling their ports that are open is the, is the construct here. So 101 is us. It's our scanner. 100.7 looks like a Windows box. 139, 445 and then 100.8 looks like it's doing some web services and 2222. So it's probably a Linux box. Target acquired. So we're going to target that guy, of course, by shooting fireballs because fireballs are fun. And the best thing I know to get a handle on those Windows boxes is by attacking with Nessus. So we're going to go to Nessus. Nessus. Nessus is a hospital room. So, so, so that's the construct here because you know, we're going to dig into this guy and see what he's, what secret he's got, what he wants to give up. So if I can get over here, come on. There's two switches on the end of the operating table for Nessus. This one brings our victim into the room. And this other one. Nessus scanning initiated. Nessus scan, like it says. Like the nice lady. Nessus scan completed.  So I will cop to another cooking show portion of this thing. Actually I don't have Nessus loaded on here. But there is an integration in Nessus that is a real live Nessus scan from that box. It's just the XML file and kind of replaying because if you're running Nessus, you know, it takes like five or ten minutes per host and I don't want you guys staring at me for five or ten minutes. I like you and all, but so I need to warn you just so you're ready for this because it's a weird thing how you can't hear it until somebody tells you to listen to it. So, what's going to happen here is I'm going to select one of these vulnerabilities that we're going to dig into. We want to be stealthy. So, we're not going after the MS-1s. We're not just going to pop shell on a Windows box using, you know, a interpreter or a Mespoid exploit. We're going to go after this. Shares on privileged access, which is Nessus speak for an open share. But when I select it, it's going to read you the output of the Nessus vulnerability or the Nessus description. So, if you're ready, you won't hear it. So, listen. The following shares can be accessed as a BBIWMGM. FileS, readable, plus content of this share. Test.txt troubleshooting.pcap. Okay, so we've got two files accessible on an open share if you heard it. And one of them is a pcap file. So, I don't know about you guys. Whenever I find a pcap file in a pen test, first thing I want to do is run it past intercap to see if there's anything in there I can use. So, that's what we're going to do. We're going to package this up. And this puts it in a little ammo box that's going to follow us around, kind of like Thor's hammer. Right, so it attaches to our hand. And the fun thing is you can kind of outrun it. You can go faster. And then it will catch up to you. So, and it's going to follow us around to the rest of the rooms here. Well, until we get rid of it, which we're going to do and it's trying to find me and it's running through walls and all that stuff right now. And it's going to catch up to us in the intercap. You can, there's no reason why you couldn't in this particular thing so far. The question was, sorry, I should repeat the question. The question was, can you carry multiple containers? And yeah, you can. There's absolutely nothing stopping you from doing that. In this case one of the time is really all I need for this particular scenario. And that took a long time to get that to happen. I don't have more than one. But when I came into the intercap room it knew because this container exists in the scene that I had a target, that I had a vulnerability and so it gave me a menu option to target that guy. So intercap for me, the hard part of this thing is how do you represent all these various tools that don't have a physical manifestation? Intercap is a big swirling death. So that's what it is. So we're going to send this to intercap. Well, another thing to listen to. Listen to the sad tone in her voice. I didn't tell her to do this but she sounds so sad when she says this. Target sent to intercap. Intercap exploiting phone. Intercap finished. So it sounds so sad. Doesn't it sound like target sent to intercap. Okay, so what happened just then? We knew we had an open SMB share, right? So there's a script attached to that that knows if there's an open SMB share to run SMB client, pull down files, if there's a file, send it to intercap. Intercap parses it and spits out any credentials that it happens to find. So now we've got creds that we can go use. So let's go back and root. Sounds like a Linux box. So let's go to our messes area. Which is where we pick targets that we're interested in. We've got the windows guy targeted, it's untarget him. Target acquired. Target acquired. I've gone crazy. Let's untarget this guy. Come on. Okay. And let's be accurate and target this guy. Target acquired. Targeting is important in games and it's also important in this game. So we had a guy with 80 and 443 open and we have some credentials. Let's go to the web room and see what we can do for those. So here's our target came with us into the web room. Let's scan him for URLs. This is just going to run WGIT against him and see what we can find. Dot dot the URLs completed. Sounds like it's it announces when it does. Something announces when it's done. So if they happen almost simultaneously it sounds like that where it kind of came over top of itself. So you can see we didn't really get much, right? So let's use our credentials that we just got from Ettercap. It gives us this option because it notices that it just ticks on. I'm going to use credentials kind of a boolean flag. And let's scan again. Gothering URLs. Gothering URLs completed. So now we got quite a bit more. So let's just WGIT using those credentials that we had. And there's a whole list of URLs we can scan through them. The gesture for that is just you put your left hand behind you a little bit and then you do kind of like give me more data movement. So we've got a bunch of URLs we can pick from. We're going to pick this challenge three guy just because I know that it works. And now that we've got a URL selected, it gives us an option to launch SequelMap. So that's what we're going to do. We're going to launch SequelMap and try to get some more credentials and see if we can kind of stealth our way. SequelMap initiated. To retrieve our garbage file. So when SequelMap finishes it's going to display whatever it gets. SequelMap completed. If your results include hash values, you may wish to visit John the Ripper for assistance. A little foreshadowing maybe. A little obvious foreshadowing. So obviously we've got a username administrator and a hash out of the back end database. So that was the SequelMap just running in a password. Give me a password mode. And just like we did before, we're going to package these up in a little module because they're not quite complete. We need more data out of them. So we're going to package it off to John. Packaging your creds. Say hi to John for me. Okay. He's got a sense of humor. Okay, so let's go to John. John. John. There's a little red box in the corner because I don't know what else to do with John. The cool thing in Blender is I'm not spending much time on Blender. I have questions about the game engine. They came out creds. One cool thing is it's got a distance sensitive sound so closer I am, the louder the sound, farther away, the quieter the sound as well. So it's got some, I guess those are standard game engine features now but they're new to Blender. So we're going to crack these credentials by sending them off to John. Credentials sent to John. And when he works he's going to display them on the wall. Completed. So John did this work that fast because that was a real-time John crack by the way, it wasn't a cooking show type thing but that password obviously is in John's default password and database. So it just took that, it was a MySQL hash cracked it against that and so now we've got administrator creds with an oddly familiar password. So let's select those because we're going to use, make use of those and... Credentials selected. So I left this kind of raw. I could have done the same ammo box thing but I wanted just an opportunity to talk about like one of the coolest things in Blender is the Python scripting engine in there. And so for example this object, me right here I'm just called the player in the scene and you can attach Python dictionaries to anything, any object inside Blender. So when I selected those credentials all that really happened was it took this string if you're a Python guy you'll recognize that just a field, value, field, value, right? So username, administrator password, Gibson hash and attach that as a cred to the player. So anything else inside Blender can make use of that same thing. So it kind of has its own internal data transfer mechanism and we're going to use these creds next. So we got a real administrator cred and let's see what's... Let me check my cheat sheet here, sorry. All right, let's go... Let's go back and select our Windows box since we got an administrator account. Okay, let's unselect that dude and we're going to select that guy. Yes, we are going to select that guy. Talk it's acquired. Talk it's acquired. Fireball's bounce. Talk it's acquired.  Okay, one target acquired. One at a time. We'll work on the mass module, maybe that's next year. Target a hundred things or something. And we're going to go to obviously the last two rooms here in our scenario. So what we're after here is like I mentioned the contents of Garbage File. So the final goal is to get some forensic work done. The thing that's going to help us get onto the box however is Metasploit. Metasploit. Let's see, maybe we have a console. Yeah, we do, okay. So we have a console output from Metasploit. It's complaining and bitching about not being updated but I didn't want to break anything. So it's not updated recently. Let's go up here. So what this is going to do is run PSExec to get an interpreter session loading on the box. And it's going to run, I don't know if you guys were here last year for Wes McGrew's talk but he released a module that gets you a forensic interface, just an MBD server network block device server on a box. So through the interpreter you can then run any forensic tool that you want. So that's what we're running against that. So it's just PSExec using those credentials that I just showed you and it's attempting to run this module and as you can see it failed dramatically. So sometimes that happens and you just run it again and we can do it using gestures. So we're loading. It's going to try again if it works it'll serve up the C drive as a network block device and there it is. Serving up a C drive and the entire C drive is now available to us as a network block device. So that's awesome. And we're going to use that in the final stretch here, wherever you guys said to the demo guys, keep saying it because we're doing pretty good. We're going to go to the forensic room where we've got raw access to it. So we're going to connect using MBD, just MBD client the regular Linux client. And it's made the connection giving us another option to search the garbage aka the recycler bin in Windows. Searching. So this kicks off a job that's going to take just a little bit so let me explain kind of what it's doing while we're waiting for the output and then we'll go to some other rooms who are waiting for the output also. Searching through. So it's got a raw much like a DD image on there. It's going to run FLS out of the sleuth kit and just look for anything with the word recycler in it and then display it up on the wall. So in the meantime, let's go out to the perch and see if we have some snort that we can take a look at. And it looks like we do. We've got a couple barrels so let's get out of the perch and see if we can go see what alerts we've triggered Here we go, snort. Snort. So I'll only do one and then we'll move on to something else here but all you do is just touch the barrel and get close to it or something interfering here and it coughs out just a little summary of what alerts are there for that particular barrel so you can see these are like priority two alerts in snort. So we've got some port sweeps that obviously are from our M-Map scan and then some other stuff probably from the SQL map that we did. So that's the snort integration and while we're waiting for our forensic output it will announce it to us when we get we don't have to go back to the room to check it'll say forensic output received let's go to Twitter and see if I ran into stuff let's see if there's any connected stuff besides my one sorry tweet early this morning gathering tweets alright let's see what I'll try to knock some of these down because the fun thing about these they don't have much weight to them much like tweets don't so you can kind of knock them over if you hit them enough times with fireballs oh come on fall over please of course now it's not gonna haha let's see what was there yeah hack the gifs in exactly yeah that's what we're doing let's see what else we got haha cool come on forensic output see this a lot of people default icons and by the way I should have said all the code for this is gonna be available site. So you saw it in the initial intro there. It's just ponlabs.com slash defcon20. And everything that's here will be available there. You're going to give me just a little bit to clean it up because there's a lot of bad code still left in here. But it will all be open on there. And Blender as well as open source, if you go to blender.org, it runs on Linux Mac, Windows, and any Blender file that you create like this can run on any platform, of course, given assuming that you've got all the rest of the stuff on there. I mean, obviously, if you're going to use that mapping, you have to have a map as well. So we're going to have all that stuff loaded. So again, everything out of here will be all for forensic output received. Cool. So we got our forensic output. So let's go back home. And let's go back to the forensic room. Let's go around. So it did a FLS against that.  So what we've got is the I know number on the far left and then the name of the file. So this is just everything that has recycler on that particular Windows box. If you have ever done forensics and recycling bin, all that kind of stuff, you'll know that the info to file, which I'm trying to select down here in the very bottom is the kind of the index for everything in the recycle bin. So we're going to choose that. There we go. Info to and a connected sport knows that info to file can be parsed with the refee UD and it gives us the option to do that. So I'm going to choose refee UD and it's going to pull down that file retrieving for forensic output received.  But we can go back to the beginning of this output. I think we can. Okay. So it just tells you where the file was and then the important thing to pay attention to. So the index number is the number that gets added to DC. So DC one will be this file up here. And if you notice the file's name is C slash numbers root slash period workspace slash garbage dot text, which sure sounds like the file that we're interested in. So let's go get our previous output here, search garbage again. Searching and this is going to forensic output received. So I ran that same exact thing that took a couple minutes last time, but it caches it. So it takes a lot less time out of the second time through. So we're going to pick DC one, which we got from our index on there. And then it just works. It's the grand finale. So let's hope it works. So we're going to go ahead and type that file out and see what it's got retrieving. Let me go over here. It's displayed the output on the back wall. So let me just go here and turn around. And hopefully this will work. And we'll be the end of connect exploit version two. There we go. There's the the output of that file. It's in that place where I put that thing that time, which if you've ever seen if you're seen hackers recently, you will recognize that. So that's connect exploit.


Yorah, tato. Ko Mississippi, Teawa, no Minneapolis, Ajo. Ko Brock, Tokufano, Ko Arthur, Toko Ingoa. Sorry, my first time doing that. Sorry. I'm Arthur Brock, originally from the Midwest United States. Did you notice I left Mountain out of that? We don't have any there. So I feel like what I'm supposed to talk about is this amazing new technology that we've created, Holochain that's like way beyond blockchain and all that kind of stuff. But what I actually want to talk about is nature and the power of designing from living systems. And really what comes to mind, I love what Naval was saying about how the early arrival of a technology is often destructive. And I connect that to because we haven't actually learned to pattern it in the flows of life, in the patterns that nature uses. And that's actually what I want to talk about. Because so you probably already know this on some level. But all living systems, they thrive or they dwindle. They live or they die based on the integrity of patterns of flow. And just a quick example, if we were to block off my airflow for a few minutes here, this living system, we call a human being, would cease to be a living system. We'd break the integrities of that. We would have a bag of meat. The same stuff is here. But the integrity of the patterns of flow have been broken. You literally no longer have a living system. So when you go to the doctor and they check your vital signs, what they're doing is they're checking in on the health of the flows of you as a living system. Now, how do we do that for communities, countries, businesses, schools? Where's that pulse? What is it that we actually use to check in on this? I would assert, I want to reclaim some language here a little bit creatively, because English has this great word. I would assert that what we use are current seas. Trying to have you think of it not just as money, but literally current seas, the ability to see flows. Money is a very small part of that picture. It makes flows of exchange of goods and services visible. But if you think of a more concrete example, I should let me just check in for a moment. Who here has experienced, especially these kind of collective spaces, communities, businesses, living systems, where all the stuff was there, but the flows weren't quite right? You did not have a thriving living system, a thriving community country. So you've run into these issues. What if there were ways that you could learn to make very small shifts that would over time of repeating these small shifts actually produce massive changes in the pattern? That's what I'm interested in, because from a living systems view, there's some massive changes we need to be making. And so I just want to take an example again, something that's a little bit familiar, like a school. Normally, the currencies that get used in a school is like the degree is a reputation currency. We have credits to be able to count the different stacks of participation in different domains and grades to measure your performance in those things to make those flows visible. Your transcript is like your balance sheet. You can see how those are currencies we use. We create symbol systems all the time to coordinate flows on all scales. A few years ago, my son's school had a little bit of a crisis. It was luckily a little bit of a progressive school, so I had a lot of creative room when this happened. I was asked to step in as the director temporarily and reboot it to basically save the school. I said, I would do that if I could rejigger the educational model. And it was for self-directed learning, like the kids actually designed their own education. So the kind of currencies that we put in place were like little dashboards on the wall. The kids had a little dashboard with sticky notes in different columns. And they'd put their intentions in projects there. And it would make visible what kind of support they needed from the staff. It would make visible to the other kids what things they might want to participate with. It ignited the passion of kids that were a little slower, a little less clear to find their intentions in projects as they started seeing the kids that were doing that really have their passion awakened, they didn't want to miss out. They wanted to try it out. And so that's an example of a currency hack. And this is work that I do all the time in hacking currencies. And a lot of my inspiration comes from this naturalist in Northern California called Paul Craftle, who is a kind of eco-warrior that goes out into the world with a small hand trowel. He goes out in rainstorms and observes patterns of flow and just makes small, subtle shifts. And he does this every rainstorm. He does this over time. He has healed complete hillsides, watersheds, ecosystems by learning the kinds of little nudges to be able to make. And I would assert we all have the capacity, we all have that power to make those little nudges if we can learn to see them. Unfortunately, I can't really go a lot deeper on that today out of time. But I would invite you to come and join in the conversation. Like, as I mentioned, Holochain, that's a technology designed on the patterns of nature. I would love to explore any of those kinds of things, but just engage with living systems design. If imagine if our economies, our currencies, our markets were attuned with the patterns that nourish life. That's what I invite you to join me in. Thank you.


Thanks Bex. So, today we're going to talk about a good trick for cleaning your hands.  I mean usually wear these nice nitrile gloves, but sometimes you get on your hands and you need to clean your mouth. Do not use things like bar salt or vinegar, as some people might advise, because that actually breaks down the resin and it can be absorbed into your skin. So here's a good trick. Poppy seeds. Take some poppy seeds and some normal hand soap and so we teach this little thing by the second axis like an exfoliant. You can rub it in, do it dry, do it dry and then wash it off and that just works fantastic. So that's a quick little tip. Stay clean and have fun.


Morning class. Today we're going to have a look at color bias between two blues. Every color has a color bias towards one way or the other on the color wheel. It's harder to see though when you look at a color in its mass tone. So these mass tones, this is an ultramarine blue and a thalo blue, are quite similar. This one looks a bit darker but essentially they're reasonably close to each other. When we start to add white to them though, to create a tint, this is when you can really see which way the bias is on each pigment. So now you can easily see how green the blue on the right is compared to the one on the left, and this is just a very quick example of color bias. If you then want to mix a green between these, you'll see the difference. You can see how the green on the right is a lot brighter or a lot cleaner green, even though initially when we look at the mass tones this looks a lot darker. So you need to have a quick understanding of pigments to know how far you can push them or how you can create the actual tone you're after. Sometimes you don't have to add, you know, it's compliments to tone it down, you can just be using the wrong blue. Okay this is Will Kemp from Will Kemp Art School.


Welcome to All Hands Update, I'm Petty Officer Ian Cotter. Women accepted for Volunteer Emergency Service, or WAVES, was established July 30th, 1942, to augment the war effort. At the end of World War II, there were more than 8,000 female officers and many thousands more enlisted WAVES. I think it was crucial for establishing a couple of things. One is that women can do any job, that the military is not solely a Mayo Preserve, but second, it showed just how important it is to get the best of America, the best of America has to offer, whether male or female. Today, women serve on surface ships, submarines and nearly every community is open to them in the Navy. This year, the Navy promoted Admiral Michelle Howard as its first female four-star admiral. Women throughout the fleet continue to make indispensable contributions to our Navy mission and operations.