Distinguish selectivity of < from <= and > from >=.

Historically, the selectivity functions have simply not distinguished
< from <=, or > from >=, arguing that the fraction of the population that
satisfies the "=" aspect can be considered to be vanishingly small, if the
comparison value isn't any of the most-common-values for the variable.
(If it is, the code path that executes the operator against each MCV will
take care of things properly.)  But that isn't really true unless we're
dealing with a continuum of variable values, and in practice we seldom are.
If "x = const" would estimate a nonzero number of rows for a given const
value, then it follows that we ought to estimate different numbers of rows
for "x < const" and "x <= const", even if the const is not one of the MCVs.
Handling this more honestly makes a significant difference in edge cases,
such as the estimate for a tight range (x BETWEEN y AND z where y and z
are close together).

Hence, split scalarltsel into scalarltsel/scalarlesel, and similarly
split scalargtsel into scalargtsel/scalargesel.  Adjust <= and >=
operator definitions to reference the new selectivity functions.
Improve the core ineq_histogram_selectivity() function to make a
correction for equality.  (Along the way, I learned quite a bit about
exactly why that function gives good answers, which I tried to memorialize
in improved comments.)

The corresponding join selectivity functions were, and remain, just stubs.
But I chose to split them similarly, to avoid confusion and to prevent the
need for doing this exercise again if someone ever makes them less stubby.

In passing, change ineq_histogram_selectivity's clamp for extreme
probability estimates so that it varies depending on the histogram
size, instead of being hardwired at 0.0001.  With the default histogram
size of 100 entries, you still get the old clamp value, but bigger
histograms should allow us to put more faith in edge values.

Tom Lane, reviewed by Aleksander Alekseev and Kuntal Ghosh

Discussion: https://postgr.es/m/12232.1499140410@sss.pgh.pa.us

12 files changed, 280 insertions, 8 deletions

diff --git a/contrib/citext/Makefile b/contrib/citext/Makefile
index 563cd22dcc..e32a7de946 100644
--- a/contrib/citext/Makefile
+++ b/contrib/citext/Makefile
@@ -3,7 +3,8 @@
 MODULES = citext
 
 EXTENSION = citext
-DATA = citext--1.4.sql citext--1.3--1.4.sql \
+DATA = citext--1.4.sql citext--1.4--1.5.sql \
+	citext--1.3--1.4.sql \
 	citext--1.2--1.3.sql citext--1.1--1.2.sql \
 	citext--1.0--1.1.sql citext--unpackaged--1.0.sql
 PGFILEDESC = "citext - case-insensitive character string data type"
diff --git a/contrib/citext/citext--1.4--1.5.sql b/contrib/citext/citext--1.4--1.5.sql
new file mode 100644
index 0000000000..97942cb7bf
--- /dev/null
+++ b/contrib/citext/citext--1.4--1.5.sql
@@ -0,0 +1,14 @@
+/* contrib/citext/citext--1.4--1.5.sql */
+
+-- complain if script is sourced in psql, rather than via ALTER EXTENSION
+\echo Use "ALTER EXTENSION citext UPDATE TO '1.5'" to load this file. \quit
+
+ALTER OPERATOR <= (citext, citext) SET (
+    RESTRICT   = scalarlesel,
+    JOIN       = scalarlejoinsel
+);
+
+ALTER OPERATOR >= (citext, citext) SET (
+    RESTRICT   = scalargesel,
+    JOIN       = scalargejoinsel
+);
diff --git a/contrib/citext/citext.control b/contrib/citext/citext.control
index 17fce4e887..4cd6e09331 100644
--- a/contrib/citext/citext.control
+++ b/contrib/citext/citext.control
@@ -1,5 +1,5 @@
 # citext extension
 comment = 'data type for case-insensitive character strings'
-default_version = '1.4'
+default_version = '1.5'
 module_pathname = '$libdir/citext'
 relocatable = true
diff --git a/contrib/cube/Makefile b/contrib/cube/Makefile
index be7a1bc1a0..244c1d9bbf 100644
--- a/contrib/cube/Makefile
+++ b/contrib/cube/Makefile
@@ -4,7 +4,8 @@ MODULE_big = cube
 OBJS= cube.o cubeparse.o $(WIN32RES)
 
 EXTENSION = cube
-DATA = cube--1.2.sql cube--1.1--1.2.sql cube--1.0--1.1.sql \
+DATA = cube--1.2.sql cube--1.2--1.3.sql \
+	cube--1.1--1.2.sql cube--1.0--1.1.sql \
 	cube--unpackaged--1.0.sql
 PGFILEDESC = "cube - multidimensional cube data type"
 
diff --git a/contrib/cube/cube--1.2--1.3.sql b/contrib/cube/cube--1.2--1.3.sql
new file mode 100644
index 0000000000..a688f19f02
--- /dev/null
+++ b/contrib/cube/cube--1.2--1.3.sql
@@ -0,0 +1,12 @@
+/* contrib/cube/cube--1.2--1.3.sql */
+
+-- complain if script is sourced in psql, rather than via ALTER EXTENSION
+\echo Use "ALTER EXTENSION cube UPDATE TO '1.3'" to load this file. \quit
+
+ALTER OPERATOR <= (cube, cube) SET (
+	RESTRICT = scalarlesel, JOIN = scalarlejoinsel
+);
+
+ALTER OPERATOR >= (cube, cube) SET (
+	RESTRICT = scalargesel, JOIN = scalargejoinsel
+);
diff --git a/contrib/cube/cube.control b/contrib/cube/cube.control
index b03cfa0a58..af062d4843 100644
--- a/contrib/cube/cube.control
+++ b/contrib/cube/cube.control
@@ -1,5 +1,5 @@
 # cube extension
 comment = 'data type for multidimensional cubes'
-default_version = '1.2'
+default_version = '1.3'
 module_pathname = '$libdir/cube'
 relocatable = true
diff --git a/contrib/hstore/Makefile b/contrib/hstore/Makefile
index 311cc099e5..ab7fef3979 100644
--- a/contrib/hstore/Makefile
+++ b/contrib/hstore/Makefile
@@ -5,7 +5,8 @@ OBJS = hstore_io.o hstore_op.o hstore_gist.o hstore_gin.o hstore_compat.o \
 	$(WIN32RES)
 
 EXTENSION = hstore
-DATA = hstore--1.4.sql hstore--1.3--1.4.sql hstore--1.2--1.3.sql \
+DATA = hstore--1.4.sql hstore--1.4--1.5.sql \
+	hstore--1.3--1.4.sql hstore--1.2--1.3.sql \
 	hstore--1.1--1.2.sql hstore--1.0--1.1.sql \
 	hstore--unpackaged--1.0.sql
 PGFILEDESC = "hstore - key/value pair data type"
diff --git a/contrib/hstore/hstore--1.4--1.5.sql b/contrib/hstore/hstore--1.4--1.5.sql
new file mode 100644
index 0000000000..92c1832dce
--- /dev/null
+++ b/contrib/hstore/hstore--1.4--1.5.sql
@@ -0,0 +1,14 @@
+/* contrib/hstore/hstore--1.4--1.5.sql */
+
+-- complain if script is sourced in psql, rather than via ALTER EXTENSION
+\echo Use "ALTER EXTENSION hstore UPDATE TO '1.5'" to load this file. \quit
+
+ALTER OPERATOR #<=# (hstore, hstore) SET (
+       RESTRICT = scalarlesel,
+       JOIN = scalarlejoinsel
+);
+
+ALTER OPERATOR #>=# (hstore, hstore) SET (
+       RESTRICT = scalargesel,
+       JOIN = scalargejoinsel
+);
diff --git a/contrib/hstore/hstore.control b/contrib/hstore/hstore.control
index f99a937acc..8a719475b8 100644
--- a/contrib/hstore/hstore.control
+++ b/contrib/hstore/hstore.control
@@ -1,5 +1,5 @@
 # hstore extension
 comment = 'data type for storing sets of (key, value) pairs'
-default_version = '1.4'
+default_version = '1.5'
 module_pathname = '$libdir/hstore'
 relocatable = true
diff --git a/contrib/isn/Makefile b/contrib/isn/Makefile
index 9543a4b1cf..ab6b175f9a 100644
--- a/contrib/isn/Makefile
+++ b/contrib/isn/Makefile
@@ -3,7 +3,8 @@
 MODULES = isn
 
 EXTENSION = isn
-DATA = isn--1.1.sql isn--1.0--1.1.sql isn--unpackaged--1.0.sql
+DATA = isn--1.1.sql isn--1.1--1.2.sql \
+	isn--1.0--1.1.sql isn--unpackaged--1.0.sql
 PGFILEDESC = "isn - data types for international product numbering standards"
 
 REGRESS = isn
diff --git a/contrib/isn/isn--1.1--1.2.sql b/contrib/isn/isn--1.1--1.2.sql
new file mode 100644
index 0000000000..d626a5f44d
--- /dev/null
+++ b/contrib/isn/isn--1.1--1.2.sql
@@ -0,0 +1,228 @@
+/* contrib/isn/isn--1.1--1.2.sql */
+
+-- complain if script is sourced in psql, rather than via ALTER EXTENSION
+\echo Use "ALTER EXTENSION isn UPDATE TO '1.2'" to load this file. \quit
+
+ALTER OPERATOR <= (ean13, ean13) SET (
+	RESTRICT = scalarlesel,
+	JOIN = scalarlejoinsel);
+
+ALTER OPERATOR >= (ean13, ean13) SET (
+	RESTRICT = scalargesel,
+	JOIN = scalargejoinsel);
+
+ALTER OPERATOR <= (ean13, isbn13) SET (
+	RESTRICT = scalarlesel,
+	JOIN = scalarlejoinsel);
+
+ALTER OPERATOR >= (ean13, isbn13) SET (
+	RESTRICT = scalargesel,
+	JOIN = scalargejoinsel);
+
+ALTER OPERATOR <= (isbn13, ean13) SET (
+	RESTRICT = scalarlesel,
+	JOIN = scalarlejoinsel);
+
+ALTER OPERATOR >= (isbn13, ean13) SET (
+	RESTRICT = scalargesel,
+	JOIN = scalargejoinsel);
+
+ALTER OPERATOR <= (ean13, ismn13) SET (
+	RESTRICT = scalarlesel,
+	JOIN = scalarlejoinsel);
+
+ALTER OPERATOR >= (ean13, ismn13) SET (
+	RESTRICT = scalargesel,
+	JOIN = scalargejoinsel);
+
+ALTER OPERATOR <= (ismn13, ean13) SET (
+	RESTRICT = scalarlesel,
+	JOIN = scalarlejoinsel);
+
+ALTER OPERATOR >= (ismn13, ean13) SET (
+	RESTRICT = scalargesel,
+	JOIN = scalargejoinsel);
+
+ALTER OPERATOR <= (ean13, issn13) SET (
+	RESTRICT = scalarlesel,
+	JOIN = scalarlejoinsel);
+
+ALTER OPERATOR >= (ean13, issn13) SET (
+	RESTRICT = scalargesel,
+	JOIN = scalargejoinsel);
+
+ALTER OPERATOR <= (ean13, isbn) SET (
+	RESTRICT = scalarlesel,
+	JOIN = scalarlejoinsel);
+
+ALTER OPERATOR >= (ean13, isbn) SET (
+	RESTRICT = scalargesel,
+	JOIN = scalargejoinsel);
+
+ALTER OPERATOR <= (ean13, ismn) SET (
+	RESTRICT = scalarlesel,
+	JOIN = scalarlejoinsel);
+
+ALTER OPERATOR >= (ean13, ismn) SET (
+	RESTRICT = scalargesel,
+	JOIN = scalargejoinsel);
+
+ALTER OPERATOR <= (ean13, issn) SET (
+	RESTRICT = scalarlesel,
+	JOIN = scalarlejoinsel);
+
+ALTER OPERATOR >= (ean13, issn) SET (
+	RESTRICT = scalargesel,
+	JOIN = scalargejoinsel);
+
+ALTER OPERATOR <= (ean13, upc) SET (
+	RESTRICT = scalarlesel,
+	JOIN = scalarlejoinsel);
+
+ALTER OPERATOR >= (ean13, upc) SET (
+	RESTRICT = scalargesel,
+	JOIN = scalargejoinsel);
+
+ALTER OPERATOR <= (isbn13, isbn13) SET (
+	RESTRICT = scalarlesel,
+	JOIN = scalarlejoinsel);
+
+ALTER OPERATOR >= (isbn13, isbn13) SET (
+	RESTRICT = scalargesel,
+	JOIN = scalargejoinsel);
+
+ALTER OPERATOR <= (isbn13, isbn) SET (
+	RESTRICT = scalarlesel,
+	JOIN = scalarlejoinsel);
+
+ALTER OPERATOR >= (isbn13, isbn) SET (
+	RESTRICT = scalargesel,
+	JOIN = scalargejoinsel);
+
+ALTER OPERATOR <= (isbn, isbn) SET (
+	RESTRICT = scalarlesel,
+	JOIN = scalarlejoinsel);
+
+ALTER OPERATOR >= (isbn, isbn) SET (
+	RESTRICT = scalargesel,
+	JOIN = scalargejoinsel);
+
+ALTER OPERATOR <= (isbn, isbn13) SET (
+	RESTRICT = scalarlesel,
+	JOIN = scalarlejoinsel);
+
+ALTER OPERATOR >= (isbn, isbn13) SET (
+	RESTRICT = scalargesel,
+	JOIN = scalargejoinsel);
+
+ALTER OPERATOR <= (isbn, ean13) SET (
+	RESTRICT = scalarlesel,
+	JOIN = scalarlejoinsel);
+
+ALTER OPERATOR >= (isbn, ean13) SET (
+	RESTRICT = scalargesel,
+	JOIN = scalargejoinsel);
+
+ALTER OPERATOR <= (ismn13, ismn13) SET (
+	RESTRICT = scalarlesel,
+	JOIN = scalarlejoinsel);
+
+ALTER OPERATOR >= (ismn13, ismn13) SET (
+	RESTRICT = scalargesel,
+	JOIN = scalargejoinsel);
+
+ALTER OPERATOR <= (ismn13, ismn) SET (
+	RESTRICT = scalarlesel,
+	JOIN = scalarlejoinsel);
+
+ALTER OPERATOR >= (ismn13, ismn) SET (
+	RESTRICT = scalargesel,
+	JOIN = scalargejoinsel);
+
+ALTER OPERATOR <= (ismn, ismn) SET (
+	RESTRICT = scalarlesel,
+	JOIN = scalarlejoinsel);
+
+ALTER OPERATOR >= (ismn, ismn) SET (
+	RESTRICT = scalargesel,
+	JOIN = scalargejoinsel);
+
+ALTER OPERATOR <= (ismn, ismn13) SET (
+	RESTRICT = scalarlesel,
+	JOIN = scalarlejoinsel);
+
+ALTER OPERATOR >= (ismn, ismn13) SET (
+	RESTRICT = scalargesel,
+	JOIN = scalargejoinsel);
+
+ALTER OPERATOR <= (ismn, ean13) SET (
+	RESTRICT = scalarlesel,
+	JOIN = scalarlejoinsel);
+
+ALTER OPERATOR >= (ismn, ean13) SET (
+	RESTRICT = scalargesel,
+	JOIN = scalargejoinsel);
+
+ALTER OPERATOR <= (issn13, issn13) SET (
+	RESTRICT = scalarlesel,
+	JOIN = scalarlejoinsel);
+
+ALTER OPERATOR >= (issn13, issn13) SET (
+	RESTRICT = scalargesel,
+	JOIN = scalargejoinsel);
+
+ALTER OPERATOR <= (issn13, issn) SET (
+	RESTRICT = scalarlesel,
+	JOIN = scalarlejoinsel);
+
+ALTER OPERATOR >= (issn13, issn) SET (
+	RESTRICT = scalargesel,
+	JOIN = scalargejoinsel);
+
+ALTER OPERATOR <= (issn13, ean13) SET (
+	RESTRICT = scalarlesel,
+	JOIN = scalarlejoinsel);
+
+ALTER OPERATOR >= (issn13, ean13) SET (
+	RESTRICT = scalargesel,
+	JOIN = scalargejoinsel);
+
+ALTER OPERATOR <= (issn, issn) SET (
+	RESTRICT = scalarlesel,
+	JOIN = scalarlejoinsel);
+
+ALTER OPERATOR >= (issn, issn) SET (
+	RESTRICT = scalargesel,
+	JOIN = scalargejoinsel);
+
+ALTER OPERATOR <= (issn, issn13) SET (
+	RESTRICT = scalarlesel,
+	JOIN = scalarlejoinsel);
+
+ALTER OPERATOR >= (issn, issn13) SET (
+	RESTRICT = scalargesel,
+	JOIN = scalargejoinsel);
+
+ALTER OPERATOR <= (issn, ean13) SET (
+	RESTRICT = scalarlesel,
+	JOIN = scalarlejoinsel);
+
+ALTER OPERATOR >= (issn, ean13) SET (
+	RESTRICT = scalargesel,
+	JOIN = scalargejoinsel);
+
+ALTER OPERATOR <= (upc, upc) SET (
+	RESTRICT = scalarlesel,
+	JOIN = scalarlejoinsel);
+
+ALTER OPERATOR >= (upc, upc) SET (
+	RESTRICT = scalargesel,
+	JOIN = scalargejoinsel);
+
+ALTER OPERATOR <= (upc, ean13) SET (
+	RESTRICT = scalarlesel,
+	JOIN = scalarlejoinsel);
+
+ALTER OPERATOR >= (upc, ean13) SET (
+	RESTRICT = scalargesel,
+	JOIN = scalargejoinsel);
diff --git a/contrib/isn/isn.control b/contrib/isn/isn.control
index 544bd8d0bf..765dce0e0a 100644
--- a/contrib/isn/isn.control
+++ b/contrib/isn/isn.control
@@ -1,5 +1,5 @@
 # isn extension
 comment = 'data types for international product numbering standards'
-default_version = '1.1'
+default_version = '1.2'
 module_pathname = '$libdir/isn'
 relocatable = true