Innodb primary key advice
Simply put, as the table (or index) grows, the performance approaches a minimum of one disk hit per lookup.
This is because UUIDs (other than a version 1 UUID with the bits suitably shuffled) are effectively &quot;random&quot;.  That is whatever is in the buffer_pool cache is approaches being useless for the next lookup.
You seem to have 3 such indexes; this means that even inserting one row is threatening to require 3 disk hits!  20M new rows per month = 8 rows per second = upwards of 24 disk hits per second just for the insert traffic.  You could tackle this with a huge amount of RAM or by avoiding the 3 UUIDs.
Similarly, any SELECT that uses an INDEX starting with one of those uuids will incur 1 disk hit.
Keep in mind (for InnoDB) that the PRIMARY KEY is a big BTree with all the data, sorted by the PK.  And a secondary index is a smaller BTree with the key column(s) plus the PK's column(s).  So, some things stated about the PK and the seocndary key are interchangeable.
Of note,...  When looking up a row by a secondary key, two BTree lookups are performed, one per BTree involved.  If both are UUIDs that could mean 2 disk hits.  If you have started, and used composite indexes starting with started, and most queries reached for data around the same time, then you get &quot;locality of reference benefits.  That is, everything might be cached and you won't need disk hits.
All of this leads to the beauty of using UUID, version 1, and rearrangin the bits so that the &quot;time&quot; part is in the high order bits.
(For your Q2 and Q3)  Assuming you now have
PRIMARY KEY(started),
INDEX(app_id_one),
INDEX(app_id_two),
INDEX(app_id_thre),

And assuming you are using InnoDB, then you already have started implicitly tacked onto the end of the 3 secondary indexes.  If, instead, you had
PRIMARY KEY(started),
INDEX(app_id_one),
INDEX(started, app_id_two),
INDEX(started, app_id_thre),

then the indexes would take exactly the same amount of space.  (OK building a BTreee leads to some unpredictables variations in &quot;fragmentation&quot;, etc.)
Using a DATETIME as the PK is risky unless you are very sure you won't have any duplicates.  Changing the PK to INT or BIGINT (presumably AUTO_INCREMENT) would not change the principles here; just a slight difference in space needed.
pt-online-schema-change or gh-ost or MySQL 8.0 can change the existing table's indexes with minimal interruption.
I don't understand how you can change from the current WHERE app_id_two = ... to WHERE started = ... AND app_id_two = ....  If you currently have started available, then just use it and get rid of the other columns??