Re: Object databases beat joins

Carl Rosenberger wrote:
> andrewst wrote:
>
> They may not fit into RAM, I am afraid. Alright then, if you have
> a perfectly balanced tree on your hard disk, you will need at least
> 31 (2 ^ 31 = 2147483648) reads to your disk and 31 compare operations.
>
> An object database typically references objects directly. Access time
> is constant:
> Walk one pointer!
> ...no matter if you have 10 atoms, 2 billion, or 42 fantastillions.
> You can get away with one singel read operation.
> That's the best performance you can get.

Sorry Carl, but this is really a bad example. like Mikito said, a B-tree needs only 4 to 5 levels for this.

But you can beat even this, if your dbms internally optimizes its structures for foreign keys. than a join using a foreign key would be also virtually a one op. Thus you can have constant access time too, but without loosing the flexibility of the relational theory.

I implement this technic in our Gonzales database server (it is NOT a relational database, but you could use this technic in a pure relational system as well).

As a side effect we are able to write queries where we use the foreign key as an implicit join:

select from a_table
where b_key::c_key::value = "xy"

instead of

select from a_table, b_table, c_table
where a_table.b_key = b_table.id and b_table.c_key = c_table.id and c_table.value = "xy"

b_key is foreign key to b_table.id
c_key is foreign key to c_table.id

the operation :: dereferences a foreign key to the row where it "points" to.

How this query is operated is job of the optimizer, because not necessarily is the way from a_table to b_table to c_table to value the fastest - even if the join in this direction is cheap.

currently our syntax for these implicit joins is limited to a special "id-type". But there is no reason not to implement it in a more general way.

Viele Grüße,

Adrian Veith. Received on Fri May 16 2003 - 12:24:44 CEST