[YSQL] Support distinct pushdown in YSQL

[vbalvida]

Jira Link: DB-6955

Description

Context

YB LSM indexes support skipping over duplicate values of the leading column(s). This results in an efficient execution of distinct queries since the scan needs only fetch distinct tuples from the index. The list of leading columns over which the index skips is called the prefix and it is uniquely identified by its length, hereby referred to as the prefix length. This access pattern is colloquially called loose index scan or skip scan.

While the storage layer supports such an access pattern using the Hybrid Scan module, YSQL support is still lacking. Currently, we compute the prefix and make the decision to pushdown distinct during execution. Such an approach is less than ideal and here we make a case for moving this task to the planner. See issues #14559 and #16257 for more information on how the pushdown is currently implemented.

Objective

Making the decision to pushdown distinct in the planner as opposed to PgGate lets us avoid several correctness issues. In summary, distinct should not be pushed down if the distinct operation does not commute/distribute with other operations in the query. This commutativity is better checked in the planner.

Aggregate and Windowing Functions

Aggregation and Windowing operations require that we do not skip over duplicate rows since aggregation happens over even duplicate tuples in the group. See #17648 for more information.

As an example, consider a query such as

SELECT DISTINCT COUNT(r1) FROM t WHERE r1 = 1;

where r1 is the leading range column of t. Fatal to skip over duplicate rows of r1 here.

Volatile targets or predicates

Similar reasoning applies to volatile targets and predicates. Volatile functions have side effects and hence need to be executed for each tuple. This property makes them inherently incompatible with distinct pushdown.

Example

SELECT DISTINCT r1 * RANDOM() FROM t WHERE r1 = 1;

Pushing down distinct here is a mistake since RANDOM() can take different values for different duplicate values of r1.

---

Other than such correctness issues, making the planner aware of distinct pushdown helps it generate and select better plans overall.

Performance

Performance is a primary reason why distinct index scans are so important. There are several shortcomings with our current approach that we wish to overcome.

Inaccurate plan selection

Imagine that we have a table t setup using the following commands

CREATE TABLE t (r1 INT, r2 INT, PRIMARY KEY(r1 ASC, r2 ASC));
INSERT INTO t (SELECT 1, i FROM GENERATE_SERIES(1, 10000) AS i);

Now, getting the distinct elements of the first column executes the following plan

EXPLAIN ANALYZE SELECT DISTINCT r1 FROM t;
                                                QUERY PLAN                                                 
-----------------------------------------------------------------------------------------------------------
 HashAggregate  (cost=102.50..102.51 rows=1 width=4) (actual time=80.961..80.962 rows=1 loops=1)
   Group Key: r1
   ->  Seq Scan on t  (cost=0.00..100.00 rows=1000 width=4) (actual time=9.449..76.847 rows=10000 loops=1)
 Planning Time: 5.901 ms
 Execution Time: 81.103 ms
 Peak Memory Usage: 14 kB
(6 rows)

Forcing an index scan yields

EXPLAIN ANALYZE SELECT DISTINCT r1 FROM t WHERE r1 <= 10000;
                                                    QUERY PLAN                                                     
-------------------------------------------------------------------------------------------------------------------
 Unique  (cost=0.00..15.50 rows=1 width=4) (actual time=1.711..1.717 rows=1 loops=1)
   ->  Index Scan using t_pkey on t  (cost=0.00..15.25 rows=100 width=4) (actual time=1.709..1.715 rows=1 loops=1)
         Index Cond: (r1 <= 10000)
 Planning Time: 0.128 ms
 Execution Time: 1.808 ms
 Peak Memory Usage: 8 kB
(6 rows)

As can be seen from the differences in the reported execution times, a wildly inaccurate plan is being picked. The primary reason is that the planner is unaware that fewer rows are being fetched in the distinct index scan. More importantly, the user is now clueless as to why the index scan is so much quicker. Classifying this particular scan as a distinct index scan helps is better debugging of performance issues. Moreover, the current approach also does some redundant computation, discussed in the next section.

Redundant Unique/HashAggregate Node

In the above plan, observe that the planner creates a Unique node on top of the index scan. In hash-partitioned tables, such a unique node is not necessary since the distinct index scan already returns distinct values of the prefix. In fact, vanilla postgres provides two methods to distinctify scan paths. Pg can either sort+unique the underlying path or use hash aggregation. Add a third mechanism to add distinct paths. If the distinct index scan already returns a distinctified path, use the path directly. This reduces redundant computation with sorting/aggregation. There are many other opportunities that not mentioned in this ticket.

Warning: Please confirm that this issue does not contain any sensitive information

• I confirm this issue does not contain any sensitive information.

[jasonyb]

Can you fix the TBD/TODO?

What is "prefix"? "prefix computation", "prefix index scan"

[vbalvida]

The basic framework has landed. Any extensions or future work will be done as separate tasks.