Тъй като в моята таблица в момента имам само около 5k реда и те бавно нарастват, реших всъщност да използвам следния прост подход (той ми дойде точно след като написах въпроса).
Да речем, че семето е Honda Accord (model_id 456), 2004 г., бензин, 2.0L, 155 к.с., седан с auto-inc ID 123.
SELECT vehicles.*,
(IF(`fuel_type`='gasoline', 3, 0) +
IF(`body_style`='sedan', 1, 0) +
IF(`year` > 2001 AND `year` < 2007, 2, 0) +
IF(`engine_size` >= 1.8 AND `engine_size` <= 2.2, 1, 0) +
IF(`engine_power`=155, 3, IF(`engine_power`>124 AND `engine_power`<186, 1, 0))) AS `rank`
FROM vehicles
WHERE vehicle_id!=123 AND model_id=456
ORDER BY `rank` DESC
LIMIT 3
Ще работи, стига да нямам твърде много редове. Ако таблицата стане 50-100k, вероятно ще трябва да премина към нещо като Lucene
?