Postgres has many different types of scans builtin. The list includes sequential scans, index scans, and bitmap scans. One useful scan type Postgres does not have builtin that other databases do is the loose index scan. Both MySQL and Oracle support loose index scans. Fortunately for Postgres users, loose index scans can be emulated through a recursive CTE.

At a high level, the idea behind the loose index scan is that rows necessary for the query are at predictable locations in the index. All of the index scans Postgres currently supports requires reading all of the values from the index between two values. Although Postgres does not do it, for certain queries it is possible to skip over large parts of the index because it is possible to determine that values in that part of the index do not affect the result of the query. For a specific example, let’s say we want to calculate the number of distinct elements in a table:

CREATE TABLE ints (n BIGINT);

INSERT INTO ints SELECT floor(random() * 10)
FROM generate_series(1, 10000000);

CREATE INDEX ON ints (n);

EXPLAIN ANALYZE SELECT COUNT(DISTINCT n) FROM ints;

This example creates a table with 10,000,000 rows, all of which contain a random number from 0 to 9. Then it counts the number of distinct elements using a naive COUNT(DISTINCT n). The plan for the query is available here.

As you can see from the query plan, using a naive COUNT(DISTINCT n) takes six seconds. Of this time, 650 milliseconds is used to read the data from disk while the rest of the time is used to perform the aggregation and determine how many distinct elements there are. A sequential scan is only performed because the query requires reading all of the rows from the database and a sequential scan is the fastest way to do it.

Most of the work Postgres is doing for this query is unnecessary. For example, once Postgres sees a row with a zero, it knows all other rows that contain a zero will not affect the result. With this idea in mind, we can write the following query which performs a loose index scan:

> EXPLAIN ANALYZE
> WITH RECURSIVE temp (i) AS (
>     (SELECT n FROM ints ORDER BY n ASC LIMIT 1)
>   UNION ALL
>     (SELECT n FROM temp, 
>                    LATERAL (SELECT n
>                             FROM ints
>                             WHERE n > i
>                             ORDER BY n ASC
>                             LIMIT 1) sub)
> )
> SELECT COUNT(*) FROM temp;

The plan is available here.

This new query takes less than one millisecond! Let’s try dissecting this query. First of all, this query makes use of a recursive CTE. If you aren’t familiar with how to interpret recursive CTEs, I suggest you read my blog post on how to understand recursive CTEs. The first part of the recursive CTE is:

SELECT n FROM ints ORDER BY n ASC LIMIT 1

This simply gets the smallest number from the table. As for the recursive part of the recursive CTE:

SELECT n FROM temp, 
              LATERAL (SELECT n
                       FROM ints
                       WHERE n > i
                       ORDER BY n ASC
                       LIMIT 1) sub

This query takes the current element in the working table and uses a lateral join to fetch the smallest element greater than the current element. In other words, the next largest element. By first fetching the smallest value in the table and then repeatedly fetching the next largest, the recursive CTE selects the distinct elements from the table! From there, we just need to count the number of distinct elements to determine the number of distinct elements in the table.

By using an index to find each element, only a single index scan needs to be performed per distinct element. Since there are only 10 distinct elements in the table, only 10 index scans need to be performed¹. The loose index scan is so much faster than the regular aggregation because once it sees a given value, it skips over all other rows with the same value.

Besides counting the number of distinct elements in a table, there is one other main use case where loose index scans are helpful: if you ever want to calculate the min of one column grouped by another column. If you have a specific value of the column you are grouping by, you can use a compound index on (grouping column, other column) to quickly find the smallest value of the other column for that one value. By iterating over the distinct values of the column you are grouping by, you can answer the query fairly quickly. Without using a loose index scan here, the query would read entire table, which as we already know, is pretty slow.

1. An 11th is actually needed to determine there is no element greater than 9.