Postgres ignores my gin index for a similarity query

Question

In my table (around 12 million rows), I have a text field called full_name and the id.

I also have the following indexes:

create index entities_full_name_gin_trgm_ops_index
  on temp.entities
  using gin(full_name gin_trgm_ops);

create index entities_id_index ON temp.entities (id);

I'm trying to run the following query:

select lhs.id, lhs.full_name, rhs.id, rhs.full_name
from temp.entities as lhs
left join lateral (
  select id, full_name
  from temp.entities
  where full_name % lhs.full_name and id < lhs.id
  limit 1
) as rhs on true
order by lhs.id desc
limit 10;

Basically this query is searching for another entity that has a similar name and has an older id than the current one (I'm using UUIDV7).

This query will generate the following plan:

UPDATE 1: Added query plan with explain(analyze, verbose, buffers, settings).

                                                                                  QUERY PLAN                                  
                                                                                                                              
                                                                                                                              
                                                                                                                              
                                                 
------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------
-------------------------------------------------
 Limit  (cost=1.12..66.24 rows=10 width=68) (actual time=22616.601..289628.893 rows=10 loops=1)
   Output: lhs.id, lhs.full_name, entities.id, entities.full_name
   Buffers: shared hit=64213445 read=2646221 written=1696
   ->  Nested Loop Left Join  (cost=1.12..86936338.39 rows=13350926 width=68) (actual time=22616.600..289628.886 rows=10 loops
=1)
         Output: lhs.id, lhs.full_name, entities.id, entities.full_name
         Buffers: shared hit=64213445 read=2646221 written=1696
         ->  Index Scan Backward using entities_id_index on temp.entities lhs  (cost=0.56..719298.01 rows=13350926 width=34) (
actual time=0.035..0.055 rows=10 loops=1)
               Output: lhs.id, lhs.first_name, lhs.middle_name, lhs.last_name, lhs.name_suffix, lhs.full_name, lhs.address_hou
se_number, lhs.address_street_direction, lhs.address_street_name, lhs.address_street_suffix, lhs.address_street_post_direction
, lhs.address_unit_prefix, lhs.address_unit_value, lhs.address_city, lhs.address_state, lhs.address_zip, lhs.address_zip_4, lh
s.address_legacy, lhs.address_normalized, lhs.address, lhs.status, lhs.total_records, lhs.total_buy_records, lhs.total_sell_re
cords, lhs."fix_and_flip?", lhs."buy_and_hold?", lhs."wholesaler?", lhs.last_year, lhs.last_year_buy_records, lhs.last_year_bu
y_transfer_amount, lhs.last_year_sell_records, lhs.last_year_sell_transfer_amount, lhs.current_year, lhs.current_year_buy_reco
rds, lhs.current_year_buy_transfer_amount, lhs.current_year_sell_records, lhs.current_year_sell_transfer_amount, lhs.score, lh
s.score_version, lhs.inserted_at, lhs.updated_at
               Buffers: shared hit=2 read=8
         ->  Limit  (cost=0.56..6.45 rows=1 width=34) (actual time=28962.880..28962.880 rows=1 loops=10)
               Output: entities.id, entities.full_name
               Buffers: shared hit=64213443 read=2646213 written=1696
               ->  Index Scan using entities_id_index on temp.entities  (cost=0.56..262023.42 rows=44503 width=34) (actual tim
e=28962.878..28962.878 rows=1 loops=10)
                     Output: entities.id, entities.full_name
                     Index Cond: (entities.id < lhs.id)
                     Filter: ((entities.full_name)::text % (lhs.full_name)::text)
                     Rows Removed by Filter: 8771697
                     Buffers: shared hit=64213443 read=2646213 written=1696
 Settings: temp_buffers = '64MB', work_mem = '128MB', max_parallel_workers_per_gather = '8', enable_seqscan = 'off'
 Planning:
   Buffers: shared hit=16 read=2
 Planning Time: 0.364 ms
 Execution Time: 289628.935 ms
(23 rows)

As you can see, Postgres is using my btree index, not my gin one making this query extremelly slow.

UPDATE 2: As suggested by Laurenz Albe, I added an order by to force the plan to use my index. That worked, but the query is still very slow (takes around 6 seconds to finish with limit 10 and I want to run the real query will a limit of 1000 or 10000 which would be way slower.

Here is the new query:

select lhs.id, lhs.full_name, rhs.id, rhs.full_name
from temp.entities as lhs
left join lateral (
  select id, full_name
  from temp.entities
  where full_name % lhs.full_name and id < lhs.id
  order by full_name
  limit 1
) as rhs on true
order by lhs.id desc
limit 10;

And here is the resulting plan:

                                                                                                                                                                                                              QUERY PLAN                                      
                                                                                                                                                                                                                                                              
                                                                                                                                                                         
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=224541.60..2469952.55 rows=10 width=68) (actual time=687.770..6063.586 rows=10 loops=1)
   Output: lhs.id, lhs.full_name, entities.id, entities.full_name
   Buffers: shared hit=479653 read=64097 written=295
   ->  Nested Loop Left Join  (cost=224541.60..2997831757508.70 rows=13350926 width=68) (actual time=687.769..6063.580 rows=10 loops=1)
         Output: lhs.id, lhs.full_name, entities.id, entities.full_name
         Buffers: shared hit=479653 read=64097 written=295
         ->  Index Scan Backward using entities_id_index on temp.entities lhs  (cost=0.56..719298.01 rows=13350926 width=34) (actual time=0.026..0.068 rows=10 loops=1)
               Output: lhs.id, lhs.first_name, lhs.middle_name, lhs.last_name, lhs.name_suffix, lhs.full_name, lhs.address_house_number, lhs.address_street_direction, lhs.address_street_name, lhs.address_street_suffix, lhs.address_street_post_direction, 
lhs.address_unit_prefix, lhs.address_unit_value, lhs.address_city, lhs.address_state, lhs.address_zip, lhs.address_zip_4, lhs.address_legacy, lhs.address_normalized, lhs.address, lhs.status, lhs.total_records, lhs.total_buy_records, lhs.total_sell_record
s, lhs."fix_and_flip?", lhs."buy_and_hold?", lhs."wholesaler?", lhs.last_year, lhs.last_year_buy_records, lhs.last_year_buy_transfer_amount, lhs.last_year_sell_records, lhs.last_year_sell_transfer_amount, lhs.current_year, lhs.current_year_buy_records, l
hs.current_year_buy_transfer_amount, lhs.current_year_sell_records, lhs.current_year_sell_transfer_amount, lhs.score, lhs.score_version, lhs.inserted_at, lhs.updated_at
               Buffers: shared hit=4 read=6
         ->  Limit  (cost=224541.04..224541.05 rows=1 width=34) (actual time=606.348..606.348 rows=1 loops=10)
               Output: entities.id, entities.full_name
               Buffers: shared hit=479649 read=64091 written=295
               ->  Sort  (cost=224541.04..224652.30 rows=44503 width=34) (actual time=606.346..606.346 rows=1 loops=10)
                     Output: entities.id, entities.full_name
                     Sort Key: entities.full_name
                     Sort Method: quicksort  Memory: 25kB
                     Buffers: shared hit=479649 read=64091 written=295
                     ->  Bitmap Heap Scan on temp.entities  (cost=102831.00..224318.53 rows=44503 width=34) (actual time=606.318..606.336 rows=2 loops=10)
                           Output: entities.id, entities.full_name
                           Recheck Cond: (((entities.full_name)::text % (lhs.full_name)::text) AND (entities.id < lhs.id))
                           Rows Removed by Index Recheck: 1
                           Heap Blocks: exact=30
                           Buffers: shared hit=479649 read=64091 written=295
                           ->  BitmapAnd  (cost=102831.00..102831.00 rows=44503 width=0) (actual time=606.297..606.297 rows=0 loops=10)
                                 Buffers: shared hit=479644 read=64066 written=295
                                 ->  Bitmap Index Scan on entities_full_name_gin_trgm_ops_index  (cost=0.00..882.62 rows=133509 width=0) (actual time=83.707..83.707 rows=5 loops=10)
                                       Index Cond: ((entities.full_name)::text % (lhs.full_name)::text)
                                       Buffers: shared hit=20153 read=11997 written=40
                                 ->  Bitmap Index Scan on entities_id_index  (cost=0.00..101925.88 rows=4450309 width=0) (actual time=522.579..522.579 rows=13350920 loops=10)
                                       Index Cond: (entities.id < lhs.id)
                                       Buffers: shared hit=459491 read=52069 written=255
 Settings: temp_buffers = '64MB', work_mem = '128MB', max_parallel_workers_per_gather = '8', enable_seqscan = 'off'
 Planning:
   Buffers: shared read=1
 Planning Time: 0.140 ms
 Execution Time: 6063.627 ms
(36 rows)

Any other suggestions to make this faster?

Answer 1

It has to plan the query without knowing what string it will be searching for in the lateral subquery, so it has to make generic assumptions about how many rows it will return. That generic assumption for % is 1/100 and for inequality of id is 1/3. Normally a high estimate of rows is conservative, but in the case of a LIMIT it is the opposite, as it thinks that with a lot of rows it can meet the LIMIT easily and then stop.

When you pull out the subquery and run it with literal values, it can plan with those literal values. (Although in this case, it doesn't meaningfully do so for the %, it is just that the literal value provokes it into using a different generic estimate which is more selective). If you want to see what the generic plan looks like, you could do:

explain (generic_plan) select id, full_name
  from temp.entities
  where full_name % $1 and id < $2
  limit 1;

In your new query with the gratuitous ORDER BY, most of the time is spent constructing the giant bitmap for the 'id' condition. It knows this is going to be slow, so I don't know why it bothers to do this. (In my hands, it doesn't do that, it applies that condition as a filter rather than a bitmap). you could probably force it to stop using the id index by writing that part of the query like this:

and id::text < lhs.id::text

Since there is no way to force the planner to use an BitmapAnd when it doesn't want to, and since in my hands it doesn't want to, there is no way for me to explore what might be going on to make it use the BitmapAnd for you. If you could show the plan you get using my proposed re-writing of it, that might give us some clues.

Answer 2

When you view the query plan with plansplainer, you'll see that Postgres spends most of it's time scanning the entities_id_index. => https://plansplainer.com/WNL8jEeNCRPPhXWzfTRrs

This index is used to create bitmap of all pages where (entities.id < lhs.id) The resulting bitmap contains tupleids for 13,350,920 rows. The And operation keeps only 2 rows average per loop. This makes sense because the id < lhs.id check effectively selects all rows with a lower id, and since your outer sorting is descending, you'll be selecting a large set there.

Scanning the GIN index however is only a 10th of the time, so this is not your bottleneck.

I think you should add the id to GIN index:

This way, postgres can use a single index scan, starting from ids below the id of the outer set.

create index entities_full_name_gin_trgm_ops_index
  on temp.entities
  using gin(id, full_name gin_trgm_ops);

Also, it feels like you might be having some table bloat here, because it accesses a lot of buffers for this operation. Maybe you need to check your vacuum settings, and long running transactions too.