I'm a student working on my thesis in database theory and looking for some research in the field of formal models of database performance and couldn't find any works in this area. I'm interested: what are the most fundamental database performance parameters and mathematical criterions for the next things: transaction execution, query performance and efficiency (evaluation, parsing, execution) and maybe some more and not just: "this query takes 50 ms to run". I want to formulate fundamental (mathematical) performance criterions, which I can use to compare on the most general (abstract) way different database models and technologies.

  • 2
    $\begingroup$ If downvoting, please consider leaving a comment on how to improve the question. $\endgroup$ – usul Feb 21 '15 at 5:43

Some of the performance-related things you can objectively compare between different databases:

  • IO complexity and computational complexity of different queries. E.g. there are different ways to do joins, sorting, different kinds of indices (including "no indices"), with objectively different asymptotic complexity. There are also column-oriented and row-oriented ways of organizing data, with different complexity of fetching a subset of columns.
  • Caching behavior: is there a performance cliff when the data stops fitting in a particular level of memory hierarchy (e.g. in RAM), or does it degrade gracefully? The second kind is called "cache-oblivious"; one example is TokuDB.
  • Presence or absence of certain types of concurrency or conflict resolution in transaction processing: e.g. if the database doesn't support MVCC, then it cannot concurrently execute transactions reading or affecting the same row.
  • For distributed databases, you can look at how consensus between replicas is achieved, and when is an update considered "done" (acknowledged) - this has huge impact on read/write throughput and latency. See e.g. Cassandra architecture overview for the "R + W > N" rule (I don't have an academic source on the top of my head); for a radically different approach, look at Google's Spanner.

Hope this helps.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.