POC: rational number type (fractions)

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
12 messages Options
Reply | Threaded
Open this post in threaded view
|

POC: rational number type (fractions)

Joe Nelson
Hi hackers, attached is a proof of concept patch adding a new base type
called "rational" to represent fractions. It includes arithmetic,
simplification, conversion to/from float, finding intermediates with a
stern-brocot tree, custom aggregates, and btree/hash indices.

The primary motivation was as a column type to support user-defined
ordering of rows (with the ability to dynamically rearrange rows). The
postgres wiki has a page [0] about this using pairs of integers to
represent fractions, but it's not particularly elegant.

I wrote about options for implementing user-defined order in an article
[1] and ended up creating a postgres extension, pg_rational [2], to
provide the new type. People have been using the extension, but told me
they wished they could use it on hosted platforms like Amazon RDS which
have a limited set of whitelisted extensions. Thus I'm submitting this
patch to discuss getting the feature in core postgres.

For usage, see the included regression test. To see how it works for the
user-defined order use case see my article. I haven't included docs in
the patch since the interface may change with community feedback.

0: https://wiki.postgresql.org/wiki/User-specified_ordering_with_fractions
1: https://begriffs.com/posts/2018-03-20-user-defined-order.html
2: https://github.com/begriffs/pg_rational

--
Joe Nelson      https://begriffs.com

diff --git a/src/backend/utils/adt/Makefile b/src/backend/utils/adt/Makefile
index 13efa9338c..10bdcff5dc 100644
--- a/src/backend/utils/adt/Makefile
+++ b/src/backend/utils/adt/Makefile
@@ -80,6 +80,7 @@ OBJS = \
  rangetypes_selfuncs.o \
  rangetypes_spgist.o \
  rangetypes_typanalyze.o \
+ rational.o \
  regexp.o \
  regproc.o \
  ri_triggers.o \
diff --git a/src/backend/utils/adt/rational.c b/src/backend/utils/adt/rational.c
new file mode 100644
index 0000000000..ab91198da3
--- /dev/null
+++ b/src/backend/utils/adt/rational.c
@@ -0,0 +1,637 @@
+/*-------------------------------------------------------------------------
+ *
+ * rational.c
+ *  Rational number data type for the Postgres database system
+ *
+ * Copyright (c) 1998-2020, PostgreSQL Global Development Group
+ *
+ * IDENTIFICATION
+ *  src/backend/utils/adt/rational.c
+ *
+ *-------------------------------------------------------------------------
+ */
+
+#include "postgres.h"
+#include "fmgr.h"
+#include "access/hash.h"
+#include "common/int.h" /* portable overflow detection */
+#include "libpq/pqformat.h" /* send/recv functions */
+#include <limits.h>
+#include <math.h>
+
+PG_MODULE_MAGIC;
+
+typedef struct
+{
+ int32 numer;
+ int32 denom;
+} Rational;
+
+static int32 gcd(int32, int32);
+static bool simplify(Rational *);
+static int32 cmp(Rational *, Rational *);
+static void neg(Rational *);
+static Rational * create(long long, long long);
+static Rational * add(Rational *, Rational *);
+static Rational * mul(Rational *, Rational *);
+static void mediant(Rational *, Rational *, Rational *);
+
+/*
+ ***************** IO ******************
+ */
+
+PG_FUNCTION_INFO_V1(rational_in);
+PG_FUNCTION_INFO_V1(rational_in_float);
+PG_FUNCTION_INFO_V1(rational_out);
+PG_FUNCTION_INFO_V1(rational_out_float);
+PG_FUNCTION_INFO_V1(rational_recv);
+PG_FUNCTION_INFO_V1(rational_create);
+PG_FUNCTION_INFO_V1(rational_in_integer);
+PG_FUNCTION_INFO_V1(rational_send);
+
+Datum
+rational_in(PG_FUNCTION_ARGS)
+{
+ char   *s = PG_GETARG_CSTRING(0),
+   *after;
+ long long n,
+ d;
+
+ if (!isdigit(*s) && *s != '-')
+ ereport(ERROR,
+ (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION),
+ errmsg("Missing or invalid numerator")));
+
+ n = strtoll(s, &after, 10);
+
+ if (*after == '\0')
+ {
+ /* if just a number and no slash, interpret as an int */
+ d = 1;
+ }
+ else
+ {
+ /* otherwise look for denominator */
+ if (*after != '/')
+ ereport(ERROR,
+ (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION),
+ errmsg("Expecting '/' after number but found '%c'", *after)));
+ if (*(++after) == '\0')
+ ereport(ERROR,
+ (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION),
+ errmsg("Expecting value after '/' but got '\\0'")));
+
+ d = strtoll(after, &after, 10);
+ if (*after != '\0')
+ ereport(ERROR,
+ (errcode(ERRCODE_INVALID_TEXT_REPRESENTATION),
+ errmsg("Expecting '\\0' but found '%c'", *after)));
+ }
+ PG_RETURN_POINTER(create(n, d));
+}
+
+/*
+  This function taken from John Kennedy's paper, "Algorithm To Convert a
+  Decimal to a Fraction." Translated from Pascal.
+*/
+Datum
+rational_in_float(PG_FUNCTION_ARGS)
+{
+ float8 target = PG_GETARG_FLOAT8(0),
+ z,
+ fnumer,
+ fdenom,
+ error;
+ int32 prev_denom,
+ sign;
+ Rational   *result = palloc(sizeof(Rational));
+
+ if (target == (int32) target)
+ {
+ result->numer = (int32) target;
+ result->denom = 1;
+ PG_RETURN_POINTER(result);
+ }
+
+ sign = target < 0.0 ? -1 : 1;
+ target = fabs(target);
+
+ if (!(target <= INT32_MAX))
+ { /* also excludes NaN's */
+ ereport(ERROR,
+ (errcode(ERRCODE_NUMERIC_VALUE_OUT_OF_RANGE),
+ errmsg("value too large for rational")));
+ }
+ z = target;
+ prev_denom = 0;
+ result->numer = (int32) round(target);
+ result->denom = 1;
+ do
+ {
+ z = 1.0 / (z - floor(z));
+ fdenom = result->denom * floor(z) + prev_denom;
+ fnumer = round(target * fdenom);
+ if (fnumer > INT32_MAX || fdenom > INT32_MAX)
+ break;
+ prev_denom = result->denom;
+ result->numer = (int32) fnumer;
+ result->denom = (int32) fdenom;
+
+ error = fabs(target - ((float8) result->numer / (float8) result->denom));
+ } while (z != floor(z) && error >= 1e-12);
+
+ result->numer *= sign;
+ PG_RETURN_POINTER(result);
+}
+
+Datum
+rational_out(PG_FUNCTION_ARGS)
+{
+ Rational   *r = (Rational *) PG_GETARG_POINTER(0);
+
+ PG_RETURN_CSTRING(psprintf("%d/%d", r->numer, r->denom));
+}
+
+Datum
+rational_out_float(PG_FUNCTION_ARGS)
+{
+ Rational   *r = (Rational *) PG_GETARG_POINTER(0);
+
+ PG_RETURN_FLOAT8((float8) r->numer / (float8) r->denom);
+}
+
+Datum
+rational_recv(PG_FUNCTION_ARGS)
+{
+ StringInfo buf = (StringInfo) PG_GETARG_POINTER(0);
+
+ PG_RETURN_POINTER(create(pq_getmsgint(buf, sizeof(int32)),
+ pq_getmsgint(buf, sizeof(int32))));
+}
+
+Datum
+rational_create(PG_FUNCTION_ARGS)
+{
+ PG_RETURN_POINTER(create(PG_GETARG_INT32(0), PG_GETARG_INT32(1)));
+}
+
+Datum
+rational_in_integer(PG_FUNCTION_ARGS)
+{
+ int32 n = PG_GETARG_INT32(0);
+ Rational   *result = palloc(sizeof(Rational));
+
+ result->numer = n;
+ result->denom = 1;
+
+ PG_RETURN_POINTER(result);
+}
+
+Datum
+rational_send(PG_FUNCTION_ARGS)
+{
+ Rational   *r = (Rational *) PG_GETARG_POINTER(0);
+ StringInfoData buf;
+
+ pq_begintypsend(&buf);
+ pq_sendint(&buf, r->numer, sizeof(int32));
+ pq_sendint(&buf, r->denom, sizeof(int32));
+
+ PG_RETURN_BYTEA_P(pq_endtypsend(&buf));
+}
+
+/*
+ ************* ARITHMETIC **************
+ */
+
+PG_FUNCTION_INFO_V1(rational_simplify);
+PG_FUNCTION_INFO_V1(rational_add);
+PG_FUNCTION_INFO_V1(rational_sub);
+PG_FUNCTION_INFO_V1(rational_mul);
+PG_FUNCTION_INFO_V1(rational_div);
+PG_FUNCTION_INFO_V1(rational_neg);
+
+Datum
+rational_simplify(PG_FUNCTION_ARGS)
+{
+ Rational   *in = (Rational *) PG_GETARG_POINTER(0);
+ Rational   *out = palloc(sizeof(Rational));
+
+ memcpy(out, in, sizeof(Rational));
+ simplify(out);
+
+ PG_RETURN_POINTER(out);
+}
+
+Datum
+rational_add(PG_FUNCTION_ARGS)
+{
+ Rational x,
+ y;
+
+ memcpy(&x, PG_GETARG_POINTER(0), sizeof(Rational));
+ memcpy(&y, PG_GETARG_POINTER(1), sizeof(Rational));
+
+ PG_RETURN_POINTER(add(&x, &y));
+}
+
+Datum
+rational_sub(PG_FUNCTION_ARGS)
+{
+ Rational x,
+ y;
+
+ memcpy(&x, PG_GETARG_POINTER(0), sizeof(Rational));
+ memcpy(&y, PG_GETARG_POINTER(1), sizeof(Rational));
+
+ neg(&y);
+ PG_RETURN_POINTER(add(&x, &y));
+}
+
+Datum
+rational_mul(PG_FUNCTION_ARGS)
+{
+ Rational x,
+ y;
+
+ memcpy(&x, PG_GETARG_POINTER(0), sizeof(Rational));
+ memcpy(&y, PG_GETARG_POINTER(1), sizeof(Rational));
+
+ PG_RETURN_POINTER(mul(&x, &y));
+}
+
+Datum
+rational_div(PG_FUNCTION_ARGS)
+{
+ Rational x,
+ y;
+ int32 tmp;
+
+ memcpy(&x, PG_GETARG_POINTER(0), sizeof(Rational));
+ memcpy(&y, PG_GETARG_POINTER(1), sizeof(Rational));
+ tmp = y.numer;
+ y.numer = y.denom;
+ y.denom = tmp;
+
+ PG_RETURN_POINTER(mul(&x, &y));
+}
+
+Datum
+rational_neg(PG_FUNCTION_ARGS)
+{
+ Rational   *out = palloc(sizeof(Rational));
+
+ memcpy(out, PG_GETARG_POINTER(0), sizeof(Rational));
+ neg(out);
+
+ PG_RETURN_POINTER(out);
+}
+
+/*
+ *************** UTILITY ***************
+ */
+
+PG_FUNCTION_INFO_V1(rational_hash);
+PG_FUNCTION_INFO_V1(rational_intermediate);
+
+Datum
+rational_hash(PG_FUNCTION_ARGS)
+{
+ Rational x;
+
+ memcpy(&x, PG_GETARG_POINTER(0), sizeof(Rational));
+
+ /*
+ * hash_any works at binary level, so we must simplify fraction
+ */
+ simplify(&x);
+
+ return hash_any((const unsigned char *) &x, sizeof(Rational));
+}
+
+Datum
+rational_intermediate(PG_FUNCTION_ARGS)
+{
+ Rational x,
+ y, /* arguments */
+ lo = {0, 1},
+ hi = {1, 0}, /* yes, an internal use of 1/0 */
+   *med = palloc(sizeof(Rational));
+
+ /*
+ * x = coalesce(lo, arg[0]) y = coalesce(hi, arg[1])
+ */
+ memcpy(&x,
+   PG_ARGISNULL(0) ? &lo : (Rational *) PG_GETARG_POINTER(0),
+   sizeof(Rational));
+ memcpy(&y,
+   PG_ARGISNULL(1) ? &hi : (Rational *) PG_GETARG_POINTER(1),
+   sizeof(Rational));
+
+ if (cmp(&x, &lo) < 0 || cmp(&y, &lo) < 0)
+ ereport(ERROR,
+ (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
+ errmsg("arguments must be non-negative")));
+
+ if (cmp(&x, &y) >= 0)
+ ereport(ERROR,
+ (errcode(ERRCODE_INVALID_PARAMETER_VALUE),
+ errmsg("first argument must be strictly smaller than second")));
+
+ while (true)
+ {
+ mediant(&lo, &hi, med);
+ if (cmp(med, &x) < 1)
+ memcpy(&lo, med, sizeof(Rational));
+ else if (cmp(med, &y) > -1)
+ memcpy(&hi, med, sizeof(Rational));
+ else
+ break;
+ }
+
+ PG_RETURN_POINTER(med);
+}
+
+
+/*
+ ************* COMPARISON **************
+ */
+
+
+PG_FUNCTION_INFO_V1(rational_cmp);
+PG_FUNCTION_INFO_V1(rational_eq);
+PG_FUNCTION_INFO_V1(rational_ne);
+PG_FUNCTION_INFO_V1(rational_lt);
+PG_FUNCTION_INFO_V1(rational_le);
+PG_FUNCTION_INFO_V1(rational_gt);
+PG_FUNCTION_INFO_V1(rational_ge);
+
+PG_FUNCTION_INFO_V1(rational_smaller);
+PG_FUNCTION_INFO_V1(rational_larger);
+
+Datum
+rational_cmp(PG_FUNCTION_ARGS)
+{
+ PG_RETURN_INT32(
+ cmp((Rational *) PG_GETARG_POINTER(0), (Rational *) PG_GETARG_POINTER(1)));
+}
+
+Datum
+rational_eq(PG_FUNCTION_ARGS)
+{
+ PG_RETURN_BOOL(
+   cmp((Rational *) PG_GETARG_POINTER(0), (Rational *) PG_GETARG_POINTER(1)) == 0);
+}
+
+Datum
+rational_ne(PG_FUNCTION_ARGS)
+{
+ PG_RETURN_BOOL(
+   cmp((Rational *) PG_GETARG_POINTER(0), (Rational *) PG_GETARG_POINTER(1)) != 0);
+}
+
+Datum
+rational_lt(PG_FUNCTION_ARGS)
+{
+ PG_RETURN_BOOL(
+   cmp((Rational *) PG_GETARG_POINTER(0), (Rational *) PG_GETARG_POINTER(1)) < 0);
+}
+
+Datum
+rational_le(PG_FUNCTION_ARGS)
+{
+ PG_RETURN_BOOL(
+   cmp((Rational *) PG_GETARG_POINTER(0), (Rational *) PG_GETARG_POINTER(1)) <= 0);
+}
+
+Datum
+rational_gt(PG_FUNCTION_ARGS)
+{
+ PG_RETURN_BOOL(
+   cmp((Rational *) PG_GETARG_POINTER(0), (Rational *) PG_GETARG_POINTER(1)) > 0);
+}
+
+Datum
+rational_ge(PG_FUNCTION_ARGS)
+{
+ PG_RETURN_BOOL(
+   cmp((Rational *) PG_GETARG_POINTER(0), (Rational *) PG_GETARG_POINTER(1)) >= 0);
+}
+
+Datum
+rational_smaller(PG_FUNCTION_ARGS)
+{
+ Rational   *a = (Rational *) PG_GETARG_POINTER(0),
+   *b = (Rational *) PG_GETARG_POINTER(1);
+
+ PG_RETURN_POINTER(cmp(a, b) < 0 ? a : b);
+}
+
+Datum
+rational_larger(PG_FUNCTION_ARGS)
+{
+ Rational   *a = (Rational *) PG_GETARG_POINTER(0),
+   *b = (Rational *) PG_GETARG_POINTER(1);
+
+ PG_RETURN_POINTER(cmp(a, b) > 0 ? a : b);
+}
+
+
+/*
+ ************** INTERNAL ***************
+ */
+
+int32
+gcd(int32 a, int32 b)
+{
+ int32 temp;
+
+ while (b != 0)
+ {
+ temp = a % b;
+ a = b;
+ b = temp;
+ }
+
+ return a;
+}
+
+bool
+simplify(Rational * r)
+{
+ int32 common = gcd(r->numer, r->denom);
+
+ /*
+ * tricky: avoid overflow from (INT32_MIN / -1)
+ */
+ if (common != -1 || (r->numer != INT32_MIN && r->denom != INT32_MIN))
+ {
+ r->numer /= common;
+ r->denom /= common;
+ }
+
+ /*
+ * prevent negative denominator, but do not negate the smallest value --
+ * that would produce overflow
+ */
+ if (r->denom < 0 && r->numer != INT32_MIN && r->denom != INT32_MIN)
+ {
+ r->numer *= -1;
+ r->denom *= -1;
+ }
+ return (common != 1) && (common != -1);
+}
+
+int32
+cmp(Rational * a, Rational * b)
+{
+ /*
+ * Overflow is not an option, we need a total order so that btree indices
+ * do not die. Hence do the arithmetic in 64 bits.
+ */
+ int64 cross1 = (int64) a->numer * (int64) b->denom,
+ cross2 = (int64) a->denom * (int64) b->numer;
+
+ return (cross1 > cross2) - (cross1 < cross2);
+}
+
+void
+neg(Rational * r)
+{
+ if (r->numer == INT32_MIN)
+ {
+ simplify(r);
+
+ /*
+ * check again
+ */
+ if (r->numer == INT32_MIN)
+ {
+ /*
+ * denom can't be MIN too or fraction would have previously
+ * simplified to 1/1
+ */
+ r->denom *= -1;
+ return;
+ }
+ }
+ r->numer *= -1;
+}
+
+
+Rational *
+create(long long n, long long d)
+{
+ Rational   *result = palloc(sizeof(Rational));
+
+ if (d == 0)
+ ereport(ERROR,
+ (errcode(ERRCODE_DIVISION_BY_ZERO),
+ errmsg("fraction cannot have zero denominator")));
+
+ if (n < INT32_MIN || n > INT32_MAX || d < INT32_MIN || d > INT32_MAX)
+ ereport(ERROR,
+ (errcode(ERRCODE_NUMERIC_VALUE_OUT_OF_RANGE),
+ errmsg("numerator or denominator outside valid int32 value")));
+
+ /*
+ * prevent negative denominator, but do not negate the smallest value or
+ * else it would overflow
+ */
+ if (d >= 0 || n == INT32_MIN || d == INT32_MIN)
+ {
+ result->numer = (int32) n;
+ result->denom = (int32) d;
+ }
+ else
+ {
+ result->numer = (int32) -n;
+ result->denom = (int32) -d;
+ }
+
+ return result;
+}
+
+Rational *
+add(Rational * x, Rational * y)
+{
+ int32 xnyd,
+ ynxd,
+ numer,
+ denom;
+ bool nxyd_bad,
+ ynxd_bad,
+ numer_bad,
+ denom_bad;
+ Rational   *result;
+
+retry_add:
+ nxyd_bad = pg_mul_s32_overflow(x->numer, y->denom, &xnyd);
+ ynxd_bad = pg_mul_s32_overflow(y->numer, x->denom, &ynxd);
+ numer_bad = pg_add_s32_overflow(xnyd, ynxd, &numer);
+ denom_bad = pg_mul_s32_overflow(x->denom, y->denom, &denom);
+
+ if (nxyd_bad || ynxd_bad || numer_bad || denom_bad)
+ {
+ /* overflow in intermediate value */
+ if (!simplify(x) && !simplify(y))
+ {
+ /* neither fraction could reduce, cannot proceed */
+ ereport(ERROR, (
+ errcode(ERRCODE_NUMERIC_VALUE_OUT_OF_RANGE),
+ errmsg("intermediate value overflow in rational addition")
+ ));
+ }
+ /* the fraction(s) reduced, good for one more retry */
+ goto retry_add;
+ }
+ result = palloc(sizeof(Rational));
+ result->numer = numer;
+ result->denom = denom;
+ return result;
+}
+
+Rational *
+mul(Rational * x, Rational * y)
+{
+ int32 numer,
+ denom;
+ bool numer_bad,
+ denom_bad;
+ Rational   *result;
+
+retry_mul:
+ numer_bad = pg_mul_s32_overflow(x->numer, y->numer, &numer);
+ denom_bad = pg_mul_s32_overflow(x->denom, y->denom, &denom);
+
+ if (numer_bad || denom_bad)
+ {
+ /* overflow in intermediate value */
+ if (!simplify(x) && !simplify(y))
+ {
+ /* neither fraction could reduce, cannot proceed */
+ ereport(ERROR,
+ (errcode(ERRCODE_NUMERIC_VALUE_OUT_OF_RANGE),
+ errmsg("intermediate value overflow in rational multiplication")));
+ }
+ /* the fraction(s) reduced, good for one more retry */
+ goto retry_mul;
+ }
+ result = palloc(sizeof(Rational));
+ result->numer = numer;
+ result->denom = denom;
+
+ return result;
+}
+
+void
+mediant(Rational * x, Rational * y, Rational * m)
+{
+ /*
+ * Rational_intermediate sends fractions with small numers and denoms, and
+ * slowly builds up. The search will take forever before we ever get close
+ * to arithmetic overflow in this function, so I don't guard it here.
+ */
+ m->numer = x->numer + y->numer;
+ m->denom = x->denom + y->denom;
+}
diff --git a/src/include/catalog/pg_aggregate.dat b/src/include/catalog/pg_aggregate.dat
index ffabe275c0..3954b2d55e 100644
--- a/src/include/catalog/pg_aggregate.dat
+++ b/src/include/catalog/pg_aggregate.dat
@@ -69,6 +69,8 @@
   aggcombinefn => 'float4pl', aggtranstype => 'float4' },
 { aggfnoid => 'sum(float8)', aggtransfn => 'float8pl',
   aggcombinefn => 'float8pl', aggtranstype => 'float8' },
+{ aggfnoid => 'sum(rational)', aggtransfn => 'rational_add',
+  aggcombinefn => 'rational_add', aggtranstype => 'rational' },
 { aggfnoid => 'sum(money)', aggtransfn => 'cash_pl', aggcombinefn => 'cash_pl',
   aggmtransfn => 'cash_pl', aggminvtransfn => 'cash_mi',
   aggtranstype => 'money', aggmtranstype => 'money' },
@@ -104,6 +106,9 @@
 { aggfnoid => 'max(float8)', aggtransfn => 'float8larger',
   aggcombinefn => 'float8larger', aggsortop => '>(float8,float8)',
   aggtranstype => 'float8' },
+{ aggfnoid => 'max(rational)', aggtransfn => 'rational_larger',
+  aggcombinefn => 'rational_larger', aggsortop => '>(rational,rational)',
+  aggtranstype => 'rational' },
 { aggfnoid => 'max(date)', aggtransfn => 'date_larger',
   aggcombinefn => 'date_larger', aggsortop => '>(date,date)',
   aggtranstype => 'date' },
@@ -169,6 +174,9 @@
 { aggfnoid => 'min(float8)', aggtransfn => 'float8smaller',
   aggcombinefn => 'float8smaller', aggsortop => '<(float8,float8)',
   aggtranstype => 'float8' },
+{ aggfnoid => 'min(rational)', aggtransfn => 'rational_smaller',
+  aggcombinefn => 'rational_smaller', aggsortop => '<(rational,rational)',
+  aggtranstype => 'rational' },
 { aggfnoid => 'min(date)', aggtransfn => 'date_smaller',
   aggcombinefn => 'date_smaller', aggsortop => '<(date,date)',
   aggtranstype => 'date' },
diff --git a/src/include/catalog/pg_amop.dat b/src/include/catalog/pg_amop.dat
index 11aaa519c8..1377f05e64 100644
--- a/src/include/catalog/pg_amop.dat
+++ b/src/include/catalog/pg_amop.dat
@@ -281,6 +281,23 @@
   amoprighttype => 'float4', amopstrategy => '5', amopopr => '>(float8,float4)',
   amopmethod => 'btree' },
 
+# default operators rational
+{ amopfamily => 'btree/rational_ops', amoplefttype => 'rational',
+  amoprighttype => 'rational', amopstrategy => '1', amopopr => '<(rational,rational)',
+  amopmethod => 'btree' },
+{ amopfamily => 'btree/rational_ops', amoplefttype => 'rational',
+  amoprighttype => 'rational', amopstrategy => '2',
+  amopopr => '<=(rational,rational)', amopmethod => 'btree' },
+{ amopfamily => 'btree/rational_ops', amoplefttype => 'rational',
+  amoprighttype => 'rational', amopstrategy => '3', amopopr => '=(rational,rational)',
+  amopmethod => 'btree' },
+{ amopfamily => 'btree/rational_ops', amoplefttype => 'rational',
+  amoprighttype => 'rational', amopstrategy => '4',
+  amopopr => '>=(rational,rational)', amopmethod => 'btree' },
+{ amopfamily => 'btree/rational_ops', amoplefttype => 'rational',
+  amoprighttype => 'rational', amopstrategy => '5', amopopr => '>(rational,rational)',
+  amopmethod => 'btree' },
+
 # btree char_ops
 
 { amopfamily => 'btree/char_ops', amoplefttype => 'char',
@@ -903,6 +920,11 @@
   amoprighttype => 'float4', amopstrategy => '1', amopopr => '=(float8,float4)',
   amopmethod => 'hash' },
 
+# rational_ops
+{ amopfamily => 'hash/rational_ops', amoplefttype => 'rational',
+  amoprighttype => 'rational', amopstrategy => '1', amopopr => '=(rational,rational)',
+  amopmethod => 'hash' },
+
 # network_ops
 { amopfamily => 'hash/network_ops', amoplefttype => 'inet',
   amoprighttype => 'inet', amopstrategy => '1', amopopr => '=(inet,inet)',
diff --git a/src/include/catalog/pg_amproc.dat b/src/include/catalog/pg_amproc.dat
index c67768fcab..20c977301e 100644
--- a/src/include/catalog/pg_amproc.dat
+++ b/src/include/catalog/pg_amproc.dat
@@ -91,6 +91,11 @@
 { amprocfamily => 'btree/float_ops', amproclefttype => 'float4',
   amprocrighttype => 'float8', amprocnum => '3',
   amproc => 'in_range(float4,float4,float8,bool,bool)' },
+
+
+{ amprocfamily => 'btree/rational_ops', amproclefttype => 'rational',
+  amprocrighttype => 'rational', amprocnum => '1', amproc => 'rational_cmp' },
+
 { amprocfamily => 'btree/network_ops', amproclefttype => 'inet',
   amprocrighttype => 'inet', amprocnum => '1', amproc => 'network_cmp' },
 { amprocfamily => 'btree/network_ops', amproclefttype => 'inet',
@@ -252,6 +257,8 @@
 { amprocfamily => 'hash/float_ops', amproclefttype => 'float4',
   amprocrighttype => 'float4', amprocnum => '2',
   amproc => 'hashfloat4extended' },
+{ amprocfamily => 'hash/rational_ops', amproclefttype => 'rational',
+  amprocrighttype => 'rational', amprocnum => '1', amproc => 'hashrational' },
 { amprocfamily => 'hash/float_ops', amproclefttype => 'float8',
   amprocrighttype => 'float8', amprocnum => '1', amproc => 'hashfloat8' },
 { amprocfamily => 'hash/float_ops', amproclefttype => 'float8',
diff --git a/src/include/catalog/pg_cast.dat b/src/include/catalog/pg_cast.dat
index 6ef8b8a4e7..21b15b0330 100644
--- a/src/include/catalog/pg_cast.dat
+++ b/src/include/catalog/pg_cast.dat
@@ -36,6 +36,14 @@
   castcontext => 'i', castmethod => 'f' },
 { castsource => 'int2', casttarget => 'float8', castfunc => 'float8(int2)',
   castcontext => 'i', castmethod => 'f' },
+
+{ castsource => 'float8', casttarget => 'rational', castfunc => 'rational_in_float',
+  castcontext => 'i', castmethod => 'f' },
+{ castsource => 'rational', casttarget => 'float8', castfunc => 'rational_out_float',
+  castcontext => 'e', castmethod => 'f' },
+{ castsource => 'int4', casttarget => 'rational', castfunc => 'rational_in_integer',
+  castcontext => 'i', castmethod => 'f' },
+
 { castsource => 'int2', casttarget => 'numeric', castfunc => 'numeric(int2)',
   castcontext => 'i', castmethod => 'f' },
 { castsource => 'int4', casttarget => 'int8', castfunc => 'int8(int4)',
diff --git a/src/include/catalog/pg_opclass.dat b/src/include/catalog/pg_opclass.dat
index ab2f50c9eb..c5bae7945d 100644
--- a/src/include/catalog/pg_opclass.dat
+++ b/src/include/catalog/pg_opclass.dat
@@ -47,6 +47,10 @@
   opcintype => 'float4' },
 { opcmethod => 'hash', opcname => 'float4_ops', opcfamily => 'hash/float_ops',
   opcintype => 'float4' },
+{ opcmethod => 'btree', opcname => 'rational_ops', opcfamily => 'btree/rational_ops',
+  opcintype => 'rational' },
+{ opcmethod => 'hash', opcname => 'rational_ops', opcfamily => 'hash/rational_ops',
+  opcintype => 'rational' },
 { oid => '3123', oid_symbol => 'FLOAT8_BTREE_OPS_OID',
   opcmethod => 'btree', opcname => 'float8_ops', opcfamily => 'btree/float_ops',
   opcintype => 'float8' },
diff --git a/src/include/catalog/pg_operator.dat b/src/include/catalog/pg_operator.dat
index 7c135da3b1..5219b3bfaf 100644
--- a/src/include/catalog/pg_operator.dat
+++ b/src/include/catalog/pg_operator.dat
@@ -3298,4 +3298,53 @@
   oprresult => 'bool', oprcode => 'jsonb_path_match_opr(jsonb,jsonpath)',
   oprrest => 'contsel', oprjoin => 'contjoinsel' },
 
+# Rationals
+
+{ oid => '8565', descr => 'equal',
+  oprname => '=', oprcanmerge => 't', oprcanhash => 't', oprleft => 'rational',
+  oprright => 'rational', oprresult => 'bool', oprcom => '=(rational,rational)',
+  oprnegate => '<>(rational,rational)', oprcode => 'rational_eq', oprrest => 'eqsel',
+  oprjoin => 'eqjoinsel' },
+{ oid => '8566', descr => 'not equal',
+  oprname => '<>', oprleft => 'rational', oprright => 'rational',
+  oprresult => 'bool', oprcom => '<>(rational,rational)',
+  oprnegate => '=(rational,rational)', oprcode => 'rational_ne', oprrest => 'neqsel',
+  oprjoin => 'neqjoinsel' },
+{ oid => '8567', descr => 'less than',
+  oprname => '<', oprleft => 'rational', oprright => 'rational',
+  oprresult => 'bool', oprcom => '>(rational,rational)',
+  oprnegate => '>=(rational,rational)', oprcode => 'rational_lt',
+  oprrest => 'scalarltsel', oprjoin => 'scalarltjoinsel' },
+{ oid => '8568', descr => 'less than or equal',
+  oprname => '<=', oprleft => 'rational', oprright => 'rational',
+  oprresult => 'bool', oprcom => '>=(rational,rational)',
+  oprnegate => '>(rational,rational)', oprcode => 'rational_le',
+  oprrest => 'scalarlesel', oprjoin => 'scalarlejoinsel' },
+{ oid => '8569', descr => 'greater than',
+  oprname => '>', oprleft => 'rational', oprright => 'rational',
+  oprresult => 'bool', oprcom => '<(rational,rational)',
+  oprnegate => '<=(rational,rational)', oprcode => 'rational_gt',
+  oprrest => 'scalargtsel', oprjoin => 'scalargtjoinsel' },
+{ oid => '8570', descr => 'greater than or equal',
+  oprname => '>=', oprleft => 'rational', oprright => 'rational',
+  oprresult => 'bool', oprcom => '<=(rational,rational)',
+  oprnegate => '<(rational,rational)', oprcode => 'rational_ge',
+  oprrest => 'scalargesel', oprjoin => 'scalargejoinsel' },
+
+{ oid => '8571', descr => 'add',
+  oprname => '+', oprleft => 'rational', oprright => 'rational',
+  oprresult => 'rational', oprcom => '+(rational,rational)', oprcode => 'rational_add' },
+{ oid => '8572', descr => 'negate',
+  oprname => '-', oprkind => 'l', oprleft => '0', oprright => 'rational',
+  oprresult => 'rational', oprcode => 'rational_neg' },
+{ oid => '8573', descr => 'subtract',
+  oprname => '-', oprleft => 'rational', oprright => 'rational',
+  oprresult => 'rational', oprcode => 'rational_sub' },
+{ oid => '8574', descr => 'divide',
+  oprname => '/', oprleft => 'rational', oprright => 'rational',
+  oprresult => 'rational', oprcode => 'rational_div' },
+{ oid => '8575', descr => 'multiply',
+  oprname => '*', oprleft => 'rational', oprright => 'rational',
+  oprresult => 'rational', oprcom => '*(rational,rational)',
+  oprcode => 'rational_mul' },
 ]
diff --git a/src/include/catalog/pg_opfamily.dat b/src/include/catalog/pg_opfamily.dat
index 26227df216..cca4210982 100644
--- a/src/include/catalog/pg_opfamily.dat
+++ b/src/include/catalog/pg_opfamily.dat
@@ -38,6 +38,10 @@
   opfmethod => 'btree', opfname => 'float_ops' },
 { oid => '1971',
   opfmethod => 'hash', opfname => 'float_ops' },
+{ oid => '8579',
+  opfmethod => 'btree', opfname => 'rational_ops' },
+{ oid => '8580',
+  opfmethod => 'hash', opfname => 'rational_ops' },
 { oid => '1974', oid_symbol => 'NETWORK_BTREE_FAM_OID',
   opfmethod => 'btree', opfname => 'network_ops' },
 { oid => '1975',
diff --git a/src/include/catalog/pg_proc.dat b/src/include/catalog/pg_proc.dat
index 226c904c04..469082162a 100644
--- a/src/include/catalog/pg_proc.dat
+++ b/src/include/catalog/pg_proc.dat
@@ -6206,6 +6206,9 @@
 { oid => '2111', descr => 'sum as float8 across all float8 input values',
   proname => 'sum', prokind => 'a', proisstrict => 'f', prorettype => 'float8',
   proargtypes => 'float8', prosrc => 'aggregate_dummy' },
+{ oid => '8578', descr => 'sum as rational across all rational input values',
+  proname => 'sum', prokind => 'a', proisstrict => 'f', prorettype => 'rational',
+  proargtypes => 'rational', prosrc => 'aggregate_dummy' },
 { oid => '2112', descr => 'sum as money across all money input values',
   proname => 'sum', prokind => 'a', proisstrict => 'f', prorettype => 'money',
   proargtypes => 'money', prosrc => 'aggregate_dummy' },
@@ -6235,6 +6238,9 @@
 { oid => '2120', descr => 'maximum value of all float8 input values',
   proname => 'max', prokind => 'a', proisstrict => 'f', prorettype => 'float8',
   proargtypes => 'float8', prosrc => 'aggregate_dummy' },
+{ oid => '8576', descr => 'maximum value of all rational input values',
+  proname => 'max', prokind => 'a', proisstrict => 'f', prorettype => 'rational',
+  proargtypes => 'rational', prosrc => 'aggregate_dummy' },
 { oid => '2122', descr => 'maximum value of all date input values',
   proname => 'max', prokind => 'a', proisstrict => 'f', prorettype => 'date',
   proargtypes => 'date', prosrc => 'aggregate_dummy' },
@@ -6302,6 +6308,9 @@
 { oid => '2136', descr => 'minimum value of all float8 input values',
   proname => 'min', prokind => 'a', proisstrict => 'f', prorettype => 'float8',
   proargtypes => 'float8', prosrc => 'aggregate_dummy' },
+{ oid => '8577', descr => 'minimum value of all rational input values',
+  proname => 'min', prokind => 'a', proisstrict => 'f', prorettype => 'rational',
+  proargtypes => 'rational', prosrc => 'aggregate_dummy' },
 { oid => '2138', descr => 'minimum value of all date input values',
   proname => 'min', prokind => 'a', proisstrict => 'f', prorettype => 'date',
   proargtypes => 'date', prosrc => 'aggregate_dummy' },
@@ -10768,4 +10777,91 @@
   proname => 'pg_partition_root', prorettype => 'regclass',
   proargtypes => 'regclass', prosrc => 'pg_partition_root' },
 
+# rational numbers
+{ oid => '8536', descr => 'I/O',
+  proname => 'rational_in', provolatile => 's', prorettype => 'rational',
+  proargtypes => 'cstring', prosrc => 'rational_in' },
+{ oid => '8537', descr => 'I/O',
+  proname => 'rational_in_float', provolatile => 's', prorettype => 'rational',
+  proargtypes => 'float8', prosrc => 'rational_in_float' },
+{ oid => '8535', descr => 'I/O',
+  proname => 'rational_in_integer', provolatile => 's', prorettype => 'rational',
+  proargtypes => 'int4', prosrc => 'rational_in_integer' },
+{ oid => '8538', descr => 'I/O',
+  proname => 'rational_out', provolatile => 's', prorettype => 'cstring',
+  proargtypes => 'rational', prosrc => 'rational_out' },
+{ oid => '8539', descr => 'I/O',
+  proname => 'rational_out_float', provolatile => 's', prorettype => 'float8',
+  proargtypes => 'rational', prosrc => 'rational_out_float' },
+{ oid => '8540', descr => 'I/O',
+  proname => 'rational_recv', prorettype => 'rational', proargtypes => 'internal',
+  prosrc => 'rational_recv' },
+{ oid => '8541', descr => 'I/O',
+  proname => 'rational_send', prorettype => 'bytea', proargtypes => 'rational',
+  prosrc => 'rational_send' },
+
+{ oid => '8542', descr => 'Construction',
+  proname => 'rational', prorettype => 'rational',
+  proargtypes => 'int4 int4', prosrc => 'rational_create' },
+{ oid => '8543', descr => 'Construction',
+  proname => 'rational', prorettype => 'rational',
+  proargtypes => 'int4', prosrc => 'rational_in_integer' },
+
+{ oid => '8547', descr => 'Arithmetic',
+  proname => 'rational_add', prorettype => 'rational',
+  proargtypes => 'rational rational', prosrc => 'rational_add' },
+{ oid => '8548', descr => 'Arithmetic',
+  proname => 'rational_sub', prorettype => 'rational',
+  proargtypes => 'rational rational', prosrc => 'rational_sub' },
+{ oid => '8549', descr => 'Arithmetic',
+  proname => 'rational_mul', prorettype => 'rational',
+  proargtypes => 'rational rational', prosrc => 'rational_mul' },
+{ oid => '8550', descr => 'Arithmetic',
+  proname => 'rational_div', prorettype => 'rational',
+  proargtypes => 'rational rational', prosrc => 'rational_div' },
+{ oid => '8551', descr => 'Arithmetic',
+  proname => 'rational_neg', prorettype => 'rational',
+  proargtypes => 'rational', prosrc => 'rational_neg' },
+{ oid => '8552', descr => 'Manipulation',
+  proname => 'rational_simplify', prorettype => 'rational',
+  proargtypes => 'rational', prosrc => 'rational_simplify' },
+{ oid => '8553', descr => 'Manipulation',
+  proname => 'rational_intermediate', prorettype => 'rational',
+  proargtypes => 'rational rational', proisstrict => 'f',
+  prosrc => 'rational_intermediate' },
+
+{ oid => '8554', descr => 'Comparison',
+  proname => 'rational_eq', prorettype => 'bool',
+  proargtypes => 'rational rational', prosrc => 'rational_eq' },
+{ oid => '8555', descr => 'Comparison',
+  proname => 'rational_ne', prorettype => 'bool',
+  proargtypes => 'rational rational', prosrc => 'rational_ne' },
+{ oid => '8556', descr => 'Comparison',
+  proname => 'rational_lt', prorettype => 'bool',
+  proargtypes => 'rational rational', prosrc => 'rational_lt' },
+{ oid => '8557', descr => 'Comparison',
+  proname => 'rational_le', prorettype => 'bool',
+  proargtypes => 'rational rational', prosrc => 'rational_le' },
+{ oid => '8558', descr => 'Comparison',
+  proname => 'rational_gt', prorettype => 'bool',
+  proargtypes => 'rational rational', prosrc => 'rational_gt' },
+{ oid => '8559', descr => 'Comparison',
+  proname => 'rational_ge', prorettype => 'bool',
+  proargtypes => 'rational rational', prosrc => 'rational_ge' },
+{ oid => '8560', descr => 'Comparison',
+  proname => 'rational_cmp', prorettype => 'int4',
+  proargtypes => 'rational rational', prosrc => 'rational_cmp' },
+{ oid => '8561', descr => 'smaller of two',
+  proname => 'rational_smaller', prorettype => 'rational',
+  proargtypes => 'rational rational', prosrc => 'rational_smaller' },
+{ oid => '8562', descr => 'larger of two',
+  proname => 'rational_larger', prorettype => 'rational',
+  proargtypes => 'rational rational', prosrc => 'rational_larger' },
+
+{ oid => '8563', descr => 'hash',
+  proname => 'hashrational', prorettype => 'int4',
+  proargtypes => 'rational', prosrc => 'rational_hash' },
+
 ]
diff --git a/src/include/catalog/pg_type.dat b/src/include/catalog/pg_type.dat
index fe2c4eabb4..9fcf969d10 100644
--- a/src/include/catalog/pg_type.dat
+++ b/src/include/catalog/pg_type.dat
@@ -595,4 +595,10 @@
   typcategory => 'P', typinput => 'anyrange_in', typoutput => 'anyrange_out',
   typreceive => '-', typsend => '-', typalign => 'd', typstorage => 'x' },
 
+{ oid => '8564', array_type_oid => '8601',
+  descr => 'rational numbers (fractions) with int4 numerator and denominator',
+  typname => 'rational', typlen => '8', typbyval => 'f', typtype => 'b',
+  typcategory => 'N', typinput => 'rational_in', typoutput => 'rational_out',
+  typreceive => 'rational_recv', typsend => 'rational_send',
+  typalign => 'd' },
 ]
diff --git a/src/test/regress/expected/opr_sanity.out b/src/test/regress/expected/opr_sanity.out
index c19740e5db..c441ced3ed 100644
--- a/src/test/regress/expected/opr_sanity.out
+++ b/src/test/regress/expected/opr_sanity.out
@@ -168,9 +168,10 @@ WHERE p1.oid < p2.oid AND
      p1.proretset != p2.proretset OR
      p1.provolatile != p2.provolatile OR
      p1.pronargs != p2.pronargs);
- oid | proname | oid | proname
------+---------+-----+---------
-(0 rows)
+ oid  |       proname       | oid  | proname  
+------+---------------------+------+----------
+ 8535 | rational_in_integer | 8543 | rational
+(1 row)
 
 -- Look for uses of different type OIDs in the argument/result type fields
 -- for different aliases of the same built-in function.
@@ -1301,9 +1302,20 @@ SELECT * FROM funcdescs
   WHERE prodesc IS DISTINCT FROM expecteddesc
     AND oprdesc NOT LIKE 'deprecated%'
     AND prodesc IS DISTINCT FROM oprdesc;
- p_oid | proname | o_oid | prodesc | expecteddesc | oprdesc
--------+---------+-------+---------+--------------+---------
-(0 rows)
+ p_oid |   proname    | o_oid |  prodesc   |         expecteddesc          |        oprdesc        
+-------+--------------+-------+------------+-------------------------------+-----------------------
+  8554 | rational_eq  |  8565 | Comparison | implementation of = operator  | equal
+  8555 | rational_ne  |  8566 | Comparison | implementation of <> operator | not equal
+  8556 | rational_lt  |  8567 | Comparison | implementation of < operator  | less than
+  8557 | rational_le  |  8568 | Comparison | implementation of <= operator | less than or equal
+  8558 | rational_gt  |  8569 | Comparison | implementation of > operator  | greater than
+  8559 | rational_ge  |  8570 | Comparison | implementation of >= operator | greater than or equal
+  8547 | rational_add |  8571 | Arithmetic | implementation of + operator  | add
+  8551 | rational_neg |  8572 | Arithmetic | implementation of - operator  | negate
+  8548 | rational_sub |  8573 | Arithmetic | implementation of - operator  | subtract
+  8550 | rational_div |  8574 | Arithmetic | implementation of / operator  | divide
+  8549 | rational_mul |  8575 | Arithmetic | implementation of * operator  | multiply
+(11 rows)
 
 -- Show all the operator-implementation functions that have their own
 -- comments.  This should happen only in cases where the function and
@@ -1336,7 +1348,18 @@ ORDER BY 1;
   3940 | jsonb_extract_path_text | get value from jsonb as text with path elements
   3951 | json_extract_path       | get value from json with path elements
   3953 | json_extract_path_text  | get value from json as text with path elements
-(9 rows)
+  8547 | rational_add            | Arithmetic
+  8548 | rational_sub            | Arithmetic
+  8549 | rational_mul            | Arithmetic
+  8550 | rational_div            | Arithmetic
+  8551 | rational_neg            | Arithmetic
+  8554 | rational_eq             | Comparison
+  8555 | rational_ne             | Comparison
+  8556 | rational_lt             | Comparison
+  8557 | rational_le             | Comparison
+  8558 | rational_gt             | Comparison
+  8559 | rational_ge             | Comparison
+(20 rows)
 
 -- Operators that are commutator pairs should have identical volatility
 -- and leakproofness markings on their implementation functions.
diff --git a/src/test/regress/expected/rational.out b/src/test/regress/expected/rational.out
new file mode 100644
index 0000000000..7aa9a3e49b
--- /dev/null
+++ b/src/test/regress/expected/rational.out
@@ -0,0 +1,690 @@
+--
+-- Rational numbers
+-- I/O
+-- can parse a simple fraction
+select '1/3'::rational;
+ rational
+----------
+ 1/3
+(1 row)
+
+-- can parse negatives
+select '-1/3'::rational;
+ rational
+----------
+ -1/3
+(1 row)
+
+select '1/-3'::rational;
+ rational
+----------
+ -1/3
+(1 row)
+
+-- SEND works
+select rational_send('1/3');
+   rational_send    
+--------------------
+ \x0000000100000003
+(1 row)
+
+-- constructor proc
+select rational(1,2) = '1/2'::rational;
+ ?column?
+----------
+ t
+(1 row)
+
+-- casting
+-- int
+select 42 = '42/1'::rational;
+ ?column?
+----------
+ t
+(1 row)
+
+-- from float
+select 0.263157894737::float::rational;
+ rational
+----------
+ 5/19
+(1 row)
+
+select 3.141592625359::float::rational;
+    rational    
+-----------------
+ 4712235/1499951
+(1 row)
+
+select 0.606557377049::float::rational;
+ rational
+----------
+ 37/61
+(1 row)
+
+select -0.5::float::rational;
+ ?column?
+----------
+ -1/2
+(1 row)
+
+select 1.000001::float::rational;
+    rational    
+-----------------
+ 1000001/1000000
+(1 row)
+
+select 1.0000001::float::rational;
+     rational    
+------------------
+ 10000000/9999999
+(1 row)
+
+select 1.00000001::float::rational;
+      rational      
+---------------------
+ 100000001/100000000
+(1 row)
+
+select 1.000000001::float::rational;
+      rational      
+---------------------
+ 999999918/999999917
+(1 row)
+
+select 1.0000000001::float::rational;
+ rational
+----------
+ 1/1
+(1 row)
+
+select 2147483647::float::rational;
+   rational  
+--------------
+ 2147483647/1
+(1 row)
+
+select 2147483647.1::float::rational;
+ERROR:  value too large for rational
+select 'NAN'::float::rational;
+ERROR:  value too large for rational
+-- to float
+select '1/2'::rational::float;
+ float8
+--------
+    0.5
+(1 row)
+
+set extra_float_digits = 0; -- default changed in PG12
+select '1/3'::rational::float;
+      float8      
+-------------------
+ 0.333333333333333
+(1 row)
+
+reset extra_float_digits;
+select '-1/2'::rational::float;
+ float8
+--------
+   -0.5
+(1 row)
+
+-- too big
+select '2147483648/2147483647'::rational;
+ERROR:  numerator or denominator outside valid int32 value
+LINE 1: select '2147483648/2147483647'::rational;
+               ^
+-- no spaces
+select '1 /3'::rational;
+ERROR:  Expecting '/' after number but found ' '
+LINE 1: select '1 /3'::rational;
+               ^
+-- no zero denominator
+select '1/0'::rational;
+ERROR:  fraction cannot have zero denominator
+LINE 1: select '1/0'::rational;
+               ^
+-- quoted number treated as int
+select '1'::rational;
+ rational
+----------
+ 1/1
+(1 row)
+
+select '-1'::rational;
+ rational
+----------
+ -1/1
+(1 row)
+
+-- no garbage
+select ''::rational;
+ERROR:  Missing or invalid numerator
+LINE 1: select ''::rational;
+               ^
+select '/'::rational;
+ERROR:  Missing or invalid numerator
+LINE 1: select '/'::rational;
+               ^
+select '2/'::rational;
+ERROR:  Expecting value after '/' but got '\0'
+LINE 1: select '2/'::rational;
+               ^
+select '/2'::rational;
+ERROR:  Missing or invalid numerator
+LINE 1: select '/2'::rational;
+               ^
+select 'sdfkjsdfj34984538'::rational;
+ERROR:  Missing or invalid numerator
+LINE 1: select 'sdfkjsdfj34984538'::rational;
+               ^
+-- simplification
+-- double negative becomes positive
+select rational_simplify('-1/-3');
+ rational_simplify
+-------------------
+ 1/3
+(1 row)
+
+-- works with negative value
+select rational_simplify('-3/12');
+ rational_simplify
+-------------------
+ -1/4
+(1 row)
+
+-- dodge the INT32_MIN/-1 mistake
+select rational_simplify('-2147483648/2147483647');
+   rational_simplify    
+------------------------
+ -2147483648/2147483647
+(1 row)
+
+-- don't move negative if it would overflow
+select rational_simplify('1/-2147483648');
+ rational_simplify
+-------------------
+ 1/-2147483648
+(1 row)
+
+-- biggest value reduces
+select rational_simplify('2147483647/2147483647');
+ rational_simplify
+-------------------
+ 1/1
+(1 row)
+
+-- smallest value reduces
+select rational_simplify('-2147483648/-2147483648');
+ rational_simplify
+-------------------
+ 1/1
+(1 row)
+
+-- idempotent on simplified expression
+select rational_simplify('1/1');
+ rational_simplify
+-------------------
+ 1/1
+(1 row)
+
+-- addition
+-- additive identity
+select '0/1'::rational + '1/2';
+ ?column?
+----------
+ 1/2
+(1 row)
+
+-- additive inverse
+select '1/2'::rational + '-1/2';
+ ?column?
+----------
+ 0/4
+(1 row)
+
+-- just regular
+select '1/2'::rational + '1/2';
+ ?column?
+----------
+ 4/4
+(1 row)
+
+-- forcing intermediate simplification
+select '2147483647/2147483647'::rational + '1/1';
+ ?column?
+----------
+ 2/1
+(1 row)
+
+-- overflow (sqrt(max)+1)/1 + 1/sqrt(max)
+select '46342/1'::rational + '1/46341';
+ERROR:  intermediate value overflow in rational addition
+-- multiplication
+-- multiplicative identity
+select '1/1'::rational * '1/2';
+ ?column?
+----------
+ 1/2
+(1 row)
+
+-- multiplicative inverse
+select '2/1'::rational * '1/2';
+ ?column?
+----------
+ 2/2
+(1 row)
+
+-- just regular
+select '5/8'::rational * '3/5';
+ ?column?
+----------
+ 15/40
+(1 row)
+
+-- forcing intermediate simplification
+select '2147483647/2147483647'::rational * '2/2';
+ ?column?
+----------
+ 2/2
+(1 row)
+
+-- overflow
+select '46342/46341'::rational * '46341/46342';
+ERROR:  intermediate value overflow in rational multiplication
+-- division
+select 1::rational / 3;
+ ?column?
+----------
+ 1/3
+(1 row)
+
+select '2/3'::rational / '2/3';
+ ?column?
+----------
+ 6/6
+(1 row)
+
+-- negation
+-- flips sign of numerator
+select -('1/2'::rational);
+ ?column?
+----------
+ -1/2
+(1 row)
+
+-- flips back
+select -('-1/2'::rational);
+ ?column?
+----------
+ 1/2
+(1 row)
+
+-- overflow not possible
+select -('-2147483648/1'::rational);
+    ?column?    
+----------------
+ -2147483648/-1
+(1 row)
+
+select -('1/-2147483648'::rational);
+    ?column?    
+----------------
+ -1/-2147483648
+(1 row)
+
+select -('-2147483648/-2147483648'::rational);
+ ?column?
+----------
+ -1/1
+(1 row)
+
+-- subtraction
+-- just regular
+select '1/2'::rational - '1/2';
+ ?column?
+----------
+ 0/4
+(1 row)
+
+-- can go negative
+select '1/2'::rational - '1/1';
+ ?column?
+----------
+ -1/2
+(1 row)
+
+-- forcing intermediate simplification
+select '2147483647/2147483647'::rational - '100/100';
+ ?column?
+----------
+ 0/100
+(1 row)
+
+-- overflow (sqrt(max)+1)/1 - 1/sqrt(max)
+select '46342/1'::rational - '1/46341';
+ERROR:  intermediate value overflow in rational addition
+-- comparison
+-- equal in every way
+select '1/1'::rational = '1/1';
+ ?column?
+----------
+ t
+(1 row)
+
+-- same equivalence class
+select '20/40'::rational = '22/44';
+ ?column?
+----------
+ t
+(1 row)
+
+-- negatives work too
+select '-20/40'::rational = '-22/44';
+ ?column?
+----------
+ t
+(1 row)
+
+-- overflow not possible
+select '46342/46341'::rational = '46342/46341';
+ ?column?
+----------
+ t
+(1 row)
+
+-- high precision
+select '1/2147483647'::rational = '1/2147483646';
+ ?column?
+----------
+ f
+(1 row)
+
+select '1/3'::rational * 3 = 1;
+ ?column?
+----------
+ t
+(1 row)
+
+select 1.0/3.0 = 1.0;
+ ?column?
+----------
+ f
+(1 row)
+
+-- not everything is equal
+select '2/3'::rational = '8/5';
+ ?column?
+----------
+ f
+(1 row)
+
+-- negates equality
+select '1/1'::rational <> '1/1';
+ ?column?
+----------
+ f
+(1 row)
+
+-- overflow not possible
+select '46342/46341'::rational <> '46342/46341';
+ ?column?
+----------
+ f
+(1 row)
+
+-- not equal
+select '2/3'::rational <> '8/5';
+ ?column?
+----------
+ t
+(1 row)
+
+-- lt anti-reflexive
+select '1/2'::rational < '1/2';
+ ?column?
+----------
+ f
+(1 row)
+
+-- gt anti-reflexive
+select '1/2'::rational > '1/2';
+ ?column?
+----------
+ f
+(1 row)
+
+-- overflow not possible
+select '1/2147483647'::rational < '2/2147483647';
+ ?column?
+----------
+ t
+(1 row)
+
+-- lte
+select r
+  from unnest(ARRAY[
+      '303700050/303700050',
+      '-2/1',
+      '0/9999999',
+      '-11/17',
+      '100/1',
+      '3/4',
+      '-1/2',
+      '-1/1',
+      '5/8',
+      '6/9',
+      '5/8'
+    ]::rational[]) as r
+order by r asc;
+          r          
+---------------------
+ -2/1
+ -1/1
+ -11/17
+ -1/2
+ 0/9999999
+ 5/8
+ 5/8
+ 6/9
+ 3/4
+ 303700050/303700050
+ 100/1
+(11 rows)
+
+-- gte
+select r
+  from unnest(ARRAY[
+      '303700050/303700050',
+      '-2/1',
+      '0/9999999',
+      '-11/17',
+      '100/1',
+      '3/4',
+      '-1/2',
+      '-1/1',
+      '5/8',
+      '6/9',
+      '5/8'
+    ]::rational[]) as r
+order by r desc;
+          r          
+---------------------
+ 100/1
+ 303700050/303700050
+ 3/4
+ 6/9
+ 5/8
+ 5/8
+ 0/9999999
+ -1/2
+ -11/17
+ -1/1
+ -2/1
+(11 rows)
+
+-- btree
+create table rs (
+  r rational
+);
+create index rs_r_btree on rs using btree(r);
+insert into rs values ('0/7'), ('1/7'), ('2/7'), ('3/7'),
+                      ('4/7'), ('5/7'), ('6/7');
+set enable_seqscan=false;
+explain select * from rs where r > '1/7' and r <= '10/14';
+                                QUERY PLAN                                
+--------------------------------------------------------------------------
+ Bitmap Heap Scan on rs  (cost=4.27..14.97 rows=11 width=8)
+   Recheck Cond: ((r > '1/7'::rational) AND (r <= '10/14'::rational))
+   ->  Bitmap Index Scan on rs_r_btree  (cost=0.00..4.27 rows=11 width=0)
+         Index Cond: ((r > '1/7'::rational) AND (r <= '10/14'::rational))
+(4 rows)
+
+select * from rs where r > '1/7' and r <= '10/14';
+  r  
+-----
+ 2/7
+ 3/7
+ 4/7
+ 5/7
+(4 rows)
+
+set enable_seqscan=true;
+drop table rs cascade;
+-- hash
+create table rs (
+  r rational
+);
+create index rs_r_hash on rs using hash(r);
+insert into rs values ('0/7'), ('1/7');
+set enable_seqscan=false;
+explain select * from rs where r = '0/1';
+                               QUERY PLAN                                
+-------------------------------------------------------------------------
+ Bitmap Heap Scan on rs  (cost=4.09..14.76 rows=11 width=8)
+   Recheck Cond: (r = '0/1'::rational)
+   ->  Bitmap Index Scan on rs_r_hash  (cost=0.00..4.08 rows=11 width=0)
+         Index Cond: (r = '0/1'::rational)
+(4 rows)
+
+select * from rs where r = '0/1';
+  r  
+-----
+ 0/7
+(1 row)
+
+select * from rs where r = '2/7';
+ r
+---
+(0 rows)
+
+set enable_seqscan=true;
+drop table rs cascade;
+-- aggregates
+select min(r)
+  from unnest(ARRAY[
+      '100/1',
+      NULL,
+      '-11/17',
+      '-1/1'
+    ]::rational[]) as r;
+ min  
+------
+ -1/1
+(1 row)
+
+select max(r)
+  from unnest(ARRAY[
+      '100/1',
+      NULL,
+      '-11/17',
+      '-1/1'
+    ]::rational[]) as r;
+  max  
+-------
+ 100/1
+(1 row)
+
+select max(r)
+  from unnest(ARRAY[
+      NULL, NULL, NULL
+    ]::rational[]) as r;
+ max
+-----
+
+(1 row)
+
+select rational_simplify(sum(r))
+  from unnest(ARRAY[
+      '1/1',  '1/2', NULL,
+      '-3/2', '1/16'
+    ]::rational[]) as r;
+ rational_simplify
+-------------------
+ 1/16
+(1 row)
+
+select sum(r)
+  from unnest(ARRAY[
+      NULL, NULL, NULL
+    ]::rational[]) as r;
+ sum
+-----
+
+(1 row)
+
+-- stern-brocot intermediates
+-- intermediates start at 1 -- between 0 and Infinity
+select rational_intermediate(NULL, NULL);
+ rational_intermediate
+-----------------------
+ 1/1
+(1 row)
+
+-- random example
+select rational_intermediate('15/16', 1);
+ rational_intermediate
+-----------------------
+ 16/17
+(1 row)
+
+select rational_intermediate('15/16', 1)
+  between '15/16'::rational and 1;
+ ?column?
+----------
+ t
+(1 row)
+
+select rational_intermediate('44320/39365', '77200/12184');
+ rational_intermediate
+-----------------------
+ 2/1
+(1 row)
+
+select rational_intermediate('44320/39365', '77200/12184')
+  between '44320/39365'::rational and '77200/12184';
+ ?column?
+----------
+ t
+(1 row)
+
+-- unbounded upper limit produces least greater integer
+select rational_intermediate('1/3', NULL);
+ rational_intermediate
+-----------------------
+ 1/1
+(1 row)
+
+select rational_intermediate('3/2', NULL);
+ rational_intermediate
+-----------------------
+ 2/1
+(1 row)
+
+-- though not the other direction
+select rational_intermediate(NULL, '15/16');
+ rational_intermediate
+-----------------------
+ 1/2
+(1 row)
+
diff --git a/src/test/regress/parallel_schedule b/src/test/regress/parallel_schedule
index d2b17dd3ea..50b4eb1220 100644
--- a/src/test/regress/parallel_schedule
+++ b/src/test/regress/parallel_schedule
@@ -13,7 +13,7 @@ test: tablespace
 # ----------
 # The first group of parallel tests
 # ----------
-test: boolean char name varchar text int2 int4 int8 oid float4 float8 bit numeric txid uuid enum money rangetypes pg_lsn regproc
+test: boolean char name varchar text int2 int4 int8 oid float4 float8 rational bit numeric txid uuid enum money rangetypes pg_lsn
 
 # ----------
 # The second group of parallel tests
@@ -27,7 +27,7 @@ test: strings numerology point lseg line box path polygon circle date time timet
 # geometry depends on point, lseg, box, path, polygon and circle
 # horology depends on interval, timetz, timestamp, timestamptz
 # ----------
-test: geometry horology regex oidjoins type_sanity opr_sanity misc_sanity comments expressions
+test: geometry horology regex regproc oidjoins type_sanity opr_sanity misc_sanity comments expressions
 
 # ----------
 # These four each depend on the previous one
diff --git a/src/test/regress/serial_schedule b/src/test/regress/serial_schedule
index acba391332..9a32246d58 100644
--- a/src/test/regress/serial_schedule
+++ b/src/test/regress/serial_schedule
@@ -12,6 +12,7 @@ test: int8
 test: oid
 test: float4
 test: float8
+test: rational
 test: bit
 test: numeric
 test: txid
diff --git a/src/test/regress/sql/rational.sql b/src/test/regress/sql/rational.sql
new file mode 100644
index 0000000000..48462ad8d3
--- /dev/null
+++ b/src/test/regress/sql/rational.sql
@@ -0,0 +1,272 @@
+--
+-- Rational numbers
+
+-- I/O
+
+-- can parse a simple fraction
+select '1/3'::rational;
+-- can parse negatives
+select '-1/3'::rational;
+select '1/-3'::rational;
+-- SEND works
+select rational_send('1/3');
+
+-- constructor proc
+select rational(1,2) = '1/2'::rational;
+
+-- casting
+
+-- int
+select 42 = '42/1'::rational;
+
+-- from float
+select 0.263157894737::float::rational;
+select 3.141592625359::float::rational;
+select 0.606557377049::float::rational;
+select -0.5::float::rational;
+select 1.000001::float::rational;
+select 1.0000001::float::rational;
+select 1.00000001::float::rational;
+select 1.000000001::float::rational;
+select 1.0000000001::float::rational;
+select 2147483647::float::rational;
+select 2147483647.1::float::rational;
+select 'NAN'::float::rational;
+
+-- to float
+select '1/2'::rational::float;
+set extra_float_digits = 0; -- default changed in PG12
+select '1/3'::rational::float;
+reset extra_float_digits;
+select '-1/2'::rational::float;
+
+-- too big
+select '2147483648/2147483647'::rational;
+-- no spaces
+select '1 /3'::rational;
+-- no zero denominator
+select '1/0'::rational;
+-- quoted number treated as int
+select '1'::rational;
+select '-1'::rational;
+-- no garbage
+select ''::rational;
+select '/'::rational;
+select '2/'::rational;
+select '/2'::rational;
+select 'sdfkjsdfj34984538'::rational;
+
+-- simplification
+
+-- double negative becomes positive
+select rational_simplify('-1/-3');
+-- works with negative value
+select rational_simplify('-3/12');
+-- dodge the INT32_MIN/-1 mistake
+select rational_simplify('-2147483648/2147483647');
+-- don't move negative if it would overflow
+select rational_simplify('1/-2147483648');
+-- biggest value reduces
+select rational_simplify('2147483647/2147483647');
+-- smallest value reduces
+select rational_simplify('-2147483648/-2147483648');
+-- idempotent on simplified expression
+select rational_simplify('1/1');
+
+-- addition
+
+-- additive identity
+select '0/1'::rational + '1/2';
+-- additive inverse
+select '1/2'::rational + '-1/2';
+-- just regular
+select '1/2'::rational + '1/2';
+-- forcing intermediate simplification
+select '2147483647/2147483647'::rational + '1/1';
+-- overflow (sqrt(max)+1)/1 + 1/sqrt(max)
+select '46342/1'::rational + '1/46341';
+
+-- multiplication
+
+-- multiplicative identity
+select '1/1'::rational * '1/2';
+-- multiplicative inverse
+select '2/1'::rational * '1/2';
+-- just regular
+select '5/8'::rational * '3/5';
+-- forcing intermediate simplification
+select '2147483647/2147483647'::rational * '2/2';
+-- overflow
+select '46342/46341'::rational * '46341/46342';
+
+-- division
+
+select 1::rational / 3;
+select '2/3'::rational / '2/3';
+
+-- negation
+
+-- flips sign of numerator
+select -('1/2'::rational);
+-- flips back
+select -('-1/2'::rational);
+-- overflow not possible
+select -('-2147483648/1'::rational);
+select -('1/-2147483648'::rational);
+select -('-2147483648/-2147483648'::rational);
+
+-- subtraction
+
+-- just regular
+select '1/2'::rational - '1/2';
+-- can go negative
+select '1/2'::rational - '1/1';
+-- forcing intermediate simplification
+select '2147483647/2147483647'::rational - '100/100';
+-- overflow (sqrt(max)+1)/1 - 1/sqrt(max)
+select '46342/1'::rational - '1/46341';
+
+-- comparison
+
+-- equal in every way
+select '1/1'::rational = '1/1';
+-- same equivalence class
+select '20/40'::rational = '22/44';
+-- negatives work too
+select '-20/40'::rational = '-22/44';
+-- overflow not possible
+select '46342/46341'::rational = '46342/46341';
+-- high precision
+select '1/2147483647'::rational = '1/2147483646';
+select '1/3'::rational * 3 = 1;
+select 1.0/3.0 = 1.0;
+-- not everything is equal
+select '2/3'::rational = '8/5';
+
+-- negates equality
+select '1/1'::rational <> '1/1';
+-- overflow not possible
+select '46342/46341'::rational <> '46342/46341';
+-- not equal
+select '2/3'::rational <> '8/5';
+
+-- lt anti-reflexive
+select '1/2'::rational < '1/2';
+-- gt anti-reflexive
+select '1/2'::rational > '1/2';
+-- overflow not possible
+select '1/2147483647'::rational < '2/2147483647';
+
+-- lte
+select r
+  from unnest(ARRAY[
+      '303700050/303700050',
+      '-2/1',
+      '0/9999999',
+      '-11/17',
+      '100/1',
+      '3/4',
+      '-1/2',
+      '-1/1',
+      '5/8',
+      '6/9',
+      '5/8'
+    ]::rational[]) as r
+order by r asc;
+-- gte
+select r
+  from unnest(ARRAY[
+      '303700050/303700050',
+      '-2/1',
+      '0/9999999',
+      '-11/17',
+      '100/1',
+      '3/4',
+      '-1/2',
+      '-1/1',
+      '5/8',
+      '6/9',
+      '5/8'
+    ]::rational[]) as r
+order by r desc;
+
+-- btree
+create table rs (
+  r rational
+);
+create index rs_r_btree on rs using btree(r);
+insert into rs values ('0/7'), ('1/7'), ('2/7'), ('3/7'),
+                      ('4/7'), ('5/7'), ('6/7');
+set enable_seqscan=false;
+
+explain select * from rs where r > '1/7' and r <= '10/14';
+select * from rs where r > '1/7' and r <= '10/14';
+
+set enable_seqscan=true;
+drop table rs cascade;
+
+-- hash
+create table rs (
+  r rational
+);
+create index rs_r_hash on rs using hash(r);
+insert into rs values ('0/7'), ('1/7');
+set enable_seqscan=false;
+
+explain select * from rs where r = '0/1';
+select * from rs where r = '0/1';
+select * from rs where r = '2/7';
+
+set enable_seqscan=true;
+drop table rs cascade;
+
+-- aggregates
+
+select min(r)
+  from unnest(ARRAY[
+      '100/1',
+      NULL,
+      '-11/17',
+      '-1/1'
+    ]::rational[]) as r;
+
+select max(r)
+  from unnest(ARRAY[
+      '100/1',
+      NULL,
+      '-11/17',
+      '-1/1'
+    ]::rational[]) as r;
+
+select max(r)
+  from unnest(ARRAY[
+      NULL, NULL, NULL
+    ]::rational[]) as r;
+
+select rational_simplify(sum(r))
+  from unnest(ARRAY[
+      '1/1',  '1/2', NULL,
+      '-3/2', '1/16'
+    ]::rational[]) as r;
+
+select sum(r)
+  from unnest(ARRAY[
+      NULL, NULL, NULL
+    ]::rational[]) as r;
+
+-- stern-brocot intermediates
+
+-- intermediates start at 1 -- between 0 and Infinity
+select rational_intermediate(NULL, NULL);
+-- random example
+select rational_intermediate('15/16', 1);
+select rational_intermediate('15/16', 1)
+  between '15/16'::rational and 1;
+select rational_intermediate('44320/39365', '77200/12184');
+select rational_intermediate('44320/39365', '77200/12184')
+  between '44320/39365'::rational and '77200/12184';
+-- unbounded upper limit produces least greater integer
+select rational_intermediate('1/3', NULL);
+select rational_intermediate('3/2', NULL);
+-- though not the other direction
+select rational_intermediate(NULL, '15/16');
Reply | Threaded
Open this post in threaded view
|

Re: POC: rational number type (fractions)

legrand legrand
Hello,
It seems you are not the first to be interested in such feature.

There was a similar extension used in "incremental view maintenance"
testing:
https://github.com/nuko-yokohama/pg_fraction

didn't tryed it myself.

Regards
PAscal



--
Sent from: https://www.postgresql-archive.org/PostgreSQL-hackers-f1928748.html


Reply | Threaded
Open this post in threaded view
|

Re: POC: rational number type (fractions)

Jeff Davis-8
In reply to this post by Joe Nelson
On Fri, 2020-02-07 at 22:25 -0600, Joe Nelson wrote:
> Hi hackers, attached is a proof of concept patch adding a new base
> type
> called "rational" to represent fractions.

Hi!

> The primary motivation was as a column type to support user-defined
> ordering of rows (with the ability to dynamically rearrange rows).
> The
> postgres wiki has a page [0] about this using pairs of integers to
> represent fractions, but it's not particularly elegant.

Sounds good.

> I wrote about options for implementing user-defined order in an
> article
> [1] and ended up creating a postgres extension, pg_rational [2], to
> provide the new type. People have been using the extension, but told
> me
> they wished they could use it on hosted platforms like Amazon RDS
> which
> have a limited set of whitelisted extensions. Thus I'm submitting
> this
> patch to discuss getting the feature in core postgres.

The decision between an extension and a core type is a tricky one. To
put an extension in core, usually it's good to show either that it
satisfies something in the SQL standard, or that there is some specific
technical advantage (like integration with the syntax or the type
system).

Integrating it in core just to make it easier to use is a double-edge
sword. It does make it easier in some environments; but it also removes
pressure to make those environments offer better support for the
extension ecosystem, ultimately weakening extensions overall.

In this case I believe it could be a candidate for in-core, but it's
borderline. The reasons it makes sense to me are:

1. It seems that there's "only one way to do it". It would be good to
validate that this really covers most of the use cases of rational
numbers, but if so, that makes it a better candidate for building it
into core. It would also be good to compare against other
implementations (perhaps in normal programming languages) to see if
there is anything interesting.

2. I don't expect this will be much of a maintenance burden.

Keep in mind that if you do want this to be in core, the data format
has to be very stable to maintain pg_upgrade compatibility.


Patch comments:

* Please include docs.

* I'm worried about the use of int32. Does that cover all of the
reasonable use cases of rational?

* Shouldn't:

    /*
     * x = coalesce(lo, arg[0]) y = coalesce(hi, arg[1])
     */

  be:

    /*
     * x = coalesce(arg[0], lo) y = coalesce(arg[1], lo)
     */

* More generally, what's the philosophy regarding NULL and rational?
Why are NULL arguments returning non-NULL answers?

* Is rational_intermediate() well-defined, or can it just choose any
rational between the two arguments?

* Can you discuss how cross-type comparisons and conversions should be
handled (e.g. int8, numeric, float8)?

Regards,
        Jeff Davis




Reply | Threaded
Open this post in threaded view
|

Re: POC: rational number type (fractions)

Joe Nelson
Jeff Davis wrote:
> The decision between an extension and a core type is a tricky one. To
> put an extension in core, usually it's good to show either that it
> satisfies something in the SQL standard, or that there is some
> specific technical advantage (like integration with the syntax or the
> type system).

I don't see any references to "rational" in the SQL standard (fifth ed,
2016) and the only reference to "fraction" is for fractions of a second
in datetime. Doesn't look like SQL includes rational numbers.

Also I don't believe I'm getting extra abilities by putting this in core vs
using an extension. Perhaps there's a syntax change that would make rationals
more pleasant to deal with than how they in this patch, but I haven't imagined
what it would be, and it's not backed by a standard.

> Integrating it in core just to make it easier to use is a double-edge
> sword. It does make it easier in some environments; but it also
> removes pressure to make those environments offer better support for
> the extension ecosystem, ultimately weakening extensions overall.

Makes sense. We petitioned RDS to allow the pg_rational extension, [0]
but they didn't respond. Not sure how that process is supposed to work.

0: https://github.com/begriffs/pg_rational/issues/7

> In this case I believe it could be a candidate for in-core, but it's
> borderline. The reasons it makes sense to me are:
>
> 1. It seems that there's "only one way to do it".

There may be more than one way to do it actually. For instance the choice
between a fixed size type with limits on the fractions it can represent, vs one
that can grow to hold any fraction. I chose the first option, to make the type
the same size as float8. My reasoning was that there was would be no space
overhead for choosing rational over float.

Also there's the choice of whether to always store fractions in normal
form (lowest terms). This patch allows fractions to be in non-normal
form after arithmetic, and only normalizes as needed when an arithmetic
operation would overflow. I wanted to cut down on how many times gcd is
called. However this choice means that hash indices have to normalize
because they hash the bit pattern, while btree indices can compare
rationals without regard to normal form.

This patch represents each rational as a separate numerator and denominator. I
did some research today to see if there are any another ways, and looks like
there's a technique from the 70s called "quote notation." [1] It appears that
quote notation makes addition and subtraction faster, but that the operations
can less predictable performance in the worst case scenarios with doing
arbitrary precision.  So there's more than one way to do it.

1: https://en.wikipedia.org/wiki/Quote_notation

> 2. I don't expect this will be much of a maintenance burden.

True, rational numbers aren't going to change anytime soon.

> Keep in mind that if you do want this to be in core, the data format
> has to be very stable to maintain pg_upgrade compatibility.

The format is currently [int32 numerator][int32 denominator] packed together,
where the denominator is made positive whenever possible (not possible when
it's -INT_MAX).  The quote notation alternative would arrange things very
differently.

> Patch comments:
>
> * Please include docs.

Of course, if we determine the patch is desirable. The included tests
should help demonstrate how it works for the purposes of review.

> * I'm worried about the use of int32. Does that cover all of the
> reasonable use cases of rational?

I could imagine having two types, a rational8 for the current
implementation, and an arbitrary precision rational. Perhaps...

> * what's the philosophy regarding NULL and rational?  Why are NULL
> arguments returning non-NULL answers?

The rational_intermediate(x, y) function picks a fraction between x and
y, and NULL was meant as a signal that one of the sides is unbounded.
So rational_intermediate(x, NULL) means find a fraction larger than x,
and rational_intermediate(NULL, y) means find one smaller than y.

The use case is a query for a spot "immediately after position 2:"

SELECT rational_intermediate(2, min(pos))
  FROM todos
 WHERE pos > 2;

If there are already todos positioned after 2 then it'll find a spot
between 2 and the min. However if there are no todos after 2 then min()
will return NULL and we'll simply find a position *somewhere* after 2.

> * Is rational_intermediate() well-defined, or can it just choose any
> rational between the two arguments?

It chooses the mediant [2] of x and y in lowest terms by walking a
Stern-Brocot tree. I found that this keeps the terms of the fraction
much smaller than taking the average of x and y. This was an advantage
over calculating with floats because I don't know how to take the
mediant of floats, and repeatedly taking the average of floats eats up
precision pretty quickly.

2: https://en.wikipedia.org/wiki/Mediant_(mathematics)

> * Can you discuss how cross-type comparisons and conversions should be
> handled (e.g. int8, numeric, float8)?

Good point, I don't have tests for that. Would implicit casts do the
trick? So '1/2'::rational < 1 would cast 1 to '1/1' and compare? I have
currently included these casts: integer -> rational, float8 <->
rational. Don't have one for numeric yet.

> Regards,

Thank you for taking the time to raise those questions.

--
Joe Nelson      https://begriffs.com


Reply | Threaded
Open this post in threaded view
|

Re: POC: rational number type (fractions)

Joe Nelson
Joe Nelson wrote:
> where the denominator is made positive whenever possible (not possible
> when it's -INT_MAX).

(I meant INT_MIN rather than -INT_MAX.)

Another more-than-one-way-to-do-it task is converting a float to a
fraction.  I translated John Kennedy's method [0] to C, but Github user
adegert sent an alternative [1] that matches the way the CPython
implementation works.

0: https://begriffs.com/pdf/dec2frac.pdf 
1: https://github.com/begriffs/pg_rational/pull/13


Reply | Threaded
Open this post in threaded view
|

Re: POC: rational number type (fractions)

Jeff Davis-8
In reply to this post by Joe Nelson
On Fri, 2020-02-21 at 19:24 -0600, Joe Nelson wrote:
> I could imagine having two types, a rational8 for the current
> implementation, and an arbitrary precision rational. Perhaps...

The main thing I'm trying to avoid is a situation where we introduce
"rational", but it only meets a subset of the use cases, and then we
end up with another extension. I'm not saying that's happening here,
but it would be good to compare against other implementations (for
instance from normal programming languages) to see if we are missing
some use cases.

If you are using rational to track positions of items in an online to-
do list, and the user keeps swapping or rotating items in the list, is
that going to lead to overflow/underflow?

> > * what's the philosophy regarding NULL and rational?  Why are NULL
> > arguments returning non-NULL answers?
>
> The rational_intermediate(x, y) function picks a fraction between x
> and
> y, and NULL was meant as a signal that one of the sides is unbounded.
> So rational_intermediate(x, NULL) means find a fraction larger than
> x,
> and rational_intermediate(NULL, y) means find one smaller than y.

Would "x+1" or "y-1" also work for that?

I am a little worried about introducing a function that is not well-
defined. Would a midpoint function serve the purpose?

> If there are already todos positioned after 2 then it'll find a spot
> between 2 and the min. However if there are no todos after 2 then
> min()
> will return NULL and we'll simply find a position *somewhere* after
> 2.

Interesting. That could probably be solved with a COALESCE() around the
MIN(), but your version is a little cleaner.

> > * Is rational_intermediate() well-defined, or can it just choose
> > any
> > rational between the two arguments?
>
> It chooses the mediant [2]

Maybe we should define it as the mediant then?

> currently included these casts: integer -> rational, float8 <->
> rational. Don't have one for numeric yet.

A cast to numeric would make sense. What will you do in cases where the
domains don't quite match, are you rounding or truncating?

Regards,
        Jeff Davis




Reply | Threaded
Open this post in threaded view
|

Re: POC: rational number type (fractions)

David Steele
In reply to this post by Joe Nelson
Hi Joe,

On 2/7/20 11:25 PM, Joe Nelson wrote:
> Hi hackers, attached is a proof of concept patch adding a new base type
> called "rational" to represent fractions.

I have set the target version for this patch to PG14 because it is POC
and this is the first CF it has appeared in.

Regards,
--
-David
[hidden email]


Reply | Threaded
Open this post in threaded view
|

Re: POC: rational number type (fractions)

Peter Eisentraut-6
In reply to this post by Joe Nelson
On 2020-02-08 05:25, Joe Nelson wrote:
> Hi hackers, attached is a proof of concept patch adding a new base type
> called "rational" to represent fractions. It includes arithmetic,
> simplification, conversion to/from float, finding intermediates with a
> stern-brocot tree, custom aggregates, and btree/hash indices.

The numeric type already stores rational numbers.  How is this
different?  What's the use?

--
Peter Eisentraut              http://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services


Reply | Threaded
Open this post in threaded view
|

Re: POC: rational number type (fractions)

Chapman Flack
On 05/18/20 17:33, Peter Eisentraut wrote:
> The numeric type already stores rational numbers.  How is this different?
> What's the use?

Seems like numeric is a base-10000 representation. Will work ok for
a rational whose denominator factors into 2s and 5s.

Won't ever quite represent, say, 1/3, no matter how big you let it get.

Regards,
-Chap


Reply | Threaded
Open this post in threaded view
|

Re: POC: rational number type (fractions)

Tom Lane-2
Chapman Flack <[hidden email]> writes:
> On 05/18/20 17:33, Peter Eisentraut wrote:
>> The numeric type already stores rational numbers.  How is this different?
>> What's the use?

> Won't ever quite represent, say, 1/3, no matter how big you let it get.

There surely are use-cases for true rational arithmetic, but I'm
dubious that it belongs in core Postgres.  I don't think that enough
of our users would want it to justify expending core-project maintenance
effort on it.  So I'd be happier to see this as an out-of-core extension.

(That'd also ease dealing with the prospect of having more than one
variant, as was mentioned upthread.)

                        regards, tom lane


Reply | Threaded
Open this post in threaded view
|

Re: POC: rational number type (fractions)

Robert Haas
On Mon, May 18, 2020 at 6:15 PM Tom Lane <[hidden email]> wrote:
> There surely are use-cases for true rational arithmetic, but I'm
> dubious that it belongs in core Postgres.  I don't think that enough
> of our users would want it to justify expending core-project maintenance
> effort on it.  So I'd be happier to see this as an out-of-core extension.

As is often the case, I'm a little more positive about including this
than Tom, but as is also often the case, I'm somewhat cautious, too.
On the one hand, I think it would be cool to have and people would
like it. But, On the other hand, I also think we'd only want it if
we're convinced that it's a really good implementation and that
there's not a competing design which is better, or even equally good.
Those things don't seem too clear at this point, so I hope Jeff and
Joe keep chatting about it ... and maybe some other people who are
knowledgeable about this will chime in, too.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company


Reply | Threaded
Open this post in threaded view
|

Re: POC: rational number type (fractions)

Noah Misch-2
On Thu, May 21, 2020 at 01:40:10PM -0400, Robert Haas wrote:

> On Mon, May 18, 2020 at 6:15 PM Tom Lane <[hidden email]> wrote:
> > There surely are use-cases for true rational arithmetic, but I'm
> > dubious that it belongs in core Postgres.  I don't think that enough
> > of our users would want it to justify expending core-project maintenance
> > effort on it.  So I'd be happier to see this as an out-of-core extension.
>
> As is often the case, I'm a little more positive about including this
> than Tom, but as is also often the case, I'm somewhat cautious, too.
> On the one hand, I think it would be cool to have and people would
> like it. But, On the other hand, I also think we'd only want it if
> we're convinced that it's a really good implementation and that
> there's not a competing design which is better, or even equally good.

I vote for keeping it out of core, mostly because writing rational numeric
code is so different from writing DBMS core code.  (Many of our existing
types, like numeric and the geometric types, have the same problem.  Let's not
invite more of that.)  The optimal reviewer pools won't have much overlap, so
patches may sit awhile and/or settle for a cursory review.

More language standard libraries provide "numeric"-style big decimals[1] than
provide big rationals[2], suggesting we're in good company.

[1] https://en.wikipedia.org/wiki/List_of_arbitrary-precision_arithmetic_software#Languages
[2] https://en.wikipedia.org/wiki/Rational_data_type#Language_support