UB-Tree
Hi,
The inventor of the B-Tree algorythm, R. Bayer, published
in the past years ('96-'01) several scientific papers where
he describes the new UB-Tree algorythm. It is based on
ordinary B-Tree implementation but allows >multidimensional<
indexing.
Apart from the need to update only one index instead of
several for each table insert/delete the UB-Tree indexing
allows to perform extremly performant lookups for queries
that contain constraints for several columns (dimensions)
and sort criterias, like:
SELECT * FROM EMPLOYEES WHERE ID>10 AND ID<100 AND INCOME>5000 SORTED BY NAME
Such a query could profit from an UB-Tree index on the columns
(dimensions) ID, INCOME and NAME - all at once, using only
one UB-Tree!
So the UB-Tree allows you:
- to make range queries on all dimensions at once, and
- read the result in sorted order (with only little overhead), where
- each dimension can be read in sorted or reverse order
I guess such an indexing method would please any SQL database.
Has anybody of you ever stumbled across the UB-Tree related
algorythms?
If not, you can download several PDF documents describing
the UB-Tree related algorythms from this URL (in english
language!):
I found no free implementation of the UB-Tree. The team
of R. Bayer only released closed source and sell it.
kind regards,
Robert Schrem
On Fri, 2002-03-08 at 20:48, Robert Schrem wrote:
If not, you can download several PDF documents describing
the UB-Tree related algorythms from this URL (in english
language!):
The last one tere seems to be the original explanation of the idea.
I found no free implementation of the UB-Tree. The team
of R. Bayer only released closed source and sell it.
This technique seems to be a good candidate for implementing using GiST
or perhaps just defined using the <. operator mentioned there.
Mappign from ordinary query with several = , < and between may be a
little tricky though.
They may also have patents on it, so we should move carefully here.
-------------
Hannu
Hi,
On Friday 08 March 2002 20:37, Hannu Krosing wrote:
This technique seems to be a good candidate for implementing using GiST
or perhaps just defined using the <. operator mentioned there.
As I understand GiST is a pretty different algorythm - but I
might be wrong because I know very much about GiST.
On Friday 08 March 2002 20:37, Hannu Krosing wrote:
Mappign from ordinary query with several = , < and between may be a
little tricky though.
But the possible performance gain can be huge - at least
this is what you find in theier benchmark documentations.
On Friday 08 March 2002 20:37, Hannu Krosing wrote:
They may also have patents on it, so we should move carefully here.
I sent a mail asking R. Bayer about any known patent issues.
He said that the UB-Tree is internationally patented.
Sad, because it looked like a briliant idea. Now it looks like
it will be banned from the open source community for some
decades to come... :-(
Robert Schrem
-------------------------------------------------------
Import Notes
Resolved by subject fallback
----- Original Message -----
From: "Robert Schrem" <robert@schrem.de>
To: "Hannu Krosing" <hannu@krosing.net>
Cc: "PostgreSQL Hackers List" <pgsql-hackers@postgresql.org>
Sent: Monday, March 11, 2002 11:55 AM
Subject: Fwd: Re: [HACKERS] UB-Tree
On Friday 08 March 2002 20:37, Hannu Krosing wrote:
They may also have patents on it, so we should move carefully here.
I sent a mail asking R. Bayer about any known patent issues.
He said that the UB-Tree is internationally patented.
Sad, because it looked like a briliant idea. Now it looks like
it will be banned from the open source community for some
decades to come... :-(
IANAL, but there seem to be some issues :
1. There is no such thing as 'internationally patented' as most countries
still don't allow patenting software algorithms.
2. I doubt it is possible to patent a general idea, like replacing multiple
one-dimensional indexes with one multi-dimensional index (conceptually
they _are_ the same thing, just optimised for different access paterns)
So as we can't use UB-Tree, we may well achieve similar result buy
using a multi-dimensional/multi-type R-tree and teach our optimiser
to use it for resolving multiple where clause restrictions simultaneously.
Of course this too may be patented. If it is not, let's hope this e-mail
will be archived and can be used as prior art to prevent future patenting
attempts :)
Another common way of fighting such patent's is patenting all possible
future improvements and then haggle with the patent holder .
I think this could be something that is effectively doable by open-source
community, at least the part of generating the ideas.
-------------
Hannu