I have a table with at least a couple million rows and a schema of all integers that looks roughly like this:

start
stop
first_user_id
second_user_id

The rows get pulled using the following queries:

SELECT * 
  FROM tbl_name 
 WHERE stop >= M 
   AND first_user_id=N  
   AND second_user_id=N 
ORDER BY start ASC

SELECT * 
  FROM tbl_name 
 WHERE stop >= M 
   AND first_user_id=N 
ORDER BY start ASC

I cannot figure out the best indexes to speed up these queries. The problem seems to be the ORDER BY because when I take that out the queries are fast.

I've tried all different types of indexes using the standard index format:

ALTER TABLE tbl_name ADD INDEX index_name (index_col_1,index_col_2,...)

And none of them seem to speed up the queries. Does anyone have any idea what index would work? Also, should I be trying a different type of index? I can't guarantee the uniqueness of each row so I've avoided UNIQUE indexes.

Any guidance/help would be appreciated. Thanks!