Making Queries Sargable

Introduction

When tuning database queries, a common technique is to add indexes that are tailor made to improve the performance of that query. However, sometimes, the query you are analyzing is written in such a way that it will not take advantage of indexes, even if they are in place.

The term used to describe whether a query is written in a way where it can take advantage of indexes is "sargable" -- it is an abbreviation for "search ARGument ABLE" (definition). That is, a query is said to be sargable if it can leverage an index.

Example

An example should help us here. Suppose we have an event_log table which stores millions of records and we want to be able to SELECT data from this log table based on a few simple predicates.

Let's create a table in CockroachDB with 10 million rows and some randomized data like this:

CREATE DATABASE IF NOT EXISTS sarg; 
USE sarg;
CREATE TABLE event_log ( id PRIMARY KEY, message, log_ts )
AS
SELECT
  g.i AS id,
  md5(random()::text) AS message,
  g.i::TIMESTAMP as log_ts
FROM generate_series(1668003200, 1678003200, 1) g(i);
-- 10,000,000 records
-- between 2022-11-09 14:13:20+00 (i.e., 1668003200)
-- and 2023-03-05 08:00:00 (i.e., 1678003200)

Now, let's create a decidedly non-sargable query to find log entries within a certain day and containing a certain log message:

SELECT *
FROM event_log
WHERE message LIKE '%abc%'
AND CAST(log_ts AS date) = CAST('2023-02-01' AS date);

      id     |             message              |       log_ts
-------------+----------------------------------+----------------------
  1675209983 | 813cdbec6ab76abc470cc19e42975692 | 2023-02-01 00:06:23
  1675210237 | 41963851207539abc612869eb5cf2301 | 2023-02-01 00:10:37(0 rows)
-- rows omitted for brevity --
(570 rows)

Time: 10.466s total (execution 10.466s / network 0.000s)

This query takes 10 seconds to run. Not good. Let's look at the query plan:

EXPLAIN SELECT *
FROM event_log
WHERE message LIKE '%abc%'
AND CAST(log_ts AS date) = CAST('2023-02-01' AS date);

                                            info
---------------------------------------------------------------------------------------------
  distribution: full
  vectorized: true

  • filter
  │ estimated row count: 1,111,111
  │ filter: (message LIKE '%abc%') AND (log_ts::DATE = '2023-02-01')
  │
  └── • scan
        estimated row count: 10,000,001 (100% of the table; stats collected 23 minutes ago)
        table: event_log@event_log_pkey
        spans: FULL SCAN
(11 rows)

We're committing the cardinal sin on non-scalable database performance -- we're doing a full scan of the table and then we're filtering for our predicate in memory. This means that as the size of the table grows, the query will get slower and slower because we have to read every record of the table every time the query runs.

Also, it's worth noting that our explain plan didn't contain any index hints (further evidence that our query is to blame here).

Just to further show that we've got a non-sargable query, let's add indexes to the message and log_ts fields to see if we can improve the execution.

CREATE INDEX ON event_log ( message );
CREATE INDEX ON event_log ( log_ts );

After adding these indexes, the query plan looks exactly the same. We have a non-sargable query on our hands.

Non-sargable patterns

There are two classic anti-patterns being used by this query contributing to it being non-sargable:

• applying functions to the left side of the predicate
• using a leading wildcard in a LIKE expression

Fixing functions on the left-side of the predicate

Let's see how we can change our query by addressing the first anti-pattern. In our query, we're trying to limit the results to only give us log entries from Feb 1, 2023. Logically, our predicate gives us the right results; but anytime you run a query with a function on the left-hand side of the predicate (i.e., the field itself), you're limiting the SQL optimizer's ability to leverage indexes. To fix this, let's employ some different logic that works without applying functions to the left-hand side of the predicate.

Instead of:

CAST(log_ts AS date) = CAST('2023-02-01' AS date)

let's do:

log_ts >= '2023-02-01' AND log_ts < '2023-02-02'

Running this edited version of the query, we get our results back in ~800ms instead of 10s+.

SELECT *
FROM event_log
WHERE message LIKE '%abc%'
AND log_ts >= '2023-02-01' AND log_ts < '2023-02-02';

      id     |             message              |       log_ts
-------------+----------------------------------+----------------------
-- rows omitted for brevity --
  1675295883 | 508472e48f1d4121d56ba36cfdabc147 | 2023-02-01 23:58:03
  1675295922 | 179a0abc7e6b8653f89be8cf875bc789 | 2023-02-01 23:58:42
(570 rows)

Time: 836ms total (execution 834ms / network 2ms)

Let's look at the query plan to see what's changed:

EXPLAIN
SELECT *
FROM event_log
WHERE message LIKE '%abc%'
AND log_ts >= '2023-02-01' AND log_ts < '2023-02-02';

--------------------------------------------------------------------------------------------------------------------------------------
  distribution: local
  vectorized: true

  • filter
  │ estimated row count: 30,670
  │ filter: message LIKE '%abc%'
  │
  └── • index join
      │ estimated row count: 92,011
      │ table: event_log@event_log_pkey
      │
      └── • scan
            estimated row count: 92,011 (0.92% of the table; stats collected 19 minutes ago; using stats forecast for 7 minutes ago)
            table: event_log@event_log_log_ts_idx
            spans: [/'2023-02-01 00:00:00' - /'2023-02-01 23:59:59.999999']

  index recommendations: 1
  1. type: index replacement
     SQL commands: CREATE INDEX ON event_log (log_ts) STORING (message); DROP INDEX event_log@event_log_log_ts_idx;
(19 rows)

This is better! We're now able to leverage the event_log_log_ts_idx index. Our plan uses this first index to filter the number of records to process, then it joins back to the primary index (i.e, the table itself) and then it does the final filter on the message field. By the time this final filter is applied, we've already narrowed down the possible result set to 30k records, so this isn't terrible, but let's see if we can improve further.

NOTE: there are some further indexing recommendations in that last query plan which we could employ to help our query performance more, but they're not related to sargability, so I'm not going to follow that bunny trail in this blog.

Fixing leading wildcards

The second non-sargable mistake we've made is to use a leading wildcard in a LIKE expression (i.e., message LIKE '%abc%'). If we had only used a wildcard at the end of the expression (i.e., message LIKE 'abc%'), then the query engine could still have leveraged the index (try looking at the query plan for this query and see for yourself); but when you put a wildcard at the beginning of the expression, the index can't be leveraged because we can't seek to specific ranges of the ordered index.

This is a classically hard problem to overcome in relational databases (it's exactly the kind of use cases that search engines like Solr and ElasticSearch are built to solve). If the requirements for our query are to look in the middle of a text string, then we can't change the query to not having a leading wildcard. We have a few choices then.

Ngram indexes

One choice is to do what we've done above and use indexes on other parts of our predicate to limit the result set so that the impact of the actual string filter is minimized. That would be a boring solution for a blog! So, let's remove that option by getting rid of the date/time filter in our query.

If we only filter by the message field, we're back to our full table scan (and our 10sec performance).

EXPLAIN
SELECT *
FROM event_log
WHERE message LIKE '%abc%';

--------------------------------------------------------------------------------------------------------------------------------------
  distribution: full
  vectorized: true

  • filter
  │ estimated row count: 3,333,334
  │ filter: message LIKE '%abc%'
  │
  └── • scan
        estimated row count: 10,000,001 (100% of the table; stats collected 30 minutes ago; using stats forecast for 18 minutes ago)
        table: event_log@event_log_pkey
        spans: FULL SCAN
(11 rows)

The next option that we have to deal with this is to leverage an n-gram index. An n-gram is a tokenization of a piece of text into "chunks" that are of length n. For example, if we tokenize the phrase "hello world" into tokens of size 3, we end up with the following values:

• "hel"
• "ell"
• "llo"
• "lo "
• "o w"
• " wo"
• "wor"
• "orl"
• "rld"

CockroachDB has a feature called trigram indexes which leverages this tokenization technique. At write time, when the index is being built, the values are broken down into 3-grams (i.e., trigrams) and these multiple values are stored. Then, at query-time, the query optimizer is able to do a seek against these values instead of having to scan the table. There is a trade-off at play here: we're doing more work at write time & storing more data in our index (potentially a lot more); but we're reducing the work that has to be done at query time.

Let's create a trigram index on our message field and see how our performance is impacted:

CREATE INDEX ON event_log USING GIN(message gin_trgm_ops);

EXPLAIN
SELECT *
FROM event_log
WHERE message LIKE '%abc%'
LIMIT 500;

info
--------------------------------------------------------------------------------------------------------------------------------------------------------------
  distribution: local
  vectorized: true

  • render
  │
  └── • limit
      │ count: 500
      │
      └── • filter
          │ estimated row count: 3,333,334
          │ filter: message LIKE '%abc%'
          │
          └── • index join
              │ estimated row count: 1,111,111
              │ table: event_log@event_log_pkey
              │
              └── • scan
                    estimated row count: 167 - 1,111,112 (11% of the table; stats collected 1 minute ago; using stats forecast for 28 minutes in the future)
                    table: event_log@event_log_message_idx1
                    spans: 1 span
(20 rows)

Let's run the query and see how long it takes:

SELECT *
FROM event_log
WHERE message LIKE '%abc%'
LIMIT 500;

Time: 43ms total (execution 34ms / network 9ms)

Pretty good!

Computed Columns

Another approach that we could use to handle this situation is to add a computed column to our table which calculates whether our keyword has been seen.

ALTER TABLE event_log
ADD COLUMN contains_abc boolean
AS ( message LIKE '%abc%' ) STORED;
CREATE INDEX ON event_log ( contains_abc );

SELECT id, message, log_ts
FROM event_log
WHERE contains_abc = true
LIMIT 500;

Time: 23ms total (execution 16ms / network 7ms)

This seems to be even a little faster which makes sense since the work done at read time is very minimal (even compared to the trigram approach). Conceptually, it's a similar approach in that we're doing some extra work at write time in order to speed things up at read time. It's a little more precise (i.e., it stores less data), but it's less flexible (i.e., you can't change the string you're searching on without changing the computed column).

Summary

We've identified a few red flags to watch out for in queries that will render them non-sargable. And, we've looked at ways to address specific instances of this problem.