Data-Oriented Django Drei

Speaker 1: Friends, Pythonistas and Django Nuts, this is Data Oriented Django 3. I presented Data Oriented Django 1 in uh Porto. Data oriented Django D last year in View and now this is Dry. That's German for three. So here we go This is a T3 nano server. That's the minimum spec server on AWS and it comes with a 5 gigabit per second network capacity. So the tiniest Punia server can still do that This is a web page. It's about a megabyte, let's say. That's a very big web page actually in terms of just HTML. But let's let's say that

Speaker 1: So if we divide out the size by the speed we can transfer it out of the server, we get 1. 7 milliseconds. That's a very short amount of time. Why then is 100 milliseconds considered a great and amazing server response time? Where does all the time go? In data-oriented Django, I presented this general diagram of the flow of data in kind of the average Django system You might have other data stores, you might have other layers between Django and the browser. But in general, this is the flow of data Today we're focusing just on what's happening inside the server between Django and your database or other data stores. But we will be focusing on relational databases. And we're going to try and determine where that time goes

Speaker 1: So what we can do is we can measure. There are lots of tools out there in this category of application performance monitoring, which is measuring your production system to find out what it's doing with the with the time it's spending rendering your web pages. So shout-outs to some top picks here would be Sentry or Scout APM or the venerable Django debug toolbar which you can get running in your production system for say admin users. If you run one of these tools, you'll probably find something like this. Very rough, very average breakdown from my experience. But about 20% of the time is in your view codes, 20% of the time in the template rendering, 60% in the database. If your project, if you have a slow view, generally more time will be spent in the database and like the slice of that pie

Speaker 1: will just go up and up and up. So it behooves us to look at what's happening inside the database. Again, another rule of thumb here would be that 95% of the resource consumption, the time spent in databases, is on reads and 5% is on rates. So we gotta optimize the reads. That's like most of the time and most Django projects. So let's take an average Django model representing a tank engine from the Isle of Sodo. It has two text fields. We're keeping this pretty simple. If we make this in a database, we're going to end up with three columns that we can see. Django is adding an ID field behind the scenes, as Tim was just telling us all about.

Speaker 1: And we'll have our two text columns. But actually if we look inside what the database is doing, there's going to be another hidden column called the row ID. And this also links back to what Tim was talking about with dead tuples as Postgres calls them, which are basically old versions of rows So the database actually keeps multiple copies of versions of rows. Every time you update, it might create a new copy. So it has its own ID for your rows. And that's generally some kind of offset into the table data structure. Let's take a query set over that table now. Django will convert this to SQL, something like this, and then we can see what the database will do. We've got a matched column here now representing the query results. And generally a database would do this.

Speaker 1: You just table scan or sequentially scan through. Did that match? No. Did that match? No. That one matched. There's the row where the name is Kana and we found it. That's the algorithm known as a sequential scan. It's also called a table scan when it's running across a whole table, but sometimes it will run on a subset of data. We have this thing called big O notation, which is a kind of mathematical description of the dominating factor of the runtime. Here it would be O of n. n is the number of items, so the runtime will be linear with the number of items. This can be quite fast for small values of n. Uh CPUs are very good at fetching data in batches, so once you've got a batch of data, scanning through it can be quite quick. But as soon as we have any kind of medium size of N, something that won't fit into your CPU, it becomes slow

Speaker 1: and almost intendable. Just to really drive that point home, here's a table. If you have a number of rows and then there's the approximate number of operations, this ON. It just goes up and up and up. So uh 1,000 row table is going to take a thousand operations to check through a million row table, a million operations. We really need to improve on this if we want to have systems that work in any reasonable amount of time. This is where we find out about the relational model being a leaky abstraction. The promise is that you describe your data to the database and then the database handles storing that. You told it, you know, the column types, but that's it. You don't need to think about where it goes on disk, which files, we send a query you get back the data you asked for.

Speaker 1: The reality though is that the performance would be absolutely horrendous in that model without indexes. So indexes are what make the world go round. They're probably the most important data structure to understand. for performance in your apps. So what is an index? It's like an index in a book. That's where the term comes from. So if you have a flip to the back of a book it will tell you where terms are located on pages inside the content of the book. So it's uh very similar in fact to a Python dictionary. where we're mapping from some value to the places it can be found. In the case of a table, these will be row IDs. So if we could build an index in Python, we might do it like this. The database is using

Speaker 1: C-level code and writing it out in other data structures, but it looked very similar like this. So to add an index over in Django, we open up the meta class indexes attribute and we can declare models. index and name a field that gets indexed. This will appear in your migration file with an add index operation. And then that will issue SQL, something like this. Where Django tells the database, hey, create this index. So similar to when we define our tables, we don't need to specify exactly all the data structures and stuff. We just say, give me this. So it's still quite powerful. But what will the database actually produce? It will produce a B

Speaker 1: tree index or B plus tree in most cases for all of the backends Django supports. I think it's called a B plus tree. The B tree is a data structure that's a bit like a binary tree, but the nodes are wider, and it empowers the right kind of searches that we want to do on our data. So for example here I've got a table with six rows. There's a root at the top with any and conner, and those values point down. through levels of the tree to the bottom, and the bottom layer stores from a value to which row ID we can find that value at. The values in each of the uh non-leaf nodes, the nodes above the bottom layer, they are kind of

Speaker 1: greater than or equal to constraints. So we're saying Everything with a value of any or greater you can find here. Everything with a value of con or greater you can find here. So the algorithm that we use is actually a sequential scan on each of these layers, which we can demonstrate now. So say we go back to that SQL, we go to our table, we could start at the top of the tree, and we scan along. the database will find Kana as the first value that matches the constraint. So it's the it's the lowest value that uh will f we can uh page down into the next level. We follow that to the next level of the tree and we again scan through there until we find a value

Speaker 1: that would let us go to the next level. And then we get to the bottom level and we can see that the data for the row with value Kana is over at the row ID 20. And at that point the database can jump over to the row the table data structure and pick out just that one row from its ID, its position in the table. So how does this algorithm perform? It gives us a log n performance, a logarithm of n. And that scales way better. It's fast even for very, very large values of n. Its table here represents how many operations we'd be doing for a given number of rows So for a thousand rows we'd just be seeing about seven operations for a million rows 13. 8

Speaker 1: Performance would be even better in a typical database due to two reasons. First, the pages are way wider than I showed. I showed a page of two values. Normally they're about a hundred. So the database can scan 100, pick down one layer, it's now operating on only 1% of the data. Again, it can do that operation, it's operating on 1% of 1%. It can very quickly narrow down. And the other benefit is that the top parts of the tree will definitely be cached in memory because they keep being used. So you can probably knock off a few of these operation counts for the speed that you can jump to you know the right part of the index that may then be needed to load it from disk We can also use an index to answer things like range scans. So that's when we're using uh Django

Speaker 1: syntax greater than or equal to a value. That will give you the syntax with the greater than or equal to operator. That will operate similarly going down the table till we find the matching value. But then here's where the plus in B tree comes, these side links between nodes. Now the database can just jump over those side links to the other leaf nodes that match the condition until it finds a non-match. So it doesn't need to go back up the tree and down again. It can go kind of sideways along the bottom layer. There are a lot of options we get with indexes. So what the most basic extra extension would be to index on multiple columns. For example, here we can index on two uh fields in Django, columns in the database, name and color.

Speaker 1: That's gonna look like an index of tuples to row IDs in Python. So um we'd have Values from two columns combined into a tuple as a kind of key, and then we kind of look up the row IDs that match that key. And that would end up looking Something like this. Um it gets very big very quickly, so the right hand side of this tree is missing. Um but I hope it gives you an idea. We can also index on expressions. So we're not indexing the values, we're asking the database to transform them before putting them in the index. This will use a function that's um deterministic, so it's repeatable, something like the lowercase function on strings. And that will speed up when you're using that same expression in your search.

Speaker 1: So in Django, we can write an annotate to add that expression and then filter on the annotation. That will send you know lower of that name down to the database in SQL and the database will match that against the index and say, hey, I have already indexed that function on that column, so it can use that index Very useful for things like making email addresses unique based on their lowercase value. We can also index just some data. in our index. We provide a condition, which in Django we can do with a models. q object, which is like the filter call, and say only for rows that match this condition, put them in this index. That will speed up queries where that condition is used, and it will not speed up queries where that condition isn't used because there isn't an index.

Speaker 1: So if we were filtering for purple engines only, then by the name, we can use this index. This is quite useful for things like I have some data that goes through a state and it reaches an archived state. And once it's in the archived state We don't need to provide a search on it anymore. We can skip archiving that 80% or we can skip indexing of that 80% or so of our archived data. Another use case is avoiding indexing null values. So if you have a foreign key that can be null, Postgres and other databases will index it. Even for the null values, so your index is filled up with, you know, oh we have you know 50% of the rows are null and they're pointing to nowhere. Well you can drop those from the index and save yourself some space.

Speaker 1: Another option, told you there's quite a lot, it's uh inclusion indexes. So this is where we take the index on some field and then where you tell the database to add other fields into that index. They aren't used in the um The sorting of the data in the index, they are there for selection. They're kind of like next to the row ID in the in the kind of value part. And this will speed up queries that only use the index fields and the included columns. It's a definitely much more targeted optimization, but it can definitely speed things up when you're using Django 's only to select a limited number of fields. or perhaps some kinds of aggregation. We also have alternative data structures.

Speaker 1: These have the same log n performance, but they can be smaller for certain kinds of data or enable certain kinds of lookups that we couldn't normally do. Here's like a quick run-through of some of them that are in Postgres. They're all kinds of uh cases, and I don't have time to dive into them. You probably know when you want some of these, like for spatial data or full text search, others are quite uh dependent on your use case. I recommend you do read uh the Django Contra Postgres Indexes documentation. These are all the types that are supported inside of Django from Postgres. And all these options I've just discussed, you can combine them all at will.

Speaker 1: You can get a partial inclusion, multi-column, expression, bloom index if you need. How do you know you need it? That's a big question. We're gonna discuss shortly. There are some default indexes. So these aren't done by Django. These are done by databases, and Django just relies on them and doesn't touch them. So whenever you create a primary key on a table, which you always need, that has to be indexed. Databases know that you're probably going to look things up by primary key, and it's not going to table scan every time. So it's enforced by relational databases that you need that primary key indexed. Additionally, whenever you add a foreign key, that will also have an index. That's because uh databases want to enforce integrity.

Speaker 1: So if you're deleting a row from the targeted table, they want to be able to look up quickly if there's anything pointing at it from the source table where the foreign key exists, hence the index. And additionally, unique constraints. Again, the database does not want to have to scan the whole data to determine if you've got a unique set of data here or not. And so it is implemented as an index. One quite interesting thing you can do is replace a default index. So you can uh as long as the index you provide, like covers the use case that the database has, then you can adjust it as you wish. So for example, you can disable the default index for a foreign key here. And then create your own for index on that same field.

Speaker 1: But perhaps you'd use the inclusion setting to add an extra field so that operations that use that foreign key and also that other field could be sped up. I think the main thing to remember about why this is a hard problem is that indexes are not free. They are extra storage. They're a second data structure alongside the table. and they add overhead to rights. Every time you're changing one of the values in an index, those pages need shuffling around. They might need like splitting or combining and like the tree needs to be kept balanced in order to be fast. So it can be quite uh complicated for a database to update and index. Um and that's why we cannot index all the things. Some databases have tried, I think Amazon's SimpleDB.

Speaker 1: Did index every column you ever added to it and it quickly did not work for any amount of data. So that is why we have the question, which indexes should we add? This is really a whole system optimization problem. It's not just about one table and one column. We need to know How are we going to filter that column? Is it used in any joins? Is there any way of optimizing to combine two indexes by having a multicolumn one? Is it better to do a function-based index? That makes it much more of an art than a science. But thankfully as an art you can start with some common sense There are two approaches from the front, from the back.

Speaker 1: Up front, we can design the indexes when we're writing the model, the tables, and the queries. And we can also go from the back. Once things are not working in production, we start debugging our slow, our resource-consuming queries and figure out what indexes might help with that. And I I say resource consuming because slow might not be the only thing you're concerned about. You might have a very fast lookup, but if it's 80% of what your database is doing, it can make sense to optimize it even further. So when we design, we've got to ask ourselves these kind of questions when we're building the model, when we're reviewing code. Like I know we'll be filtering by the name field a lot, so let's index it. Or archive messages won't support

Speaker 1: searching, so they can be excluded from that index using the inclusion condition I discussed. When it comes to debugging, it's the other way around, and we're looking at things like these are the slowest queries. Let's see if any indexes could help them. And that index is never used. Can we remove it? That one's particularly useful if you have the right monitoring on your database. Most of them are tracking the number of uses of an index. If you see that's never going up. It means that it's not finding any queries to optimize with that index. So you can drop it, save yourself the storage, the right overhead. Here I'd like to call out one tool in particular, which might be useful for you Postgres users, which I think is most Django users. It's called PG Mustard.

Speaker 1: Here's how we can use it within Django. So we get a query set and then we tack on this explain method. Explain has a lot of options for Postgres at least. And these are the set of options they recommend you you call it with. You say give me the JSON format and then you just pass through these flags that tell it to gather more and more data. So the this is getting the maximum data about how this query runs out of your database. That will give you some giant JSON blob that's like way too big to put on a slide. But thankfully PG Mustard understands it. So we go paste it into this tool. And through a number of tuned heuristics from its uh Postgres expert creators, it will give us some top tips. And typically

Speaker 1: it will call out uh something like, here is the best place to add an index to speed up this query. It's uh free for like five or ten uses, I think, and then it's got a reasonable price tag after that. It's um yeah, pretty cool. Here it's uh an example screenshot I got from it's showing that I've got a query that does a sequential scan or sex scan, if you can read that, over an auth user table in Django, and it's saying the Top twip, five stars, most optimization is to add an index. And then there's some other tips about uh cache performance which uh could be investigated after indexes. So for you to learn a bit more about indexes and go in depth, I've got some recommendations here

Speaker 1: of resources. The first one, a Planet Scale B tree post, is an interactive tool that really lets you see how data gets added and removed from a B tree and understand the searching too. The second one, Use the Index Look, is a great uh book about using uh indexes. It covers uh general SQL advice. It's kind of targeted to Oracle, but it it diverges into like if you're on Postgres, do this, and that's cool. If you search for Django PG Mustard, you'll find my blog post on using PG Mustard, the technique I just showed in a bit more detail. And then I'd always recommend you go read the docs. So they're Django documentational indexes or the Postgres docs or perhaps your database of choice And with that, I'd like to say thank you. My slides are up here.

Speaker 1: That's my website, adamj. eu, and these are my four books with the next one work in progress. Thank you.

Speaker 2: Thank you very much. Thank you for a great talk. Do you have any insights in the overhead costs of rights for indexes?

Speaker 1: The question is, do I have any insights into the overhead costs? So one way to think about it is i if your table you know has rows that are 10 columns wide and we're writing into an index like two columns, like one column and the row ID, then it could be like 20%-ish costs. It's faster to write into the main table data structure because that's typically just appending a row, whereas with the index we have to maintain the data structure B tree, for example, requires shifting around. Those other exotic indexes might require even more maintenance. But yeah, it it depends, but m it's always gonna be a fraction of the main table, I think. Yeah.

Speaker 2: Thank you very much

Speaker 3: Thanks Adam. When you have a multi-column index, give an example with the color and the name, how do you decide on which in the which column to include first? Because At least last I understood years ago it made a difference to which one came first, but is this still this case or did that change?

Speaker 1: Right, yes, uh I didn't touch on it in the talk. Uh when you when the database uses a multicolumn index, is b basically searching on the first column first and then on the second. So a multi-column index on columns A and B can speed up queries on A or speed up queries on A and B, but it cannot speed up queries on B. So you want to put your like most searched column of the pair first. So for example, you might have a foreign key first because that's nearly always searched and then some auxiliary data.

Speaker 4: Since index usage highly depends on the data you have, on whether it's even used or not, um it makes sense to test near to production to actually see if the data um uh if the index is used. Do you have any recommendations on how to get um production data into a usable test system probably with some anonymization or so or how to handle that data there.

Speaker 1: Um yes so the question is like can we get usable data from production into test? I think in general No, it's better to test in production with this kind of thing. If you say take a SQL dump of your whole database, you load it into your test system and then you start firing similar queries at it. It will still look different. The data arranged on disk will look different. Your tables might not have any dead tuples as Tim was talking about, things like that. So that's why using one of the APM tools, application performance monitoring that I suggested is more important. You want to see what's happening really in your life system. Places like and as well as as you reach a certain scale, it's impossible to duplicate your data into some test system. Like it's just impractical

Speaker 5: Thank you for your talk. Um my question is about uh test examples when you're working with this. So you can create kind of toy examples to demonstrate various database features, but Have you come across any helpful open kind of training databases or data sets that you can use to understand how some of these work for like your own practice as it were?

Speaker 1: Uh yeah, so the question is about are there any test databases for learning about indexes? Um yeah, there are a few that pop to mind. One is this uh MySQL test database that they provide called Sakila It's a SQL dump, it might load in other um servers. That's a general try and test all the features in my SQL uh data struct um data set so that will have different kinds of foreign keys Another one is this TPC benchmark that different database providers all use to like benchmark their databases and say, hey, we're really good at this kind of index search. You might want to try loading that and see the kinds of challenging queries that the databases are being forced to search for.

Speaker 1: Thank you.