This is a note that echoes optimization techniques that I have described in some of my previous articles.
https://www.postgresdba.com/bbs/board.php?bo_table=C05&wr_id=200&page=3
https://www.postgresdba.com/bbs/board.php?bo_table=C05&wr_id=246
This note is probably nothing new to most readers of this bulletin board, however sometimes an old thing presented in a new way offers fresh insights or enhances comprehesion. I was tasked with optimizing a query that became 50 times slower in PostgreSQL 13.4 compared to Oracle 12.2 after migration.
Here is the test code I used to model the performance-degraded query:
DROP TABLE ORDERS_DETAIL;
CREATE TABLE ORDERS_DETAIL
AS
SELECT i AS ORD_LINE_NO
, MOD(i, 1000000) AS ORD_NO
, 'PP'||MOD(i, 10) AS PROD_ID
, LPAD('X',10,'Y') AS COMENT
, CASE WHEN i < 1000 THEN i*100
ELSE i END AS ORD_AMT
FROM generate_series(1, 5000000) a(i);
ALTER TABLE ORDERS_DETAIL ADD CONSTRAINT PK_ORDERS_DETAIL PRIMARY KEY(ORD_LINE_NO);
CREATE INDEX ORDERS_DETAIL_X02 ON ORDERS_DETAIL(PROD_ID, ORD_AMT);
CREATE TABLE PROD (
PROD_ID VARCHAR(10) NOT NULL
,PROD_NM VARCHAR(100) NOT NULL
);
INSERT INTO PROD
SELECT 'PP'||i::text as prod_id
, 'Product_name'||i::text as prod_nm
FROM generate_series(0,9) a(i);
ALTER TABLE PROD ADD CONSTRAINT PK_PROD PRIMARY KEY(PROD_ID);
ALTER TABLE ORDERS_DETAIL ADD CONSTRAINT FK_ORDERS_DETAIL FOREIGN KEY(PROD_ID) REFERENCES PROD(PROD_ID);
All we've got is an ORDERS_DETAIL table with a declared primary key of ORD_LINE_NO and a PROD table with a PROD_ID column declared as a primary key. Additionally, the ORDERS_DETAIL table has a foreign key constraint to the PROD table on the PROD_ID column.
Let's say that we should write a query to report all detailed information of orders where the ord_amt is less than the average ord_amt for the corresponding product. The typical choice of SQL for this requirement would be something like this:
SELECT A.PROD_ID, A.PROD_NM, B.ORD_LINE_NO, B.ORD_AMT
FROM PROD A, ORDERS_DETAIL B
WHERE A.PROD_ID = B.PROD_ID
AND B.ORD_AMT < (SELECT AVG(C.ORD_AMT)
FROM ORDERS_DETAIL C
WHERE B.PROD_ID = C.PROD_ID);
The subquery calculates the average ORD_AMT for the correlated PROD_ID, and we are probably assuming PostgreSQL will execute the subquery for each row in the ORDERS_DETAIL (B) table, benefiting from the ORDERS_DETAIL_X02 access. We have created a "value-added" index of (PROD_ID, ORD_AMT) before running the query. Here is the execution plan I obtained from the query in its current form:
Nested Loop (cost=0.00..88529309414.42 rows=1666667 width=268)
Join Filter: ((a.prod_id)::text = (b.prod_id)::text)
-> Seq Scan on orders_detail b (cost=0.00..88522334220.00 rows=1666667 width=16)
Filter: (ord_amt < (SubPlan 1))
SubPlan 1
-> Aggregate (cost=17704.43..17704.44 rows=1 width=32)
-> Index Only Scan using orders_detail_x02 on orders_detail c (cost=0.43..16454.43 rows=500000 width=6)
Index Cond: (prod_id = (b.prod_id)::text)
-> Materialize (cost=0.00..14.20 rows=280 width=256)
-> Seq Scan on prod a (cost=0.00..12.80 rows=280 width=256)
I had to stop excuting the query because I could not get the result on my laptop computer after running the query for 480 seconds. The original query I was requested to optimize, took 50 seconds on PostgreSQL 13.4 in the production environment, while the same query took only 1 second on Oracle 12.2.
Let's take a look at the plan closely. We can observe that the database engine is estimating it would retrieve 1,666,667 rows after scanning the ORDERS_DETAIL table. If the estimate is correct, we can infer that it will access the ORDERS_DETAIL_X02 index 1,666,667 times, which is an outrageous inefficiency.
The Materialize node is utilized when the same set of results is needed more than once to avoid redundant calculations or scans. In this specific plan, the results from scanning PROD are stored in memory, thus avoiding repetitive access to the PROD table.
If you read previous notes mentioned in the top paragraph, you will be able to make the query run faster with ease.
Strategy 1 : Using a Window Function
The first thing that came to my mind was to rewrite the subquery using a window function by hand, removing the aggregate subquery. Here is the reenginnered query using a window function:
SELECT PROD_ID, PROD_NM, ORD_LINE_NO, ORD_AMT
FROM (
SELECT A.PROD_ID, A.PROD_NM, B.ORD_AMT
, CASE WHEN B.ORD_AMT < AVG(B.ORD_AMT) OVER (PARTITION BY B.PROD_ID)
THEN B.ORD_LINE_NO
END AS ORD_LINE_NO
FROM PROD A, ORDERS_DETAIL B
WHERE A.PROD_ID = B.PROD_ID
) FOO
WHERE ORD_LINE_NO IS NOT NULL;
I have used a CASE statement to generate the ORD_LINE_NO value ,which is then checked for null values. Notice that the query has been reduced to a simple two table join, elimiated the correlated subquery, and has an analytic funtion being used somehow to handle the comparison with the average.
And here is the execution plan:
Subquery Scan on foo (actual time=372.322..4878.178 rows=2500010 loops=1)
Filter: (foo.ord_line_no IS NOT NULL)
Rows Removed by Filter: 2499990
Buffers: shared hit=1864 read=486311, temp read=55935 written=29361
-> WindowAgg (actual time=372.321..4573.024 rows=5000000 loops=1)
Buffers: shared hit=1864 read=486311, temp read=55935 written=29361
-> Merge Join (actual time=0.076..2234.702 rows=5000000 loops=1)
Merge Cond: ((a.prod_id)::text = (b.prod_id)::text)
Buffers: shared hit=1864 read=486311
-> Index Scan using pk_prod on prod a (actual time=0.019..0.028 rows=10 loops=1)
Buffers: shared hit=1 read=1
-> Index Scan using orders_detail_x02 on orders_detail b (actual time=0.052..1560.417 rows=5000000 loops=1)
Buffers: shared hit=1863 read=486310
Planning Time: 0.125 ms
Execution Time: 4953.077 ms
Compared to the first intuitive query, this convoluted query is a lot faster.
Strategy 2 : Flattening the correlated subquery
Next, let's explore another strategy: unnesting the correlated subquery by transforming the subquery into an inlive view.
Here is the modified query:
SELECT A.PROD_ID, A.PROD_NM, B.ORD_LINE_NO, B.ORD_AMT
FROM (SELECT PROD_ID, AVG(ORD_AMT) AS AVG_AMT
FROM ORDERS_DETAIL
GROUP BY PROD_ID
) C, PROD A, ORDERS_DETAIL B
WHERE C.PROD_ID = B.PROD_ID
AND A.PROD_ID = B.PROD_ID
AND B.ORD_AMT < C.AVG_AMT;
Hash Join (actual time=1223.920..3122.753 rows=2500010 loops=1)
Hash Cond: ((orders_detail.prod_id)::text = (a.prod_id)::text)
Buffers: shared hit=31318 read=62123
-> Hash Join (actual time=1223.854..2698.751 rows=2500010 loops=1)
Hash Cond: ((b.prod_id)::text = (orders_detail.prod_id)::text)
Join Filter: (b.ord_amt < (avg(orders_detail.ord_amt)))
Rows Removed by Join Filter: 2499990
Buffers: shared hit=31317 read=62123
-> Seq Scan on orders_detail b (actual time=0.032..332.499 rows=5000000 loops=1)
Buffers: shared hit=15674 read=31046
-> Hash (actual time=1223.816..1223.816 rows=10 loops=1)
Buckets: 1024 Batches: 1 Memory Usage: 9kB
Buffers: shared hit=15643 read=31077
-> HashAggregate (actual time=1223.807..1223.811 rows=10 loops=1)
Group Key: orders_detail.prod_id
Batches: 1 Memory Usage: 24kB
Buffers: shared hit=15643 read=31077
-> Seq Scan on orders_detail (actual time=0.001..326.358 rows=5000000 loops=1)
Buffers: shared hit=15643 read=31077
-> Hash (actual time=0.013..0.013 rows=10 loops=1)
Buckets: 1024 Batches: 1 Memory Usage: 9kB
Buffers: shared hit=1
-> Seq Scan on prod a (actual time=0.008..0.009 rows=10 loops=1)
Buffers: shared hit=1
Planning Time: 0.251 ms
Execution Time: 3198.911 ms
Take note particulary of the Hash Cond and Join Filter on the Hash Join node - it's a reminder that hash joins apply only for equality predicates, so the check against average ORD_AMT has to take place as a filter predicate after PostgreSQL found the correct average by scanning the build table. Even though this query accesses the ORERS_DETAIL table twice, the elapsed time has decreased from 4953 ms to 3198 ms.
When I checked the execution plan for the original, intuitive query in Oracle 12.2, the plan was the same as this:
HASH JOIN
TABLE ACCESS (FULL) OF PROD
HASH JOIN
VIEW OF SYS.VW_SQ_1 (VIEW)
HASH (GROUP BY)
TABLE ACCESS (FULL) OF ORDERS_DETAIL (TABLE)
TABLE ACCESS (FULL) OF ORDERS_DTAIL (TABLE)
So I believed that I had my optimization task done and handed over the optimized query to the developer, expecting that he would be blown away. However, I was left feeling embarrassed when the developer returned with a rewritten version of the query which was much faster than the one I had constructed. He did not add an index, he did not collect statistics, but he improved the query's performance simply by modifying the query. I will share the details of the developer's approach sometime next week.
Added on Mar. 17, 2024
Here is the clever tweak the developer made to the original query:
SELECT A.PROD_ID, A.PROD_NM, B.ORD_LINE_NO, B.ORD_AMT
FROM PROD A, ORDERS_DETAIL B
WHERE A.PROD_ID = B.PROD_ID
AND B.ORD_AMT < (SELECT AVG(C.ORD_AMT)
FROM ORDERS_DETAIL C
WHERE A.PROD_ID = C.PROD_ID);
As you can see, the developer made the logically valid, minor edit to the original query (and it is so minor that I have highlighted the critical line in case you miss it). When we closely examine the original query, we can observe that the ORDERS_DETAIL table is joined to the PROD table, and then the PROD_ID column on the ORDERS_DETAIL table is joined to the PROD_ID column in the subquery. So based on transitive predicates, we should be happy to replace the join condition B.PROD_ID = C.PROD_ID with A.PROD_ID = C.PROD_ID.
It's easy of course to do the "I knew that" claim after seeing someone else's solution. Honestly, this simple yet effective solution eluded me when I was initially tasked with optimizing the origninal query.
Here is the execution plan for the reenginnered query:
Nested Loop (actual time=104.768..2190.485 rows=2500010 loops=1)
Buffers: shared hit=8455 read=255734
-> Seq Scan on prod a (actual time=0.060..0.069 rows=10 loops=1)
Buffers: shared hit=1
-> Index Scan using orders_detail_x02 on orders_detail b (actual time=0.018..100.004 rows=250001 loops=10)
Index Cond: (((prod_id)::text = (a.prod_id)::text) AND (ord_amt < (SubPlan 1)))
Buffers: shared hit=8442 read=236539
SubPlan 1
-> Aggregate (actual time=93.673..93.673 rows=1 loops=10)
Buffers: shared hit=12 read=19195
-> Index Only Scan using orders_detail_x02 on orders_detail c (actual time=0.057..57.719 rows=500000 loops=10)
Index Cond: (prod_id = (a.prod_id)::text)
Heap Fetches: 0
Buffers: shared hit=12 read=19195
Planning Time: 0.416 ms
Execution Time: 2269.226 ms
Even though the block I/O jumped from (31318+62123) to (6455+255734), the elapsed time dropped, resuling in an around 30% improvement in speed.
Conclusion
If you haven't been living under a rock, you are probably aware of PostgreSQL's limitations in collapsing correlated subqueries. For certain patterns of queries that use aggregate subqueries as filter conditions, here are a few strategies we might explore:
1. We can rewrite expressions like max(subquery) or avg(subquery) using analytic functions. This approach can minimize the number of tables involved in the join, streamlining the query.
2. We can collapse the correlated subquery by transforming the subquery into an inline view by hand.
3. If there are appropriate indexes, we should consider "adjusting the correlated column". Data quality is of critical importance to implement this strategy.
