Why is my index not being used in this nested query?

Question

I have a nested query: an inner geoquery to filter, then an outside query to get the ids of the objects.
Because this query became a speed bottleneck in an important operation, I am working on improving it.

This is where I stand:

• I can't understand why the query won't use an index on the select column.
• When I EXPLAIN the query, I see that it is using a Seq Scan where I expected it to use the index I created.

The data sizes

The table has 34k rows.

This query usually selects a couple hundreds of rows, but in this new particularly large case it selects 5k rows.

The query

Original version

The query was:

• Querying for objects within an area (ST_WITHIN);
• Then selecting the parent_id of the object;
• Then selecting all the objects whose id or parent_id were in the list.

The complicated part is that the table has composite objects, that are "linear objects" ¹ made up of child objects. And if some of their child objects are in the area, we want to select the parent object and all the siblings.

¹ (Lines, pipes, etc; bBézier curves built by using several child objects as... nodes.)

SELECT id
FROM public.world_objects
-- where the root_id is in...
WHERE COALESCE(parent_id, id) IN (
    -- select the root_id: parent_id, or the id if no parent_id.
    SELECT COALESCE(parent_id, id)
    FROM public.world_objects
    WHERE is_deleted = false
        -- COALESCE to '' because we cannot compare NULL using an equals sign.
        AND COALESCE(public.world_objects.label_type, '') = COALESCE('80624e39-96b8-4058-a61e-5171060105a6', '')
        AND ST_DWithin(
            ST_SetSRID(st_point(-12.3456788012345, 12.3456788012345), 4326),
            ST_SetSRID(st_point(longitude, latitude), 4326),
            100000, false)
        AND internal_type_description NOT IN ('Chain', 'Flightpath', 'Line', 'Pipe'));

Current version

To speed this process up, we are computing and persisting COALESCE(parent_id, id) into root_id.
A trigger before insert or update sets the value.

(We can't use a generated column because that's only for pg12+, and we have a server that we can't yet upgrade from pg10.)

So we changed the query to:

SELECT id
FROM public.world_objects
WHERE root_id IN (
    SELECT root_id
    FROM public.world_objects
    WHERE is_deleted = false
        -- COALESCE to '' because we cannot compare NULL using an equals sign.
        AND COALESCE(public.world_objects.label_type, '') = COALESCE('80624e39-96b8-4058-a61e-5171060105a6', '')
        AND ST_DWithin(
            ST_SetSRID(st_point(-12.3456788012345, 12.3456788012345), 4326),
            ST_SetSRID(st_point(longitude, latitude), 4326),
            100000, false)
        AND internal_type_description NOT IN ('Chain', 'Flightpath', 'Line', 'Pipe'));

This sped the process up from 1m:20s (!!) to 0m:10s.
But that's still a lot.

I am aiming for a magnitude not above 0m:0.01s = 100ms.
I think that this must be feasible, for a table with less than 100k rows. Surely I am doing something wrong.

Explaining the query

When the improved query is EXPLAINed, the weight seems to be on joining the inner query with the outer query:

I added an index on the root_id, but it does not seem to be used?!?

CREATE INDEX "world_objects_IX_root_id" ON public.world_objects USING btree (root_id)

Confusion

What's worse is that a co-worker can speed the query up by running vacuum after adding the index.
But not me in my machine, following exactly the same steps.

We have the same PG version, but different PostGIS versions:

• PostgreSQL 12.5, compiled by Visual C++ build 1914, 64-bit
• PostGIS
  • I have POSTGIS="3.1.0 3.1.0" [EXTENSION] PGSQL="120" GEOS="3.9.0-CAPI-1.14.1" PROJ="7.1.1" LIBXML="2.9.9" LIBJSON="0.12" LIBPROTOBUF="1.2.1" WAGYU="0.5.0 (Internal)"
  • and they have 3.0.1

But the inner query is fast, so I don't think that the different PostGIS version is the source of the problem.

Conclusion, questions

• Shouldn't the root_id index be used in the query?
• Are we doing something wrong? What should be done differently? :(
• Is this behaviour explainable?

Answer 1

As I was typing and re-typing the question, I noticed this on the EXPLAIN:

... and decided to try making the inner query not return repeated values. It worked!

SELECT id
FROM public.world_objects
WHERE root_id IN (
    select distinct root_id
    FROM public.world_objects
    WHERE is_deleted = false
        -- COALESCE to '' because we cannot compare NULL using an equals sign.
        AND COALESCE(public.world_objects.label_type, '') = COALESCE('80624e39-96b8-4058-a61e-5171060105a6', '')
        AND ST_DWithin(
            ST_SetSRID(st_point(-12.3456788012345, 12.3456788012345), 4326),
            ST_SetSRID(st_point(longitude, latitude), 4326),
            100000, false)
        AND internal_type_description NOT IN ('Chain', 'Flightpath', 'Line', 'Pipe'));

I don't really know why.
The EXPLAIN on the Nested Loop still says "Inner-Unique" false...
But the query now skips "materialize" and uses an Index Scan instead of Seq Scan, and it's fast. 🤷‍♀️

Answer 2

Your images show only partial result of the explain, but if I understand correctly this is what happens:

1. In the first (slow) version, 4924 objects are found inside the area. Posgresql probably estimates that doing nearly 5k index searches on a 34k rows table will be worse than scanning the whole table once and checking if the rows are in the 5k list.

2. In the second (fast) version, the distinct reduces the number of distinct root_id to only 15. It is then faster to do 15 index searches (every one returning on average 359 objects).

So the difference is probably due to a lot of the objects in the area having the same root_id. Also note that the query plan is chosen by postgresql before executing it. So it probably knows, using statistics, that in the table there are lots of objects with the same root_id. When you tell it you want only distinct values, it expects the number of rows returned from the inner query will be much less and it chooses the different query plan.

Statistics can be slightly different on different machines, and are refreshed by a VACUUM ANALYZE, so that could explain why the query plan is different for your co-worker.