On Nov 9, 2009, at 9:00 AM, Jonas Sicking wrote:
On Mon, Nov 9, 2009 at 3:51 AM, Anne van Kesteren <[email protected]>
wrote:
On Mon, 09 Nov 2009 08:12:22 +0100, Jonas Sicking
<[email protected]> 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
