2

A leader may have many followers. A notification_followers table gets a single notification when a leader adds a post with an entry leader_id 1 and notifiable_id 0 (id 1,2 in table). The same table gets a single notification when the current user 14 is followed by someone, with an entry leader_id 0 and notifiable_id 14 (id 3 in table).

notification_followers (id is PRIMARY, each field except data is an index on its own)

| id | uuid               | leader_id | notifable_id | data   | created_at
-----------------------------------------------------------------------------------
| 1  | 001w2cwfoqzp8F3... | 1         | 0            | Post A | 2018-04-19 00:00:00
| 2  | lvbuX4d5qCHJUIN... | 1         | 0            | Post B | 2018-04-20 00:00:00
| 3  | eEq5r5g5jApkKgd... | 0         | 14           | Follow | 2018-04-21 00:00:00

All the follower related notifications are in one place now which is perfect.

We need to now check if the user 14 is a follower of leader_id 1 to know whether to show them notifications 1 and 2. For that, we scan the user_follows table to see if the logged in user exists as a followed_id to the leader_id so they know about the notification, but only if they followed the leader before the notification was posted (new followers should not get older post notifications when the follow the user, only new ones).

user_follows (id is PRIMARY, each field is an index on its own)

| id | leader_id | follower_id | created_at
----------------------------------------------------
| 1  | 1         | 14         |  2018-04-18 00:00:00 // followed before, has notifs
| 2  | 1         | 15         |  2018-04-22 00:00:00 // followed after, no notifs

The final thing to note, is the user should know if the notification was read or not, this is where the notification_followers_read table comes in. It stores the follower_id along with the notification_uuid for all read notifications, along with their read_at timestamp.

notification_followers_read (composite index on notification_uuid, follower_id)

| notification_uuid | follower_id | read_at
--------------------------------------------------------
  qIXE97AP49muZf... | 17          | 2018-04-21 00:00:00 // not for 14, we ignore it

We now want to return the latest 10 notifications ordered by the auto incrementing nf.id desc for user 14. They should see all 3 notifications from notification_followers, since non of them were read by this user yet. The first 2, since they followed the leader before the leader made the posts, and the 3rd notification, since they were followed and their notifiable_id is 14.

Here is the query which works, but take too long ~9 secs:

SELECT nf.id, nf.uuid, nf.leader_id, nf.data, nf.created_at, nfr.read_at
FROM notification_followers nf
LEFT JOIN user_follows uf ON uf.leader_id = nf.leader_id AND uf.follower_id = 14
LEFT JOIN notification_followers_read nfr ON nf.uuid = nfr.notification_uuid AND nfr.follower_id = 14
WHERE (nf.created_at > uf.created_at OR notifiable_id = 14)
ORDER BY nf.id DESC LIMIT 10

notification_followers has ~100K records and we're using InnoDB. Here is the EXPLAIN for the query:

Explain

How can we optimize the query so it runs in a few ms?

UPDATE WITH SQL DUMP

SQL DUMP TO REPRODUCE LOCALLY just create speed_test database locally and import file to see the slow query issue live with all the table data (~100K rows).

  • Is follower_id a different value then notifable_id? It seems you are doing unneeded filtering by adding follower_id = 14 t both join clauses and that just doing notifable_id in the where clause should cover it, – Joe W Apr 25 '18 at 20:18
  • @JoeW 14 is the currently logged in user in this case. In user_follows table they are follower_id to identify them with the leader_id there. In notification_followers_read table they are follower_id to identify them with the notification_uuid. In notification_followers they are notifiable_id only when a user follows them, not a new leader post, so we can identify that they were followed. – Wonka Apr 25 '18 at 20:52
  • My point was it looks like there was an unneeded filter on both the user_follows and the notification_followers_read tables since you can put it in the where clause and filter it a single time rather then then it being filtered 3 times like it is now. – Joe W Apr 25 '18 at 20:56
  • @Joe W: But reducing the cardinality of the sets to join as early as possible is likely to reduce the costs of the join. – sticky bit Apr 25 '18 at 21:02
  • 1
    I had an execution time of about 4 secs without and .2 secs with the indexes i mentioned. But I don't dare to give much on that. On the plus side it ran on a 12 year old notebook which was middle class, when it was new and I also use as a desktop. So a dedicated server can presumably cope better. On the other hand the database server is just for some testing and didn't really do much. So especially the pressure on the system buffer might be very low compared to a server with realistic load and thus more (expensive) disk IO. – sticky bit Apr 27 '18 at 14:41
3
+100

Summary from the comments:

So far I'm getting the best result with

CREATE INDEX nfr_fid_nuuid
             ON notification_followers_read
                (follower_id,
                 notification_uuid);

and

CREATE INDEX uf_fid_lid
             ON user_follows
                (follower_id,
                 leader_id);

and all the other indexes, except the primary ones, dropped. For notification_followers it used the PRIMARY index with me. I couldn't find anything better than PRIMARY for this table so far.

Tests were done on a MySQL v5.7.21 32 bit on Windows 7 32 bit.

Execution times were about 4 secs without and .2 secs with the indexes as stated above.

Some lines on how, why and whatever: (haven't had the space for that in the comments)

(Disclaimer: My knowledge on that shouldn't be All bad overall. Though, in some aspects my understanding might be improvable or just plainly wrong. Anyone feel free to correct me if I'm wrong somewhere -- edits or comments welcome.)

A general thing about joins in terms of performance:

As already mentioned in the comments, one goal with joins is to keep the sets joined as small as possible, as early as possible. For illustration: In the worst case, when a nested loop join must be applied, an A JOIN B needs #A*#B (let #A be the number of rows in A, analog for B) comparison operations. So any row from A (or B), which can be ruled out before the actual join operation is applied, will reduce the number of operations not only by 1 but by #B (or #A). One would want that in terms of performance.

If a join can be done via an index, especially in a way, that the DBMS can easily localize the portion of the index relevant for the join (i.e. keeping the set small), that can be a huge booster. Of course there are some other advantages an index can provide here (e.g.: the rows are already accessible in a sorted manner supporting more efficient join methods, the index might be significantly smaller and fit largely into memory thus reducing the need for constant disk IO, ...).

But all that is a topic on it's own, so this is just meant as a rough abstract.

On the query the question is about:

Now first thing to notice about the query: It is a LEFT OUTER JOIN (OK actually it's two but that doesn't matter for this thought). notification_followers is the left table here, so its set of records won't get reduced by the joins, just the WHERE can do that.

The WHERE unfortunately is an OR. These are difficult and "bad" in contrast to AND. It is more like a union hence keeping the set large, than like an intersect reducing the set's cardinality (Compare: For A OR B the result set is all rows WHERE A UNION all rows WHERE B in contrast to A AND B for which the result set is the all rows WHERE A INTERSECT all rows WHERE B).

So the WHERE isn't a too promising target to be answered from one index alone in a single run. Furthermore one of the ORed operations from the WHERE (nf.created_at > uf.created_at) depends on the joined data, so that one can only be applied after (or at best while) the join.

There is also the ORDER BY which can be expensive especially, when the result set is too large to be kept in memory. It then needs to be sorted with constantly writing and reading from the disk (for a larger buffer). And disk access takes a lot of time.

So my hope for notification_followers was to find a compound index, that would support the ORDER and ideally at least one of the ORed comparisons. As mentioned I failed on that. But my expectations also weren't too high on that, given the discussion on that part above.

Or PRIMARY is just good enough for that in the view of the DBMS, which might be fine. As I understand tables with a primary key in InnoDB are actually stored as clustered indexes. What I couldn't find (quickly) in the docs was, if the records are also double linked in order by the primary key. That would allow PRIMARY to support the ORDER by a reverse traverse of that linked list and make PRIMARY a good choice indeed.

The ONs of the joined tables are rather easy in contrast to the WHERE and the ORDER. (Exemplary I will use the join with user_follows, notification_followers_read is analog.) Here we have two relevant columns, leader_id and follower_id.

follower_id seems to be more suitable for the first column of a compound index. It's compared with a literal, hence independent of the partner rows of the join. The relevant portion of the index, a subtree -- "normal" indexes in MySQL are some B tree variant -- can thus be (re)used for all join partners. And also note the reduction of the set of possible rows from user_follows here!

Also having leader_id as a column in that index should then make the user_follows's part of the join answerable from this index alone. And indeed it worked.

Note, that the order of the columns in the statement isn't necessarily the same for an index on them. Whatever is commutable is commuted by the optimizer, if it promises to be better. So the order won't be necessarily kept anyway. To find a good order of columns for an index one must mainly think about what order would partition the index in a most "radical" fashion first (leaving the remaining part as small as possible).

  • This is a really great explanation, thank you for taking the time to type up this detailed answer. It really helped me so much and I now understand a bit more why the query time shrunk drastically. You ended my 5 day frustration with this issue and for that I am awarding you 100 point bounty as a thank you as soon as SO lets me. Thank you so much again sticky bit. You're awesome!! – Wonka Apr 28 '18 at 1:56
  • So it seems the query was slow when it was a user that was not 14, I also read that OR is slow, and better to use UNION. So I split the query into two subqueries (both using indexes), with UNION. One of them is very fast, the other, really slow ~9 secs So I created a question here with the slow query stackoverflow.com/questions/50476360/… Also we had to add a follow_status to the user_follows table. That's the only difference. – Wonka May 22 '18 at 21:03
2

Do not blindly use LEFT. I think that the first LEFT is wrong, and the second can be reformulated as follows.

SELECT  nf.id, nf.uuid, nf.leader_id,
        nf.data, nf.created_at,
        ( SELECT  read_at
            FROM  notification_followers_read
            WHERE  nf.uuid = notification_uuid
              AND  follower_id = 14 
        ) AS read_at
    FROM  notification_followers nf
    JOIN  user_follows uf  ON uf.leader_id = nf.leader_id
    WHERE  (nf.created_at > uf.created_at
              OR  nf.notifiable_id = 14 
           )
      AND  uf.follower_id = 14
    ORDER BY  nf.id DESC
    LIMIT  10 

ON should show how the tables are related, and not include filtering criteria.

Indexes:

notification_followers_read:
       INDEX(notification_uuid, follower_id,  -- in either order
             read_at)   -- last (to make it 'covering')
user_follows:
       INDEX(leader_id, follower_id,  -- in either order
             created_at)   -- last

(These indexes do not disagree with stickbit's, but they improve on them.)

  • Thanks for jumping in, I tried your query, but if you compare yours with the original, it seems your query results are missing the first id 100001 – Wonka May 19 '18 at 23:49
  • It was also ~5-6s as opposed to the other query ~25ms (both queries using your indexes) – Wonka May 20 '18 at 0:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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