Content-Type: multipart/mixed; boundary="------------H3kYmtJBaDN7Qm4rf6ikTPj0"
Message-ID: <83464ae9-a79a-43c8-a425-4b0773f9e759@tantorlabs.com>
Date: Wed, 18 Mar 2026 17:26:51 +0300
MIME-Version: 1.0
User-Agent: Mozilla Thunderbird
Subject: Re: Reduce planning time for large NOT IN lists containing NULL
To: David Rowley <dgrowleyml@gmail.com>
Cc: Zsolt Parragi <zsolt.parragi@percona.com>,
 David Geier <geidav.pg@gmail.com>,
 PostgreSQL Developers <pgsql-hackers@lists.postgresql.org>
References: <eaa2598c-5356-4e1e-9ec3-5fd6eb1cd704@tantorlabs.com>
 <52596e08-0902-475b-ad0f-265ec6918f19@gmail.com>
 <7791ec74-369d-48c7-969c-cf4ad18024f2@tantorlabs.com>
 <ed61316c-2e48-45d1-9cca-dc539bfd93b9@tantorlabs.com>
 <dd5e91c1-5e59-471c-bd9d-96a11c7928f4@tantorlabs.com>
 <6b3aebb5-f26c-4f50-abd6-e733d452af26@gmail.com>
 <f43547c8-1a21-4337-98f9-f6a1d2b8fd2b@tantorlabs.com>
 <CAN4CZFNJHro_pEVTHggBX43f+AebwKLZdp39+V4pV0EB4BZuZw@mail.gmail.com>
 <52f3c637-465d-4f0e-9546-732ecf61ab87@tantorlabs.com>
 <3fc74079-f429-48c8-ad8c-688b21d4d1c1@gmail.com>
 <4c761b02-5a60-4076-aa0c-9c6fef06e2c1@tantorlabs.com>
 <CAN4CZFOTAyVk9srBp560049Xu655xUDZv5NBTvj7RYND-xKymA@mail.gmail.com>
 <2bdf4a7e-f5b9-4e75-b5a3-1e2608fd3297@tantorlabs.com>
 <CAApHDvphShGABn-3AoE36dTvGHW7gUpFSw0_ZZnH84wGCW3hHw@mail.gmail.com>
 <390a46f3-dbc4-4dc1-b49d-5cc61dd36026@tantorlabs.com>
 <977365f2-2ab7-4008-8d9c-f62ef5271cea@tantorlabs.com>
 <CAApHDvq+Tk=BUwzJZsPsm49_QxAXRe9Vd2iFroMsB_Mnt8LdHg@mail.gmail.com>
Content-Language: en-US
From: Ilia Evdokimov <ilya.evdokimov@tantorlabs.com>
In-Reply-To: 
 <CAApHDvq+Tk=BUwzJZsPsm49_QxAXRe9Vd2iFroMsB_Mnt8LdHg@mail.gmail.com>
Archived-At: 
 <https://www.postgresql.org/message-id/83464ae9-a79a-43c8-a425-4b0773f9e759%40tantorlabs.com>
Precedence: bulk

This is a multi-part message in MIME format.
--------------H3kYmtJBaDN7Qm4rf6ikTPj0
Content-Type: multipart/alternative;
 boundary="------------SH8mH5n2O0HqKWK4QOXsY0SY"

--------------SH8mH5n2O0HqKWK4QOXsY0SY
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit

On 3/18/26 07:32, David Rowley wrote:

> Thanks. I've pushed 0001.
>
> I ended up renaming the new file to planner_est.sql as the function
> handles width estimate masking too, so I thought just calling it
> selectivity_est was a bit too restrictive. I went with planner_est.

+1. Thank you.

> That means 0002 needed rebased. I've done that in the attached.

After the new test was committed, I realized that v8 tests relies on 
selectivity calculation, which are not guaranteed to remain stable over 
time and way vary depending on planner heuristics or platform 
differences. Therefore, it seems better to remove tests from v8.

Instead, we can test the invariant behavior: when NULL is present in a 
<> ALL clause, the selectivity is always 0.0.

The v9-patch adds three test cases: a degenerate case with only NULL, 
NULL combined with constants, NULL combined with both constants and 
non-constant expression.

Thoughts?


-- 
Best regards,
Ilia Evdokimov,
Tantor Labs LLC,
https://tantorlabs.com/

--------------SH8mH5n2O0HqKWK4QOXsY0SY
Content-Type: text/html; charset=UTF-8
Content-Transfer-Encoding: 8bit

<!DOCTYPE html>
<html>
  <head>
    <meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
  </head>
  <body>
    <p>On 3/18/26 07:32, David Rowley wrote:</p>
    <blockquote type="cite"
cite="mid:CAApHDvq+Tk=BUwzJZsPsm49_QxAXRe9Vd2iFroMsB_Mnt8LdHg@mail.gmail.com">
      <pre wrap="" class="moz-quote-pre">Thanks. I've pushed 0001.

I ended up renaming the new file to planner_est.sql as the function
handles width estimate masking too, so I thought just calling it
selectivity_est was a bit too restrictive. I went with planner_est.</pre>
    </blockquote>
    <p>+1. Thank you.</p>
    <p><span style="white-space: pre-wrap">
</span></p>
    <blockquote type="cite"
cite="mid:CAApHDvq+Tk=BUwzJZsPsm49_QxAXRe9Vd2iFroMsB_Mnt8LdHg@mail.gmail.com">
      <pre wrap="" class="moz-quote-pre">That means 0002 needed rebased. I've done that in the attached.</pre>
    </blockquote>
    <p>After the new test was committed, I realized that v8 tests relies
      on selectivity calculation, which are not guaranteed to remain
      stable over time and way vary depending on planner heuristics or
      platform differences. Therefore, it seems better to remove tests
      from v8.</p>
    <p>Instead, we can test the invariant behavior: when NULL is present
      in a &lt;&gt; ALL clause, the selectivity is always 0.0.</p>
    <p>The v9-patch adds three test cases: a degenerate case with only
      NULL, NULL combined with constants, NULL combined with both
      constants and non-constant expression.</p>
    <p>Thoughts?</p>
    <p><br>
    </p>
    <p><span class="moz-txt-tag">-- <br>
      </span>Best regards,
      <br>
      Ilia Evdokimov,
      <br>
      Tantor Labs LLC,
      <br>
      <a class="moz-txt-link-freetext" href="https://tantorlabs.com/">https://tantorlabs.com/</a></p>
  </body>
</html>

--------------SH8mH5n2O0HqKWK4QOXsY0SY--

--------------H3kYmtJBaDN7Qm4rf6ikTPj0
Content-Type: text/x-patch; charset=UTF-8;
 name="v9-0001-Reduce-planning-time-for-large-NOT-IN-lists-conta.patch"
Content-Disposition: attachment;
 filename*0="v9-0001-Reduce-planning-time-for-large-NOT-IN-lists-conta.pa";
 filename*1="tch"
Content-Transfer-Encoding: base64

RnJvbSBjMGJhOTgxNDFjMTgzMDkwNzgzNjUzZDg4MmQyMDZhY2I3YzM4YTI5IE1vbiBTZXAg
MTcgMDA6MDA6MDAgMjAwMQpGcm9tOiBJbGlhIEV2ZG9raW1vdiA8aWx5YS5ldmRva2ltb3ZA
dGFudG9ybGFicy5ydT4KRGF0ZTogV2VkLCAxOCBNYXIgMjAyNiAxNzoyMzo1MCArMDMwMApT
dWJqZWN0OiBbUEFUQ0ggdjldIFJlZHVjZSBwbGFubmluZyB0aW1lIGZvciBsYXJnZSBOT1Qg
SU4gbGlzdHMgY29udGFpbmluZwogTlVMTAoKRm9yIHggPD4gQUxMICguLi4pLCB0aGUgcHJl
c2VuY2Ugb2YgYSBOVUxMIG1ha2VzIHRoZSBzZWxlY3Rpdml0eSAwLjAuCgpUaGUgcGxhbm5l
ciBjdXJyZW50bHkgc3RpbGwgaXRlcmF0ZXMgb3ZlciBhbGwgZWxlbWVudHMgYW5kIGNvbXB1
dGVzCnBlci1lbGVtZW50IHNlbGVjdGl2aXR5LCBldmVuIHRob3VnaCB0aGUgZmluYWwgcmVz
dWx0IGlzIGtub3duLgoKQWRkIGFuIGVhcmx5IE5VTEwgY2hlY2sgZm9yIGNvbnN0YW50IGFy
cmF5cyBhbmQgaW1tZWRpYXRlbHkgcmV0dXJuCjAuMCB1bmRlciBBTEwgc2VtYW50aWNzLgoK
VGhpcyByZWR1Y2VzIHBsYW5uaW5nIHRpbWUgZm9yIGxhcmdlIDw+IEFMTCBsaXN0cyB3aXRo
b3V0CmNoYW5naW5nIHNlbWFudGljcy4KLS0tCiBzcmMvYmFja2VuZC91dGlscy9hZHQvc2Vs
ZnVuY3MuYyAgICAgICAgICB8IDE3ICsrKysrKysrKysrCiBzcmMvdGVzdC9yZWdyZXNzL2V4
cGVjdGVkL3BsYW5uZXJfZXN0Lm91dCB8IDM1ICsrKysrKysrKysrKysrKysrKysrKysrCiBz
cmMvdGVzdC9yZWdyZXNzL3NxbC9wbGFubmVyX2VzdC5zcWwgICAgICB8IDE2ICsrKysrKysr
KysrCiAzIGZpbGVzIGNoYW5nZWQsIDY4IGluc2VydGlvbnMoKykKCmRpZmYgLS1naXQgYS9z
cmMvYmFja2VuZC91dGlscy9hZHQvc2VsZnVuY3MuYyBiL3NyYy9iYWNrZW5kL3V0aWxzL2Fk
dC9zZWxmdW5jcy5jCmluZGV4IGQ0ZGEwZThkZWE5Li4wNzNkOTNmNGYzZCAxMDA2NDQKLS0t
IGEvc3JjL2JhY2tlbmQvdXRpbHMvYWR0L3NlbGZ1bmNzLmMKKysrIGIvc3JjL2JhY2tlbmQv
dXRpbHMvYWR0L3NlbGZ1bmNzLmMKQEAgLTIwMTgsNiArMjAxOCwxNSBAQCBzY2FsYXJhcnJh
eXNlbChQbGFubmVySW5mbyAqcm9vdCwKIAkJaWYgKGFycmF5aXNudWxsKQkJLyogcXVhbCBj
YW4ndCBzdWNjZWVkIGlmIG51bGwgYXJyYXkgKi8KIAkJCXJldHVybiAoU2VsZWN0aXZpdHkp
IDAuMDsKIAkJYXJyYXl2YWwgPSBEYXR1bUdldEFycmF5VHlwZVAoYXJyYXlkYXR1bSk7CisK
KwkJLyoKKwkJICogRm9yIEFMTCBzZW1hbnRpY3MsIGlmIHRoZSBhcnJheSBjb250YWlucyBO
VUxMLCBhc3N1bWUgb3BlcmF0b3IgaXMKKwkJICogc3RyaWN0LiBUaGUgU2NhbGFyQXJyYXlP
cEV4cHIgY2Fubm90IGV2YWx1YXRlIHRvIFRSVUUsIHNvIHJldHVybgorCQkgKiB6ZXJvLgor
CQkgKi8KKwkJaWYgKCF1c2VPciAmJiBhcnJheV9jb250YWluc19udWxscyhhcnJheXZhbCkp
CisJCQlyZXR1cm4gKFNlbGVjdGl2aXR5KSAwLjA7CisKIAkJZ2V0X3R5cGxlbmJ5dmFsYWxp
Z24oQVJSX0VMRU1UWVBFKGFycmF5dmFsKSwKIAkJCQkJCQkgJmVsbWxlbiwgJmVsbWJ5dmFs
LCAmZWxtYWxpZ24pOwogCQlkZWNvbnN0cnVjdF9hcnJheShhcnJheXZhbCwKQEAgLTIxMTUs
NiArMjEyNCwxNCBAQCBzY2FsYXJhcnJheXNlbChQbGFubmVySW5mbyAqcm9vdCwKIAkJCUxp
c3QJICAgKmFyZ3M7CiAJCQlTZWxlY3Rpdml0eSBzMjsKIAorCQkJLyoKKwkJCSAqIEZvciBB
TEwgc2VtYW50aWNzLCBpZiB0aGUgYXJyYXkgY29udGFpbnMgTlVMTCwgYXNzdW1lIG9wZXJh
dG9yCisJCQkgKiBpcyBzdHJpY3QuIFRoZSBTY2FsYXJBcnJheU9wRXhwciBjYW5ub3QgZXZh
bHVhdGUgdG8gVFJVRSwgc28KKwkJCSAqIHJldHVybiB6ZXJvLgorCQkJICovCisJCQlpZiAo
IXVzZU9yICYmIElzQShlbGVtLCBDb25zdCkgJiYgKChDb25zdCAqKSBlbGVtKS0+Y29uc3Rp
c251bGwpCisJCQkJcmV0dXJuIChTZWxlY3Rpdml0eSkgMC4wOworCiAJCQkvKgogCQkJICog
VGhlb3JldGljYWxseSwgaWYgZWxlbSBpc24ndCBvZiBub21pbmFsX2VsZW1lbnRfdHlwZSB3
ZSBzaG91bGQKIAkJCSAqIGluc2VydCBhIFJlbGFiZWxUeXBlLCBidXQgaXQgc2VlbXMgdW5s
aWtlbHkgdGhhdCBhbnkgb3BlcmF0b3IKZGlmZiAtLWdpdCBhL3NyYy90ZXN0L3JlZ3Jlc3Mv
ZXhwZWN0ZWQvcGxhbm5lcl9lc3Qub3V0IGIvc3JjL3Rlc3QvcmVncmVzcy9leHBlY3RlZC9w
bGFubmVyX2VzdC5vdXQKaW5kZXggM2E0NzA2MTgwMGEuLjYyNGQ1ODU4Njg3IDEwMDY0NAot
LS0gYS9zcmMvdGVzdC9yZWdyZXNzL2V4cGVjdGVkL3BsYW5uZXJfZXN0Lm91dAorKysgYi9z
cmMvdGVzdC9yZWdyZXNzL2V4cGVjdGVkL3BsYW5uZXJfZXN0Lm91dApAQCAtMTgzLDQgKzE4
MywzOSBAQCBmYWxzZSwgdHJ1ZSwgZmFsc2UsIHRydWUpOwogIEZ1bmN0aW9uIFNjYW4gb24g
Z2VuZXJhdGVfc2VyaWVzIGcgIChjb3N0PU4uLk4gcm93cz0xMDAwIHdpZHRoPU4pCiAoMSBy
b3cpCiAKKy0tCistLSBUZXN0IDw+IEFMTCBiZWhhdmlvciB3aGVuIE5VTEwgYXBwZWFycyBp
biB0aGUgYXJyYXkKKy0tCitTRUxFQ1QgZXhwbGFpbl9tYXNrX2Nvc3RzKCQkCitTRUxFQ1Qg
KiBGUk9NIHRlbmsxIFdIRVJFIHVuaXF1ZTEgPD4gQUxMIChBUlJBWVtOVUxMXTo6aW50ZWdl
cltdKTskJCwKK3RydWUsIHRydWUsIGZhbHNlLCB0cnVlKTsKKyAgICAgICAgICAgICAgICAg
ICAgICAgICAgICBleHBsYWluX21hc2tfY29zdHMgICAgICAgICAgICAgICAgICAgICAgICAg
ICAgCistLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0t
LS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLQorIFNlcSBTY2FuIG9uIHRlbmsxICAoY29zdD1O
Li5OIHJvd3M9MSB3aWR0aD1OKSAoYWN0dWFsIHJvd3M9MC4wMCBsb29wcz0xKQorICAgRmls
dGVyOiAodW5pcXVlMSA8PiBBTEwgKCd7TlVMTH0nOjppbnRlZ2VyW10pKQorICAgUm93cyBS
ZW1vdmVkIGJ5IEZpbHRlcjogMTAwMDAKKygzIHJvd3MpCisKK1NFTEVDVCBleHBsYWluX21h
c2tfY29zdHMoJCQKK1NFTEVDVCAqIEZST00gdGVuazEgV0hFUkUgdW5pcXVlMSA8PiBBTEwg
KEFSUkFZWzEsIDIsIDk5LCBOVUxMXSk7JCQsCit0cnVlLCB0cnVlLCBmYWxzZSwgdHJ1ZSk7
CisgICAgICAgICAgICAgICAgICAgICAgICAgICAgZXhwbGFpbl9tYXNrX2Nvc3RzICAgICAg
ICAgICAgICAgICAgICAgICAgICAgIAorLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0t
LS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0KKyBTZXEgU2Nh
biBvbiB0ZW5rMSAgKGNvc3Q9Ti4uTiByb3dzPTEgd2lkdGg9TikgKGFjdHVhbCByb3dzPTAu
MDAgbG9vcHM9MSkKKyAgIEZpbHRlcjogKHVuaXF1ZTEgPD4gQUxMICgnezEsMiw5OSxOVUxM
fSc6OmludGVnZXJbXSkpCisgICBSb3dzIFJlbW92ZWQgYnkgRmlsdGVyOiAxMDAwMAorKDMg
cm93cykKKworU0VMRUNUIGV4cGxhaW5fbWFza19jb3N0cygkJAorU0VMRUNUICogRlJPTSB0
ZW5rMSBXSEVSRSB1bmlxdWUxIDw+IEFMTCAoQVJSQVlbMSwgMiwgOTgsIChTRUxFQ1QgOTkp
LCBOVUxMXSk7JCQsCit0cnVlLCB0cnVlLCBmYWxzZSwgdHJ1ZSk7CisgICAgICAgICAgICAg
ICAgICAgICAgICAgICAgICAgICBleHBsYWluX21hc2tfY29zdHMgICAgICAgICAgICAgICAg
ICAgICAgICAgICAgICAgICAgCistLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0t
LS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tLS0tCisg
U2VxIFNjYW4gb24gdGVuazEgIChjb3N0PU4uLk4gcm93cz0xIHdpZHRoPU4pIChhY3R1YWwg
cm93cz0wLjAwIGxvb3BzPTEpCisgICBGaWx0ZXI6ICh1bmlxdWUxIDw+IEFMTCAoQVJSQVlb
MSwgMiwgOTgsIChJbml0UGxhbiBleHByXzEpLmNvbDEsIE5VTEw6OmludGVnZXJdKSkKKyAg
IFJvd3MgUmVtb3ZlZCBieSBGaWx0ZXI6IDEwMDAwCisgICBJbml0UGxhbiBleHByXzEKKyAg
ICAgLT4gIFJlc3VsdCAgKGNvc3Q9Ti4uTiByb3dzPTEgd2lkdGg9TikgKGFjdHVhbCByb3dz
PTEuMDAgbG9vcHM9MSkKKyg1IHJvd3MpCisKIERST1AgRlVOQ1RJT04gZXhwbGFpbl9tYXNr
X2Nvc3RzKHRleHQsIGJvb2wsIGJvb2wsIGJvb2wsIGJvb2wpOwpkaWZmIC0tZ2l0IGEvc3Jj
L3Rlc3QvcmVncmVzcy9zcWwvcGxhbm5lcl9lc3Quc3FsIGIvc3JjL3Rlc3QvcmVncmVzcy9z
cWwvcGxhbm5lcl9lc3Quc3FsCmluZGV4IDQ3ZDVhZTY3OWM3Li42MWM5ZjY0MDc2MSAxMDA2
NDQKLS0tIGEvc3JjL3Rlc3QvcmVncmVzcy9zcWwvcGxhbm5lcl9lc3Quc3FsCisrKyBiL3Ny
Yy90ZXN0L3JlZ3Jlc3Mvc3FsL3BsYW5uZXJfZXN0LnNxbApAQCAtMTMxLDUgKzEzMSwyMSBA
QCBTRUxFQ1QgZXhwbGFpbl9tYXNrX2Nvc3RzKCQkCiBTRUxFQ1QgKiBGUk9NIGdlbmVyYXRl
X3NlcmllcygyNS4wLCAyLjAsIDAuMCkgZyhzKTskJCwKIGZhbHNlLCB0cnVlLCBmYWxzZSwg
dHJ1ZSk7CiAKKy0tCistLSBUZXN0IDw+IEFMTCBiZWhhdmlvciB3aGVuIE5VTEwgYXBwZWFy
cyBpbiB0aGUgYXJyYXkKKy0tCisKK1NFTEVDVCBleHBsYWluX21hc2tfY29zdHMoJCQKK1NF
TEVDVCAqIEZST00gdGVuazEgV0hFUkUgdW5pcXVlMSA8PiBBTEwgKEFSUkFZW05VTExdOjpp
bnRlZ2VyW10pOyQkLAordHJ1ZSwgdHJ1ZSwgZmFsc2UsIHRydWUpOworCitTRUxFQ1QgZXhw
bGFpbl9tYXNrX2Nvc3RzKCQkCitTRUxFQ1QgKiBGUk9NIHRlbmsxIFdIRVJFIHVuaXF1ZTEg
PD4gQUxMIChBUlJBWVsxLCAyLCA5OSwgTlVMTF0pOyQkLAordHJ1ZSwgdHJ1ZSwgZmFsc2Us
IHRydWUpOworCitTRUxFQ1QgZXhwbGFpbl9tYXNrX2Nvc3RzKCQkCitTRUxFQ1QgKiBGUk9N
IHRlbmsxIFdIRVJFIHVuaXF1ZTEgPD4gQUxMIChBUlJBWVsxLCAyLCA5OCwgKFNFTEVDVCA5
OSksIE5VTExdKTskJCwKK3RydWUsIHRydWUsIGZhbHNlLCB0cnVlKTsKKwogCiBEUk9QIEZV
TkNUSU9OIGV4cGxhaW5fbWFza19jb3N0cyh0ZXh0LCBib29sLCBib29sLCBib29sLCBib29s
KTsKLS0gCjIuMzQuMQoK

--------------H3kYmtJBaDN7Qm4rf6ikTPj0--