Content-Type: multipart/mixed; boundary="------------5zRGx0TmCB4vzKWybUsQvigs"
Message-ID: <7791ec74-369d-48c7-969c-cf4ad18024f2@tantorlabs.com>
Date: Fri, 20 Feb 2026 12:06:55 +0300
MIME-Version: 1.0
User-Agent: Mozilla Thunderbird
Subject: Re: Reduce planning time for large NOT IN lists containing NULL
To: 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>
Content-Language: en-US
From: Ilia Evdokimov <ilya.evdokimov@tantorlabs.com>
In-Reply-To: <52596e08-0902-475b-ad0f-265ec6918f19@gmail.com>
Archived-At: <https://www.postgresql.org/message-id/7791ec74-369d-48c7-969c-cf4ad18024f2%40tantorlabs.com>
Precedence: bulk

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

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

Hi David,

Thanks for review

On 2/19/26 18:38, David Geier wrote:
> +1 on the general idea.
>
>> For constant arrays I propose adding a simple pre-check before entering
>> the per-element loop: detect whether the array contains at least one
>> NULL element (e.g., via memchr() for the deconstructed array case). If
>> so, and we are in the ALL / NOT IN case, we can immediately return
>> selectivity = 0.0 and skip all further computation. This would avoid
>> extra per-element estimation work while preserving semantics.
> How much overhead does the memchr() call add? It seems like this
> approach optimizes the edge case at the expense of the common case,
> which doesn't seem like a good trade-off.
>
> How about instead adding a flag to ArrayType which indicates if the
> array contains NULL or not. This flag could be set in
> construct_md_array() which already iterates over all elements. The flag
> would need to be kept up-to-date, e.g. in array_set_element() and
> possibly other functions modifying the array.

It seems we might reinventing the wheel.

There is already ARR_HASNULL() which allows us to detect the presence of 
NULL in ArrayType.

>> In cases where array elements are not known to be constants in advance,
>> such a pre-check is less straightforward, because each element must
>> first be inspected to determine whether it is a Const and whether it is
>> NULL. That already requires iterating through the list, so introducing a
>> separate early pass would not actually reduce the amount of work.
>> Therefore, it like makes sense to keep the current behavior in that
>> situation.
> Agreed.

After thinking about this more, is seems reasonable to short-circuit еру 
loop when we detect a NULL element by checking whether the element is a 
Const and NULL.


I've attached v2 patch.

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

--------------r8LAm0pPWkkB9qEMRqs6QNgT
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>Hi David,</p>
    <p>Thanks for review</p>
    <div class="moz-cite-prefix">On 2/19/26 18:38, David Geier wrote:<span
      style="white-space: pre-wrap">
</span></div>
    <blockquote type="cite"
      cite="mid:52596e08-0902-475b-ad0f-265ec6918f19@gmail.com">
      <pre wrap="" class="moz-quote-pre">+1 on the general idea.

</pre>
      <blockquote type="cite">
        <pre wrap="" class="moz-quote-pre">For constant arrays I propose adding a simple pre-check before entering
the per-element loop: detect whether the array contains at least one
NULL element (e.g., via memchr() for the deconstructed array case). If
so, and we are in the ALL / NOT IN case, we can immediately return
selectivity = 0.0 and skip all further computation. This would avoid
extra per-element estimation work while preserving semantics.
</pre>
      </blockquote>
      <pre wrap="" class="moz-quote-pre">
How much overhead does the memchr() call add? It seems like this
approach optimizes the edge case at the expense of the common case,
which doesn't seem like a good trade-off.

How about instead adding a flag to ArrayType which indicates if the
array contains NULL or not. This flag could be set in
construct_md_array() which already iterates over all elements. The flag
would need to be kept up-to-date, e.g. in array_set_element() and
possibly other functions modifying the array.</pre>
    </blockquote>
    <p>It seems we might reinventing the wheel.</p>
    <p>There is already ARR_HASNULL() which allows us to detect the
      presence of NULL in ArrayType.</p>
    <p><span style="white-space: pre-wrap">
</span></p>
    <blockquote type="cite"
      cite="mid:52596e08-0902-475b-ad0f-265ec6918f19@gmail.com">
      <blockquote type="cite">
        <pre wrap="" class="moz-quote-pre">In cases where array elements are not known to be constants in advance,
such a pre-check is less straightforward, because each element must
first be inspected to determine whether it is a Const and whether it is
NULL. That already requires iterating through the list, so introducing a
separate early pass would not actually reduce the amount of work.
Therefore, it like makes sense to keep the current behavior in that
situation.
</pre>
      </blockquote>
      <pre wrap="" class="moz-quote-pre">
Agreed.
</pre>
    </blockquote>
    <p>After thinking about this more, is seems reasonable to
      short-circuit еру loop when we detect a NULL element by checking
      whether the element is a Const and NULL.</p>
    <p><br>
    </p>
    <p>I've attached v2 patch.</p>
    <p>--
      <br>
      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>

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

RnJvbSA3Njc3NTAxMzk0N2Q5MzQ1YjQ3NTRlMzNkOWI4MDc4NDVmODY1NDZmIE1vbiBTZXAg
MTcgMDA6MDA6MDAgMjAwMQpGcm9tOiBJbGlhIEV2ZG9raW1vdiA8aWx5YS5ldmRva2ltb3ZA
dGFudG9ybGFicy5ydT4KRGF0ZTogRnJpLCAyMCBGZWIgMjAyNiAxMjowMzoxMCArMDMwMApT
dWJqZWN0OiBbUEFUQ0ggdjJdIFJlZHVjZSBwbGFubmluZyB0aW1lIGZvciBsYXJnZSBOT1Qg
SU4gbGlzdHMgY29udGFpbmluZwogTlVMTAoKRm9yIHggPD4gQUxMICguLi4pIC8geCBOT1Qg
SU4gKC4uLiksIHRoZSBwcmVzZW5jZSBvZiBhIE5VTEwgZWxlbWVudAptYWtlcyB0aGUgc2Vs
ZWN0aXZpdHkgMC4wLgoKVGhlIHBsYW5uZXIgY3VycmVudGx5IHN0aWxsIGl0ZXJhdGVzIG92
ZXIgYWxsIGVsZW1lbnRzIGFuZCBjb21wdXRlcwpwZXItZWxlbWVudCBzZWxlY3Rpdml0eSwg
ZXZlbiB0aG91Z2ggdGhlIGZpbmFsIHJlc3VsdCBpcyBrbm93bi4KCkFkZCBhbiBlYXJseSBO
VUxMIGNoZWNrIGZvciBjb25zdGFudCBhcnJheXMgYW5kIGltbWVkaWF0ZWx5IHJldHVybgow
LjAgdW5kZXIgQUxMIHNlbWFudGljcy4KClRoaXMgcmVkdWNlcyBwbGFubmluZyB0aW1lIGZv
ciBsYXJnZSBOT1QgSU4gLyA8PiBBTEwgbGlzdHMgd2l0aG91dApjaGFuZ2luZyBzZW1hbnRp
Y3MuCi0tLQogc3JjL2JhY2tlbmQvdXRpbHMvYWR0L3NlbGZ1bmNzLmMgfCA3ICsrKysrKysK
IDEgZmlsZSBjaGFuZ2VkLCA3IGluc2VydGlvbnMoKykKCmRpZmYgLS1naXQgYS9zcmMvYmFj
a2VuZC91dGlscy9hZHQvc2VsZnVuY3MuYyBiL3NyYy9iYWNrZW5kL3V0aWxzL2FkdC9zZWxm
dW5jcy5jCmluZGV4IDI5ZmVjNjU1NTkzLi45NzcwNjU2ZjEyNSAxMDA2NDQKLS0tIGEvc3Jj
L2JhY2tlbmQvdXRpbHMvYWR0L3NlbGZ1bmNzLmMKKysrIGIvc3JjL2JhY2tlbmQvdXRpbHMv
YWR0L3NlbGZ1bmNzLmMKQEAgLTIwMjUsNiArMjAyNSwxMCBAQCBzY2FsYXJhcnJheXNlbChQ
bGFubmVySW5mbyAqcm9vdCwKIAkJCQkJCSAgZWxtbGVuLCBlbG1ieXZhbCwgZWxtYWxpZ24s
CiAJCQkJCQkgICZlbGVtX3ZhbHVlcywgJmVsZW1fbnVsbHMsICZudW1fZWxlbXMpOwogCisJ
CS8qIFNlbGVjdGl2aXR5IG9mICJXSEVSRSB4IE5PVCBJTiAoTlVMTCwgLi4uICkiIGlzIGFs
d2F5cyAwICIqLworCQlpZiAoIXVzZU9yICYmIEFSUl9IQVNOVUxMKGFycmF5dmFsKSkKKwkJ
CXJldHVybiAoU2VsZWN0aXZpdHkpIDAuMDsKKwogCQkvKgogCQkgKiBGb3IgZ2VuZXJpYyBv
cGVyYXRvcnMsIHdlIGFzc3VtZSB0aGUgcHJvYmFiaWxpdHkgb2Ygc3VjY2VzcyBpcwogCQkg
KiBpbmRlcGVuZGVudCBmb3IgZWFjaCBhcnJheSBlbGVtZW50LiAgQnV0IGZvciAiPSBBTlki
IG9yICI8PiBBTEwiLApAQCAtMjExNSw2ICsyMTE5LDkgQEAgc2NhbGFyYXJyYXlzZWwoUGxh
bm5lckluZm8gKnJvb3QsCiAJCQlMaXN0CSAgICphcmdzOwogCQkJU2VsZWN0aXZpdHkgczI7
CiAKKwkJCS8qIFNlbGVjdGl2aXR5IG9mICJXSEVSRSB4IE5PVCBJTiAoTlVMTCwgLi4uICki
IGlzIGFsd2F5cyAwICIqLworCQkJaWYgKCF1c2VPciAmJiBJc0EoZWxlbSwgQ29uc3QpICYm
ICgoQ29uc3QgKikgZWxlbSktPmNvbnN0aXNudWxsKQorCQkJCXJldHVybiAoU2VsZWN0aXZp
dHkpIDAuMDsKIAkJCS8qCiAJCQkgKiBUaGVvcmV0aWNhbGx5LCBpZiBlbGVtIGlzbid0IG9m
IG5vbWluYWxfZWxlbWVudF90eXBlIHdlIHNob3VsZAogCQkJICogaW5zZXJ0IGEgUmVsYWJl
bFR5cGUsIGJ1dCBpdCBzZWVtcyB1bmxpa2VseSB0aGF0IGFueSBvcGVyYXRvcgotLSAKMi4z
NC4xCgo=

--------------5zRGx0TmCB4vzKWybUsQvigs--