PostgreSQL Indexing : How, why, and when.

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 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 it took me the full half-hour and it's grown since then so I am Curtis Miley 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 in this indexes and Postgres when you make a query we'll try to optimize that query for the minimal cost our 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 then a lot of the costing is actually expressed in terms of numbers of pages by default in Postgres our page is 8k this is seems a little odd for anyone who's used to storage but it's there it's a Chosen think about it as iCade chunks 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 gonna start with a very simple very simple schema here for a threaded forum post we're gonna have our account I use your account very simple account ID name date of birth we're gonna 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 title table is going to contain most of our data so it's got the 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 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 oppose 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 no not that simple okay I had a lot of help in generating this but basically I you don't have to understand what's going on here but the major points that I'm generating a hundred random users a thousand random threads and a hundred thousand random posts in those threads with twenty 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 160 k100 and 12k in actual data our accounts table is even smaller because there's very little actually in there and our post table is a massive 27 Meg total 24 mega 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 Postgres is actually going to create an index so that it can take 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 counts table just tiny a thread tables a little bit bigger our post table is just huge enormous 24 Meg long stream of pages each individual page has a small header at the front to let us know who is it live what's going on how old is it what transactions its 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 topple 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 - 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 analyze 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 a sequential scan on the post table and it's going to cost about four thousand three hundred and seventy nine 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 hundred thousand records so it's kind of a waste of time for a lot of that and it takes 32 milliseconds to do this work next page so full table scan what does it mean start at the beginning work your way all the way to at 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 make of it so indexes 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's sorts the values so it knows how to find them efficiently in this case what happens and why is as 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 and they'll say everything below this value go look over here and that'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 down here we go and then you can look through that page and get the answers there's another variant called a B+ tree where each of the leaf nodes actually has a pointer unto 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 as simple as saying 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 size it's on the primary key but in comparison to the original table size it's tiny it's only 2 Meg compared to 24 so let's have a look at that query again what's our scan 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 does it 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 can't look our cost in total now for our query is fourteen hundred and thirty nine where previously it was four thousand three hundred and seventy-nine I think it we can all see this a much lower number and the execution time is now six point seven milliseconds whereas before is 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 the count 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 seventeen point nine seven and then when we aggregate the answers after that it's nineteen point three six so we've gone down from four thousand and something to 219 and our scan our actual query time has gone from thirty four milliseconds down to 0.8 milliseconds I haven't actually done what the order of magnetization of that is but when you're done 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're only 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 ninety-nine thousand nine hundred and sixty one out of a hundred thousand so we've wasted 99.9 percent 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 in - oh that's a bit better so now we have our bitmap heat index scan and bitmap heat scan again where our cost has gone down to 339 and it was at four thousand three hundred and seventy-nine 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 as 4629 whoo 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 the 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 heap 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 recheck condition is there because of the multi versioning that Postgres does and it has to be sure they've 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 unvisible now we were 4629 now we're at 21 that's a dramatic improvement we were at 13 more 40 milliseconds now we're at 399 milliseconds hmm sorry 0.39 9 milliseconds I was only out by a thousand times yeah 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 3 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 trait ID and visible get a better result and come back at us at 300 million of 300 and in 2.77 milliseconds at point two seven seven milliseconds so it was at four point five eight 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 for which also wanted to filter on the same - 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 felt a interesting that it already filters on visible again but our result is we're at 0.35 five milliseconds whereas previously zero point three nine nine as Tim hopefully pointed out so again a small improvement but an improvement on the less can we do it 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.3 55 so we've stepped down an order of magnitude again so now we've gone from 13 milliseconds 20.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 so we've paid for this what did it cost us well storage storage Awards 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 got a situation where we now have four indexes on the one table and they're taking two to three makes 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 write amplification we're 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 don't 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 we're visible it's true we leave visible out of the index and just say we only put things in the index we're visible is true this gives us an index that is now oh look it's only well yeah 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 scan across our new index and our time is at zero point zero seven nine there's previously it was zero point zero nine seven so we actually shaved another almost twenty percent off and our number of pages hit cost has gone from 4.45 down to 4.33 so that rude measure of how efficiently being is actually improved you will find and I found this when trying to produce these slides your actual execution time will vary due to a large number of factors like anything else you are doing on your system if I was playing a music that was encoded at a higher bitrate that would throw up my timing a little bit very hard to reproduce the numbers okay this index actually also helps query number three which doesn't use all those fields but it does use thread ID invisible so here's now what we get and we'll see could our bitmap index scan on the new index and our time is at 0.26 three which has actually come down from zero point two seven seven 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 paint but maybe get rid of any news 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 this rate ID we can scan across the threat ID we've effectively got two indexes in one here we've got the thread index and the thread in account index in the one table let's move on to query number five where we're going to select everything from posts where thread is number one it's all visible and it was created sometime in the last month so we've got from now - one month and again with no indexes big linear scan big expensive query five thousand because it actually has to do a little more work in comparison now with the indexes in place we get our bitmap index scan on the post 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 a hundred thousand and our result is 33 milliseconds comes down to 0.33 milliseconds a hundred times improvement we've gone from a cost of 5100 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.09 4 milliseconds from the original 33 milliseconds that's a huge improvement an original cost has come down and is now down at zero about twelve point forty six from the 5700 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 okay only 25k a memory to implement the sort where 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 we've grouped by the straight ID save work by doing it once when you insert the 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 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 in order to have an idea of how many words people are putting into their post now to go around and count the number of words in your posts to run statistics on that could actually be quite expensive so we have this index here where we create 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 and 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 in yet 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 your cash but with a hardwired expiration policy that is updated correctly now as I said earlier Postgres supports more than just be trees the 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 lookup 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 inverse indices or djinns which are really really powerful for when you don't 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 blobs XML trees and so on or even date 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't really 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 24 K 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 tables start 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 thousandfold 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 or is set and not updating it again when it hasn't changed not calculating it again so I made it just didn't just in under 30 minutes thank you that's it any questions and I want to thank these people who I know from IRC rhodium toad on IRC on freenode knows absolutely everything about post careers it seems we have time for one question sorry one question anyone please yeah well you were first you're first wait up some of the queries you edited next to you sort of thousandfold improvements that cost you were saying with updating is that conversely is out a thousand times cost or is it much smaller no no the cost of updating is much much much smaller it does mean that 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 or worse but these are algorithms that have worked out to be very very efficient for their for the needs and the operations are going to perform on them all right that's my one question I've overdone my time by a minute but if anyone wants to talk further about this you can hit me up on IRC or on Twitter or talk to me I'm here until all the slides all the sprints [Applause]

Channel: PyCon AU

Views: 44,451

Rating: 4.9632692 out of 5

Keywords: pyconau, pyconau_2018, Python, PyCon, PyConAU, CurtisMaloney

Id: clrtT_4WBAw

Length: 31min 21sec (1881 seconds)

Published: Fri Aug 24 2018