Re: Dreaming About Redesigning SQL

From: "Anthony W(dot) Youngman" <thewolery(at)nospam(dot)demon(dot)co(dot)uk>
To: pgsql-hackers(at)postgresql(dot)org
Subject: Re: Dreaming About Redesigning SQL
Date: 2003-10-26 20:09:19
Message-ID: $xpsVWAvnCn$Ew5r@thewolery.demon.co.uk
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-hackers

In article <bn72o3$as$1(at)nyytiset(dot)pp(dot)htv(dot)fi>, Lauri Pietarinen <lauri.pie
tarinen(at)atbusiness(dot)com> writes
>Anthony W. Youngman wrote:
>
>>In article <bn4cca$dj0$1(at)nyytiset(dot)pp(dot)htv(dot)fi>, Lauri Pietarinen
>><lauri(dot)pietarinen(at)atbusiness(dot)com> writes
>>
>>
>>>Anthony W. Youngman wrote:
>>>
>>>
>>>
>>>>Fine. But MV *doesn't* *need* much of a cache. Let's assume both SQL and
>>>>MV have the same amount of RAM to cache in - i.e. *not* *much*. I did
>>>>say the spec said "extract maximum performance from the hardware
>>>>available".
>>>>
>>>>
>>>>
>>>So what's wrong with gettng a machine with lots of memory? How much
>>>does 2G of
>>>memory for an Intel-box cost now a days? Is this some kind of new
>>>ultimate sport, trying
>>>to get along with as little memory as possible?
>>>
>>>
>>
>>I presume you didn't read the bit below ... what if you have SEVERAL
>>tables, and EACH of them is a gigabyte or two in size?
>>
>OK, I get your point.

Using technology to get you out of a hole is fine. Assuming it will be
there if you need it is not. And actually, this is one of the factors
hammering the MV model :-( Technology is now powerful enough to solve a
lot of problems simply by using brute force.
>
>>>Well, if it is normalised, how easy is it for you to change the
>>>customer_id of an order? Anyway,
>>>
>>>
>>
>>Incredibly easy. Just update the "customer_id" field of the invoice
>>record. A single change to a single "row"
>>
>And I presume the system will automatically move all related stuff
>(order details etc.) into
>the same block as the new customer? How long will that take? What if
>there is no room for it there?

Well, I'd view an order as an entity. As such, I would give it its own
FILE, and your question doesn't make sense. But if the system did move
the stuff, it would be four disk accesses - read/write to delete the old
entry, read/write to save the new. As for "enough room" - well - it'll
fall over if we have a "disk full" (or it might not).
>
>>>if we stick to your example and even if we don't normalise using e.g.
>>>clustering features of Oracle,
>>>as Bob pointed out, we are getting at most the same number of I/O's.
>>>So, answer to your
>>>question: our formula is at least as good as yours.
>>>
>>>
>>
>>Except I think Bob said we could "optimise to favour *certain*
>>transactions". I think actually ANY transaction benefits. You're relying
>>on stuff that's outwith your theory, we're relying on stuff that's
>>inherent to our model.
>>
>That certainly is not true. The theory says NOTHING about how data
>should be arranged on disk.
>You are talking about how modern SQL-databases behave. The DBMS is at
>liberty to do whatever
>it pleases with the data, even save it in a PICK database. Hey, wadda
>you think? Would that be
>a good idea? We get to keep our SQL but with the speed of PICK ;-)

That would be nice ;-) But I think our two paragraphs don't connect. I
was talking about MV ...
>
>>
>>We let the hardware help us out if it can. There's a big difference. If
>>you can't get the hardware, you're stuffed. We don't need it, so while
>>we may have a hard time of it it's nowhere near as bad for us.
>>
>>And again, relational separates the physical from the logical. You're
>>being hypocritical if you call upon the physical representation to help
>>out with the (speed of the) logical presentation.
>>
>My goodness, no I'm not! Its the same as claiming that if you have a
>drawing for a house, you
>have to make that house out of paper?!?
>
>>>I want a list with all products with corresponding total sales, read
>>>
>>>
>>>from order detail e.g.
>>
>>
>>>Hammer 10000$
>>>Nail 5000$
>>>Screw 1200$
>>>
>>>How many disk reads (or head movements)?
>>>
>>>
>>
>>Actually, probably the same as you here.
>>
>
>>If we're indexed on order
>>detail. If Hammer appears in N invoices, then T = (1+N) * ST * 1.05 for
>>hammers, and the same for all the other products.
>>
>>Theory favours us, in that if a product appears X times in one invoice,
>>that's one read for us and X for you, but hardware will probably help
>>you more than us (that is, assuming thrashing cuts in) in that you stand
>>a marginally higher chance of getting multiple instances of a product in
>>any given read.
>>
>So for each product you get T = (1+N) * ST * 1.05.
>
>Now, for our SQL-DBMS, presuming that we build indexes for detail and
>product:
>
>order_detail(product_id, qty, unit_price) = 20 bytes/row
>product(product_id, product_name) = 50 bytes/row
>
>With 2 disk reads I would get
>8K/20 = 400 order detail rows and
>8K/50 = 160 product rows
>
>Since all rows are in product_id order, no need for random disk reads so
>T = 1 + N/400 + P/160 (N=number of details, P=number of products)
>for ALL products and details.
>
>And, because of sequential prefetch, we probably would not have to wait
>for I/O's at all.
>
>Really, however you calculate it, it is an order of magnitude less
>than your alternative.
>
>And please don't tell me that using indexes is not fair or not in the
>spirit of the
>relational model ;-)

Well, it does result in data being stored multiple times ;-)

And while it maybe doesn't affect the result that much, you wanted the
value? Where has that come from? What if the price changed half way
through the period you're calculating? :-) You've failed to answer your
own question, so maybe I could match you ...
>
>>>>>And: what if I was just reading customer-data. Would the same formula
>>>>>apply (= (2+N)*ST*1.05)?
>>>>>
>>>>Nope. If I understand you correctly, you want attributes that belong to
>>>>the entity "customer", not the entity "invoice". T = ST * 1.05. (By the
>>>>way, billing and/or invoice address (for example) are invoice
>>>>attributes, not company attributes.)
>>>>
>>>No, I want you to give me a list of all your customers. How many disk
>>>reads?
>>>
>>T = N * 1.05 where N is the number of customers. What do you want to
>>know about those customers? Address? Phone number*s*? Anything else?
>>That's *all* at no extra cost.
>>
>Well, no thanks. I just wanted their names this time.
>The relational alternative, with an index on customer_name, would be
>again an order
>of magnitune less disk reads.
>
Well, if you let me use an index here, I'm sorry, GAME OVER! The best
you can do would be a photo finish.

Assuming an overhead of, say, 4 bytes per index entry, the entire index
would be

Size = 4 * N + sigma(name_length) + sigma(key_length)

Okay, I've probably got some padding there as well, but so will you. And
note I didn't say N * field_length, I said sigma(name_length). ;-)

I notice that at no point have you asked where this strange 1.05 keeps
coming from. That's why I keep hammering performance ... okay, maybe
I've lost this "order detail" but it's why I keep hammering my
confidence in general. Given that your data is all ordered optimally for
answering this "detail" request, what's it going to cost you in time or
disk space to answer the request "please recreate invoice X for me"?

MV stores data efficently - look at how little space the index took :-)

It accesses data efficiently - that 1.05 is actually the "how many
places do I need to look" value for the database to respond to a
userland request, given a known primary key or index value. Okay - that
means we push back at the programmer some of the management of data
access, but why should that be solely the response of the dbms? If it
makes sense for the app to do it, then it should ... why should the dbms
have to guess at how to optimise a request if the app has all the
necessary information at its fingertips?

We're now getting into the realms of statistics - and my teacher's
attitude to stats was "you don't need it for the exam so I'm not
teaching it!" :-( So my arguments are more gut feel and experience than
proof, but experience tells me the proof wouldn't be difficult.

But surely, your requirement for grabbing data across multiple invoices
is statistically unusual. And I benefit just as much as you from any ram
being available to cache :-) although I wouldn't benefit so much from
prefetch. The probability is that consecutive requests for data are
either "can I know something else about the entity I've just looked at",
or "can I access another entity at random".

In the former case, if you've stored it in another table, it's another
request from the app to the dbms. With MV, it all came in the first
request. In the latter case, this is where my 1.05 factor cuts in - bear
in mind even for a simple btree file, this factor is only 1 for a
1-level root only file - it goes up to 1.5 when the root bucket splits
and keeps rising from there :-)

So as an engineer, here I am appealing to stats :-) But this is the real
world, and no stats? no real world! Because we have no optimiser, it
encourages the programmer to optimise - I've heard various people say
that if you want a SQL-using app to run fast you mustn't use views -
forcing the programmer to interest themselves in the db in a manner that
relational says they shouldn't. We're not interested in being able to
improve the speed at which the db can find data to respond to an app
request - with an access factor of 1.05 (actually, it's nearer 1.02 or
1.03) we consider any effort there to be a waste of time ...

Basically, the only way you can beat us in the real world is to throw
hardware at the problem - and like I said with linux and macro/micro
kernels, we can do the same :-)

>>>>>>But as I understand relational theory, such a question is completely
>>>>>>outside the scope of the theory. Seeing as it tries to divorce the
>>>>>>database logic from the practical implementation ...
>>>>>>
>>>>>The theory, indeed, does not say anything about buffer pools, but by
>>>decoupling
>>>>>logic
>>>>>from implementation we leave the implementor (DBMS) to do as it feels fit
>to
>>>do.
>>>
>>>>>As DBMS technology advances, we get faster systems without having to
>change
>>>our
>>>>>programs.

Can you improve on what I've just done? Is any improvement POSSIBLE?
>>>>>
>>>>But with MV, if our database is too large for current technology, we
>>>>kick the shit out of relational for speed ...
>>>>
>What is "too large"?
>
>>>>Don't forget. You've already said that, if nothing is cached, my average
>>>>case exceeds your best. And my case is *already* assuming that the
>>>>system is seriously stressed and struggling ...
>>>>
>It does?

Yes. I'll only be in trouble if I'm so short of ram that my working set
gets forced into swap ...
>
>>>>>When we design databases we can decouple logical planning from performance
>>>>>considerations, which, you must agree, are two separate issues.
>>>>>
>>Yes. BUT what's the point of having a database that is logically
>>perfect, and who's performance is slow to the point of being unusable?
>>
>>Don't forget - in practice MultiValue ends up with a database that is
>>*inherently* optimised such that it almost invariably outperforms an
>>equivalent SQL database, AND we don't normally have DBAs to help us
>>achieve that nirvana ...
>>
>Frankly, it may well be that PICK systems run faster and cheaper than
>relational ones, but certainly
>not for the reasons you state.
>
Well, could you optimise that index any more?
>>>>>
>>>>I can't find the post now :-( but is Christopher reading this? You know
>>>>I compared that relational system on a twin Xeon 800, to an MV system
>>>>running on a P90? Christopher made the (reasonable in the circumstances)
>>>>assumption that the relational consultants must be crap, and the MV guy
>>>>a guru. Actually, I'd come to exactly the OPPOSITE conclusion. My MV
>>>>experience tells me that MV query was probably thrown together, by an
>>>>average programmer, in 30 seconds. On the other hand, those SQL
>>>>consultants had an axe to grind and a point to prove. They couldn't
>>>>afford to let this "old fashioned" system beat them. That SQL query
>>>>would have been optimised to within an inch of its life over weeks.
>>>>Don't forget how proud they were to beat this MV system! Yet with
>>>>hardware that was so much more powerful and a query that was heavily
>>>>optimised, they had great difficulty beating a query that was thrown
>>>>together in seconds by an average MV guy (or even just a luser!).
>>>>
>>>>Don't forget. I said I am a database *engineer*. Engineers believe in
>>>>elegance, they believe in beauty. And when I look at relational, all I
>>>>see is the theorists pleading "power", "hardware", "brute force", to get
>>>>them out of trouble.
>>>>
>>>>
>>>>
>>You said that logical planning and performance are separate issues. And
>>I wouldn't expect you to address the above example in a discussion of
>>relational, because performance is irrelevant to relational.
>>
>I would have to know a lot more details to address it properly.
>Performance is irrelevant to the model.
>It's like E=mc**2. Nice theory and it actually works. But to get
>performance out of it
>(=exploding bomb) you have to solve lots of practical details. However,
>without the theory
>you could experiment for a milloin years without being able to build an
>atom bomb.
>
>>But surely, the fact that I am SUPREMELY CONFIDENT that I can get
>>superior performance from inferior hardware should give you pause for
>>thought that maybe, just maybe, the relational model is flawed from an
>>engineer's or scientist's viewpoint?
>>
>That's OK with me. But the most you can claim is that todays
>IMPLEMENTATIONS are flawed,
>and you would be 100% correct. How would you go and prove that the model
>is flawed?
>You should prove that a relational DBMS could not POSSIBLY be efficient.

Well, if the relational people insist on divorcing theory from
implementation, it's hard to see how they can prove it is efficient.
While that is exactly what I'm trying to prove for MV. Whether
relational is efficient or not is irrelevant, if I can prove MV is
efficient and you can't prove the same for relational.

If that results in running SQL over MV then we've won, I think :-) We
can do that already ...
>
>>From the mathematician's (or logician's) viewpoint I agree it's
>>flawless. But that's true of plenty of broken scientific theories...
>>
>Could you give me some other examples?

Euclidean Geometry - just look at the equatorial event horizon of a
black hole.
Newtons laws of motion - just look at Mercury's orbit.
Quantum mechanics - just look at a black hole.
Relativity - just look at quantum mechanics :-) or Schrodinger's cat.

Actually, it's probably true of pretty much all of theoretical physics
since the start of last century ... in each case the only thing wrong
with the theory is that reality just doesn't happen to agree ...
>
>best regards,
>Lauri Pietarinen
>
Cheers,
Wol
--
Anthony W. Youngman - wol at thewolery dot demon dot co dot uk
Witches are curious by definition and inquisitive by nature. She moved in. "Let
me through. I'm a nosey person.", she said, employing both elbows.
Maskerade : (c) 1995 Terry Pratchett

In response to

Responses

Browse pgsql-hackers by date

  From Date Subject
Next Message Dave Page 2003-10-26 20:18:59 Re: Call for port reports (Win32 Client)
Previous Message Dave Page 2003-10-26 17:34:08 Re: Call for port reports