Lets get physical

From: paul c <toledobythesea_at_oohay.ac>
Date: Thu, 15 Jun 2006 17:44:16 GMT
Message-ID: <Q%gkg.33827$IK3.26838_at_pd7tw1no>

Like some others here (as best as I can recall), I've puzzled over comments such as the TRM not being a physical layer. Also, I noticed recently that the last of the LZW patents is about to expire. Not that they're related but along with the latest jibe about physical matters, it gets me to thinking about implementations again.

I can accept the assertion about TRM as being a kind of indirection as long as I can envisage direct structures and algorithms for implementing it. TRM's ideas may well go deeper than I can express but what stuck with me about trying to implement it is that as far as deleting and insert are concerned the nature of OS storage allocation, whether on disk or in ram is such that lots of pointer chasing or re-allocation seems to be needed, if one avoids a "row-image" mapping. (When I say pointers, I don't necessarily mean the familiar 32 or 64 bit ones.)

In blunt terms, I couldn't see how a physical implementation of TRM could avoid having two values for some equivalent of pointers for each
"row-column intersection", one to associate a value within a "row" or
"tuple" and another to place it within some ordering. Not counting the
values themselves, all those pointers seem to me to result in a physical size that is probably similar to one that used, say, a btree index for every column of a row-image table. Whether the indexes are sparse or dense or whether they have shortcuts to avoid repeating identical values seemed irrelevant as far as comparing a TRM implementation with say, a so-called column-based store.

What I read about TRM seemed to echo my impression, if only because of the two logical structures it gives.

At the level or disk or ram, it seems to me that for a db of unpredictable size the usual fragmentation wastage will arise. (Also, depending on the number of columns, insert and delete time could be quite lengthy for an implementation that tries to minimize storage.)

Finally, I wonder whether anybody has thought of implanting an LZW or other compression variation in conventional indexes.

Whether TRM is fundamentally a new idea or not doesn't seem to be a question that its proponents are going to give us an answer for. If somebody could show that at a physical level, it has no overriding advantages, I think that would be useful as I suspect there are others besides me for whom it would save time. Of course if somebody could show the opposite, that might be even more useful.

p Received on Thu Jun 15 2006 - 19:44:16 CEST

Original text of this message