SQL query latency inconsistencies

I've made a query with and without the ORDER BY clause, and it is actually much much faster without the ordering. I can't tell why, but my best guess is it's somehow related to the PRIMARY KEY index.

When I use ORDER BY o.id ASC / Don't order it, my query runs in around 3-4 seconds, whereas ORDER BY o.id DESC runs it in 30ms.

I've made indexes on o.attached_offline_id, o.total_payable_amount, o.updated_at and o.status, and o.id, u.id are primary keys, but they don't seem to speed up my query, any suggestions on how to better index my columns are very welcome, since I'm not very confident about writing performant SQL.

This is my basic query:

SELECT u.id as user_id, u.phone_number, o.id as order_id,
	o.total_payable_amount as amount, o.updated_at AS order_date
FROM orders o
JOIN users u ON o.user_id = u.id
WHERE o.status = 'Completed' AND o.payment_status = 'Completed' 
    AND o.total_payable_amount >= 1
    AND o.attached_offline_id IS NULL AND o.updated_at >= DATE('2023-02-01');

Thanks!

EDIT 1: Here is some additional info everyone requested:

1. Yes, there is a FK relation between orders and users on u.id = o.user_id.

2. show create table orders; and show create table users; results are a bit too big for me to write here, since the tables have a lot of fields and constraints, so I'll omit it here since I've mentioned the FK relation above and think that's what everyone was looking for.

3. My mysql version is 5.7.37

4. EXPLAIN gives me:

id|select_type|table|partitions|type  |possible_keys                                                                                                                                                                              |key              |key_len|ref               |rows  |filtered|Extra                             |
--+-----------+-----+----------+------+-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+-----------------+-------+------------------+------+--------+----------------------------------+
 1|SIMPLE     |o    |          |ref   |orders_user_id_foreign,total_payable_amount,payment_status,status,orders_updated_at_IDX,orders_attached_offline_id_IDX,orders_total_payable_amount_IDX,orders_status_IDX,orders_user_id_IDX|orders_status_IDX|2      |const,const       |831158|    8.09|Using index condition; Using where|
 1|SIMPLE     |u    |          |eq_ref|PRIMARY                                                                                                                                                                                    |PRIMARY          |4      |vidyakul.o.user_id|     1|   100.0|                                  |

You need a composite index, not lots of single-column indexes:

INDEX(status, payment_status, attached_offline_id,  -- "=" test
      updated_at)    -- "range" test last

More in my Index Cookbook

(PS: DATE('2023-02-01') can be written simply '2023-02-01'.)