Use a hash table to speed up NOT IN(values)
David Rowley <drowley@postgresql.org>
Use a hash table to speed up NOT IN(values) Similar to 50e17ad28, which allowed hash tables to be used for IN clauses with a set of constants, here we add the same feature for NOT IN clauses. NOT IN evaluates the same as: WHERE a <> v1 AND a <> v2 AND a <> v3. Obviously, if we're using a hash table we must be exactly equivalent to that and return the same result taking into account that either side of the condition could contain a NULL. This requires a little bit of special handling to make work with the hash table version. When processing NOT IN, the ScalarArrayOpExpr's operator will be the <> operator. To be able to build and lookup a hash table we must use the <>'s negator operator. The planner checks if that exists and is hashable and sets the relevant fields in ScalarArrayOpExpr to instruct the executor to use hashing. Author: David Rowley, James Coleman Reviewed-by: James Coleman, Zhihong Yu Discussion: https://postgr.es/m/CAApHDvoF1mum_FRk6D621edcB6KSHBi2+GAgWmioj5AhOu2vwQ@mail.gmail.com
Files
| Path | Change | +/− |
|---|---|---|
| src/backend/executor/execExpr.c | modified | +20 −4 |
| src/backend/executor/execExprInterp.c | modified | +15 −2 |
| src/backend/nodes/copyfuncs.c | modified | +1 −0 |
| src/backend/nodes/equalfuncs.c | modified | +6 −0 |
| src/backend/nodes/outfuncs.c | modified | +1 −0 |
| src/backend/nodes/readfuncs.c | modified | +1 −0 |
| src/backend/optimizer/plan/setrefs.c | modified | +3 −0 |
| src/backend/optimizer/prep/prepqual.c | modified | +1 −0 |
| src/backend/optimizer/util/clauses.c | modified | +60 −16 |
| src/backend/parser/parse_oper.c | modified | +1 −0 |
| src/backend/partitioning/partbounds.c | modified | +1 −0 |
| src/include/catalog/catversion.h | modified | +1 −1 |
| src/include/executor/execExpr.h | modified | +1 −0 |
| src/include/nodes/primnodes.h | modified | +14 −4 |
| src/test/regress/expected/expressions.out | modified | +84 −0 |
| src/test/regress/sql/expressions.sql | modified | +30 −0 |
Discussion
- Binary search in ScalarArrayOpExpr for OR'd constant arrays 78 messages · 2020-04-21 → 2021-07-07