Thread: 'infinity' in GiST index
Hi there,
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 ?
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:
> 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_0a_0 + a_0 = 2 x a_0 = a_0a_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