High scalability: SQL and computational complexity
rethinkdb.com
High scalability: SQL and computational complexity
1–10 of 21 posts
Re: High scalability: SQL and computational complexity
#2"Given modern trends, if a given query isn’t scalable vertically, it also isn’t scalable horizontally, which makes SQL fundamentally unscalable, period."
Re: High scalability: SQL and computational complexity
#3"Given modern trends, if a given query isn’t scalable vertically, it also isn’t scalable horizontally, which makes SQL fundamentally unscalable, period."
That was the line that jumped out at me too. The justification: information grows exponentially, machines grow polynomially, therefore horizontal scaling doesn't help - the information growth is still exponential - and therefore vertical scaling is the same as horizontal scaling.
Seems rather unrealistic and academic to me.
The point about a query language that provides a complexity guarantee is more interesting.
Re: High scalability: SQL and computational complexity
#4"Given modern trends, if a given query isn’t scalable vertically, it also isn’t scalable horizontally, which makes SQL fundamentally unscalable, period."
That was the line that jumped out at me too. The justification: information grows exponentially, machines grow polynomially, therefore horizontal scaling doesn't help - the information growth is still exponential - and therefore vertical scaling is the same as horizontal scaling. Seems rather unrealistic and academic to me. The point about a query language that provides a complexity guarantee is more interesting.
I agree. That quote applies to all possible queries, especially the worst-case ones that touch every record in the database. Obviously such queries don't scale in any paradigm, and thus they aren't useful for comparing systems. Small queries are more interesting IMO, because they scale on some systems but not others.
Re: High scalability: SQL and computational complexity
#5You can't rule out queries to suit your implementation; if the data is needed and can't be computed within the constraints, then the user will just run multiple queries to get that data.
For example, a key-value store can run simple lookups fast - O(1) - but if you want to run a complex analytical query you'll be running lots of those queries - maybe O(N) because you have to fetch all the data. You'd be better off simply allowing one O(N) (or better) query, rather than dealing with the overhead of N O(1) queries.
Disallowing some fraction of queries doesn't magically make your database scalable, it's just an accountancy trick.
Re: High scalability: SQL and computational complexity
#6You can't rule out queries to suit your implementation; if the data is needed and can't be computed within the constraints, then the user will just run multiple queries to get that data. For example, a key-value store can run simple lookups fast - O(1) - but if you want to run a complex analytical query you'll be running lots of those queries - maybe O(N) because you have to fetch all the data. You'd be better off si…
You don't allow N O(1) queries, you allow k O(1) queries, where k is a small constant independent from N. It is simply a physical reality that a massively scalable realtime system cannot run anything other than a small number of log(N) queries. You can't run N O(1) queries or one O(N) query - there is just no way to evaluate it in real time. If you need to present the result of such a query to users, you can run it as an analytical query and cache it, but you will not be able to run it on every request.
Re: High scalability: SQL and computational complexity
#7You can't rule out queries to suit your implementation; if the data is needed and can't be computed within the constraints, then the user will just run multiple queries to get that data. For example, a key-value store can run simple lookups fast - O(1) - but if you want to run a complex analytical query you'll be running lots of those queries - maybe O(N) because you have to fetch all the data. You'd be better off si…
You don't allow N O(1) queries, you allow k O(1) queries, where k is a small constant independent from N. It is simply a physical reality that a massively scalable realtime system cannot run anything other than a small number of log(N) queries. You can't run N O(1) queries or one O(N) query - there is just no way to evaluate it in real time. If you need to present the result of such a query to users, you can run it a…
But the users are going to issue those N queries while you're still at the whiteboard talking about big-O notation.
Exposing a full query language to the database system means that you have the opportunity to optimize the query fully. Limiting the query language only limits your ability to optimize, so you won't even be able to explain to the user that there's an alternative way to get their answer without bringing down the database.
Are there limitations of databases such that it is possible to come up with better query execution strategies than the database can figure out automatically - of course there are! But in that case, fix the query optimizer or fix the database. Don't try to solve the problem by redefining it.
Re: High scalability: SQL and computational complexity
#8Earlier quoted context omitted.
You don't allow N O(1) queries, you allow k O(1) queries, where k is a small constant independent from N. It is simply a physical reality that a massively scalable realtime system cannot run anything other than a small number of log(N) queries. You can't run N O(1) queries or one O(N) query - there is just no way to evaluate it in real time. If you need to present the result of such a query to users, you can run it a…
But the users are going to issue those N queries while you're still at the whiteboard talking about big-O notation. Exposing a full query language to the database system means that you have the opportunity to optimize the query fully. Limiting the query language only limits your ability to optimize, so you won't even be able to explain to the user that there's an alternative way to get their answer without bringing d…
If the query language is designed with this in mind, the compiler would detect that a non-realtime query is passed to a database marked as realtime and would throw an error. Of course the user could issue N realtime queries from within a host language, but that would involve really trying to work against the database. A good analogy might be CORBA/DCOM vs. SOAP. In DCOM days it was easy to call many different functions while being oblivious that each call requires a network roundtrip. Most programmers made this mistake most of the time. With SOAP, you can still work this way, but it makes the likelihood of this happening in practice significantly lower because it exposes the issue to the programmer.
Regarding your argument of a fuller optimization, presumably a well designed query language would be flexible enough to allow the user to express every possible realtime query (assuming this is theoretically possible), so the user doesn't need to combine smaller queries via host-language trickery. People have been trying to fix the optimizer for decades, but most production optimizers still have plenty of edge cases. Perhaps redefining the problem is exactly what the doctor ordered?
Re: High scalability: SQL and computational complexity
#9Earlier quoted context omitted.
But the users are going to issue those N queries while you're still at the whiteboard talking about big-O notation. Exposing a full query language to the database system means that you have the opportunity to optimize the query fully. Limiting the query language only limits your ability to optimize, so you won't even be able to explain to the user that there's an alternative way to get their answer without bringing d…
If the query language is designed with this in mind, the compiler would detect that a non-realtime query is passed to a database marked as realtime and would throw an error. Of course the user could issue N realtime queries from within a host language, but that would involve really trying to work against the database. A good analogy might be CORBA/DCOM vs. SOAP. In DCOM days it was easy to call many different functio…
Nice theory, but consider that the N+1 problem is so widespread that it actually has a name, and I think you'll realize that people are a much harder problem than you think. And this isn't even a place where SQL is at all problematic! Perhaps this supports your DCOM argument though, in that it's the abstraction layers that really cause the problem.
That said, it's great that you're re-examining the problem; that's how progress is made.
Re: High scalability: SQL and computational complexity
#10Laboratory Evaluation, wholesale" rel="nofollow">http://www.shoesgroups.com/reebokanswer-c-70.html>wholes... reebok answershoes, pump
technology can support the players affect the soles of the feet and legs friction weight, these href="wholesale" rel="nofollow">http://www.shoesgroups.com/reebokanswer-c-70.html>wholes... reebok answer shoes are the perfect combination of speed
and passion. This wholesale reebok answer shoe has launched an all-star red, black and the world, these two limited edition
colors. Series, as fans should not miss the fine, We are free shippmtand a week to your door.004