Finding Applicable Indexes

To find applicable indexes, the query processor looks at the conditions in the WHERE clause, trying to "match" such predicates with the index paths that define each index and convert the matched predicates to index search conditions. In general the WHERE clause consists of one or more conditions connected with AND or OR operators, forming a tree whose leaves are the conditions and whose internal nodes are the AND/OR operators. Let a predicate be any subtree of this WHERE-clause tree. The query processor will consider only top-level AND predicates, i.e., predicates that appear as the operands of a root AND node. If the WHERE clause does not have an AND root, the whole WHERE expression is considered a single top-level AND predicate. Notice that the query processor does not currently attempt to reorder the AND/OR tree in order to put it in conjunctive normal form. On the other hand, it does flatten the AND/OR tree so that an AND node will not have another AND node as a child, and an OR node will not have another OR node as a child. For example, the expression a = 10 and b < 5 and (c > 10 or c < 0) has 3 top-level AND predicates: a = 10, b < 5, and (c > 10 or c < 0), whereas the expression a = 10 and b < 5 and c > 10 or c < 0 has an OR as its root and the whole of it is considered as a single top-level AND predicate. For brevity, in the rest of this section we will use the term "predicate" to mean top-level AND predicate.

The query processor will also look at the expressions in the ORDER BY and GROUP BY clauses in order to find sorting indexes, that is, indexes that sort the table rows according to the expressions appearing in these clauses. As explained in sections GROUP BY Clause and ORDER BY Clause,, use of a sorting index will result in more efficient and memory-sparing sorting and grouping.

The query processor will consider an index applicable to a query if the index is a sorting one or if the query contains at least one index predicate: a predicate that can be evaluated during an index scan, using the content of the current index entry only, without the need to access the associated table row. Index predicates are further categorized as start/stop predicates or filtering predicates. A start/stop predicate participates in the establishment of the first/last index entry to be scanned during an index scan. A filtering predicate is applied during the index scan on the entries being scanned. In the current implementation, the following kinds of predicates are considered as candidate start/stop predicates:

comparisons, using either the value or sequence (any) comparison operators, but not != or !=any,
IS NULL and IS NOT NULL operators,
EXISTS and NOT EXISTS predicates, and
IN predicates

However, if an index is created with the WITH NO NULLS clause, IS NULL and NOT EXISTS predicates cannot be used as index predicates for that index. In fact, such an index can be used by a query only if the query has an index predicate for each of the indexed fields.

An index is called a covering index with respect to a query if the query can be evaluated using only the entries of that index, that is, without the need to retrieve the associated rows.

If an index is used in a query, its index predicates are removed from the query because they are evaluated by the index scan. We say that index predicates are "pushed to the index". In the rest of this section we explain applicable indexes further via a number of example queries, and using the non-json indexes from the Appendix. The algorithm for finding applicable json indexes is essentially the same as for non-json indexes. The same is true for geometry indexes, with the exception that geosearch predicates that are pushed to the index are not removed from the query, because they need to stay there to eliminate false positive results from the index scans.