Okay, next up, we're going to learn how database indexes work, how we should use them, why we should use them, because they somehow apparently make accessing data in databases faster, and Curtis is going to talk to us about how that actually works. Afternoon, I hope you've all been enjoying yourselves. I'm going to have to run through this fairly quickly because the last time I ran through, this had took me the full half hour, and it's grown since then. So, I am Curtis Mooney, I'm known as Funky Bob, to many people in the Django community and outside. If you want to tweet me, there's my address and GitHub, I'm Funky Bob. So, as a quick overview, we're going to be talking about Postgres and this indexes, and Postgres, when you make a query, we'll try to optimize that query for the minimal cost. Now, cost is based on an awfully large number of factors, but a most significant one that you're likely to run into every day, is the number of pages of data that are involved in the query, the more pages, the bigger the cost, and a lot of the costing is actually expressed in terms of numbers of pages. By default, in Postgres, a page is 8K. This seems a little odd for anyone who's used to storage, but it's there, it's chosen, think about it at 8K, chance of data. Indexes in general are a cost storage time trade-off. So, you are actually spending more on storage in order to get a faster query. So, we're going to start with a very simple, very simple schema here for a threaded forum post. We're going to have our account, a user account. Very simple, a counter ID named data birth. We're going to have a thread which has an account ID as to who created it, and a title. And then we're going to have our post table and a post table is going to contain most of our data. So, it's got a post ID, it's got the thread that it's a part of who created it. When it was created, whether or not it's visible has it been moderated out of existence, and what the actual content is. We're going to go through a number of queries and try and optimize them and keep them efficient, so that our users don't get annoyed and go somewhere else. So, we've got a first query of what are all my posts. Second is how many posts have I actually made? Because some people want to know how prolific they are. What are all the posts of the current thread? How many posts have I made on the current thread? So, am I involved in this discussion? And also, all the current posts for a thread for this month in order. So, when you were reviewing a thread, look at it in the current order. I've seeded my database with some random data, as we can all see. It's nice and simple. I don't know. Not that simple. Okay, I had a lot of help in generating this, but basically you don't have to understand what's going on here. But the major points are that I'm generating 100 random users, 1,000 random threads, and 100,000 random posts in those threads with 20 random words each. Associated with different users, different threads, whatever. Statistically well distributed, but just still random. This basically costs a space, and we can see our thread table has cost us a total of 160k, 112k in actual data. Our accounts table is even smaller, because there's very little actually in that. And our post table is a massive 27 meg total, 24 meg of data and 2 meg of index. Now, I didn't declare any indexes, but there's one there already, because I declared the primary key, unique, and post-grass is actually going to create an index so that it can track of that and make sure that it is unique. I don't have a choice. Tables are really just stored as a file and a sequence of pages. So our accounts table is tiny. Our thread table is a little bit bigger, and our post table is just huge. It is enormous, 24 meg long stream of pages. Each individual page has a small header at the front to let us know, is it live, what's it going on, how old is it, what transactions it's involved in? And so on. Then there's another section, which is the item ID data. And this is a list of pointers into the page of where every tuple actually starts. So every tuple in that table is referenced by page number and item ID. So this together allows you to uniquely reference a record in your database. So they can actually be shifted around within the page, as new versions come along and older versions go away, without the reference to them changing. This makes life a little more efficient for everyone trying to deal with transactions and data updating. So here's our first query, pretty straightforward. Do anyone familiar with SQL? We're going to get everything from the post table where the account ID is our account number. And I'm going to analyze what Postgres does by using explain analyzer. And that's going to get Postgres to output its query plan. What it plans to do to satisfy this query. Here it is. And we see here what it plans to do is the sequential scan on the post table. And it's going to cost about 4,379. Now that doesn't make any sense. We don't know what that is on a scale, but it's a useful number. Whilst it's doing this scan, it's going to filter for where account ID equals one, which is what we asked it to do. And note that it's going to remove almost every single one of those 100,000 records. So it's kind of a waste of time of a lot of that. And it takes 32 milliseconds to do this work. Yeah, man. Next page. So, fault table scan, what does it mean? Start at the beginning, work your way all the way to the end. I don't think there's a single person in this room who thinks that's the most efficient way to do this. But it's the only option Postgres has because it doesn't know where everything is. All 24 meg of it. So index is to the rescue. What is an index? Basically, it's in this case a key value store where the keys are the list of values in the field that we've asked to index. And the values are the page number and item ID that we mentioned before. So this means that when Postgres wants to find something, it knows what page to go to. It's also a sorted list, at least in the case of B-tree indexes, which is the default indexes in Postgres. We'll get onto this later on. So it sorts the values so it knows how to find them efficiently. In this case, what happens and why is this a win? Apart from being the sorted list is we store fewer bytes. Just the fields we're interested in and therefore access fewer pages in order to satisfy the query we're trying to execute. What is a B-tree that I mentioned before? It's a self-balancing search tree. So you start with a bunch of nodes which divide up the records by a low and a high range. They'll say everything below this value, go look over here. And they'll grow the tree according to a balancing algorithm that makes sure that it's as flat as possible. And the fan out, the number of steps between depends on how big a record is and how big it takes. So in the case of here, because we have an 8K page, and it only takes about 16 bytes to reference a page and item, you're looking at a few hundred pages next level down. So it fans out very, very wide. So you can actually get very flat trees for large number of records. Then each one of them eventually, somewhere down the tree, refers to the leaf nodes which actually contain that sorted list of keys and values so that we can scan through them to find the values that actually matter to us. So we've chopped down saying, okay, we want the values that are greater than this or less than this and follow the tree to say less than greater than here we go. And then you can look through that page and get the answers. There's another variant called a B plus tree where each of the leaf nodes actually has a pointer under the next one. So that if you want to scan from one page to the next, you don't have to climb back up the tree and back down again, you can just keep going. So we're going to add the index and it's a simple the same create index on this table for account ID. This has a cost of course, now our page for the post has 4.4 meg of indexes. So that's a doubled in size, which is not surprising because it's an index across one field should be about the same sizes on the primary key. But in comparison to the original table size, it's tiny, it's only two meg compared 24. So let's have a look at that query again. What's our query plan? Well, now we have a bitmap index scan on that index, which means postgres is going to allocate a chunk of memory to build a bitmap to say this record is in, this record is out, this record is in, this record is out. And use the index scan to determine which pages it should mark as being of interest. And from that, it can then decide I only need to read these pages and when I get to that page, I only need to read these records. And it can scan through the index and just check the account ID. Then it will do a bitmap heap scan, which takes that index scan result and actually goes through the data and picks up the pages. So we see here that now our costs have, on the bitmap index scan, whoop, our cost in total now for our query is 1439. Where previously, it was 4379. I think it would also be the much lower number. And the execution time is now 6.7 milliseconds, whereas before it was 32 milliseconds. Now when we're talking milliseconds, that's not going to make a big difference to your average user, but when you've got a few thousand users, that starts counting. So let's move on to our next query. We're going to select account of posts, where the account ID is my account ID. And the query plan, very similar to originally, we're going to sequentially scan the post table, which costs us the same amount. But now we have to aggregate and count how many records actually matched, which means we go from that original value up to just a little bit more. Not much more expensive, but just a little bit more. Now when we add our index into the mix, we get a very different answer. Now it's going to be an index only scan. Because all the information we need is the account ID. We don't need any other information from the records. We just want to count how many records match this ID. We can actually get the answer from the index itself and leave the table data alone entirely. So now our cost has gone down to, well, the initial scan is 17.97, and then when we aggregate the answers after that, it's 19.36. So we've gone down from 4,000 and something to 19. And our actual query time has gone from 34 milliseconds. Down to 0.8 milliseconds. So I haven't actually done what the order of the, what the actual multiplication of that is, but when you're down down to better than 34 times the speed, that's not a bad result. So next we have query number three. Select everything from the post table, whether we're on thread ID one and it's visible. Because we aren't interested in the visible queries. Our initial query plan, of course, is sequential scan on the post table, filter for visible and thread ID equals one. So we've got two terms here. And removes 99,961 out of 100,000. So we've wasted 99.9% of our effort, reading rows that we weren't interested in. But it only takes 14 milliseconds. Thank you. So let's create another index. This time on the thread ID, because that's what we're searching on this time. So now our query goes from what it was into, oh, that's a bit better. So now we have our bitmap index scan and bitmap heat scan again. Our cost has gone down to 339. And it was at 4,379. And previously we were taking 14 milliseconds and now we're down at four and a half. Not a bad improvement at all. Let's snack on to query number four. What's the count of the number of posts in the thread that are visible, that I posted. Again, the initial query. Again, sequential scan, we filter on all these different terms. And 99.99% of the rows don't match. But we're still costing us 4,629. This is getting repetitive. So what's the query plan for this? Well, actually it turns out to be quite a big one. This is one of those things that Postgres does very well, is it will combine indexes that it knows about. So what's happened here is it's done a bitmap index scan on the thread index and the account index. And then it's going to end them together and then use the result of that for the heat scan. So it's actually on a bitmap, both of the indexes and whatever matches both of them is obviously a record that it's interested in. And then it can recheck its conditions and make everything's right. The recheck condition is there because of the multi-versioning that Postgres does. And it has to be sure that it got the right one. But usually it's a very cheap check. It has to read the rows anyway. And then of course it has to filter on visible. Now we were at 4,629. Now we're at 21. That's a dramatic improvement. We were at 13, 14 milliseconds. Now we're at 399 milliseconds. Mm? Sorry, 0.399 milliseconds. I was only out by 1000 times. Thank you for reading my slides better than I do. We can do better. Believe it or not, because we can create an index on multiple fields. So let's create an index on the thread ID and visible because that's what we're actually filtering on. So for query number three, this helps a lot because that's actually what our filters are on. So this time we've gone from our original value though with the old index. Now it can actually scan down and do the bitmap index scan on both thread ID and visible. Get a better result and come back at us at 300 to cost of 300 and in 2.77 milliseconds. So it was at 4.58. So we've actually dropped an order of magnitude. And it was at a cost of 339. Now it's at a cost of 307. Again, slightly better, not a huge improvement, but an improvement. Does this index help with query four, which also wanted to filter on the same two? Yes, it does. And in fact, our app query becomes even smarter, just a little bit cleaner. So we have our bitmap index scan on the post thread ID and visible index. And an index scan on the account ID. And again, we add them together. Then we filter interesting that it already filters on visible again. But our results is we're at 0.35 milliseconds. We're previously at 0.399 as Tim Healthfully pointed out. So again, small improvement, but an improvement nonetheless. Can we do a better index for query four? Because the query three one was good, but query four uses three different fields. So let's index all three fields and maybe we'll get something better again. And remember, query four is account, which means if we have all the information we need in the index, we might get an index only scan, which is the most efficient we can hope for. Well, sure enough, we get an index only scan because all three times that we want to filter on are available in the index. And now we're down to 0.097 milliseconds. It was 0.355. So we've stepped down and ordered magnitude again. So now we've gone from 13 milliseconds to 0.39 to 0.35 to 0.09. That's a couple of orders of magnitude improvement. Anyone know what this interesting word means? Yes? There ain't no such thing as a free lunch. There ain't no such thing as a free lunch. So we've paid for this. What did it cost us? Well, storage. Storage of what it cost us. And of course, when we're talking databases, storage isn't just the amount of disk space you use. But the amount of RAM it's going to need when it needs to read that. And a single user, that's not such a big problem. But when you're scaling to hundreds of users accessing this, the more pages of data you can share, the better you are. So we've got a situation where we now have four indexes on the one table and they're taking two to three megs each. Remember, some of them are a bit bigger because they're indexing more fields. So that's a cost that we have to consider. There is another cost. And that is that actually inserting or updating any rows, mean we have to update the indexes as well, each and every one of them. So you get this thing called right amplification, where just writing one record, you actually have to write three or four records for the indexes as well. There is a nice solution for some of this, partial indexes. Why are we storing in the index? Rows of references to rows we know we don't want. We're not interested in the ones that are marked not visible. So why do we store them in the index? Can't we tell our index to ignore them? Of course we can. So we do what we did before, but this time we say, where visible is true, we leave visible out of the index and just say, we only put things in the index where visible is true. This gives us an index that is now, oh look, it's only, well, we've saved 300k. Not a huge amount, but it's an amount and it's a bonus. So what does this do for query number four? Well, we've now got our index only scanned across our new index. And our time is at 0.079. There's previously it was 0.097. So we actually shaved another almost 20% off. And our number of pages hit, our cost has gone from 4.45 down to 4.33. So that root measure of our efficiently being actually improved. You will find, and I found this when trying to produce these slides, the actual execution time will vary due to a large number of factors, like anything else you're doing on your system. If I was playing a music that was encoded at a higher bit rate, that would throw up my time here a little bit. Very hard to reproduce numbers. OK, this index actually also helps query number three, which doesn't use all those fields, but it does use thread ID and visible. So here's now what we get. And we'll see, we've got our bitmap index scan on the new index. And our time is at 0.263, which has actually come down from 0.277. And the number of pages hit is pretty much the same. Our cost is almost identical. So we haven't really improved that much, which is why the time is pretty close to what it was. But it actually is using the same index, which means we could maybe get rid of an index. But how can we use this index when we're not referring to all the fields in the index? Well, that's because the index, remember, is a sorted list of keys to values. And we're interested in filtering on the thread ID. So in query number three, we want the thread ID. We can scan across the thread ID. We've effectively got two indexes in one here. We've got the thread index and the thread in the count index in the one table. Let's move on to query number five. Where we're going to select everything from post, where thread is number one. It's all visible. And it was created sometime in the last month. So we've got from now minus one month. And again, with no indexes, big linear scan, big expensive query, 5,000, because it actually has to do a little more work in comparison. Now with the index is in place. We've got our bitmap index scan on the posts thread ID account ID index that we created with visible missing. It can then do a heap scan. It's removed the extra stuff it doesn't want and the created records. It can now filter the extra 37 rows out, but it's only going across. 87 rows instead of 100,000. And our result is 33 milliseconds comes down to 0.33 milliseconds, 100 times improvement. We've gone from a cost of 5,100 down to a cost of 307. But maybe we can make an index specifically for this, because we're querying across created. We're interested in that in the index as well. Now our query plan becomes almost trivial. So index condition is on thread ID and created being larger than this value. So we know an index condition and an index scan and get our results. So we've gone from 0.33 milliseconds to 0.094 milliseconds. From the original 33 milliseconds that's a huge improvement. An original cost has come down and is now down at 0, 12.46 from the 5,700 that it was. That's not a bad improvement. So why did creating an index make such a big difference to our ordering query plan, which had to spend a lot of time sorting. It had to allocate only 25K of memory to implement the sort. But that cost was quite significant. Why did we get to skip that? Because, as you remember, the index is a sorted list of values. So it's already done the work of sorting the created values with grouped by the thread ID. Save work by doing it once. When you insert the record, figure out what order it would be, save that in the index. The index does this for us. Saving work by pre-calculating our data, we can do it in other ways. Because the values that we put into our index can be calculated rather than just being the values, the raw values from our fields. So here's an example. What if we wanted at times to tell people to have an idea of how many words people are putting into their post? To go around and count the number of words in your post, run statistics on that could actually be quite expensive. So we have this index here where we get the array length of doing a regex split on the comment by anything that is a space character, many groups of spacings. And that will create an index with that value already figured out. So when you insert the record or update the record, it calculates that. When you want to run statistics on it and you say in your query, I want to know the answer to this value, Postgres will just go, oh, that's in this index here. I'll just look it up. I've got your key. Here's your value off we go. Now we can save it by calculating these things once, when it matters and leave it alone. It's like having a cache, but with a hardwired exploration policy, it is updated correctly. Now as I said earlier, Postgres supports more than just betries. It supports hash table indexes, which are excellent for doing equals comparisons, but nothing else. You can't scan them linearly because they're not sorted. You can't do greater than or smaller than comparisons because they just don't support that. Sort of look up and they can only support one field in the value. But if you need to do that, they are very efficient for that. Then there's generalized inverse indices or gins, which are really, really powerful when you want to do something like full-text search, and you can use them to express lots of different functions on your queries that you just couldn't do. But they're very good for working with field types that have multiple values, such as text documents, JSON blogs, XML trees, and so on. Very, very late times. Then there's block range index, the BRIN, which for every block of data in your table, every page will actually across that index, store the minimum and maximum value. And that's it. So that when you're searching and you want to find things within a range of values, you can trivially discard pages that you know don't have values within those ranges. They are absolutely tiny. For comparison, I did a BRIN index on the creation field. So for a B-tree, it would be 2.2 megabytes. For the BRIN, it was 24K. And it can't get much smaller than that. However, they're not very useful. They don't cover a lot of cases. They do come in handy when your table starts getting very, very large. So to summarize, index, speed, filtering, and sorting in comparisons. They can also help with other operations. If you use the right index for the job, you can see we can get 1,000 fold improvement in performance. They add a cost on insert and update. So don't just go add them to anything at all. But they can also save you work by doing it once when the value changes are set and not updating it again when it hasn't changed, not calculating it again. Ah, so I made it just in just an under 30 minutes. Thank you. That's it. Any questions? And I want to thank these people who I know from IRC. Rodium told on IRC on free note and who's absolutely everything about Postgres. It seems. We have time for one question, sorry. One question. Anyone, please? Come on. Yeah. Whoop. You were first. You were first. Right up. Thank you. Some of the queries you added in next to you, you saw 1,000 fold improvements. That cost you were saying with updating is that conversely is that 1,000 times cost or is it much smaller? No, no, the cost of updating is much, much, much smaller. It does mean that every time you insert a row, it will have to insert a row in the index as well. But that's not a very large cost in that respect. It does have to rebalance the tree or update the table in the way at worst. But these are algorithms that are worked out to be very, very efficient for the needs. The operations are going to perform on them. All right. That's my one question. I've over run my time by a minute. But if anyone wants to talk further about this, you can hit me up on IRC on Twitter or talk to me. I'm here until all the slides. All the sprints.