Edit: I guess the main difference is that it's just calculating separate sets and then merging them, which isn't really DeMorgan's, but a calculation approach.
Edit: I guess the main difference is that it's just calculating separate sets and then merging them, which isn't really DeMorgan's, but a calculation approach.
There _are_ optimizers that try to represent this kind of AND/OR expression as sets of distinct ranges in order to at least be able to consider whether a thousand different index scans are worth it or not, with rather limited success (it doesn't integrate all that well when you get more than one table, and getting cardinalities for that many index scans can be pretty expensive).
I imagine negative filters to be a bit inefficient as well, though maybe not for a simple count.
And the example shows exactly two sets.
So it's exactly De Morgan's law.
It doesn't have to be, it just "is" in some database engines for various historical reasons.
I.e.: PostgreSQL 18 is the first version to support "B-tree Skip Scan" operators: https://neon.com/postgresql/postgresql-18/skip-scan-btree
Other database engines are capable of this kind of thing to various degrees.
Unrelated or not, skip-scan will be useful in some cases. However, the cases where it adds noticeable benefit are the cases where a separate index should have been used for leading columns anyway (and in memory-constrained/frequently-cold-cache situations, a separate index might even be faster). If you can’t even begin to guess at the order of magnitude of cardinality, or if your leading-column-lacking queries are quite rare and not that perf-sensitive on a big table exerting index cache pressure, then skip scans make sense.
The query planner can include the entire matching range for the 'A' column and check the 'B' column for matches via skip-scan.
This is possible in principle, but I don't believe most (any?) database engines use this specific approach.
It could be optimal if the results are required in A,B sorted order.