Loose indexscan
"Loose indexscan" in MySQL and Cockroach, and "Hybrid Scan" in YugabyteDB are names used for an operation that finds distinct values of the leading columns of a btree index efficiently; rather than scanning all equal values of a key, as soon as a new value is found, restart the search by looking for a larger value. This is much faster when the index has many equal keys.
Loose Indexscan versus Index Skip Scan
Although they apply similar techniques, Loose Indexscans and Index Skip Scans describe two different optimizations. Below a comparison table.
| Loose Indexscan | Index Skip Scan | |
|---|---|---|
| Returns | Results for grouping sets, often DISTINCT values | All matching rows for a predicate, can easily return more than one rows with same value |
| Limitations | Requires the use of a prefix of columns in the index as grouping key | Works on any selection of columns in the index, with filters on any subset of columns of the index |
| Information for skipping values must be provided | During scan execution, or (with limitations) before query execution | Before scan execution |
| Example |
SELECT DISTINCT user_id FROM orders; -- common
SELECT user_id
FROM orders
GROUP BY user_id
HAVING count(*) > 10; -- Uncommon / nonexistent
|
CREATE INDEX ON orderlines (order_id, product_id);
SELECT order_id,
product_option
FROM orderlines
WHERE product_id IN (2, 11, 23);
|
| DB Engine | Loose Indexscan | Index Skip Scan |
|---|---|---|
| PostgreSQL |
No |
No |
| MySQL |
Yes, with limitations |
|
| Oracle | ||
| DB2 | ||
| SQLite | ||
| CockroachDB |
Yes, with limitations |
|
| YugabyteDB |
Yes, with limitations |
Selecting Distinct Values
Postgres does not support Loose Index Scan natively (though plans are afoot), but they can be emulated using a recursive CTE as follows:
WITH RECURSIVE t AS (
SELECT min(col) AS col FROM tbl
UNION ALL
SELECT (SELECT min(col) FROM tbl WHERE col > t.col)
FROM t WHERE t.col IS NOT NULL
)
SELECT col FROM t WHERE col IS NOT NULL
UNION ALL
SELECT null WHERE EXISTS(SELECT 1 FROM tbl WHERE col IS NULL);
The recursive part of the query processes one new row in each pass, finding the smallest column value greater than that on the previous pass; the main query adds in a single null result if needed. The above query is therefore equivalent to
SELECT DISTINCT col FROM tbl;
but runs orders of magnitude faster when "col" has only a proportionally small number of distinct values.
If col IS NOT NULL
If col is defined NOT NULL the query can be simplified.
Also using alternative syntax with ORDER BY / LIMIT 1, which typically results in a simpler (and faster) query plan:
WITH RECURSIVE t AS (
(SELECT col FROM tbl ORDER BY col LIMIT 1) -- parentheses required
UNION ALL
SELECT (SELECT col FROM tbl WHERE col > t.col ORDER BY col LIMIT 1)
FROM t
WHERE t.col IS NOT NULL
)
SELECT col FROM t WHERE col IS NOT NULL;
SQL fiddle (Postgres 9.3) demonstrating both.
Making use of a non-leading column of an index
The same technique can be used to allow a query to benefit from an index which has a leading column with few distinct values (and which would not naturally be specified in the query), and a 2nd column which is highly specific and is used by the query. The leading column can be introduced into the query in a way which does not alter the meaning.
To set up the example:
CREATE TABLE tbl (col integer NOT NULL, col2 integer NOT NULL);
INSERT INTO tbl
SELECT trunc(random()*5) AS col, (random()*1000000)::int AS col2 FROM generate_series(1,10000000);
CREATE INDEX ON tbl (col, col2);
The natural specification of the query, which typically doesn't use the index takes 1758 ms:
SELECT count(*) FROM tbl WHERE col2 = 9854;
The modified version can benefit from the index and runs in 2 ms:
SELECT count(*) FROM tbl WHERE col2 = 9854 AND col IN
(
WITH RECURSIVE
t AS (SELECT min(col) AS col FROM tbl
UNION ALL
SELECT (SELECT min(col) FROM tbl WHERE col > t.col) FROM t WHERE t.col IS NOT NULL)
SELECT col FROM t
);
A correct version of this query would be much more complex if col could be NULL.
