설문조사
PostgreSQL/PPAS 관련 듣고 싶은 교육은


총 게시물 169건, 최근 0 건
   

Incremental Sort

글쓴이 : 모델광 날짜 : 2023-04-22 (토) 21:47 조회 : 1384
A few years ago I was involved in a project where I had to convert SQL statements from Oracle to PostgreSQL. The Oracle version was 12.2 and the PostgreSQL version was 12. During the migration, I encountered numerous queries that did not function properly in PostgreSQL. As a result, I made a few notes to remember what I learned during the project. The following article was one of those notes, and I recently updated it to reflect new features added in recent versions of PostgreSQL.

There are certain SQL statements in Oracle that may not run in PostgreSQL, requiring modification to be compatible. Sometimes, while investigating the queries, you may find suboptimal performance. In such cases, query optimization is necessary during the migration process. Here is a demo script to build some sample data in Oracle and an example of the SQL statement I had to migrate. The souce database version is Oracle 12.2.

CREATE TABLE ORDERS_DETAIL
AS
SELECT ROWNUM AS ORD_LINE_NO
          , MOD(ROWNUM, 1000000) AS ORD_NO
          , 'PP'||MOD(ROWNUM, 5) AS PROD_ID
          , LPAD('X',10,'Y') AS COMENT
          , CASE WHEN ROWNUM < 1000 THEN ROWNUM*100
                     ELSE ROWNUM END AS PROD_AMT
  FROM XMLTABLE('1 to 10000000') ;

CREATE INDEX ORDERS_X02 ON ORDERS_DETAIL(PROD_AMT);

SELECT ORD_NO, PROD_ID, COMENT, PROD_AMT
  FROM ORDERS_DETAIL
WHERE PROD_ID = 'PP2'
ORDER BY PROD_AMT DESC, ORD_NO DESC
OFFSET 0 ROWS FETCH NEXT 10 ROWS ONLY;


Note that the SQL statement used the ANSI-standard FETCH FIRST/NEXT and OFFSET clause. This clause enables you to easily retrieve the first N rows from a result set.
When Oracle released the 12c version, it marketed this new feature by saying, "Oracle 12c complies with the ANSI standard and your pagination query can be more readable." As a result, many early adopters used this feature. However, this new feature is less performant than the old-style ROWNUM clause.

Here is the execution plan of the query, pulled from memory with rowsource execution stats enabled.
-------------------------------------------------------------------------------------------------------------------------------
| Id  | Operation                | Name          | Starts | A-Rows |   A-Time   | Buffers | Reads  |  OMem |  1Mem | Used-Mem |
-------------------------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT         |               |      1 |     10 |00:00:01.52 |   51004 |  50989 |       |       |          |
|*  1 |  VIEW                    |               |      1 |     10 |00:00:01.52 |   51004 |  50989 |       |       |          |
|*  2 |   WINDOW SORT PUSHED RANK|               |      1 |     10 |00:00:01.52 |   51004 |  50989 | 13312 | 13312 |12288  (0)|
|*  3 |    TABLE ACCESS FULL     | ORDERS_DETAIL |      1 |   2000K|00:00:00.73 |   51004 |  50989 |       |       |          |
-------------------------------------------------------------------------------------------------------------------------------

Predicate Information (identified by operation id):
---------------------------------------------------

1 - filter((\"from$_subquery$_002\".\"rowlimit_$$_rownumber\"<=10 AND \"from$_subquery$_002\".\"rowlimit_$$_rownumber\">0))
2 - filter(ROW_NUMBER() OVER ( ORDER BY INTERNAL_FUNCTION(\"PROD_AMT\") DESC ,INTERNAL_FUNCTION(\"ORD_NO\") DESC )<=10)
3 - filter(\"PROD_ID\"='PP2')


As you can see from the execution plan, Oracle has used a TABLE ACCESS FULL operation. It failed to access the ORDERS_X02 index, which was built on the column PROD_AMT. In passing you will notice from the Predicate Information at operation 2 that Oracle has transformed our "fetch next" into an analytic query using row_number() over().
How do thins change if we use the old-style ROWNUM clause? Here is the query using the ROWNUM clause followed by its execution plan.


SELECT ORD_NO, PROD_ID, COMENT, PROD_AMT
  FROM (SELECT ORD_NO, PROD_ID, COMENT, PROD_AMT
               FROM ORDERS_DETAIL
             WHERE PROD_ID = 'PP2'
             ORDER BY PROD_AMT DESC, ORD_NO DESC
            )
WHERE ROWNUM <= 10;

------------------------------------------------------------------------------------------------------------------------------
| Id  | Operation               | Name          | Starts | A-Rows |   A-Time   | Buffers | Reads  |  OMem |  1Mem | Used-Mem |
------------------------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT        |               |      1 |     10 |00:00:01.28 |   51004 |  50989 |       |       |          |
|*  1 |  COUNT STOPKEY          |               |      1 |     10 |00:00:01.28 |   51004 |  50989 |       |       |          |
|   2 |   VIEW                  |               |      1 |     10 |00:00:01.28 |   51004 |  50989 |       |       |          |
|*  3 |    SORT ORDER BY STOPKEY|               |      1 |     10 |00:00:01.28 |   51004 |  50989 | 13312 | 13312 |12288  (0)|
|*  4 |     TABLE ACCESS FULL   | ORDERS_DETAIL |      1 |   2000K|00:00:00.90 |   51004 |  50989 |       |       |          |
------------------------------------------------------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
1 - filter(ROWNUM<=10)
3 - filter(ROWNUM<=10)
4 - filter((\"PROD_ID\"='PP2' AND \"PROD_AMT\">0))


Although the number of block I/Os is identical with the first execution plan, the elapsed time dropeed from 1.52 sec to 1.28 sec. It can be concluded that the old-style ROWNUM clause is more performant than the ANSI-standard FETCH FIRST/NEXT clause.
Fundamentally, the problem with the query is that it is using the TABLE ACCESS FULL operation. The simple and easy way to improve the query performance would be to create an index on the columns (PROD_AMT, ORD_NO). So Oracle can access the index and read just 10 rows in the index removing the SORT operation. What if we can not add an index for some reason? Note that we have an index on the column PROD_AMT. We can improve the query performance using the index on the column PROD_AMT.

Here is the query I rewrote to drive the query to use the index on the column PROD_AMT.


SELECT A.ORD_NO, A.PROD_ID, A.COMENT, A.PROD_AMT
  FROM (SELECT RID, ORD_NO, PROD_ID, COMENT, PROD_AMT
              FROM (SELECT ROWID AS RID, ORD_NO, PROD_ID, COMENT, PROD_AMT
                           FROM ORDERS_DETAIL
                         WHERE PROD_ID = 'PP2'
                              AND PROD_AMT >= 0
                          ORDER BY PROD_AMT DESC
                        )
             WHERE ROWNUM <= 10
           ) A, ORDERS_DETAIL B
WHERE A.RID = B.ROWID
ORDER BY A.PROD_AMT DESC, A.ORD_NO DESC;

Here is the execution plan.

-------------------------------------------------------------------------------------------------------------------------------
| Id  | Operation                         | Name          | Starts | A-Rows |   A-Time   | Buffers |  OMem |  1Mem | Used-Mem |
-------------------------------------------------------------------------------------------------------------------------------
|   0 | SELECT STATEMENT                  |               |      1 |     10 |00:00:00.01 |       5 |       |       |          |
|   1 |  SORT ORDER BY                    |               |      1 |     10 |00:00:00.01 |       5 |  2048 |  2048 | 2048  (0)|
|   2 |   NESTED LOOPS                    |               |      1 |     10 |00:00:00.01 |       5 |       |       |          |
|   3 |    VIEW                           |               |      1 |     10 |00:00:00.01 |       4 |       |       |          |
|*  4 |     COUNT STOPKEY                 |               |      1 |     10 |00:00:00.01 |       4 |       |       |          |
|   5 |      VIEW                         |               |      1 |     10 |00:00:00.01 |       4 |       |       |          |
|*  6 |       TABLE ACCESS BY INDEX ROWID | ORDERS_DETAIL |      1 |     10 |00:00:00.01 |       4 |       |       |          |
|*  7 |        INDEX RANGE SCAN DESCENDING| ORDERS_X02    |      1 |     49 |00:00:00.01 |       3 |       |       |          |
|   8 |    TABLE ACCESS BY USER ROWID     | ORDERS_DETAIL |     10 |     10 |00:00:00.01 |       1 |       |       |          |
-------------------------------------------------------------------------------------------------------------------------------
Predicate Information (identified by operation id):
---------------------------------------------------
4 - filter(ROWNUM<=10)
6 - filter(\"PROD_ID\"='PP2')
7 - access(\"PROD_AMT\">=0)


Note that we could not remove the SORT ORDER BY at operation 2. However, as you can see from the A-rows column, Oracle has sorted merely 10 rows. And the number of block I/Os is just 5.
Now that we have completed optimizing a query in Oracle, let us think about how we will migrate the query to PostgreSQL. We know that ROWID and ROWNUM do not function in PostgreSQL. If we run the first query using the FETCH NEXT 10 ROWS ONLY clause, it will execute without any errors in PostgreSQL. But we know that the query is not performant.
Here is a simple script to test the performance of the query in PostgreSQL 12.


CREATE TABLE ORDERS_DETAIL
AS
SELECT i as ORD_LINE_NO
         , mod(i,1000000) AS ORD_NO
         , 'PP'||MOD(i,5) AS PROD_ID
         , lpad('X',10,'Y') as comment
         , case when i < 1000 then i*100 else i end as prod_amt
FROM generate_series(1,10000000) a(i);

CREATE INDEX ORDERS_X02 ON ORDERS_DETAIL(PROD_AMT);

I have run the first query.

SELECT ORD_NO, PROD_ID, COMENT, PROD_AMT
  FROM ORDERS_DETAIL
WHERE PROD_ID = 'PP2'
ORDER BY PROD_AMT DESC, ORD_NO DESC
OFFSET 0 ROWS FETCH NEXT 10 ROWS ONLY;


Here is the execution plan obtained by running the EXPLAIN command.

Limit (actual time=991.724..991.727 rows=10 loops=1)
  Buffers: shared hit=16073 read=57457
  ->  Sort (actual time=991.722..991.724 rows=10 loops=1)
        Sort Key: prod_amt DESC, ord_no DESC
        Sort Method: top-N heapsort  Memory: 26kB
        Buffers: shared hit=16073 read=57457
        ->  Seq Scan on orders_detail (actual time=0.295..712.315 rows=2000000 loops=1)
              Filter: (prod_id = 'PP2'::text)
              Rows Removed by Filter: 8000000
              Buffers: shared hit=16073 read=57457
Planning Time: 0.066 ms
Execution Time: 991.745 ms

We can observe that PostgreSQL is also performing a FULL TABLE SCAN, similar to Oracle. We need to rewrite the query to utilize the index on the column PROD_AMT. Here is the modified query:

SELECT C.ORD_NO, C.PROD_ID, C.COMMENT, C.PROD_AMT
  FROM (SELECT PROD_AMT
              FROM (SELECT PROD_AMT
                          FROM ORDERS_DETAIL
                        WHERE PROD_ID = 'PP2'
                        ORDER BY PROD_AMT DESC
                        OFFSET 0 ROWS FETCH NEXT 10 ROWS ONLY
                      ) A
           GROUP BY PROD_AMT
          ) B, ORDERS_DETAIL C
WHERE B.PROD_AMT = C.PROD_AMT
     AND C.PROD_ID = 'PP2'
ORDER BY C.PROD_AMT DESC, C.ORD_NO DESC
OFFSET 0 ROWS FETCH NEXT 10 ROWS ONLY;


Here is the execution plan.

Limit (actual time=0.059..0.061 rows=10 loops=1)
  Buffers: shared hit=44
  ->  Sort (actual time=0.059..0.060 rows=10 loops=1)
        Sort Key: c.prod_amt DESC, c.ord_no DESC
        Sort Method: quicksort  Memory: 25kB
        Buffers: shared hit=44
        ->  Nested Loop (actual time=0.039..0.052 rows=10 loops=1)
              Buffers: shared hit=44
              ->  HashAggregate (actual time=0.031..0.033 rows=10 loops=1)
                    Group Key: orders_detail.prod_amt
                    Batches: 1  Memory Usage: 24kB
                    Buffers: shared hit=4
                    ->  Limit (actual time=0.022..0.027 rows=10 loops=1)
                          Buffers: shared hit=4
                          ->  Index Scan Backward using orders_x02 on orders_detail (actual time=0.022..0.026 rows=10 loops=1)
                                Filter: (prod_id = 'PP2'::text)
                                Rows Removed by Filter: 39
                                Buffers: shared hit=4
              ->  Index Scan using orders_x02 on orders_detail c (actual time=0.001..0.001 rows=1 loops=10)
                    Index Cond: (prod_amt = orders_detail.prod_amt)
                    Filter: (prod_id = 'PP2'::text)
                    Buffers: shared hit=40
Planning Time: 0.136 ms
Execution Time: 0.101 ms


As you can see, there is a substantial performance boost due to the index access. In conclusion, when an optimal index for pagination is not available, try to reduce the amount of SORT operation.

A few days ago, when I did the same experiment on PostgreSQL 15, I observed a completely different behavior of PostgreSQL.
Here is the query I ran in PostgreSQL 15, followed by its execution plan.

SELECT ORD_NO, PROD_ID, COMENT, PROD_AMT
  FROM ORDERS_DETAIL
WHERE PROD_ID = 'PP2'
ORDER BY PROD_AMT DESC, ORD_NO DESC
OFFSET 0 ROWS FETCH NEXT 10 ROWS ONLY;


Limit (actual time=0.030..0.032 rows=10 loops=1)
  Buffers: shared hit=4
  ->  Incremental Sort (actual time=0.029..0.030 rows=10 loops=1)
        Sort Key: prod_amt DESC, ord_no DESC
        Presorted Key: prod_amt
        Full-sort Groups: 1  Sort Method: quicksort  Average Memory: 25kB  Peak Memory: 25kB
        Buffers: shared hit=4
        ->  Index Scan Backward using orders_x02 on orders_detail (actual time=0.017..0.022 rows=11 loops=1)
              Filter: (prod_id = 'PP2'::text)
              Rows Removed by Filter: 43
              Buffers: shared hit=4
Planning Time: 0.069 ms
Execution Time: 0.045 ms



Note that the optimizer decided to use the incremental sort rather than sorting the whole result in one go . You will also notice that this new approach gets the job done in 25kB of memory. As evident from the plan, the set is pre-sorted by PROD_AMT, being the output of an index scan against this column (Presorted Key). Due to the FETCH NEXT 10 ROWS ONLY clause, Incremental Sort stopped when it retrieved 10 rows, resulting in 4 block I/Os.

The identical ANSI-style query took 0.040 mili seconds to complete in Postgres when it took 1.52 seconds to complete in Oracle due to the wonderful mechanism called incremental sorting.

Conclusion
Postgres has a wonderful mechanism for optimizing sorts that can make a huge difference to "fetch next n rows only" queries. When you migrate "fetch next N rows only" queries (or, Oracle style, rownum <= N with optimizer_mode = first_rows_N) from Oracle to Postgres, you may observe a significant performance boost in PostgreSQL.

Footnote
Incremental Sort was added in PostgreSQL 13.


   

postgresdba.com