Flexible Indexing with Postgres
Momjian, Bruce
When considering database indexing, many people are confused by the many Postgres indexing structures available, and the many data-type-specific index lookup methods. For example, brin allows for efficient indexing of many columns. gin indexing specializes in the rapid lookup of keys with many duplicates — an area where traditional btree indexes perform poorly. This is particularly useful for json and full text searching. GiST allows for efficient indexing of two-dimensional values and range types. This talk explores the various indexing features of Postgres and when to use them. This is ideal when presented after my Non-Relational Postgres presentation.
 Okay. There's probably enough energy in the room. We can just coast through this one. For those of you in the previous session. So anyway, I'm sure we'll get some feedback from that big discussion. What I am here to talk to you about today is not about what the previous session is about, but something completely different. As you know, Postgres has a very flexible object extension system and a very flexible data model, a way of storing a lot of very non-traditional data types like JSON and GIS and full-text search and stuff like that. And one of the core things behind all of that sort of creative non-traditional relational object storage stuff is indexing. And this talk is about exactly that topic. I think that indexing is sort of one of our unsung heroes of Postgres. You don't see it a lot. People don't talk about it very much. But without really, really powerful indexing, a lot of the non-traditional storage types that we support like JSON-B and full-text search and GIS would really not be possible. So this talk is about that topic. It's about indexing. I think you'll find it very interesting. I learned a little bit even in working on it. And frankly, the way that the Postgres documentation presents indexing is not ideal. It's a little hard to get your handle on. You end up sort of following what everyone else did. Oh, I need a specific type of index for that data type. Or I need a specific type of index for that data type. But what this talk tries to do is to actually explain why. Why do you need special indexing types? Why do you use one indexing type over the other? And also to give you one or two indexing types you may not have even heard before that are available in Postgres that are very powerful. So I think you're going to enjoy it. I have to give attribution here. A lot of the indexing that we're talking about here comes from the Russians, as we call them, Theodore, Alexander, and Oleg. Oleg is not here. Alexander and Theodore certainly are. If you look around, I don't think they're here, unfortunately, but are they? No? I don't see them. Anyway, Theodore normally has a vest. And I think Alexander was wearing red today, but he's kind of tall, sort of stately looking in a way. But young, so sort of a combination there. Oleg is not here. Jonathan Katz also is around. He's in New York or so. If you hear the voice, you'll know right away who that is. These presentations are actually on my website right here. So if you wish to download these slides right now, you can, or sometime in the future, there's probably 20 or so other slides, other presentations up there that you might find useful. So we have an ambitious agenda because indexing is a complex topic. First, we're going to talk about traditional indexing. This is going to be the easy part. This is sort of what you remember from all the other relational systems that you've worked on. But then we're going to talk about some of the ways that Postgres has taken traditional indexing and extended it, I think, in a very powerful way. This will probably be the easier of the parts because what we're doing is we're taking the traditional indexing type that you've seen in all the other relational systems and just adding new capabilities to it. And I'll show you some examples of that in items three and four and indeed in item five. Then when we get into item, I'm sorry, item four, and we get into item five, we start to talk about where the wheels come off, non-B tree indexing types. We'll talk about what those types are, give them names, explain a little bit about their structure. Then we're going to explain how they support indexing, particularly, and specific data types, and then finally give you a summary. There is another presentation that I'm not going to be giving at this conference called non-relational Postgres. So if you're curious about how Postgres supports a lot of the non-relational types, range types, I see some range types guys here, GIS and full text search and geographical stuff, that non-relational Postgres is sort of a good one to watch before this. If you're not familiar with a lot of the non-relational things that Postgres can do, so I'm not going to cover that too much. If you need a primer on non-relational Postgres from my website, great place to look. So any questions? Because I like to take questions as we go. Yes? Nope? Nope? Okay. So first, traditional indexing. Traditional indexing for relational systems is B tree. Great, very flexible, has high concurrency, fairly compact storage, although I know that somebody, another one of our Russian friends at Estasia is working on making B tree even better. So if you catch her, feel free to talk to her about that. But there are other, B tree is sort of the catch-all. And if you only have B tree, it is the only option for your relational system. So there's a lot of relational systems that really just kind of have B tree. Maybe they have hash, but they don't get into some of the craziness that Postgres does. And therefore they can't really support a lot of the indexing that we do. Because Postgres originally was designed as an extensible system, it's been very easy over the years to say, oh, I'm doing full-text search, I need a special indexing type for that. Oh, I'm doing GIS or 2D points, 2D geometry, I need a special. So the idea of being able to extend Postgres as new data types became necessary for storage is one of the sort of geniuses of Michael Stonebreaker and how that original research project was designed. And I'll try and cover that to a tiny extent. But again, B tree, great. Great for high concurrency. Great. The index is basically key and then some kind of row pointer and key and row pointer all the way down. Great for sort of single lookups, even range looksups. Order by, of course, makes a lot of sense for B tree. If you're familiar with merge joins, merge joins make use of these B tree operators because they present a single linear ordering of your results. I'll have you curious about merge joins. I do have a explaining the Postgres optimizer talk on my website that covers that. And also, Neslub with index scans, again, this is sort of the bread and butter of most relational systems. But what I'm going to be talking about today is the idea that as good as they are, they can be extended in some creative ways, even B tree, and then there are some even more cool types that I think you'll find really interesting. Okay. But I want more. Maybe I want an index, not a column, but an expression or a function. Some relational systems support that, some don't. Maybe I want roll control. Maybe I want small, lightweight indexes because B tree can be, you know, a significant portion of the size of the table. You might think, well, that's always going to be that way, but that's not actually always that way. You might want to index nonlinear data. Very hard to linearly represent a 2D space, right? I mean, my definition, 2D spaces are 2D. You might want to do something like closest match searches. This is kind of difficult to do in B tree. You may want to index a lot of duplicates. Now, B tree will index a lot of duplicates, not very efficiently. And you might want to do multi-valued fields, particularly something like a JSON, JSON B type. Again, you can see where B tree doesn't really play too well in this area. So let's just talk about the straightforward extending expression indexes. So extending B tree indexes, I'm sorry, in this case, I'm going to show you an example of, actually, let me ask you any questions. Okay. So let's talk about indexing an expression or a function call. Again, some databases support this. Some databases don't. If you have a query like, I want to look up somebody's name, but I don't want to specify the name in the case specifically. I want to specify just the name in all lower case, but I just want anything that has any match in case to match this record. You can do this query in any relational system, and it will return the right result. Okay. But what you, what the problem is that if you try and create an index on the column, it's not going to use that here. So one of the things I'm, one of the things that I continually talk about when I'm talking about indexing is that you can do a lot of non-relational storage with a lot of the other database systems. But if you can't index it, it's a toy, right? This is the classic case. You do a proof of concept. It runs great. You go to a production. It doesn't, the system just falls over because it needs that indexing to really make it function and perform at the scale that your enterprise needs. So one of the great things about Post Grass is that you can create something called an expression index, and that's either by placing a function call inside the created index command or literally a plus sign, a factorial, you know, a concatenation. You can do almost anything, any type of expression in there, and Post Grass will actually use it. So here's an example. I've created a thousand customers, and I basically created an index on their name. Now, this is the traditional index, just create name, and if I go and I say, give me customer 9999, the system automatically knows, oh, okay, let's just, you know, do an index scan, pull them up. That's a standard B3 operation, no problem. Okay? But if you try and do something like function call on that column, Post Grass, by default, if you just index the column, it's going to fall over. Okay? It's going to do a sequential scan. This is what I'm talking about. It's not going to scale for that kind of use case. But if you use an expression index and you now say, create an index on the lower of the function call of that, then when I actually do a lookup, it actually knows to do an index scan and to pull the records back. Okay? So a lot of cases, you may have lookups in your ware clauses that are not traditional lookups. They may rely on an expression. They may rely on concatenation. They may rely on a function call. And by creating an expression index, you can now get performant results from this kind of query. Okay? Again, user-mined functions, concatenation, math expressions. The functions that you use in an index have got to be immutable. There is a special immutable flag that has to be present on that particular function because you can't have the value that that function returns changing over time. Right? It's got to be a stable. Every time I put a two in, I get a four out. If you have something that relates to current timestamp or something like that, you start to get into trouble because that, the value that comes out at the time the row was added and the value that you may compute later, if you've got current timestamp in there, it would be potentially different. Okay? So just be aware that's the one that usually catches people up is that current timestamp shifting and it's not immutable function and therefore you're going to have trouble. So just be aware of that sort of restriction. And also you might need to do casting depending on how it works. Okay? Any questions about expression indexes? Okay. I know, you know, I will tell you I always start really kind of slow. By the time we get to the end, you'll be like, whoa, okay. But I always kind of ramp up as we're going. So let's go to the next one. This is partial indexes. This is a little more on the edge. You've always assumed when you create an index that every single row is indexed. But there is a value to being able to say, I only want to index some rows. You might think, I'm never going to want that. Well, don't make that decision right away. Okay? Sometimes, why index every row if you're only going to look up some of them? Like, why have the storage space? Okay? It's smaller if you just index as the one you want. The index is less deep. Okay? And more shallow, basically. There's not the insert update overhead of updating index for rows that you're never going to use. But you can still get to the rows. It's just that they aren't indexed. Okay? So here's an example of another table I'm going to add. I'm going to add a state column to my existing customer table I did over here. I'm going to update and add. I'm going to make all of the 900 and plus, so we're all like from 900 to 1,000, those people are all going to be in Arizona. Okay? So I'm just going to put Arizona for one tenth of my people. And now I'm going to create an expression index. I'm going to say, index all of the people in Arizona. All right? Maybe I have some tax law in Arizona. Maybe I live in Arizona. And I'm always looking at people who are local to me. Maybe I have it out for Arizona. I don't know. Whatever. Okay? Now if I go and I say, give me everyone in Pennsylvania, system runs fine. It's like, I know you didn't index Pennsylvania, but I can still give you the rows. I'm just going to automatically sequential scan that table. Okay? But I've asked for everyone in Arizona, system automatically does an index scan and says, oh, I can get you those Arizona people much faster than doing a sequential scan. I have an index that will just pull those off right away. Okay? And that's a really, really powerful optimization you can do. Again, reduces the overhead of maintaining that index, the storage size of the index, and obviously the depth of the index. Classic case from my experience, we used to have an accounting system. Oh, you have a question? Yes, sir. Please. Let's say the column is a boolean. And you say, index where, you know, is true. Totally. So, but I always assumed that all the ones that were in other case would all be in the same index slot as it were. Yeah. And so, would occupy one slot of the index anyway and that would be it. So, that's, you're, you've walked right into what I was about to say, which is great. Okay? We used to have an accounting system that I used to do consulting and it had a, it had a, you know, what was it? Invoice is zero flag, right? So, you'd have, I don't remember what it was called, but you'd have a flag that would indicate whether this index was closed, like whether it had activity or it was non-zero or it was zero. It was zero. It was really there just for historical reasons, right? And you were always running reports asking for the non-zero invoices, right? Because that was all of your work. But in the database that I was using in the 90s, there was no way to do that. So, you effectively had to index all of your rows. 99% in my legal application experience were zero, right? But I had to index all of them so I could pull out the non-zeros really quickly. And this is a classic case. If you create an index on a boolean on the whole table, it's going to index every row. It's going to have, and I'm going to go back up here because I hate to do this, but remember I said that the index is effectively key value, key value, key pointer, key pointer. So, you're going to have 99% of your index is false, pointer to false. False, pointer to false, right? The index does not make a distinction even though it knows 99% of those are indexed false. And frankly, probably the optimizer would never choose a 99%. It's only filtering out 1% of the rows, right? And it's never going to use an index for that. Frankly, indexes have to filter out almost 95% of the rows before they're going to be used in a lot of cases, okay? Not in this case, but the index system is not going to make that decision. It's not going to know what your future data layout is going to be. It's not going to know a lot of things. So, it's going to index all of them, right? And that's the classic case actually for me as boolean where you're kind of like, well, I don't really want to index all these zero invoices. I just really want the other ones. So, that's a great example. But the bottom line is, yeah, it's going to have a lot of falses in there. And that index is going to be huge. It's still going to get to the true ones really quickly because the index, the optimizer knows how selective a true is or a false, right? And it's going to use the index depending on that. But in terms of storage space, they're all there. That's a great, perfect question. Yes, sir? Yeah. I would, so I'll repeat the question. So, the question is, would you use four different indexes on four different unique state values? The bottom line is no. You'd create a single index on that. There's really the optimizer smart enough to know which ones are selective and which ones aren't, creating individual ones. I don't think gains anything. Because of the way B tree works, all of your states are going to be right next to each other and the index, the optimizer knows that. So, it's going to do that fine. The case where you would really want to use that is where you've got some really dominant state that you don't want to index, right? That's when it starts to make sense. And technically, so if 95% of your customers were in your home state or province, okay, you might want to index everyone who isn't in the province you're in. And technically, you can actually, I'm not going to cover this, but you can actually say, state is Arizona and state is not Pennsylvania and it'll actually use the is not Pennsylvania. You can create an index of is not in Pennsylvania and it'll actually use is not in Pennsylvania to find the Arizona people, okay? Because what I'm doing is by saying not in Pennsylvania, I'm excluding 95% of my rows, right? I'm creating a very small index on 5% of my customers. But now my where clause, I have to say, which doesn't seem to be logical, customer in equal state equals Pennsylvania and state not equal to Arizona, which sounds completely ridiculous because I've already said Pennsylvania, why would I say not Arizona? But I'm saying, or I would say in Arizona not in Pennsylvania, why would I say not in Pennsylvania only so I matched an index? Literally, the system is going to try and match the where clause with whatever literal you put in the preposition of the partial index. It's kind of tricky. Yeah. Yes. Totally. I would love to, if you can tell me, I can't remember some of the smarts is enough. Like when I say not Pennsylvania and equal Arizona, I thought it would figure that out. I can't remember if it figures it out. So maybe I need to go back and try some more testing. I could probably just take this example and run it for somebody here could do it, whatever. But I don't remember how smart it is or how literally you have to match this. Years ago, you had to literally match it. I think we've gotten smarter here, but I don't know how smart. So great question. I don't have an answer to it. Next question. Okay. So again, if I now do my check equals Arizona, it does a sequential scan. If I now, so I'm sorry, when I'm doing it here, I'm saying I'm creating an extra Arizona. If I look for everybody, I get a sequential scan because it can't use the index. But if I ask for Arizona, even if I ask for the customer name and Arizona, it still knows to use the index because the index is definitely restrictive. So I'm still looking for these customers, but only in that Arizona index. And of course, if I just ask for everyone in Arizona that works, I can even do, I can even create, let's see here. But anyway, so you kind of get the idea of how that will go. We have another way of doing index is called a bitmap index. It's used. It's called a bitmap index scan. It's not technically an index. It's automatically happens when you run queries. You've seen bitmap index scan right here, for example. It's particularly used when we expect an index to generate multiple matches on the same page. So if we expect the index to hit a bunch of matches, we'll use a bitmap index scan. It creates a bitmap in memory. It basically does either raw or block level granularity. And then we can visit the rows once just using our bitmap. And what's really great is you can take different bitmap scans, join them together using multiple indexes and kind of get this mega index, which is a combination of bunch of different indexes. Okay, again, this happens automatically. It's not something you're going to do, but be aware when you see a bitmap index scan, that is what it is doing. Okay. Now, that is the easy part. Okay, now we'll go to the hard part. The hard part is all the non-B tree indexing types, all of the non-traditional indexing types that Postgres supports. Why are they there? What do they do? And why do they really make Postgres's type system shine? Okay. This is like a big, I know it's like, whoa. The first one is kind of an interesting index type. We've had it for a couple of years. It's called BRIN. It stands for Block Range Indexing. It basically creates tiny indexes for large tables. So if you've ever wanted to create an index on every single column in a table, this is your baby. All right. The index are very small. Index is typically something like.003% of the size of the table. Right? I mean, really small. So it basically stores minimum and maximum values over a range of blocks, in this case, one megabyte. So for each one megabyte piece, it's just going to store a minimum max. And then it's going to skip or scan each one meg chunk. Now you can change the sizes, but default, you've got like a one meg range there. Skip to the large sections of the table, thinking of a 300 gigabyte table. This BRIN index is just great. You're breaking the table up into what, you know, 300,000 individual pieces, and then you're just able to kind of skip or scan each one and beg a bite chunk. It's really great for naturally ordered tables, things like indexing, insert-only tables, chronologically ordered. If you've loaded it to data in a sequential order, that's really good. Indexes are very inexpensive to update, you know, very small costs. They are slower than B-Tree. But again, if you try and B-Tree index every column in your table, your indexes are going to be far larger than your table itself. And a lot of times you don't know what you need to index. This is a great sort of fallback for that case. Okay? Second index type, GIN. We've had this for years. Alexander Klokoff has worked very hard on this in terms of improving it. It's really great for indexing values that have many keys, like text documents, JSON, multidimensional arrays. Okay? Also great if you have a lot of duplicates. Remember I told this gentleman about the, like, the falls and every, like, you know, 99% is false. Well, in this case, you're going to have one falls and a whole bunch of rows, which is a lot more compact than the traditional B-Tree where every single row has to have a key in the B-Tree index. Okay? Yeah? Absolutely. In fact, if you look at the Postgres to-do list, one of the things that is listed as not wanted is Bitmap Index. And the reason the to-do list says we don't want it is, effectively, we are unclear where a Bitmap Index would win over this indexing type. Because the problem with Bitmap Index, it's, Bitmap Index is great if you've got a table that never changes. But growing a Bitmap is fairly difficult to do. So what Jim is sort of allowing you to do is to have the benefits of the Bitmap Index without the overhead and the problems of growing and shrinking that index as the table changes. So we don't know if we're ever going to have a Bitmap Index because we don't know how we'd ever be, effectively, your great point this exact index type. So if you're familiar with Bitmap Indexes from other, not Bitmap Index Scans, which is a different case, Bitmap Indexes, this is a great replacement for that in some ways better than a Bitmap Index. So that's a really good point. Other questions? Yes? Could you put a range of the medians that's coming in at the end? Well, I'll just give you some just off the wall. So let's just think of a data type. Let's think of full text search. So I'm going to have tons of me, the word me, all over that index. So do I want every me that's in the index to have a single, every me that's in the table is going to, in the text fields, even though I have multiple me's, I'm going to have an entry in the index that says me and then the value. What Jim is going to do is he's going to give me one me for no matter how many me's across any column, any field, any row in that table, and this is going to have all the matches. So it basically takes the B tree we're going to have due because you just roll them up. So frankly, I don't even know how you do full text search with B tree because you'd have to have multiple matching rows for multiple words. It wouldn't even work, right? Because it's like saying, you know, typical B tree, when you create a B tree, it's like, okay, when I index that column, you know, that column has an indexed value of five and that one has a, in this case, that one column because it's a full text search row or a JSON row, it may have a five and a seven and a 12 and, you know, a bunch of row, values in that single field. So there's no even way to think of how we do this in B tree. But certainly any case where you're looking at a significant percentage of the table, even like three or five percent of the table has the same value, you'd probably be doing this. In fact, there is a contrib module called B tree gin, right? And it effectively takes the B tree sort of operators and makes a gin index out of it. So if you want to, right? So that's actually, I can't tell you when that's going to win, but I know I see a lot of activity on it. Like we get bug fixes once in a while. It's not there. People are using it. And again, when you have a lot of duplicates in B tree, Anastasia, I want to say Lumikova, I'm not saying her last name, right? She's kind of tall and like, I know what you were yesterday. I didn't see her today. So if you see her around, you can ask her because she's done a lot of research on duplicates on B tree. So when I was in Russia a couple of years ago, she did a talk on, she has a whole patch that's designed to take B tree and make it operate more efficiently. But the problem is that's gone now compete against B tree gin, which is this. So now you've got B tree, which is not good for duplicates. You've got gin, which is great for duplicates. You've got B tree gin, which is in the middle. And then she's trying to say whether we could take B tree and kind of move it closer to B tree gin, you know what I'm saying? So the kind of, the kind of, you'd think that there's only a couple of ways to index something, but there's a whole spectrum of efficiencies that you can do when you've got duplicates and when you've got multi-valued matches in a single field or a single field. Yeah. Great question. Yes. Okay. So optimize for multiple batches. Key is stored only once. The index is key and then many row pointers. Remember B tree was key, row pointer, key, row pointer. This is key, many row pointers. If it was visually, I'll show you a visual example later. Indexes are batched. Therefore, one of the problems we always have with bitmap indexes is updates. Very expensive because it just, so this, the gin code has like a, like a queue. So when you do a change on the index, it kind of goes into the queue. And then when anyone looks up the index, they check the queue first and then they go to the main index. So there's always this, and then you batch those updates because when we originally implemented gin, I think this was Alexander, a little before Alexander, maybe it was Theodore or Futter, the updates were very slow. So over time, we were able to kind of batch them and that really improved the insert update performance of gin indexes now where they perform really well. And in fact, even as recently as 9.4, Alexander added compression, very powerful compression to this gin row pointer list. So you can imagine for the word me or the word thank you, a thank or son, there may be, you know, thousands of row pointers. And he in 9.4 is able to have a compression algorithm across there and optimize it for multi-key filtering. I'm not going to go into it. I did understand it at one point. But again, this is really, really high-powered stuff, which really takes postgres, I think, for these multivalued and non-relational storages into a really amazing direction. A related index is called GIST. We've had this a little longer than gin. It's called generalize search tree. It's a lot less specific, hence the name generalize. It's really designed for things where we can't use B tree, we can't use gin, we can't use brin. So things like geometric types, range types, h store, trigrams, these are nearest neighbor. So again, it's kind of a catch-all indexing method for a whole bunch of things. And I'll show you some specific examples later, what that does. SPGIST, I think this is Futter and Alexander worked on this. This is something called space partitioned generalized search tree. So it allows the key to be split up and the parts are indexed hierarchically into partitions. So I'm going to show you a graph of this later. But effectively the idea is that you take a URL or an email address and you break it up into parts and then everyone who has the same common first part goes in the same place in the index. You don't see this very much. Usually when you're indexing something, you're indexing a discrete thing. What space partitioned GIST is, is it's assuming it can take that thing you're indexing and look at prefixes and slice it up into prefix parts and then put everybody, for example, who's at a Yahoo address in the same place and whatever. This is something I think is pretty cool. It's not traditionally used very much, but there are special use cases, particularly for very long indexed values. Integers doesn't make any sense, right? Words probably doesn't make any sense. But when you start to think about a structure, think of a URL, right? It's kind of how directories work, the idea of taking a path name and breaking it up into pieces and then having this piece is kind of all together. So everyone in bin is going to be, even though you're indexing a long path, everyone who has a bin to begin with is going to go in the same part of the index, right? Really great for prefix searches, obviously. Yeah. You could. You'd have to make sure that the last name is the first part of the indexed search and then maybe concatenate it together. So I would almost take, if you've got first and last name in a separate field, you can actually create an index that concatenate like that, use an expression index and concatenate it together and then put the word at the front and then the space and then, and that would actually kind of start to do that type of thing. Yeah. Phone numbers is a classic, right? Because you've got the area, country code and then area code, right? Yeah. Yeah. Is it one slice or can you put country, use country code for one grouping and then within that area code? The cool thing is you don't do anything. You just index, you just take, create an index and it figures out how much, what's a good break point for these partition boundaries. Yeah. Yeah. And then you just assign it table spaces, basically. No, you just create an index on the column and you're done. That's it. That's it. Yeah. So if you see footer, he's the guy who worked on this. He's been around for a couple of years, but it doesn't seem to get a lot of traction. Partially because people read the docs and they're like, why would I use this, right? And they're like, well, yeah, there are some cool reasons to use it. All right. But again, it isn't, it isn't obvious. Hash indexes, we have improved those in Postgres 10. I don't have to embarrassingly sheep away and say boo, like I did, I used to have a boo slide for this. So again, hash indexes, very good for quality, doesn't have any not a quality look up, no range look ups, but again, crash safe, replicated. The B tree is so fast, I'm not sure when hashes are when there are some cases, hash indexes are typically smaller, particularly for long keys. So if you're indexing, the classic case I had was indexing something like a large object. You might say, well, why would you index a large object? If you're indexing an encrypted value, which is effectively stored as a large object in Postgres, those can be pretty long, like 64 bytes or whatever. And you create a hash index, now you're not indexing the whole thing, you're just indexing like the hash of it. And that's a great one. Jimmy, you had a point. You were great for UUIDs. UUIDs, thank you. Because it's automatically shrinking it down for you. It's still going to check to make sure for hash collisions. So you don't have to worry about it. It's still going to check the raw value. But obviously that hash is filtering very well. And it's going to check the raw value. Great. Yeah, UUID. Any kind of long text string or anything, the idea is to kind of auto-hash it, auto-shrink it down. That's really, I think, where the big win is for hash indexes. Yeah. Would it be UUIDs stored as text or as a native UUID? Either one, there's a performance that it overbeats UUIDs. Cool. Yeah. Thank you. Great point. Thank you. In other databases, you can use it for social security. Well, the problem is this is just the indexing portion. So you still have the raw social security in the table. Yeah. Sometimes if you're an insurance company, you have to have the raw social. The point is that you never do a range search on social... Absolutely true. And then... Absolutely true. Yeah. Yeah. Now, I have to ask a question because you've asked two questions. Did I tell you last year that you should have been like a radio announcer or did I talk to you about that already? I was. I knew it. That's great because as soon as you asked the question yesterday, I'm like, wow, who's that talking? This is kind of funny. Great. Good for you. Thank you. Okay. I'm not making this up. So effectively, this is a query from Postgres. These index types are literally stored in the database. I talked about the extensibility of Postgres. These are literally stored inside the database. Okay. All right. So let's get a summary. Where are we? B-treat. Ideal for indexing unique values. Nobody's going to beat that. Okay? Bryn. Ideal for indexing many columns. Small indexes. Again, these slides are online, so feel free to look them up whenever you want. Okay? They're on my website. I didn't even mention I work for Enterprise DB, but anyway, it's been 12 years. I guess I don't even say it anymore. Genie index is ideal for many duplicates, space, SP gist. Ideal for indexes whose keys have many duplicate prefixes. That's really the concept I want to get across. Space partition gist, common prefixes of long key values. Gist is just everything else. It's just the catch all when everything falls through those cracks. Okay? All right. Any questions? Yes. Yeah. Right. Right. So why don't we consider hash for primary keys? Part of the reason is because a primary key by definition is unique. We could use a hash for that, but historically, because post-grass, the hash indexes weren't crash safe. We just never were going to do that. Now that we're crash safe in 10, we potentially could do that. If somebody came to us and said, you know, I want the option to do it, and here's the benefit in speed I get if I could do it, we would definitely consider that. There's nothing. There are some internal reasons why we really like B-treat, because when we're locking a row for foreign key check, we're going to want to lock that specific value. And the problem with the hash is you can have hash collisions, and we can't identify as quickly from the index exactly which index matches my row. So if you're two people are inserting at the same time, this is more internals, we're going to lock that index so somebody else doesn't come along and insert the same key value. And if we, to do that for hash index, it would be kind of dicey because of the conflicts, potential hash conflicts within the index. That's not a user-visible thing, because we're always going to check the heat, but we might not want to do that. I don't know, but it's possible. That's a great point. So other databases do support this, so maybe we should look at this. Now that we have unembarrassing hash indexes, I'm going to use that term, it's definitely something we could look at. Yeah. Great. Yeah. In fact, Grant, who was speaking before, has a great talk about that hot problem with, I think he's done a lightning talk on it, and I think he hasn't talked about it. So if you're curious about that, what he found was that when he indexed a hash, he got so much churn in the index because he wasn't hitting the same rows on insert, he was getting all over the place that he didn't actually, it didn't actually work well. That was kind of interesting because that was a time series case. So anyway, I thought it was interesting. Okay, so let's take a look. Data type support. So again, I'm querying the system tables. Not every data type supports every indexing method. Okay, so you can't, you can probably use Btree on almost anything, okay, but you probably don't want to do that because if you Btree index something like JSON B, it's going to index like the whole thing, the whole document, right? That's probably not what you want to do. You want it to break it up into pieces and index, there's a whole bunch of operators that are possible only when you, only, they're indexable only when you create a non-Btree index on some of these types. So just because Btree supports it doesn't mean that's where you should be going, right? So you, unfortunately, you have to understand a little bit of this, particularly like the range types and stuff. You just don't want to use Btree on this unless you're looking for absolute equality of the whole field. That's really where Btree wants to be, right? No surprise. If we look at Brinn, again, this is that tiny index where we can kind of slice things up, okay, and you can see that it's effectively slicing it up very well. So the whole bunch of different data types are going to be sliced up with Brinn, okay? Gin, again, very, very small support because you don't have a lot of data types with a lot of duplicates, right? What are they? Well, TS vector, that's full text search, okay? No surprise there. JSON B, yep, that makes sense. A lot of duplicates there, okay? JSON B, this one, and an arrays, a lot of duplicates. That's it. So don't, you know, you don't, don't bet the form on gin because it's only a couple, a couple data types that really benefit from this. Jist, again, I said the catch-all for everyone else, things like box, circle, all the 2D stuff, we can do Jist on JSON B. Maybe not, I don't, I may not recommend it, but we used to recommend it when gin was slow. Now that gin's fast, we may not need this anymore. But again, it's there. Point, polygon, again, 2D stuff, range types is the go-to for Jist. I'm not going to get any range types, my other talk does talk about that. And full text search, again, you can also use Jist, probably want to use gin, now that gin's so much faster, in fact, I've been responsible for updating the documentation to kind of talk about that, okay? SP Jist, this is that prefix thing. Range types, text stops, this is the one you probably were thinking of, where you've got a prefix and you're going to slice it up and it does it automatically for you. Range types, again, I'm not sure too much. These I'm going to talk about later, yes? The email address might be a case where, at first it appears this is good, but since your repeated pieces are... At the end, yeah, you'd almost have to flip the email address around to make it useful, yeah. And almost, yeah, it's kind of an unfortunate way that we do... Yeah. But you could do that, but again, it'd be kind of awkward, yeah, I agree. Okay, let's go... Let's look at some examples. So this is B-tree, standard structure. Everyone knows that one. So, Bryn, here's an example. I'm going to create, I think, 10 million rows. I'll create a B-tree index, I'll create a Bryn index, and you can take a look, that's my B-tree size of my index, that's my Bryn size of my index. Okay? Just dramatically different. Here's full text search. If I have this text here and this text here, this is my full text search, it's broken up into words. What's interesting is the index has individual entries for some of the words and has multi-row entries for some of the other words. That's what I'm trying to get at, this... The way the gene works, it's effectively going to have one key and then a bunch of row matches. Okay? Obviously, very similar. In their initial rays, similar kind of case. JSON, here we've got key value, key value. Again, it breaks it up that way. But if you look at the index, again, key, multiple values. Key, multiple values, key, multiple values. Okay? Pretty straightforward. Okay? Let's see here. Text, JSONB, path ops, this is a little different. This is a different way of indexing with gene on JSON. It actually hashes the whole path and therefore, you effectively... If we're going to look at very deep hierarchies, you can look up very deep hierarchies very efficiently with path ops. Because in this case, it's going to break up every key separately and it's got to kind of put them together. Whereas when you do path ops, it's kind of kind of... Hold on, it's starting here. Yeah. When you do path ops, it's effectively going to hash them and kind of pull them together. So, again, supports loosely a couple values, also tightly coupled values like that. Okay? Now, unfortunately, I am out of time. However, we do have an hour lunch. So, I'm thinking I'll go an extra five minutes. Is that good with everybody? Everyone, you're okay? You might be at the end of the line, though. Like, is that okay? Like the food line. We're good? Okay. So, just to talk about nonlinear indexing a little bit, again, think of this as a B tree. You're doing B tree. Everything's linear. Very easy to understand. How do you index this with B tree? Right? You don't do this. That's not very helpful. Right? Because you're not distinguishing the why, value, and any of these things. The real way to do it is with bounding boxes. And if you want to hear bounding boxes over and over again, talk to my Russian friends. They used to talk about it forever. Bounding box is effectively an index that's a 2D box. And you're indexing by making smaller and smaller boxes within your larger index. Okay? This is very, not only would you use it for 2D points, but think of range types, which are kind of 2D ranges, right? You've got a range in the box gets smaller. Same kind of thing. They go levels. They go smaller and smaller. Okay? And again, box, circle, point, polygon, these are all used by PostJS. Feel free to talk to Paul Ramsey about that. He is here at the conference. But again, JIST is really good for that. So again, range is smaller, smaller, smaller boxes is how you do it. This is the SP JIST. Remember we talked about the prefix one. What we're effectively doing is we've got a prefix. Think of a URL. I've got all the HTTPs in one part of the index, all the FTPs in another. Then we've got the domain names and we broke those up. And then underneath those domain names we have, you know, smaller and smaller boxes. Okay? So we're basically just getting smaller and smaller. But it's automatically slicing this long string up into pieces for me. And that's really great. So there is these other ones. I talked to Theodore about the details. They're all kind of cool. So extensions. We have a bunch of extensions. Btree, JIN. I talked about, for this gentleman, it's a JIN implementation of Btree for lots of duplicates. Btree, JIST for the same, cube, HSTOR, again, a lot of indexing support for those types. So in summary, how would you figure out when to create indexes? PGSTAT user table sequential scan would indicate maybe I need an index there. You can use explain, PGSTAT statements, PG badger. Sequential scans aren't always bad. But again, you may want to delete indexes that have low usage and unnecessary indexes are a bad thing. When you're considering an index type, consider how long it takes to build, consider how big it is, consider the index update overhead, and the access speed. And also the operator flexibility. If you start to look at full text search and JSON and arrays, there are some special operators that only work and are only indexed by these special data types. And that is it, ladies and gentlemen. I went six minutes over. Shame on me. But again, I wanted to open it up to all the questions that you had. We had some really good ones, particularly in the beginning. I know the part at the end where I start to talk about special operators, it's really complicated. But I will, I try the best I can. Let me answer this question. Yes, sir? Yeah. So is there a way to see inside the index and see the matches? You'd have to dump the index out and look at the internals of it. There's no way to look at the index directly, which is a great question. So thank you very much. I will be here for questions. Sorry I went over. Have a great lunch. Thank you.
 Okay. There's probably enough energy in the room. We can just coast through this one.  For those of you in the previous session. So anyway, I'm sure we'll get some feedback  from that big discussion. What I am here to talk to you about today is not about what  the previous session is about, but something completely different. As you know, Postgres  has a very flexible object extension system and a very flexible data model, a way of  storing a lot of very non-traditional data types like JSON and GIS and full-text search  and stuff like that. And one of the core things behind all of that sort of creative non-traditional  relational object storage stuff is indexing. And this talk is about exactly that topic.  I think that indexing is sort of one of our unsung heroes of Postgres. You don't see  it a lot. People don't talk about it very much. But without really, really powerful  indexing, a lot of the non-traditional storage types that we support like JSON-B and full-text  search and GIS would really not be possible. So this talk is about that topic. It's about  indexing. I think you'll find it very interesting. I learned a little bit even in working on it.  And frankly, the way that the Postgres documentation presents indexing is not ideal. It's a little  hard to get your handle on. You end up sort of following what everyone else did. Oh, I  need a specific type of index for that data type. Or I need a specific type of index for  that data type. But what this talk tries to do is to actually explain why. Why do you  need special indexing types? Why do you use one indexing type over the other? And also  to give you one or two indexing types you may not have even heard before that are available  in Postgres that are very powerful. So I think you're going to enjoy it. I have to give attribution  here. A lot of the indexing that we're talking about here comes from the Russians, as we  call them, Theodore, Alexander, and Oleg. Oleg is not here. Alexander and Theodore certainly  are. If you look around, I don't think they're here, unfortunately, but are they? No? I don't  see them. Anyway, Theodore normally has a vest. And I think Alexander was wearing red  today, but he's kind of tall, sort of stately looking in a way. But young, so sort of a  combination there. Oleg is not here. Jonathan Katz also is around. He's in New York or so.  If you hear the voice, you'll know right away who that is. These presentations are actually  on my website right here. So if you wish to download these slides right now, you can,  or sometime in the future, there's probably 20 or so other slides, other presentations  up there that you might find useful. So we have an ambitious agenda because indexing  is a complex topic. First, we're going to talk about traditional indexing. This is going  to be the easy part. This is sort of what you remember from all the other relational systems  that you've worked on. But then we're going to talk about some of the ways that Postgres  has taken traditional indexing and extended it, I think, in a very powerful way. This  will probably be the easier of the parts because what we're doing is we're taking the traditional  indexing type that you've seen in all the other relational systems and just adding new  capabilities to it. And I'll show you some examples of that in items three and four and  indeed in item five. Then when we get into item, I'm sorry, item four, and we get into  item five, we start to talk about where the wheels come off, non-B tree indexing types.  We'll talk about what those types are, give them names, explain a little bit about their  structure. Then we're going to explain how they support indexing, particularly, and specific  data types, and then finally give you a summary. There is another presentation that I'm not  going to be giving at this conference called non-relational Postgres. So if you're curious  about how Postgres supports a lot of the non-relational types, range types, I see some range types  guys here, GIS and full text search and geographical stuff, that non-relational Postgres is sort  of a good one to watch before this. If you're not familiar with a lot of the non-relational  things that Postgres can do, so I'm not going to cover that too much. If you need a primer  on non-relational Postgres from my website, great place to look.  So any questions? Because I like to take questions as we go. Yes? Nope? Nope? Okay. So first,  traditional indexing. Traditional indexing for relational systems is B tree. Great, very  flexible, has high concurrency, fairly compact storage, although I know that somebody, another  one of our Russian friends at Estasia is working on making B tree even better. So if you catch  her, feel free to talk to her about that. But there are other, B tree is sort of the  catch-all. And if you only have B tree, it is the only option for your relational system.  So there's a lot of relational systems that really just kind of have B tree. Maybe they  have hash, but they don't get into some of the craziness that Postgres does. And therefore  they can't really support a lot of the indexing that we do. Because Postgres originally was  designed as an extensible system, it's been very easy over the years to say, oh, I'm doing  full-text search, I need a special indexing type for that. Oh, I'm doing GIS or 2D points,  2D geometry, I need a special. So the idea of being able to extend Postgres as new data  types became necessary for storage is one of the sort of geniuses of Michael Stonebreaker  and how that original research project was designed. And I'll try and cover that to a  tiny extent. But again, B tree, great. Great for high concurrency. Great. The index is  basically key and then some kind of row pointer and key and row pointer all the way down. Great  for sort of single lookups, even range looksups. Order by, of course, makes a lot of sense  for B tree. If you're familiar with merge joins, merge joins make use of these B tree  operators because they present a single linear ordering of your results. I'll have you curious  about merge joins. I do have a explaining the Postgres optimizer talk on my website  that covers that. And also, Neslub with index scans, again, this is sort of the bread and  butter of most relational systems. But what I'm going to be talking about today is the  idea that as good as they are, they can be extended in some creative ways, even B tree,  and then there are some even more cool types that I think you'll find really interesting.  Okay. But I want more. Maybe I want an index, not a column, but an expression or a function.  Some relational systems support that, some don't. Maybe I want roll control. Maybe I  want small, lightweight indexes because B tree can be, you know, a significant portion  of the size of the table. You might think, well, that's always going to be that way,  but that's not actually always that way. You might want to index nonlinear data. Very  hard to linearly represent a 2D space, right? I mean, my definition, 2D spaces are 2D. You  might want to do something like closest match searches. This is kind of difficult to do  in B tree. You may want to index a lot of duplicates. Now, B tree will index a lot of  duplicates, not very efficiently. And you might want to do multi-valued fields, particularly  something like a JSON, JSON B type. Again, you can see where B tree doesn't really play  too well in this area. So let's just talk about the straightforward extending expression  indexes. So extending B tree indexes, I'm sorry, in this case, I'm going to show you  an example of, actually, let me ask you any questions. Okay. So let's talk about indexing  an expression or a function call. Again, some databases support this. Some databases don't.  If you have a query like, I want to look up somebody's name, but I don't want to specify  the name in the case specifically. I want to specify just the name in all lower case,  but I just want anything that has any match in case to match this record. You can do this  query in any relational system, and it will return the right result. Okay. But what you,  what the problem is that if you try and create an index on the column, it's not going to  use that here. So one of the things I'm, one of the things that I continually talk about  when I'm talking about indexing is that you can do a lot of non-relational storage with  a lot of the other database systems. But if you can't index it, it's a toy, right?  This is the classic case. You do a proof of concept. It runs great. You go to a production.  It doesn't, the system just falls over because it needs that indexing to really make it function  and perform at the scale that your enterprise needs. So one of the great things about Post  Grass is that you can create something called an expression index, and that's either by  placing a function call inside the created index command or literally a plus sign, a  factorial, you know, a concatenation. You can do almost anything, any type of expression  in there, and Post Grass will actually use it. So here's an example. I've created a thousand  customers, and I basically created an index on their name. Now, this is the traditional  index, just create name, and if I go and I say, give me customer 9999, the system automatically  knows, oh, okay, let's just, you know, do an index scan, pull them up. That's a standard  B3 operation, no problem. Okay? But if you try and do something like function call on  that column, Post Grass, by default, if you just index the column, it's going to fall  over. Okay? It's going to do a sequential scan. This is what I'm talking about. It's  not going to scale for that kind of use case. But if you use an expression index and you  now say, create an index on the lower of the function call of that, then when I actually  do a lookup, it actually knows to do an index scan and to pull the records back. Okay? So  a lot of cases, you may have lookups in your ware clauses that are not traditional lookups.  They may rely on an expression. They may rely on concatenation. They may rely on a function  call. And by creating an expression index, you can now get performant results from this  kind of query. Okay? Again, user-mined functions, concatenation, math expressions. The functions  that you use in an index have got to be immutable. There is a special immutable flag that has  to be present on that particular function because you can't have the value that that  function returns changing over time. Right? It's got to be a stable. Every time I put  a two in, I get a four out. If you have something that relates to current timestamp or something  like that, you start to get into trouble because that, the value that comes out at the time  the row was added and the value that you may compute later, if you've got current timestamp  in there, it would be potentially different. Okay? So just be aware that's the one that  usually catches people up is that current timestamp shifting and it's not immutable function and  therefore you're going to have trouble. So just be aware of that sort of restriction.  And also you might need to do casting depending on how it works. Okay? Any questions about  expression indexes? Okay. I know, you know, I will tell you I always start really kind  of slow. By the time we get to the end, you'll be like, whoa, okay. But I always kind of  ramp up as we're going. So let's go to the next one. This is partial indexes. This is  a little more on the edge. You've always assumed when you create an index that every single  row is indexed. But there is a value to being able to say, I only want to index some rows.  You might think, I'm never going to want that. Well, don't make that decision right away.  Okay? Sometimes, why index every row if you're only going to look up some of them? Like,  why have the storage space? Okay? It's smaller if you just index as the one you want. The  index is less deep. Okay? And more shallow, basically. There's not the insert update overhead  of updating index for rows that you're never going to use. But you can still get to the  rows. It's just that they aren't indexed. Okay? So here's an example of another table  I'm going to add. I'm going to add a state column to my existing customer table I did  over here. I'm going to update and add. I'm going to make all of the 900 and plus, so  we're all like from 900 to 1,000, those people are all going to be in Arizona. Okay? So I'm  just going to put Arizona for one tenth of my people. And now I'm going to create an  expression index. I'm going to say, index all of the people in Arizona. All right? Maybe  I have some tax law in Arizona. Maybe I live in Arizona. And I'm always looking at people  who are local to me. Maybe I have it out for Arizona. I don't know. Whatever. Okay? Now  if I go and I say, give me everyone in Pennsylvania, system runs fine. It's like, I know you didn't  index Pennsylvania, but I can still give you the rows. I'm just going to automatically  sequential scan that table. Okay? But I've asked for everyone in Arizona, system automatically  does an index scan and says, oh, I can get you those Arizona people much faster than  doing a sequential scan. I have an index that will just pull those off right away. Okay?  And that's a really, really powerful optimization you can do. Again, reduces the overhead of  maintaining that index, the storage size of the index, and obviously the depth of the  index. Classic case from my experience, we used to have an accounting system. Oh, you  have a question? Yes, sir. Please. Let's say the column is a boolean. And you say, index  where, you know, is true. Totally. So, but I always assumed that all the ones that were  in other case would all be in the same index slot as it were. Yeah. And so, would occupy  one slot of the index anyway and that would be it. So, that's, you're, you've walked right  into what I was about to say, which is great. Okay? We used to have an accounting system  that I used to do consulting and it had a, it had a, you know, what was it? Invoice is  zero flag, right? So, you'd have, I don't remember what it was called, but you'd have  a flag that would indicate whether this index was closed, like whether it had activity or  it was non-zero or it was zero. It was zero. It was really there just for historical reasons,  right? And you were always running reports asking for the non-zero invoices, right? Because  that was all of your work. But in the database that I was using in the 90s, there was no  way to do that. So, you effectively had to index all of your rows. 99% in my legal application  experience were zero, right? But I had to index all of them so I could pull out the  non-zeros really quickly. And this is a classic case. If you create an index on a boolean on  the whole table, it's going to index every row. It's going to have, and I'm going to  go back up here because I hate to do this, but remember I said that the index is effectively  key value, key value, key pointer, key pointer. So, you're going to have 99% of your index  is false, pointer to false. False, pointer to false, right? The index does not make a  distinction even though it knows 99% of those are indexed false. And frankly, probably the  optimizer would never choose a 99%. It's only filtering out 1% of the rows, right? And it's  never going to use an index for that. Frankly, indexes have to filter out almost 95% of the  rows before they're going to be used in a lot of cases, okay? Not in this case, but the  index system is not going to make that decision. It's not going to know what your future data  layout is going to be. It's not going to know a lot of things. So, it's going to index all  of them, right? And that's the classic case actually for me as boolean where you're kind  of like, well, I don't really want to index all these zero invoices. I just really want  the other ones. So, that's a great example. But the bottom line is, yeah, it's going to  have a lot of falses in there. And that index is going to be huge. It's still going to get  to the true ones really quickly because the index, the optimizer knows how selective a  true is or a false, right? And it's going to use the index depending on that. But in  terms of storage space, they're all there. That's a great, perfect question. Yes, sir?  Yeah. I would, so I'll repeat the question. So, the question is, would you use four different  indexes on four different unique state values? The bottom line is no. You'd create a single  index on that. There's really the optimizer smart enough to know which ones are selective  and which ones aren't, creating individual ones. I don't think gains anything. Because  of the way B tree works, all of your states are going to be right next to each other and  the index, the optimizer knows that. So, it's going to do that fine. The case where you  would really want to use that is where you've got some really dominant state that you don't  want to index, right? That's when it starts to make sense. And technically, so if 95%  of your customers were in your home state or province, okay, you might want to index  everyone who isn't in the province you're in. And technically, you can actually, I'm  not going to cover this, but you can actually say, state is Arizona and state is not Pennsylvania  and it'll actually use the is not Pennsylvania. You can create an index of is not in Pennsylvania  and it'll actually use is not in Pennsylvania to find the Arizona people, okay? Because  what I'm doing is by saying not in Pennsylvania, I'm excluding 95% of my rows, right? I'm creating  a very small index on 5% of my customers. But now my where clause, I have to say, which  doesn't seem to be logical, customer in equal state equals Pennsylvania and state not equal  to Arizona, which sounds completely ridiculous because I've already said Pennsylvania, why  would I say not Arizona? But I'm saying, or I would say in Arizona not in Pennsylvania,  why would I say not in Pennsylvania only so I matched an index? Literally, the system  is going to try and match the where clause with whatever literal you put in the preposition  of the partial index. It's kind of tricky. Yeah.  Yes. Totally.  I would love to, if you can tell me, I can't remember some of the smarts is enough. Like  when I say not Pennsylvania and equal Arizona, I thought it would figure that out. I can't  remember if it figures it out. So maybe I need to go back and try some more testing.  I could probably just take this example and run it for somebody here could do it, whatever.  But I don't remember how smart it is or how literally you have to match this. Years ago,  you had to literally match it. I think we've gotten smarter here, but I don't know how  smart. So great question. I don't have an answer to it. Next question. Okay. So again,  if I now do my check equals Arizona, it does a sequential scan. If I now, so I'm sorry,  when I'm doing it here, I'm saying I'm creating an extra Arizona. If I look for everybody,  I get a sequential scan because it can't use the index. But if I ask for Arizona, even  if I ask for the customer name and Arizona, it still knows to use the index because the  index is definitely restrictive. So I'm still looking for these customers, but only in that  Arizona index. And of course, if I just ask for everyone in Arizona that works, I can  even do, I can even create, let's see here. But anyway, so you kind of get the idea of  how that will go. We have another way of doing index is called a bitmap index. It's used.  It's called a bitmap index scan. It's not technically an index. It's automatically happens  when you run queries. You've seen bitmap index scan right here, for example. It's particularly  used when we expect an index to generate multiple matches on the same page. So if we expect  the index to hit a bunch of matches, we'll use a bitmap index scan. It creates a bitmap  in memory. It basically does either raw or block level granularity. And then we can visit  the rows once just using our bitmap. And what's really great is you can take different bitmap  scans, join them together using multiple indexes and kind of get this mega index, which is  a combination of bunch of different indexes. Okay, again, this happens automatically. It's  not something you're going to do, but be aware when you see a bitmap index scan, that is  what it is doing. Okay. Now, that is the easy part. Okay, now we'll go to the hard part.  The hard part is all the non-B tree indexing types, all of the non-traditional indexing  types that Postgres supports. Why are they there? What do they do? And why do they really  make Postgres's type system shine? Okay. This is like a big, I know it's like, whoa.  The first one is kind of an interesting index type. We've had it for a couple of years.  It's called BRIN. It stands for Block Range Indexing. It basically creates tiny indexes  for large tables. So if you've ever wanted to create an index on every single column  in a table, this is your baby. All right. The index are very small. Index is typically  something like.003% of the size of the table. Right? I mean, really small. So it basically  stores minimum and maximum values over a range of blocks, in this case, one megabyte. So  for each one megabyte piece, it's just going to store a minimum max. And then it's going  to skip or scan each one meg chunk. Now you can change the sizes, but default, you've  got like a one meg range there. Skip to the large sections of the table, thinking of a  300 gigabyte table. This BRIN index is just great. You're breaking the table up into what,  you know, 300,000 individual pieces, and then you're just able to kind of skip or scan each  one and beg a bite chunk. It's really great for naturally ordered tables, things like  indexing, insert-only tables, chronologically ordered. If you've loaded it to data in a  sequential order, that's really good. Indexes are very inexpensive to update, you know,  very small costs. They are slower than B-Tree. But again, if you try and B-Tree index every  column in your table, your indexes are going to be far larger than your table itself. And  a lot of times you don't know what you need to index. This is a great sort of fallback  for that case. Okay? Second index type, GIN. We've had this for years. Alexander Klokoff  has worked very hard on this in terms of improving it. It's really great for indexing values  that have many keys, like text documents, JSON, multidimensional arrays. Okay? Also great  if you have a lot of duplicates. Remember I told this gentleman about the, like, the  falls and every, like, you know, 99% is false. Well, in this case, you're going to have one  falls and a whole bunch of rows, which is a lot more compact than the traditional B-Tree  where every single row has to have a key in the B-Tree index. Okay? Yeah?  Absolutely. In fact, if you look at the Postgres to-do list, one of the things that is listed  as not wanted is Bitmap Index. And the reason the to-do list says we don't want it is, effectively,  we are unclear where a Bitmap Index would win over this indexing type. Because the  problem with Bitmap Index, it's, Bitmap Index is great if you've got a table that never  changes. But growing a Bitmap is fairly difficult to do. So what Jim is sort of allowing you  to do is to have the benefits of the Bitmap Index without the overhead and the problems  of growing and shrinking that index as the table changes. So we don't know if we're ever  going to have a Bitmap Index because we don't know how we'd ever be, effectively, your great  point this exact index type. So if you're familiar with Bitmap Indexes from other, not  Bitmap Index Scans, which is a different case, Bitmap Indexes, this is a great replacement  for that in some ways better than a Bitmap Index. So that's a really good point. Other  questions? Yes?  Could you put a range of the medians that's coming in at the end?  Well, I'll just give you some just off the wall. So let's just think of a data type.  Let's think of full text search. So I'm going to have tons of me, the word me, all over  that index. So do I want every me that's in the index to have a single, every me that's  in the table is going to, in the text fields, even though I have multiple me's, I'm going  to have an entry in the index that says me and then the value. What Jim is going to do  is he's going to give me one me for no matter how many me's across any column, any field,  any row in that table, and this is going to have all the matches. So it basically takes  the B tree we're going to have due because you just roll them up. So frankly, I don't  even know how you do full text search with B tree because you'd have to have multiple  matching rows for multiple words. It wouldn't even work, right? Because it's like saying,  you know, typical B tree, when you create a B tree, it's like, okay, when I index that  column, you know, that column has an indexed value of five and that one has a, in this  case, that one column because it's a full text search row or a JSON row, it may have  a five and a seven and a 12 and, you know, a bunch of row, values in that single field.  So there's no even way to think of how we do this in B tree. But certainly any case where  you're looking at a significant percentage of the table, even like three or five percent  of the table has the same value, you'd probably be doing this. In fact, there is a contrib  module called B tree gin, right? And it effectively takes the B tree sort of operators and makes  a gin index out of it. So if you want to, right? So that's actually, I can't tell you  when that's going to win, but I know I see a lot of activity on it. Like we get bug fixes  once in a while. It's not there. People are using it. And again, when you have a lot of  duplicates in B tree, Anastasia, I want to say Lumikova, I'm not saying her last name,  right? She's kind of tall and like, I know what you were yesterday. I didn't see her  today. So if you see her around, you can ask her because she's done a lot of research on  duplicates on B tree. So when I was in Russia a couple of years ago, she did a talk on,  she has a whole patch that's designed to take B tree and make it operate more efficiently.  But the problem is that's gone now compete against B tree gin, which is this. So now  you've got B tree, which is not good for duplicates. You've got gin, which is great for duplicates.  You've got B tree gin, which is in the middle. And then she's trying to say whether we could  take B tree and kind of move it closer to B tree gin, you know what I'm saying? So the  kind of, the kind of, you'd think that there's only a couple of ways to index something, but  there's a whole spectrum of efficiencies that you can do when you've got duplicates and  when you've got multi-valued matches in a single field or a single field. Yeah. Great  question. Yes. Okay. So optimize for multiple batches. Key is stored only once. The index  is key and then many row pointers. Remember B tree was key, row pointer, key, row pointer.  This is key, many row pointers. If it was visually, I'll show you a visual example later.  Indexes are batched. Therefore, one of the problems we always have with bitmap indexes  is updates. Very expensive because it just, so this, the gin code has like a, like a queue.  So when you do a change on the index, it kind of goes into the queue. And then when anyone  looks up the index, they check the queue first and then they go to the main index. So there's  always this, and then you batch those updates because when we originally implemented gin,  I think this was Alexander, a little before Alexander, maybe it was Theodore or Futter,  the updates were very slow. So over time, we were able to kind of batch them and that  really improved the insert update performance of gin indexes now where they perform really  well. And in fact, even as recently as 9.4, Alexander added compression, very powerful  compression to this gin row pointer list. So you can imagine for the word me or the  word thank you, a thank or son, there may be, you know, thousands of row pointers. And  he in 9.4 is able to have a compression algorithm across there and optimize it for multi-key  filtering. I'm not going to go into it. I did understand it at one point. But again,  this is really, really high-powered stuff, which really takes postgres, I think, for  these multivalued and non-relational storages into a really amazing direction.  A related index is called GIST. We've had this a little longer than gin. It's called  generalize search tree. It's a lot less specific, hence the name generalize. It's really designed  for things where we can't use B tree, we can't use gin, we can't use brin. So things like  geometric types, range types, h store, trigrams, these are nearest neighbor. So again, it's  kind of a catch-all indexing method for a whole bunch of things. And I'll show you some  specific examples later, what that does.  SPGIST, I think this is Futter and Alexander worked on this. This is something called space  partitioned generalized search tree. So it allows the key to be split up and the parts  are indexed hierarchically into partitions. So I'm going to show you a graph of this later.  But effectively the idea is that you take a URL or an email address and you break it  up into parts and then everyone who has the same common first part goes in the same place  in the index. You don't see this very much. Usually when you're indexing something, you're  indexing a discrete thing. What space partitioned GIST is, is it's assuming it can take that  thing you're indexing and look at prefixes and slice it up into prefix parts and then  put everybody, for example, who's at a Yahoo address in the same place and whatever. This  is something I think is pretty cool. It's not traditionally used very much, but there  are special use cases, particularly for very long indexed values. Integers doesn't make  any sense, right? Words probably doesn't make any sense. But when you start to think about  a structure, think of a URL, right? It's kind of how directories work, the idea of taking  a path name and breaking it up into pieces and then having this piece is kind of all  together. So everyone in bin is going to be, even though you're indexing a long path, everyone  who has a bin to begin with is going to go in the same part of the index, right? Really  great for prefix searches, obviously. Yeah.  You could. You'd have to make sure that the last name is the first part of the indexed  search and then maybe concatenate it together. So I would almost take, if you've got first  and last name in a separate field, you can actually create an index that concatenate  like that, use an expression index and concatenate it together and then put the word at the front  and then the space and then, and that would actually kind of start to do that type of  thing. Yeah.  Phone numbers is a classic, right? Because you've got the area, country code and then  area code, right? Yeah. Yeah.  Is it one slice or can you put country, use country code for one grouping and then within  that area code?  The cool thing is you don't do anything. You just index, you just take, create an index  and it figures out how much, what's a good break point for these partition boundaries.  Yeah. Yeah.  And then you just assign it table spaces, basically.  No, you just create an index on the column and you're done.  That's it.  That's it. Yeah. So if you see footer, he's the guy who worked on this. He's been around  for a couple of years, but it doesn't seem to get a lot of traction. Partially because  people read the docs and they're like, why would I use this, right? And they're like,  well, yeah, there are some cool reasons to use it. All right. But again, it isn't, it  isn't obvious. Hash indexes, we have improved those in Postgres 10. I don't have to embarrassingly  sheep away and say boo, like I did, I used to have a boo slide for this. So again, hash  indexes, very good for quality, doesn't have any not a quality look up, no range look ups,  but again, crash safe, replicated. The B tree is so fast, I'm not sure when hashes  are when there are some cases, hash indexes are typically smaller, particularly for long  keys. So if you're indexing, the classic case I had was indexing something like a large  object. You might say, well, why would you index a large object? If you're indexing  an encrypted value, which is effectively stored as a large object in Postgres, those can be  pretty long, like 64 bytes or whatever. And you create a hash index, now you're not indexing  the whole thing, you're just indexing like the hash of it. And that's a great one. Jimmy,  you had a point.  You were great for UUIDs.  UUIDs, thank you. Because it's automatically shrinking it down for you. It's still going  to check to make sure for hash collisions. So you don't have to worry about it. It's  still going to check the raw value. But obviously that hash is filtering very well. And it's  going to check the raw value.  Great. Yeah, UUID. Any kind of long text string or anything, the idea is to kind of auto-hash  it, auto-shrink it down. That's really, I think, where the big win is for hash indexes.  Yeah.  Would it be UUIDs stored as text or as a native UUID? Either one, there's a performance that  it overbeats UUIDs.  Cool.  Yeah.  Thank you.  Great point. Thank you.  In other databases, you can use it for social security.  Well, the problem is this is just the indexing portion. So you still have the raw social  security in the table.  Yeah. Sometimes if you're an insurance company, you have to have the raw social. The point  is that you never do a range search on social...  Absolutely true.  And then...  Absolutely true.  Yeah.  Yeah.  Now, I have to ask a question because you've asked two questions. Did I tell you last year  that you should have been like a radio announcer or did I talk to you about that already?  I was.  I knew it. That's great because as soon as you asked the question yesterday, I'm like,  wow, who's that talking?  This is kind of funny.  Great. Good for you. Thank you.  Okay. I'm not making this up. So effectively, this is a query from Postgres. These index  types are literally stored in the database. I talked about the extensibility of Postgres.  These are literally stored inside the database.  Okay.  All right.  So let's get a summary. Where are we? B-treat. Ideal for indexing unique values. Nobody's  going to beat that. Okay?  Bryn. Ideal for indexing many columns. Small indexes. Again, these slides are online, so  feel free to look them up whenever you want. Okay? They're on my website. I didn't even  mention I work for Enterprise DB, but anyway, it's been 12 years. I guess I don't even say  it anymore.  Genie index is ideal for many duplicates, space, SP gist. Ideal for indexes whose keys  have many duplicate prefixes. That's really the concept I want to get across. Space partition  gist, common prefixes of long key values. Gist is just everything else. It's just the  catch all when everything falls through those cracks. Okay?  All right. Any questions?  Yes.  Yeah. Right. Right.  So why don't we consider hash for primary keys? Part of the reason is because a primary  key by definition is unique. We could use a hash for that, but historically, because  post-grass, the hash indexes weren't crash safe. We just never were going to do that.  Now that we're crash safe in 10, we potentially could do that. If somebody came to us and  said, you know, I want the option to do it, and here's the benefit in speed I get if I  could do it, we would definitely consider that. There's nothing. There are some internal  reasons why we really like B-treat, because when we're locking a row for foreign key check,  we're going to want to lock that specific value. And the problem with the hash is you  can have hash collisions, and we can't identify as quickly from the index exactly which index  matches my row. So if you're two people are inserting at the same time, this is more internals,  we're going to lock that index so somebody else doesn't come along and insert the same  key value. And if we, to do that for hash index, it would be kind of dicey because of the conflicts,  potential hash conflicts within the index. That's not a user-visible thing, because we're  always going to check the heat, but we might not want to do that. I don't know, but it's  possible.  That's a great point. So other databases do support this, so maybe we should look at this.  Now that we have unembarrassing hash indexes, I'm going to use that term, it's definitely  something we could look at. Yeah. Great. Yeah. In fact, Grant, who was speaking before,  has a great talk about that hot problem with, I think he's done a lightning talk on it,  and I think he hasn't talked about it. So if you're curious about that, what he found  was that when he indexed a hash, he got so much churn in the index because he wasn't  hitting the same rows on insert, he was getting all over the place that he didn't actually,  it didn't actually work well. That was kind of interesting because that was a time series  case. So anyway, I thought it was interesting. Okay, so let's take a look. Data type support.  So again, I'm querying the system tables. Not every data type supports every indexing  method. Okay, so you can't, you can probably use Btree on almost anything, okay, but you  probably don't want to do that because if you Btree index something like JSON B, it's  going to index like the whole thing, the whole document, right? That's probably not what  you want to do. You want it to break it up into pieces and index, there's a whole bunch  of operators that are possible only when you, only, they're indexable only when you create  a non-Btree index on some of these types. So just because Btree supports it doesn't  mean that's where you should be going, right? So you, unfortunately, you have to understand  a little bit of this, particularly like the range types and stuff. You just don't want  to use Btree on this unless you're looking for absolute equality of the whole field.  That's really where Btree wants to be, right? No surprise. If we look at Brinn, again, this  is that tiny index where we can kind of slice things up, okay, and you can see that it's  effectively slicing it up very well. So the whole bunch of different data types are going  to be sliced up with Brinn, okay?  Gin, again, very, very small support because you don't have a lot of data types with a  lot of duplicates, right? What are they? Well, TS vector, that's full text search, okay?  No surprise there. JSON B, yep, that makes sense. A lot of duplicates there, okay? JSON  B, this one, and an arrays, a lot of duplicates. That's it. So don't, you know, you don't,  don't bet the form on gin because it's only a couple, a couple data types that really  benefit from this.  Jist, again, I said the catch-all for everyone else, things like box, circle, all the 2D stuff,  we can do Jist on JSON B. Maybe not, I don't, I may not recommend it, but we used to recommend  it when gin was slow. Now that gin's fast, we may not need this anymore. But again, it's  there.  Point, polygon, again, 2D stuff, range types is the go-to for Jist. I'm not going to get  any range types, my other talk does talk about that. And full text search, again, you can  also use Jist, probably want to use gin, now that gin's so much faster, in fact, I've been  responsible for updating the documentation to kind of talk about that, okay?  SP Jist, this is that prefix thing. Range types, text stops, this is the one you probably  were thinking of, where you've got a prefix and you're going to slice it up and it does  it automatically for you. Range types, again, I'm not sure too much. These I'm going to  talk about later, yes?  The email address might be a case where, at first it appears this is good, but since  your repeated pieces are...  At the end, yeah, you'd almost have to flip the email address around to make it useful,  yeah. And almost, yeah, it's kind of an unfortunate way that we do... Yeah. But you could do that,  but again, it'd be kind of awkward, yeah, I agree.  Okay, let's go... Let's look at some examples. So this is B-tree, standard structure. Everyone  knows that one. So, Bryn, here's an example. I'm going to create, I think, 10 million rows.  I'll create a B-tree index, I'll create a Bryn index, and you can take a look, that's  my B-tree size of my index, that's my Bryn size of my index. Okay? Just dramatically different.  Here's full text search. If I have this text here and this text here, this is my full text  search, it's broken up into words. What's interesting is the index has individual entries  for some of the words and has multi-row entries for some of the other words. That's what I'm  trying to get at, this... The way the gene works, it's effectively going to have one  key and then a bunch of row matches. Okay? Obviously, very similar. In their initial  rays, similar kind of case. JSON, here we've got key value, key value. Again, it breaks  it up that way. But if you look at the index, again, key, multiple values. Key, multiple  values, key, multiple values. Okay? Pretty straightforward. Okay? Let's see here. Text,  JSONB, path ops, this is a little different. This is a different way of indexing with gene  on JSON. It actually hashes the whole path and therefore, you effectively... If we're  going to look at very deep hierarchies, you can look up very deep hierarchies very efficiently  with path ops. Because in this case, it's going to break up every key separately and  it's got to kind of put them together. Whereas when you do path ops, it's kind of kind of...  Hold on, it's starting here. Yeah. When you do path ops, it's effectively going to hash  them and kind of pull them together. So, again, supports loosely a couple values, also tightly  coupled values like that. Okay? Now, unfortunately, I am out of time. However, we do have an  hour lunch. So, I'm thinking I'll go an extra five minutes. Is that good with everybody?  Everyone, you're okay? You might be at the end of the line, though. Like, is that okay?  Like the food line. We're good? Okay. So, just to talk about nonlinear indexing a little  bit, again, think of this as a B tree. You're doing B tree. Everything's linear. Very easy  to understand. How do you index this with B tree? Right? You don't do this. That's not  very helpful. Right? Because you're not distinguishing the why, value, and any of these things.  The real way to do it is with bounding boxes. And if you want to hear bounding boxes over  and over again, talk to my Russian friends. They used to talk about it forever. Bounding  box is effectively an index that's a 2D box. And you're indexing by making smaller and smaller  boxes within your larger index. Okay? This is very, not only would you use it for 2D  points, but think of range types, which are kind of 2D ranges, right? You've got a range  in the box gets smaller. Same kind of thing. They go levels. They go smaller and smaller.  Okay? And again, box, circle, point, polygon, these are all used by PostJS. Feel free to  talk to Paul Ramsey about that. He is here at the conference. But again, JIST is really  good for that. So again, range is smaller, smaller, smaller boxes is how you do it.  This is the SP JIST. Remember we talked about the prefix one. What we're effectively doing  is we've got a prefix. Think of a URL. I've got all the HTTPs in one part of the index,  all the FTPs in another. Then we've got the domain names and we broke those up. And then  underneath those domain names we have, you know, smaller and smaller boxes. Okay? So  we're basically just getting smaller and smaller. But it's automatically slicing this long string  up into pieces for me. And that's really great. So there is these other ones. I talked to  Theodore about the details. They're all kind of cool. So extensions. We have a bunch of  extensions. Btree, JIN. I talked about, for this gentleman, it's a JIN implementation  of Btree for lots of duplicates. Btree, JIST for the same, cube, HSTOR, again, a lot of  indexing support for those types. So in summary, how would you figure out when to create indexes?  PGSTAT user table sequential scan would indicate maybe I need an index there. You can use explain,  PGSTAT statements, PG badger. Sequential scans aren't always bad. But again, you may want  to delete indexes that have low usage and unnecessary indexes are a bad thing. When you're considering  an index type, consider how long it takes to build, consider how big it is, consider  the index update overhead, and the access speed. And also the operator flexibility. If you  start to look at full text search and JSON and arrays, there are some special operators  that only work and are only indexed by these special data types. And that is it, ladies  and gentlemen. I went six minutes over. Shame on me. But again, I wanted to open it up to  all the questions that you had. We had some really good ones, particularly in the beginning.  I know the part at the end where I start to talk about special operators, it's really  complicated. But I will, I try the best I can. Let me answer this question. Yes, sir?  Yeah.  So is there a way to see inside the index and see the matches? You'd have to dump the  index out and look at the internals of it. There's no way to look at the index directly,  which is a great question. So thank you very much. I will be here for questions. Sorry I  went over. Have a great lunch. Thank you.
Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_0_131.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_132_383.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_384_4955.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_4956_7523.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_7524_7703.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_7704_11003.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_11004_12527.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_12528_16235.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_16236_17087.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_17088_18263.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_18264_18563.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_18564_18647.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_18648_18755.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_18756_20207.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_20208_21203.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_21204_24431.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_24432_24479.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_24480_24527.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_24528_25847.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_25848_25895.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_25896_25967.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_25968_31943.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_31944_32087.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_32088_32207.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_32208_32411.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_32412_32999.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_33000_33059.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_33060_33155.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_33156_33479.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_33480_33551.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_33552_34103.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_34104_34547.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_34548_35027.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_35028_37811.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_37812_48203.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_48204_48491.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_48492_48563.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_48564_49139.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_49140_54863.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_54864_55991.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_55992_57311.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_57312_57707.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_57708_63119.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_63120_64607.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_64608_65015.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_65016_65411.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_65412_65807.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_65808_66803.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_66804_68087.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_68088_68135.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_68136_68519.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_68520_68783.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_68784_69539.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_69540_69851.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_69852_70439.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_70440_70523.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_70524_70667.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_70668_70727.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_70728_70787.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_70788_70991.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_70992_71939.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_71940_72839.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_72840_72959.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_72960_73007.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_73008_73151.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_73152_73199.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_73200_73343.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_73344_74267.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_74268_74663.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_74664_75827.png Bruce_Momjian__Flexible_Indexing_with_Postgres_--__esHnS6G33ak_75828_77326.png
Okay. There's probably enough energy in the room. We can just coast through this one. For those of you in the previous session. So anyway, I'm sure we'll get some feedback from that big discussion. What I am here to talk to you about today is not about what the previous session is about, but something completely different. As you know, Postgres has a very flexible object extension system and a very flexible data model, a way of storing a lot of very non-traditional data types like JSON and GIS and full-text search and stuff like that. And one of the core things behind all of that sort of creative non-traditional relational object storage stuff is indexing. And this talk is about exactly that topic. I think that indexing is sort of one of our unsung heroes of Postgres. You don't see it a lot. People don't talk about it very much. But without really, really powerful indexing, a lot of the non-traditional storage types that we support like JSON-B and full-text search and GIS would really not be possible. So this talk is about that topic. It's about indexing. I think you'll find it very interesting. I learned a little bit even in working on it. And frankly, the way that the Postgres documentation presents indexing is not ideal. It's a little hard to get your handle on. You end up sort of following what everyone else did. Oh, I need a specific type of index for that data type. Or I need a specific type of index for that data type. But what this talk tries to do is to actually explain why. Why do you need special indexing types? Why do you use one indexing type over the other? And also to give you one or two indexing types you may not have even heard before that are available in Postgres that are very powerful. So I think you're going to enjoy it. I have to give attribution here. A lot of the indexing that we're talking about here comes from the Russians, as we call them, Theodore, Alexander, and Oleg. Oleg is not here. Alexander and Theodore certainly are. If you look around, I don't think they're here, unfortunately, but are they? No? I don't see them. Anyway, Theodore normally has a vest. And I think Alexander was wearing red today, but he's kind of tall, sort of stately looking in a way. But young, so sort of a combination there. Oleg is not here. Jonathan Katz also is around. He's in New York or so. If you hear the voice, you'll know right away who that is. These presentations are actually on my website right here. So if you wish to download these slides right now, you can, or sometime in the future, there's probably 20 or so other slides, other presentations up there that you might find useful. So we have an ambitious agenda because indexing is a complex topic. First, we're going to talk about traditional indexing. This is going to be the easy part. This is sort of what you remember from all the other relational systems that you've worked on. But then we're going to talk about some of the ways that Postgres has taken traditional indexing and extended it, I think, in a very powerful way. This will probably be the easier of the parts because what we're doing is we're taking the traditional indexing type that you've seen in all the other relational systems and just adding new capabilities to it. And I'll show you some examples of that in items three and four and indeed in item five. Then when we get into item, I'm sorry, item four, and we get into item five, we start to talk about where the wheels come off, non-B tree indexing types. We'll talk about what those types are, give them names, explain a little bit about their structure. Then we're going to explain how they support indexing, particularly, and specific data types, and then finally give you a summary. There is another presentation that I'm not going to be giving at this conference called non-relational Postgres. So if you're curious about how Postgres supports a lot of the non-relational types, range types, I see some range types guys here, GIS and full text search and geographical stuff, that non-relational Postgres is sort of a good one to watch before this. If you're not familiar with a lot of the non-relational things that Postgres can do, so I'm not going to cover that too much. If you need a primer on non-relational Postgres from my website, great place to look. So any questions? Because I like to take questions as we go. Yes? Nope? Nope? Okay. So first, traditional indexing. Traditional indexing for relational systems is B tree. Great, very flexible, has high concurrency, fairly compact storage, although I know that somebody, another one of our Russian friends at Estasia is working on making B tree even better. So if you catch her, feel free to talk to her about that. But there are other, B tree is sort of the catch-all. And if you only have B tree, it is the only option for your relational system. So there's a lot of relational systems that really just kind of have B tree. Maybe they have hash, but they don't get into some of the craziness that Postgres does. And therefore they can't really support a lot of the indexing that we do. Because Postgres originally was designed as an extensible system, it's been very easy over the years to say, oh, I'm doing full-text search, I need a special indexing type for that. Oh, I'm doing GIS or 2D points, 2D geometry, I need a special. So the idea of being able to extend Postgres as new data types became necessary for storage is one of the sort of geniuses of Michael Stonebreaker and how that original research project was designed. And I'll try and cover that to a tiny extent. But again, B tree, great. Great for high concurrency. Great. The index is basically key and then some kind of row pointer and key and row pointer all the way down. Great for sort of single lookups, even range looksups. Order by, of course, makes a lot of sense for B tree. If you're familiar with merge joins, merge joins make use of these B tree operators because they present a single linear ordering of your results. I'll have you curious about merge joins. I do have a explaining the Postgres optimizer talk on my website that covers that. And also, Neslub with index scans, again, this is sort of the bread and butter of most relational systems. But what I'm going to be talking about today is the idea that as good as they are, they can be extended in some creative ways, even B tree, and then there are some even more cool types that I think you'll find really interesting. Okay. But I want more. Maybe I want an index, not a column, but an expression or a function. Some relational systems support that, some don't. Maybe I want roll control. Maybe I want small, lightweight indexes because B tree can be, you know, a significant portion of the size of the table. You might think, well, that's always going to be that way, but that's not actually always that way. You might want to index nonlinear data. Very hard to linearly represent a 2D space, right? I mean, my definition, 2D spaces are 2D. You might want to do something like closest match searches. This is kind of difficult to do in B tree. You may want to index a lot of duplicates. Now, B tree will index a lot of duplicates, not very efficiently. And you might want to do multi-valued fields, particularly something like a JSON, JSON B type. Again, you can see where B tree doesn't really play too well in this area. So let's just talk about the straightforward extending expression indexes. So extending B tree indexes, I'm sorry, in this case, I'm going to show you an example of, actually, let me ask you any questions. Okay. So let's talk about indexing an expression or a function call. Again, some databases support this. Some databases don't. If you have a query like, I want to look up somebody's name, but I don't want to specify the name in the case specifically. I want to specify just the name in all lower case, but I just want anything that has any match in case to match this record. You can do this query in any relational system, and it will return the right result. Okay. But what you, what the problem is that if you try and create an index on the column, it's not going to use that here. So one of the things I'm, one of the things that I continually talk about when I'm talking about indexing is that you can do a lot of non-relational storage with a lot of the other database systems. But if you can't index it, it's a toy, right? This is the classic case. You do a proof of concept. It runs great. You go to a production. It doesn't, the system just falls over because it needs that indexing to really make it function and perform at the scale that your enterprise needs. So one of the great things about Post Grass is that you can create something called an expression index, and that's either by placing a function call inside the created index command or literally a plus sign, a factorial, you know, a concatenation. You can do almost anything, any type of expression in there, and Post Grass will actually use it. So here's an example. I've created a thousand customers, and I basically created an index on their name. Now, this is the traditional index, just create name, and if I go and I say, give me customer 9999, the system automatically knows, oh, okay, let's just, you know, do an index scan, pull them up. That's a standard B3 operation, no problem. Okay? But if you try and do something like function call on that column, Post Grass, by default, if you just index the column, it's going to fall over. Okay? It's going to do a sequential scan. This is what I'm talking about. It's not going to scale for that kind of use case. But if you use an expression index and you now say, create an index on the lower of the function call of that, then when I actually do a lookup, it actually knows to do an index scan and to pull the records back. Okay? So a lot of cases, you may have lookups in your ware clauses that are not traditional lookups. They may rely on an expression. They may rely on concatenation. They may rely on a function call. And by creating an expression index, you can now get performant results from this kind of query. Okay? Again, user-mined functions, concatenation, math expressions. The functions that you use in an index have got to be immutable. There is a special immutable flag that has to be present on that particular function because you can't have the value that that function returns changing over time. Right? It's got to be a stable. Every time I put a two in, I get a four out. If you have something that relates to current timestamp or something like that, you start to get into trouble because that, the value that comes out at the time the row was added and the value that you may compute later, if you've got current timestamp in there, it would be potentially different. Okay? So just be aware that's the one that usually catches people up is that current timestamp shifting and it's not immutable function and therefore you're going to have trouble. So just be aware of that sort of restriction. And also you might need to do casting depending on how it works. Okay? Any questions about expression indexes? Okay. I know, you know, I will tell you I always start really kind of slow. By the time we get to the end, you'll be like, whoa, okay. But I always kind of ramp up as we're going. So let's go to the next one. This is partial indexes. This is a little more on the edge. You've always assumed when you create an index that every single row is indexed. But there is a value to being able to say, I only want to index some rows. You might think, I'm never going to want that. Well, don't make that decision right away. Okay? Sometimes, why index every row if you're only going to look up some of them? Like, why have the storage space? Okay? It's smaller if you just index as the one you want. The index is less deep. Okay? And more shallow, basically. There's not the insert update overhead of updating index for rows that you're never going to use. But you can still get to the rows. It's just that they aren't indexed. Okay? So here's an example of another table I'm going to add. I'm going to add a state column to my existing customer table I did over here. I'm going to update and add. I'm going to make all of the 900 and plus, so we're all like from 900 to 1,000, those people are all going to be in Arizona. Okay? So I'm just going to put Arizona for one tenth of my people. And now I'm going to create an expression index. I'm going to say, index all of the people in Arizona. All right? Maybe I have some tax law in Arizona. Maybe I live in Arizona. And I'm always looking at people who are local to me. Maybe I have it out for Arizona. I don't know. Whatever. Okay? Now if I go and I say, give me everyone in Pennsylvania, system runs fine. It's like, I know you didn't index Pennsylvania, but I can still give you the rows. I'm just going to automatically sequential scan that table. Okay? But I've asked for everyone in Arizona, system automatically does an index scan and says, oh, I can get you those Arizona people much faster than doing a sequential scan. I have an index that will just pull those off right away. Okay? And that's a really, really powerful optimization you can do. Again, reduces the overhead of maintaining that index, the storage size of the index, and obviously the depth of the index. Classic case from my experience, we used to have an accounting system. Oh, you have a question? Yes, sir. Please. Let's say the column is a boolean. And you say, index where, you know, is true. Totally. So, but I always assumed that all the ones that were in other case would all be in the same index slot as it were. Yeah. And so, would occupy one slot of the index anyway and that would be it. So, that's, you're, you've walked right into what I was about to say, which is great. Okay? We used to have an accounting system that I used to do consulting and it had a, it had a, you know, what was it? Invoice is zero flag, right? So, you'd have, I don't remember what it was called, but you'd have a flag that would indicate whether this index was closed, like whether it had activity or it was non-zero or it was zero. It was zero. It was really there just for historical reasons, right? And you were always running reports asking for the non-zero invoices, right? Because that was all of your work. But in the database that I was using in the 90s, there was no way to do that. So, you effectively had to index all of your rows. 99% in my legal application experience were zero, right? But I had to index all of them so I could pull out the non-zeros really quickly. And this is a classic case. If you create an index on a boolean on the whole table, it's going to index every row. It's going to have, and I'm going to go back up here because I hate to do this, but remember I said that the index is effectively key value, key value, key pointer, key pointer. So, you're going to have 99% of your index is false, pointer to false. False, pointer to false, right? The index does not make a distinction even though it knows 99% of those are indexed false. And frankly, probably the optimizer would never choose a 99%. It's only filtering out 1% of the rows, right? And it's never going to use an index for that. Frankly, indexes have to filter out almost 95% of the rows before they're going to be used in a lot of cases, okay? Not in this case, but the index system is not going to make that decision. It's not going to know what your future data layout is going to be. It's not going to know a lot of things. So, it's going to index all of them, right? And that's the classic case actually for me as boolean where you're kind of like, well, I don't really want to index all these zero invoices. I just really want the other ones. So, that's a great example. But the bottom line is, yeah, it's going to have a lot of falses in there. And that index is going to be huge. It's still going to get to the true ones really quickly because the index, the optimizer knows how selective a true is or a false, right? And it's going to use the index depending on that. But in terms of storage space, they're all there. That's a great, perfect question. Yes, sir? Yeah. I would, so I'll repeat the question. So, the question is, would you use four different indexes on four different unique state values? The bottom line is no. You'd create a single index on that. There's really the optimizer smart enough to know which ones are selective and which ones aren't, creating individual ones. I don't think gains anything. Because of the way B tree works, all of your states are going to be right next to each other and the index, the optimizer knows that. So, it's going to do that fine. The case where you would really want to use that is where you've got some really dominant state that you don't want to index, right? That's when it starts to make sense. And technically, so if 95% of your customers were in your home state or province, okay, you might want to index everyone who isn't in the province you're in. And technically, you can actually, I'm not going to cover this, but you can actually say, state is Arizona and state is not Pennsylvania and it'll actually use the is not Pennsylvania. You can create an index of is not in Pennsylvania and it'll actually use is not in Pennsylvania to find the Arizona people, okay? Because what I'm doing is by saying not in Pennsylvania, I'm excluding 95% of my rows, right? I'm creating a very small index on 5% of my customers. But now my where clause, I have to say, which doesn't seem to be logical, customer in equal state equals Pennsylvania and state not equal to Arizona, which sounds completely ridiculous because I've already said Pennsylvania, why would I say not Arizona? But I'm saying, or I would say in Arizona not in Pennsylvania, why would I say not in Pennsylvania only so I matched an index? Literally, the system is going to try and match the where clause with whatever literal you put in the preposition of the partial index. It's kind of tricky. Yeah. Yes. Totally. I would love to, if you can tell me, I can't remember some of the smarts is enough. Like when I say not Pennsylvania and equal Arizona, I thought it would figure that out. I can't remember if it figures it out. So maybe I need to go back and try some more testing. I could probably just take this example and run it for somebody here could do it, whatever. But I don't remember how smart it is or how literally you have to match this. Years ago, you had to literally match it. I think we've gotten smarter here, but I don't know how smart. So great question. I don't have an answer to it. Next question. Okay. So again, if I now do my check equals Arizona, it does a sequential scan. If I now, so I'm sorry, when I'm doing it here, I'm saying I'm creating an extra Arizona. If I look for everybody, I get a sequential scan because it can't use the index. But if I ask for Arizona, even if I ask for the customer name and Arizona, it still knows to use the index because the index is definitely restrictive. So I'm still looking for these customers, but only in that Arizona index. And of course, if I just ask for everyone in Arizona that works, I can even do, I can even create, let's see here. But anyway, so you kind of get the idea of how that will go. We have another way of doing index is called a bitmap index. It's used. It's called a bitmap index scan. It's not technically an index. It's automatically happens when you run queries. You've seen bitmap index scan right here, for example. It's particularly used when we expect an index to generate multiple matches on the same page. So if we expect the index to hit a bunch of matches, we'll use a bitmap index scan. It creates a bitmap in memory. It basically does either raw or block level granularity. And then we can visit the rows once just using our bitmap. And what's really great is you can take different bitmap scans, join them together using multiple indexes and kind of get this mega index, which is a combination of bunch of different indexes. Okay, again, this happens automatically. It's not something you're going to do, but be aware when you see a bitmap index scan, that is what it is doing. Okay. Now, that is the easy part. Okay, now we'll go to the hard part. The hard part is all the non-B tree indexing types, all of the non-traditional indexing types that Postgres supports. Why are they there? What do they do? And why do they really make Postgres's type system shine? Okay. This is like a big, I know it's like, whoa. The first one is kind of an interesting index type. We've had it for a couple of years. It's called BRIN. It stands for Block Range Indexing. It basically creates tiny indexes for large tables. So if you've ever wanted to create an index on every single column in a table, this is your baby. All right. The index are very small. Index is typically something like.003% of the size of the table. Right? I mean, really small. So it basically stores minimum and maximum values over a range of blocks, in this case, one megabyte. So for each one megabyte piece, it's just going to store a minimum max. And then it's going to skip or scan each one meg chunk. Now you can change the sizes, but default, you've got like a one meg range there. Skip to the large sections of the table, thinking of a 300 gigabyte table. This BRIN index is just great. You're breaking the table up into what, you know, 300,000 individual pieces, and then you're just able to kind of skip or scan each one and beg a bite chunk. It's really great for naturally ordered tables, things like indexing, insert-only tables, chronologically ordered. If you've loaded it to data in a sequential order, that's really good. Indexes are very inexpensive to update, you know, very small costs. They are slower than B-Tree. But again, if you try and B-Tree index every column in your table, your indexes are going to be far larger than your table itself. And a lot of times you don't know what you need to index. This is a great sort of fallback for that case. Okay? Second index type, GIN. We've had this for years. Alexander Klokoff has worked very hard on this in terms of improving it. It's really great for indexing values that have many keys, like text documents, JSON, multidimensional arrays. Okay? Also great if you have a lot of duplicates. Remember I told this gentleman about the, like, the falls and every, like, you know, 99% is false. Well, in this case, you're going to have one falls and a whole bunch of rows, which is a lot more compact than the traditional B-Tree where every single row has to have a key in the B-Tree index. Okay? Yeah? Absolutely. In fact, if you look at the Postgres to-do list, one of the things that is listed as not wanted is Bitmap Index. And the reason the to-do list says we don't want it is, effectively, we are unclear where a Bitmap Index would win over this indexing type. Because the problem with Bitmap Index, it's, Bitmap Index is great if you've got a table that never changes. But growing a Bitmap is fairly difficult to do. So what Jim is sort of allowing you to do is to have the benefits of the Bitmap Index without the overhead and the problems of growing and shrinking that index as the table changes. So we don't know if we're ever going to have a Bitmap Index because we don't know how we'd ever be, effectively, your great point this exact index type. So if you're familiar with Bitmap Indexes from other, not Bitmap Index Scans, which is a different case, Bitmap Indexes, this is a great replacement for that in some ways better than a Bitmap Index. So that's a really good point. Other questions? Yes? Could you put a range of the medians that's coming in at the end? Well, I'll just give you some just off the wall. So let's just think of a data type. Let's think of full text search. So I'm going to have tons of me, the word me, all over that index. So do I want every me that's in the index to have a single, every me that's in the table is going to, in the text fields, even though I have multiple me's, I'm going to have an entry in the index that says me and then the value. What Jim is going to do is he's going to give me one me for no matter how many me's across any column, any field, any row in that table, and this is going to have all the matches. So it basically takes the B tree we're going to have due because you just roll them up. So frankly, I don't even know how you do full text search with B tree because you'd have to have multiple matching rows for multiple words. It wouldn't even work, right? Because it's like saying, you know, typical B tree, when you create a B tree, it's like, okay, when I index that column, you know, that column has an indexed value of five and that one has a, in this case, that one column because it's a full text search row or a JSON row, it may have a five and a seven and a 12 and, you know, a bunch of row, values in that single field. So there's no even way to think of how we do this in B tree. But certainly any case where you're looking at a significant percentage of the table, even like three or five percent of the table has the same value, you'd probably be doing this. In fact, there is a contrib module called B tree gin, right? And it effectively takes the B tree sort of operators and makes a gin index out of it. So if you want to, right? So that's actually, I can't tell you when that's going to win, but I know I see a lot of activity on it. Like we get bug fixes once in a while. It's not there. People are using it. And again, when you have a lot of duplicates in B tree, Anastasia, I want to say Lumikova, I'm not saying her last name, right? She's kind of tall and like, I know what you were yesterday. I didn't see her today. So if you see her around, you can ask her because she's done a lot of research on duplicates on B tree. So when I was in Russia a couple of years ago, she did a talk on, she has a whole patch that's designed to take B tree and make it operate more efficiently. But the problem is that's gone now compete against B tree gin, which is this. So now you've got B tree, which is not good for duplicates. You've got gin, which is great for duplicates. You've got B tree gin, which is in the middle. And then she's trying to say whether we could take B tree and kind of move it closer to B tree gin, you know what I'm saying? So the kind of, the kind of, you'd think that there's only a couple of ways to index something, but there's a whole spectrum of efficiencies that you can do when you've got duplicates and when you've got multi-valued matches in a single field or a single field. Yeah. Great question. Yes. Okay. So optimize for multiple batches. Key is stored only once. The index is key and then many row pointers. Remember B tree was key, row pointer, key, row pointer. This is key, many row pointers. If it was visually, I'll show you a visual example later. Indexes are batched. Therefore, one of the problems we always have with bitmap indexes is updates. Very expensive because it just, so this, the gin code has like a, like a queue. So when you do a change on the index, it kind of goes into the queue. And then when anyone looks up the index, they check the queue first and then they go to the main index. So there's always this, and then you batch those updates because when we originally implemented gin, I think this was Alexander, a little before Alexander, maybe it was Theodore or Futter, the updates were very slow. So over time, we were able to kind of batch them and that really improved the insert update performance of gin indexes now where they perform really well. And in fact, even as recently as 9.4, Alexander added compression, very powerful compression to this gin row pointer list. So you can imagine for the word me or the word thank you, a thank or son, there may be, you know, thousands of row pointers. And he in 9.4 is able to have a compression algorithm across there and optimize it for multi-key filtering. I'm not going to go into it. I did understand it at one point. But again, this is really, really high-powered stuff, which really takes postgres, I think, for these multivalued and non-relational storages into a really amazing direction. A related index is called GIST. We've had this a little longer than gin. It's called generalize search tree. It's a lot less specific, hence the name generalize. It's really designed for things where we can't use B tree, we can't use gin, we can't use brin. So things like geometric types, range types, h store, trigrams, these are nearest neighbor. So again, it's kind of a catch-all indexing method for a whole bunch of things. And I'll show you some specific examples later, what that does. SPGIST, I think this is Futter and Alexander worked on this. This is something called space partitioned generalized search tree. So it allows the key to be split up and the parts are indexed hierarchically into partitions. So I'm going to show you a graph of this later. But effectively the idea is that you take a URL or an email address and you break it up into parts and then everyone who has the same common first part goes in the same place in the index. You don't see this very much. Usually when you're indexing something, you're indexing a discrete thing. What space partitioned GIST is, is it's assuming it can take that thing you're indexing and look at prefixes and slice it up into prefix parts and then put everybody, for example, who's at a Yahoo address in the same place and whatever. This is something I think is pretty cool. It's not traditionally used very much, but there are special use cases, particularly for very long indexed values. Integers doesn't make any sense, right? Words probably doesn't make any sense. But when you start to think about a structure, think of a URL, right? It's kind of how directories work, the idea of taking a path name and breaking it up into pieces and then having this piece is kind of all together. So everyone in bin is going to be, even though you're indexing a long path, everyone who has a bin to begin with is going to go in the same part of the index, right? Really great for prefix searches, obviously. Yeah. You could. You'd have to make sure that the last name is the first part of the indexed search and then maybe concatenate it together. So I would almost take, if you've got first and last name in a separate field, you can actually create an index that concatenate like that, use an expression index and concatenate it together and then put the word at the front and then the space and then, and that would actually kind of start to do that type of thing. Yeah. Phone numbers is a classic, right? Because you've got the area, country code and then area code, right? Yeah. Yeah. Is it one slice or can you put country, use country code for one grouping and then within that area code? The cool thing is you don't do anything. You just index, you just take, create an index and it figures out how much, what's a good break point for these partition boundaries. Yeah. Yeah. And then you just assign it table spaces, basically. No, you just create an index on the column and you're done. That's it. That's it. Yeah. So if you see footer, he's the guy who worked on this. He's been around for a couple of years, but it doesn't seem to get a lot of traction. Partially because people read the docs and they're like, why would I use this, right? And they're like, well, yeah, there are some cool reasons to use it. All right. But again, it isn't, it isn't obvious. Hash indexes, we have improved those in Postgres 10. I don't have to embarrassingly sheep away and say boo, like I did, I used to have a boo slide for this. So again, hash indexes, very good for quality, doesn't have any not a quality look up, no range look ups, but again, crash safe, replicated. The B tree is so fast, I'm not sure when hashes are when there are some cases, hash indexes are typically smaller, particularly for long keys. So if you're indexing, the classic case I had was indexing something like a large object. You might say, well, why would you index a large object? If you're indexing an encrypted value, which is effectively stored as a large object in Postgres, those can be pretty long, like 64 bytes or whatever. And you create a hash index, now you're not indexing the whole thing, you're just indexing like the hash of it. And that's a great one. Jimmy, you had a point. You were great for UUIDs. UUIDs, thank you. Because it's automatically shrinking it down for you. It's still going to check to make sure for hash collisions. So you don't have to worry about it. It's still going to check the raw value. But obviously that hash is filtering very well. And it's going to check the raw value. Great. Yeah, UUID. Any kind of long text string or anything, the idea is to kind of auto-hash it, auto-shrink it down. That's really, I think, where the big win is for hash indexes. Yeah. Would it be UUIDs stored as text or as a native UUID? Either one, there's a performance that it overbeats UUIDs. Cool. Yeah. Thank you. Great point. Thank you. In other databases, you can use it for social security. Well, the problem is this is just the indexing portion. So you still have the raw social security in the table. Yeah. Sometimes if you're an insurance company, you have to have the raw social. The point is that you never do a range search on social... Absolutely true. And then... Absolutely true. Yeah. Yeah. Now, I have to ask a question because you've asked two questions. Did I tell you last year that you should have been like a radio announcer or did I talk to you about that already? I was. I knew it. That's great because as soon as you asked the question yesterday, I'm like, wow, who's that talking? This is kind of funny. Great. Good for you. Thank you. Okay. I'm not making this up. So effectively, this is a query from Postgres. These index types are literally stored in the database. I talked about the extensibility of Postgres. These are literally stored inside the database. Okay. All right. So let's get a summary. Where are we? B-treat. Ideal for indexing unique values. Nobody's going to beat that. Okay? Bryn. Ideal for indexing many columns. Small indexes. Again, these slides are online, so feel free to look them up whenever you want. Okay? They're on my website. I didn't even mention I work for Enterprise DB, but anyway, it's been 12 years. I guess I don't even say it anymore. Genie index is ideal for many duplicates, space, SP gist. Ideal for indexes whose keys have many duplicate prefixes. That's really the concept I want to get across. Space partition gist, common prefixes of long key values. Gist is just everything else. It's just the catch all when everything falls through those cracks. Okay? All right. Any questions? Yes. Yeah. Right. Right. So why don't we consider hash for primary keys? Part of the reason is because a primary key by definition is unique. We could use a hash for that, but historically, because post-grass, the hash indexes weren't crash safe. We just never were going to do that. Now that we're crash safe in 10, we potentially could do that. If somebody came to us and said, you know, I want the option to do it, and here's the benefit in speed I get if I could do it, we would definitely consider that. There's nothing. There are some internal reasons why we really like B-treat, because when we're locking a row for foreign key check, we're going to want to lock that specific value. And the problem with the hash is you can have hash collisions, and we can't identify as quickly from the index exactly which index matches my row. So if you're two people are inserting at the same time, this is more internals, we're going to lock that index so somebody else doesn't come along and insert the same key value. And if we, to do that for hash index, it would be kind of dicey because of the conflicts, potential hash conflicts within the index. That's not a user-visible thing, because we're always going to check the heat, but we might not want to do that. I don't know, but it's possible. That's a great point. So other databases do support this, so maybe we should look at this. Now that we have unembarrassing hash indexes, I'm going to use that term, it's definitely something we could look at. Yeah. Great. Yeah. In fact, Grant, who was speaking before, has a great talk about that hot problem with, I think he's done a lightning talk on it, and I think he hasn't talked about it. So if you're curious about that, what he found was that when he indexed a hash, he got so much churn in the index because he wasn't hitting the same rows on insert, he was getting all over the place that he didn't actually, it didn't actually work well. That was kind of interesting because that was a time series case. So anyway, I thought it was interesting. Okay, so let's take a look. Data type support. So again, I'm querying the system tables. Not every data type supports every indexing method. Okay, so you can't, you can probably use Btree on almost anything, okay, but you probably don't want to do that because if you Btree index something like JSON B, it's going to index like the whole thing, the whole document, right? That's probably not what you want to do. You want it to break it up into pieces and index, there's a whole bunch of operators that are possible only when you, only, they're indexable only when you create a non-Btree index on some of these types. So just because Btree supports it doesn't mean that's where you should be going, right? So you, unfortunately, you have to understand a little bit of this, particularly like the range types and stuff. You just don't want to use Btree on this unless you're looking for absolute equality of the whole field. That's really where Btree wants to be, right? No surprise. If we look at Brinn, again, this is that tiny index where we can kind of slice things up, okay, and you can see that it's effectively slicing it up very well. So the whole bunch of different data types are going to be sliced up with Brinn, okay? Gin, again, very, very small support because you don't have a lot of data types with a lot of duplicates, right? What are they? Well, TS vector, that's full text search, okay? No surprise there. JSON B, yep, that makes sense. A lot of duplicates there, okay? JSON B, this one, and an arrays, a lot of duplicates. That's it. So don't, you know, you don't, don't bet the form on gin because it's only a couple, a couple data types that really benefit from this. Jist, again, I said the catch-all for everyone else, things like box, circle, all the 2D stuff, we can do Jist on JSON B. Maybe not, I don't, I may not recommend it, but we used to recommend it when gin was slow. Now that gin's fast, we may not need this anymore. But again, it's there. Point, polygon, again, 2D stuff, range types is the go-to for Jist. I'm not going to get any range types, my other talk does talk about that. And full text search, again, you can also use Jist, probably want to use gin, now that gin's so much faster, in fact, I've been responsible for updating the documentation to kind of talk about that, okay? SP Jist, this is that prefix thing. Range types, text stops, this is the one you probably were thinking of, where you've got a prefix and you're going to slice it up and it does it automatically for you. Range types, again, I'm not sure too much. These I'm going to talk about later, yes? The email address might be a case where, at first it appears this is good, but since your repeated pieces are... At the end, yeah, you'd almost have to flip the email address around to make it useful, yeah. And almost, yeah, it's kind of an unfortunate way that we do... Yeah. But you could do that, but again, it'd be kind of awkward, yeah, I agree. Okay, let's go... Let's look at some examples. So this is B-tree, standard structure. Everyone knows that one. So, Bryn, here's an example. I'm going to create, I think, 10 million rows. I'll create a B-tree index, I'll create a Bryn index, and you can take a look, that's my B-tree size of my index, that's my Bryn size of my index. Okay? Just dramatically different. Here's full text search. If I have this text here and this text here, this is my full text search, it's broken up into words. What's interesting is the index has individual entries for some of the words and has multi-row entries for some of the other words. That's what I'm trying to get at, this... The way the gene works, it's effectively going to have one key and then a bunch of row matches. Okay? Obviously, very similar. In their initial rays, similar kind of case. JSON, here we've got key value, key value. Again, it breaks it up that way. But if you look at the index, again, key, multiple values. Key, multiple values, key, multiple values. Okay? Pretty straightforward. Okay? Let's see here. Text, JSONB, path ops, this is a little different. This is a different way of indexing with gene on JSON. It actually hashes the whole path and therefore, you effectively... If we're going to look at very deep hierarchies, you can look up very deep hierarchies very efficiently with path ops. Because in this case, it's going to break up every key separately and it's got to kind of put them together. Whereas when you do path ops, it's kind of kind of... Hold on, it's starting here. Yeah. When you do path ops, it's effectively going to hash them and kind of pull them together. So, again, supports loosely a couple values, also tightly coupled values like that. Okay? Now, unfortunately, I am out of time. However, we do have an hour lunch. So, I'm thinking I'll go an extra five minutes. Is that good with everybody? Everyone, you're okay? You might be at the end of the line, though. Like, is that okay? Like the food line. We're good? Okay. So, just to talk about nonlinear indexing a little bit, again, think of this as a B tree. You're doing B tree. Everything's linear. Very easy to understand. How do you index this with B tree? Right? You don't do this. That's not very helpful. Right? Because you're not distinguishing the why, value, and any of these things. The real way to do it is with bounding boxes. And if you want to hear bounding boxes over and over again, talk to my Russian friends. They used to talk about it forever. Bounding box is effectively an index that's a 2D box. And you're indexing by making smaller and smaller boxes within your larger index. Okay? This is very, not only would you use it for 2D points, but think of range types, which are kind of 2D ranges, right? You've got a range in the box gets smaller. Same kind of thing. They go levels. They go smaller and smaller. Okay? And again, box, circle, point, polygon, these are all used by PostJS. Feel free to talk to Paul Ramsey about that. He is here at the conference. But again, JIST is really good for that. So again, range is smaller, smaller, smaller boxes is how you do it. This is the SP JIST. Remember we talked about the prefix one. What we're effectively doing is we've got a prefix. Think of a URL. I've got all the HTTPs in one part of the index, all the FTPs in another. Then we've got the domain names and we broke those up. And then underneath those domain names we have, you know, smaller and smaller boxes. Okay? So we're basically just getting smaller and smaller. But it's automatically slicing this long string up into pieces for me. And that's really great. So there is these other ones. I talked to Theodore about the details. They're all kind of cool. So extensions. We have a bunch of extensions. Btree, JIN. I talked about, for this gentleman, it's a JIN implementation of Btree for lots of duplicates. Btree, JIST for the same, cube, HSTOR, again, a lot of indexing support for those types. So in summary, how would you figure out when to create indexes? PGSTAT user table sequential scan would indicate maybe I need an index there. You can use explain, PGSTAT statements, PG badger. Sequential scans aren't always bad. But again, you may want to delete indexes that have low usage and unnecessary indexes are a bad thing. When you're considering an index type, consider how long it takes to build, consider how big it is, consider the index update overhead, and the access speed. And also the operator flexibility. If you start to look at full text search and JSON and arrays, there are some special operators that only work and are only indexed by these special data types. And that is it, ladies and gentlemen. I went six minutes over. Shame on me. But again, I wanted to open it up to all the questions that you had. We had some really good ones, particularly in the beginning. I know the part at the end where I start to talk about special operators, it's really complicated. But I will, I try the best I can. Let me answer this question. Yes, sir? Yeah. So is there a way to see inside the index and see the matches? You'd have to dump the index out and look at the internals of it. There's no way to look at the index directly, which is a great question. So thank you very much. I will be here for questions. Sorry I went over. Have a great lunch. Thank you.
going to talk about traditional indexing. This is see some range types guys here, GIS and full text for one tenth of my people. And now I'm going to example. It's particularly used when we expect an indexing values that have many keys, like text performance of gin indexes now where they perform index types are literally stored in the database. I talked about the extensibility of Postgres. Ideal for indexing many columns. Small indexes. ideal for many duplicates, space, SP gist. Ideal unembarrassing hash indexes, I'm going to use indexes are a bad thing. When you're considering