Postgres Index types and where to find them by Louise Grandjonc

Speaker 1: Hello. Uh oh yes, it works. Okay. Um so uh hi. I'm really happy to be here at DjangoCon. It's really exciting. It's my first DjangoCon. I was in DjangoCon Europe a couple years ago Um so I'm going to today talk about Postgres Index types and even if my uh title contains something referring to a very bad movie, I'm mostly going to be talking about crocodiles and not Harry Potter references. So just about me, I'm a software engineer at CITES data that got acquired by Microsoft a few months ago. So I'm now a Microsoft software engineer. I before that I've been a Python developer for uh years and uh I also really love databases, as good as that sounds.

Speaker 1: Um I kind of tend to be more specialized in Postgres. I did co-found Postgres Women about a year ago. Uh we you know realized that there were not that many women and we kind of wanted to prove that we exist. And now we're trying to work a little bit more on, you know, the different diversities because you know white women are not really diversity. If you want to follow me on Twitter, I'm Luis Meta and I have a blog. And I'm mentioning this blog Because mostly uh I did write a very uh long series of article that uh take the content of this talk Um I wrote the first version of this talk about a year and a half ago, uh, and uh what I did to prepare for that talk was read the entire source code for

Speaker 1: you know, indexes in Postgres and that was a very painful thing and it was because there was no good content on that specific thing. So I ended up writing what I needed So uh today we're gonna talk about indexes. So first I'm gonna give you kind of a reminder for those who are new to uh databases and Postgres and Django and everything. So what are they for? And then we'll go through kind of the options that you have when you create indexes. And then we'll go through four different types of indexes and how they are internally implemented in Postgres. And I kind of uh on purpose decided to not talk about two types which are SPGs

Speaker 1: and uh hash because I've never met someone who actually needs that. So So I was talking about crocodiles. So here is the example that I'm going to use for this talk. You have crocodiles. It's a table that contains, you know, email, first name, last name, number of T. very important and the last checkup and they can take appointment uh because uh they need dentist appointment and the birds uh are um you know the doctors This is like a really realistic example because in nature the croc does you know get their teeth cleaned by birds eating the food. So it's really uh everything I say is true. So

Speaker 1: what are indexes for? Uh the first uh thing I'm gonna talk about is constraints. I know that's not necessarily the first thing you think about when you think indexes. But constraints are very important. So when you create a primary key or a unique constraint or an exclude constraint, it will be transformed in the database into an index So that you can see like if you connect to your PSQL and you look at your table, you will see indexes appearing that are note as primary key or unique constraints. here. Here I have a weird exclude that prevents a crocodile to take two skill two appointments at the same time. We also use them for optimizing queries. That's the basically often the main reason we create index

Speaker 1: So why are they helping? The idea is that in an index you're going to have the value of the row, of the column that you're indexing, and a pointer. And instead of reading the entire table, it's going to go to the index and search for the value that you're looking for. If that's not clear, kind of think about it as an encyclopedia. If you want to read about crocodiles, you're not going to read the entire Encopedia from A to Z. You're just going to go to the index, look for crocodiles, and go back to the pages. So creating indexes. To create an index, here I have this query. I want the core class that have 10 teeth, and I want to optimize that query. It takes about 30 milliseconds to execute.

Speaker 1: So what I do in Django, it's really easy. In my model, I just add in the field db index equal true. And it's going to create the index in the database. You can also use RAW SQL. I do that a lot, so not no judgment here. You can do create index and then give an index name, this is optional, on the table and the column that you're doing. And so here it really helps. I mean six milliseconds instead of 31, it's pretty good. You can also create unique indexes. For that, again, in the field, I can here I have emails and I want my emails to be unique. unique which kind of makes sense. So you can just have a unique equal true here. In RaiSQL it transforms into

Speaker 1: create unique index on again you could give a name here So what will happen is when you try to insert a row with you know twice the value louis at croco. com, that's not my real email address, uh it will fail with uh key already exists. And no fun stuff, because that was kind of you know basic. So you can also create partial index. Which is really cool. Here in my database I have appointments and 95 % of them have been already done. Like they've, you know, a bird took care of it. So I end up with that field done equal true for most of my rows. And let's say most of my queries are going to be on done equal false

Speaker 1: and I want the emergency level bigger than eight. So basically I would just want what is what appointments are not done and an emergency I could create a simple index like this, just on emergency level, but what I can also do is create a index with a condition. Here in it's available from Django 2. 2, so if you don't use it, you'll have to do some RASQL things. So here I add the condition uh don't equal false in my index And so it's going to generate the following uh thing. Thing is not the right term, but um so create index with a wear close. So why is it great? It's great for so first the size of my index here is much smaller.

Speaker 1: I had 13 megabytes and now it's like 350 megabytes fifty kilobytes. So really it's smaller. And also now the time of my query is actually ten times uh faster than with a normal index So that really is a good trick, especially like if you have some uh soft deletes. Let's say you have a forum, you delete the people can delete their messages, but you don't, you know remove them from a database, you mark them as deleted. This can be the kind of use case where a partial index is is pretty good. You can also of course do partial unique indexes. Again, like my email, let's say I have history and I can't actually have a unique constraint on the entire table. So I can say for example, oh okay, now I had a unique constraints on email with a condition that is

Speaker 1: it's been created after uh 2019, September 1st. That is also available Django 2. 2. And it transforms into Create Unique Index again with just the wear clause here. Again, it will create a very s an index that will be much, much smaller. So here it's not just saving disk space. That's a very good thing in general. Uh it's also that you have we're going to have much faster indexes. Uh sorry, inserts. Because when you insert and uh there's a unique constraint uh Postgres will go through the the the index and check that you're not breaking the constraint. So having a smaller index will actually help you a lot

Speaker 1: in terms of performance. And again if you have soft delete like your users they can uh delete their account but they can rejoin but with a new account uh that's a good thing to do to have like a unique index on email where delete did equal false or something But with GDPR you should just delete the data. So you also have uh multicolumn indexes. So here I have appointment, I'm filtering the appointment for a specific bird And uh we want to know kind of like just the appointment that the the the bird did that are uh an emergency. And I kind of want to optimize that.

Speaker 1: So I hear I create an index and in fields there are two columns. So in RASQL you do a create index and uh on table. Instead of having just one field, you have two, three, four, five. Just don't go too crazy about that, but uh you have more than one field. There are two things that you have to know about multi-column indexes. Uh the first thing is that you can actually reuse your index. The reason is light. So I decided to do this little thing with colors because it was I I I I wanted to be able to explain that in simple terms So if you have your index, and so it's indexing the values, and here basically I have the first column is the proverb bird ID, and the second one is the emergency level.

Speaker 1: In the index, we'll order by plover ID for the first column, and then for each plover bird, it will be ordered by emergency level. So what you can see is that here the first column is ordered. The second is ordered by Ploverbird by emergency level. So here it's goes 6, 10, 10 and then 1, 6, 7, 10. So it's actually not ordered overall. Only the first column is. So you can reuse that index if you're doing a you know just a simple filter proverbird equals value. So that would reuse the index. It's important to note that because you might if you need a multicolumn index, then you might also want to clean the useless indexes that could be just

Speaker 1: reused. by this one. So that's the first thing. The second thing that you have to think about is that you should put your most filtering column first. That means that uh tr at least try. It's not always possible. This is like very theoretical. Um here I have uh you know 75,000 Appointments that are emergency level bigger or equal than nine. And I have five appointments that are from this bird. Here when I do the index with ploverbird and then appointments, it will look on the it will you know get the five and out of the five filter on appointment level uh emergence

Speaker 1: emergency level sorry. Uh if you did the opposite it would actually be filtering out of seventy five thousand So you can actually I've had that problem a lot at outside us where uh people are like, Oh, I created that multicolumn index and it actually doesn't really help. I'm like, let's, you know, try to see actually what order you used because that does change. And so now a little bit of fun uh with uh Postgres and uh index types. The first index I'm going to be talking about is B trees. It's the default index. So everything that you've seen before, just B trees. Nothing crazy about that. So when you do create index, it's just going to create a B tree.

Speaker 1: So what is a B tree? It's a balanced tree. That's the first thing. The difference between a balanced tree and a binary tree is that all the so first all the leaves are at uh equal distance from the root. This is the root. These are the leaves. And a parent node can have multiple children, it's not only two. So that means that basically the depth of the tree will be smaller, which is good when you're going to search into the tree to kind of limit the amount of you know changing the reading head between pages. So right now I'm talking about pages And because I don't want to scare any th anyone, I'm just gonna say a page is basically where everything is stored eh

Speaker 1: almost in Postgres. It's a eight kilobyte data structure. It's not nothing crazy. It's just that the name is page. So in an index, what is a page and what does it contain? It contains a blocked number that is going to be used for the point. It's going to define a high key. And what is a high key? It's the high, basically in that page, any item will have a value lower or equal to the high key. And then it has items and we'll go through items later. So I was talking about high key. So here, for example, I maybe in the back you don't see uh as well. I'm sorry, I hope you do.

Speaker 1: but not sure. Here I have this page as uh has the high key 16, so it means that I will only find crocodiles with 16 or less teeth In this one the high key is 31, so it will be 31 or less. And here I don't have a high key because it's the last page of the level. So you kinda don't know how many teeth a crocodile will have. It could be like a hundred, yay, or less probably. Um and now there are also items. And the items basically contains the value and a pointer. That was what I was describing before. The value will be basically just the value of the of what you're indexing, of the column, and the pointer will be in the leaves, the pointer to the row.

Speaker 1: in the parents a pointer to the the the children. So to sum up, you have a B tree is a balanced tree The values that are indexed are the values of the rows. And I know this sounds very trivial and very obvious, but it's not the case for every index. That's why I'm saying it The data is stored in pages and the pages have a high key and items that are pointing either to a child page or to the row. And so why are B trees so good then? They're very good for anything where you compare data. Like is it equal, bigger, lower, bigger or equal and lower than or equal. Why? It's basically again like you are indexing the value in a structure

Speaker 1: with high key. The high key really uh matters when it comes to uh the binary search, and that's what Postgres is using. to search into the tree, it's going to do a binary search. So B trees are good for almost everything that you want to do. Like really commonly you won't need Anything else than a B tree. But when you do, there are other types. And the second one I will talk about is gin. Um so gin is used to index arrays and JSON B uh Ts vector. Ts vector for those of you who are not necessarily you know, pff, don't really use that. It's uh full text search in Postgres.

Speaker 1: Uh it will basically just transform a text into a series of vectors uh of Lex M, which is basically just the root of the word. It's efficient for this operators, which probably don't mean much. This is basically anything that would be like, oh, does this array contain this value? Does this array contain this array? Does this uh element you know uh overlap to that? Um for full text search, for example, it's really good because you're going to be wanted really often to have like, oh, does is that word in that text or something So here I added a new column. It's the heel teeth, and it's the what the crocodiles uh got hurt and the blubber bird dentist uh had to repair.

Speaker 1: So here I have I randomly generated this. This is not my real uh I think that this would be a lot of teeth uh damaged, but yeah. So I create a GIN index, and so how do I do that? Uh Postgres is very good with Django, and Django is amazing. And so you have in uh Django contrib Postgres indexes, Ginindex, and basically it Django supports all the different types of indexes. That Postgres provides out of the box. So it's really easy for you to use that. So you can just simply create a GIN index with the fields. If you're using RASQL , because you love SQL and

Speaker 1: It's fun, I guess. Uh I mean I do. It's I yeah. Um you can do create index using GIN. That's how it works. So how is it different from a B tree? Earlier I was telling you, oh, uh we in the B tree we just just you know index the value as it is. If we were to use a B tree on an array, it would just index the entire array. What GIN does is that it's going to take the array and split it. And each value will be an entry in the So here what you can see is uh this is again my array of uh um heel teeth, and it was actually split.

Speaker 1: And so this this branch of the tree will contain all the crocodiles that have the teeth one uh health. and this one will have the four or six and whatever. It's and the difference is that so in a B tree, each element of your table has an item in the leaves Here instead, what there's in the leaf is a list of all the crocodiles that have the teeth one health When you know the sometimes the the the um the list just becomes so big that it just doesn't even fit in a page anymore. And what happens in that moment is that what we do is we have a posting tree. which just contains also pointers to uh crocodiles or rows

Speaker 1: um that are just stored in a in a tree instead of uh in the page. So uh here I have the time that I if I was you I this I I showed that example because I actually created an index, a B tree index. to just to show that it would actually not even be used by PostgreSQL when uh executing the query. So here it used to take a hundred and sixty milliseconds even with a between index. And now it takes 41 milliseconds. And you can see here in the bitmap in there's a bitmap index scan and then on my index. For those who of you who don't really know what that comes from, it's an explained plan that you can

Speaker 1: actually execute on your query within PostgreSQL just to kind of see whatever is done when uh executed. So to sum it up, so Jin is also a balanced tree, so that's pretty close to a B tree. And each value in the tree is unique. We uh instead of just indexing the row, we split the value. And each value is an entry, a unique entry in the tree. So it's very efficient for full-text search uh and uh you know overlapping data etc And I'm gonna speak about GIST. So GIST is uh an index that is a little bit weird because it is a framework.

Speaker 1: So you could write your own gist index for your own data if you have time and patience. So it provides, like if you look into it, and uh the there are articles on my blog about this But if you look into it, there's like a list of functions that you could implement for any data type that you would have and that would do a gin index, a gist index, sorry. So what is the difference between a gist index and a B tree or a GIN? The first thing is that the data is not ordered in it, which seems weird, but does make sense. Weirdly. Here I uh created a weird uh data type for an integer

Speaker 1: integered range. Just to show you that in the here, you can see that here it's the three to five the range, and then here it's zero to two, and here it's four to eight, so it overlaps and it's not even ordered. Why is it this way? If you're using gist index, it's most likely because you're using uh you know g PUSGIS and if you and using geometry and everything. What happens is in a geometry, you would, if you think about it a little bit, it makes sense that it's almost impossible to build a tree on a geometry that just never overlaps. You know, geometry that gives you to take two big circles, it's really you you will have some overlapping.

Speaker 1: So when you build a gist index, there will be overlapping, and that's something that has to be taken into account Um so the same value can be inserted in several places, which is why uh you have if you build your own gist index, you'll have to be very careful because you can end up with bad performance. But you can trust the people who build gists for PostGIS. When you create a GIST index, again, very simple. It's in Contrib Postgres indexes. You can just use GIST index, or again, you can use uh create index using gist. So it's why use a gist index for any overlapping the you know thing that you would want to do with whether it's geometry

Speaker 1: array ranges. I d the main test I did with uh just for this talk was on a TS range and that's a pretty good example I think. It's well again especially used for postGIS and for nearest neighbor operations. It's also used very commonly for full text search. And there are some very uh if if you want to use you know full text search and you want to use GIN or GIST, there are several differences between them. I don't think I have time to talk about them right now, so I'm going to pass that. If you have questions about it, I'm happy to answer them in the hallway. I'll be probably hanging out at the booth my the not Postgres, sorry.

Speaker 1: Microsoft, where do I work? Uh uh booth, sorry. Damn it, it's filmed. And the last one I will be speaking about, uh brain indexes are amazing. I love that. Um so they are very different because they're not even a tree. It's the the only index that is not a tree. So it's uh something that we call block range index. And what it contains, and be careful because it's going to be very confusing until I show you what it is. Is that it's going to have a group of pages that are physically adjacent and the range of value that this adjacent block range contains.

Speaker 1: So it makes Brain indexes very, very small and good when you have to fast scan like really really big tables. So what I mean with all of that is that here I have a brand index on a create it at. So from for the pages from zero to hundred and twenty-eight, I have the range two thousand and eight to two thousand and nine July something. Then two thousand 128 to 256, it's 2009 to 2010 something. So here you can see uh how a BRIN index is. But be careful because it's not always good. In this case, like if I'm just try looking for 2013, it's prime I I know it will be here, but

Speaker 1: if you want to use it for a birthday column, that will be terrible because all the ranges will be really big. So when you use a brain index, you have to be careful of about having values that are have a correlation with the physical location of your data. So basically any data that actually increments Would be a good thing. You also have to be careful about deletes, uh, because when you delete data uh from, you know, I don't know, two years ago, whatever, and then you vacuum, the space is then reused. And then your ranges are really bad again. So it's uh something to think about when you have when you want to add a brain indexes correlation and uh not deletes, which again

Speaker 1: GDPR, So when you create a bryn index, again, yik, super easy, Postgres indexes, brin index, you add it to your meta and indexes, and that's it. So conclusion, um a B tree is great for any comparison operators. Gin are good when it comes to arrays and and when it comes to full tech search, when you have to kind of have, oh, this uh array contains whatever. Just are good for overlapping, especially Especially for geometry that can also be used for full text search and Brain are really good when it comes to fast scanning large amounts of data. Thank you for attention. Yeah, that's it.

Speaker 2: Alright. So we have time for one, maybe two questions at the order.

Speaker 3: I was curious about gin use on uh you said JSON B. It would be used on JSON B. Uh specifically I was curious about like depth. How that's handled. Um can you only index on like an array or keys or

Speaker 1: uh on uh from what I remember it's on the keys. But you know what, I'm not sure. Because I I would guess the keys. I've only mostly used gen indexes for full text search actually. So uh if you're curious about that, there are like some pretty good extensions to Postgres where you can actually that's what I was showing for Bryn, you can actually go and analyze what the page is containing. So when it's things like that where you don't know exactly what is indexed, you can use these extensions to go and see that.

Speaker 3: Hi, can you elaborate a little bit on how you handled uh regulatory uh things like GDPR or uh CCPA. Like did you hard delete the rows or did you scrub them? And if you did scrub them, like how did you handle certain constraint issues?

Speaker 1: Oh, um okay, so it's sorry, the c is the question on constraints or on BRIN and handling a BRIN index? I'm not sure.

Speaker 3: Uh specifically with like how you address GPR

Speaker 4: or TCPA.

Speaker 1: Okay, so uh F in my company that I worked for before, uh what we had was a very complex I think that anyone has a complex system where uh so our constraints had uh conditions uh for deleted accounts and then after uh six months I think of an account marker's deleted we would delete all the data because legally we have to I think.

Speaker 2: Okay, that's it. Thank you.