15

Lets say I have students and classes which are 2 entities. A student can take many classes and a class can have many students. This would be a many to many relationship.

To solve this with an RDBMS my understanding is that one would create a joining table, so the tables would be:

student table

student_id | student_name
--------------------------
s1         |  john
s2         |  jane
classes table

class_id | class name
---------------------
c1       | asking questions on stack overflow
c2       | designing database systems
joining table

student_id | class_id
---------------------
s1         | c1
s2         | c1
s1         | c2

The 2 kinds of queries I would want to answer are:

  1. what classes is student <student id> taking?
  2. what students are enrolled in class <class id>?

I could query the joining table for this information but I imagine queries would be slow since there's no clear way to horizontally partition the data. For the queries above, I'd want 1 partition scheme on student id, and another separate partition scheme on class id. Which databases support this? I could have indices on both columns to help speed up queries.

Would a different data model work better?

What about graph dbs? I would imagine that graph dbs could support bi-directionality: i.e s1 isMemberOf c1 and c1 Contains s1

The third option I can think of is a no-sql format: i.e I would have a "student" document and a "class" document. A student document would be a JSON document under which there is an array of classes. A class document would contain an array of students. This means only 1 "slice" of information would be accessed at each point. But the data is not normalized here and it can get difficult to manage.

12
  • 51
    If your concern is performance, stop right now. You should handle performance issues when measurements show that they are there. The join table is the canonical approach in RDBMSs and will likely perform well given appropriate indexes. Nov 6, 2023 at 5:56
  • 41
    Never optimize for imaginary problems. All SQL databases are optimized for this Nov 6, 2023 at 6:30
  • 34
    Developers who have no background in databases often find imaginary inefficiencies in SQL - things that are not found to be slow as matter of fact, but which they believe must be slower than possible based on some inference from what they can see or what they think is happening. It's generally a mistake to embark on these kinds of efficiency assessments when just learning the basic tenets.
    – Steve
    Nov 6, 2023 at 11:15
  • 10
    The previous three comments should all be posted as answers :) Nov 6, 2023 at 11:27
  • 8
    "But the data is not normalized here and it can get difficult to manage." — people don't realize how complex and confounding this problem can be. It is good you understand this. Nov 6, 2023 at 14:40

4 Answers 4

48

Quote of the day:

Premature optimization is the root of all evil
- C.A.R. Hoare

There is no reason to assume that the join will be slow, if you made sure that the join table is indexed on its both foreign keys. SQL engine optimizer usually do a much better job than hand-crafted optimization.

You could of course use different models. In nosql document oriented databases, you'd probably have a list of attended courses in each the student document, and a list of students in each course document (in this article, you'll find an example using document references). However, you'd have to maintain consistency between these lists, which is not a simple matter if there is a high number of simultaneous changes.

A graph database could be another option, but navigating the graph in this example will not necessarily be faster than a join on an RDBMS. It's however easier to maintain consistency than with document databases thanks to the use of bidirectional edges.

Other nosql structures such as key-value store would boil down to the same kind of strategies as above, with you having to ensure the consistency AND on top of that manually optimize the different possible access strategies.

Conclusion: unless there are other architectural considerations that you omitted to share, start with your join table and the correct indexes, and consider the alternatives to improve performance only if you really encounter a serious performance issue.

14
  • 14
    "SQL engine optimizer usually do a mich better job than hand-crafter optimization" or at least, SQL engine optimizer will get within 10% of the hand-crafted optimization with 1% of the effort and that's almost always the right trade-off. Nov 6, 2023 at 13:02
  • 2
    @PhilipKendall: You mean, 99% of the time, SQL engine will get within 10% of the hand-crafted optimization with 1% of the effort. Because sometimes, they can be really, really, dumb... Nov 6, 2023 at 14:08
  • 1
    Note that a number of SQL databases enforce the creation of indexes to support foreign keys (or do so automatically) -- so as to be able to quickly validate whether there's a child record when deleting a record from the parent table. Nov 6, 2023 at 14:12
  • 1
    @JeremyFisher: Use prototype-driven design. Imagine your current project as a prototype of your planned project, and take notes on what does and does not work during its development. Then, when you're ready, throw out the prototype and reimplement it from scratch. In this particular case, imagine that each SQL query is a prototype of a planned query workflow, and be prepared to rewrite slow or incorrect queries.
    – Corbin
    Nov 6, 2023 at 18:32
  • 2
    Minor point: it's actually C.A.R Hoare, not T. Hoare ("Tony" is the shortened form of his middle name, Antony).
    – psmears
    Nov 7, 2023 at 16:58
19

I could query the joining table for this information but I imagine queries would be slow since there's no clear way to horizontally partition the data.

Assuming the Primary key on this table is { student_id, class_id } (just based on how you've shown the columns) then it's already "partitioned" one way (by Student).
To "partition" it the other way (by Class), simply add an index on { class_id, student_id }.

That way, it doesn't matter which field(s) you query by; the DBMS will always have a suitable index to query the table efficiently.

7
  • If both ids are foreign keys, aren't they already indexed?
    – Laiv
    Nov 6, 2023 at 15:36
  • 11
    Not by default, no. /Primary/ Keys are automatically indexed. Foreign Keys may not be.
    – Phill W.
    Nov 6, 2023 at 15:38
  • 1
    This is also a great answer! Nov 6, 2023 at 16:47
  • Unique keys would be indexed and enforce uniqueness, depending on your needs.
    – ps2goat
    Nov 7, 2023 at 4:31
  • 1
    @PhillW. Some databases, e.g. MySQL, require an index on foreign keys, and automatically adds an index if necessary when you create the FK.
    – Barmar
    Nov 7, 2023 at 16:10
9

I’m going to jump on the premature bandwagon, but from a different direction. I know your students and classes are placeholders for something else, but…

How many students and how many classes are we talking about? Unless you have millions of both, it probably doesn’t matter what you use. You use a database in that case not because it’s faster than what you would write (although it will be) but because it’s so dramatically easier to write. Once loaded your times are probably going to be totally irrelevant.

Here’s some hashtable benchmarks from a nearly a decade ago, https://jimbelton.wordpress.com/2015/11/27/hash-table-shootout-updated/, note that the first increment is 5 million, and for some of the test that still barely gets off of zero seconds, here’s a blog on writing a really fast hash map, https://probablydance.com/2017/02/26/i-wrote-the-fastest-hashtable/.

Create a million classes, create a million students, find all students, and link them, should be basically no time. Take a look at the fastest article, 100 million objects and lookup is still under 150 nanoseconds for the slowest.

And that’s using a hash table, it would probably be feasible to use a raw array (references/pointers are 4/8 bytes and storing a couple million of them isn’t a problem for most modern systems, outside of embedded systems).

Basically, databases don’t get slow because they have a few million entries, they get slow when they have complex joins on unindexed data. If your bridge table is well indexed (typical bridge table has 1 for each column, each including the other column) finding a crossing is going to be so quick as to be irrelevant.

Here’s a SO question about to use MySQL with a table with 100’s of millions of rows. https://stackoverflow.com/questions/38346613/mysql-and-a-table-with-100-millions-of-rows. Also, last I knew SO runs on sql server, and look at the number of posts, answers, and comments on it https://data.stackexchange.com/.

It sounds like you can use a sql database, go ahead and do so.

1
  • 6
    How fast the hash table is barely matters. What databases are good at is loading the right data from disk, since most queries are IO-bound.
    – Bergi
    Nov 7, 2023 at 9:43
1

I could query the joining table for this information but I imagine queries would be slow since there's no clear way to horizontally partition the data. For the queries above, I'd want 1 partition scheme on student id, and another separate partition scheme on class id. Which databases support this? I could have indices on both columns to help speed up queries.

Most of the responses seem to be ignoring this. This answer doesn't seem to describe what a partition actually is.

A horizontal partition (in this context) is when the data is too big to fit on one database server. So you partition it onto multiple servers. You do this by dividing on characteristics of the data. E.g. some students go on one server and some students go on a different server.

If this is actually a serious problem, then you need two tables. Both tables will have identical information. One will be partitioned by student and the other by class.

As this answer already noted, it is unlikely that you will be facing this problem as an actual constraint. There is no school that is so large that you need to partition either by student or class. Seven million students and fewer classes is well within the range of a database. Even two hundred million students over a century would be fine. A billion is only thirty levels deep in a balanced binary search tree. So no need to go through engineering gymnastics to enable partitioning.

If you are instead looking at a group of schools, then you partition both student and class by school. Because students mostly go to classes at their own schools. The exceptions can be handled by pretending that Harvard:Joe and MIT:Joe are two different students. Or by pretending that MIT:Joe attending Harvard:English is actually attending MIT:EnglishAtHarvard. Or by partitioning both Harvard and MIT on the same server (won't scale to all schools though). Which is preferable would depend on how you needed to use the data. You might even use two or three search indexes, each using a different pretense.

Using lessons from consistent hashing, you might even duplicate some data on multiple servers based on different partitions. For example, Harvard:English might appear on Joe's server and Sara's at the same time. Joe attends MIT and Sara Harvard.

If you are using students and classes as a proxy for something else, then we can't help you. Because the characteristics of the underlying data will determine how you handle it. First find where your data has actual limitations and then solve them for that specific data space.

If the data is small enough to allow it, the simple join table is going to be superior to partitioned solutions. Because they tend to either require data duplication or some data can't be compared to other data (because it's on different servers). This isn't an area for a one-size-fits-all solution.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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