Team Pleroma is back from FOSDEM and I finally got rid of most of my Tenshi stickers! The meetup was a lot of fun and we did learn a thing or two. One talk I went to see was this one on the state of full text search in current PostgreSQL. Sadly, it didn’t offer any new information to me, but it’s a good primer on the subject.
Overall, it paints a very rosy picture of full text search in PostgreSQL. With the right indexes, you can do efficient and fast full text searches without Elastic or any other additional component. While this is in general true, the devil is in the details. We have been using PostgreSQL for FTS for a while now in Pleroma, so this article is about all the gotchas, pitfalls and caveats that will ruin your search performance and make your users hate you.
(This image is just to grab your attention, what a wall of text, wow.)
How to search
Many Pleroma users are asking “what even is full text search”? That’s easy, it’s just what normal people call ‘search’. You input a term, you get relevant results. But how does this work?
Here’s an example. Let’s say you have two posts in your database, one that says “I love cats” and another that says “I hate cats”. For search, this text will have to be turned into a tsvector, which is essentially a list of relevant words with their position in the text. So, for the two examples, it would look like this:
id: 1, "I love cats" => ["I":0, "love":2, "cats":7]
id: 2, "I hate cats" => ["I":0, "hate":2, "cats":7]
(This has been simplified. See the talk I linked above for the details)
Now, a search would go through all of these tsvectors and try to see if it matches a query. Easy! But it can become problematic when you have a huge dataset.
A database snapshot I took of Soykaf in March last year contains 17960551 posts. Yes, that’s 18 million. It’s obvious that you can’t look through gigabytes of posts on every single search request, so PostgreSQL (and any other search machine) will use indexes to speed up search. The one most appropriate for FTS is the GIN index.
The GIN index
How does the GIN index accelerate searches? Remember our cat posts above? A GIN index for them would look like this:
{
"I": [1,2],
"love": [1],
"hate": [2],
"cats": [1,2]
}
(Again, this is simplified)
The keywords are associated with the ids of the posts they appear in. So to search the whole database now, you don’t actually need to go through the whole database, you just need to check the index for the word you are looking for!
That works well, but it has one BIG gotcha which we’ll soon discover.
GIN index examples
All these examples have been run on my Soykaf database snapshot on a 32 core system. Search performance generally differs between terms that are rare and those that are popular. In our examples, we will always limit the set of results to 10, which is a very common usecase because your users don’t want to see 50000 results.
Here we have a search term that’s rare:
pleroma=# select count(*) from objects where to_tsvector('english', data->>'content') @@ plainto_tsquery('english', 'supercalifragilistic');
count
-------
1
(1 row)
And here’s one that appears many times:
pleroma=# select count(*) from objects where to_tsvector('english', data->>'content') @@ plainto_tsquery('english', 'nsfw');
count
-------
59266
(1 row)
Searching for the rare term is very fast. No surprise, there’s only one result in the index.
pleroma=# explain analyze select id from objects where to_tsvector('english', data->>'content') @@ plainto_tsquery('english', 'supercalifragilistic') limit 10;
QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------
Limit (cost=93.84..107.41 rows=10 width=4) (actual time=0.020..0.021 rows=1 loops=1)
-> Bitmap Heap Scan on objects (cost=93.84..14599.19 rows=10689 width=4) (actual time=0.019..0.020 rows=1 loops=1)
Recheck Cond: (to_tsvector('english'::regconfig, (data ->> 'content'::text)) @@ '''supercalifragilist'''::tsquery)
Heap Blocks: exact=1
-> Bitmap Index Scan on objects_fts (cost=0.00..91.17 rows=10689 width=0) (actual time=0.014..0.014 rows=1 loops=1)
Index Cond: (to_tsvector('english'::regconfig, (data ->> 'content'::text)) @@ '''supercalifragilist'''::tsquery)
Planning Time: 0.144 ms
Execution Time: 0.037 ms
(8 rows)
Searching for the popular term is still quite fast, but noticeably slower.
pleroma=# explain analyze select id from objects where to_tsvector('english', data->>'content') @@ plainto_tsquery('english', 'nsfw') limit 10;
QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------------
Limit (cost=537.94..551.32 rows=10 width=4) (actual time=23.448..23.742 rows=10 loops=1)
-> Bitmap Heap Scan on objects (cost=537.94..87734.07 rows=65153 width=4) (actual time=23.447..23.739 rows=10 loops=1)
Recheck Cond: (to_tsvector('english'::regconfig, (data ->> 'content'::text)) @@ '''nsfw'''::tsquery)
Heap Blocks: exact=10
-> Bitmap Index Scan on objects_fts (cost=0.00..521.65 rows=65153 width=0) (actual time=16.004..16.004 rows=59266 loops=1)
Index Cond: (to_tsvector('english'::regconfig, (data ->> 'content'::text)) @@ '''nsfw'''::tsquery)
Planning Time: 0.165 ms
Execution Time: 23.974 ms
(8 rows)
Looks perfect. We quickly find our results, get 10 of them and display to user. Just one more change, the results should be ordered by descending date, because our users want to see the most recent stuff first - we are a social network, after all.
Searching and ordering by the rare term:
pleroma=# explain analyze select id from objects where to_tsvector('english', data->>'content') @@ plainto_tsquery('english', 'supercalifragilistic') order by inserted_at desc limit 10;
QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------------------------
Limit (cost=13754.89..13756.07 rows=10 width=12) (actual time=4.492..4.494 rows=1 loops=1)
-> Gather Merge (cost=13754.89..14978.93 rows=10344 width=12) (actual time=4.488..6.867 rows=1 loops=1)
Workers Planned: 3
Workers Launched: 3
-> Sort (cost=12754.85..12763.47 rows=3448 width=12) (actual time=0.156..0.156 rows=0 loops=4)
Sort Key: inserted_at DESC
Sort Method: quicksort Memory: 25kB
Worker 0: Sort Method: quicksort Memory: 25kB
Worker 1: Sort Method: quicksort Memory: 25kB
Worker 2: Sort Method: quicksort Memory: 25kB
-> Parallel Bitmap Heap Scan on objects (cost=93.84..12680.34 rows=3448 width=12) (actual time=0.101..0.101 rows=0 loops=4)
Recheck Cond: (to_tsvector('english'::regconfig, (data ->> 'content'::text)) @@ '''supercalifragilist'''::tsquery)
Heap Blocks: exact=1
-> Bitmap Index Scan on objects_fts (cost=0.00..91.17 rows=10689 width=0) (actual time=0.016..0.016 rows=1 loops=1)
Index Cond: (to_tsvector('english'::regconfig, (data ->> 'content'::text)) @@ '''supercalifragilist'''::tsquery)
Planning Time: 0.202 ms
Execution Time: 6.903 ms
No problem here.
Searching and ordering by the popular term:
pleroma=# explain analyze select id from objects where to_tsvector('english', data->>'content') @@ plainto_tsquery('english', 'nsfw') order by inserted_at desc limit 10;
QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------------------------------
Limit (cost=76136.95..76138.14 rows=10 width=12) (actual time=78.802..91.001 rows=10 loops=1)
-> Gather Merge (cost=76136.95..83937.90 rows=65152 width=12) (actual time=78.801..90.998 rows=10 loops=1)
Workers Planned: 4
Workers Launched: 4
-> Sort (cost=75136.89..75177.61 rows=16288 width=12) (actual time=75.029..75.029 rows=9 loops=5)
Sort Key: inserted_at DESC
Sort Method: top-N heapsort Memory: 25kB
Worker 0: Sort Method: top-N heapsort Memory: 25kB
Worker 1: Sort Method: top-N heapsort Memory: 25kB
Worker 2: Sort Method: top-N heapsort Memory: 25kB
Worker 3: Sort Method: top-N heapsort Memory: 25kB
-> Parallel Bitmap Heap Scan on objects (cost=537.94..74784.91 rows=16288 width=12) (actual time=20.261..73.576 rows=11853 loops=5)
Recheck Cond: (to_tsvector('english'::regconfig, (data ->> 'content'::text)) @@ '''nsfw'''::tsquery)
Heap Blocks: exact=19202
-> Bitmap Index Scan on objects_fts (cost=0.00..521.65 rows=65153 width=0) (actual time=13.891..13.891 rows=59266 loops=1)
Index Cond: (to_tsvector('english'::regconfig, (data ->> 'content'::text)) @@ '''nsfw'''::tsquery)
Planning Time: 0.179 ms
Execution Time: 91.032 ms
(18 rows)
And this is the part that the evil PostgreSQL search blog posters won’t tell you about. Here’s where it breaks down. Remember, this is one of the fastest desktop computers available, with the necassary data already in RAM. If you run this on your one CPU VPS at scaleway, this will most likely just time out.
But why does it get so slow? The problem here is that the index is not sorted by anything. So what it returns will just be a list of all the ids that match. To sort by inserted_at after that, it will need to fetch ALL the objects that match, which are around 60000 in this case, and THEN sort them. Quite a bad situation for any search term that matches a lot.
Solving the sorted results slowness
So what can you do to solve this? Well, one easy approach is to just not order the search results and just display whatever you get from the index. This is what Pleroma does at the moment if you are using the GIN index, which is the default.
Another rather interesting option for GIN indexes is the option called gin_fuzzy_search_limit. The makers of the index anticipated this problem and made it possible to instruct GIN to only return a random subset of the results. This leads to the rather strange behavior that, for terms that match a lot of posts, you’ll get a different set of results every time you search. Still, if your queries are timing out otherwise, this is a good quick fix.
Here’s an example with our slow query:
pleroma=# set gin_fuzzy_search_limit = 500;
SET
pleroma=# explain analyze select id from objects where to_tsvector('english', data->>'content') @@ plainto_tsquery('english', 'nsfw') order by inserted_at desc limit 10;
QUERY PLAN
-------------------------------------------------------------------------------------------------------------------------------------------------
Limit (cost=76136.95..76138.14 rows=10 width=12) (actual time=10.695..14.826 rows=10 loops=1)
-> Gather Merge (cost=76136.95..83937.90 rows=65152 width=12) (actual time=10.694..14.824 rows=10 loops=1)
Workers Planned: 4
Workers Launched: 4
-> Sort (cost=75136.89..75177.61 rows=16288 width=12) (actual time=7.084..7.085 rows=9 loops=5)
Sort Key: inserted_at DESC
Sort Method: top-N heapsort Memory: 25kB
Worker 0: Sort Method: top-N heapsort Memory: 25kB
Worker 1: Sort Method: top-N heapsort Memory: 25kB
Worker 2: Sort Method: top-N heapsort Memory: 25kB
Worker 3: Sort Method: top-N heapsort Memory: 25kB
-> Parallel Bitmap Heap Scan on objects (cost=537.94..74784.91 rows=16288 width=12) (actual time=3.680..6.904 rows=620 loops=5)
Recheck Cond: (to_tsvector('english'::regconfig, (data ->> 'content'::text)) @@ '''nsfw'''::tsquery)
Heap Blocks: exact=1617
-> Bitmap Index Scan on objects_fts (cost=0.00..521.65 rows=65153 width=0) (actual time=5.518..5.518 rows=3100 loops=1)
Index Cond: (to_tsvector('english'::regconfig, (data ->> 'content'::text)) @@ '''nsfw'''::tsquery)
Planning Time: 0.187 ms
Execution Time: 14.851 ms
(18 rows)
It’s fast again, even when ordered! But how many results does it actually return?
pleroma=# select count(*) from objects where to_tsvector('english', data->>'content') @@ plainto_tsquery('english', 'nsfw');
count
-------
3285
(1 row)
pleroma=# select count(*) from objects where to_tsvector('english', data->>'content') @@ plainto_tsquery('english', 'nsfw');
count
-------
3258
(1 row)
pleroma=# select count(*) from objects where to_tsvector('english', data->>'content') @@ plainto_tsquery('english', 'nsfw');
count
-------
3138
(1 row)
pleroma=# select count(*) from objects where to_tsvector('english', data->>'content') @@ plainto_tsquery('english', 'nsfw');
count
-------
3165
(1 row)
Wild! It’s a lot more than 500 and we also get a different amount each time. Still, it solves the problem, even if it behaves a bit strangely.
The alcoholic’s guide to FTS indexes: RUM
Once again, the smart index people knew that people would want to have it all, fast, accurate and complete results. So they took a trip to their local shop and came back with RUM. RUM indexes are very similar to GIN indexes, but they have a few new features:
- They support index-only scans
- They can do ranking purely using the index
- They can attach an extra piece of information to the index
The last thing is key here. We can build our RUM index and associate the inserted_at field with the index, so if we want to order by it, we’ll never have to look beyond the index!
Here’s the effect it has on the rare term:
pleroma=# explain analyze select id from objects where fts_content @@ plainto_tsquery('english', 'supercalifragilistic') order by now()::date <=> inserted_at limit 10;
QUERY PLAN
--------------------------------------------------------------------------------------------------------------------------------------
Limit (cost=8.80..19.80 rows=10 width=12) (actual time=0.039..0.040 rows=1 loops=1)
-> Index Scan using objects_fts on objects (cost=8.80..345095.85 rows=313700 width=12) (actual time=0.038..0.039 rows=1 loops=1)
Index Cond: (fts_content @@ '''supercalifragilist'''::tsquery)
Order By: (inserted_at <=> ((now())::date)::timestamp without time zone)
Planning Time: 0.224 ms
Execution Time: 0.061 ms
(6 rows)
And finally our problem child, the popular term, sorted by date:
pleroma=# explain analyze select id from objects where fts_content @@ plainto_tsquery('english', 'nsfw') order by now()::date <=> inserted_at limit 10;
QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------------------
Limit (cost=8.80..19.80 rows=10 width=12) (actual time=17.936..17.950 rows=10 loops=1)
-> Index Scan using objects_fts on objects (cost=8.80..345095.85 rows=313700 width=12) (actual time=17.935..17.948 rows=10 loops=1)
Index Cond: (fts_content @@ '''nsfw'''::tsquery)
Order By: (inserted_at <=> ((now())::date)::timestamp without time zone)
Planning Time: 0.218 ms
Execution Time: 17.972 ms
(6 rows)
Exactly what we wanted. As you can see, it doesn’t even have to touch anything but the index. So why not just use RUM instead of GIN every time? Well, RUM is not part of core PostgreSQL, but an extension. The indexes it builds are also a lot larger than the GIN indexes, because they contain more information. Still, overall they are the best solution to the problem.
Super Pro Tip for when your search suddenly is too slow even with indexes
The GIN index is very sensitive to the work_mem setting. If the setting is too low, the index will still work, but it will become a lossy index and lots of rows will have to be rechecked.
Here’s a search with work_mem = 655kb
pleroma=# explain analyze select count(*) from objects where to_tsvector('english', data->>'content') @@ plainto_tsquery('english', 'cofe');
NOTICE: word is too long to be indexed
DETAIL: Words longer than 2047 characters are ignored.
NOTICE: word is too long to be indexed
DETAIL: Words longer than 2047 characters are ignored.
QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------------------------------
Finalize Aggregate (cost=1729421.89..1729421.90 rows=1 width=8) (actual time=770.379..770.379 rows=1 loops=1)
-> Gather (cost=1729421.68..1729421.89 rows=2 width=8) (actual time=770.208..776.522 rows=3 loops=1)
Workers Planned: 2
Workers Launched: 2
-> Partial Aggregate (cost=1728421.68..1728421.69 rows=1 width=8) (actual time=743.782..743.782 rows=1 loops=3)
-> Parallel Bitmap Heap Scan on objects (cost=93.84..1728410.54 rows=4454 width=0) (actual time=57.359..743.286 rows=8332 loops=3)
Recheck Cond: (to_tsvector('english'::regconfig, (data ->> 'content'::text)) @@ '''cofe'''::tsquery)
Rows Removed by Index Recheck: 72094
Heap Blocks: exact=1104 lossy=7298
-> Bitmap Index Scan on objects_fts (cost=0.00..91.17 rows=10689 width=0) (actual time=15.809..15.809 rows=24995 loops=1)
Index Cond: (to_tsvector('english'::regconfig, (data ->> 'content'::text)) @@ '''cofe'''::tsquery)
Planning Time: 0.202 ms
JIT:
Functions: 17
Options: Inlining true, Optimization true, Expressions true, Deforming true
Timing: Generation 2.253 ms, Inlining 80.641 ms, Optimization 54.557 ms, Emission 18.036 ms, Total 155.488 ms
Execution Time: 777.608 ms
(17 rows)
Super slow! Here’s the same one with work_mem = 20971kB.
pleroma=# explain analyze select count(*) from objects where to_tsvector('english', data->>'content') @@ plainto_tsquery('english', 'cofe');
QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------------------------
Finalize Aggregate (cost=13689.28..13689.29 rows=1 width=8) (actual time=28.208..28.208 rows=1 loops=1)
-> Gather (cost=13688.96..13689.27 rows=3 width=8) (actual time=28.010..30.311 rows=4 loops=1)
Workers Planned: 3
Workers Launched: 3
-> Partial Aggregate (cost=12688.96..12688.97 rows=1 width=8) (actual time=24.763..24.763 rows=1 loops=4)
-> Parallel Bitmap Heap Scan on objects (cost=93.84..12680.34 rows=3448 width=0) (actual time=8.597..24.400 rows=6249 loops=4)
Recheck Cond: (to_tsvector('english'::regconfig, (data ->> 'content'::text)) @@ '''cofe'''::tsquery)
Heap Blocks: exact=7106
-> Bitmap Index Scan on objects_fts (cost=0.00..91.17 rows=10689 width=0) (actual time=6.878..6.878 rows=24995 loops=1)
Index Cond: (to_tsvector('english'::regconfig, (data ->> 'content'::text)) @@ '''cofe'''::tsquery)
Planning Time: 1.769 ms
Execution Time: 30.371 ms
And it’s fine again! Check out something like PGTune to figure out good values for your server.
TL;DR ~~~~ LESSONS LEARNED ~~~~
Postgres search works quite well and is a good alternative to external solutions for a lot of cases. Just remember these:
- Keep your
work_memtuned - Use an index
- Use RUM if you can
- If you use GIN and want ranking and sorting, use
gin_fuzzy_search_limit
That’s it for today! See ya next time!