SELECT Count(*) AS recordCount
FROM PART AS p
INNER JOIN Interchange AS i ON p.PART_ID = Interchange.Part_ID
INNER JOIN PartToBaseVehicle S bv ON p.PART_ID = bv.PART_ID
INNER JOIN Applications AS a ON bv.PartToBaseVehicleID = a.PartToBaseVehicleID
WHERE i.InterchangeNumber Like '%aaa%'
LIKE '%aaa%'
cannot use an index because of the prefixed 'wild card'.
Have you considered FULLTEXT?
"I put indexes on all the fields" -- Do you know about 'compound indexes'?
For further discussion, please provide
* SHOW CREATE TABLE tbl\G -- engine, indexes
* SHOW TABLE STATUS LIKE 'tbl'\G -- sizes
* EXPLAIN SELECT ...\G -- clues of inefficiencies
* SHOW VARIABLES LIKE '%buffer%'; -- cache size
and surround them with [ code ] and [ / code ]