1

I've been reading through this excellent answer to understand how pg_trgm works a bit, but I'm still unclear on the most efficient way of solving this query (efficient in terms of speed of search):

I have a table search that I run trigram searches on that looks like this:

Column      |  Type   | Modifiers
------------+---------+-----------
id          | bpchar  | collate C
user_id     | integer |
type        | text    |
search_on   | text    | collate C
data        | json    |
Indexes:
 "index_search_id" UNIQUE, btree (id)
 "index_search_search_on" gist (search_on gist_trgm_ops)
 "index_search_type" btree (type)
 "index_search_user_id" btree (user_id)

In this scenario, user_id is NULLable and type is also NULLable. The queries I'd run amount to these possibilities:

  1. Search for rows (WHERE user_id = 123 OR user_id IS NULL) AND search_on % 'mystring'
  2. Search for rows (WHERE user_id = 123 OR user_id IS NULL) AND type='my-type' AND search_on % 'mystring'

In plain words, I want all rows that have my user_id or NULL user_id, optionally are categorized by type, and match the term being passed in.

Right now I just have individual indexes on the 3 columns (as shown above) that can change based on the query. I understand however that a single index is generally more efficient.

Is it possible to use a single index that does trigram searches, but also exact match on user_id and type where they can optionally be NULL.

1
  • I assume you mean WHERE ( user_id = 123 OR user_id IS NULL ) AND search_on % 'mystring'? You need parentheses to keep AND binding before OR. – Erwin Brandstetter May 14 '18 at 2:43
1

Is it possible to use a single index that does trigram searches, but also exact match on user_id and type where they can optionally be NULL.

Yes, NULL is included in indexes. And you can search for it like for any other value.

Yes, you can have a multicolumn trigram GiST index. But GiST indexes typically don't make sense for the data type integer. Btree indexes are better in every respect - except for your case of a multicolumn index. So Postgres does not install the required operator class by default. You need to install the additional module btree_gist first, once per database:

CREATE EXTENSION IF NOT EXISTS btree_gist;  -- only if not installed, yet

Then you can create your multicolumn index:

CREATE INDEX foo ON search USING gist (user_id, type, search_on gist_trgm_ops);

Related (with detailed instructions):

And get operator precedence in your WHERE clause right:

WHERE (user_id = 123 OR user_id IS NULL)  -- parentheses!
AND    search_on % 'mystring'

Or:

WHERE (user_id = 123 OR user_id IS NULL)
AND   (type = 'my-type' OR type IS NULL)
AND    search_on % 'mystring'

Depending on data distribution, cardinalities, selectivity of predicates, cost settings etc. Postgres may still prefer an index on one (or two) column(s) (occasionally).

7
  • 1
    While NULL values are supported in indexes in general, the way btree_gist in particular supports them is rather disgraceful. He is quite unlikely to find the multi-column gist index to outperform the three independent indexes, unless he recodes his data so that it uses a dummy non-NULL value rather than NULL. – jjanes May 14 '18 at 14:05
  • 1
    Actually it appears to the entire GiST framework, not just btree_gist, which can't cope gracefully with NULLs. – jjanes May 14 '18 at 20:21
  • @jjanes: That's bad news. I didn't test performance with NULL values in particular. Would you happen to have a link to more info on this? – Erwin Brandstetter May 15 '18 at 1:54
  • @brad: Since you have a use case at hand: Could you test performance with the suggested index with user_id = 123 and user_id IS NULL? – Erwin Brandstetter May 15 '18 at 1:58
  • Just my own experimentation. There is this somewhat cryptic comment in the code "On non-leaf page we can't conclude that child hasn't NULL values because of assumption in GiST: union (VAL, NULL) is VAL." It seems like that assumption should be explained elsewhere as well in more depth, but I can't find it. – jjanes May 15 '18 at 2:34
1

Sorry for the delay on this one. I'm not sure if protocol dictates that I answer my own question to post these details, but comments (to Erwin's answer) don't provide enough space.

So I was noticing pretty poor performance using the above individual indexes when I'd run queries. I have 2 main uses cases:

  1. Query for all things in the 'public sphere' or my own: (user_id = 123 OR user_id IS NULL) AND search_on % 'my_string'
  2. Query for all things by type, in the 'public sphere' or my own (user_id = 123 OR user_id IS NULL) AND type='my-type' AND search_on % 'mystring'

I forgot to mention that type IS NOT NULL in all of this, so there's never a case where I want to fetch NULL typed rows, only NULL user_id rows.

Using the separate indexes from the original post, I'd see queries taking anywhere from 1s to 10+s. It seemed as if "warming up" and running a few queries would bring the time down, but even 1 second is insufficient for a typeahead without negatively affecting the UX.

Playing with Erwin's suggestions, I added first:

CREATE INDEX idx_typed_search ON search USING gist (user_id, type, search_on gist_trgm_ops);

And ran both typed and non-typed queries. The typed queries were insanely fast (~ 50 ms) and the non-typed were still pretty slow, but definitely faster than the original posting with separate indexes (~ 400 ms)

Then I added:

CREATE INDEX idx_search ON search USING gist (user_id, search_on gist_trgm_ops);

and ran both typed and non-typed queries. As expected, typed queries weren't affected, they used the other index, but non-typed queries actually got worse (~ 1000+ ms). Dropping that index brought them back down to (~ 400ms)

So I wasn't sure if it was the presence of two potentially competing indexes to choose from that caused performance issues. Since I'm absolutely satisfied with the typed indexing (~ 50ms is roughly the speed I was hoping for) I decided to focus just on the untyped queries.

With no indexes, the baseline query using a sequence scan runs in about 8s (roughly 700,000 total rows)

With the individual btree index on user_id plus the gist_trgm on search_on, the performance is in the 400ms range. Interestingly it never uses the user_id index, because by the time it index scans on the search term, there's probably only a few rows to filter out from other user_ids (given my current data). This could likely change over time with more user data though, so I think the user_id index still makes sense even though its unused in this case.

With the combined gist (user_id, search_on) index, I get performance roughly similar to the 2 separate indexes (~ 400ms)

I should mention that the shape of the data is such that there would be 100's of records owned by each user_id, but 100's of 1000's (a majority) of records in the 'public sphere' (user_id IS NULL).

Given that data shape, it seems best to simply optimize for the search term and type themselves, as the user_id filtering at the end of the query is cheap.

Since a specific non-typed index doesn't actually yield any performance benefit, it seems the best option is to stick with a single gist index on the type and search_on columns only:

CREATE INDEX idx_typed_global_search ON searchables USING gist (type, search_on gist_trgm_ops);

I don't have enough users currently to test the user_id filtering, but my guess is that as we grow our user base, an index on user_id would yield fruit.

1
  • Thanks for the follow-up. No big surprises, but interesting & useful in any case. – Erwin Brandstetter Jul 18 '18 at 9:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.