MySQL - Left Join takes too long, how to optimize query?
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 &gt; 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).