I don't know the MySQL syntax super well but that query implied that it will always use the time index and then iterate in time order looking for a link to the category you want. Unless that category is an appreciable fraction of the total links I don't imagine that is a good plan.