Content-Type: multipart/mixed; boundary="------------w83OiYWIK7THWmr0Iqp8XmOq"
Message-ID: <eef0ea8c-4aaa-8d0d-027f-58b1f35dd170@enterprisedb.com>
Date: Fri, 13 Oct 2023 00:38:40 +0200
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101
 Thunderbird/102.13.0
Content-Language: en-US
To: PostgreSQL Hackers <pgsql-hackers@lists.postgresql.org>
From: Tomas Vondra <tomas.vondra@enterprisedb.com>
Subject: BRIN minmax multi - incorrect distance for infinite timestamp/date
Cc: Ashutosh Bapat <ashutosh.bapat.oss@gmail.com>
Archived-At: 
 <https://www.postgresql.org/message-id/eef0ea8c-4aaa-8d0d-027f-58b1f35dd170%40enterprisedb.com>
Precedence: bulk

This is a multi-part message in MIME format.
--------------w83OiYWIK7THWmr0Iqp8XmOq
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 7bit

Hi,

Ashutosh Bapat reported me off-list a possible issue in how BRIN
minmax-multi calculate distance for infinite timestamp/date values.

The current code does this:

    if (TIMESTAMP_NOT_FINITE(dt1) || TIMESTAMP_NOT_FINITE(dt2))
        PG_RETURN_FLOAT8(0);

so means infinite values are "very close" to any other value, and thus
likely to be merged into a summary range. That's exactly the opposite of
what we want to do, possibly resulting in inefficient indexes.

Consider this example

    create table test (a timestamptz) with (fillfactor=50);

    insert into test
    select (now() + ((10000 * random())::int || ' seconds')::interval)
      from generate_series(1,1000000) s(i);

    update test set a = '-infinity'::timestamptz where random() < 0.01;
    update test set a = 'infinity'::timestamptz where random() < 0.01;

    explain (analyze, timing off, costs off)
     select * from test where a = '2024-01-01'::timestamptz;

                                  QUERY PLAN

------------------------------------------------------------------------------
 Bitmap Heap Scan on test (actual rows=0 loops=1)
   Recheck Cond: (a = '2024-01-01 00:00:00+01'::timestamp with time zone)
   Rows Removed by Index Recheck: 680662
   Heap Blocks: lossy=6024
   ->  Bitmap Index Scan on test_a_idx (actual rows=60240 loops=1)
         Index Cond: (a = '2024-01-01 00:00:00+01'::timestamp with time
zone)
 Planning Time: 0.075 ms
 Execution Time: 106.871 ms
(8 rows)

Clearly, large part of the table gets scanned - this happens because
when building the index, we end up with ranges like this:


    [-infinity,a,b,c,...,x,y,z,infinity]

and we conclude that distance for [-infinity,a] is 0, and we combine
these values into a range. And the same for [z,infinity]. But we should
do exactly the opposite thing - never merge those.

Attached is a patch fixing this, with which the plan looks like this:

                                  QUERY PLAN

------------------------------------------------------------------------------
 Bitmap Heap Scan on test (actual rows=0 loops=1)
   Recheck Cond: (a = '2024-01-01 00:00:00+01'::timestamp with time zone)
   ->  Bitmap Index Scan on test_a_idx (actual rows=0 loops=1)
         Index Cond: (a = '2024-01-01 00:00:00+01'::timestamp with time
zone)
 Planning Time: 0.289 ms
 Execution Time: 9.432 ms
(6 rows)

Which seems much better.


regards

-- 
Tomas Vondra
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company
--------------w83OiYWIK7THWmr0Iqp8XmOq
Content-Type: text/x-patch; charset=UTF-8; name="brin-infinity-fix.patch"
Content-Disposition: attachment; filename="brin-infinity-fix.patch"
Content-Transfer-Encoding: base64

ZGlmZiAtLWdpdCBhL3NyYy9iYWNrZW5kL2FjY2Vzcy9icmluL2JyaW5fbWlubWF4X211bHRp
LmMgYi9zcmMvYmFja2VuZC9hY2Nlc3MvYnJpbi9icmluX21pbm1heF9tdWx0aS5jCmluZGV4
IGY4YjJhM2Y5YmMuLmM4Nzc1YzI3NGUgMTAwNjQ0Ci0tLSBhL3NyYy9iYWNrZW5kL2FjY2Vz
cy9icmluL2JyaW5fbWlubWF4X211bHRpLmMKKysrIGIvc3JjL2JhY2tlbmQvYWNjZXNzL2Jy
aW4vYnJpbl9taW5tYXhfbXVsdGkuYwpAQCAtMjA4NCw4ICsyMDg0LDE0IEBAIGJyaW5fbWlu
bWF4X211bHRpX2Rpc3RhbmNlX2RhdGUoUEdfRlVOQ1RJT05fQVJHUykKIAlEYXRlQURUCQlk
YXRlVmFsMSA9IFBHX0dFVEFSR19EQVRFQURUKDApOwogCURhdGVBRFQJCWRhdGVWYWwyID0g
UEdfR0VUQVJHX0RBVEVBRFQoMSk7CiAKKwkvKgorCSAqIElmIGVpdGhlciB2YWx1ZSBpcyBp
bmZpbml0ZSwgd2UgdHJlYXQgdGhlbSBhcyBpbiBpbmZpbml0ZSBkaXN0YW5jZS4KKwkgKiBX
ZSBkZWR1cGxpY2F0ZSB0aGUgdmFsdWVzIGJlZm9yZSBjYWxjdWxhdGluZyBkaXN0YW5jZXMg
Zm9yIHRoZW0sIHNvCisJICogZWl0aGVyIG9uZSB2YWx1ZSBpcyBmaW5pdGUsIG9yIHRoZSBz
aWduIGlzIGRpZmZlcmVudCAtIHNvIHRoZQorCSAqIGluaWZpbml0ZSBkaXN0YW5jZSBpcyBh
cHByb3ByaWF0ZSBmb3IgYm90aCBjYXNlcy4KKwkgKi8KIAlpZiAoREFURV9OT1RfRklOSVRF
KGRhdGVWYWwxKSB8fCBEQVRFX05PVF9GSU5JVEUoZGF0ZVZhbDIpKQotCQlQR19SRVRVUk5f
RkxPQVQ4KDApOworCQlQR19SRVRVUk5fRkxPQVQ4KGdldF9mbG9hdDhfaW5maW5pdHkoKSk7
CiAKIAlQR19SRVRVUk5fRkxPQVQ4KGRhdGVWYWwxIC0gZGF0ZVZhbDIpOwogfQpAQCAtMjE0
MSw4ICsyMTQ3LDE0IEBAIGJyaW5fbWlubWF4X211bHRpX2Rpc3RhbmNlX3RpbWVzdGFtcChQ
R19GVU5DVElPTl9BUkdTKQogCVRpbWVzdGFtcAlkdDEgPSBQR19HRVRBUkdfVElNRVNUQU1Q
KDApOwogCVRpbWVzdGFtcAlkdDIgPSBQR19HRVRBUkdfVElNRVNUQU1QKDEpOwogCisJLyoK
KwkgKiBJZiBlaXRoZXIgdmFsdWUgaXMgaW5maW5pdGUsIHdlIHRyZWF0IHRoZW0gYXMgaW4g
aW5maW5pdGUgZGlzdGFuY2UuCisJICogV2UgZGVkdXBsaWNhdGUgdGhlIHZhbHVlcyBiZWZv
cmUgY2FsY3VsYXRpbmcgZGlzdGFuY2VzIGZvciB0aGVtLCBzbworCSAqIGVpdGhlciBvbmUg
dmFsdWUgaXMgZmluaXRlLCBvciB0aGUgc2lnbiBpcyBkaWZmZXJlbnQgLSBzbyB0aGUKKwkg
KiBpbmlmaW5pdGUgZGlzdGFuY2UgaXMgYXBwcm9wcmlhdGUgZm9yIGJvdGggY2FzZXMuCisJ
ICovCiAJaWYgKFRJTUVTVEFNUF9OT1RfRklOSVRFKGR0MSkgfHwgVElNRVNUQU1QX05PVF9G
SU5JVEUoZHQyKSkKLQkJUEdfUkVUVVJOX0ZMT0FUOCgwKTsKKwkJUEdfUkVUVVJOX0ZMT0FU
OChnZXRfZmxvYXQ4X2luZmluaXR5KCkpOwogCiAJZGVsdGEgPSBkdDIgLSBkdDE7CiAK

--------------w83OiYWIK7THWmr0Iqp8XmOq--