What does the word "SARGable" really mean?

Question

SQL Server users use the term "sargable". I'm wondering if there is an objective implementation-agnostic timeless definition for "sargable."

For instance, WHERE foo LIKE '%bar%' is said by many to be not sargable, but some RDBMSs are able to use indexes on such queries. What then does "not sargable" mean?

Other References

• What makes a SQL statement sargable?

Answer 1

The term "sargable" was first introduced by P. Griffiths Selinger et al. in their 1979 paper "Access Path Selection in a Relational Database Management System", published by ACM. For non-ACM members there's a copy of that paper at http://cs.stanford.edu/people/chrismre/cs345/rl/selinger.pdf

The term is defined in this paragraph:

Both index and segment¹ scans may optionally take a set of predicates, called search arguments (or SARGS), which are applied to a tuple before it is returned to the RSI² caller. If the tuple satisfies the predicates, it is returned; otherwise the scan continues until it either finds a tuple which satisfies the SARGS or exhausts the segment or the specified index value range. This reduces cost by eliminating the overhead of making RSI calls for tuples which can be efficiently rejected within the RSS. Not all predicates are of the form that can become SARGS. A sargable predicate is one of form (or which can be put into the form) "column comparison-operator value". SARGS are expressed as a boolean expression of such predicates in disjunctive normal form.

In other words, a sargable predicate is such that can be resolved by the storage engine (access method) by directly observing the table or index record. A non-sargable predicate, conversely, requires a higher level of the DBMS to take action. For example, the outcome of WHERE lastname = 'Doe' can be decided by the storage engine by simply looking at the contents of the field lastname of each record. On the other hand, WHERE UPPER(lastname) = 'DOE' requires execution of a function by the SQL engine, which means the storage engine will have to return all rows it reads (provided they match possible other, sargable predicates) back to the SQL engine for evaluation, incurring additional CPU costs.

You can see from the original definition that sargable predicates can apply not only to index scans, but also to table (segment in System R terminology) scans, as long as the conditions "column comparison-operator value" are met and therefore they can be evaluated by the storage engine. This is indeed the case with Db2, a descendant of System R in many ways:

Index sargable predicates are not used to bracket a search, but are evaluated from the index if one is chosen, because the columns involved in the predicate are part of the index key. These predicates are also evaluated by the index manager.

Data sargable predicates are predicates that cannot be evaluated by the index manager, but can be evaluated by Data Management Services (DMS). Typically, these predicates require the access of individual rows from a base table. If necessary, DMS will retrieve the columns needed to evaluate the predicate,

The fact that in SQL Server-speak sargable predicates are only those that can be resolved using index seeks is probably determined by its storage engine's inability to apply such predicates during table scans.

Sargable and non-sargable predicates are sometimes described as "stage 1" and "stage 2" predicates respectively (this also comes from Db2 terminology). Stage 1 predicates can be evaluated at the lowest level of query processing, while reading table or index records. Rows that match stage 1 conditions, if any, are sent to the next level, stage 2, of evaluation.

---

¹ -- Segment in System R is the physical storage of a table's tuples; a segment scan is somewhat equivalent to a table scan in other DBMSes.

² -- RSI -- RSS³ Interface, a tuple-oriented query interface. The interface function relevant to this discussion is NEXT, which returns the next row matching query predicates.

³ -- RSS, or Research Storage System, the storage subsystem of System R.

Answer 2

For me, SARGable means that SQL Server can perform an index seek using your search predicates.

You can't just say the DBMS can "take advantage" of an index, because with a non-sargable predicate, SQL Server may end up scanning a nonclustered index.

Answer 3

According to Pro SQL Server Internals by Dmitri Korotkevitch:

A Search ARgument ABLE predicate is one where SQL SERVER can utilize an index seek operation, if an index exists.

A SARGable predicate is one where SQL server can isolate the single value or range of index key values to process

SARGable predicates include the following operators: =, >, >=, <, <=, IN, BETWEEN, and LIKE (in the case of prefix matching)

Non-SARGable operators include: NOT, NOT IN, <>, and LIKE (not prefix matching), as well as the use of functions or calculations against the table, and type conversions where the datatype does not fulfill the index created.

Example:

WHERE name like 'SARGable%'
WHERE name like '%non-SARGable%'

Demo:

DROP TABLE dbo.Testing;
GO

CREATE TABLE Testing (
    WeirdDatatype   int NOT NULL,
    SomethingElse   char(200)
);

CREATE NONCLUSTERED INDEX IDX_ALWAYS_SARGable
    ON dbo.Testing( SomethingElse);

CREATE NONCLUSTERED INDEX IDX_NOT_ALWAYS_SARGable
    ON dbo.Testing(SomethingElse);

INSERT INTO dbo.Testing
        ( WeirdDatatype, SomethingElse )
SELECT TOP 1000 m.message_id, CONVERT(char(200), m.text)
FROM sys.messages AS m;

Now we run:

SELECT *
FROM dbo.Testing AS t
WHERE  t.WeirdDatatype = 1001;
SELECT *
FROM dbo.Testing AS t
WHERE t.SomethingElse LIKE 'Line%'
SELECT *
FROM dbo.Testing AS t
WHERE t.SomethingElse LIKE '%Line%'
     AND t.WeirdDatatype = 1001;

The results are:

Let's look at the properties of the SARGable query (Index Seek)

The query optimizer is able to define a limit in the index of a start and end. It has a search argument to query with.

Now the non-SARGable query:

You can see with the beginning of the predicate '%non..%' does not allow the query optimizer to DEFINE a begin and end or range in the index. It must now search the whole table (scan).