Most efficient way to get oldest row in MySQL by id
For the specific query that gets only one row from the table:

SELECT *
FROM message
WHERE conversation_id = @some_id
ORDER BY add_date ASC
LIMIT 1 ;


you only need a common (btree) index on (conversation_id, add_date). The query will need to do only an index seek (which will find the PK value) and then a seek on the table. The operations should be both very fast (O(logn)), so the size of the table will not matter much.

After you add the index (or any index), you don't need to do anything more. Whenever a query runs, if  the optimizer decides that the index is useful (for that query, which can be the specific query above or any other), then it will use the index.



Side notes: please add PRIMARY KEYs to the tables.