Re: The TransRelational Model: Clarifications

On 13 Nov 2004 16:44:37 -0800, lajos.nagy_at_gmail.com (Josh Hewitt) wrote:

>First of all, my analysis is just a preliminary, back-of-napkin type
>calculation that I did in order to establish the feasibility (or lack
>thereof) of implementing the relational model using the TRM.

Then why you gave striking conclusions if the analisys was incomplete?

> My
>reasoning was that any new proposal for storage organization should prove
>itself on some simple examples before checking it against more complex
>ones.

Should prove what?

Even if a new proposal is significantly worse by a constant factor on the simplest cases, it could be very interesting whether it is a lot better on the complex cases where the traditional approaches perform horribly.

Most practicioers tend to avoid complex queries due to the performance issues. An implementation which makes performance independent to the complexity of the queries would be an important advance.

> Hence the lack of queries involving JOIN, SUMMARIZE, etc. In my
>opinion, no performance analysis that is based on simple queries should
>be discarded on the grounds that it has not taken into consideration all
>other kinds of queries.

This is true, but an analysis based in TWO almost identical trivial retrieval queries is not serious.

> If the analysis is valid then the performance
>concerns are real and one cannot proceed until those concerns are
>resolved in some satisfactory manner.

Even if the rest of the analisys were correct (and it is not), the average performance could be better than with the traditional approach.

>In fact, the two basic functions that I put to a test in my analysis
>(lookup and record-reconstruction - RR) are such fundamental elements
>that very few useful queries can be formulated without them.

But you only analize one of the many possible embodiments.

The queries of your examples don't need a reconstruction table at all because you restrict over a single attribute.

> Actually, I
>cannot think of a single query that does not involve lookup and/or RR.

-Queries on tables with merged columns.
-Queries on unidimensional tables.
-Queries on tables with only one sorted attribute.

>The performance of lookup and RR cut to the heart of any storage
>organization so negative results in this area are not something that
>can be handled lightly.

Unproved statement.

> All in all, I think that even a preliminary
>analysis that does not cover every aspect of a new system can be of
>importance.

You didn't say that your conclusions were preliminar, nor you said that your analisys don't apply to main memory DBMSs.

It is rather clear that the TRM as described by Date and by the patent is a candidate for implementing main memory DBMSs. If you want to implement a disk based DBMS you have to solve several issues first. Date says that they are solved but he says nothing about how.

I tried to solve the issues myself and it is very feasible. I changed many of the algorithms but the fundamental idea is still the same: value tables and reconstruction tables. IMO the essence of the TRM is this and only this.

>Now this is a very good observation. In fact, closer examination of
>the question of indexing reveals an interesting feature (?) of the
>TRM: that the Field-Value tables _cannot_ easily use B-Trees or
>Hashing for speeding up searches.

Very vague. We could say the same about the traditional implementations. DBMS development was never an easy job.

But to use the hashing technique described in the patent would be very easy.

> In fact, the core ideas of the TRM
>hinge on the positional addressing (meaning that they behave like
>arrays) capability of the FV and RR tables.

So what?

We can build trees "indexed" by position.

>First, an important remark: the patent itself does not mention the
>usage of B-Trees.

Nor forbides it.

> I thought that it might have been just an oversight
>but if one sits down in front of a piece of paper and tries to think
>about how the columns in the Field-Values table could be indexed using
>B-Trees (or Hashing, which is even worse in this case, as we will
>see), one will be surprised to find that this cannot be easily done!

I agree, it is not very easy, but nobody said that computer science is always an easy job.

>The columns of the Field-Values table cannot be indexed using B-Trees
>without significantly modifying the TRM itself.

This is your opinion. IMO the essence of the TRM are the FV and RR tables, and nobody said that they must be on the lowest implementation level.

>In my opinion, the reason for using a positional approach (ordered
>arrays) for links in the TRM is because other approaches (B-Trees) are
>even worse.

Your analisys is naive and you make many unsupported assumptions.

There are many other ways to implement the tables besides the ones you mention.

>The analysis assumes 100 records per page. What page size does this
>imply? Well, there are eight attributes in the EMP relation: E#,
>ENAME, HIREYEAR, SALARY, DEPT#, EMAIL, ADDRESS and PHONENO. The
>following table gives (quite conservative) estimates on the _average
>stored sizes_ (not maximum sizes) of these attributes (measured in
>bytes):
>
>
>E# 4
>ENAME 16
>HIREYEAR 2
>SALARY 4
>DEPT# 4
>EMAIL 20
>ADDRESS 40
>PHONENO 10
>
>Total 100 bytes

This way of calculating the page size is biased to the traditional approach.

This is a completely inadecuate way to calculate the page size on a TRM implementation.

For instance if you have 6000000000 tuples (the whole mankind) you may store all the salary value table in a page of perhaps few MB which would be loaded in a hurry using a modern disk and it would be a very little table for a modern computer.

The cost of a 16Kb disk transference multiplied by 1024 has nothing to do with the cost of a 16MB disk transference.

>are always open for subjective interpretation, I think that it is safe
>to say that in the year of 2004 a disk page size of 16KB cannot be
>considered little.

I was talking about the memory page size, the block size.

>Closing remark on the page size issue: I deliberately formulated my
>cost analysis using disk-block transfers as a performance measure
>because the general consensus is that disk I/O makes up for by far the
>bulk of the execution cost in traditional query processing
>environments.

Traditional means outdated here.

Your references are rather outdated, the bulk of the execution cost is moving to the memory I/O very fast.

The disk and memory technologies changed a lot in the last decades. Many of the traditional analisys are not valid today.   

>Before going into details let's make one thing clear: in the analysis
>I considered using the TRM for implementing a disk-based relational
>DBMS.
OK, you should have said that before.

The TRM as described by Date seems to be more intended for implementing main memory DBMSs.

> Disk-based here means that either the size of the database is
>larger than available memory, or that updates must be written to disk
>to ensure the durability of transactions (ACID).

Wrong. Many main memory DBMSs use disk based logs.

>My analysis was based on position (1): ignore caching for a moment and
>let's see how the two contestants perform. (Surprisingly, this is an
>approach that is quite often taken in the field.

It was common when memory was very expensive. This is not a common approach today when machines with 16GB of RAM are affordable to almost any company.

Columns of more than 16GB are not very common in small and medium company's database.

Big companies can afford machines with a lot bigger memories.

> For the simple
>reason that if one approach is proved to be better than an other one
>without caching then turning on caching usually will not change the
>situation significantly.)

Unproved statement. And even if it were true, the situation could change a lot in the specific case of the TRM which is not an usual approach.

> Lookup
>
> Finding a record based on the value of one of its attributes is
> performed using binary search (as I have tried to show previously
> the TRM cannot really use other search techniques.) Binary search
> is a random access search. There is absolutely no guarantee that a
> disk block fetched in a previous step of the search will be needed
> in subsequent steps. In other words, if 20% of the relation is
> cached then the probability that the next block accessed by the
> binary search will be found in cache is going to be close to 20% on
> average.

You are not considering that a value table is often substantially smaller than a relation. If the 20% of the relation is cached is very possible that the 100% of the value table is cached.

But even if the 0% of the value table is on the cache, if we are using a B-Tree like structure for the value table and the inner nodes are cached the cost for a lookup would be always 1 block.

As you know, the memory needed to cache the inner nodes is orders of magnitude smaller than the memory required for the whole tree.

> Record-Reconstruction
>
> The figure shows reconstructing one of the Johnson's. Realize that
> when we reconstruct the other Johnson his HIREYEAR, SALARY, and E#
> attributes will be very likely _completely_ different from the
> previous Johnson's. This translates to the fact that caching does
> not help much in this situation because data access does not show
> _locality_.

Again to cache the inner nodes of the RR trees would help a lot, and several columns probably would not need to be sorted.

> If we fetch the block that contains that attribute
> value 7000 for the SALARY, we might _never_ need this block again in
> the reconstruction of the rest of the result set. To be more
> precise: if 20% of the relation is cached then the probability that
> the next block accessed by the record reconstruction will be found
> in cache will be close to 20% on average.

Again the same, if few columns are sorted then the reconstruction table would be very little and could fit in the cache easily.

The most recent used blocks would be probably mantained on the cache for all the query processing so the probability of finding a block in the cache would increase.

>To summarize, the TRM does not have the nice property of 'locality of
>access' which translates to the fact that its performance will only
>increase linearly as we increase the proportion of the relation that
>is kept in the cache.

So to analize the effect of the cache is fundamental.

In many if not most practical cases the most part of the queries only affect to a little part of the relations, and there are many attributes that don't need to be indexed (or sorted).

>Inserts
>-------

>is just an _additional_ cost. In the example I gave I analyzed the
>insertion of a new Employee record into the EMP relation. Since an
>Employee record has eight different attributes, the TRM has to insert
>_each and every_ attribute value into its corresponding sorted set.

Wrong again. This would be comparable to a traditional approach with all the attributes indexed, with several multi-attribute indices.

>The cost of performing this search is in itself prohibitive:
>
> ACNT * log (|EMP|/ACNT) = 8 * log (125) = 8 * 7 = 56 blocks

This is not prohibitive. Only slower by a little constant factor.

It would be compensated by an orders of magnitude gain in complex queries.

>No matter what indexing technique the TRM chooses to use it will have
>to perform a search followed by an insert for _each and every_
>attribute value.

No, the number of attributes to "sort" is optional, you might sort 0 attributes and then you would have something very similar to a traditional table.

> So even if it uses a B-Tree on each attribute value
>(as we have seen, this would be quite hard to do so) and we assume 2
>block accesses for each B-Tree search, the total cost comes to 8 * 2,
>that is 16 blocks.

And this is very affordable.

It would be 8 blocks caching the inner nodes, and it would be the same with the traditional approach and 8 indexed attributes.

>My goal with these posts is not to bash the TransRelational Model.
>What I would like to see instead is a healthy debate that might result
>in better storage organizations for relational DBMSs.

Ok, you second post was a lot better than the first.

Regards Received on Mon Nov 15 2004 - 20:58:01 CET