Re: What do we mean by "parking" Web Database?

On Nov 9, 2009, at 9:00 AM, Jonas Sicking wrote:

> On Mon, Nov 9, 2009 at 3:51 AM, Anne van Kesteren <annevk@opera.com>  
> wrote:
>> On Mon, 09 Nov 2009 08:12:22 +0100, Jonas Sicking  
>> <jonas@sicking.cc> wrote:
>>>
>>> * SQL doesn't give any performance guarantees. Many times people  
>>> tweak
>>> their SQL in order to get the implementation to use a desired
>>> evaluation stategy. This won't work in the likely event that  
>>> different
>>> implementations use different evaluation strategies for the same
>>> query.
>>
>> From what I understood so far this would also be the case with the  
>> Web
>> B-Tree Database proposal (maybe even more so given that all SQL
>> implementations currently have the same underlying engine). Am I  
>> missing
>> something?
>
> I don't think this is the case with the SimpleDB proposal. I think
> it's possible to for example guarantee that a lookup based on an index
> is O(log n) on the number of items in that entity store. Nikunj, is
> this correct?

Theoretically, you should get a small single digit as the complexity  
for B-tree look ups. In big-O notation, you are right - it is O(log  
n). The base for this log is typically the number of keys that would  
fit on an internal page, which would be approaching 1000. Therefore,  
practically, even "million key" stores would have a very small  
complexity.

A hash database would have the complexity of O(1), however, this is  
currently not in WebSimpleDB.

The market can figure out what guarantees are possible and desirable.  
Providing guarantees at the API level is the wrong thing to do, IMHO.  
This is because ultimately, a poor implementation can do in a good  
design.


> Anne, are there any specific operations you have in mind where you
> don't think we can give timing guarantees?
>
> / Jonas
>

Nikunj
http://o-micron.blogspot.com

Received on Monday, 9 November 2009 22:26:12 UTC