Unnecessary buffer usage with multicolumn index, row comparison, and equility constraint

From: WU Yan <4wuyan(at)gmail(dot)com>
To: pgsql-general(at)lists(dot)postgresql(dot)org
Subject: Unnecessary buffer usage with multicolumn index, row comparison, and equility constraint
Date: 2024-05-11 03:27:40
Message-ID: CAAdwFAxBjyrYUkH7u+EceTaztd1QxBtBY1Teux8K=vcGKe==-A@mail.gmail.com
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-general

Hi everyone, first time here. Please kindly let me know if this is not the
right place to ask.

I notice a simple query can read a lot of buffer blocks in a meaningless
way, when
1. there is an index scan on a multicolumn index
2. there is row constructor comparison in the Index Cond
3. there is also an equality constraint on the leftmost column of the
multicolumn index

## How to reproduce

I initially noticed it on AWS Aurora RDS, but it can be reproduced in
docker container as well.
```bash
docker run --name test-postgres -e POSTGRES_PASSWORD=mysecretpassword -d -p
5432:5432 postgres:16.3
```

Create a table with a multicolumn index. Populate 12 million rows with
random integers.
```sql
CREATE TABLE t(a int, b int);
CREATE INDEX my_idx ON t USING BTREE (a, b);

INSERT INTO t(a, b)
SELECT
(random() * 123456)::int AS a,
(random() * 123456)::int AS b
FROM
generate_series(1, 12345678);

ANALYZE t;
```

Simple query that uses the multicolumn index.
```
postgres=# explain (analyze, buffers) select * from t where row(a, b) >
row(123450, 123450) and a = 0 order by a, b;
QUERY PLAN
-------------------------------------------------------------------------------------------------------------------
Index Only Scan using my_idx on t (cost=0.43..8.46 rows=1 width=8)
(actual time=284.312..284.314 rows=0 loops=1)
Index Cond: ((ROW(a, b) > ROW(123450, 123450)) AND (a = 0))
Heap Fetches: 0
Buffers: shared hit=3777 read=37304 written=11713
Planning:
Buffers: shared hit=22 read=4
Planning Time: 0.270 ms
Execution Time: 284.341 ms
(8 rows)
```

## Expected output

The number of buffer blocks used is high. I expect it to be no more than
when there’s only one constraint.

```
postgres=# explain (analyze, buffers) select * from t where row(a, b) >
row(123450, 123450) order by a, b;
QUERY PLAN
--------------------------------------------------------------------------------------------------------------------
Index Only Scan using my_idx on t (cost=0.43..23.67 rows=642 width=8)
(actual time=0.030..0.158 rows=542 loops=1)
Index Cond: (ROW(a, b) > ROW(123450, 123450))
Heap Fetches: 0
Buffers: shared hit=254 read=3
Planning:
Buffers: shared read=4
Planning Time: 0.232 ms
Execution Time: 0.206 ms
(8 rows)

postgres=# explain (analyze, buffers) select * from t where a = 0 order by
a, b;
QUERY PLAN
------------------------------------------------------------------------------------------------------------------
Index Only Scan using my_idx on t (cost=0.43..6.20 rows=101 width=8)
(actual time=0.099..0.113 rows=57 loops=1)
Index Cond: (a = 0)
Heap Fetches: 0
Buffers: shared hit=27 read=2
Planning Time: 0.081 ms
Execution Time: 0.131 ms
(6 rows)
```

## Postgres version

16.3

## Platform information

I can reproduce it on the latest postgres docker image, which is based on
Debian Linux. Originally found the issue on AWS Aurora.

The following are my own observation and thoughts. Please disregard if it’s
distraction.

For a general form of
```sql
select * from t where (a, b) > (x, y) and a = z order by a, b;
```

1. The number of buffer blocks is proportional to the gap between x and z.
Strictly, it’s max(0, min(x, max(a)) – max(z, min(a))).

```
postgres=# explain (analyze, buffers) select * from t where row(a, b) >
row(123450, 123450) and a = -30000 order by a, b;
QUERY PLAN
-------------------------------------------------------------------------------------------------------------------
Index Only Scan using my_idx on t (cost=0.43..4.45 rows=1 width=8)
(actual time=243.173..243.175 rows=0 loops=1)
Index Cond: ((ROW(a, b) > ROW(123450, 123450)) AND (a =
'-30000'::integer))
Heap Fetches: 0
Buffers: shared hit=1 read=41080
Planning:
Buffers: shared hit=2 read=2
Planning Time: 0.174 ms
Execution Time: 243.199 ms
(8 rows)

postgres=# explain (analyze, buffers) select * from t where row(a, b) >
row(123450, 123450) and a = 0 order by a, b;
QUERY PLAN
-------------------------------------------------------------------------------------------------------------------
Index Only Scan using my_idx on t (cost=0.43..4.45 rows=1 width=8)
(actual time=230.425..230.426 rows=0 loops=1)
Index Cond: ((ROW(a, b) > ROW(123450, 123450)) AND (a = 0))
Heap Fetches: 0
Buffers: shared hit=1 read=41080
Planning:
Buffers: shared read=4
Planning Time: 0.296 ms
Execution Time: 230.460 ms
(8 rows)

postgres=# explain (analyze, buffers) select * from t where row(a, b) >
row(123450, 123450) and a = 30000 order by a, b;
QUERY PLAN
-------------------------------------------------------------------------------------------------------------------
Index Only Scan using my_idx on t (cost=0.43..4.45 rows=1 width=8)
(actual time=171.787..171.788 rows=0 loops=1)
Index Cond: ((ROW(a, b) > ROW(123450, 123450)) AND (a = 30000))
Heap Fetches: 0
Buffers: shared hit=1 read=31126
Planning:
Buffers: shared read=4
Planning Time: 0.191 ms
Execution Time: 171.812 ms
(8 rows)

postgres=# explain (analyze, buffers) select * from t where row(a, b) >
row(123450, 123450) and a = 60000 order by a, b;
QUERY PLAN
-------------------------------------------------------------------------------------------------------------------
Index Only Scan using my_idx on t (cost=0.43..4.45 rows=1 width=8)
(actual time=137.516..137.518 rows=0 loops=1)
Index Cond: ((ROW(a, b) > ROW(123450, 123450)) AND (a = 60000))
Heap Fetches: 0
Buffers: shared hit=1 read=21139
Planning:
Buffers: shared read=4
Planning Time: 0.212 ms
Execution Time: 137.543 ms
(8 rows)

postgres=# explain (analyze, buffers) select * from t where row(a, b) >
row(123450, 123450) and a = 90000 order by a, b;
QUERY PLAN
-----------------------------------------------------------------------------------------------------------------
Index Only Scan using my_idx on t (cost=0.43..4.45 rows=1 width=8)
(actual time=57.868..57.870 rows=0 loops=1)
Index Cond: ((ROW(a, b) > ROW(123450, 123450)) AND (a = 90000))
Heap Fetches: 0
Buffers: shared hit=11187 read=1
Planning:
Buffers: shared hit=1 read=3
Planning Time: 0.240 ms
Execution Time: 57.896 ms
(8 rows)

postgres=# explain (analyze, buffers) select * from t where row(a, b) >
row(123450, 123450) and a = 120000 order by a, b;
QUERY PLAN
---------------------------------------------------------------------------------------------------------------
Index Only Scan using my_idx on t (cost=0.43..4.45 rows=1 width=8)
(actual time=6.018..6.019 rows=0 loops=1)
Index Cond: ((ROW(a, b) > ROW(123450, 123450)) AND (a = 120000))
Heap Fetches: 0
Buffers: shared hit=1173 read=1
Planning:
Buffers: shared hit=4
Planning Time: 0.122 ms
Execution Time: 6.052 ms
(8 rows)
```

2. It’s not an issue when `a=x` becomes `a<x` or `a>x`.

```
postgres=# explain (analyze, buffers) select * from t where row(a, b) >
row(123450, 123450) and a < 100 order by a, b;
QUERY PLAN
---------------------------------------------------------------------------------------------------------------
Index Only Scan using my_idx on t (cost=0.43..4.45 rows=1 width=8)
(actual time=0.006..0.006 rows=0 loops=1)
Index Cond: ((ROW(a, b) > ROW(123450, 123450)) AND (a < 100))
Heap Fetches: 0
Buffers: shared hit=3
Planning:
Buffers: shared hit=8
Planning Time: 0.119 ms
Execution Time: 0.020 ms
(8 rows)

postgres=# explain (analyze, buffers) select * from t where row(a, b) >
row(123450, 123450) and a > 100 order by a, b;
QUERY PLAN
--------------------------------------------------------------------------------------------------------------------
Index Only Scan using my_idx on t (cost=0.43..25.25 rows=641 width=8)
(actual time=0.040..0.339 rows=542 loops=1)
Index Cond: ((ROW(a, b) > ROW(123450, 123450)) AND (a > 100))
Heap Fetches: 0
Buffers: shared hit=257
Planning:
Buffers: shared hit=8
Planning Time: 0.233 ms
Execution Time: 0.443 ms
(8 rows)
```

3. It’s not an issue when `a=x` becomes `b=x`.

4. The example query is trivial and for demo purpose only. Obviously
there’s no need to supply `a = 0` when there’s `(a, b) > (123450, 123450)`.
However, in practice it can be a problem when the table is joined to other
tables, resulting in a nested loop for a list of `a` values that we have no
control of, while `(a, b) > (x, y)` is used for paging.

5. My current workaround is add `AND a >= x` to `(a, b) > (x, y)`. However,
this makes the planner underestimate the number of rows due to the
multiplied selectivities.

Best regards,
Yan

Responses

Browse pgsql-general by date

  From Date Subject
Next Message Ron Johnson 2024-05-11 04:05:22 Re: Unnecessary buffer usage with multicolumn index, row comparison, and equility constraint
Previous Message David Rowley 2024-05-11 01:37:10 Re: SELECT DISTINCT chooses parallel seqscan instead of indexscan on huge table with 1000 partitions