Join with index problem

[Seokhee Kim]

I have a big problem with MySQL join query.
It like this

create table product_extract
select a.store_id, a.month_year, a.product_id, b.CLASS_DESC, a.cost, a.cost_new
from sales_data a, Product_Alignment b
where a.product_id=b.product_id;

If I do join with indexIproduct_id), most of mysqld process status is on 'wait_on_block'.

If I don't use index, result is faster but slower than my expectation.
This problem comes with little big(?) size tables ( a:500MB--4M records, b:500K--2K records ).
I did this test on RedHat 7.2 and RedHat 9 with upgrading kernels(2.4, 2.6) and changing my.cnf. Also I tried different version of MySQL(4.0.12,4.0.14,4.1.7).
Another MS SQL guy tested that query on SQL server. that gave us 10 times faster result. Is this MySQL bugs or limit?
The query is really simple join query. Now we are on an edge to go SQL Server or MySQL.
Could anybody give me any ideas for me? I'd like to keep MySQL.
I would really appreciate.

Thanks