Обсуждение: [GENERAL] Unexpected interval comparison
I came across an unexpected comparison (tested on PostgreSQL 9.4 and 9.6) for intervals with a large difference in magnitude.
I narrowed it down to this example, where comparisons with this range give the wrong value:
postgres=# SELECT
'1 year'::interval > '3854933 years'::interval,
'1 year'::interval > '3854934 years'::interval,
'1 year'::interval > '32618664 years'::interval,
'1 year'::interval > '32618665 years'::interval;
?column? | ?column? | ?column? | ?column?
----------+----------+----------+----------
f | t | t | f
(1 row)
Is this a bug? Should I not be comparing intervals? It would seem the interval type has enough information to give the correct answer here.
Regards,
Frazer McLean
Frazer McLean <frazer@frazermclean.co.uk> writes:
> I came across an unexpected comparison (tested on PostgreSQL 9.4 and
> 9.6) for intervals with a large difference in magnitude.
> '1 year'::interval > '32618665 years'::interval;
> Is this a bug?
It looks like the problem is overflow of the result of interval_cmp_value,
because it's trying to compute
=# select '32618665'::int8 * 30 * 86400 * 1000000;
ERROR: bigint out of range
It's not immediately obvious how to avoid that while preserving the same
comparison semantics :-(
regards, tom lane
On 03/21/2017 07:42 AM, Tom Lane wrote: > Frazer McLean <frazer@frazermclean.co.uk> writes: >> I came across an unexpected comparison (tested on PostgreSQL 9.4 and >> 9.6) for intervals with a large difference in magnitude. > >> '1 year'::interval > '32618665 years'::interval; > >> Is this a bug? > > It looks like the problem is overflow of the result of interval_cmp_value, > because it's trying to compute > > =# select '32618665'::int8 * 30 * 86400 * 1000000; > ERROR: bigint out of range > > It's not immediately obvious how to avoid that while preserving the same > comparison semantics :-( Not sure if it helps but this works: test=# select extract(epoch from '1 year'::interval) > extract(epoch from '32618665 years'::interval); ?column? ---------- f > > regards, tom lane > > -- Adrian Klaver adrian.klaver@aklaver.com
Hello,
At Tue, 21 Mar 2017 07:52:25 -0700, Adrian Klaver <adrian.klaver@aklaver.com> wrote in
<375c9e5a-960f-942c-913f-55632a1f0a90@aklaver.com>
> On 03/21/2017 07:42 AM, Tom Lane wrote:
> > Frazer McLean <frazer@frazermclean.co.uk> writes:
> >> I came across an unexpected comparison (tested on PostgreSQL 9.4 and
> >> 9.6) for intervals with a large difference in magnitude.
> >
> >> '1 year'::interval > '32618665 years'::interval;
> >
> >> Is this a bug?
> >
> > It looks like the problem is overflow of the result of
> > interval_cmp_value,
> > because it's trying to compute
> >
> > =# select '32618665'::int8 * 30 * 86400 * 1000000;
> > ERROR: bigint out of range
> >
> > It's not immediately obvious how to avoid that while preserving the
> > same
> > comparison semantics :-(
This is an apparent bug of interval comparison. During comparison
interval is converted into int64 in milliseconds but it overflows
in the case.
Detecting the overflow during the conversion can fix it and
preserving the semantics (except value range). The current code
tells a lie anyway for the cases but I'm not sure limting the
range of value is acceptable or not.
| =# select '106751990 days 24:59:59'::interval;
| interval
| -------------------------
| 106751990 days 24:59:59
| =# select '106751990 days 24:59:59'::interval > '1 year'::interval;
| ERROR: interval out of range during comparison
If this is not acceptable, some refactoring would be required.
> Not sure if it helps but this works:
>
> test=# select extract(epoch from '1 year'::interval) > extract(epoch
> from '32618665 years'::interval);
> ?column?
> ----------
> f
It calculates in seconds. So it is useful if subseconds are not
significant. But extract also silently overflows during
converting the same interval to usecs. This seems to need the
same amendment.
> =# select extract(usec from '32618665 years'::interval);
> date_part
> -----------
> 0
regards,
--
Kyotaro Horiguchi
NTT Open Source Software Center
diff --git a/src/backend/utils/adt/timestamp.c b/src/backend/utils/adt/timestamp.c
index 4be1999..f77cfcc 100644
--- a/src/backend/utils/adt/timestamp.c
+++ b/src/backend/utils/adt/timestamp.c
@@ -2293,10 +2293,23 @@ static inline TimeOffset
interval_cmp_value(const Interval *interval)
{
TimeOffset span;
+ TimeOffset timedayfraction;
+ TimeOffset timedays;
- span = interval->time;
- span += interval->month * INT64CONST(30) * USECS_PER_DAY;
- span += interval->day * INT64CONST(24) * USECS_PER_HOUR;
+ timedays = ((int64)interval->time) / USECS_PER_DAY;
+ timedayfraction = interval->time - timedays * USECS_PER_DAY;
+
+ /* calculate span in days. this cannot overflow */
+ span = timedays;
+ span += interval->month * INT64CONST(30);
+ span += interval->day;
+
+ /* overflow check */
+ if (span > INT64CONST(0x7fffffffffffffff) / USECS_PER_DAY - 1)
+ ereport(ERROR,
+ (errcode(ERRCODE_DATETIME_VALUE_OUT_OF_RANGE),
+ errmsg ("interval out of range during comparison")));
+ span = span * USECS_PER_DAY + timedayfraction;
return span;
}
@@ -2304,6 +2317,7 @@ interval_cmp_value(const Interval *interval)
static int
interval_cmp_internal(Interval *interval1, Interval *interval2)
{
+
TimeOffset span1 = interval_cmp_value(interval1);
TimeOffset span2 = interval_cmp_value(interval2);
Kyotaro HORIGUCHI <horiguchi.kyotaro@lab.ntt.co.jp> writes:
> At Tue, 21 Mar 2017 07:52:25 -0700, Adrian Klaver <adrian.klaver@aklaver.com> wrote in
<375c9e5a-960f-942c-913f-55632a1f0a90@aklaver.com>
>> On 03/21/2017 07:42 AM, Tom Lane wrote:
>>> It looks like the problem is overflow of the result of interval_cmp_value,
>>> because it's trying to compute
>>> =# select '32618665'::int8 * 30 * 86400 * 1000000;
>>> ERROR: bigint out of range
>>> It's not immediately obvious how to avoid that while preserving the
>>> same comparison semantics :-(
> Detecting the overflow during the conversion can fix it and
> preserving the semantics (except value range). The current code
> tells a lie anyway for the cases but I'm not sure limting the
> range of value is acceptable or not.
I don't think it is. It'd cause failures in attempting to enter
very large interval values into btree indexes, for instance.
A possible solution is to manually work in wider-than-64-bit
arithmetic, that is compute the comparison values div and mod
some pretty-large number and then compare the two halves.
I seem to recall that we did something similar in a few cases
years ago, before we were willing to assume that every machine
had 64-bit integer support.
Of course, for machines having int128, you could just use that
type directly. I'm not sure how widespread that support is
nowadays. Maybe a 95%-good-enough solution is to use int128
if available and otherwise throw errors for intervals exceeding
64 bits.
regards, tom lane
At Thu, 30 Mar 2017 10:57:19 -0400, Tom Lane <tgl@sss.pgh.pa.us> wrote in <2087.1490885839@sss.pgh.pa.us>
> Kyotaro HORIGUCHI <horiguchi.kyotaro@lab.ntt.co.jp> writes:
> > At Tue, 21 Mar 2017 07:52:25 -0700, Adrian Klaver <adrian.klaver@aklaver.com> wrote in
<375c9e5a-960f-942c-913f-55632a1f0a90@aklaver.com>
> >> On 03/21/2017 07:42 AM, Tom Lane wrote:
> >>> It looks like the problem is overflow of the result of interval_cmp_value,
> >>> because it's trying to compute
> >>> =# select '32618665'::int8 * 30 * 86400 * 1000000;
> >>> ERROR: bigint out of range
> >>> It's not immediately obvious how to avoid that while preserving the
> >>> same comparison semantics :-(
>
> > Detecting the overflow during the conversion can fix it and
> > preserving the semantics (except value range). The current code
> > tells a lie anyway for the cases but I'm not sure limting the
> > range of value is acceptable or not.
>
> I don't think it is. It'd cause failures in attempting to enter
> very large interval values into btree indexes, for instance.
As for btree on intervals, it uses the same conversion function
with bare comparisons so it works for btree, too. The following
correctly fails with the patch.
| =# insert into ti values ('32618665 years'::interval);
| ERROR: interval out of range during comparison
But, strange behavior is seen on creating an index.
| =# insert into ti values ('32618665 years'::interval);
| INSERT 0 1
| postgres=# create index on ti using btree (i);
| ERROR: interval out of range during comparison
So, restricting the domain on reading (interval_in or such) might
be better. Since we don't have big-bigint, extract(usec) will
overflow for certain range of interval values anyway. Or allow
returning them in numeric?
If we don't mind such inconsistency, just using wider integer
will useful.
> A possible solution is to manually work in wider-than-64-bit
> arithmetic, that is compute the comparison values div and mod
> some pretty-large number and then compare the two halves.
> I seem to recall that we did something similar in a few cases
> years ago, before we were willing to assume that every machine
> had 64-bit integer support.
>
> Of course, for machines having int128, you could just use that
> type directly. I'm not sure how widespread that support is
> nowadays. Maybe a 95%-good-enough solution is to use int128
> if available and otherwise throw errors for intervals exceeding
> 64 bits.
int128 is seen in numeric.c. It is doable in the same manner. In
that case it will be a bit slower on the platforms without
int128.
By the way is it right that we don't assume this as a bug-fix
which should be done in the Pg10 dev cycle, but an improvement
for 11?
regards,
--
Kyotaro Horiguchi
NTT Open Source Software Center
Kyotaro HORIGUCHI <horiguchi.kyotaro@lab.ntt.co.jp> writes:
> At Thu, 30 Mar 2017 10:57:19 -0400, Tom Lane <tgl@sss.pgh.pa.us> wrote in <2087.1490885839@sss.pgh.pa.us>
>> A possible solution is to manually work in wider-than-64-bit
>> arithmetic, that is compute the comparison values div and mod
>> some pretty-large number and then compare the two halves.
>> I seem to recall that we did something similar in a few cases
>> years ago, before we were willing to assume that every machine
>> had 64-bit integer support.
>>
>> Of course, for machines having int128, you could just use that
>> type directly. I'm not sure how widespread that support is
>> nowadays. Maybe a 95%-good-enough solution is to use int128
>> if available and otherwise throw errors for intervals exceeding
>> 64 bits.
> int128 is seen in numeric.c. It is doable in the same manner. In
> that case it will be a bit slower on the platforms without
> int128.
> By the way is it right that we don't assume this as a bug-fix
> which should be done in the Pg10 dev cycle, but an improvement
> for 11?
Well, it seems like a bug to me. We might conclude that the fix
is too risky to back-patch, but it's hard to make that decision
before having a patch in hand to evaluate.
regards, tom lane
Hmm. It took a bit longer time than expected. At Fri, 31 Mar 2017 13:29:24 -0400, Tom Lane <tgl@sss.pgh.pa.us> wrote in <10353.1490981364@sss.pgh.pa.us> > Kyotaro HORIGUCHI <horiguchi.kyotaro@lab.ntt.co.jp> writes: > > int128 is seen in numeric.c. It is doable in the same manner. In > > that case it will be a bit slower on the platforms without > > int128. > > > By the way is it right that we don't assume this as a bug-fix > > which should be done in the Pg10 dev cycle, but an improvement > > for 11? > > Well, it seems like a bug to me. We might conclude that the fix > is too risky to back-patch, but it's hard to make that decision > before having a patch in hand to evaluate. Ok, the attached patch changes the result type of interval_cmp_value from TimeOffset(=int64) to new 128 bit LinearInterval. The value is hidden under the functions interval_eq/ge.../cmp and all other stuff seems to use the functions. For platforms without 128 bit support, int64 * 2 version of interval_cmp_value is used. I added separate test for the near-overflow values since just adding such values into INTERVAL_TABLE resuted in a mess. (I ran 64-bit version by commenting-out the definition of PG_INT128_TYPE in pg_config.h). The attached patch is that. regards, -- Kyotaro Horiguchi NTT Open Source Software Center
Kyotaro HORIGUCHI <horiguchi.kyotaro@lab.ntt.co.jp> writes:
> Ok, the attached patch changes the result type of
> interval_cmp_value from TimeOffset(=int64) to new 128 bit
> LinearInterval. The value is hidden under the functions
> interval_eq/ge.../cmp and all other stuff seems to use the
> functions.
Looking at this now ... why isn't the INT64_AU32 macro just
#define INT64_AU32(i64) ((i64) >> 32)
? The business with subtracting and re-adding 1 seems unnecessary, and it
also creates a risk of overflow with the minimum possible int64 value.
regards, tom lane
Thank you for the comment. At Mon, 03 Apr 2017 11:35:25 -0400, Tom Lane <tgl@sss.pgh.pa.us> wrote in <23053.1491233725@sss.pgh.pa.us> > Kyotaro HORIGUCHI <horiguchi.kyotaro@lab.ntt.co.jp> writes: > > Ok, the attached patch changes the result type of > > interval_cmp_value from TimeOffset(=int64) to new 128 bit > > LinearInterval. The value is hidden under the functions > > interval_eq/ge.../cmp and all other stuff seems to use the > > functions. > > Looking at this now ... why isn't the INT64_AU32 macro just > > #define INT64_AU32(i64) ((i64) >> 32) > > ? The business with subtracting and re-adding 1 seems unnecessary, and it > also creates a risk of overflow with the minimum possible int64 value. It is equivalent to "i64 / (1<<32)" except for -INT64_MAX. INT64_AU32 gives the value for the first term in the following polynomial. (int64)INT64_AU32(i64) * (2^32) + (int64)INT64_AL32(i64) = i64 The previous expression intended to avoid decimal arithmetic, but gcc optimizes the simple division better (using cmovns-add-sar) than the current INT64_AU32 (jmp-sar) so I changed it. This doesn't suffer overflow. -#define INT64_AU32(i64) (((i64) < 0 ? (((i64) - 1) >> 32) + 1: ((i64) >> 32))) +#define INT64_AU32(i64) ((i64) / (1LL<<32)) In summation of terms in 128bit multiplication expression, I noticed that the value of the second term's lower 32bit loses MSB for certain cases. I changed LINEARINTERVAL_ADD_INT64 to accept the MSB (as the 65th bit) separately. The first attached is the revised patch and the second is temporary sanity check code for non-128bit environment code. (but works only on 128 bit environment) regards, -- Kyotaro Horiguchi NTT Open Source Software Center
On Tue, Apr 4, 2017 at 4:15 AM, Kyotaro HORIGUCHI <horiguchi.kyotaro@lab.ntt.co.jp> wrote:
How does this affect non-gcc compilers? Specifically I am interested in the llvm based compilers in FreeBSD. Or is this within a gcc-specific section of the header?
The previous expression intended to avoid decimal arithmetic, but
gcc optimizes the simple division better (using cmovns-add-sar)
than the current INT64_AU32 (jmp-sar) so I changed it. This
doesn't suffer overflow.
How does this affect non-gcc compilers? Specifically I am interested in the llvm based compilers in FreeBSD. Or is this within a gcc-specific section of the header?
Kyotaro HORIGUCHI <horiguchi.kyotaro@lab.ntt.co.jp> writes:
> The first attached is the revised patch and the second is
> temporary sanity check code for non-128bit environment code. (but
> works only on 128 bit environment)
This seemed to me to be probably even less correct, so I extracted
the addition and multiplication logic into a standalone test program
(attached), which compares the result of a multiplication to that
of native int128 arithmetic. I changed the order of the LinearInterval
fields to be LS-first so that I could overlay them onto an int128
result (on a little-endian machine); this is just for testing purposes
not something we must do in the finished code. I soon found cases
where it indeed fails, eg
$ ./a.out 0x7ffffffff 0x7ffffffff
7FFFFFFFF * 7FFFFFFFF
result = 62 18446744004990074881
result = 3E FFFFFFF000000001
MISMATCH!
result = 63 18446744004990074881
result = 3F FFFFFFF000000001
After fooling with it for awhile, I decided that the cause of the
problems was basically not thinking carefully about the lower half
of the value being unsigned: that affects when to do carries in
the addition macro, and we also have to be careful about whether
or not to sign-extend the partial product terms. The second
attached file is a version that I can't break anymore, though I'm
not quite sure it's bug-free.
regards, tom lane
#include "postgres.h"
/*
* LinearInterval's alternative defeinition for the environments without
* int128 arithmetics. See interval_cmp_value for datails.
*/
typedef struct
{
uint64 lo; /* holds the lower 64 bits without sign */
int64 hi; /* holds significant 64 bits including a sign bit */
} LinearInterval;
typedef union LI
{
int128 i128;
LinearInterval li;
} LI;
/*
* arithmetic 32 bit extraction from int64
*
* INT64_AU32 extracts significant 32 bit of int64 as a int64, and INT64_AL32
* extracts non-siginificant 32 bit as a int64. Both macros extends sign bits
* according to the given value. The values of these macros and the parameter
* value are in the following relationship.
*
* i64 = (int64)INT64_AU32(i64) * (2^32) + (int64)INT64_AL32(i64)
*/
#define INT64_AU32(i64) ((i64) / (1LL<<32))
#define INT64_AL32(i64) (((i64) & 0xffffffff) | ((i64) < 0 ? 0xffffffff00000000 : 0))
/*
* Adds signed 65 bit integer into LinearInterval variable. If s is not zero,
* its sign is used as v's sign.
*/
#define LINEARINTERVAL_ADD_INT65(li, v, s) \
{ \
uint64 t = (uint64)(v); \
uint64 p = (li).lo; \
(li).lo += t; \
if (s < 0 || (s == 0 && v < 0)) \
(li).hi --; \
if ((li).lo < p) \
(li).hi ++; \
}
static inline LinearInterval
interval_times(int64 x, int64 y)
{
LinearInterval span = {0, 0};
int64 tmp;
/*
* perform 128 bit multiplication using 64 bit variables.
*
* x * y = ((x.hi << 32) + x.lo) * (((y.hi << 32) + y.lo)
* = (x.hi * y.hi) << 64 +
* ((x.hi * y.lo) + (x.lo * y.hi)) << 32 +
* x.lo * y.lo
*/
/* We don't bother calculation results in zero */
if (x != 0 && y != 0)
{
int64 x_u32 = INT64_AU32(x);
int64 x_l32 = INT64_AL32(x);
/* the first term */
span.hi = x_u32 * (y >> 32);
/* the second term */
tmp = x_l32 * (y >> 32)
+ x_u32 * (y & 0xffffffff);
span.hi += INT64_AU32(tmp);
/* this shift may push out MSB. supply it explicitly */
LINEARINTERVAL_ADD_INT65(span, INT64_AL32(tmp) << 32, tmp);
/* the third term */
tmp = x_l32 * (y & 0xffffffff);
LINEARINTERVAL_ADD_INT65(span, tmp, 0);
}
return span;
}
int
main(int argc, char **argv)
{
int64 x = strtol(argv[1], NULL, 0);
int64 y = strtol(argv[2], NULL, 0);
LI li;
LI li2;
printf("%lX * %lX\n", x, y);
li.li = interval_times(x, y);
printf("result = %ld %lu\n", li.li.hi, li.li.lo);
printf("result = %lX %lX\n", li.li.hi, li.li.lo);
li2.i128 = (int128) x * (int128) y;
if (li.li.hi != li2.li.hi || li.li.lo != li2.li.lo)
{
printf("MISMATCH!\n");
printf("result = %ld %lu\n", li2.li.hi, li2.li.lo);
printf("result = %lX %lX\n", li2.li.hi, li2.li.lo);
}
return 0;
}
#include "postgres.h"
/*
* LinearInterval's alternative defeinition for the environments without
* int128 arithmetics. See interval_cmp_value for datails.
*/
typedef struct
{
uint64 lo; /* holds the lower 64 bits without sign */
int64 hi; /* holds significant 64 bits including a sign
* bit */
} LinearInterval;
typedef union LI
{
int128 i128;
LinearInterval li;
} LI;
/*
* INT64_AU32 extracts the most significant 32 bits of int64 as int64, while
* INT64_AL32 extracts the least significant 32 bits as uint64.
*/
#define INT64_AU32(i64) ((i64) >> 32)
#define INT64_AL32(i64) ((i64) & UINT64CONST(0xFFFFFFFF))
/*
* Add an unsigned int64 value into a LinearInterval variable.
* First add the value to the .lo part, then check to see if a carry
* needs to be propagated into the .hi part. A carry is needed if both
* inputs have high bits set, or if just one input has high bit set
* but the new .lo part doesn't. Remember that .lo part is unsigned;
* we cast to signed here just as a cheap way to check the high bit.
*/
#define LINEARINTERVAL_ADD_UINT64(li, v) \
do { \
uint64 t = (uint64) (v); \
uint64 oldlo = (li).lo; \
(li).lo += t; \
if (((int64) t < 0 && (int64) oldlo < 0) || \
(((int64) t < 0 || (int64) oldlo < 0) && (int64) (li).lo >= 0)) \
(li).hi++; \
} while (0)
static inline LinearInterval
interval_times(int64 x, int64 y)
{
LinearInterval span = {0, 0};
/*----------
* Form the 128-bit product x * y using 64-bit arithmetic.
* Considering each 64-bit input as having 32-bit high and low parts,
* we can compute
*
* x * y = ((x.hi << 32) + x.lo) * (((y.hi << 32) + y.lo)
* = (x.hi * y.hi) << 64 +
* (x.hi * y.lo) << 32 +
* (x.lo * y.hi) << 32 +
* x.lo * y.lo
*
* Each individual product is of 32-bit terms so it won't overflow when
* computed in 64-bit arithmetic. Then we just have to shift it to the
* correct position while adding into the 128-bit result. We must also
* keep in mind that the "lo" parts must be treated as unsigned.
*----------
*/
/* INT64_AU32 must use arithmetic right shift */
StaticAssertStmt(((int64) -1 >> 1) == (int64) -1,
"arithmetic right shift is needed");
/* No need to work hard if product must be zero */
if (x != 0 && y != 0)
{
int64 x_u32 = INT64_AU32(x);
uint64 x_l32 = INT64_AL32(x);
int64 y_u32 = INT64_AU32(y);
uint64 y_l32 = INT64_AL32(y);
int64 tmp;
/* the first term */
span.hi = x_u32 * y_u32;
printf("first term = %016lX\n", span.hi);
/* the second term: sign-extend it only if x is negative */
tmp = x_u32 * y_l32;
printf("second term = %016lX\n", tmp);
if (x < 0)
span.hi += INT64_AU32(tmp);
else
span.hi += ((uint64) tmp) >> 32;
LINEARINTERVAL_ADD_UINT64(span, ((uint64) INT64_AL32(tmp)) << 32);
printf("partial sum = %016lX%016lX\n", span.hi, span.lo);
/* the third term: sign-extend it only if y is negative */
tmp = x_l32 * y_u32;
printf("third term = %016lX\n", tmp);
if (y < 0)
span.hi += INT64_AU32(tmp);
else
span.hi += ((uint64) tmp) >> 32;
LINEARINTERVAL_ADD_UINT64(span, ((uint64) INT64_AL32(tmp)) << 32);
printf("partial sum = %016lX%016lX\n", span.hi, span.lo);
/* the fourth term: always unsigned */
printf("fourth term = %016lX\n", x_l32 * y_l32);
LINEARINTERVAL_ADD_UINT64(span, x_l32 * y_l32);
}
return span;
}
int
main(int argc, char **argv)
{
int64 x = strtol(argv[1], NULL, 0);
int64 y = strtol(argv[2], NULL, 0);
LI li;
LI li2;
printf("%lX * %lX\n", x, y);
li.li = interval_times(x, y);
printf("result = %016lX%016lX\n", li.li.hi, li.li.lo);
printf("result = %ld %lu\n", li.li.hi, li.li.lo);
li2.i128 = (int128) x * (int128) y;
if (li.li.hi != li2.li.hi || li.li.lo != li2.li.lo)
{
printf("MISMATCH!\n");
printf("result = %016lX%016lX\n", li2.li.hi, li2.li.lo);
printf("result = %ld %lu\n", li2.li.hi, li2.li.lo);
}
return 0;
}
Mmm. It's shameful.
At Tue, 04 Apr 2017 18:06:38 -0400, Tom Lane <tgl@sss.pgh.pa.us> wrote in <5084.1491343598@sss.pgh.pa.us>
> Kyotaro HORIGUCHI <horiguchi.kyotaro@lab.ntt.co.jp> writes:
> > The first attached is the revised patch and the second is
> > temporary sanity check code for non-128bit environment code. (but
> > works only on 128 bit environment)
>
> This seemed to me to be probably even less correct, so I extracted
> the addition and multiplication logic into a standalone test program
> (attached), which compares the result of a multiplication to that
> of native int128 arithmetic. I changed the order of the LinearInterval
> fields to be LS-first so that I could overlay them onto an int128
> result (on a little-endian machine); this is just for testing purposes
> not something we must do in the finished code. I soon found cases
> where it indeed fails, eg
>
> $ ./a.out 0x7ffffffff 0x7ffffffff
> 7FFFFFFFF * 7FFFFFFFF
> result = 62 18446744004990074881
> result = 3E FFFFFFF000000001
> MISMATCH!
> result = 63 18446744004990074881
> result = 3F FFFFFFF000000001
I admit that I was careless about that.
> After fooling with it for awhile, I decided that the cause of the
> problems was basically not thinking carefully about the lower half
> of the value being unsigned: that affects when to do carries in
> the addition macro, and we also have to be careful about whether
> or not to sign-extend the partial product terms. The second
> attached file is a version that I can't break anymore, though I'm
> not quite sure it's bug-free.
In the first version, I converted all operands to positive
numbers and finally correct the sign of the result. This was
straightforward but doesn't looked clean so I tried direct
handling of singed values. It was the beginning of this mess.
There was a time when the lower bits is in uint64 but I was
confused by arithmetics mixing signed and unsigned. I realized
that I misunderstood composing 64 bit value from decomposition of
a negative int64.
I reconsidered this based on Tom's test program and try to give
reasoning for the algorithm of the attached new version.
1. Now INT64_AL32 returns explicitly casted into uint64 (for
safety). the upper and lower 32 bit values surely makes the
original value just by INT64_AU32 << 32 + INT64_AL32 because
1.1. The arithmetic is done assuming that both operands of the
addition are in signed int64 but the MSB of the right
operand is always 0 so no difference by reading it as
singed.
- As mentioned in added comment, all terms (stored in the
variable tmp) are the products of two signed/unsigned 32-bit
values expanded to singed int64 variables. This is safe.
- The second and third terms should be left-shifted by 32 bit in
virtually-128-bit storage then added to exiting 128 bit
value. This can be said as adding INT128_AU64(tmp<<32) into hi
part. If INT128_AU64(tmp<<32) is equivalent to
INT64_AU32(tmp)>>32, "span.hi += INT64_AU32(tmp)" is safe.
INT128_AU64(tmp << 32) ; tmp is assumed signed int128 here
= ((tmp << 32) >> 64)
= tmp >>32
= INT64_AU32(tmp) ; here, tmp is safe even if singed int64
Similary,
INT128_AL64(tmp << 32)
= (uint128)(tmp << 32) & 0xFFFFFFFF_FFFFFFFF (lower 32 bits are always 0)
= ((uint64)(tmp) & 0xFFFFFFFF) << 32
= INT64_AL32(tmp) << 32
- The last thing I should confirm is that
LINEARINTERVAL_ADD_UINT64 is correct. This is analogous to 1
above.
(int128)x + (uint64)y
= (int128)x + (int128)y ; safely extended without change
= (INT128AU64(x) << 64 + INT128AL64(x))
+ (INT128AU64(y) << 64 + INT128AL64(y))
= (INT128AU64(x) + INT128AU64(y)) << 64 ; performed as signed
+ (INT128AL64(x) + INT128AL64(y)) ; performed as unsigned
Where (INT128AL64(x) + INT128AL64(y)) is performed as unsigned
and can be overflow, and the carry can be just pushed to the
upper 64bit.
2. Adding two values with MSB of 0 doesn't overflow.
3. If at least one of the two has MSB of 1, it can be overflow.
3.1. Both have MSB of 1, it must overflow.
3.2. If one of the two has MSB of 1, the maximum overflowed
value is made by 0xFFF...FF + 0x7FF...FF and result is
0x(1)7FF..FE so "MSB of the result is 0" and "overflowed" is
equivalent for the case.
Addition to all of the above, dayfraction should be positive so
that LINEARINTERVAL_ADD_UINT64 can be used.
The attached patch is the revised version.
regards,
--
Kyotaro Horiguchi
NTT Open Source Software Center
Kyotaro HORIGUCHI <horiguchi.kyotaro@lab.ntt.co.jp> writes:
> The attached patch is the revised version.
Hmm, this still isn't right --- testing shows that you had the comparison
rule right the first time.
Looking at what we've got here, it's already a substantial fraction of
what would be needed to provide a compiler-independent implementation
of the int128-based aggregate logic in numeric.c. With that in mind,
I propose that we extract the relevant stuff into a new header file
that is designed as general-purpose int128 support. Something like the
attached. I also attach the test program I put together to verify it.
On my Fedora 25 laptop, it appears that the hand-rolled implementation
is actually respectably fast compared to gcc's "native" functionality;
the test program runs in ~2m for 1B iterations with the native logic,
and ~2.5m with the hand-rolled logic. Allowing for overhead and the
fact that we're doing the arithmetic twice, we're probably within 2X
of the native code. Not bad at all.
I'm not entirely sure what to do with the test program:
1. discard it
2. commit it as utils/adt/int128.c, as suggested in its comment
3. commit it somewhere else, maybe src/tools/.
Thoughts?
regards, tom lane
/*-------------------------------------------------------------------------
*
* int128.h
* Roll-our-own 128-bit integer arithmetic.
*
* We make use of the native int128 type if there is one, otherwise
* implement things the hard way based on two int64 halves.
*
* Copyright (c) 2017, PostgreSQL Global Development Group
*
* src/include/utils/int128.h
*
*-------------------------------------------------------------------------
*/
#ifndef INT128_H
#define INT128_H
/*
* For testing purposes, use of native int128 can be switched on/off by
* predefining USE_NATIVE_INT128.
*/
#ifndef USE_NATIVE_INT128
#ifdef HAVE_INT128
#define USE_NATIVE_INT128 1
#else
#define USE_NATIVE_INT128 0
#endif
#endif
#if USE_NATIVE_INT128
typedef int128 INT128;
/*
* Add an unsigned int64 value into an INT128 variable.
*/
static inline void
int128_add_uint64(INT128 *i128, uint64 v)
{
*i128 += v;
}
/*
* Add a signed int64 value into an INT128 variable.
*/
static inline void
int128_add_int64(INT128 *i128, int64 v)
{
*i128 += v;
}
/*
* Add the 128-bit product of two int64 values into an INT128 variable.
*
* XXX with a stupid compiler, this could actually be less efficient than
* the other implementation; maybe we should do it by hand always?
*/
static inline void
int128_add_int64_mul_int64(INT128 *i128, int64 x, int64 y)
{
*i128 += (int128) x *(int128) y;
}
/*
* Compare two INT128 values, return -1, 0, or +1.
*/
static inline int
int128_compare(INT128 x, INT128 y)
{
if (x < y)
return -1;
if (x > y)
return 1;
return 0;
}
#else /* !USE_NATIVE_INT128 */
/*
* We lay out the INT128 structure with the same content and byte ordering
* that a native int128 type would (probably) have. This makes no difference
* for ordinary use of INT128, but allows union'ing INT128 with int128 for
* testing purposes.
*/
typedef struct
{
#ifdef WORDS_BIGENDIAN
int64 hi; /* most significant 64 bits, including sign */
uint64 lo; /* least significant 64 bits, without sign */
#else
uint64 lo; /* least significant 64 bits, without sign */
int64 hi; /* most significant 64 bits, including sign */
#endif
} INT128;
/*
* Add an unsigned int64 value into an INT128 variable.
*/
static inline void
int128_add_uint64(INT128 *i128, uint64 v)
{
/*
* First add the value to the .lo part, then check to see if a carry needs
* to be propagated into the .hi part. A carry is needed if both inputs
* have high bits set, or if just one input has high bit set while the new
* .lo part doesn't. Remember that .lo part is unsigned; we cast to
* signed here just as a cheap way to check the high bit.
*/
uint64 oldlo = i128->lo;
i128->lo += v;
if (((int64) v < 0 && (int64) oldlo < 0) ||
(((int64) v < 0 || (int64) oldlo < 0) && (int64) i128->lo >= 0))
i128->hi++;
}
/*
* Add a signed int64 value into an INT128 variable.
*/
static inline void
int128_add_int64(INT128 *i128, int64 v)
{
/*
* This is much like the above except that the carry logic differs for
* negative v. Ordinarily we'd need to subtract 1 from the .hi part
* (corresponding to adding the sign-extended bits of v to it); but if
* there is a carry out of the .lo part, that cancels and we do nothing.
*/
uint64 oldlo = i128->lo;
i128->lo += v;
if (v >= 0)
{
if ((int64) oldlo < 0 && (int64) i128->lo >= 0)
i128->hi++;
}
else
{
if (!((int64) oldlo < 0 || (int64) i128->lo >= 0))
i128->hi--;
}
}
/*
* INT64_AU32 extracts the most significant 32 bits of int64 as int64, while
* INT64_AL32 extracts the least significant 32 bits as uint64.
*/
#define INT64_AU32(i64) ((i64) >> 32)
#define INT64_AL32(i64) ((i64) & UINT64CONST(0xFFFFFFFF))
/*
* Add the 128-bit product of two int64 values into an INT128 variable.
*/
static inline void
int128_add_int64_mul_int64(INT128 *i128, int64 x, int64 y)
{
/* INT64_AU32 must use arithmetic right shift */
StaticAssertStmt(((int64) -1 >> 1) == (int64) -1,
"arithmetic right shift is needed");
/*----------
* Form the 128-bit product x * y using 64-bit arithmetic.
* Considering each 64-bit input as having 32-bit high and low parts,
* we can compute
*
* x * y = ((x.hi << 32) + x.lo) * (((y.hi << 32) + y.lo)
* = (x.hi * y.hi) << 64 +
* (x.hi * y.lo) << 32 +
* (x.lo * y.hi) << 32 +
* x.lo * y.lo
*
* Each individual product is of 32-bit terms so it won't overflow when
* computed in 64-bit arithmetic. Then we just have to shift it to the
* correct position while adding into the 128-bit result. We must also
* keep in mind that the "lo" parts must be treated as unsigned.
*----------
*/
/* No need to work hard if product must be zero */
if (x != 0 && y != 0)
{
int64 x_u32 = INT64_AU32(x);
uint64 x_l32 = INT64_AL32(x);
int64 y_u32 = INT64_AU32(y);
uint64 y_l32 = INT64_AL32(y);
int64 tmp;
/* the first term */
i128->hi += x_u32 * y_u32;
/* the second term: sign-extend it only if x is negative */
tmp = x_u32 * y_l32;
if (x < 0)
i128->hi += INT64_AU32(tmp);
else
i128->hi += ((uint64) tmp) >> 32;
int128_add_uint64(i128, ((uint64) INT64_AL32(tmp)) << 32);
/* the third term: sign-extend it only if y is negative */
tmp = x_l32 * y_u32;
if (y < 0)
i128->hi += INT64_AU32(tmp);
else
i128->hi += ((uint64) tmp) >> 32;
int128_add_uint64(i128, ((uint64) INT64_AL32(tmp)) << 32);
/* the fourth term: always unsigned */
int128_add_uint64(i128, x_l32 * y_l32);
}
}
/*
* Compare two INT128 values, return -1, 0, or +1.
*/
static inline int
int128_compare(INT128 x, INT128 y)
{
if (x.hi < y.hi)
return -1;
if (x.hi > y.hi)
return 1;
if (x.lo < y.lo)
return -1;
if (x.lo > y.lo)
return 1;
return 0;
}
#endif /* USE_NATIVE_INT128 */
#endif /* INT128_H */
/*-------------------------------------------------------------------------
*
* int128.c
* Testbed for roll-our-own 128-bit integer arithmetic.
*
* This file is not meant to be compiled into the backend; rather, it builds
* a standalone test program that compares the behavior of an implementation
* in int128.h to an (assumed correct) int128 native type.
*
* Copyright (c) 2017, PostgreSQL Global Development Group
*
*
* IDENTIFICATION
* src/backend/utils/adt/int128.c
*
*-------------------------------------------------------------------------
*/
#include "postgres.h"
/*
* By default, we test the non-native implementation in int128.h; but
* by predefining USE_NATIVE_INT128 to 1, you can test the native
* implementation, just to be sure.
*/
#ifndef USE_NATIVE_INT128
#define USE_NATIVE_INT128 0
#endif
#include "int128.h"
/*
* We assume the parts of this union are laid out compatibly.
*/
typedef union
{
int128 i128;
INT128 I128;
union
{
#ifdef WORDS_BIGENDIAN
int64 hi;
uint64 lo;
#else
uint64 lo;
int64 hi;
#endif
} hl;
} test128;
/*
* Control version of comparator.
*/
static inline int
my_int128_compare(int128 x, int128 y)
{
if (x < y)
return -1;
if (x > y)
return 1;
return 0;
}
/*
* Get a random uint64 value.
* We don't assume random() is good for more than 16 bits.
*/
static uint64
get_random_uint64(void)
{
uint64 x;
x = (uint64) (random() & 0xFFFF) << 48;
x |= (uint64) (random() & 0xFFFF) << 32;
x |= (uint64) (random() & 0xFFFF) << 16;
x |= (uint64) (random() & 0xFFFF);
return x;
}
/*
* Main program.
*
* You can give it a loop count if you don't like the default 1B iterations.
*/
int
main(int argc, char **argv)
{
long count;
if (argc >= 2)
count = strtol(argv[1], NULL, 0);
else
count = 1000000000;
while (count-- > 0)
{
int64 x = get_random_uint64();
int64 y = get_random_uint64();
int64 z = get_random_uint64();
test128 t1;
test128 t2;
/* check unsigned addition */
t1.hl.hi = x;
t1.hl.lo = y;
t2 = t1;
t1.i128 += (int128) (uint64) z;
int128_add_uint64(&t2.I128, (uint64) z);
if (t1.hl.hi != t2.hl.hi || t1.hl.lo != t2.hl.lo)
{
printf("%016lX%016lX + unsigned %lX\n", x, y, z);
printf("native = %016lX%016lX\n", t1.hl.hi, t1.hl.lo);
printf("result = %016lX%016lX\n", t2.hl.hi, t2.hl.lo);
return 1;
}
/* check signed addition */
t1.hl.hi = x;
t1.hl.lo = y;
t2 = t1;
t1.i128 += (int128) z;
int128_add_int64(&t2.I128, z);
if (t1.hl.hi != t2.hl.hi || t1.hl.lo != t2.hl.lo)
{
printf("%016lX%016lX + signed %lX\n", x, y, z);
printf("native = %016lX%016lX\n", t1.hl.hi, t1.hl.lo);
printf("result = %016lX%016lX\n", t2.hl.hi, t2.hl.lo);
return 1;
}
/* check multiplication */
t1.i128 = (int128) x *(int128) y;
t2.hl.hi = t2.hl.lo = 0;
int128_add_int64_mul_int64(&t2.I128, x, y);
if (t1.hl.hi != t2.hl.hi || t1.hl.lo != t2.hl.lo)
{
printf("%lX * %lX\n", x, y);
printf("native = %016lX%016lX\n", t1.hl.hi, t1.hl.lo);
printf("result = %016lX%016lX\n", t2.hl.hi, t2.hl.lo);
return 1;
}
/* check comparison */
t1.hl.hi = x;
t1.hl.lo = y;
t2.hl.hi = z;
t2.hl.lo = get_random_uint64();
if (my_int128_compare(t1.i128, t2.i128) !=
int128_compare(t1.I128, t2.I128))
{
printf("comparison failure: %d vs %d\n",
my_int128_compare(t1.i128, t2.i128),
int128_compare(t1.I128, t2.I128));
printf("arg1 = %016lX%016lX\n", t1.hl.hi, t1.hl.lo);
printf("arg2 = %016lX%016lX\n", t2.hl.hi, t2.hl.lo);
return 1;
}
/* check case with identical hi parts; above will hardly ever hit it */
t2.hl.hi = x;
if (my_int128_compare(t1.i128, t2.i128) !=
int128_compare(t1.I128, t2.I128))
{
printf("comparison failure: %d vs %d\n",
my_int128_compare(t1.i128, t2.i128),
int128_compare(t1.I128, t2.I128));
printf("arg1 = %016lX%016lX\n", t1.hl.hi, t1.hl.lo);
printf("arg2 = %016lX%016lX\n", t2.hl.hi, t2.hl.lo);
return 1;
}
}
return 0;
}
I wrote:
> Looking at what we've got here, it's already a substantial fraction of
> what would be needed to provide a compiler-independent implementation
> of the int128-based aggregate logic in numeric.c. With that in mind,
> I propose that we extract the relevant stuff into a new header file
> that is designed as general-purpose int128 support. Something like the
> attached. I also attach the test program I put together to verify it.
Here's a fleshed-out patch for the original problem based on that.
I found that direct int64-to-int128 coercions were also needed to
handle some of the steps in timestamp.c, so I added those to int128.h.
I think it would be reasonable to back-patch this, although it would
need some adjustments for the back branches since we only recently
got rid of the float-timestamp option. Also I'd not be inclined to
depend on native int128 any further back than it was already in use.
regards, tom lane
diff --git a/src/backend/utils/adt/int128.c b/src/backend/utils/adt/int128.c
index ...8bc0663 .
*** a/src/backend/utils/adt/int128.c
--- b/src/backend/utils/adt/int128.c
***************
*** 0 ****
--- 1,181 ----
+ /*-------------------------------------------------------------------------
+ *
+ * int128.c
+ * Testbed for roll-our-own 128-bit integer arithmetic.
+ *
+ * This file is not meant to be compiled into the backend; rather, it builds
+ * a standalone test program that compares the behavior of an implementation
+ * in int128.h to an (assumed correct) int128 native type.
+ *
+ * Copyright (c) 2017, PostgreSQL Global Development Group
+ *
+ *
+ * IDENTIFICATION
+ * src/backend/utils/adt/int128.c
+ *
+ *-------------------------------------------------------------------------
+ */
+
+ #include "postgres.h"
+
+ /*
+ * By default, we test the non-native implementation in int128.h; but
+ * by predefining USE_NATIVE_INT128 to 1, you can test the native
+ * implementation, just to be sure.
+ */
+ #ifndef USE_NATIVE_INT128
+ #define USE_NATIVE_INT128 0
+ #endif
+
+ #include "utils/int128.h"
+
+ /*
+ * We assume the parts of this union are laid out compatibly.
+ */
+ typedef union
+ {
+ int128 i128;
+ INT128 I128;
+ union
+ {
+ #ifdef WORDS_BIGENDIAN
+ int64 hi;
+ uint64 lo;
+ #else
+ uint64 lo;
+ int64 hi;
+ #endif
+ } hl;
+ } test128;
+
+
+ /*
+ * Control version of comparator.
+ */
+ static inline int
+ my_int128_compare(int128 x, int128 y)
+ {
+ if (x < y)
+ return -1;
+ if (x > y)
+ return 1;
+ return 0;
+ }
+
+ /*
+ * Get a random uint64 value.
+ * We don't assume random() is good for more than 16 bits.
+ */
+ static uint64
+ get_random_uint64(void)
+ {
+ uint64 x;
+
+ x = (uint64) (random() & 0xFFFF) << 48;
+ x |= (uint64) (random() & 0xFFFF) << 32;
+ x |= (uint64) (random() & 0xFFFF) << 16;
+ x |= (uint64) (random() & 0xFFFF);
+ return x;
+ }
+
+ /*
+ * Main program.
+ *
+ * You can give it a loop count if you don't like the default 1B iterations.
+ */
+ int
+ main(int argc, char **argv)
+ {
+ long count;
+
+ if (argc >= 2)
+ count = strtol(argv[1], NULL, 0);
+ else
+ count = 1000000000;
+
+ while (count-- > 0)
+ {
+ int64 x = get_random_uint64();
+ int64 y = get_random_uint64();
+ int64 z = get_random_uint64();
+ test128 t1;
+ test128 t2;
+
+ /* check unsigned addition */
+ t1.hl.hi = x;
+ t1.hl.lo = y;
+ t2 = t1;
+ t1.i128 += (int128) (uint64) z;
+ int128_add_uint64(&t2.I128, (uint64) z);
+
+ if (t1.hl.hi != t2.hl.hi || t1.hl.lo != t2.hl.lo)
+ {
+ printf("%016lX%016lX + unsigned %lX\n", x, y, z);
+ printf("native = %016lX%016lX\n", t1.hl.hi, t1.hl.lo);
+ printf("result = %016lX%016lX\n", t2.hl.hi, t2.hl.lo);
+ return 1;
+ }
+
+ /* check signed addition */
+ t1.hl.hi = x;
+ t1.hl.lo = y;
+ t2 = t1;
+ t1.i128 += (int128) z;
+ int128_add_int64(&t2.I128, z);
+
+ if (t1.hl.hi != t2.hl.hi || t1.hl.lo != t2.hl.lo)
+ {
+ printf("%016lX%016lX + signed %lX\n", x, y, z);
+ printf("native = %016lX%016lX\n", t1.hl.hi, t1.hl.lo);
+ printf("result = %016lX%016lX\n", t2.hl.hi, t2.hl.lo);
+ return 1;
+ }
+
+ /* check multiplication */
+ t1.i128 = (int128) x *(int128) y;
+
+ t2.hl.hi = t2.hl.lo = 0;
+ int128_add_int64_mul_int64(&t2.I128, x, y);
+
+ if (t1.hl.hi != t2.hl.hi || t1.hl.lo != t2.hl.lo)
+ {
+ printf("%lX * %lX\n", x, y);
+ printf("native = %016lX%016lX\n", t1.hl.hi, t1.hl.lo);
+ printf("result = %016lX%016lX\n", t2.hl.hi, t2.hl.lo);
+ return 1;
+ }
+
+ /* check comparison */
+ t1.hl.hi = x;
+ t1.hl.lo = y;
+ t2.hl.hi = z;
+ t2.hl.lo = get_random_uint64();
+
+ if (my_int128_compare(t1.i128, t2.i128) !=
+ int128_compare(t1.I128, t2.I128))
+ {
+ printf("comparison failure: %d vs %d\n",
+ my_int128_compare(t1.i128, t2.i128),
+ int128_compare(t1.I128, t2.I128));
+ printf("arg1 = %016lX%016lX\n", t1.hl.hi, t1.hl.lo);
+ printf("arg2 = %016lX%016lX\n", t2.hl.hi, t2.hl.lo);
+ return 1;
+ }
+
+ /* check case with identical hi parts; above will hardly ever hit it */
+ t2.hl.hi = x;
+
+ if (my_int128_compare(t1.i128, t2.i128) !=
+ int128_compare(t1.I128, t2.I128))
+ {
+ printf("comparison failure: %d vs %d\n",
+ my_int128_compare(t1.i128, t2.i128),
+ int128_compare(t1.I128, t2.I128));
+ printf("arg1 = %016lX%016lX\n", t1.hl.hi, t1.hl.lo);
+ printf("arg2 = %016lX%016lX\n", t2.hl.hi, t2.hl.lo);
+ return 1;
+ }
+ }
+
+ return 0;
+ }
diff --git a/src/backend/utils/adt/timestamp.c b/src/backend/utils/adt/timestamp.c
index 4be1999..88ecb78 100644
*** a/src/backend/utils/adt/timestamp.c
--- b/src/backend/utils/adt/timestamp.c
***************
*** 33,38 ****
--- 33,40 ----
#include "utils/array.h"
#include "utils/builtins.h"
#include "utils/datetime.h"
+ #include "utils/int128.h"
+
/*
* gcc's -ffast-math switch breaks routines that expect exact results from
*************** timestamptz_cmp_timestamp(PG_FUNCTION_AR
*** 2288,2302 ****
/*
* interval_relop - is interval1 relop interval2
*/
! static inline TimeOffset
interval_cmp_value(const Interval *interval)
{
! TimeOffset span;
! span = interval->time;
! span += interval->month * INT64CONST(30) * USECS_PER_DAY;
! span += interval->day * INT64CONST(24) * USECS_PER_HOUR;
return span;
}
--- 2290,2324 ----
/*
* interval_relop - is interval1 relop interval2
+ *
+ * Interval comparison is based on converting interval values to a linear
+ * representation expressed in the units of the time field (microseconds,
+ * in the case of integer timestamps) with days assumed to be always 24 hours
+ * and months assumed to be always 30 days. To avoid overflow, we need a
+ * wider-than-int64 datatype for the linear representation, so use INT128.
*/
!
! static inline INT128
interval_cmp_value(const Interval *interval)
{
! INT128 span;
! int64 dayfraction;
! int64 days;
! /*
! * Separate time field into days and dayfraction, then add the month and
! * day fields to the days part. We cannot overflow int64 days here.
! */
! dayfraction = interval->time % USECS_PER_DAY;
! days = interval->time / USECS_PER_DAY;
! days += interval->month * INT64CONST(30);
! days += interval->day;
!
! /* Widen dayfraction to 128 bits */
! span = int64_to_int128(dayfraction);
!
! /* Scale up days to microseconds, forming a 128-bit product */
! int128_add_int64_mul_int64(&span, days, USECS_PER_DAY);
return span;
}
*************** interval_cmp_value(const Interval *inter
*** 2304,2313 ****
static int
interval_cmp_internal(Interval *interval1, Interval *interval2)
{
! TimeOffset span1 = interval_cmp_value(interval1);
! TimeOffset span2 = interval_cmp_value(interval2);
! return ((span1 < span2) ? -1 : (span1 > span2) ? 1 : 0);
}
Datum
--- 2326,2335 ----
static int
interval_cmp_internal(Interval *interval1, Interval *interval2)
{
! INT128 span1 = interval_cmp_value(interval1);
! INT128 span2 = interval_cmp_value(interval2);
! return int128_compare(span1, span2);
}
Datum
*************** Datum
*** 2384,2392 ****
interval_hash(PG_FUNCTION_ARGS)
{
Interval *interval = PG_GETARG_INTERVAL_P(0);
! TimeOffset span = interval_cmp_value(interval);
! return DirectFunctionCall1(hashint8, Int64GetDatumFast(span));
}
/* overlaps_timestamp() --- implements the SQL OVERLAPS operator.
--- 2406,2423 ----
interval_hash(PG_FUNCTION_ARGS)
{
Interval *interval = PG_GETARG_INTERVAL_P(0);
! INT128 span = interval_cmp_value(interval);
! int64 span64;
! /*
! * Use only the least significant 64 bits for hashing. The upper 64 bits
! * seldom add any useful information, and besides we must do it like this
! * for compatibility with hashes calculated before use of INT128 was
! * introduced.
! */
! span64 = int128_to_int64(span);
!
! return DirectFunctionCall1(hashint8, Int64GetDatumFast(span64));
}
/* overlaps_timestamp() --- implements the SQL OVERLAPS operator.
diff --git a/src/include/utils/int128.h b/src/include/utils/int128.h
index ...876610b .
*** a/src/include/utils/int128.h
--- b/src/include/utils/int128.h
***************
*** 0 ****
--- 1,274 ----
+ /*-------------------------------------------------------------------------
+ *
+ * int128.h
+ * Roll-our-own 128-bit integer arithmetic.
+ *
+ * We make use of the native int128 type if there is one, otherwise
+ * implement things the hard way based on two int64 halves.
+ *
+ * Copyright (c) 2017, PostgreSQL Global Development Group
+ *
+ * src/include/utils/int128.h
+ *
+ *-------------------------------------------------------------------------
+ */
+ #ifndef INT128_H
+ #define INT128_H
+
+ /*
+ * For testing purposes, use of native int128 can be switched on/off by
+ * predefining USE_NATIVE_INT128.
+ */
+ #ifndef USE_NATIVE_INT128
+ #ifdef HAVE_INT128
+ #define USE_NATIVE_INT128 1
+ #else
+ #define USE_NATIVE_INT128 0
+ #endif
+ #endif
+
+
+ #if USE_NATIVE_INT128
+
+ typedef int128 INT128;
+
+ /*
+ * Add an unsigned int64 value into an INT128 variable.
+ */
+ static inline void
+ int128_add_uint64(INT128 *i128, uint64 v)
+ {
+ *i128 += v;
+ }
+
+ /*
+ * Add a signed int64 value into an INT128 variable.
+ */
+ static inline void
+ int128_add_int64(INT128 *i128, int64 v)
+ {
+ *i128 += v;
+ }
+
+ /*
+ * Add the 128-bit product of two int64 values into an INT128 variable.
+ *
+ * XXX with a stupid compiler, this could actually be less efficient than
+ * the other implementation; maybe we should do it by hand always?
+ */
+ static inline void
+ int128_add_int64_mul_int64(INT128 *i128, int64 x, int64 y)
+ {
+ *i128 += (int128) x *(int128) y;
+ }
+
+ /*
+ * Compare two INT128 values, return -1, 0, or +1.
+ */
+ static inline int
+ int128_compare(INT128 x, INT128 y)
+ {
+ if (x < y)
+ return -1;
+ if (x > y)
+ return 1;
+ return 0;
+ }
+
+ /*
+ * Widen int64 to INT128.
+ */
+ static inline INT128
+ int64_to_int128(int64 v)
+ {
+ return (INT128) v;
+ }
+
+ /*
+ * Convert INT128 to int64 (losing any high-order bits).
+ * This also works fine for casting down to uint64.
+ */
+ static inline int64
+ int128_to_int64(INT128 val)
+ {
+ return (int64) val;
+ }
+
+ #else /* !USE_NATIVE_INT128 */
+
+ /*
+ * We lay out the INT128 structure with the same content and byte ordering
+ * that a native int128 type would (probably) have. This makes no difference
+ * for ordinary use of INT128, but allows union'ing INT128 with int128 for
+ * testing purposes.
+ */
+ typedef struct
+ {
+ #ifdef WORDS_BIGENDIAN
+ int64 hi; /* most significant 64 bits, including sign */
+ uint64 lo; /* least significant 64 bits, without sign */
+ #else
+ uint64 lo; /* least significant 64 bits, without sign */
+ int64 hi; /* most significant 64 bits, including sign */
+ #endif
+ } INT128;
+
+ /*
+ * Add an unsigned int64 value into an INT128 variable.
+ */
+ static inline void
+ int128_add_uint64(INT128 *i128, uint64 v)
+ {
+ /*
+ * First add the value to the .lo part, then check to see if a carry needs
+ * to be propagated into the .hi part. A carry is needed if both inputs
+ * have high bits set, or if just one input has high bit set while the new
+ * .lo part doesn't. Remember that .lo part is unsigned; we cast to
+ * signed here just as a cheap way to check the high bit.
+ */
+ uint64 oldlo = i128->lo;
+
+ i128->lo += v;
+ if (((int64) v < 0 && (int64) oldlo < 0) ||
+ (((int64) v < 0 || (int64) oldlo < 0) && (int64) i128->lo >= 0))
+ i128->hi++;
+ }
+
+ /*
+ * Add a signed int64 value into an INT128 variable.
+ */
+ static inline void
+ int128_add_int64(INT128 *i128, int64 v)
+ {
+ /*
+ * This is much like the above except that the carry logic differs for
+ * negative v. Ordinarily we'd need to subtract 1 from the .hi part
+ * (corresponding to adding the sign-extended bits of v to it); but if
+ * there is a carry out of the .lo part, that cancels and we do nothing.
+ */
+ uint64 oldlo = i128->lo;
+
+ i128->lo += v;
+ if (v >= 0)
+ {
+ if ((int64) oldlo < 0 && (int64) i128->lo >= 0)
+ i128->hi++;
+ }
+ else
+ {
+ if (!((int64) oldlo < 0 || (int64) i128->lo >= 0))
+ i128->hi--;
+ }
+ }
+
+ /*
+ * INT64_AU32 extracts the most significant 32 bits of int64 as int64, while
+ * INT64_AL32 extracts the least significant 32 bits as uint64.
+ */
+ #define INT64_AU32(i64) ((i64) >> 32)
+ #define INT64_AL32(i64) ((i64) & UINT64CONST(0xFFFFFFFF))
+
+ /*
+ * Add the 128-bit product of two int64 values into an INT128 variable.
+ */
+ static inline void
+ int128_add_int64_mul_int64(INT128 *i128, int64 x, int64 y)
+ {
+ /* INT64_AU32 must use arithmetic right shift */
+ StaticAssertStmt(((int64) -1 >> 1) == (int64) -1,
+ "arithmetic right shift is needed");
+
+ /*----------
+ * Form the 128-bit product x * y using 64-bit arithmetic.
+ * Considering each 64-bit input as having 32-bit high and low parts,
+ * we can compute
+ *
+ * x * y = ((x.hi << 32) + x.lo) * (((y.hi << 32) + y.lo)
+ * = (x.hi * y.hi) << 64 +
+ * (x.hi * y.lo) << 32 +
+ * (x.lo * y.hi) << 32 +
+ * x.lo * y.lo
+ *
+ * Each individual product is of 32-bit terms so it won't overflow when
+ * computed in 64-bit arithmetic. Then we just have to shift it to the
+ * correct position while adding into the 128-bit result. We must also
+ * keep in mind that the "lo" parts must be treated as unsigned.
+ *----------
+ */
+
+ /* No need to work hard if product must be zero */
+ if (x != 0 && y != 0)
+ {
+ int64 x_u32 = INT64_AU32(x);
+ uint64 x_l32 = INT64_AL32(x);
+ int64 y_u32 = INT64_AU32(y);
+ uint64 y_l32 = INT64_AL32(y);
+ int64 tmp;
+
+ /* the first term */
+ i128->hi += x_u32 * y_u32;
+
+ /* the second term: sign-extend it only if x is negative */
+ tmp = x_u32 * y_l32;
+ if (x < 0)
+ i128->hi += INT64_AU32(tmp);
+ else
+ i128->hi += ((uint64) tmp) >> 32;
+ int128_add_uint64(i128, ((uint64) INT64_AL32(tmp)) << 32);
+
+ /* the third term: sign-extend it only if y is negative */
+ tmp = x_l32 * y_u32;
+ if (y < 0)
+ i128->hi += INT64_AU32(tmp);
+ else
+ i128->hi += ((uint64) tmp) >> 32;
+ int128_add_uint64(i128, ((uint64) INT64_AL32(tmp)) << 32);
+
+ /* the fourth term: always unsigned */
+ int128_add_uint64(i128, x_l32 * y_l32);
+ }
+ }
+
+ /*
+ * Compare two INT128 values, return -1, 0, or +1.
+ */
+ static inline int
+ int128_compare(INT128 x, INT128 y)
+ {
+ if (x.hi < y.hi)
+ return -1;
+ if (x.hi > y.hi)
+ return 1;
+ if (x.lo < y.lo)
+ return -1;
+ if (x.lo > y.lo)
+ return 1;
+ return 0;
+ }
+
+ /*
+ * Widen int64 to INT128.
+ */
+ static inline INT128
+ int64_to_int128(int64 v)
+ {
+ INT128 val;
+
+ val.lo = (uint64) v;
+ val.hi = (v < 0) ? -INT64CONST(1) : INT64CONST(0);
+ return val;
+ }
+
+ /*
+ * Convert INT128 to int64 (losing any high-order bits).
+ * This also works fine for casting down to uint64.
+ */
+ static inline int64
+ int128_to_int64(INT128 val)
+ {
+ return (int64) val.lo;
+ }
+
+ #endif /* USE_NATIVE_INT128 */
+
+ #endif /* INT128_H */
diff --git a/src/test/regress/expected/interval.out b/src/test/regress/expected/interval.out
index 946c97a..d4e6a00 100644
*** a/src/test/regress/expected/interval.out
--- b/src/test/regress/expected/interval.out
*************** SELECT '' AS fortyfive, r1.*, r2.*
*** 207,212 ****
--- 207,248 ----
| 34 years | 6 years
(45 rows)
+ -- intervals out of 64bit linear value in microseconds
+ CREATE TABLE INTERVAL_TBL_OF (f1 interval);
+ INSERT INTO INTERVAL_TBL_OF (f1) VALUES ('2147483647 days 2147483647 months');
+ INSERT INTO INTERVAL_TBL_OF (f1) VALUES ('1 year');
+ INSERT INTO INTERVAL_TBL_OF (f1) VALUES ('-2147483648 days -2147483648 months');
+ SELECT '' AS "64bits", r1.*, r2.*
+ FROM INTERVAL_TBL_OF r1, INTERVAL_TBL_OF r2
+ WHERE r1.f1 > r2.f1
+ ORDER BY r1.f1, r2.f1;
+ 64bits | f1 | f1
+ --------+----------------------------------------+-------------------------------------------
+ | 1 year | -178956970 years -8 mons -2147483648 days
+ | 178956970 years 7 mons 2147483647 days | -178956970 years -8 mons -2147483648 days
+ | 178956970 years 7 mons 2147483647 days | 1 year
+ (3 rows)
+
+ CREATE INDEX ON INTERVAL_TBL_OF USING btree (f1);
+ SET enable_seqscan to false;
+ EXPLAIN SELECT '' AS "64bits_2", f1
+ FROM INTERVAL_TBL_OF r1 ORDER BY f1;
+ QUERY PLAN
+ --------------------------------------------------------------------------------------------------------
+ Index Only Scan using interval_tbl_of_f1_idx on interval_tbl_of r1 (cost=0.13..12.18 rows=3 width=48)
+ (1 row)
+
+ SELECT '' AS "64bits_2", f1
+ FROM INTERVAL_TBL_OF r1 ORDER BY f1;
+ 64bits_2 | f1
+ ----------+-------------------------------------------
+ | -178956970 years -8 mons -2147483648 days
+ | 1 year
+ | 178956970 years 7 mons 2147483647 days
+ (3 rows)
+
+ SET enable_seqscan to default;
+ DROP TABLE INTERVAL_TBL_OF;
-- Test multiplication and division with intervals.
-- Floating point arithmetic rounding errors can lead to unexpected results,
-- though the code attempts to do the right thing and round up to days and
diff --git a/src/test/regress/sql/interval.sql b/src/test/regress/sql/interval.sql
index cff9ada..aa21673 100644
*** a/src/test/regress/sql/interval.sql
--- b/src/test/regress/sql/interval.sql
*************** SELECT '' AS fortyfive, r1.*, r2.*
*** 59,64 ****
--- 59,81 ----
WHERE r1.f1 > r2.f1
ORDER BY r1.f1, r2.f1;
+ -- intervals out of 64bit linear value in microseconds
+ CREATE TABLE INTERVAL_TBL_OF (f1 interval);
+ INSERT INTO INTERVAL_TBL_OF (f1) VALUES ('2147483647 days 2147483647 months');
+ INSERT INTO INTERVAL_TBL_OF (f1) VALUES ('1 year');
+ INSERT INTO INTERVAL_TBL_OF (f1) VALUES ('-2147483648 days -2147483648 months');
+ SELECT '' AS "64bits", r1.*, r2.*
+ FROM INTERVAL_TBL_OF r1, INTERVAL_TBL_OF r2
+ WHERE r1.f1 > r2.f1
+ ORDER BY r1.f1, r2.f1;
+ CREATE INDEX ON INTERVAL_TBL_OF USING btree (f1);
+ SET enable_seqscan to false;
+ EXPLAIN SELECT '' AS "64bits_2", f1
+ FROM INTERVAL_TBL_OF r1 ORDER BY f1;
+ SELECT '' AS "64bits_2", f1
+ FROM INTERVAL_TBL_OF r1 ORDER BY f1;
+ SET enable_seqscan to default;
+ DROP TABLE INTERVAL_TBL_OF;
-- Test multiplication and division with intervals.
-- Floating point arithmetic rounding errors can lead to unexpected results,