Unexpected interval comparison

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

--
Sent via pgsql-general mailing list (pgsql-general@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-general

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

--
Sent via pgsql-general mailing list (pgsql-general@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-general

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

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

--
Sent via pgsql-general mailing list (pgsql-general@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-general

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

--
Sent via pgsql-general mailing list (pgsql-general@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-general

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

--
Sent via pgsql-general mailing list (pgsql-general@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-general

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

--
Sent via pgsql-general mailing list (pgsql-general@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-general

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:

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

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

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

At Wed, 05 Apr 2017 15:51:10 -0400, Tom Lane <tgl@sss.pgh.pa.us> wrote in <27982.1491421870@sss.pgh.pa.us>

Hmm, this still isn't right --- testing shows that you had the comparison
rule right the first time.

Perhaps Laplaces's deamon is continuously nudging on my head
toward wrong conclusion, sigh. Sorry for bothering you.

At Wed, 05 Apr 2017 17:06:53 -0400, Tom Lane <tgl@sss.pgh.pa.us> wrote in <385.1491426413@sss.pgh.pa.us>

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.

+1

Something like the
attached. I also attach the test program I put together to verify it.

The new patch seems cleaner and fine to me with maybe-fresh eyes.

Since we have some instances of failure cases on non-native
int128 arithmetic, I'd like to provide regression test for them
but that seems not so simple.

By the way the adt directory is, as suggested by the name,
storing files with names of SQL data types so "int128.c" among
then seems incongruous. Is "int128_test.c" acceptable? int16.c
will be placed there in case we support int16 or hugeint on SQL.

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.

Back to 9.5 seems reasonable to me.

--
Kyotaro Horiguchi
NTT Open Source Software Center

--
Sent via pgsql-general mailing list (pgsql-general@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-general

Kyotaro HORIGUCHI <horiguchi.kyotaro@lab.ntt.co.jp> writes:

By the way the adt directory is, as suggested by the name,
storing files with names of SQL data types so "int128.c" among
then seems incongruous. Is "int128_test.c" acceptable? int16.c
will be placed there in case we support int16 or hugeint on SQL.

After further reflection I've decided to put int128.h in
src/include/common/, thinking that maybe someday it will be useful
on client side too. Also I've changed the test harness file to
be src/tools/testint128.c, so that it won't be confused with code
meant to be part of the backend.

Back to 9.5 seems reasonable to me.

I poked around and noticed that before 9.4, we did not attempt
to guard against overflows in interval calculations at all.
So backpatch to 9.4 seems pretty defensible. The non-HAVE_INT128
code works fine in 9.4.

I've just about finished adjusting the patch for the back
branches, and will push in a little bit.

regards, tom lane

--
Sent via pgsql-general mailing list (pgsql-general@postgresql.org)
To make changes to your subscription:
http://www.postgresql.org/mailpref/pgsql-general