MIN/MAX with GROUP BY

https://stackoverflow.com/questions/54856702/postgresql-11-goes-for-parallel-seq-scan-on-partitioned-table-where-index-should

The most popular answer in the post concluded that "PostgreSQL punts when it sees a GROUP BY clause." And it also supplied the source code in src/backend/optimizer/plan/planagg.c to convince that there is not much point in optimizing MIN/MAX with GROUP BY.

I thought that I might be able to work out a solution to improve the performance of the query with ease. But it took me about a week to find a solution.

One of the wonderful features I think PostgreSQL has is its "min/max" optimization. Rather than talking through it, here is a little demonstration.

CREATE TABLE PART (

C1     INT,

C2     VARCHAR(100),

C3     VARCHAR(10),

STATUS VARCHAR(1) 

)

PARTITION BY LIST(C1)

;

CREATE TABLE PART1 PARTITION OF PART FOR VALUES IN(1);

CREATE TABLE PART2 PARTITION OF PART FOR VALUES IN(2);

CREATE TABLE PART3 PARTITION OF PART FOR VALUES IN(3);

CREATE TABLE PART4 PARTITION OF PART FOR VALUES IN(4);

INSERT INTO PART

SELECT i%4+1

     , i::text||'WhoeverDoesNotLoveDoesNotKnowGodBecauseGodIsLove'

     , substr(md5(random()::text),1,10)

     , chr(65+i%3)

  FROM GENERATE_SERIES(1,1000000) a(i);

CREATE INDEX PART_X01 ON PART(STATUS, C3);

CREATE INDEX PART_X02 ON PART(C1, STATUS);

CREATE TABLE NONPART AS SELECT * FROM PART;

CREATE INDEX NONPART_X01 ON NONPART(STATUS, C3);

I have created a non-partitioned table "NONPART" and a partitioned table "PART". Let's say that I want to get a minimum STATUS value and maximum STATUS value. Then my query would be:

SELECT MIN(STATUS), MAX(STATUS) FROM PART;

If you run the query in ORACLE, it is inevitable to do an index fast full scan which has to read all the index blocks. And it also has to do a sort aggregate by STATUS. The ORACLE execution plan would be as follows:

    OPERATION                         NAME

-----------------------------------------------

 SELECT STATEMENT

    SORT AGGREGATE

       INDEX FAST FULL SCAN        PART_X01                --> this results in a lot of block I/Os

In ORACLE if you want to improve the response time, you have to rewrite it as follows.

SELECT MIN(MIN_VAL), MAX(MAX_VAL)

  FROM (    

            SELECT MIN(STATUS) as MIN_VAL, NULL as MAX_VAL

               FROM PART

              UNION ALL

             SELECT NULL AS MIN_VAL, MAX(STATUS) as MAX_VAL

                  FROM PART

           )

;

Then how would PostgreSQL get the minimum and maximum values of STATUS? Below is the execution plan the optimizer produces with some cosmetic editing.

In the above plan we can not see any aggregate operations. PostgreSQL doesn't need to acquire a lot of data and sort it when it knows that the "left hand" end of an index is the low values and the "right hand" end is the high values.  Surely with the same amount of data the block I/O and the execution time are much smaller than those of ORACLE. The bigger the data, the more huge the performance gap is.

In the InitPlan 1 of the execution plan the optimizer could simply walk down the index branches to the left hand leaf and look at the single lowest entry in the leaf block to determine the lowest value for STATUS. (In a partitioned table, PostgreSQL supports only local indexes. So it had to access four local indexes.) The Limit is specifically designed to stop reading the object early when the desired row, the max/min value in this example, was extracted.

In the InitPlan 2 of the execution plan the optimizer could simply walk down the index branches to the right hand leaf and look at the single highest entry in the leaf block to determine the highest value for STATUS. It hit three index blocks and one heap block in each partition.

In the future if PostgreSQL implements global indexes in a partitioned table, it will be able to get the result without visiting every partition.

Now let's assume that we should extract min(c3) and max(c3) per STATUS. Then the query would be like this:

--From now on I use a non-partitioned table for simplicity of explanation.

SELECT STATUS, MIN(C3), MAX(C3)

  FROM NONPART

GROUP BY STATUS;

Since we have an index on the columns (STATUS, C3), we would expect the optimizer produces an execution plan using the index. It would access the left-hand end of the index and the right-hand end of the index.

Now let's take a look at the execution plan.

Disappointingly the optimizer didn't use the index. PostgreSQL is not smart enough to figure out it can use the index to speed up min()/max() with GROUP BY.  So how can we work around this problem?

STATUS has small number of distinct values. PostgreSQL can extract distinct values super efficiently when the column is indexed. So I re-engineered the query as follows:

WITH RECURSIVE W AS (

(SELECT STATUS FROM NONPART ORDER BY STATUS LIMIT 1)

UNION ALL

SELECT (SELECT STATUS

          FROM NONPART A

         WHERE A.STATUS > W.STATUS

         ORDER BY A.STATUS LIMIT 1)

  FROM W

 WHERE STATUS IS NOT NULL

)

SELECT W.STATUS, B.*

  FROM W

 JOIN LATERAL 

      (SELECT MIN(C3) AS MIN_C3, MAX(C3) AS MAX_C3

         FROM NONPART B

        WHERE W.STATUS = B.STATUS

        ) B ON TRUE

WHERE W.STATUS IS NOT NULL;

The key thing in the above query is that I got rid of the GROUP BY clause. According to the PostgreSQL source code "src/backend/optimizer/plan/planagg.c", you cannot get a performance boost with GROUP BY.

To understand the revised query, you need to have knowledge of the following:

1. PostgreSQL can get distinct values efficiently using the Common Table Expression.

2. Using a lateral join we can run everything after the lateral for each row before the lateral.

3. PostgreSQL is super excellent in MIN/MAX optimization on an indexed column. (This was explained in the above example.)

If we run the above query against a partitioned table(PART) instead of a non-partitioned table(NONPART), we will do lots of individual probes into the local indexes. Still they will stay very efficient using a MIN/MAX access.

Wrap Up

PostgreSQL looks at all the rows when it implements GROUP BY even when there is an index on columns.

When we want to improve MIN/MAX with GROUP BY, we should find a method to remove GROUP BY in the SQL statement.