Database Normalization Causing Inefficiency

Question

Note: I am relatively new to managing an SQL database. I have done my fair share of reading, research, and experimentation, but it is possible that I am missing some fairly basic knowledge. I'm also not sure how to tag this question so if someone could add relevant tags that would be appreciated.

---

I am currently building an SQL database for a forum like website. Among other things, the website will contain pages with threads, basically a series of posts by different users.

Users on the website are identified by a unique ID (char(36)) that is set once at registration and cannot be changed afterward. The user also has a username (varchar(16)) that is just a screen name. This name is almost always unique between users, but not necessarily. The user can also change the name, but there is a hard limit of two weeks between any two username changes. All of this information, and a few other things like login details, are stored in one Users table with the ID as a primary key.

There are multiple tables for the forum itself, but the one that is important for this question is the Posts table (primary key is 'post_id' int(10) NOT NUll AUTO_INCREMENT PRIMARY KEY. It contains one row for every time somebody makes a post on a thread, including responses to existing posts. As a result, whenever a user requests a thread, I query the posts table for all posts matching that thread (I store a thread ID foreign key). My question now concerns storing a user who is the author of the post. When a thread is requested, I need to send the username (not ID) of the users that made different posts. However, I also need to make sure that changes in usernames do not cause the apparent author of a post to change. As far as I can tell I have two possibilities:

1. For storing the author of a post, I can store only the ID. However, this means that I will have to make quite a few requests to the Users table for the usernames of the various IDs of the posters. This seems highly inefficient, seeing that the usernames will change very rarely.

2. I can store both the author ID and the author username in the Posts table. I can then go through the table and change all usernames among the posts (I can even set this up with a trigger, I believe). However, this opens the window for update anomalies, if the username stored for an ID in the Users table is different than in one of the posts. I can still use a trigger to prevent these anomalies at the database level, but from what I understand this should not be necessary in a well-designed database.

Which one of these two solutions (or something entirely different) should I use to both maintain efficiency and database normalization?

If it matters, I'm using the most recent version of MariaDB and accessing using PHP.

Answer 1

I'm using the most recent version of MariaDB [...] 10.0.31-MariaDB-0ubuntu0.16.04.2

That's not at all the "most recent version". MariaDB 10.0 was released on 12 Nov 2012. That's not even the most recent security release which goes to 10.0.33 released on 30 Oct 2017. The version you're on has been frozen for over 5 years (no development except fixes just handling "security issues and bugs")

I am currently building an SQL database for a forum like website. Among other things, the website will contain pages with threads, basically a series of posts by different users.

In order to build threads, you really need Recursive CTEs. This is a hierarchical question and you can't model hierarchy relationally without recursion. MariaDB added Recursive CTEs in 10.2.2, that went stable in 2017-05-23 with 10.2.6.

With that you could get the job done, but if you haven't started the job, give PostgreSQL a shot. I did this very task here. You can just take that code and your done, and if you migrate to PostgreSQL you get an all around better database too.

For more information on the problem domain, check out hierarchy

Answer 2

With regard to the threading issue that people have picked up on as much as your question about user id and name normalisation, without using CTEs there are a number of ways to arrange hierarchies to allow efficient retrieval of threads or portions thereof. You could store a materialised path to each post for instance. Efficiently dealing with trees in SQL is a subject whole books could be (and have been) written about, so I'll not go into more detail here. For a quick primer the relevant chapter in Bill Karwin's "SQL Antipatterns" (a book I recommend generally) is a good place to start, or for a fuller analysis Joe Celko's "Trees and hierarchies in SQL for Smarties", or search online for the tree management methods (with search terms like adjacency list, materialised path / cached path / path enumeration, nested sets, and of course recursive CTE / recursive common table expression).

On to the actual question:

For storing the author of a post, I can store only the ID. However, this means that I will have to make quite a few requests to the Users table for the usernames of the various IDs of the posters. This seems highly inefficient, seeing that the usernames will change very rarely.

This is normal and should not be significantly inefficient. You will not be performing a separate lookup for every user ID spotted, instead you will use a JOIN and let the SQL engine worry about that for you which it will do well if you give it good index choices to work with. Something like:

SELECT posts.postTitle
     , posts.postText
     , posts.postTimeStamp
     , users.fullName
FROM   posts
JOIN   users
       ON users.id = posts.userID

Having said that, it is important to note that data normalisation is not about performance efficiency it is about protecting data integrity/correctness and (less importantly) storage efficiency: in this instance if you avoid having several copies of the same data (the username) you avoid the possibility of inconsistency because one or more copies disagree with the others.

I can store both the author ID and the author username in the Posts table.

Unless you want to allow usernames to change and keep the original name displayed, this is unnecessary and you should use normal form and a join, as above.

Before trying to support name changes in a particular way, first decide if you actually need to allow them at all. If the name in question is an account name then perhaps you don't need or want to support it changing at all. If it is a personal name or email address, both of which can change over time, then you perhaps want to change all instances when this happens so you don't have to worry about it: just update the name in the users table and future queries like the above will get the new data instead of you needing to

go through the [posts] table and change all usernames among the posts

at all.

Things get a bit more complicated if you want to maintain the display of the user's name at the time they made a post instead of old posts being displayed with the new name. You could store "name at time of post" in the posts table, and with this requirement you don't need to update it when the user's name changes (you are wanting to keep the old name). The other option is to keep a history of the user's record in normal form and using that to ready the correct name. This will be more efficient for storage (and less likely to become inconsistent due to bugs) but reading the username-at-time-of-post can be more complicated and will vary depending on what your chosen database supports (does it have efficient window functions?) and how you chose to store the history (using "system versioned history table" support in SQL Server or Oracle for instance). I'll not go in depth on this, as I suspect simply letting the displayed name change when the user's details change is perfectly fine and easy to implement.

Side note: key type choice

With CHAR(36) I assume you are using UUIDs for internal user ID? Unless you have reason to use UUIDs (the requirement comes from elsewhere and is not in your control, you are writing a distributed system and are concerned about key collisions for users created in different locations, ...) you might want to consider using an automatically incrementing integer instead (INT NOT NULL AUTO_INCREMENT in mysql/mariadb, INT NOT NULL IDENTITY(1,1) in MSSQL, ...) which will only use 4 bytes per key.

The same for post IDs if you are using UUIDs for them also.

For space efficiency some DBS support packed UUID types (UNIQUEIDENTIFIER in MS SQL Server, UUID in postgres, ...) which will store the value in 16 bytes instead of 36, but I don't think mySQL does. You could use BINARY(16) but you may need to faf around converting back and forth when reading/writing the values so that probably isn't recommended.

Depending on the number of rows you expect the difference in key size may not be significant to worry about, but if you plan for your application to scale into something huge it should be considered in the early design stages (making key type changes is a nightmare once an application has already rolled out!).

Answer 3

I would suggest going for option 1. Your DB would be normalized and you can achieve data integrity by leveraging the foreign key features provided by InnoDB engine.

For instance:

Create table posts (
post_id Int(10) NOT NULL AUTO_INCREMENT,
author_id Char(36) NOT NULL,
Primary Key (post_id)) ENGINE = InnoDB;

Create table users (
id Char(36) NOT NULL,
username Varchar(16),
Primary Key (id)) ENGINE = InnoDB;

And then you define a foreign key relationship to maintain integrity:

Alter table posts add Constraint rel_post_author Foreign Key (author_id) references users (id) on delete restrict on update restrict;

What happens on delete or on update is up to you, you may want to refer to MariaDB doc here: https://mariadb.com/kb/en/library/foreign-keys/

This would be the simplest option in general, unless you have some VERY HIGH load to justify some de-normalized database design.

For example, you may have relational tables defined as I suggested above and have another set of tables optimized for read-only operations: one of such tables would store both the ID and the name of the post's author along with the other post's columns.

Another option that you may want to consider is using Views. See here: https://stackoverflow.com/questions/10302615/mysql-views-performance

Answer 4

The "Entities" you have are

• Users -- with an AUTO_INCREMENT, not a UUID
• Posts -- with post_id as PK, and a parent_id to define the threading. A parent_id is either 0 (start of threading tree) or a link (via "self join")

To keep from having username changing in lots of Posts, copy it into the Post. The probably requires two fields -- one for the true user identity (user_id), one for the as-posted- identity (username).

"Normalization" allows the changing of a name without retroactively fixing all the places where it is used. That is not your use case. So don't use normalization.

That said, let me point out how someone might "game the system" and cause you trouble. A user adopts someone else's name, makes a few nasty/naughty posts, then changes his name back. I suggest you disallow ever reusing a username. This would involve making it UNIQUE and living forever (with a deleted flag).

If you change your mind about having both a true identity and a identity-at-the-time, then all you will need is user_id, plus a JOIN to get the unchanging username.

And if you do that, you can get rid of user_id and simply use username as the PRIMARY KEY and key to JOIN on.

All of the above applies to any version of MySQL/MariaDB.

You may need CTEs for traversing the "tree" of posts. For CTEs, you need MariaDB 10.2 or the, as yet not-GA, MySQL 8.0.

(Why UUIDs are evil for huge datasets: Blog)

(FOREIGN KEYs are a crutch for not debugging/testing code. INDEXes, including those auto-generated by FKs, are important for performance, especially for huge databases.)

Answer 5

I would suggest one potential general change, as well as two options.

The potential general change: Don't use that char(36) as your unique user identifier for the joins within your database!!! Even if you can't easily change the web code, put in an integer type author_int_id column for joins and foreign keys

• it uses far, far too much space in each table and each index
• performance will degrade due to both the size, and how much work chars are due to collation, and since you're concerned with performance

For your actual lookups of post to author, there are two major possibilities that I see as wise:

• Option #1 is a reasonable choice as long as you do NOT do one call to get posts, and a second call to get usernames. Instead, do a call that gets both the posts and the usernames all at once with a simple inner join across a foreign key that's backed by unique indexes.
• Option #3 is a different design entirely; definitely add the foreign key for referential integrity reasons, but instead have the web code itself cache the userid to username mapping in some global storage - read it in once at the beginning.
  • Since the web code is where usernames would change, the web code should update the cache as well as the database each change.
    • If you have multiple servers without shared RAM, well, in the rare case a username changes, it's not the end of the world if the old username shows up for a while. Add an indexed last_changed column to the users table and refresh the username cache once every hour or so with what's changed recently and you'll be fine. Warn the users that username changes take some time to propogate when they're doing the change.
  • When a userid is found that isn't in the cache table... look up all new users from the database (see last_changed column, above) and add them! Again, this is for web servers not sharing a cache.
  • This is solely because you seem highly concerned about very minor database load, and I assume that your database server is heavily loaded.