Re: Re[2]: [HACKERS] Fwd: Joins and links

Leon <leon(at)udmnet(dot)ru> writes:
> I'm afraid that's mainly because fields in Postgres have variable
> length and after update they go to the end of the table. Am I right?
> In that case there could be done such referencing only with
> tables with wixed width rows, whose updates can naturally be done
> without moving. It is a little sacrifice, but it is worth it.

No, you are not right. Tuple updates can *never* be done without
moving the tuple, because the old tuple value must not be overwritten
until and unless the transaction is committed. (Under MVCC, it may
need to stick around even longer than that, I believe.) Thus, a tuple
update would require an update (and move) of every referencing tuple,
which could cascade into updates of tuples that reference those tuples,
etc.

But the really serious problem is simply that of finding the tuples
that reference the tuple you are about to update. This is relatively
straightforwards for indexes --- you just compute the index value for
the old tuple and probe into the index with it. When the tuples might
be anywhere in the database, there are no easy shortcuts. I think the
only way would be maintaining an index listing all the referencing
tuples for every referenced tuple. This would be a bit of a bear to
maintain, as well as a source of unwanted blocks/deadlocks since it
would be a bottleneck for updates to *every* table in the database.

T> Finally, I'm not convinced that the results would be materially faster
T> than a standard mergejoin (assuming that you have indexes on both the
T> fields being joined) or hashjoin (in the case that one table is small
T> enough to be loaded into memory).

> Consider this: no indices,

You'd still need indices --- see above

> no optimizer thinking,

You'd still need to run the optimizer to decide whether you wanted to
use this technique or some more-conventional one (unless your proposal
is to remove all other join mechanisms? Rather inflexible, that...)

> no nothing! Just a sequential number of record multiplied by
> record size. Exactly three CPU instructions: read, multiply,
> lookup. Can you see the gain now?

If you think it takes three instructions to access a tuple that's out
on disk somewhere, I'm afraid you're sadly mistaken.

regards, tom lane