With just one Disk I/O
Date: Thu, 24 Nov 2005 18:34:45 GMT
Message-ID: <9Jnhf.5107$wf.4723_at_newsread3.news.atl.earthlink.net>
Over in another thread, DonR points out, with emphasis, that Pick can retrieve a record with just ONE disk I/O. I don't blame Don for drawing attention to that point. It's one thing that can make Pick applications run blazingly fast under certain circumstances.
Caution: long post follows.
Here, I want to draw attention to how a (purported) relational DBMS can do the same thing. My reference is to DEC Rdb/VMS, as the product stood in the summer of 1994. Over 50% of the current code base was written since the product came under Oracle, so my description may be out of date. But it should serve for illustrative purposes. I believe that DEC Rdb/VMS IS a relational DBMS, but some theoreticians may dispute that point. Whatever.
There is a unit of data that Rdb reads in a single disk read. It's called a "Database Page". The address in filespace of a database page can be computed by simple arithmetic from two numbers, called the Storage Area Number and the Database Page Number. Rdb computes the address in filespace, and the operating system fetches the appropriate disk block(s).
A database page can contain a variety of what I will call, for present purposes, a "record". A record can contain a table row, a table row fragment, an index node, a hash bucket, a duplicate node, a system record, or some other things.
A database has been built and loaded for fast lookup of single orders.
The following query comes in...
SELECT *
FROM ORDERS O, ORDER_ITEMS I
WHERE O.ORDER_NO = I.ORDER_NO
AND O.ORDER_NO = '1234567';
In the real world the literal order number would have been provided by a
program variable, but that need not concern us here.
The optimizer looks at the query, looks at the metadata (which is in memory due to a prior request). The metadata includes some volume statistics concerning the size of tables. The optimizer now comes up with a strategy. We've burned a little CPU time, but no Disk I/Os.
Now, Rdb hashes the order number in order to come up with a target page number, in a storage area devoted to hash buckets that index ORDERS on ORDER_NO. It then reads this entire Database page (along with a few adjacent pages) into a memory buffer.
It looks for the relevant hash bucket, and by golly, there it is! (Well, not by golly.... by design... I'll just say "by design" from here onward). The hash bucket relates the key value '1234567' to the DB address of the record containing the table row.
By design, it's the same page just read! With no more disk I/O's it now has the contents of ORDERS for the desired row.
It now looks up in another index, the value '1234567' in a hashed index on ORDER_ITEMS. By design it hashes to the same database page we already read! And there's the second hash bucket, by design! This time, the index permits duplicates, (obviously), and the key points to a "duplicate node" somewhere in database land.
Where? In the same page we already read! (I hope you're starting to get the point). The duplicate node contains pointers to six records containing table rows. Why? because this order had six items in it.
Where are these six ORDER_ITEM rows? You guessed it! They are in six more records of the database page we already read! Well, no, actually one of the items was in an adjacent database page, but it turns out that the one disk I/O we did read that page into memory, as well as the target page.
Now Rdb completes the join, and returns the result to the program. Total Disk I/O's? One!
Compared to Pick, it's probably burned more CPU time, but's that not the point, here.
Now let's try this query:
SELECT *
FROM ORDERS O, ORDER_ITEMS I
WHERE O.ORDER_NO = I.ORDER_NO
AND O.ORDER_DATE BETWEEN '1-NOV-2005' AND '30-NOV-2005';
A disappointing 200 disk I/Os. Much slower, but still lots better than a
sequential scan of the order table, which would have required about a
million I/Os.
Moving on, we try this:
SELECT *
FROM P.PRODUCTS, ORDER_ITEMS I
WHERE P.PRODUCT_ID = I.PRODUCT_ID
AND P.PRODUCT_ID = '98765';
Again a disappointing 50 disk I/Os. The indexes aren't hashed, and the
tables aren't colocated with the indexes.
Too bad.
But all three queries are logically correct, and give logically correct results. The designer optimized the physical design for the most urgent query, at the expense of deoptimizing for the less urgent ones. And it's all done without stepping outside of the SQL-Relational framework!
My point is that comparing the relational data model with the Pick data model can be done without prejudice due to the ability of eith one to get the necessary data in one disk I/O. It can be done with either Pick or Rdb! Received on Thu Nov 24 2005 - 19:34:45 CET