How does a relational database work?
coding-geek.com
coding-geek.com
[1] http://db.cs.berkeley.edu/papers/fntdb07-architecture.pdf
The thing I love most about database engines is that there is probably more hardcore computer science per line of code than any other software system of similar scope. It is a very rich ecosystem for an algorithms and data structures geek.
For instance, you don't typically look at the size of the literals in the query when evaluating query complexity. If it's really unbounded, you probably shouldn't use a relational database.
The "problem" of malloc() function (or any other equivalent allocation stuff) is that internally manages free blocks (it is a middleman between the OS and user process -the purpose is to reduce OS calls-), if you have lots of them, dynamic memory could take time. For "malloc" I meant malloc/realloc/free, the whole kit. Those operations are not free (in most cases you're not going to have millions of allocations in one process, that was just an example of hidden things that could make your algorithm not behave like expected).
Someone told me the same on the article comments and here is the answer I gave him:
You’re right and I agree with you. When I wrote this part, I REALLY hesitated to give the real asymptotic definition and what it means for the number of operations but I chose a simpler explanation since the aim of this post is not to become an expert but to have a good idea. I hope that this won’t mislead people but I thought the real definition was too hard for a “newcomer” and not important to understand a database. This is also why I added in this part “The time complexity doesn’t give the exact number of operations but a good idea.” and said at the end of the part “I didn’t give you the real definition of the big O notation but just the idea” with a link to the real definition.
http://www.se-radio.net/2013/12/episode-199-michael-stonebra...
[1]: http://www.theregister.co.uk/2015/03/25/mike_stonebraker_win...
That's because the inner workings are really old, as in: emerged before blogging etc. was popular, hell before the internet was invented.
In the 'before/early internet days', we read books like 'An introduction to Database Systems' by C.J. Date. (I had to blow the dust off my copy to read the exact title ;)), which are more in depth than this article, but I like the article better, because it's more to the point and easier to understand. Well done!
With a relational database the complexity is hidden (more or less…) whereas with Big Data and NoSQL the developer needs to deal with this complexity himself/herself. As a result, most of the Big Data applications I’ve seen don’t work well.
A really like Big Data because it’s more complex but to be honest, most of the time my work does not required the “Big Data scale”.
The other thing document databases can offer that relational databases struggle with is taking subsets (which we use for offline sync.) [2]
[1] http://blog.couchbase.com/nosql-adoption-survey-surprises
I don't see too many use cases where having being schemaless is a good thing outside of infrastructure ease of use. If you want to store arbitrary data in a table, BJSON in postgres is very efficient and flexible in that regard, while allowing you to have a schema for the rest of the data (e.g. if you are collecting data you probably want a schema for things like name, email, timestamp, etc and then have a BJSON field to jam in whatever you need.)
The place NoSQL shines is the acknowledgement that most data is complex. Of course it often also does away with ACIDity, which is a huge disaster (EDIT: the doing-away-with is a disaster, I mean).
I don't think there are any "inherent" problems to relational or NoSQL databases, but there are many tradeoffs. The tradeoff of NoSQL databases is that complexity gets very, very difficult to pull off in a distributed fashion. So throw 99% of the indices out the window, dumb your queries down, and cache any joins or scans as much as possible. The upside, I guess, is that the "schema" is pretty irrelevant if it's not your primary key (or secondary, in some databases). But, you lose joins, schemas, subqueries, orderings, many types of transactions, etc, etc, and a lot of "free" stuff that is really only "free" for small numbers of rows per table or strong assumptions about the data.
EDIT: Clarification, spelling.
I used to be a programming language oriented person, was big into data structures and objects, but then I read Date and my mind was blown at how beautiful and expressive the relational model is -- for its intended purpose (managing data for logical integrity and ad hoc queriability).
The main issues are
1. is that many implementations don't include some features such as unions.
2. Certain things (tree traversal) have also been hard to express in older versions of SQL or older versions of Tutorial D (Chris Date's language that's closer to the model).
3. Sometimes you don't care about long term data management (i.e. ad hoc queriability and integrity), you just want programmatic data persistence with pre-baked access paths that are FAST.
4. Relational integrity features are often crude implementations that slow things down too much or require custom triggers.
5. Queriability in reality requires decent knowledge of the physical layout and indexing if you're going to make it performant
6. Most relational databases have not been built in a cloud native era where we assume distribution across ephemeral disks and compute
So... great mathematical model, great way to think through and organize your data for no ambiguity, but the practical implementations leave a lot to be desired.
The problem is that "my data is too complex for the relational model" often means "I haven't thought through my data". Things like maps, unions, ordered sets, N-ary relationships, graphs and trees, are actually quite straight forward to represent in relations. The challenge is many of the lessons and arguments for this are trapped in books from the 70s-90s, not on the Web.
Firstly, it should be made clear to people that SQL is not truly relational, and a lot of the things people dislike about it are nothing to do with the relational model and more to do with its late 70s, early 80s heritage. It was thrown together at a time when business systems were still very focused around COBOL.
The second thing that people are not picking up on is that the industry _already_ went through a pre-sql "nosql" phase in the 60s and 70s when network and hierarchical databases were the norm, and the relational model was developed to deal with the perceived faults those systems had: an enforced topology which could not easily rearranged at query time, lack of rigor in modeling, lack of standardized modeling concepts and notation...
Finally, I did find in previous jobs certain uses for nosql systems -- very low latency high throughput quasi-realtime systems that deal with very small bits of simply structured data and need to distribute it widely across a cluster. For that I used Cassandra (tho I understand now that there are successors that are better).
What I don't get is the point of systems like Redis or MongoDB which don't offer a compelling distribution implementation and simply replace the fairly well understood quasi-relational model of SQL with their own ultimately inferior graph/network/hierarchical models.
Btw, to me the point of Redis and Mongo is a very fast distributed dictionary. They're data structure servers, for when you want to persist and share data structures across processes, not "manage information". It depends on your goal.
I just don't think that it naturally reflects the data structures people use, and we should be willing to make the computer do the work, rather than humans.
That is my main issue. I use Cassandra over relational firstly for its linear scalability and multi-master-esque HA. But even ignoring those, I understand exactly what is being scanned and what is not, I don't have to fight with an optimizer at runtime based on several parameters.
For example, when I started in Big Data, in less than 3 weeks I was able to optimize some batches just because I read the documentation of the framework used (PIG in this case) and read a small part of the source code to dig deeper. And it was not some touchy optimizations: I used in-memory joins and reduced the number relations in the scripts to reduce the generation of Hadoop jobs (which led to batchs 4 times faster).
There are often problems with our HBase database because it’s often overloaded (I’m not an IT operator so I can’t give more details) and no one really masters this database whereas it’s in production since 2014.
I do understand that in some cases a NoSQL database is mandatory and like you I like to understand what I’m doing. But:
- I’m not working in Silicon Valley
- Most of my co-worker are not geeks (and I respect that)
- It's VERY hard to find guys with real Big Data or NoSQL skills (this comes from a French technical recruiter)
So, if the geek part of me loves Big Data and NoSQL, the rational part prefers using well known technologies. If NoSQL and Big Data becomes mainstream and more known then the rational part will love them too.
I don't believe NoSQL means no validation. In fact, I've found things like Cassandra CQL actively prevent me from running expensive queries unless I opt in (e.g. ALLOW FILTERING). Validation is DB specific, but I don't think it's fair to say it's a footgun in NoSQL any more than in SQL databases.
As for choosing what is known by the employee market, I personally don't choose technologies that way (but I do choose based on maturity of course). I rarely look for skills as much as the ability to learn new ones, but I understand it can be a pipe dream when in the market for juniors.
Teradata, Oracle, PostgreSQL for example are reasonably complex databases to cluster and manage yourself. Just as easy/hard as setting up HDFS and installing Hive. In all cases people who are at big data scale are buying OTS solutions e.g. Cloudera appliance. They aren't rolling their own.
And if you are using Hive then I can understand why you are not feeling the buzz. But play around for Spark for a while and it's easy to see the future. Being able to write Scala/Python/SQL/R against a data set that can be anywhere from 100MB to 100PB without any changes is pretty compelling.
It's really understandable, very straight forward, even if a lot of it refers to SQLite v2, it still seems very relevant.
Use lmdb for db library.
Use redis for the protocol.
Use twitter.gizzard for replication+sharding.
Boom! Your own webscale nosql!
That's a pretty bold statement...
Very thorough explanations though!
If you liked this article, maybe you'll like my article on Shazam. I used the same pattern: I start from the basics of sound processing and computer science and finish with an in-depth explanation of Shazam.