Table attribute for sorting
Without seeing the table schema, I see two options:


Adjust the schema so that the Foreign Keys(FK) are not part of the Primary Key(PK); only the AUTO_INCREMENT column is the PK. The Foreign Keys can still be Unique Indexes to prevent multiple likes of a particular track by the same user. This won't work of course if the FKs are part of a partitioning scheme.
Take out the AUTO_INCREMENT column and add a TIMESTAMP(0) DEFAULT CURRENT_TIME column. The timestamp column will take up as much space as an INT AUTO_INCREMENT column. The downside to this is all rows before adding the timestamp column would not have an order.