9 ms·

Data denormalization is broken

171 points by endswapper 10y ago

swlkr 10y ago
I can see why the normalized approach is difficult to make performant, but it seems much simpler.
- arjunnarayan 10y ago
  You're correct on both counts. A normalized approach is simpler, and is more difficult to make performant. So you start there, but as you scale, it becomes more and more untenable for your users as your latency goes up the wazoo. Thus, eventually your app hits a scale where you have to rewrite your code to explicitly denormalize things and maintain the denormalized views yourself. This makes any feature addition/backend update horrendously complicated, and everyone's life difficult. You slowly start losing consistency which causes "glitches in the matrix" for your users. To stop that you start adding in transactional semantics yourself at the application level, checking and cross-checking everything, and doing abort/restarts, and then finally, in an analogue to Greenspun's tenth rule[1], your application starts to contain an ad hoc, informally-specified, bug-ridden, slow implementation of a distributed database. I think there's a CircleCI blog post parody hidden inside this comment, but I'm not clever enough to materialize it[2]. [1]: Any sufficiently complicated C or Fortran program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp., https://en.wikipedia.org/wiki/Greenspun%27s_tenth_rule https://en.wikipedia.org/wiki/Greenspun%27s_tenth_rule [2]: A reference to https://circleci.com/blog/its-the-future/ https://circleci.com/blog/its-the-future/
- jacques_chester 10y ago
  Broadly: Normalised data is more performant on write, because for each piece of state, there will be one and only one place to store it. It's less performant on read because you are constructing logical deductions out of a lattice of tiny pebbles of truth. It takes time to find, filter, sort and project those. Denormalisation "works" by skipping to a read-optimised schema for those applications where reads greatly outnumber writes. Which is very many. As an aside, "denormalised" doesn't have to mean "unstructured chaos". Do As Thou Wilt isn't necessarily the law of denormalising. There are well-studied, widely-used denormalisation techniques under the heading of "dimensional modelling". It's just that most of these discussions are dominated by web folk, not data warehouse folk. The shoutout to Event Sourcing is promising, given the interaction with the CQRS pattern. In short: read schema and write schema have different demand and performance characteristics. So split them up.
  - LgWoodenBadger 10y ago
    I don't know that you can always conclude that normalized data is more performant for writes. Take for example the case where your normalized write consists of 5 insert statements into 5 tables, instead of 1 insert into 1 table that you'd do with a denormalized write.
    - jacques_chester 10y ago
      As always, consult your doctor, accountant, lawyer and profiler.
jkkramer 10y ago
One technique that can be useful is imposing domain-specific restrictions, then passing responsibility down the chain. For example, most people only have a handful of recent conversations; can you get away with ignoring distant-past conversations when it comes to read/unread marking? If so, you could send recent normalized data to the frontend and let it derive the unread state client-side. React has some nice tools for efficiently deriving state from server-sent data. This isn't always the best solution, but it's something to consider.
- extrapickles 10y ago
  Unless the amount of data you need to transmit is large, I always prefer that approach as it enables other UI features without any additional network trips by the client. Also, it lets one use the same mechanism for multiple uses (in this case, get latest messages), so it adds less complexity to the app. In the articles example application, you can transmit the top X oldest messages after the last seen timestamp for each room, then have the client derive the unreadness of each room. You then can use that same info to do things like preview the oldest unread message for each room and hide latency when opening a room as you already have a screens worth of messages in hand. One doesn't need to get more recent messages as UIs generally don't have room to display large numbers and should switch to a "lots" indicator.
  - Roboprog 10y ago
    Sure, denormalize working storage in the app, fight to keep the "system of record" / "operational data store" clean.
- Roboprog 10y ago
  Hmm. So just make a request for "(my) messages since timestamp-x" from a client, build the join-query between "message rooms for me" and "messages since timestamp-x" on the server, then send a list of messages back to the client for the client code to sort out? That actually sound good enough, as far as I can see: sometimes the client code pulls up 3 days (or max-N rows, or whatever) worth of messages when started (no big deal for me, might be for my daughter...), but usually only asks for new messages in the last minute (or whatever polling interval), after which the database and any application/middleware server are left alone.
akavi 10y ago
If I've understood correctly, it feels like what the author wants is a DSL for event-driven FRP[0]. If so, I'm 100% on board. It's something I've wanted for a long time. I've found it easy enough to implement a naive version. The tricky part, unsurprisingly, is making it performant. [0] https://en.wikipedia.org/wiki/Functional_reactive_programming https://en.wikipedia.org/wiki/Functional_reactive_programmin...
- Liron 10y ago
  Author here. Yep, I basically want my database to be a giant Excel spreadsheet that includes formula cells (a.k.a. denormalized fields).
hosh 10y ago
Martin Kleppmann was presenting architectures that solve this problem: http://www.confluent.io/blog/turning-the-database-inside-out-with-apache-samza/ http://www.confluent.io/blog/turning-the-database-inside-out... http://www.confluent.io/blog/bottled-water-real-time-integration-of-postgresql-and-kafka/ http://www.confluent.io/blog/bottled-water-real-time-integra... He does not just identify secondary indices and materialized views as possible candidates, but also other applications such as caching and search indexing as within the same class of problem. Here, rather than trying to figure out a tradeoff between normalized and denormalized views, Samza and Kafka are used as the heart of what the above article was talking about as "generalized denormalization engine". It's done by capturing data change as a stream to incrementally build whatever denormalized view you want. The downside is that this is still fairly clunky, if you have this expectation that this should be built into the database. Kleppmann's ideas breaks it out into a whole infrastructure to support that. On the other hand, if you do have a full time ops team, it sounds like it can work very well at scale.
josephg 10y ago
I've been thinking about this a lot recently, and I'm convinced we need a Storm[1]-like architecture for databases. Something which would allow views / denormalization / indexing to run in separate processes. Preferably in the same language the app developers speak. And at the same time be part of the database transaction logic - triggered idempotently by the database so you always see a consistent view of the data no matter how you update & query it. (You can do this efficiently with MVCC if you proxy queries through the indexer / denormalizer / view logic / whatever you want to call it). I've scattered some more thoughts about this here, but its a big topic: https://josephg.com/blog/composing-databases/ https://josephg.com/blog/composing-databases/ [1] http://storm.apache.org/ http://storm.apache.org/
- jerf 10y ago
  "triggered idempotently by the database so you always see a consistent view of the data no matter how you update & query it" As I sit here trying to build the thing in my head that would do that, I see some major performance issues arising. Specifying how you want the data denormalized isn't that big a deal. Taking a frozen normalized database and denormalizing it according to that spec is a somewhat bigger deal; the performance implications are non-obvious because the denormalization can invoke arbitrary amounts of data in arbitrary combinations in arbitrary orders, even before we let the denormalization specification be Turing complete. Mathematically it all works but if in practice my denormalization pass is randomly accessing huge swathes of the database every time I insert a row that's not going to work very well. If we're trying to avoid slow queries when the user asks for data, and we're trying to denormalize in advance, we're basically trying to have our already-presumably-pretty-busy database pre-emptively guess all possible slow queries it might run in the future, and run them now. And then run them again when a small change comes in, having possibly never used the first set of denormalized, expensive queries I just ran. That seems... likely to generate performance problems, to understate my case by a lot. Even accounting for possible efficiencies the denormalizer might be able to take advantage of; there's still the bound of what has to be written out. OK, so that doesn't really work. But it doesn't need to; the database could do this more lazily. But, doing it fully lazily is just the same as the case where you use the normalized data, so we can't do it fully lazily. Somehow the database needs to figure out what it should and should not precompute. Well, that doesn't sound like that big a deal, right? No, it's a nightmare to even begin to specify what that might be, in the face of full Turing chaos. I can almost see how one might try to apply some basic "learning" algorithms to the task of pre-computing things partially, but it's getting pretty complicated in the backend there. There's an awful lot of symbolic computation there where I really want things to just be computing for performance. Furthermore, if one insists on consistency in the denormalized fields... yeow, that's complicated. Again, it's not hard to specify the math but making it happen would be crazy insane. Oh, and I don't mean distributed consistency... I mean even consistency on a single busy host is going to be a challenge. A feasible challenge, certainly, but a challenge that shouldn't be ignored. It seems to me there might be a use case for this to be a bullet-point feature for a database, for developers to very, very carefully use on very high-use fields. But it wouldn't be very hard for a real-world denormalization engine to become a performance nightmare. Or to end up taking more "index tuning" to be usable engine than the code we already have.
dasil003 10y ago
I'm usually the guy arguing against microservices, but I think this is a good example of why they shine. It's much easier to manage the updating of these synthesized numbers if you have a discrete service that limits the things you can do at a higher level. So instead of worrying about who is updating the data store directly, you push it up to a higher service-level interface where you have a finite list of operations that are supported, and the scope is small enough that one architect can understand the system in its entirety and make smart decisions about how to compute/store/cache these synthesized data. That said, if you have less than 10 engineers this shouldn't even be thinking about this. Way too many young engineers get hung up on scalability when they don't even have anything on the horizon that will require scaling. Couple that with a general ignorance of SQL because it's old and boring, and not realizing how much performance you can eke out of a well tuned RDBMS with proper schema and queries. A SQL DB is an incredible hedge against an uncertain future, keep your data tidy and you can keep pivoting until you find something you actually have to scale.
- buckbova 10y ago
  That's not to mention simple app caching techniques for computed values.
- coldtea 10y ago
  >So instead of worrying about who is updating the data store directly, you push it up to a higher service-level interface where you have a finite list of operations that are supported, and the scope is small enough that one architect can understand the system in its entirety and make smart decisions about how to compute/store/cache these synthesized data. Nothing about this requires a microservice. A module / package / etc barrier in a "monolithic" app through a limited exposed interface is totally enough.
  - dasil003 10y ago
    Yes yes, I know, I've made all the same arguments myself. But you have to admit, the isolation of a code base with a discrete test suite and a discrete team that has to think about nothing else gives a level of awareness to the subtleties on the potential issue that you don't get in a monolith. SOA is about scaling people more than anything.
Maarius 10y ago
Can someone explain why you wouldn't use a "read_at" flag on the message entity in this example?
- mosdave 10y ago
  which User read the Message?
makmanalp 10y ago
So I'm doing a lot of academic reading around databases, and people have been thinking about this sort of thing for a while. Here's one approach: > In this paper, we study the complementary approach, addressing index maintenance as part of query processing using continuous physical reorganization, i.e., cracking the database into manageable pieces. The motivation is that by automatically organizing data the way users request it, we can achieve fast access and the much desired self-organized behavior. > The cracking approach is based on the hypothesis that index maintenance should be a byproduct of query processing, not of updates. Each query is interpreted not only as a request for a particular result set, but also as an advice to crack the physical database store into smaller pieces. http://stratos.seas.harvard.edu/files/IKM_CIDR07.pdf http://stratos.seas.harvard.edu/files/IKM_CIDR07.pdf The references are also pretty good. edit: Here's one more specifically about (de)normalization: http://stratos.seas.harvard.edu/publications/main-memory-adaptive-denormalization http://stratos.seas.harvard.edu/publications/main-memory-ada... But it's much newer and lighter on info.
- ComodoHacker 10y ago
  Interesting read, thank you. Where can I track recent interesting papers in databases?
  - makmanalp 10y ago
    Unfortunately I'm as clueless on this as you - I'm mostly going on the papers that my professor suggests (cs165 and cs265 at harvard, the syllabus is public). Though VLDB and cidrdb seems like two conferences that seem to publish the most famous papers. Eventually you start learning the names of the authors, etc.
briHass 10y ago
To some degree, this looks like premature optimization. That query (on the normalized tables), with the proper indexes and decent hardware, should be plenty fast, even with millions of rows. I would potentially start my optimization by considering if messages could be 'archived' to other tables or considering how long I could cache the query results vs. how often the client would poll. I've seen small-medium sized systems go way overboard with complicated mechanisms for handling performance problems that they don't, and may never, have.
- jerf 10y ago
  You have to grant blog posts about issues that only appear at scale a certain amount of leeway with their examples. In the wild, if you're writing normalized schemas, traversing 5 tables isn't that difficult and traversing a couple dozen comes up more often than you'd like. It's not hard to run past what a query optimizer can handle.
- sixdimensional 10y ago
  So I agree, premature optimization can often not be necessary. But let's be crazy for a minute. How much CPU/RAM/disk IO does that query on normalized tables end up using? How much electricity does that query use? Maybe from a pure efficiency perspective, it takes less energy to query the pre-computed value, than to constantly be recalculating it on every query.
  - quickben 10y ago
    Craziness comes later. Usually few years after several developers added not normalized tables, and it all grew organically with multiple apps depending on the data. When it comes to rdbms shema, you want it optimized and enforced from day one, or the price paid later will be significant.
TurningCanadian 10y ago
I skipped around a bit in the article, but didn't see them consider having database updates simply trigger a cache invalidation (i.e. set it null) of the denormalized data instead of doing a full recomputation every time the data changes. That way you only pay the price when you need it, and it still allows for caching. You can prewarm the cache with a cron while still allowing for ondemand calculation if the cache is cold.
- repsilat 10y ago
  I think TFA was more about "when to invalidate/recompute" than "how to invalidate/update" -- that you need to take care to enumerate all of the times the denormalized value may get out of sync with the rest of the data. (This is a reasonable idea though, depending on access patterns. Can increase latency, can decrease computation.)
ThrustVectoring 10y ago
What are the tradeoffs of making the data denormalization happen in database triggers? Fundamentally, you want to update certain fields whenever certain other fields get changed, and that's exactly what database triggers do. I'm not enough of a database wizard to know if there's good reasons why this isn't more popular, though.
- snuxoll 10y ago
  Too many people argue "code doesn't belong in the database", but honestly, with everyone circling around to FRP it honestly makes me think maybe stored procedures and database triggers are going to make a comeback again. I never really bought into the whole "but you can't version stored procedures!" bit because that's precisely what schemas and the search path in PostgreSQL are for (triggers are another matter entirely, but I avoid those whenever possible - though it's exactly what I would use for a task like this).
  - buckbova 10y ago
    Triggers are synchronous and is not much different than the application updating this value when the underlying data is updated, except for the reliability that always when the data is updated the trigger will for sure fire. Postgres triggers are row by row so depending on your use cases they can be quite slow. Ideally I'd cache all these values and invalidate the global cache through the application. This would require one set of services or each set of services managing their own cache. Anytime a room is updated, boot and reload the cache for that room. Let the db stay normalized.
- anonetal 10y ago
  It's not very efficient if you have a large number of triggers. There was an early research prototype called Triggerman (http://ieeexplore.ieee.org/document/754942/ http://ieeexplore.ieee.org/document/754942/) which attempted to scale triggers, but most implementations are still clunky (probably because of the transactional guarantees required by triggers). Materialized views (that the article talks about) is a related concept, but only a few databases really support that. Both of these are also related to the work on 'Stream Databases', where the problems of efficient recomputation are central. There is a ton of work on this in academic research (http://www.springer.com/gp/book/9783540286073 http://www.springer.com/gp/book/9783540286073), but it hasn't been able to gain a foothold in the data management market (several of the academic research projects transitioned into startups).
combatentropy 10y ago
I don't think, as the article claims, data denormalization is broken. I think most programmer's knowledge of SQL is scrawny --- unexpectedly so for a language that's 30 years old and underpins most applications. SQL was obviously meant to be simple, almost declarative, and resembling plain-English sentences. And yet it's the first thing that developers abstract away with an Object Relational Mapping, much to their loss. The article's example is one-to-one chat with millions of users. It says that counting unread messages is too slow unless you denormalize it. First of all, the Rooms aren't a core table. If each Room has just two people, as the article says, then all you need is one table, messages: a | b | sent | body | read -----+-------+---------------------+----------------+--------------------- ed | tom | 09/29/2016 14:22:10 | Hi | 09/30/2016 02:02:15 tom | ed | 09/30/2016 02:03:15 | What up? | 09/30/2016 02:04:03 sue | sally | 09/30/2016 08:19:20 | Catch ya later | So the count of unread rooms is: select count(1) from (select distinct a from messages where b = :user and read is null) t; If the columns are indexed, I would think PostgreSQL could handle such queries in a split second, even with millions of rows. At Facebook's scale, where you have hundreds of millions of users, then you will have hundreds of billions or rows, maybe trillions. Okay, so it might start to get slow that this point. But let's stop for a second and remember that 99.999% of web applications will never reach Facebook's scale. In Facebook's case, I read a long time ago that they make a database for each user. If so, the aforementioned table and query would still work --- in fact without the need for the b column.
- Tenhundfeld 10y ago
  I agree with most of what you said, but one thing bothers me: > And yet [SQL]'s the first thing that developers abstract away with an Object Relational Mapping, much to their loss. I see that sentiment repeated often, but I really don't understand it. A decent ORM does two things: 1) It makes writing simple queries better – more maintainable, easier to compose, easier to secure against injection, smoother to write without constantly translating between your domain language and SQL. 2) It gets out of your way when you need to take the reins. If it is difficult to make your ORM run raw SQL queries and map the results back into domain models and primitives like array, hash, whatevs – it's time to find a better ORM. For me and many decent devs I've worked with, an ORM is not about hiding SQL. It's about automating the simple, routine stuff and letting me focus on the important, complicated parts – including highly-optimized SQL queries, at times.
aristus 10y ago
TLDR: cache invalidation is hard, even if you don't call it cache invalidation. More seriously there are plenty of ways to make this less painful, eg, adding a "lastMessageTime" to the Room table, which would reduce the work to a simple intersection of RoomUser and Room. Facebook uses a more complicated system involving "graph" relations and a global ID space, but it's more or less the same thing. Also, "normalized" is not a binary thing. There are several levels from 1NF (flat file, fully denorm) on through 3NF and BCNF (what the SQL books usually call "normalized") on up to 4th, 5th, and 6th normal forms, some of which are academic party tricks but sometimes see use in production.
- aristus 10y ago
  To add to this: every serious production system tends toward a slurry of 2NF-3NF-BCNF models, mostly for performance reasons. The case of lastMessageTime is a simpler one, as it might drift out of date but generally you get false positives but never a false negative. Note that people complain about Facebook message jewels showing up when there's nothing new but seldom complain about not getting notified. Another curious example is columnar databases. They are basically a 4NF storage layout with a veneer of 3NF syntax for ease of querying.
orasis 10y ago
I identify with the problems this article eloquently describes. I think GraphQL could be a first piece of the solution.
- Liron 10y ago
  I'm a fan of GraphQL, but that's like saying "object-oriented programming is the solution to people leaving variables on the heap after they go out of scope". No, the solution is managed memory. OOP is a higher level of abstraction that happens to work better with managed memory. See the analogy?
drcode 10y ago
Smart people already have developed general solutions to this problem- This problem is the main reason "graph queries" were independently invented by both Facebook and Netflix. See here for an exact solution to the problem posed in OP, using the OmNext graph query language: https://github.com/omcljs/om/wiki/Components,-Identity-&-Normalization https://github.com/omcljs/om/wiki/Components,-Identity-&-Nor...
- carterehsmith 10y ago
  "Smart people already have developed general solutions to this problem" Yes, they did, 50 years ago :) The article behind link refers to several-decades-old concepts of identity and normalization. That was not invented by Facebook or Netflix.
marknadal 10y ago
I very much enjoyed reading this article, it explains a lot of the pain and calls out a lot of the current broken designs. While the conclusions are correct, I feel like they could be simplified. If you try to use the vocabulary of the broken system you will get complicated phrases like "denormalization engines" (which I very much hope does not catch on despite agreeing with it). Instead, if you look at correct systems - like Elm, Rx, Datomic.com , or https://github.com/amark/gun https://github.com/amark/gun (my own, obviously I am biased) you get less complicated ideas: - Event Driven. - Data Streams. - Data Flow. - Data Pipeline. - Reactive Programming. All of these, despite "FRP" itself being jargony, solve the majority of the article's complaints. Largely because the solution he comes to at the end is the same thing as FRP. Don't we wish we had all listened to Alan Kay now?
nostrademons 10y ago
Interestingly, this article reflects a really common misconception about database normalization: The relational algebra that normal forms are expressed in has no concept of aggregate functions. The example the article gives uses fields like numUnreadRooms or lastSeenTimestamp. These are derivable from the contents of other tables with SQL aggregates like COUNT() or MAX(), but the relational algebra itself would treat them as facts of the relation itself, dependent upon the primary key. And they'd be updated by the application itself. In other words, having numUnreadRooms or lastSeenTimestamp in your schema does not make it denormalized. I was under a similar misconception for the first 5-6 years of my career, and then when I realized that it's perfectly fine to store these aggregates inline, my database queries suddenly started performing acceptably. As for how to update them - in non-broken databases, the solution is usually triggers. A trigger is a stored procedure that executes when a database operation makes some condition true, and then is executed entirely in the DB, with full transactional awareness. So you could listen for inserts and deletes and then update the count on them, and if your insert failed or the transaction was rolled back, your trigger would never be executed. This keeps data integrity in the database, but still gives you efficient queries and an application interface that's consistent.
- rjbwork 10y ago
  Yeah, the whole time I was reading this I was thinking - wouldn't you just do an insert trigger to increment your unread message counter?
  - developer2 10y ago
    Except you have the same problem, but are simply moving the complexity from the application to the database. It's not just a single insert trigger. You need one or more delete triggers. You need update triggers for things like unread or soft delete flags. It's also more difficult to maintain 5-10 triggers at the database level where there are few tools to see how multiple triggers for the same aggregation interact with each other. The point is you're suffering the same problem. Whether you do it at the application level or the database level, it's a mess.
tkyjonathan 10y ago
ProxySQL has a mirroring feature that can act like a trigger on a separate thread: https://github.com/sysown/proxysql/blob/master/doc/mirroring.md#rewrite-mirror-query-only https://github.com/sysown/proxysql/blob/master/doc/mirroring... Add a cronjob to refresh results if you are worried about skews over time. Problem solved.
callesgg 10y ago
What we need to solve this is a cell aggregation dependency function in the database. Where we define a column and a query that will be used to define the values in the cells of the column. The database would use its planer to figure out what the dependency's are and update the cell every time one of the dependencys are changed. That dependency thing is very complex but very necessary. If you dont have it you might as well just make a normal view.
- Liron 10y ago
  Author here. Yep, I think you're getting to the heart of what characterizes a "denormalization engine".
catnaroek 10y ago
There's a lot of confusion in this article. The author doesn't seem to be able to distinguish the logical view of data (in which we distinguish between primitive and derived data) from its physical representation (in which derived data may be physically stored redundantly for efficiency reasons).
thwee 10y ago
Yup, that's the job!
ComodoHacker 10y ago
One way to solve this particular problem of "number of unread rooms" is not to persist it in database at all. Send push notifications of new messages and have client app to compute it client-side.
Roboprog 10y ago
META: When did we all start saying "performant", instead of "fast [enough]"? Was it about 5 years ago??? Maybe 10? English, like SQL, is passe`.
- rplst8 10y ago
  I hate the word performant. People may argue that "fast" is a simpleton of a word, however "performant" is ambiguous as to what characteristic is performing well.
bryanlarsen 10y ago
Wasn't this essentially what CouchDB did?

171 points by endswapper 10y ago

swlkr 10y ago

I can see why the normalized approach is difficult to make performant, but it seems much simpler.

arjunnarayan 10y ago
You're correct on both counts. A normalized approach is simpler, and is more difficult to make performant. So you start there, but as you scale, it becomes more and more untenable for your users as your latency goes up the wazoo. Thus, eventually your app hits a scale where you have to rewrite your code to explicitly denormalize things and maintain the denormalized views yourself. This makes any feature addition/backend update horrendously complicated, and everyone's life difficult. You slowly start losing consistency which causes "glitches in the matrix" for your users. To stop that you start adding in transactional semantics yourself at the application level, checking and cross-checking everything, and doing abort/restarts, and then finally, in an analogue to Greenspun's tenth rule[1], your application starts to contain an ad hoc, informally-specified, bug-ridden, slow implementation of a distributed database. I think there's a CircleCI blog post parody hidden inside this comment, but I'm not clever enough to materialize it[2]. [1]: Any sufficiently complicated C or Fortran program contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of Common Lisp., https://en.wikipedia.org/wiki/Greenspun%27s_tenth_rule https://en.wikipedia.org/wiki/Greenspun%27s_tenth_rule [2]: A reference to https://circleci.com/blog/its-the-future/ https://circleci.com/blog/its-the-future/
jacques_chester 10y ago
Broadly: Normalised data is more performant on write, because for each piece of state, there will be one and only one place to store it. It's less performant on read because you are constructing logical deductions out of a lattice of tiny pebbles of truth. It takes time to find, filter, sort and project those. Denormalisation "works" by skipping to a read-optimised schema for those applications where reads greatly outnumber writes. Which is very many. As an aside, "denormalised" doesn't have to mean "unstructured chaos". Do As Thou Wilt isn't necessarily the law of denormalising. There are well-studied, widely-used denormalisation techniques under the heading of "dimensional modelling". It's just that most of these discussions are dominated by web folk, not data warehouse folk. The shoutout to Event Sourcing is promising, given the interaction with the CQRS pattern. In short: read schema and write schema have different demand and performance characteristics. So split them up.
- LgWoodenBadger 10y ago
  I don't know that you can always conclude that normalized data is more performant for writes. Take for example the case where your normalized write consists of 5 insert statements into 5 tables, instead of 1 insert into 1 table that you'd do with a denormalized write.
  - jacques_chester 10y ago
    As always, consult your doctor, accountant, lawyer and profiler.

jkkramer 10y ago

One technique that can be useful is imposing domain-specific restrictions, then passing responsibility down the chain. For example, most people only have a handful of recent conversations; can you get away with ignoring distant-past conversations when it comes to read/unread marking? If so, you could send recent normalized data to the frontend and let it derive the unread state client-side. React has some nice tools for efficiently deriving state from server-sent data. This isn't always the best solution, but it's something to consider.

extrapickles 10y ago
Unless the amount of data you need to transmit is large, I always prefer that approach as it enables other UI features without any additional network trips by the client. Also, it lets one use the same mechanism for multiple uses (in this case, get latest messages), so it adds less complexity to the app. In the articles example application, you can transmit the top X oldest messages after the last seen timestamp for each room, then have the client derive the unreadness of each room. You then can use that same info to do things like preview the oldest unread message for each room and hide latency when opening a room as you already have a screens worth of messages in hand. One doesn't need to get more recent messages as UIs generally don't have room to display large numbers and should switch to a "lots" indicator.
- Roboprog 10y ago
  Sure, denormalize working storage in the app, fight to keep the "system of record" / "operational data store" clean.
Roboprog 10y ago
Hmm. So just make a request for "(my) messages since timestamp-x" from a client, build the join-query between "message rooms for me" and "messages since timestamp-x" on the server, then send a list of messages back to the client for the client code to sort out? That actually sound good enough, as far as I can see: sometimes the client code pulls up 3 days (or max-N rows, or whatever) worth of messages when started (no big deal for me, might be for my daughter...), but usually only asks for new messages in the last minute (or whatever polling interval), after which the database and any application/middleware server are left alone.

akavi 10y ago

If I've understood correctly, it feels like what the author wants is a DSL for event-driven FRP[0]. If so, I'm 100% on board. It's something I've wanted for a long time. I've found it easy enough to implement a naive version. The tricky part, unsurprisingly, is making it performant. [0] https://en.wikipedia.org/wiki/Functional_reactive_programming https://en.wikipedia.org/wiki/Functional_reactive_programmin...

Liron 10y ago
Author here. Yep, I basically want my database to be a giant Excel spreadsheet that includes formula cells (a.k.a. denormalized fields).

hosh 10y ago

Martin Kleppmann was presenting architectures that solve this problem: http://www.confluent.io/blog/turning-the-database-inside-out-with-apache-samza/ http://www.confluent.io/blog/turning-the-database-inside-out... http://www.confluent.io/blog/bottled-water-real-time-integration-of-postgresql-and-kafka/ http://www.confluent.io/blog/bottled-water-real-time-integra... He does not just identify secondary indices and materialized views as possible candidates, but also other applications such as caching and search indexing as within the same class of problem. Here, rather than trying to figure out a tradeoff between normalized and denormalized views, Samza and Kafka are used as the heart of what the above article was talking about as "generalized denormalization engine". It's done by capturing data change as a stream to incrementally build whatever denormalized view you want. The downside is that this is still fairly clunky, if you have this expectation that this should be built into the database. Kleppmann's ideas breaks it out into a whole infrastructure to support that. On the other hand, if you do have a full time ops team, it sounds like it can work very well at scale.

josephg 10y ago

I've been thinking about this a lot recently, and I'm convinced we need a Storm[1]-like architecture for databases. Something which would allow views / denormalization / indexing to run in separate processes. Preferably in the same language the app developers speak. And at the same time be part of the database transaction logic - triggered idempotently by the database so you always see a consistent view of the data no matter how you update & query it. (You can do this efficiently with MVCC if you proxy queries through the indexer / denormalizer / view logic / whatever you want to call it). I've scattered some more thoughts about this here, but its a big topic: https://josephg.com/blog/composing-databases/ https://josephg.com/blog/composing-databases/ [1] http://storm.apache.org/ http://storm.apache.org/

jerf 10y ago
"triggered idempotently by the database so you always see a consistent view of the data no matter how you update & query it" As I sit here trying to build the thing in my head that would do that, I see some major performance issues arising. Specifying how you want the data denormalized isn't that big a deal. Taking a frozen normalized database and denormalizing it according to that spec is a somewhat bigger deal; the performance implications are non-obvious because the denormalization can invoke arbitrary amounts of data in arbitrary combinations in arbitrary orders, even before we let the denormalization specification be Turing complete. Mathematically it all works but if in practice my denormalization pass is randomly accessing huge swathes of the database every time I insert a row that's not going to work very well. If we're trying to avoid slow queries when the user asks for data, and we're trying to denormalize in advance, we're basically trying to have our already-presumably-pretty-busy database pre-emptively guess all possible slow queries it might run in the future, and run them now. And then run them again when a small change comes in, having possibly never used the first set of denormalized, expensive queries I just ran. That seems... likely to generate performance problems, to understate my case by a lot. Even accounting for possible efficiencies the denormalizer might be able to take advantage of; there's still the bound of what has to be written out. OK, so that doesn't really work. But it doesn't need to; the database could do this more lazily. But, doing it fully lazily is just the same as the case where you use the normalized data, so we can't do it fully lazily. Somehow the database needs to figure out what it should and should not precompute. Well, that doesn't sound like that big a deal, right? No, it's a nightmare to even begin to specify what that might be, in the face of full Turing chaos. I can almost see how one might try to apply some basic "learning" algorithms to the task of pre-computing things partially, but it's getting pretty complicated in the backend there. There's an awful lot of symbolic computation there where I really want things to just be computing for performance. Furthermore, if one insists on consistency in the denormalized fields... yeow, that's complicated. Again, it's not hard to specify the math but making it happen would be crazy insane. Oh, and I don't mean distributed consistency... I mean even consistency on a single busy host is going to be a challenge. A feasible challenge, certainly, but a challenge that shouldn't be ignored. It seems to me there might be a use case for this to be a bullet-point feature for a database, for developers to very, very carefully use on very high-use fields. But it wouldn't be very hard for a real-world denormalization engine to become a performance nightmare. Or to end up taking more "index tuning" to be usable engine than the code we already have.

dasil003 10y ago

I'm usually the guy arguing against microservices, but I think this is a good example of why they shine. It's much easier to manage the updating of these synthesized numbers if you have a discrete service that limits the things you can do at a higher level. So instead of worrying about who is updating the data store directly, you push it up to a higher service-level interface where you have a finite list of operations that are supported, and the scope is small enough that one architect can understand the system in its entirety and make smart decisions about how to compute/store/cache these synthesized data. That said, if you have less than 10 engineers this shouldn't even be thinking about this. Way too many young engineers get hung up on scalability when they don't even have anything on the horizon that will require scaling. Couple that with a general ignorance of SQL because it's old and boring, and not realizing how much performance you can eke out of a well tuned RDBMS with proper schema and queries. A SQL DB is an incredible hedge against an uncertain future, keep your data tidy and you can keep pivoting until you find something you actually have to scale.

buckbova 10y ago
That's not to mention simple app caching techniques for computed values.
coldtea 10y ago
>So instead of worrying about who is updating the data store directly, you push it up to a higher service-level interface where you have a finite list of operations that are supported, and the scope is small enough that one architect can understand the system in its entirety and make smart decisions about how to compute/store/cache these synthesized data. Nothing about this requires a microservice. A module / package / etc barrier in a "monolithic" app through a limited exposed interface is totally enough.
- dasil003 10y ago
  Yes yes, I know, I've made all the same arguments myself. But you have to admit, the isolation of a code base with a discrete test suite and a discrete team that has to think about nothing else gives a level of awareness to the subtleties on the potential issue that you don't get in a monolith. SOA is about scaling people more than anything.

Maarius 10y ago

Can someone explain why you wouldn't use a "read_at" flag on the message entity in this example?

mosdave 10y ago
which User read the Message?

makmanalp 10y ago

So I'm doing a lot of academic reading around databases, and people have been thinking about this sort of thing for a while. Here's one approach: > In this paper, we study the complementary approach, addressing index maintenance as part of query processing using continuous physical reorganization, i.e., cracking the database into manageable pieces. The motivation is that by automatically organizing data the way users request it, we can achieve fast access and the much desired self-organized behavior. > The cracking approach is based on the hypothesis that index maintenance should be a byproduct of query processing, not of updates. Each query is interpreted not only as a request for a particular result set, but also as an advice to crack the physical database store into smaller pieces. http://stratos.seas.harvard.edu/files/IKM_CIDR07.pdf http://stratos.seas.harvard.edu/files/IKM_CIDR07.pdf The references are also pretty good. edit: Here's one more specifically about (de)normalization: http://stratos.seas.harvard.edu/publications/main-memory-adaptive-denormalization http://stratos.seas.harvard.edu/publications/main-memory-ada... But it's much newer and lighter on info.

ComodoHacker 10y ago
Interesting read, thank you. Where can I track recent interesting papers in databases?
- makmanalp 10y ago
  Unfortunately I'm as clueless on this as you - I'm mostly going on the papers that my professor suggests (cs165 and cs265 at harvard, the syllabus is public). Though VLDB and cidrdb seems like two conferences that seem to publish the most famous papers. Eventually you start learning the names of the authors, etc.

briHass 10y ago

To some degree, this looks like premature optimization. That query (on the normalized tables), with the proper indexes and decent hardware, should be plenty fast, even with millions of rows. I would potentially start my optimization by considering if messages could be 'archived' to other tables or considering how long I could cache the query results vs. how often the client would poll. I've seen small-medium sized systems go way overboard with complicated mechanisms for handling performance problems that they don't, and may never, have.

jerf 10y ago
You have to grant blog posts about issues that only appear at scale a certain amount of leeway with their examples. In the wild, if you're writing normalized schemas, traversing 5 tables isn't that difficult and traversing a couple dozen comes up more often than you'd like. It's not hard to run past what a query optimizer can handle.
sixdimensional 10y ago
So I agree, premature optimization can often not be necessary. But let's be crazy for a minute. How much CPU/RAM/disk IO does that query on normalized tables end up using? How much electricity does that query use? Maybe from a pure efficiency perspective, it takes less energy to query the pre-computed value, than to constantly be recalculating it on every query.
- quickben 10y ago
  Craziness comes later. Usually few years after several developers added not normalized tables, and it all grew organically with multiple apps depending on the data. When it comes to rdbms shema, you want it optimized and enforced from day one, or the price paid later will be significant.

TurningCanadian 10y ago

I skipped around a bit in the article, but didn't see them consider having database updates simply trigger a cache invalidation (i.e. set it null) of the denormalized data instead of doing a full recomputation every time the data changes. That way you only pay the price when you need it, and it still allows for caching. You can prewarm the cache with a cron while still allowing for ondemand calculation if the cache is cold.

repsilat 10y ago
I think TFA was more about "when to invalidate/recompute" than "how to invalidate/update" -- that you need to take care to enumerate all of the times the denormalized value may get out of sync with the rest of the data. (This is a reasonable idea though, depending on access patterns. Can increase latency, can decrease computation.)

ThrustVectoring 10y ago

What are the tradeoffs of making the data denormalization happen in database triggers? Fundamentally, you want to update certain fields whenever certain other fields get changed, and that's exactly what database triggers do. I'm not enough of a database wizard to know if there's good reasons why this isn't more popular, though.

snuxoll 10y ago
Too many people argue "code doesn't belong in the database", but honestly, with everyone circling around to FRP it honestly makes me think maybe stored procedures and database triggers are going to make a comeback again. I never really bought into the whole "but you can't version stored procedures!" bit because that's precisely what schemas and the search path in PostgreSQL are for (triggers are another matter entirely, but I avoid those whenever possible - though it's exactly what I would use for a task like this).
- buckbova 10y ago
  Triggers are synchronous and is not much different than the application updating this value when the underlying data is updated, except for the reliability that always when the data is updated the trigger will for sure fire. Postgres triggers are row by row so depending on your use cases they can be quite slow. Ideally I'd cache all these values and invalidate the global cache through the application. This would require one set of services or each set of services managing their own cache. Anytime a room is updated, boot and reload the cache for that room. Let the db stay normalized.
anonetal 10y ago
It's not very efficient if you have a large number of triggers. There was an early research prototype called Triggerman (http://ieeexplore.ieee.org/document/754942/ http://ieeexplore.ieee.org/document/754942/) which attempted to scale triggers, but most implementations are still clunky (probably because of the transactional guarantees required by triggers). Materialized views (that the article talks about) is a related concept, but only a few databases really support that. Both of these are also related to the work on 'Stream Databases', where the problems of efficient recomputation are central. There is a ton of work on this in academic research (http://www.springer.com/gp/book/9783540286073 http://www.springer.com/gp/book/9783540286073), but it hasn't been able to gain a foothold in the data management market (several of the academic research projects transitioned into startups).

combatentropy 10y ago

I don't think, as the article claims, data denormalization is broken. I think most programmer's knowledge of SQL is scrawny --- unexpectedly so for a language that's 30 years old and underpins most applications. SQL was obviously meant to be simple, almost declarative, and resembling plain-English sentences. And yet it's the first thing that developers abstract away with an Object Relational Mapping, much to their loss. The article's example is one-to-one chat with millions of users. It says that counting unread messages is too slow unless you denormalize it. First of all, the Rooms aren't a core table. If each Room has just two people, as the article says, then all you need is one table, messages: a | b | sent | body | read -----+-------+---------------------+----------------+--------------------- ed | tom | 09/29/2016 14:22:10 | Hi | 09/30/2016 02:02:15 tom | ed | 09/30/2016 02:03:15 | What up? | 09/30/2016 02:04:03 sue | sally | 09/30/2016 08:19:20 | Catch ya later | So the count of unread rooms is: select count(1) from (select distinct a from messages where b = :user and read is null) t; If the columns are indexed, I would think PostgreSQL could handle such queries in a split second, even with millions of rows. At Facebook's scale, where you have hundreds of millions of users, then you will have hundreds of billions or rows, maybe trillions. Okay, so it might start to get slow that this point. But let's stop for a second and remember that 99.999% of web applications will never reach Facebook's scale. In Facebook's case, I read a long time ago that they make a database for each user. If so, the aforementioned table and query would still work --- in fact without the need for the b column.

Tenhundfeld 10y ago
I agree with most of what you said, but one thing bothers me: > And yet [SQL]'s the first thing that developers abstract away with an Object Relational Mapping, much to their loss. I see that sentiment repeated often, but I really don't understand it. A decent ORM does two things: 1) It makes writing simple queries better – more maintainable, easier to compose, easier to secure against injection, smoother to write without constantly translating between your domain language and SQL. 2) It gets out of your way when you need to take the reins. If it is difficult to make your ORM run raw SQL queries and map the results back into domain models and primitives like array, hash, whatevs – it's time to find a better ORM. For me and many decent devs I've worked with, an ORM is not about hiding SQL. It's about automating the simple, routine stuff and letting me focus on the important, complicated parts – including highly-optimized SQL queries, at times.

aristus 10y ago

TLDR: cache invalidation is hard, even if you don't call it cache invalidation. More seriously there are plenty of ways to make this less painful, eg, adding a "lastMessageTime" to the Room table, which would reduce the work to a simple intersection of RoomUser and Room. Facebook uses a more complicated system involving "graph" relations and a global ID space, but it's more or less the same thing. Also, "normalized" is not a binary thing. There are several levels from 1NF (flat file, fully denorm) on through 3NF and BCNF (what the SQL books usually call "normalized") on up to 4th, 5th, and 6th normal forms, some of which are academic party tricks but sometimes see use in production.

aristus 10y ago
To add to this: every serious production system tends toward a slurry of 2NF-3NF-BCNF models, mostly for performance reasons. The case of lastMessageTime is a simpler one, as it might drift out of date but generally you get false positives but never a false negative. Note that people complain about Facebook message jewels showing up when there's nothing new but seldom complain about not getting notified. Another curious example is columnar databases. They are basically a 4NF storage layout with a veneer of 3NF syntax for ease of querying.

orasis 10y ago

I identify with the problems this article eloquently describes. I think GraphQL could be a first piece of the solution.

Liron 10y ago
I'm a fan of GraphQL, but that's like saying "object-oriented programming is the solution to people leaving variables on the heap after they go out of scope". No, the solution is managed memory. OOP is a higher level of abstraction that happens to work better with managed memory. See the analogy?

drcode 10y ago

Smart people already have developed general solutions to this problem- This problem is the main reason "graph queries" were independently invented by both Facebook and Netflix. See here for an exact solution to the problem posed in OP, using the OmNext graph query language: https://github.com/omcljs/om/wiki/Components,-Identity-&-Normalization https://github.com/omcljs/om/wiki/Components,-Identity-&-Nor...

carterehsmith 10y ago
"Smart people already have developed general solutions to this problem" Yes, they did, 50 years ago :) The article behind link refers to several-decades-old concepts of identity and normalization. That was not invented by Facebook or Netflix.

marknadal 10y ago

I very much enjoyed reading this article, it explains a lot of the pain and calls out a lot of the current broken designs. While the conclusions are correct, I feel like they could be simplified. If you try to use the vocabulary of the broken system you will get complicated phrases like "denormalization engines" (which I very much hope does not catch on despite agreeing with it). Instead, if you look at correct systems - like Elm, Rx, Datomic.com , or https://github.com/amark/gun https://github.com/amark/gun (my own, obviously I am biased) you get less complicated ideas: - Event Driven. - Data Streams. - Data Flow. - Data Pipeline. - Reactive Programming. All of these, despite "FRP" itself being jargony, solve the majority of the article's complaints. Largely because the solution he comes to at the end is the same thing as FRP. Don't we wish we had all listened to Alan Kay now?

nostrademons 10y ago

Interestingly, this article reflects a really common misconception about database normalization: The relational algebra that normal forms are expressed in has no concept of aggregate functions. The example the article gives uses fields like numUnreadRooms or lastSeenTimestamp. These are derivable from the contents of other tables with SQL aggregates like COUNT() or MAX(), but the relational algebra itself would treat them as facts of the relation itself, dependent upon the primary key. And they'd be updated by the application itself. In other words, having numUnreadRooms or lastSeenTimestamp in your schema does not make it denormalized. I was under a similar misconception for the first 5-6 years of my career, and then when I realized that it's perfectly fine to store these aggregates inline, my database queries suddenly started performing acceptably. As for how to update them - in non-broken databases, the solution is usually triggers. A trigger is a stored procedure that executes when a database operation makes some condition true, and then is executed entirely in the DB, with full transactional awareness. So you could listen for inserts and deletes and then update the count on them, and if your insert failed or the transaction was rolled back, your trigger would never be executed. This keeps data integrity in the database, but still gives you efficient queries and an application interface that's consistent.

rjbwork 10y ago
Yeah, the whole time I was reading this I was thinking - wouldn't you just do an insert trigger to increment your unread message counter?
- developer2 10y ago
  Except you have the same problem, but are simply moving the complexity from the application to the database. It's not just a single insert trigger. You need one or more delete triggers. You need update triggers for things like unread or soft delete flags. It's also more difficult to maintain 5-10 triggers at the database level where there are few tools to see how multiple triggers for the same aggregation interact with each other. The point is you're suffering the same problem. Whether you do it at the application level or the database level, it's a mess.

tkyjonathan 10y ago

ProxySQL has a mirroring feature that can act like a trigger on a separate thread: https://github.com/sysown/proxysql/blob/master/doc/mirroring.md#rewrite-mirror-query-only https://github.com/sysown/proxysql/blob/master/doc/mirroring... Add a cronjob to refresh results if you are worried about skews over time. Problem solved.

callesgg 10y ago

What we need to solve this is a cell aggregation dependency function in the database. Where we define a column and a query that will be used to define the values in the cells of the column. The database would use its planer to figure out what the dependency's are and update the cell every time one of the dependencys are changed. That dependency thing is very complex but very necessary. If you dont have it you might as well just make a normal view.

Liron 10y ago
Author here. Yep, I think you're getting to the heart of what characterizes a "denormalization engine".

catnaroek 10y ago

There's a lot of confusion in this article. The author doesn't seem to be able to distinguish the logical view of data (in which we distinguish between primitive and derived data) from its physical representation (in which derived data may be physically stored redundantly for efficiency reasons).

thwee 10y ago

Yup, that's the job!

ComodoHacker 10y ago

One way to solve this particular problem of "number of unread rooms" is not to persist it in database at all. Send push notifications of new messages and have client app to compute it client-side.

Roboprog 10y ago

META: When did we all start saying "performant", instead of "fast [enough]"? Was it about 5 years ago??? Maybe 10? English, like SQL, is passe`.

rplst8 10y ago
I hate the word performant. People may argue that "fast" is a simpleton of a word, however "performant" is ambiguous as to what characteristic is performing well.

bryanlarsen 10y ago

Wasn't this essentially what CouchDB did?