MySQL solution for many to many associative table that scale over billion entries

Question

Scenario

Imagine we have a table user and an item user. These 2 tables have an associative table called user_item to define a many to manyrelationship.

• We start 100 item records

• We have 500 Millions user records.

• Therefore we must generate 50_000_000_000 user_item (50 billions)

• We could potentially have even more

• Won't be easy to shard nor partition because then, it will slow down any other operation (otherwise we need to scan everything)

• Assume as query pattern (INSERT, SELECT, UPDATE) basic/typical m2m patterns (that could be found in any tutorial or example

Question

What's the best design or known solution for handling billions of Many to Many relationship in a database regardless of a schema?

Schema

Imagine this simple schema

CREATE DATABASE IF NOT EXISTS `playground` CHARACTER SET = latin1;
USE playground;

CREATE TABLE IF NOT EXISTS `user`
(
    `id`   BIGINT UNSIGNED NOT NULL AUTO_INCREMENT,
    `name` VARCHAR(255)    NOT NULL,
    PRIMARY KEY (`id`),
    INDEX `user__name_fk` (`name`)
) ENGINE = InnoDB
  DEFAULT CHARSET = latin1
  ROW_FORMAT = DYNAMIC;

CREATE TABLE IF NOT EXISTS `item`
(
    `id`   BIGINT UNSIGNED NOT NULL AUTO_INCREMENT,
    `name` VARCHAR(255)    NOT NULL,
    PRIMARY KEY (`id`),
    INDEX `user__name` (`name`)
) ENGINE = InnoDB
  DEFAULT CHARSET = latin1
  ROW_FORMAT = DYNAMIC;

CREATE TABLE IF NOT EXISTS `user_item`
(
    `user_id` BIGINT UNSIGNED NOT NULL,
    `item_id` BIGINT UNSIGNED NOT NULL,
    PRIMARY KEY (`user_id`, `item_id`),
    INDEX `user_item__item` (`item_id`),

    FOREIGN KEY `user_id_fk` (`user_id`) REFERENCES `user` (`id`) ON DELETE CASCADE,
    FOREIGN KEY `item_id_fk` (`item_id`) REFERENCES `item` (`id`) ON DELETE CASCADE
) ENGINE = InnoDB
  DEFAULT CHARSET = latin1
  ROW_FORMAT = DYNAMIC;

-- create some default items
INSERT INTO `item` (`name`) VALUES ('item_1'), ('item_2'), ('item_3'), ('item_4'), ('item_5'), ('item_6'), ('item_7'), ('item_8'), ('item_9'), ('item_10');
-- create some users
INSERT INTO `user` (`name`) VALUES ('user_1'), ('user_2'), ('user_3'), ('user_4'), ('user_5'), ('user_6'), ('user_7'), ('user_8'), ('user_9'), ('user_10');
INSERT INTO `user_item` (`user_id`, `item_id`) VALUES (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1, 7), (1, 8), (1, 9), (1, 10);

More info

I'm not asking on how to use many to many relation ship in MySQL, i know that. I'm asking what is the more known solution for a scaling issue, that is, when number of related records are exponentially growing to such big scale.

Also I intentionally didn't add any query pattern (INSERT, SELECT, UPDATE) because is irrelevant. Assume the most/typical M2M pattern. I don't want to loose focus on the real question which is about scaling and huge amount of data.

There must be some trick or some known workaround right? I'm also considering a NoSQL database so the answer could include anything non related to MySQL (or any SQL databases),

I feel like this should be a common issue that many big company will face and hence there should be a common (or few) solution. The root cause of this issue is that, while MySQL is great to create relationship, it will grow associative m2m table exponentially.

The 500 Millions x 100 == 50 Billions is just an example. But could theoretically happen.

Clarification

• I left query out in purpose because you can assume to most easy one.
• I'm sure if I gave few example, will start to pop optimization over the specific query, that's not the question
• I'm asking a very high level question, and if there is not a real known solution then a no with explaining why would suffice (assuming is correct)

Here an example of a simple many to many query..

SELECT user.*, item.* FROM user
LEFT JOIN user_item ON user.id = user_item.user_id
LEFT JOIN item ON item.id = user_item.item_id
WHERE user.name = 'user_1';

Similar but not same questions

• Best design for a many:many relationship issue
• Design a many-to-many table for scale
• Many Many to many relationships databse design with MySql
• better database design for nested relation (many-to-many-to-many?)

Answer 1

Preface

I think you're unfortunately misunderstanding:

1. How databases work at their core level, and
2. What some of the people of this community have been trying to communicate to you in regards to that.

Hopefully this answer helps clarify that.

I'll preface this by saying I have worked with large tables (~1 TB big) that had 10s of billions of rows in them, with queries that typically ran in under 1 second, on very modest hardware (4 CPUs, 16 GB of RAM).

I will also point out that size of data at rest is not a reason for choosing a specific database system, as they all handle the same amount of data relatively equally from a performance perspective (regardless if you're talking about NoSQL databases or RDBMS).

Data Organization

X amount of data is always going to take Y amount of time to read off disk. For example, in a 100 GB table, 1 GB of data is always going to take a consistently constant amount of time to read from the disk, it doesn't matter which database system is being used to store that data. Similarly to how a pickup truck can transport 100 bricks from one place to another, it doesn't matter what color that pickup truck is, it'll still take a consistent amount of time to transport the bricks.

The timesuck is locating the bricks that the customer wants to transport from the pile of all bricks (the table). If a customer wants 100 red bricks, and the bricks are all stored in one large unorganized pile on the ground (an unindexed Heap data structure), among 10 different colors, locating those 100 red bricks is going to take a long time to sort through all of the bricks to find.

Enter Indexes

Indexes are a feature (that almost every database system offers) as a way to organize the data in an efficient data structure for searching (generally a B-Tree by default). An index sorts the data in the table on the order of the columns specified in its definition, which then sorts related data together making it much more efficient to search than an unorganized heap table.

So if we apply an index to our random pile of bricks, let's say by color, then all the red bricks will be stacked next to each other, then the blue bricks all together, then the yellow bricks all together etc. Now instead of having to dig through the entire unorganized pile of all bricks, we can just walk directly to the red section and grab the first 100 bricks we can grab. This is obviously significantly more efficient than having to aimlessly search through all bricks.

The same is true for how data is organized in a table in a database. If the appropriate indexes are created on that table, then those indexes can be directly seeked on to the rows that correspond to the query that is asking for those rows, instead of having to scan through the entire table.

Why The Queries Are Relevant

I'll re-state what I just said above with some emphasis:

If the appropriate indexes are created on that table, then those indexes can be directly seeked on to the rows that correspond to the query that is asking for those rows

And a reminder on how indexes work:

An index sorts the data in the table on the order of the columns specified in its definition...

So in order for an index to be effective and helpful for a particular query, it needs to be defined appropriately based on the columns specifically used in that query.

In my example earlier about bricks, color was the field being searched on. If we sorted the bricks by color (defined the index by color) and the customer wanted bricks by size instead, then the index we created doesn't help us. This is akin to the WHERE clause in a query. Knowing what queries are most commonly ran, even more importantly what predicates (JOIN and WHERE clauses) those queries use, helps us define the most appropriate indexes to serve those queries.

It all goes hand-in-hand, and it's almost impossible to talk about performance in practice without talking about the queries you specifically want to perform well.

Another reason why knowing what queries will be most important to optimize for is because it may influence your table design and architecture. And there are other reasons as well, but all too many to go through in depth in one answer here. So I'm sticking to the most important one (in my opinion) to this discussion, and which is indexes.

Finale

I suppose somehow you gotta have to 'split' the data.. and there is no much else solution am i wrong?

Yes and no. You are right about the data being split but you are wrong in how you're thinking you have to do that, with Partitioning or Sharding. These aren't the right tools for this generalized discussion of performance tuning, and are only used for very specific purposes. Instead, you want Indexes again, which do split the data for you in how it's organized in that underlying data structure, again, a B-Tree.

B-Trees have an O(log2(n)) search time complexity with the way they organize data. That means in a table with 50 billion rows in it, aka n = 50 billion, the search time is log2(50 billion) = ~36. In other words, to seek on a B-Tree index against a table with 50 billion rows, only 36 of them need to be crawled to locate the data you asked for, in the worst case scenario. My graphing calculator can search through 36 rows of data in milliseconds.

As you can see, managing data to be searched for efficiently, is a solved problem, unlike you originally thought.

Answer 2

The best solution for your problem is what you already designed.

That's because all RDBMS are designed to handle exactly that: a bunch of tables, with many-to-many relations, and potentially billions of rows, where you SELECT, INSERT, or DELETE rows.

Any "special" storage system, like NoSQL, columnar storage, partitioning, etc. is useful only when you have "special" needs and your usage patterns are no more generic.

But for all OLTP and OLAP normal processing of data in a database, the schema you provided, is typical because it's the best one to solve the problem in absence of more specific characterics of data or usage patterns.

If you need to access a few rows at a time, you need indexes, and you have all the needed ones. If you need to access a great percentage of data, nothing is more efficient than a full scan.

More optimization is possible only when your data is no more "generic", but displays some particularities (in the composition, or in the access pattern) that can be optimized with some tweaking, but as long as you don't have this particularities, there are no optimizations possible and scaling is not a problem, because RDBMS are designed exactly for this task.

Of course, the response will be slower when there are billions of records, but there is no general way you could store those billion of records in a more efficient way, if you have the typical access pattern.

Answer 3

• Since there are only 100 items... If there won't be a lot more items, change to SMALL UNSIGNED (max of 65K). This will save 30GB. (Shrinking a table --> less I/O and better caching --> maybe better query performance.)

• Consider having the item VARCHAR(..) in user_item instead of needing theitemstable. If the strings are usually "short", the cost of the extra space will be offset by avoiding an extra lookup. [I did this quite successfully withpicture_idandtag`.]

• 50 billion rows is not a serious problem if you are always using one of the indexes.

• Consider INT UNSIGNED for user_id -- it will save 4 bytes over BIGINT, but is limited to 4 billion. Check SELECT MAX(user_id) FROM user to see if you are [for whatever reason] already getting into the billions.

• "otherwise we need to scan everything" -- What query is causing a big scan?

• Is ON DELETE CASCADE important? [This may not matter.]

• PARTITIONing is useful for deleting old data, but not for performance of SELECTs.

• Sharding may be useful when you have so much data that writing becomes a problem. However, the setup and maintenance is a hassle.

• When you get into terabyte-sized tables, you should compute how long it will take to fill up the table. 50 billion rows, even if batched, could take weeks or months. A hardware RAID controller could help a little.

Answer 4

This is a great question, but there's not a simple answer - particularly with the "ignore query pattern and schema/relationship". Those two are needed if you are aiming at optimizations to help you scale. Would love to know more about that. The "NoSQL to help scale" has proven to many to be a non-answer. If the data is relational (absolutely if it's transactional and relational) you will end up compensating for the nature of the things the NoSQL database concedes in your app layer. NoSQL databases as a category relax consistency and transactional correctness and often abandon the relational model. Re-implementing these in your application can be as complex (in some cases more complex) as the question of "how do I scale the database layer". That said - there are good answers for this pattern in the NewSQL world. I want to acknowledge I have a bias - I work for a database startup (Regatta) that has built a transactional, relational database that scales to hundreds and thousands of nodes, PB of data, trillions of records, and millions of TPS with strict serializability and external consistency. Oh, and we can do analytics directly on that data too. This has been viewed as an unsolvable problem, so people have often started with abandoning transactional/relational properties to scale out, or just accept sharded islands. Would love to talk to you about it, and put us through out paces - we were built for this!

Answer 5

Ok I'll mark my answer as accepted but if another more complete answer comes out in the future I can change it, I really don't care, important is the most correct/complete answer to my question.

My question has been greatly misunderstood and went in all different direction (except Andrea B. one).

However, especially thanks to the 'conversations' in the comments, some part of the answer comes up, so if we combined comments + pieces of answer I think we can answer properly. I don't mark Andrea B. answer though because after learning it I've a more complete answer.

---

So how can we solve a possible table, in this case ManytoMany - Associative table (which by nature is the easiest to grow in size compared to others).

We can assume that the schema its self is well designed at its maximum (column datatype etc) as well as query patterns (SELECT, INSERT ...) imagine/assume they have been already optimized to the maximum and there is really no better way to do them. And is someone reading this answer is unsure, can go have a look at this guide of Many-to-Many by Rick James, is pretty cool I think.

But in your case, imagine you also know the rows of this table will grow exponentially, and soon or later will go over billions, what do you do?

First of all, it seems there isn't accepted way or 'technique' that works all the time so all below solution may or may not work (a.k.a are all workarounds) .

Among all 'solution' is seems that they have all 1 thing in common, there are basically some form of:

Divide-and-conquer algorithm

In other words, you need to find a way split the data as much as possible to make it more manageable. But in the same time, don't split too much because you may end up on a worst position, for instance, you need to being able to still retrieve SELECT data in a fast way, so keep in mind to avoid 'scanning' all this 'divided' 'part' (here I am still talking in a very high level and is an abstract idea, I'm not talking in anything in specific!)

Here are the techniques

• Split data on the WHERE clause
• Split data on the INDEX
• Split data on usage | the 'Archive' concept
• Sharding

Split data on the WHERE clause

This is the most obvious one and pretty basic, but may not work for all queries or sometimes you really need to find something and require to scan 'all data'. Obviously here comes along the LIMIT and OFFSET and all good practices.

Also, copied paste from comments (sorry I would link comment if was possible)

The contents of a WHERE clause is very relevant to performance. Fetching one row with an exact value will be fast if the indexing is good; fetching with OR or RLIKE leads to a table scan -- thereby being as slow as the table is big

You never want to do a CROSS JOIN, especially not when the result set is 50B rows. So, the Optimizer will look at the WHERE and ON clauses to avoid doing that. [Hence the repeated plea to the OP for the queries that will be run.]

Split data on the INDEX

Taken from J.D. Answer on the Finale (after talking about bricks) is actually pretty interesting.

I won't add what he wrote to avoid repetition so you should check out that answer but the technique is true. While I personally know it I think is different if you think it in that way and have that explanation in mind. Really we are just using indexing to split 'data population', Divide-and-conquer.

Split data on usage | the 'Archive' concept

Use Least recently used (LRU) for instance

An example of "access pattern" is News articles. Most people search for "recent" articles -- the articles on the current hot news topics. This tends to bias queries toward the "end" of the table. This can be helped by LRU and by clustering on date.

So this may not work for all cases for sure but, if you can implement a logic where basically, you avoid access all data if you know is 'old' or less used. Here may be different ways to achieve this

• bias queries toward the "end" of the table with a DATETIME column (probably) - (or could be even id bigger than <VALUE> etc..
• What if you can move 'all data' into a separate table (or database) and is access only when requested or the data you are looking for is not there.

For the second point, for instance, if you recognize a pattern in the data where, lots of data (maybe even most) is not accessed anymore you could move that (or rename the table) into another one ( user_item_archive ) then you create a new user_item and work on the fresh one. This is oversimplified and depends on use case but the important is the concept.

I'm pretty sure there are articles online about this concept, if someone finds any (or if I will in the future) we could add here.

Sharding

This is the only 'well known' technique but it's a double-edged sword for sure.

This blog on percona is very interesting

Someone mention partition, but I don't recommended because it as IMO little to none use cases and I see it more for when you need to delete data. Accessing data with partition already may lead to a lot of trouble.

Furthermore from this answer by Rick James while the first part tries to optimize the schema example (which is good but it was just an example) The last 2 bits are interestings IMO

Sharding may be useful when you have so much data that writing becomes a problem. However, the setup and maintenance is a hassle.

When you get into terabyte-sized tables, you should compute how long it will take to fill up the table. 50 billion rows, even if batched, could take weeks or months. A hardware RAID controller could help a little