48

I have a database with a 1:m relationship.

I have to display a list of parents to the user rapidly on a home screen at startup. The parent shows a single piece of information that is a sum of a particular child field for that parent.

I don’t want the expense of making large queries to the child table (essentially doing lists of calculations on the entire child table) - in order to show the parents. I also feel it's important to show the sum to the user on the home screen.

I have therefore denormalised the sum of all children for a particular parent and added it as a field within the parent table. Each time a CRUD operation is done within the child table (with an ID that matches a particular parent), I recalculate and reinsert the new value into the parent field.

Is this an anti-pattern and therefore 'bad' practice? I felt I was doing the right thing by prioritising performance for the UI.

14
  • 27
    Did you measure the performance (both of a SUM query and the impact on the CRUD operations)? I suspect ensuring there are appropriate indexes will give you good enough performance for a page's worth of parent info – Caleth Jun 14 at 16:20
  • 4
    Fantastic - thanks so much... Im seeing now that i made performance assumptions that i shouldnt have. Im currently researching the best procedure to performance test both options before i go any further. – tommytucker7182 Jun 14 at 17:21
  • 11
    A not so funny read about where this would've been preferred. Although this seems to be NoSQL, the principle remains the same. TL;DR, the website went viral and incurred over 30k USD in a Firebase bill in 48 hours. hackernoon.com/… – Jan Dorniak Jun 15 at 0:15
  • 9
    Don't forget to write a script or program which inserts millions of test records into your database to test average and worst case scenarios. Every software is fast if you test it with 1000 records. It gets interesting if you test it (early) with 5 or 10 million records. – some_coder Jun 15 at 8:16
  • 4
    Note that instead of performing the update manually on every CRUD operation, you may want to consider using triggers or other mechanisms natively supported by your database server. This way you don't have to worry about missing forgetting to update the sum. – Michael Mior Jun 15 at 13:37
85

Performance requirements are legitimate requirements, and it's great that you have found a potential way to meet these requirements. Denormalization is a tool, not an anti-pattern. But this likely involves tradeoffs, and you should consider them before committing to this solution.

For example, I'm worried about maintaining consistency when the same information is expressed through multiple fields:

  1. What is your “source of truth”? What happens if the sum in the parent gets out of sync? Can the cached values be recalculated from scratch?
  2. If there is a consistency problem, what would the impact be?
  3. How will you ensure that parents get updated whenever a child changes? Would that be triggers or materialized views in the DB or is this the responsibility of the applications making queries?
  4. Will you use transactions/locks to ensure that updates are performed atomically?
  5. Might transactions/locks lead to lock contention on parents with lots of children, thus reducing performance?

Many scenarios can sidestep many of these problems either because they don't have that stringent performance requirements, or because the business problem can tolerate eventual consistency. Also, workloads that mostly read a value and rarely modify it are typically easier to optimize.

You might also consider whether this is the most appropriate way to achieve your performance:

  1. Is the query just slow because the child table is not properly indexed? Does the query plan (“explain” statement) look reasonable?
  2. Is the query really on the critical path, or could it be performed asynchronously?
  3. Is the speed actually acceptable, but the GUI merely feels slow because there are no transition animations?
3
  • Thanks for the questions - i have answers to most of them, some i need to reconsider after my performance testing is completed. – tommytucker7182 Jun 15 at 10:11
  • 3
    answer accepted becuase of the comprehensive list of questions to consider - thanks! – tommytucker7182 Jun 15 at 10:24
  • 6
    Excellent post. I've found that denormalization schemes almost always become terrible pain pain points when these questions have not been thoroughly answered. Another thing to consider is whether these computed values should actually take the form of denormalization, rather than being stored separately (perhaps in a store specifically designed for caching). – Matthew Read Jun 16 at 21:27
90

Is denormalisation for performance reasons an anti-pattern? Not of itself - if something is required, then you have to find a way to do it, and it may well be better to denormalise your data than spend $$$ on a SuperHugeDatabaseInstance to get you the speed you need. I've certainly done this in the past when we were calculating summary data for billions of data points.

Is denormalisation for performance reasons before you've measured things and found out if you actually need to do it an anti-pattern? Yes, every time.

1
  • 7
    A really good point, I didnt even notice that id made that assumption!! Thanks for your answer. – tommytucker7182 Jun 14 at 17:22
26

Premature optimization is the root of all evil - most of it, anyway - in computer science. ~Donald Knuth

Denormalizing aggregate data to avoid the aggregate function is not an anti-pattern. The anti-pattern is doing so without first establishing that the aggregate function is infeasibly slow.

First, define "quite large". Hundreds of children? Thousands? Trivial. Modern DBMS software on modern hardware can make short work of even naive implementations of the aggregate at these scales. If by "quite large" you mean hundreds of thousands or millions of rows, then we may be talking about enough raw data for a more custom solution.

A related consideration is multi-level aggregates. If the sum isn't just of children, but children of children, then the Big-O shape of the aggregate function is the number of children raised to the power of the maximum number of "generations" of child data involved in the aggregate. A thousand children of one parent is trivial, but a thousand rows with a thousand children is a million rows that have to be queried. Add one more layer and you're summing a billion rows for just three referential generations. That assumes constant access time for each record, which is rarely true in RDBMSes; best-case is usually logarithmic if indexed, linear if not, so basically add another polynomial degree to the search for tablescans. If all parents reference all children in each generation, this billion-row calculation can be required from a worst-case table of just 3000 rows, making a trivial-looking table a computational nightmare.

Last is the shape of the aggregate function itself. Most "built-ins" like SUM, AVG, STDEV etc are linear to total inputs, but there are "aggregate" functions (defined loosely as algorithms digesting a series to a scalar) that have higher computational complexity. Regression analyses tend to be N^2 or worse, and certain specialized scalar calculations can be higher-order polynomial or NP-time.

I put aggregate function complexity last because you typically have less control over the calculation you need than the inputs into it, however a common optimization involves reducing the problem from a complete calculation to an incremental one. Calculating the sum of a million random data points is a million addition operations, and there really isn't any way around that. However, calculating the sum of a million data points, given the sum of 999,999 of them and the millionth value, is basically constant-time.

This is how that aggregate column is going to help you, if it is really needed. A trigger on an insert or update of a child record, to set the sum field of the parent record(s) to (currentSum - deleted.ValueToSum + inserted.ValueToSum), makes maintaining these sums dramatically less complex than calculating the value from scratch. This improves query speed of the aggregate value without sacrificing insert speed (which is impacted by both triggers and indexes).

Again, all of this is contingent on a simple, intuitive, "naive" solution not being good enough. To determine that, you first have to define "good enough", usually "some insignificant fraction of the total load time of the UI view", and test your candidate implementation to show that it definitely doesn't meet the definition. So, start with a computed column defined as a subquery of the record's children (basically a stored subquery giving you the advantage of a cached execution plan). If that isn't fast enough, make sure you are including the value you're summing in an index of the child table on the parent ID. If that's still not fast enough, then consider replacing the computed column with incremental calculation in a trigger or the create/update SP.

5
  • 2
    "Modern DBMS software on modern hardware can make short work of even naive implementations of the aggregate at these scales." It may be that aggregating 1000 children is a fast query, but it's still about 1000 times worse than just loading a single row by primary key. If this query is in a frequently used path, denormalization could decrease the cost of this query by three orders of magnitude. Don't be so quick to assume optimization is premature. – Phil Frost Jun 15 at 20:02
  • 2
    On the other hand, this answer could make a good illustration for Wirth's law. – Phil Frost Jun 15 at 20:04
  • i forgot to say thanks for the incredibly comprehensive answer! much appreciated. It turns out, my DB is quite trivial so this has given me some much needed perspective. – tommytucker7182 Jun 16 at 10:42
  • "This is how that aggregate column is going to help you". You're overlooking the read/write ratio. If reads>writes, then an aggregate is a win regardless. – Mooing Duck Jun 17 at 14:29
  • @PhilFrost - I agree with everything you've said; that's why there are a few "never do's" regarding algorithm complexity, and performance/load testing is paramount in performance-critical applications. Re: Wirth's Law, I agree there as well, but the explanation is simple; hardware is cheaper than developer time. As with many creative pursuits, the result's never perfect, you just run out of time to get it there. – KeithS Jul 1 at 20:44
23

Most relational databases have something called Materialized Views. It basically has the database precompute a query and keep that around for quick response. The database is then responsible for keeping the View consistent with the data, including any complications from atomicity transactions. Basically like database-managed caching.

Read the documentation for your database, because this can get complicated.

Using Materialized Views is no more a denormalization antipattern than using indices. But making the application layer ensure data consistency when the database could be doing it: that is an antipattern.

4
  • 3
    I wasnt aware of Materialized views so i will look up. I have a lot of things to do from this one blog post, its been great, ive gotten some education from it and a lot of things to read up on and research! Thanks for taking the time to comment. – tommytucker7182 Jun 15 at 9:49
  • 7
    As a caveat, there are substantial differences between DBs. T-SQL has materialized views as presented in this answer, which works as a more flexible index. Postgres has materialized views as well, but they must be refreshed explicitly. Oracle has a wide variety of options for refreshs (e.g. on commit or on a schedule). MySQL doesn't have materialized views but can emulate them using triggers or events. So while materialized views in Oracle and SQL Server can be kept automatically consistent, this feature is more geared towards data warehousing use cases where up to date data isn't required. – amon Jun 15 at 17:27
  • Materialized views in sql server may not be picked without a hint. They can be useful, but shouldn’t be you first try unless you know what you are doing. – jmoreno Jun 16 at 1:20
  • That's an under-appreciated answer that probably best addresses OP's real problem, but maybe you can add an explicit answer to the question as asked? Something along the lines of "It's an anti-pattern if you prefer de-normalization over other mechanisms your database already gives you to handle redundancy in a controlled manner, such as materialised views." – xLeitix Jun 17 at 9:41
3

If you are pulling data from a database to display in an app and hitting up against performance issue if this kind, I would seriously consider a caching layer. It's significantly faster to retrieve from a cache rather than a database.

At it's minimum the cache would store the count of children against the parent's ID whenever the count is done, and a CRUD operation that changes the quantity of children would clear the relevant values from the cache. When fetching the data for the UI first check if it's in the cache, and if not do the database sum request.

This solution would open up further performance improvements as you find other things that could easily be cached.

2
  • 2
    I'd disagree that a separate caching layer is always required. Major databases have their own caching implementations. For example Views in MW SQL Server can be cached in Memory, making them just as fast as some extra caching layer. (Plus they would be a little easier to keep in sync.) – SwissCoder Jun 16 at 13:56
  • 2
    I was going to suggest this approach, a local cache for just the child totals make more sense than denormalizing the tables.. even if dbs have cache policies, it is more transparent for the developer to control their own cache – lurscher Jun 17 at 6:29

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