第一个语句：
从sql语句本身来说，是单表查询，已经使用了索引，且索引中选择性较高的字段userid也放到了前面，感觉没什么可以优化的地方。
从业务逻辑来说，可以考虑是否能增加insert_time的条件，并创建(userid, insert_time)的索引，这样通过索引能够过滤掉的记录更多。
还有一个思路就是拿空间换时间，创建一个包括查询结果和条件所有字段的索引，如(user_id, priority, notify_id, notify)，这样只用查询索引就能得到结果，避免了回表的查询成本。
另外就是看业务上是否允许不排序，这样可以减少mysql做排序的成本。

第二个语句：
除了第一个语句的优化思路外，可以考虑重写sql，让mysql使用索引idx_userid_notifyid

SELECT notify_id, notify, priority FROM t_user_notification WHERE user_id = 1 AND notify_id > 123 AND (priority = 1 OR (priority = 0 AND notify_id > 345)) ORDER BY notify_id ASC LIMIT 20

语句1：

select notify_id, notify from t_user_notification where user_id = 1 and priority = 1 and notify_id > 1 order by notify_id asc limit 20\G

语句2：
不懂怎么优化，但应该尽量避免用OR。

比较奇怪，为什么不用自增主键？
然后看样子应该用了分区吧，按user_id分吗？

这个索引：

KEY `idx_user_notification__priority_user_id` (`user_id`,`priority`)

改成这样

KEY `idx_user_notification__priority_user_id` (`user_id`,`priority`，`notify_id`)

select t1.notify_id, t1.notify from t_user_notification t1, (select notify_id from t_user_notification where user_id = 1 and notify_id > 1 and priority = 1 order by notify_id asc limit 20) t2 where t1.notify_id = t2.notify_id;

语句2改成这样试试

SELECT notify_id, notify, priority FROM t_user_notification JOIN (SELECT notify_id FROM t_user_notification WHERE user_id = 1 AND notify_id > 123 AND (priority = 1 OR (priority = 0 AND notify_id > 345)) ORDER BY notify_id ASC LIMIT 20) as tmp using(notify_id)

强制使用索引吧，你这里涉及到索引合并 select * from xxx FORCE INDEX(primary_key)