In the previous note titled 'Incremental Sort 2', I showed you how performant PostgreSQL can be with the lovely incremental sort mechanism when joining two tables and ordering them by a column on the driving table. In the demo query, PostgreSQL was doing a nested loop join, walking the appropriate index on the column of the driving table. As a result, you may think that an index is required for incremental sort to be used. But that is not always the case. In this note, I will illustrate how PostgreSQL can utilize incremental sort without an index on the column sorted by.
Here's a sample data set (tested on PostgreSQL 15) to demonstrate my point:
DROP TABLE ORDERS;
create table ORDERS (
ord_no bigint,
cust_id varchar(20),
comment varchar(100),
ord_date varchar(8)
);
ALTER TABLE ORDERS ADD CONSTRAINT PK_ORDERS PRIMARY KEY(ORD_NO);
DROP TABLE ORDERS_DETAIL;
CREATE TABLE ORDERS_DETAIL(
ORD_LINE_NO BIGINT NOT NULL,
ORD_NO BIGINT NOT NULL,
PROD_ID VARCHAR(10) NOT NULL,
COMMENT VARCHAR(100),
ORD_AMT BIGINT
);
insert into ORDERS
select i as ord_no
, 'C'||mod(i,10) as cust_id
, lpad('X',10,'Y')
, to_char(to_date('20191001','YYYYMMDD')+mod(i,600),'yyyymmdd') as ord_date
from generate_series(1,1000000) a(i);
INSERT INTO ORDERS_DETAIL
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);
ALTER TABLE ORDERS_DETAIL ADD CONSTRAINT PK_ORDERS_DETAIL PRIMARY KEY(ORD_LINE_NO);
CREATE INDEX ORDERS_DETAIL_X01 ON ORDERS_DETAIL(ORD_NO, PROD_ID);
CREATE INDEX ORDERS_DETAIL_X02 ON ORDERS_DETAIL(ORD_NO, ORD_AMT);
I have created an ORDERS table with 1 million rows, covering 600 dates out into the future, starting from 2019-10-01. As you can see, there is noting in the slightest bit interesting, unusual, or exciting about the content of the table. Each day in the table has approximately 1667 rows (1,000,000 / 600 = 1666.66). I have also created an ORDERS_DETAIL table with 10 million rows.
Now let's investigate how the following query works:
I have disabled parallel processing for simplicity and clarity.
set max_parallel_workers_per_gather = 0;
SELECT A.ORD_NO, ORD_LINE_NO, CUST_ID, PROD_ID, A.ORD_DATE, B.ORD_AMT
FROM ORDERS A, ORDERS_DETAIL B
WHERE A.ORD_NO = B.ORD_NO
AND A.ORD_DATE < '20191213'
ORDER BY A.ORD_DATE DESC, B.ORD_AMT
FETCH NEXT 20 ROWS ONLY;
Here is the execution plan obtained by running the EXPLAIN command:
Limit (actual time=2481.860..2481.864 rows=20 loops=1)
Buffers: shared hit=14357 read=76330
-> Sort (actual time=2481.859..2481.861 rows=20 loops=1)
Sort Key: a.ord_date DESC, b.ord_amt
Sort Method: top-N heapsort Memory: 28kB
Buffers: shared hit=14357 read=76330
-> Hash Join (actual time=104.699..2306.087 rows=1216900 loops=1)
Hash Cond: (b.ord_no = a.ord_no)
Buffers: shared hit=14357 read=76330
-> Seq Scan on orders_detail b (actual time=0.052..697.282 rows=10000000 loops=1)
Buffers: shared hit=14229 read=69105
-> Hash (actual time=104.544..104.544 rows=121690 loops=1)
Buckets: 131072 Batches: 1 Memory Usage: 7204kB
Buffers: shared hit=128 read=7225
-> Seq Scan on orders a (actual time=0.009..84.035 rows=121690 loops=1)
Filter: ((ord_date)::text < '20191213'::text)
Rows Removed by Filter: 878310
Buffers: shared hit=128 read=7225
Planning:
Buffers: shared hit=16
Planning Time: 0.212 ms
Execution Time: 2481.908 ms
PostgreSQL creates a hash table for the smaller ORDERS table and then probes it with the ORDERS_DETAIL table, using the ORD_NO column to look up matching rows in the hash table. The resulting hash join produces 1,216,900 rows, which are sorted using a top-N heapsort algorithm on the ORD_DATE and ORD_AMT columns. The query returns the top 20 sorted rows.
Did you notice anything special in the plan? Since we don't have an index on the column ORD_DATE, the execution plan above looks reasonable.
However, when I ran the query with parallel processing enabled, I was amazed.
set max_parallel_workers_per_gather = 2;
Here is the execution plan.
Limit (actual time=92.415..94.162 rows=20 loops=1)
Buffers: shared hit=15034 read=14108
-> Incremental Sort (actual time=92.414..94.159 rows=20 loops=1)
Sort Key: a.ord_date DESC, b.ord_amt
Presorted Key: a.ord_date
Full-sort Groups: 1 Sort Method: top-N heapsort Average Memory: 27kB Peak Memory: 27kB
Pre-sorted Groups: 1 Sort Method: top-N heapsort Average Memory: 26kB Peak Memory: 26kB
Buffers: shared hit=15034 read=14108
-> Nested Loop (actual time=47.814..90.769 rows=16671 loops=1)
Buffers: shared hit=15034 read=14108
-> Gather Merge (actual time=47.790..50.060 rows=1668 loops=1)
Workers Planned: 2
Workers Launched: 2
Buffers: shared hit=210 read=7257
-> Sort (actual time=45.108..45.245 rows=1343 loops=3)
Sort Key: a.ord_date DESC
Sort Method: quicksort Memory: 3888kB
Buffers: shared hit=210 read=7257
Worker 0: Sort Method: quicksort Memory: 3578kB
Worker 1: Sort Method: quicksort Memory: 3492kB
-> Parallel Seq Scan on orders a (actual time=0.027..34.486 rows=40563 loops=3)
Filter: ((ord_date)::text < '20191213'::text)
Rows Removed by Filter: 292770
Buffers: shared hit=96 read=7257
-> Index Scan using orders_detail_x01 on orders_detail b (actual time=0.006..0.023 rows=10 loops=1668)
Index Cond: (ord_no = a.ord_no)
Buffers: shared hit=14824 read=6851
Planning:
Buffers: shared hit=6 read=10
Planning Time: 0.443 ms
Execution Time: 94.191 ms
Postgresql reads all the rows on the ORDERS table, sorting them by ORD_DATE. The trick here is that PostgreSQl did not sort all the rows (121690), but ordered 1668 rows, which indicates that it stopped sorting after reading the data on '20191212'. Then the nested loop operation was performed between the 1668 rows and the ORDERS_DETAIL table. While doing the join, the incremental sort mechanism kicked in, returning the top 20 sorted rows. Overall, the elapsed time descreased from 2.481 seconds to 0.094 seconds. This test illustrates that incremental sort can operate without indexes on the driving table.
The test so far gives us some idea of incremental sort that the optimizer is using to paginate rows efficiently. The next question, of course, is "why doesn't PostgreSQL use incremental sort when parallel processing is disabled?". Trying to help the optimizer use the incremental sort mechanism when parallel processing is disabled, I used a hint to override the optimizer's choice of hash join.
set max_parallel_workers_per_gather = 0;
/+ NestLoop(a b) */ --I have omitted '*+' sign because there is a formatting bug in this borad.
SELECT A.ORD_NO, ORD_LINE_NO, CUST_ID, PROD_ID, A.ORD_DATE, B.ORD_AMT
FROM ORDERS A, ORDERS_DETAIL B
WHERE A.ORD_NO = B.ORD_NO
AND A.ORD_DATE < '20191213'
ORDER BY A.ORD_DATE DESC, B.ORD_AMT
FETCH NEXT 20 ROWS ONLY;
Limit (actual time=872.475..872.478 rows=20 loops=1)
Buffers: shared hit=1550061 read=39262
-> Sort (actual time=872.474..872.476 rows=20 loops=1)
Sort Key: a.ord_date DESC, b.ord_amt
Sort Method: top-N heapsort Memory: 28kB
Buffers: shared hit=1550061 read=39262
-> Nested Loop (actual time=0.076..695.139 rows=1216900 loops=1)
Buffers: shared hit=1550061 read=39262
-> Seq Scan on orders a (actual time=0.053..83.036 rows=121690 loops=1)
Filter: ((ord_date)::text < '20191213'::text)
Rows Removed by Filter: 878310
Buffers: shared read=7353
-> Index Scan using orders_detail_x01 on orders_detail b (actual time=0.001..0.004 rows=10 loops=121690)
Index Cond: (ord_no = a.ord_no)
Buffers: shared hit=1550061 read=31909
Planning Time: 0.186 ms
Execution Time: 872.501 ms
The key point to note is this - incremental sort was not employed, so PostgreSQL accessed the ORDERS_DETAIL_X01 index 121690 times because that is the number of rows extracted from the driving table. If incremental sort had worked, the elapsed time would have been 200 ms or something. I do not know why incremental sort does not work with parallel processing disabled. In this pattern of query where there is no optimal index on the driving table, enabling parallel processing could be a viable option to improve performance.
I again attempted to help the optimizer use incremental sort when parallel processing disabled by rewriting the query as follows:
/+ Set(enable_bitmapscan off ) */
SELECT A.ORD_NO, ORD_LINE_NO, CUST_ID, PROD_ID, A.ORD_DATE, B.ORD_AMT
FROM (SELECT ORD_NO, ORD_DATE, CUST_ID
FROM ORDERS A
WHERE A.ORD_DATE < '20191213'
ORDER BY A.ORD_DATE DESC
) A
, ORDERS_DETAIL B
WHERE A.ORD_NO = B.ORD_NO
ORDER BY A.ORD_DATE DESC, B.ORD_AMT
FETCH NEXT 20 ROWS ONLY;
Limit (actual time=157.080..157.085 rows=20 loops=1)
Buffers: shared hit=3340 read=25688, temp read=434 written=449
-> Incremental Sort (actual time=157.079..157.082 rows=20 loops=1)
Sort Key: a.ord_date DESC, b.ord_amt
Presorted Key: a.ord_date
Full-sort Groups: 1 Sort Method: top-N heapsort Average Memory: 27kB Peak Memory: 27kB
Pre-sorted Groups: 1 Sort Method: top-N heapsort Average Memory: 26kB Peak Memory: 26kB
Buffers: shared hit=3340 read=25688, temp read=434 written=449
-> Nested Loop (actual time=104.432..153.871 rows=16671 loops=1)
Buffers: shared hit=3340 read=25688, temp read=434 written=449
-> Sort (actual time=104.402..104.754 rows=1668 loops=1)
Sort Key: a.ord_date DESC
Sort Method: external merge Disk: 3576kB
Buffers: shared read=7353, temp read=434 written=449
-> Seq Scan on orders a (actual time=0.018..79.230 rows=121690 loops=1)
Filter: ((ord_date)::text < '20191213'::text)
Rows Removed by Filter: 878310
Buffers: shared read=7353
-> Index Scan using orders_detail_x01 on orders_detail b (actual time=0.006..0.028 rows=10 loops=1668)
Index Cond: (ord_no = a.ord_no)
Buffers: shared hit=3340 read=18335
Planning:
Buffers: shared hit=1 read=7
Planning Time: 0.315 ms
Execution Time: 157.673 ms
Note that incremental sort worked, so PostgreSQL accesed the ORDERS_DETAIL_X01 index 1668 times because that is the number of rows extracted from the driving table. If we cannot enable parallel processing, rewriting the query using an inline view could be a viable option.
Conclusion
When two tables are joined and there is no optimal index on the driving table, incremental sort can kick in by using parallel processing or an inline view for the driving table.
Addendum
You may be tempted to create an index to speed up the query. Let's explore how an index can impact query performance.
I have created an index on the ORD_DATE column.
CREATE INDEX ORDERS_X01 ON ORDERS(ORD_DATE);
set max_parallel_workers_per_gather = 0;
Here is the basic statement I want to execute.
SELECT A.ORD_NO, ORD_LINE_NO, CUST_ID, PROD_ID, A.ORD_DATE, B.ORD_AMT
FROM ORDERS A, ORDERS_DETAIL B
WHERE A.ORD_NO = B.ORD_NO
AND A.ORD_DATE < '20191213'
ORDER BY A.ORD_DATE DESC, B.ORD_AMT
FETCH NEXT 20 ROWS ONLY;
Here is the execution plan from PostgreSQL 15.
Limit (actual time=48.743..48.747 rows=20 loops=1)
Buffers: shared hit=10676 read=12674
-> Incremental Sort (actual time=48.742..48.744 rows=20 loops=1)
Sort Key: a.ord_date DESC, b.ord_amt
Presorted Key: a.ord_date
Full-sort Groups: 1 Sort Method: top-N heapsort Average Memory: 27kB Peak Memory: 27kB
Pre-sorted Groups: 1 Sort Method: top-N heapsort Average Memory: 26kB Peak Memory: 26kB
Buffers: shared hit=10676 read=12674
-> Nested Loop (actual time=0.024..45.380 rows=16671 loops=1)
Buffers: shared hit=10676 read=12674
-> Index Scan Backward using orders_x01 on orders a (actual time=0.015..4.102 rows=1668 loops=1)
Index Cond: ((ord_date)::text < '20191213'::text)
Buffers: shared hit=409 read=1266
-> Index Scan using orders_detail_x01 on orders_detail b (actual time=0.005..0.023 rows=10 loops=1668)
Index Cond: (ord_no = a.ord_no)
Buffers: shared hit=10267 read=11408
Planning:
Buffers: shared hit=6 read=10
Planning Time: 0.257 ms
Execution Time: 48.769 ms
We can observe that the elapsed time dropped from 157 ms to 48 ms. PostgreSQL stopped walking the ORDERS_X01 index after scanning 1668 rows and incremental sort was employed.
So is it advisable to create an index to speed up this query?
The answer is : It depends. There are several benefits and drawbacks associated with creating an index to optimize query performance. To gain a better understanding of why creating an index could potentially harm your database system, please refer to the following article.
https://www.percona.com/blog/postgresql-indexes-can-hurt-you-negative-effects-and-the-costs-involved/
