Re: [External] Join queries slow with predicate, limit, and ordering

On Mon, Dec 2, 2019 at 8:29 AM Aufar Gilbran <aufar(dot)gilbran(at)grab(dot)com> wrote:

> Hello,
>
> I'm trying to figure out how to optimise 3-table (many-to-many relation)
> joins
> with predicate, limit, and ordering, where one of the tables returns at
> most one
> row.
>
> This is the query that I have right now:
>
> SELECT entity.id
> FROM (
> SELECT entity_tag.entity_id
> FROM tag
> JOIN entity_tag ON tag.id = entity_tag.tag_id
> WHERE tag.key = 'status'
> AND tag.value = 'SUCCEEDED'
> ) matched
> JOIN entity ON matched.entity_id = entity.id
> WHERE entity.type = 'execution'
> ORDER BY entity.id DESC
> LIMIT 10;
>

What happens if you set enable_sort to off before running it?

> -> Nested Loop (cost=1.28..723.38 rows=1 width=4) (actual
> time=0.153..5590.717 rows=89222 loops=1)
>

It thinks it will find 1 row, and actually finds 89,222. I don't know
exactly why that would be, I suppose tag_id has an extremely skewed
distribution. But yeah, that is going to cause some problems. For one
thing, if there was actually just one qualifying row, then it wouldn't get
to stop early, as the LIMIT would never be satisfied. So it thinks that if
it choose to walk the index backwards, it would have to walk the **entire**
index.

-> Index Only Scan using
> entity_tag_tag_id_entity_id_idx on public.entity_tag (cost=0.43..711.53
> rows=201 width=16) (actual time=0.035..756.829 rows=89222 loops=1)
> Heap Fetches: 89222
>

You should vacuum this table. Doing that (and only that) probably won't
make a great deal of difference to this particular query, but still, it
will help some. And might help other ones you haven't noticed yet as well.

>
> Both tag_key_value_key and entity_tag_tag_id_entity_id_idx is a UNIQUE
> constraint on tag(key,value) and entity_tag(tag_id, entity_id)
> respectively.
>
> It seems to me that PostgreSQL runs the nested loop against all of the 90K
> records because it wants to sort the result before limiting the result.

It doesn't **know** there are going to be 90000 records. It cannot plan
queries based on knowledge it doesn't possess.

> It
> doesn't take into account of the UNIQUE constraint imposed on the table and
> thinks that the join being done inside the subquery will change the
> ordering of
> entity_id returned by the subquery, thus prompting the sort.
>

This seems like rather adventurous speculation. It does the sort because
the horrible estimation makes it think it will be faster that way, not
because it thinks it is the only possible way. Of you set enable_sort =
off and it still does a sort, then you know it thinks there is no other way.

>
> I believe with how the index sorted, it should be able to just scan the
> index
> backwards because at most only one tag_id will be returned. When I tried
> changing the predicate here to filter by ID with the following query:
>
> -- This runs very fast
> SELECT entity.id
> FROM (
> SELECT entity_tag.entity_id
> FROM tag
> JOIN entity_tag ON tag.id = entity_tag.tag_id
> WHERE tag.id = 24
> ) matched
> JOIN entity ON matched.entity_id = entity.id
> WHERE entity.type = 'execution'
> ORDER BY entity.id DESC
> LIMIT 10;
>

With this query, it can use the join condition to transfer the knowledge of
tag.id=24 to become entity_tag.tag_id=24, and then look up stats on
entity_tag.tag_id for the value 24. When you specify the single row of tag
indirectly, it can't do that as it doesn't know what specific value of
tag.id is going to be the one it finds (until after the query is done being
planned and starts executing, at which point it is too late). But the row
with id=24 doesn't seem to be the same one with "tag.key = 'status' AND
tag.value = 'SUCCEEDED'", so you have basically changed the query entirely
on us.

If you replanned this query with ORDER BY entity.id+0 DESC, (and with the
true value of tag_id) that might give you some more insight into the hidden
"thought process" behind the planner.

Cheers,

Jeff