'infinity' in GiST index

Oleg Bartunov <oleg@sai.msu.su> writes:

there was complain about problem with creating GiST index if
timestamp column contains 'infinity' value. The problem is indeed
exists and I'd like to have it fixed, but we have no idea
how to handle it in GiST, actually in penalty function.
Any thoughts ?

Seems like it's not really GiST's fault but a definitional problem
for the timestamp datatype. Specifically, what does it mean to
subtract two infinite timestamps? I find it hard to assign a
value to any of these combinations:
+infinity minus +infinity
-infinity minus -infinity
+infinity minus -infinity
-infinity minus +infinity
The first two can't really be identified with zero, and the last two are
surely not representable are they?

What's worse, a subtraction involving one infinite and one finite
timestamp *is* well defined from a mathematical point of view, eg
+infinity minus 'yesterday' = +infinity
but I doubt GiST will be happy if we make the datatype behave that
way...

regards, tom lane

-----Original Message-----
From: Tom Lane [mailto:tgl@sss.pgh.pa.us]
Sent: Wednesday, May 04, 2005 11:17 PM
To: Oleg Bartunov
Cc: Pgsql Hackers
Subject: Re: [HACKERS] 'infinity' in GiST index

[...]
Seems like it's not really GiST's fault but a definitional problem
for the timestamp datatype. Specifically, what does it mean to
subtract two infinite timestamps? I find it hard to assign a
value to any of these combinations:
+infinity minus +infinity
-infinity minus -infinity
+infinity minus -infinity
-infinity minus +infinity

That's because you're talking about transfinite arithmetic, and
subtraction is not defined therein. AKA "the arithmetic of
infinite cardinals". I've actually seen a few different
formulations, some of which say that adding a finite number to
an infinity results in a different number than the infinity, and
some that say it is the original infinity. However, it seems
that the most common formulation is the latter:

w + 1 = w

Where w is lower-case omega, or aleph_0. If we allowed subtraction,
then we could subtract w from both sides and end up with 1 = 0,
which would be an inconsistency. Also, -w makes sense when talking
about the reals, but not when talking about transfinite arithmetic.
There are no additive inverses, because that is the same as allowing
subtraction, with the same result. Note that within real arithemtic,
you can't do any math with infinity anyway.

The first two can't really be identified with zero, and the
last two are surely not representable are they?

Not unless you change to another math system, which, of course,
wouldn't be appropriate for this application.

What's worse, a subtraction involving one infinite and one finite
timestamp *is* well defined from a mathematical point of view, eg
+infinity minus 'yesterday' = +infinity

Actually not. When doing transfinite arithmetic, you can only
add naturals to infinities. Otherwise, you're getting a form of
subtraction, which will eventually lead to inconsistency.

but I doubt GiST will be happy if we make the datatype behave
that way...

I guess it depends on why you want to take the difference. If
you want to take some measure of distance, it might be useful
to say that all infinite values of the same sign are at 0 distance
from each other, in which case you would say that +w - +w = 0.
Probably infinities of opposite signs should just be w apart
(which is also mathematically consistent).

__
David B. Held
Software Engineer/Array Services Group
200 14th Ave. East, Sartell, MN 56377
320.534.3637 320.253.7800 800.752.8129

On 2005-05-05, "Dave Held" <dave.held@arraysg.com> wrote:

That's because you're talking about transfinite arithmetic, and
subtraction is not defined therein. AKA "the arithmetic of
infinite cardinals". I've actually seen a few different
formulations, some of which say that adding a finite number to
an infinity results in a different number than the infinity, and
some that say it is the original infinity. However, it seems
that the most common formulation is the latter:

w + 1 = w

Where w is lower-case omega, or aleph_0.

No; you're confusing your cardinals and your ordinals. aleph_0 is a
cardinal number (the cardinality of any infinite countable set);
omega is an ordinal number. The arithmetic of transfinite ordinals is
completely different to that of cardinals; the most obvious example of
this is that addition involving transfinite ordinals is not commutative:

1 + w = w != w + 1

(Think of this as follows: 1 + w represents a single item followed by an
infinite sequence; this is indistinguishable from the infinite sequence
alone. w + 1 is an infinite sequence followed by a single item; this is
not equivalent to the original sequence, so you can continue to w + 2,
w + 3, ... w + w = 2w and so on.)

In contrast the arithmetic of cardinals behaves quite differently:

a_0 + 1 = a_0
a_0 + a_0 = 2 x a_0 = a_0
a_0 x a_0 = a_0 ^ 2 = a_0

2 ^ a_0 = C > a_0

(A countable infinite set with an item added is still countable. Two
countable infinite sets can be counted by taking items alternately from
each. A square whose dimensions are countably infinite can be counted by
starting at any point and spiralling outwards. C, which may or may not be
a_1 but is larger than a_0, is the cardinality of the real numbers; this
is shown not to be countable, and therefore > a_0, by Cantor's famous
diagonal argument.)

But this is all irrelevent to the original question, because the 'infinity'
used in floating-point arithmetic corresponds neither to transfinite
cardinals nor transfinite ordinals, but instead is an arbitrary label with
its own rules, defined as follows in IEEE arithmetic:

  +Inf + +Inf = +Inf
  +Inf - +Inf = NaN
  +Inf + -Inf = NaN
  +Inf * 0    = NaN
  +Inf / +Inf = NaN

etc.

--
Andrew, Supernews
http://www.supernews.com - individual and corporate NNTP services

On Thu, 5 May 2005, Dave Held wrote:

but I doubt GiST will be happy if we make the datatype behave
that way...

I guess it depends on why you want to take the difference. If
you want to take some measure of distance, it might be useful
to say that all infinite values of the same sign are at 0 distance
from each other, in which case you would say that +w - +w = 0.
Probably infinities of opposite signs should just be w apart
(which is also mathematically consistent).

actually, it's timestamp_mi function rise the error which prevent
GiST index creation.

__
David B. Held
Software Engineer/Array Services Group
200 14th Ave. East, Sartell, MN 56377
320.534.3637 320.253.7800 800.752.8129

---------------------------(end of broadcast)---------------------------
TIP 9: the planner will ignore your desire to choose an index scan if your
joining column's datatypes do not match

Regards,
Oleg
_____________________________________________________________
Oleg Bartunov, sci.researcher, hostmaster of AstroNet,
Sternberg Astronomical Institute, Moscow University (Russia)
Internet: oleg@sai.msu.su, http://www.sai.msu.su/~megera/
phone: +007(095)939-16-83, +007(095)939-23-83

Oleg Bartunov <oleg@sai.msu.su> writes:

On Thu, 5 May 2005, Dave Held wrote:

I guess it depends on why you want to take the difference. If
you want to take some measure of distance, it might be useful
to say that all infinite values of the same sign are at 0 distance
from each other, in which case you would say that +w - +w = 0.
Probably infinities of opposite signs should just be w apart
(which is also mathematically consistent).

actually, it's timestamp_mi function rise the error which prevent
GiST index creation.

Right --- the question is why is GIST calling that function.
What do you really need it to do?

regards, tom lane