Postgres LIKE query using a GiST index is just as slow as a full scan

Question

What I have is a very simple database that stores paths, extensions and names of files from UNC shares. For testing, I inserted about 1,5 mio rows and the below query uses a GiST index as you see, but still it takes 5 seconds to return. Expected would be a few (like 100) milliseconds.

EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM residentfiles  WHERE  parentpath LIKE 'somevalue'

When using %% in the query, it takes the not that long, even when using sequential scan (?!)

EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM residentfiles  WHERE  parentpath LIKE '%a%'

I also have the same setup for the name (filename) column, when executing a similar query on that one, it only takes half of the time, even when using %%:

EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM residentfiles  WHERE  name LIKE '%a%'

What I already tried cannot be written here in short words. Whatever I do, it gets slow starting from about 1 mio rows. As there is basically never anything deleted, of course vacuuming and reindexing does not help at all. I cannot really use any other type of search than LIKE %% and a GIN or GiST index because I need to be able to find any character in the columns of interest, not only "words for a specific human language".

Is my expectation that this should work in around 100 milliseconds even for many million more rows that wrong?

Further information

DB create script

Re-try without any text or other index at all, 1.7 mio unique entries

EXPLAIN ANALYZE select * from residentfiles where name like '%12345%'
Seq Scan on residentfiles  (cost=0.00..78162.76 rows=33225 width=232) (actual time=0.076..3195.965 rows=45301 loops=1)
  Filter: ((name)::text ~~ '%12345%'::text)
  Rows Removed by Filter: 1604780+
Planning time: 0.596 ms
Execution time: 3318.595 ms

Try with Triagram gin index:

CREATE INDEX IF NOT EXISTS  name_gin_idx ON residentfiles USING gin (name gin_trgm_ops);
CREATE INDEX IF NOT EXISTS  parentpath_gin_idx ON residentfiles USING gin (parentpath gin_trgm_ops);
CREATE INDEX IF NOT EXISTS  ext_gin_idx ON residentfiles USING gin (extension gin_trgm_ops);
EXPLAIN ANALYZE select * from residentfiles where name like '%12345%'

Aggregate  (cost=53717.59..53717.60 rows=1 width=0) (actual time=1694.223..1694.224 rows=1 loops=1)
  ->  Bitmap Heap Scan on residentfiles  (cost=341.89..53631.82 rows=34308 width=0) (actual time=72.010..1615.007 rows=46532 loops=1)
        Recheck Cond: ((name)::text ~~ '%12345%'::text)
        Rows Removed by Index Recheck: 111
        Heap Blocks: exact=46372
        ->  Bitmap Index Scan on name_gin_idx  (cost=0.00..333.31 rows=34308 width=0) (actual time=52.287..52.287 rows=46643 loops=1)
              Index Cond: ((name)::text ~~ '%12345%'::text)
Planning time: 10.881 ms
Execution time: 1694.755 ms

Try with varchar_pattern:

CREATE INDEX idx_varchar_pattern_parentpath ON residentfiles (parentpath varchar_pattern_ops);
CREATE INDEX idx_varchar_pattern_name ON residentfiles (name varchar_pattern_ops);
CREATE INDEX idx_varchar_pattern_extension ON residentfiles (extension varchar_pattern_ops);
EXPLAIN ANALYZE select * from residentfiles where name like '%12345%'

Aggregate  (cost=89718.74..89718.75 rows=1 width=0) (actual time=1995.206..1995.207 rows=1 loops=1)
  ->  Seq Scan on residentfiles  (cost=0.00..89574.98 rows=57507 width=0) (actual time=0.060..1913.114 rows=52232 loops=1)
        Filter: ((name)::text ~~ '%12345%'::text)
        Rows Removed by Filter: 1852103
Planning time: 8.280 ms
Execution time: 1995.255 ms

Update: i switched to elasticsearch for any text-search apps. Everything just works there and the efforts are minimal compared to the efforts i made with postgres and still not getting the desired results. — Harry
– Harry, Commented Feb 19, 2022 at 23:43

MarcoP · Accepted Answer · 2019-01-30 09:07:12Z

In my opinion if you do not share how you did the test, it's very hard to give you an answer. Let see an example of what I mean. Sorry for I used a postgres 11 but the conclusions are the same:

This is a new db, there is nothing running against the instance:

test=# CREATE EXTENSION pg_trgm;
CREATE EXTENSION
test=# create table test_trgmidx (col1 varchar(30), col2 varchar(50));
CREATE TABLE
test=# CREATE INDEX trgm_idx_test_col2 ON test_trgmidx USING gist (col2 gist_trgm_ops);
CREATE INDEX

Inserting 500000 rows using a very simple loop.

test=# \i loop_long.sql
DO
test=# select count(1) from test_trgmidx;
 count
--------
 500000
(1 row)

test=# select * from test_trgmidx limit 20;
col1        |    col2
------------+------------
 ABCD1EFGH  | abcd1efgh
 ABCD2EFGH  | abcd2efgh
 ABCD3EFGH  | abcd3efgh
 ABCD4EFGH  | abcd4efgh
 ABCD5EFGH  | abcd5efgh
 ABCD6EFGH  | abcd6efgh
 ABCD7EFGH  | abcd7efgh
 ABCD8EFGH  | abcd8efgh
 ABCD9EFGH  | abcd9efgh
 ABCD10EFGH | abcd10efgh
 ABCD11EFGH | abcd11efgh
 ABCD12EFGH | abcd12efgh
 ABCD13EFGH | abcd13efgh
 ABCD14EFGH | abcd14efgh
 ABCD15EFGH | abcd15efgh
 ABCD16EFGH | abcd16efgh
 ABCD17EFGH | abcd17efgh
 ABCD18EFGH | abcd18efgh
 ABCD19EFGH | abcd19efgh
 ABCD20EFGH | abcd20efgh
(20 rows)

Now I restart the instance to have a clean buffer cache, then I run the explain for the first select twice, to see how cache is "disturbing" our results:

test=# explain (analyze, buffers, verbose) select * from test_trgmidx where col2 like 'abcd345678efgh';
                                                               QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------------------
 Index Scan using trgm_idx_test_col2 on public.test_trgmidx  (cost=0.29..8.30   rows=1 width=28) (actual time=4.586..4.912 rows=1 loops=1)
  Output: col1, col2
  Index Cond: ((test_trgmidx.col2)::text ~~ 'abcd345678efgh'::text)
  Buffers: shared hit=19 read=237
 Planning Time: 0.303 ms
 Execution Time: 4.934 ms
(6 rows)

test=# explain (analyze, buffers, verbose) select * from test_trgmidx where col2 like 'abcd345678efgh';
                                                               QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------------------
 Index Scan using trgm_idx_test_col2 on public.test_trgmidx  (cost=0.29..8.30 rows=1 width=28) (actual time=2.096..2.298 rows=1 loops=1)
 Output: col1, col2
 Index Cond: ((test_trgmidx.col2)::text ~~ 'abcd345678efgh'::text)
Buffers: shared hit=232
Planning Time: 0.072 ms
Execution Time: 2.317 ms
(6 rows)

It's clear that the first run need to retrive rows from disk (read=237) while the second one need only to access buffer cache (shared hit=232, NO reads). Now let's do the same for the second select, restart the instance and run the explain twice:

test=# explain (analyze, buffers, verbose) select * from test_trgmidx where col2 like '%d2%';
                                                         QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------
 Seq Scan on public.test_trgmidx  (cost=0.00..9926.00 rows=106061 width=28) (actual time=0.039..89.906 rows=111111 loops=1)
   Output: col1, col2
   Filter: ((test_trgmidx.col2)::text ~~ '%d2%'::text)
   Rows Removed by Filter: 388889
   Buffers: shared read=3676
 Planning Time: 0.719 ms
 Execution Time: 94.942 ms
(7 rows)

test=# explain (analyze, buffers, verbose) select * from test_trgmidx where col2 like '%d2%';
                                                         QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------
 Seq Scan on public.test_trgmidx  (cost=0.00..9926.00 rows=106061 width=28) (actual time=0.015..61.741 rows=111111 loops=1)
   Output: col1, col2
   Filter: ((test_trgmidx.col2)::text ~~ '%d2%'::text)
   Rows Removed by Filter: 388889
   Buffers: shared hit=3676
 Planning Time: 0.081 ms
 Execution Time: 65.878 ms
(7 rows)

As you can see, now the reads come from disk the first run and from buffer the second one. Things are even more complicated because of OS buffers. Is is possible to clean OS cache and re-run everithing having back different results:

# free
              total        used        free      shared  buff/cache   available
Mem:        7914604      929920     4105056       93960     2879628     6748994
Swap:       4063228           0     4063228

# echo 3 > /proc/sys/vm/drop_caches

# free
              total        used        free      shared  buff/cache   available
Mem:        7914604      802204     6846392       93960      266008     6951156
Swap:       4063228           0     4063228
#

Look at column buff/cache as it drop down from 2879628 to 266008. Now run the explain again (twice for any select):

postgres=# \c test
You are now connected to database "test" as user "postgres".
test=#  explain (analyze, buffers, verbose) select * from test_trgmidx where col2 like 'abcd345678efgh';
                                                                     QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------------------------
 Index Scan using trgm_idx_test_col2 on public.test_trgmidx  (cost=0.29..8.30 rows=1 width=28) (actual time=130.858..140.403 rows=1 loops=1)
   Output: col1, col2
   Index Cond: ((test_trgmidx.col2)::text ~~ 'abcd345678efgh'::text)
   Buffers: shared hit=19 read=237
 Planning Time: 38.448 ms
 Execution Time: 140.466 ms
(6 rows)

test=#  explain (analyze, buffers, verbose) select * from test_trgmidx where col2 like 'abcd345678efgh';
                                                               QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------------------
 Index Scan using trgm_idx_test_col2 on public.test_trgmidx  (cost=0.29..8.30 rows=1 width=28) (actual time=4.386..4.759 rows=1 loops=1)
   Output: col1, col2
   Index Cond: ((test_trgmidx.col2)::text ~~ 'abcd345678efgh'::text)
   Buffers: shared hit=232
 Planning Time: 0.115 ms
 Execution Time: 4.787 ms
   (6 rows)

test=# explain (analyze, buffers, verbose) select * from test_trgmidx where col2 like '%d2%';
                                                         QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------
 Seq Scan on public.test_trgmidx  (cost=0.00..9926.00 rows=106061 width=28) (actual time=9.214..161.243 rows=111111 loops=1)
   Output: col1, col2
   Filter: ((test_trgmidx.col2)::text ~~ '%d2%'::text)
   Rows Removed by Filter: 388889
   Buffers: shared hit=1 read=3675
 Planning Time: 0.090 ms
 Execution Time: 165.354 ms
(7 rows)

test=#  explain (analyze, buffers, verbose) select * from test_trgmidx where col2 like '%d2%';
                                                          QUERY PLAN
       ----------------------------------------------------------------------------------------------------------------------------
 Seq Scan on public.test_trgmidx  (cost=0.00..9926.00 rows=106061 width=28) (actual time=0.013..62.043 rows=111111 loops=1)
   Output: col1, col2
   Filter: ((test_trgmidx.col2)::text ~~ '%d2%'::text)
   Rows Removed by Filter: 388889
   Buffers: shared hit=3676
 Planning Time: 0.078 ms
 Execution Time: 66.101 ms
   (7 rows)

You can check how different are now the statistics, first run read form disk, second one from buffer cache. All these lines only to say that in my opinion and for my experience, it is almost impossible to have a clear understanding about what is happening in you environment without all the information around how you did any single explain. And even having all the informations, it is sometimes very difficult to find the answer because of all the variables playing a role. My 2 cents

That's great info, i'll need lots of time to investigate all of it. Anyway, this is not a theoretical thing, it needs to work in production. I am not searching for differences of some (hundred) milliseconds but i'd like to get rid of some seconds. It cannot be that hard to search for text in varchar tables with a few mio entries. Does my comment change anything on your request to take care about caches? — Harry
– Harry, Commented Jan 30, 2019 at 9:20
Cache always plays a role, both from OS point of view and from rdbms. You can have the most unpredictable explain, but once the result is on cache the access to this data is very fast. What I alway try to test when I have to deploy a new service is to run the application against the database and check after a few hours how the select performs. If in a scenario like the one that will be deployed on production, the response time is ok from a user perspective, then it is ok. Otherwise I start to check every single sql to put out the best I can. — MarcoP
– MarcoP, Commented Jan 30, 2019 at 9:56
As i am not interested at all in the bare existence of a cache (it just has negative influence to my testing but no positive influence to production), i am looking for the best way how to exclude this variable from my tests. Do you think restarting the DB service before executing any statement will suffice? — Harry
– Harry, Commented Feb 8, 2019 at 22:59
For sure restarting the instance will clean the postgres shared buffers. But it does not clean the OS cache, so at the first select you wont be able to know if the blocks have been read from disk or simply by OS cache (which is mapped in RAM). Deleting the OS cache as I did in my answer is not definitely a prof that the buffers you need have been cleaned, my understanting is not so deep to been able to identify which blocks have been cleand and which not. restarting the server could be a solution..not really useful I konw. — MarcoP
– MarcoP, Commented Feb 11, 2019 at 8:01
In the end in IMVHO if you are trying to speed up every single read, tuning every single ms, probably you need a cache layer up to the database, as the respond time you can have (from db) is not a fixed value, there are too many variables. Let suppose you end up whit a read time good for you. How can you be sure that if the load in the server grows (I/O problems, number of concurrent transactions go up..) yuo can achieve same respond time? — MarcoP
– MarcoP, Commented Feb 11, 2019 at 8:05

Erwin Brandstetter · Accepted Answer · 2019-01-30 18:09:07Z

It all depends ...

Well, a couple of things are certain:

For the presented use case, a trigram GIN index should deliver best read performance. Not GiST (slower) and not text_pattern_ops (only applicable for left-anchored / leading patterns). So focus your efforts around this Index:
```
CREATE INDEX name_gin_trgm_idx ON residentfiles
USING gin (name gin_trgm_ops);
```
etc. See:
- LIKE query performance variations
Postgres 9.5 is getting old. The current major version as of writing is Postgres 11. There have been major improvements since - for big data in general, and for GIN (and GiST) indexes in particular - especially for trigram GIN indexes. Urgently consider upgrading .
- Failing that, at least upgrade to the lagest minor version, as is the standing recommendation of the Postgres project
An added LIMIT n is a game changer. You mentioned that only in s comment, but it completely changes the task. Given a common pattern (like your unfotunate example 'a', Postgres will switch to a sequential scan, for good reason: just scan and filter few data pages until enough matches pop up.
- Just in case: the situation changes yet again if you add ORDER BY on top of it.
Hardware and server configuration are important for your case. Yet you hardly disclosed anything ...
Size matters. You can gain a few percent by redesigning your base table. See:
- Calculating and saving space in PostgreSQL

Michał Zaborowski · Accepted Answer · 2019-01-29 10:33:03Z

Thanks for the question. In this case I would use pg_trgm. Here is blog post with samples, and explanation: https://niallburkley.com/blog/index-columns-for-like-in-postgres/

In short:

CREATE EXTENSION pg_trgm;
CREATE INDEX residentfiles_parentpath_trgm_idx ON residentfiles USING gin (parentpath gin_trgm_ops);
EXPLAIN (ANALYZE, BUFFERS) SELECT * FROM residentfiles  WHERE  name LIKE '%a%'

I don't want to repeat that post here, on the other hand - it should be meaningful response. If that is not - just guide me to right direction.

Community · Accepted Answer · 2020-06-15 09:05:18Z

1

To speed up "like" queries in postgres, the special operators varchar_pattern_ops and text_pattern_ops should be used.

Please look at that page of documentation which will explain how to create such an index.

Have a nice day

edited Jun 15, 2020 at 9:05

CommunityBot

1

answered Jan 30, 2019 at 7:36

Arkhena

1,61010 silver badges15 bronze badges

1

Postgres keep tracks of data through statistics. By default, it will keep the top 100 most frequent values and their frequencies. Then it also keeps a track of a estimated number of rows in a table, so it simply just needs to multiply the frequency by the estimated number of rows. You may find this presentation useful : postgresql.eu/events/nordicpgday2018/sessions/session/1769/…

Arkhena
– Arkhena

2019-01-30 09:59:24 +00:00
Commented Jan 30, 2019 at 9:59

Add a comment |

Stack Exchange Network

Postgres LIKE query using a GiST index is just as slow as a full scan

Further information

4 Answers 4

Your Answer

Hot Network Questions

Postgres LIKE query using a GiST index is just as slow as a full scan

Further information

4 Answers 4

Your Answer

Sign up or log in

Post as a guest

Related

Hot Network Questions