GitLab Database Office Hours, 9 Aug 2019

Previous Meeting Next Meeting

⏯

youtube image

►

From YouTube: 2019-08-09 - Database query optimization techniques: UNION push down and TOP-K with index

Description

We optimize a query to retrieve TOP-100 projects for a user, bringing down query runtime from 7s to less than 20ms.

Context: https://gitlab.com/gitlab-org/gitlab-ce/issues/65854

The tricks applied are:
1. UNION push down instead of OR
2. ORDER BY, LIMIT push down into UNION branches
3. Partial index to efficiently retrieve TOP-K by ORDER BY criteria

A

All right, so I would like to quickly record with you about a query optimization, because it is rather interesting to see those like tricks that can be applied, and it's also quite an interesting query. So, let's, let's talk right into that came from looking at from a at a checkup report that we got from a production database once a week and it basically looks at its 30 minutes interval and records all the all.

A

The queries that come in and one query stood out or actually quite a few are interesting, but that's the one I took- and this is this one- you can see that it's not called very often so the frequency is not as high as four other queries, for example, but the average query timing is quite concerning, so that is that is at about eight seconds per call, and we see we saw this 360 times in in about 30 minutes and I took that Korea when you format that a little bit you can see that better.

A

So it is actually fairly fairly standard. Query we like to retrieve projects for a particular user. That's my my user ID in this case and we'd like to retrieve the private ones, are the ones that are like that I'm authorized to see, and in addition to that, the ones that are in public. So basically when you're it could lock on those are quite a lot of products, because we have a lot of public projects.

A

The way we do, that is we basically or those two conditions additionally we're looking at or we want to exclude the products that are an Englishman and the caveat here is that we also ordered by created at an ID which makes me think that comes from an API call but I'm not totally sure, but and we're looking at the top top 100 projects by that sort. Water. Basically, and what happens when you, when you run that currently when it takes like six, seven or eight hours, not hours seconds?

A

Is that it basically.

A

It basically performs a sequential scan on projects.

A

That is mostly because of the oral condition you know you can't use them that you can't always use an index for or conditions looks better for end, but or is difficult, and we end up scanning the whole table evaluating the things on the fly and we're actually discarding.

A

Instead, eight point five million projects on the fly and we still return one 1.3 1.4 million. We sort them and then we take the top hundred, and that is rather inefficient way of doing that.

A

What we can do about that is just open that in the issue also detect you, so what we can do about that is actually splitting in two different parts. Remember that we wanted to get the private projects, and we can do that in relatively simple query, so to get the ones that I'm authorized to see.

A

I'll just select the ID for projects where same condition, basically as before, but it's only this condition like we only look at the ones that I'm authorized to see, and we also exclude the pending deletions so that that's where to get get my product project and the public ones in a similar way.

A

We can do basically here same things like the ID from projects based on the visibility level as before same condition or depending delete same old boys and and then a limit I'll talk about that in a second and then we Union those right and you can do without the order by and limit on the on the particular branches.

A

But then you end up like retrieving quite a still very many projects from from that Union and then you sort of on the fly order them and then you take the top 400 and that is not necessary, because we only had those two branches for the Union and if you want to make sure that we end up with a maximum of 100 projects, we have to take maximum of hundred projects from each each part of that Union branch.

A

So what we do is we just take a hundred private projects and one hundred public ones, and we make sure that the order buy is right because you want to you want to take the most recent ones by create that time stem and then IB, and we do that in both branches here. So we end up by selecting from the Union.

A

We end up with a maximum of 200 projects here and actually that makes it simple to you know, sort them on the fly, so we would sort them both created at the my ID once again, because now we have this common set of like both private and public ones. We sort them again on the fly and then we take the top hundred, but there is only very little data to sort by so that is quite efficient.

A

We can. We can take that and just without any additional index see how the how the plan would look like.

A

I'll probably have to drop the index I created earlier.

A

This is a lot of.

A

Not exactly prepared for that.

A

Alright, so this is the courier we just discussed with the Union tricks and they push down autopilot courses and it still takes a long time to execute.

A

Should probably have to put the explained for the query so that we can look at the plan to the once again.

A

Now, when we look at this, there is the.

A

There is when you look at this here, this is basically to figure out the projects that are internal public, so this is day visibility, condition and we basically.

A

Spend most of the time for this curry, so the curry took about 2.7 seconds and we've spent 2.5 and actually scanning this index, and we read a lot of data from that forum there and we we have two. We have an index for the visibility level here, so that is that a sufficient to retrieve, but the data we're getting back is quite quite a lot and only once we have all that data.

A

We do the sorting this is here, so the sorting doesn't come from the index, but it's it's performed on the fly and then we apply the limit. So we've first retrieve all that one point: oh, what's that one point four million rows from like for me: we do the sorting on the fly and then we applied a limit and take the top 100 ones right, and this is actually I think the major optimization that we can do here.

A

We can create an index um that supports both the condition that we're looking at and the ordering and the way to do that is creating a partial index for the condition. So this translates to the same condition that we're using in the query, visibility, level in 1020's or internal or public and pending delete is false. This is the partial condition, and now we index columns that directly relate to the columns that we order by.

A

So if we look at the query once again, what we want to all about is the created, add x term in descending order and the ID in descending order, and now we create an index that has exactly the columns, like the all about clause and majesty sort of the where conditions, with its partial condition and the resulting thing is an index that is a perfect match because it contains exactly the data they're looking for and the index order is already in the order that you want to look at it.

A

So, basically you can go to the index. You can retrieve the first hundred curry's and you don't have to do any sorting at all and primarily you don't have to retrieve the full index right. So you only take the top hundred ones from the index and that's very efficient to do so. When we run that query once again, hopefully it's very fast- and it actually is like goes down to 18 milliseconds, and when we look at how this changed the plan.

A

That's in here the system new index that we created, we do index only scan, which is also very efficient, because we only read from the index, and this is actually what we just talked about. We retrieved the first yeah. That's the first hundred rows from from the index. We do. We don't do any sorting on that, because we know the reading from that from that index will give us the expected sort order.

A

We're basically done with that branch right, and that really makes it a lot faster than before, coming from 2.7 seconds to about 18 18 milliseconds.

A

So in summary, what we did was fiddling or splitting the the or parts of the query into unions and then finding a way to make sure that each of those branches only retrieves enough records for us to retrieve the hundred records that we're looking for and the way to do.

A

That was to push down the order by and limit losses to those individual branches of the Union query and then provide an index for one of them to make sure that retrieving the top hundred by this order becomes very efficient, and by doing that, we were able to speed the curry up from I think initially, it was about six some seven seconds about that down to like twenty milliseconds. That's quite good and does those tricks are quite universal.

A

So whenever you spot an or on the query, that may be a good candidate to look to think about a union with like specialized branches instead of instead of a lower query and I hope that we find all the places where that crew is used.

A

It looks quite familiar, so I mean retrieving projects or checking project. Authorization is something that we do in a lot of places. So hopefully we can find all of them and make sure that we use the better create or the optimized version for that there I hope that was kind of interesting I'm, always looking for feedback, so feel free to comment somewhere. Where, if sent me a message once back, Thanks.