In the previous article I
have taken advantage of the technique of extracting distinct values from
an indexed column efficiently. The technique is so commonly used that
many blog posts have introduced it. According to Jonathan Lewis, Sayan
Malakshnov,a Russian, was one of those suspected developers who first
found the strategy.
http://orasql.org/2012/09/21/distinct-values-by-index-topn/
In this note, I will explain how to find all the distinct combinations for the first two columns of a very large index in PostgreSQL without having to scan and aggregate the whole index or table. The
solution in this note was worked out by Jonathan Lewis. I've tried to
come up with a better solution than his, but I couldn't.
Let's start with a suitable table and index.
DROP TABLE T1;
CREATE TABLE T1
AS
SELECT i id
, mod(i-1,3) val1
, mod(i-1,10) val2
, lpad('k',100,'k') dummy
FROM generate_series(1,1e6) a(i)
ORDER BY random();
ALTER TABLE T1 ADD CONSTRAINT T1_PK PRIMARY KEY(val1, val2, id);
ANALYZE T1;
SELECT relname, relpages, relpages*8/1024 as size_MB
FROM PG_CLASS
WHERE RELNAME LIKE 't1%';
+---------+----------+---------+
| relname | relpages | size_MBytes |
+---------+----------+---------+
| t1 | 18182 | 142 |
| t1_pk | 4511 | 35 |
+---------+----------+---------+
I have created a table with 3 values for val1, 10 values for val2, with a total of 30 combinations. The addition of the primary key
starting with (val1, val2) is just a lazy way to ensure that I have a
suitable index and val1 and val2 are both declared not null.
If the business requirement is to retrieve the distinct values for (val1, val2), you would have used a query like below:
SELECT DISTINCT VAL1, VAL2
FROM T1;
The following is the execution plan the optimizer produced.
HashAggregate (actual time=437.168..437.172 rows=30 loops=1)
Group Key: val1, val2
Batches: 1 Memory Usage: 24kB
Buffers: shared hit=11821 read=6361
-> Seq Scan on t1 (actual time=0.019..124.505 rows=1000000 loops=1)
Buffers: shared hit=11821 read=6361
Planning:
Buffers: shared hit=122 read=31
Planning Time: 3.880 ms
Execution Time: 437.502 ms
To our disappointment, PostgreSQL didn't access the index we have. It visited 11821 memory blocks and 6361 disk blocks.
Another query that meets the business requirement would be like below:
SELECT VAL1, VAL2
FROM T1
GROUP BY VAL1, VAL2;
Group (actual time=151.274..155.047 rows=30 loops=1)
Group Key: val1, val2
Buffers: shared hit=11867 read=6329
-> Gather Merge (actual time=151.273..155.006 rows=90 loops=1)
Workers Planned: 2
Workers Launched: 2
Buffers: shared hit=11867 read=6329
-> Sort (actual time=144.965..144.967 rows=30 loops=3)
Sort Key: val1, val2
Sort Method: quicksort Memory: 26kB
Buffers: shared hit=11867 read=6329
Worker 0: Sort Method: quicksort Memory: 26kB
Worker 1: Sort Method: quicksort Memory: 26kB
-> Partial HashAggregate (actual time=144.872..144.876 rows=30 loops=3)
Group Key: val1, val2
Batches: 1 Memory Usage: 24kB
Buffers: shared hit=11853 read=6329
Worker 0: Batches: 1 Memory Usage: 24kB
Worker 1: Batches: 1 Memory Usage: 24kB
-> Parallel Seq Scan on t1 (actual time=0.038..31.946 rows=333333 loops=3)
Buffers: shared hit=11853 read=6329
Planning:
Buffers: shared hit=17 read=3 dirtied=1
Planning Time: 0.547 ms
Execution Time: 155.195 ms
The elapsed time dropped due to parallel processing. But it is still not accessing the index.
Now it is time to take advantage of the technique of getting distinct values using the Common Table Expression.
My first step will be to demonstrate the recursive CTE to get the distinct values for val1 using the index probe. I have included its execution plan to show that this does a minimal amount of work.
WITH RECURSIVE w1 AS (
(SELECT val1, val2 FROM t1 ORDER BY val1, val2 LIMIT 1) --non-recursive term
UNION ALL
SELECT t1.val1, t1.val2 --recursive term
FROM w1
JOIN LATERAL (SELECT val1, val2
FROM t1
WHERE t1.val1 > w1.val1
ORDER BY t1.val1, t1.val1
LIMIT 1) t1 ON TRUE
WHERE w1.val1 IS NOT NULL
AND w1.val2 IS NOT NULL
)
SELECT * FROM w1
WHERE w1.val1 IS NOT NULL
AND w1.val2 IS NOT NULL;
CTE Scan on w1 (actual time=0.181..0.411 rows=3 loops=1)
Filter: ((val1 IS NOT NULL) AND (val2 IS NOT NULL))
Buffers: shared hit=8 read=6
CTE w1
-> Recursive Union (actual time=0.178..0.407 rows=3 loops=1)
Buffers: shared hit=8 read=6
-> Limit (actual time=0.176..0.177 rows=1 loops=1)
Buffers: shared hit=1 read=3
-> Index Only Scan using t1_pk on t1 (actual time=0.174..0.174 rows=1 loops=1)
Heap Fetches: 0
Buffers: shared hit=1 read=3
-> Nested Loop (actual time=0.075..0.075 rows=1 loops=3)
Buffers: shared hit=7 read=3
-> WorkTable Scan on w1 w1_1 (actual time=0.001..0.001 rows=1 loops=3)
Filter: ((val1 IS NOT NULL) AND (val2 IS NOT NULL))
-> Limit (actual time=0.072..0.072 rows=1 loops=3)
Buffers: shared hit=7 read=3
-> Index Only Scan using t1_pk on t1 t1_1 (actual time=0.064..0.064 rows=1 loops=3
Index Cond: (val1 > w1_1.val1)
Heap Fetches: 0
Buffers: shared hit=7 read=3
Planning:
Buffers: shared hit=3 read=4
Planning Time: 0.863 ms
Execution Time: 0.639 ms
At first sight we can spot that we've got an Index Only Scan as the first step of the recursive query, visiting just 1 buffered block and three disk blocks. The Limit in
the plan indicates that it stopped reading the index after getting a
single row. So PostgreSQL is clearly doing an efficient access for that
value. We then see Nested Loop operation executed three times. By using
LATERAL JOIN the inline view after the LATERAL is run for every w1.val1 before the LATERAL. The inline view is also accessed via the t1_pk index.
So we can get the val1 values very easily and efficiently with this recursive CTE technology.
Using the same technology we can write some code to find the val2 values for each possible val1 value in turn:
WITH RECURSIVE w1 AS (
(SELECT val1, val2 FROM t1 ORDER BY val1, val2 LIMIT 1)
UNION ALL
SELECT t1.val1, t1.val2
FROM w1
JOIN LATERAL (SELECT val1, val2
FROM t1
WHERE t1.val1 > w1.val1
ORDER BY t1.val1, t1.val2
LIMIT 1) t1 ON TRUE
WHERE w1.val1 IS NOT NULL
),
w2 AS (
SELECT val1, val2 FROM w1
UNION ALL
SELECT w2.val1, (SELECT t1.val2
FROM t1
WHERE t1.val1 = w2.val1
AND t1.val2 > w2.val2
ORDER BY t1.val1, t1.val2
LIMIT 1) val2
FROM w2
WHERE w2.val2 is not null
AND w2.val1 is not null
)
SELECT *
FROM w2
WHERE w2.val2 is not null
;
In
this query the second CTE (w2) looks similar to the first CTE (w1) -
except I now have included an equality predicate against val1 based on the first of the two columns. The second CTE gets distinct val2 values for each val1 value. The following is the execution plan.
CTE Scan on w2 (actual time=0.060..3.028 rows=30 loops=1)
Filter: (val2 IS NOT NULL)
Rows Removed by Filter: 3
Buffers: shared hit=84 read=22
CTE w1
-> Recursive Union (actual time=0.058..0.258 rows=3 loops=1)
Buffers: shared hit=14
-> Limit (actual time=0.045..0.046 rows=1 loops=1)
Buffers: shared hit=4
-> Index Only Scan using t1_pk on t1 (actual time=0.044..0.044 rows=1 loops=1)
Heap Fetches: 0
Buffers: shared hit=4
-> Nested Loop (actual time=0.065..0.065 rows=1 loops=3)
Buffers: shared hit=10
-> WorkTable Scan on w1 (actual time=0.000..0.000 rows=1 loops=3)
Filter: (val1 IS NOT NULL)
-> Limit (actual time=0.060..0.060 rows=1 loops=3)
Buffers: shared hit=10
-> Index Only Scan using t1_pk on t1 t1_1 (actual time=0.056..0.056 rows=1 lops=3
Index Cond: (val1 > w1.val1)
Heap Fetches: 0
Buffers: shared hit=10
CTE w2
-> Recursive Union (actual time=0.059..3.006 rows=33 loops=1)
Buffers: shared hit=84 read=22
-> CTE Scan on w1 w1_1 (actual time=0.058..0.259 rows=3 loops=1)
Buffers: shared hit=14
-> WorkTable Scan on w2 w2_1 (actual time=0.079..0.248 rows=3 loops=11)
Filter: ((val2 IS NOT NULL) AND (val1 IS NOT NULL))
Rows Removed by Filter: 0
Buffers: shared hit=70 read=22
SubPlan 2
-> Limit (actual time=0.089..0.089 rows=1 loops=30)
Buffers: shared hit=70 read=22
-> Index Only Scan using t1_pk on t1 t1_2 (actul time=0.088..0.088 rows=1 loops=30
Index Cond: ((val1 = w2_1.val1) AND (val2 > w2_1.val2))
Heap Fetches: 0
Buffers: shared hit=70 read=22
Planning Time: 0.679 ms
Execution Time: 3.230 ms
The
execution plan above is too complex to read in one go. Let's take a
look at the CTE w2 part. Since we've got 3 rows from CTE w1, the first
step of the recursive query produces 3 rows. The SubPlan2
represents the scalar subquery. The execution plan shows that we've got
30 Index Only Scans with 70 shared hits and 22 disk I/Os. And that's
exactly the right number of probes to return my result set.
You
will notice that I have got various "is not null" predicates scattered
throughout the query. In some cases this is to stop PostgreSQL from
running into an infinite loop. It is kind of a default pattern for
recursive CTEs and some of them could probably be removed with no change
in meaning.
Wrap Up
We
can take advantage of the recursive CTE technology to pick out the
unique set of combinations of the first two columns of a multi-column
index.
The
downside to using the recursive CTE technology is that if there are too
many distinct values, for example over 10,000, it will have poor
performance.
Addendum
You can use this version of the last query as well.
WITH RECURSIVE w1 AS (
(SELECT val1, val2 FROM t1 ORDER BY val1, val2 LIMIT 1)
UNION ALL
SELECT t1.val1, t1.val2
FROM w1
JOIN LATERAL (SELECT val1, val2
FROM t1
WHERE t1.val1 > w1.val1
ORDER BY t1.val1, t1.val2
LIMIT 1) t1 ON TRUE
WHERE w1.val1 IS NOT NULL
),
w2 AS(
SELECT val1, val2 FROM w1
UNION ALL
SELECT t1.val1, t1.val2
FROM w2
JOIN LATERAL (SELECT val1, val2
FROM t1
WHERE t1.val1 = w2.val1
AND t1.val2 > w2.val2
ORDER BY t1.val1, t1.val2
LIMIT 1) t1 ON TRUE
WHERE w2.val2 is not null
AND w2.val1 is not null
)
SELECT * FROM w2
WHERE w2.val2 is not null
;
Added on September 3, 2023
You can implement this technique in Oracle 12.2 as follows:
WITH W1 (VAL1, VAL2) AS (
(SELECT VAL1, VAL2 FROM T1 ORDER BY VAL1, VAL2 FETCH NEXT 1 ROWS ONLY)
UNION ALL
SELECT (SELECT MIN(T1.VAL1) FROM T1 WHERE T1.VAL1 > W1.VAL1) AS VAL1,
W1.VAL2
FROM W1
WHERE W1.VAL1 IS NOT NULL
)
, W2 (VAL1, VAL2) AS (
SELECT VAL1, VAL2 FROM W1
UNION ALL
SELECT W2.VAL1,
(SELECT MIN(T1.VAL2) FROM T1 WHERE T1.VAL1=W2.VAL1 AND T1.VAL2 > W2.VAL2) AS VAL2
FROM W2
WHERE W2.VAL2 IS NOT NULL
)
SELECT *
FROM W2
WHERE W2.VAL2 IS NOT NULL
AND W2.VAL1 IS NOT NULL
ORDER BY VAL1, VAL2;
