Content-Type: multipart/mixed; boundary="------------ZOD4mPzUBE9egabd8NrhumG7"
Message-ID: <eaa2598c-5356-4e1e-9ec3-5fd6eb1cd704@tantorlabs.com>
Date: Wed, 18 Feb 2026 17:11:56 +0300
MIME-Version: 1.0
User-Agent: Mozilla Thunderbird
Content-Language: en-US
To: PostgreSQL Developers <pgsql-hackers@lists.postgresql.org>
From: Ilia Evdokimov <ilya.evdokimov@tantorlabs.com>
Subject: Reduce planning time for large NOT IN lists containing NULL
Archived-At: <https://www.postgresql.org/message-id/eaa2598c-5356-4e1e-9ec3-5fd6eb1cd704%40tantorlabs.com>
Precedence: bulk

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

Hi hackers,

In this thread [0] an interesting idea came up about avoiding 
unnecessary work during selectivity estimation for x <> ALL (NULL, ...) 
or x NOT IN (NULL, ...)

Semantically, if the array contains at least one NULL, the selectivity 
of x NOT IN (...) is always 0.0, regardless of the other elements in the 
list.

Currently, the planner still iterates over all array elements and 
invokes the operator's selectivity estimator for each of them. For large 
IN / ALL lists, this increases planning time.

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.

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.

Thoughts?

[0]: 
https://www.postgresql.org/message-id/CAHza6qdAH99C0xa27YDTixiNVFa99j90QYquUPAxL0JwahmggA%40mail.gmail.com

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

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

RnJvbSA4NjkxNGY0NGEzN2IzYzlhZmJkMThiMzMzZWI1YzQ1MWY0MWNlNjViIE1vbiBTZXAg
MTcgMDA6MDA6MDAgMjAwMQpGcm9tOiBJbGlhIEV2ZG9raW1vdiA8aWx5YS5ldmRva2ltb3ZA
dGFudG9ybGFicy5ydT4KRGF0ZTogV2VkLCAxOCBGZWIgMjAyNiAxNzowNjozNSArMDMwMApT
dWJqZWN0OiBbUEFUQ0ggdjFdIFJlZHVjZSBwbGFubmluZyB0aW1lIGZvciBsYXJnZSBOT1Qg
SU4gbGlzdHMgY29udGFpbmluZwogTlVMTAoKRm9yIHggPD4gQUxMICguLi4pIC8geCBOT1Qg
SU4gKC4uLiksIHRoZSBwcmVzZW5jZSBvZiBhIE5VTEwgZWxlbWVudAptYWtlcyB0aGUgc2Vs
ZWN0aXZpdHkgMC4wLgoKVGhlIHBsYW5uZXIgY3VycmVudGx5IHN0aWxsIGl0ZXJhdGVzIG92
ZXIgYWxsIGVsZW1lbnRzIGFuZCBjb21wdXRlcwpwZXItZWxlbWVudCBzZWxlY3Rpdml0eSwg
ZXZlbiB0aG91Z2ggdGhlIGZpbmFsIHJlc3VsdCBpcyBrbm93bi4KCkFkZCBhbiBlYXJseSBO
VUxMIGNoZWNrIGZvciBjb25zdGFudCBhcnJheXMgYW5kIGltbWVkaWF0ZWx5IHJldHVybgow
LjAgdW5kZXIgQUxMIHNlbWFudGljcy4KClRoaXMgcmVkdWNlcyBwbGFubmluZyB0aW1lIGZv
ciBsYXJnZSBOT1QgSU4gLyA8PiBBTEwgbGlzdHMgd2l0aG91dApjaGFuZ2luZyBzZW1hbnRp
Y3MuCi0tLQogc3JjL2JhY2tlbmQvdXRpbHMvYWR0L3NlbGZ1bmNzLmMgfCAzICsrKwogMSBm
aWxlIGNoYW5nZWQsIDMgaW5zZXJ0aW9ucygrKQoKZGlmZiAtLWdpdCBhL3NyYy9iYWNrZW5k
L3V0aWxzL2FkdC9zZWxmdW5jcy5jIGIvc3JjL2JhY2tlbmQvdXRpbHMvYWR0L3NlbGZ1bmNz
LmMKaW5kZXggMjlmZWM2NTU1OTMuLmEwYjU3YmQ1N2FhIDEwMDY0NAotLS0gYS9zcmMvYmFj
a2VuZC91dGlscy9hZHQvc2VsZnVuY3MuYworKysgYi9zcmMvYmFja2VuZC91dGlscy9hZHQv
c2VsZnVuY3MuYwpAQCAtMjAyNSw2ICsyMDI1LDkgQEAgc2NhbGFyYXJyYXlzZWwoUGxhbm5l
ckluZm8gKnJvb3QsCiAJCQkJCQkgIGVsbWxlbiwgZWxtYnl2YWwsIGVsbWFsaWduLAogCQkJ
CQkJICAmZWxlbV92YWx1ZXMsICZlbGVtX251bGxzLCAmbnVtX2VsZW1zKTsKIAorCQlpZiAo
IXVzZU9yICYmIG1lbWNocihlbGVtX251bGxzLCB0cnVlLCBudW1fZWxlbXMpICE9IE5VTEwp
CisJCQlyZXR1cm4gKFNlbGVjdGl2aXR5KSAwLjA7CisKIAkJLyoKIAkJICogRm9yIGdlbmVy
aWMgb3BlcmF0b3JzLCB3ZSBhc3N1bWUgdGhlIHByb2JhYmlsaXR5IG9mIHN1Y2Nlc3MgaXMK
IAkJICogaW5kZXBlbmRlbnQgZm9yIGVhY2ggYXJyYXkgZWxlbWVudC4gIEJ1dCBmb3IgIj0g
QU5ZIiBvciAiPD4gQUxMIiwKLS0gCjIuMzQuMQoK

--------------ZOD4mPzUBE9egabd8NrhumG7--