Your reformulated query must do 3 full scans of the table. The original was making at least 7, perhaps many more. I suggested "A0005=A AND A03413 IN (B,C,D)" because it would be only 2 scans -- better, but still not scalable. (And probably harder for you to construct the query.) Those stats do not include the number of sorts, tmp tables, etc needed behind the scenes.
When you look up something in a dictionary or directory, do you walk through it page by page? No. There are techniques for zipping directly to what you want (using the alphabetical nature of the data, binary search, index, table of contents). Getting database table lookups to use such techniques is the performance winner.
Do you at least have
If MyISAM, a compound index: INDEX(atrID, valID)
If InnoDB, PRIMARY KEY(atrID)
?
I just unleashed my rants against key-value schema on another poster:
http://forums.mysql.com/read.php?10,368426,368568#msg-368568
Once the data is too big to fit in RAM (hence my question about %buffer%), the disk hits (there will be lots) will slow down the queries 10-fold.
If you ever get into ranges -- Double-Ouch! "WHERE GHz BETWEEN 1.0 AND 1.5" becomes a very ugly and slooooow "WHERE (GHz = 1.0 OR GHz = 1.15 OR ... )". This warning applies to any attribute that is 'range searched' (dates, sizes, speeds, price, quantity, weight, model year, etc). If you were looking up every 'Dingel' in a directory, you would stop after a brief scan, right? The big OR can't be that smart.
Even the simple fix of having an indexed 'Product' column with rows saying "12345" ('Product' is atrID and "12345" is 'A00056'??) could change that 1 second to 0.2 second (with suitable changes to the SELECT). And, if you always search by Product, then all such SELECTs will be faster.