38.15. Operator Optimization Information

38.15. Operator Optimization Information
Prev	Up	Chapter 38. Extending SQL	Home	Next

38.15.1. COMMUTATOR
38.15.2. NEGATOR
38.15.3. RESTRICT
38.15.4. JOIN
38.15.5. HASHES
38.15.6. MERGES

+ A PostgreSQL operator definition can include + several optional clauses that tell the system useful things about how + the operator behaves. These clauses should be provided whenever + appropriate, because they can make for considerable speedups in execution + of queries that use the operator. But if you provide them, you must be + sure that they are right! Incorrect use of an optimization clause can + result in slow queries, subtly wrong output, or other Bad Things. + You can always leave out an optimization clause if you are not sure + about it; the only consequence is that queries might run slower than + they need to. +

+ Additional optimization clauses might be added in future versions of + PostgreSQL. The ones described here are all + the ones that release 14.5 understands. +

+ It is also possible to attach a planner support function to the function + that underlies an operator, providing another way of telling the system + about the behavior of the operator. + See Section 38.11 for more information. +

38.15.1. `COMMUTATOR`

+ The COMMUTATOR clause, if provided, names an operator that is the + commutator of the operator being defined. We say that operator A is the + commutator of operator B if (x A y) equals (y B x) for all possible input + values x, y. Notice that B is also the commutator of A. For example, + operators < and > for a particular data type are usually each others' + commutators, and operator + is usually commutative with itself. + But operator - is usually not commutative with anything. +

+ The left operand type of a commutable operator is the same as the + right operand type of its commutator, and vice versa. So the name of + the commutator operator is all that PostgreSQL + needs to be given to look up the commutator, and that's all that needs to + be provided in the COMMUTATOR clause. +

+ It's critical to provide commutator information for operators that + will be used in indexes and join clauses, because this allows the + query optimizer to “flip around” such a clause to the forms + needed for different plan types. For example, consider a query with + a WHERE clause like tab1.x = tab2.y, where tab1.x + and tab2.y are of a user-defined type, and suppose that + tab2.y is indexed. The optimizer cannot generate an + index scan unless it can determine how to flip the clause around to + tab2.y = tab1.x, because the index-scan machinery expects + to see the indexed column on the left of the operator it is given. + PostgreSQL will not simply + assume that this is a valid transformation — the creator of the + = operator must specify that it is valid, by marking the + operator with commutator information. +

+ When you are defining a self-commutative operator, you just do it. + When you are defining a pair of commutative operators, things are + a little trickier: how can the first one to be defined refer to the + other one, which you haven't defined yet? There are two solutions + to this problem: + +

+ One way is to omit the COMMUTATOR clause in the first operator that + you define, and then provide one in the second operator's definition. + Since PostgreSQL knows that commutative + operators come in pairs, when it sees the second definition it will + automatically go back and fill in the missing COMMUTATOR clause in + the first definition. +
+ The other, more straightforward way is just to include COMMUTATOR clauses + in both definitions. When PostgreSQL processes + the first definition and realizes that COMMUTATOR refers to a nonexistent + operator, the system will make a dummy entry for that operator in the + system catalog. This dummy entry will have valid data only + for the operator name, left and right operand types, and result type, + since that's all that PostgreSQL can deduce + at this point. The first operator's catalog entry will link to this + dummy entry. Later, when you define the second operator, the system + updates the dummy entry with the additional information from the second + definition. If you try to use the dummy operator before it's been filled + in, you'll just get an error message. +

38.15.2. `NEGATOR`

+ The NEGATOR clause, if provided, names an operator that is the + negator of the operator being defined. We say that operator A + is the negator of operator B if both return Boolean results and + (x A y) equals NOT (x B y) for all possible inputs x, y. + Notice that B is also the negator of A. + For example, < and >= are a negator pair for most data types. + An operator can never validly be its own negator. +

+ Unlike commutators, a pair of unary operators could validly be marked + as each other's negators; that would mean (A x) equals NOT (B x) + for all x. +

+ An operator's negator must have the same left and/or right operand types + as the operator to be defined, so just as with COMMUTATOR, only the operator + name need be given in the NEGATOR clause. +

+ Providing a negator is very helpful to the query optimizer since + it allows expressions like NOT (x = y) to be simplified into + x <> y. This comes up more often than you might think, because + NOT operations can be inserted as a consequence of other rearrangements. +

+ Pairs of negator operators can be defined using the same methods + explained above for commutator pairs. +

38.15.3. `RESTRICT`

+ The RESTRICT clause, if provided, names a restriction selectivity + estimation function for the operator. (Note that this is a function + name, not an operator name.) RESTRICT clauses only make sense for + binary operators that return boolean. The idea behind a restriction + selectivity estimator is to guess what fraction of the rows in a + table will satisfy a WHERE-clause condition of the form: +

+column OP constant
+

+ for the current operator and a particular constant value. + This assists the optimizer by + giving it some idea of how many rows will be eliminated by WHERE + clauses that have this form. (What happens if the constant is on + the left, you might be wondering? Well, that's one of the things that + COMMUTATOR is for...) +

+ Writing new restriction selectivity estimation functions is far beyond + the scope of this chapter, but fortunately you can usually just use + one of the system's standard estimators for many of your own operators. + These are the standard restriction estimators: +

eqsel for =

neqsel for <>

scalarltsel for <

scalarlesel for <=

scalargtsel for >

scalargesel for >=

+ You can frequently get away with using either eqsel or neqsel for + operators that have very high or very low selectivity, even if they + aren't really equality or inequality. For example, the + approximate-equality geometric operators use eqsel on the assumption that + they'll usually only match a small fraction of the entries in a table. +

+ You can use scalarltsel, scalarlesel, + scalargtsel and scalargesel for comparisons on + data types that have some sensible means of being converted into numeric + scalars for range comparisons. If possible, add the data type to those + understood by the function convert_to_scalar() in + src/backend/utils/adt/selfuncs.c. + (Eventually, this function should be replaced by per-data-type functions + identified through a column of the pg_type system catalog; but that hasn't happened + yet.) If you do not do this, things will still work, but the optimizer's + estimates won't be as good as they could be. +

+ Another useful built-in selectivity estimation function + is matchingsel, which will work for almost any + binary operator, if standard MCV and/or histogram statistics are + collected for the input data type(s). Its default estimate is set to + twice the default estimate used in eqsel, making + it most suitable for comparison operators that are somewhat less + strict than equality. (Or you could call the + underlying generic_restriction_selectivity + function, providing a different default estimate.) +

+ There are additional selectivity estimation functions designed for geometric + operators in src/backend/utils/adt/geo_selfuncs.c: areasel, positionsel, + and contsel. At this writing these are just stubs, but you might want + to use them (or even better, improve them) anyway. +

38.15.4. `JOIN`

+ The JOIN clause, if provided, names a join selectivity + estimation function for the operator. (Note that this is a function + name, not an operator name.) JOIN clauses only make sense for + binary operators that return boolean. The idea behind a join + selectivity estimator is to guess what fraction of the rows in a + pair of tables will satisfy a WHERE-clause condition of the form: +

+table1.column1 OP table2.column2
+

+ for the current operator. As with the RESTRICT clause, this helps + the optimizer very substantially by letting it figure out which + of several possible join sequences is likely to take the least work. +

+ As before, this chapter will make no attempt to explain how to write + a join selectivity estimator function, but will just suggest that + you use one of the standard estimators if one is applicable: +

eqjoinsel for =

neqjoinsel for <>

scalarltjoinsel for <

scalarlejoinsel for <=

scalargtjoinsel for >

scalargejoinsel for >=

matchingjoinsel for generic matching operators

areajoinsel for 2D area-based comparisons

positionjoinsel for 2D position-based comparisons

contjoinsel for 2D containment-based comparisons

38.15.5. `HASHES`

+ The HASHES clause, if present, tells the system that + it is permissible to use the hash join method for a join based on this + operator. HASHES only makes sense for a binary operator that + returns boolean, and in practice the operator must represent + equality for some data type or pair of data types. +

+ The assumption underlying hash join is that the join operator can + only return true for pairs of left and right values that hash to the + same hash code. If two values get put in different hash buckets, the + join will never compare them at all, implicitly assuming that the + result of the join operator must be false. So it never makes sense + to specify HASHES for operators that do not represent + some form of equality. In most cases it is only practical to support + hashing for operators that take the same data type on both sides. + However, sometimes it is possible to design compatible hash functions + for two or more data types; that is, functions that will generate the + same hash codes for “equal” values, even though the values + have different representations. For example, it's fairly simple + to arrange this property when hashing integers of different widths. +

+ To be marked HASHES, the join operator must appear + in a hash index operator family. This is not enforced when you create + the operator, since of course the referencing operator family couldn't + exist yet. But attempts to use the operator in hash joins will fail + at run time if no such operator family exists. The system needs the + operator family to find the data-type-specific hash function(s) for the + operator's input data type(s). Of course, you must also create suitable + hash functions before you can create the operator family. +

+ Care should be exercised when preparing a hash function, because there + are machine-dependent ways in which it might fail to do the right thing. + For example, if your data type is a structure in which there might be + uninteresting pad bits, you cannot simply pass the whole structure to + hash_any. (Unless you write your other operators and + functions to ensure that the unused bits are always zero, which is the + recommended strategy.) + Another example is that on machines that meet the IEEE + floating-point standard, negative zero and positive zero are different + values (different bit patterns) but they are defined to compare equal. + If a float value might contain negative zero then extra steps are needed + to ensure it generates the same hash value as positive zero. +

+ A hash-joinable operator must have a commutator (itself if the two + operand data types are the same, or a related equality operator + if they are different) that appears in the same operator family. + If this is not the case, planner errors might occur when the operator + is used. Also, it is a good idea (but not strictly required) for + a hash operator family that supports multiple data types to provide + equality operators for every combination of the data types; this + allows better optimization. +

Note

+ The function underlying a hash-joinable operator must be marked + immutable or stable. If it is volatile, the system will never + attempt to use the operator for a hash join. +

Note

+ If a hash-joinable operator has an underlying function that is marked + strict, the + function must also be complete: that is, it should return true or + false, never null, for any two nonnull inputs. If this rule is + not followed, hash-optimization of IN operations might + generate wrong results. (Specifically, IN might return + false where the correct answer according to the standard would be null; + or it might yield an error complaining that it wasn't prepared for a + null result.) +

38.15.6. `MERGES`

+ The MERGES clause, if present, tells the system that + it is permissible to use the merge-join method for a join based on this + operator. MERGES only makes sense for a binary operator that + returns boolean, and in practice the operator must represent + equality for some data type or pair of data types. +

+ Merge join is based on the idea of sorting the left- and right-hand tables + into order and then scanning them in parallel. So, both data types must + be capable of being fully ordered, and the join operator must be one + that can only succeed for pairs of values that fall at the + “same place” + in the sort order. In practice this means that the join operator must + behave like equality. But it is possible to merge-join two + distinct data types so long as they are logically compatible. For + example, the smallint-versus-integer + equality operator is merge-joinable. + We only need sorting operators that will bring both data types into a + logically compatible sequence. +

+ To be marked MERGES, the join operator must appear + as an equality member of a btree index operator family. + This is not enforced when you create + the operator, since of course the referencing operator family couldn't + exist yet. But the operator will not actually be used for merge joins + unless a matching operator family can be found. The + MERGES flag thus acts as a hint to the planner that + it's worth looking for a matching operator family. +

+ A merge-joinable operator must have a commutator (itself if the two + operand data types are the same, or a related equality operator + if they are different) that appears in the same operator family. + If this is not the case, planner errors might occur when the operator + is used. Also, it is a good idea (but not strictly required) for + a btree operator family that supports multiple data types to provide + equality operators for every combination of the data types; this + allows better optimization. +

Note

+ The function underlying a merge-joinable operator must be marked + immutable or stable. If it is volatile, the system will never + attempt to use the operator for a merge join. +

Prev	Up	Next
38.14. User-Defined Operators	Home	38.16. Interfacing Extensions to Indexes