Why a larger table is faster than new smaller one?

We have a large table in SQL Server with almost 40.000.000 records. it took considerable time to running queries on it. so we decided to leave all old and out of date records there and move usable records in a new table an use the new one. while it supposed to be faster than old table which have almost double count of records, the problematic result was somthing else. although runnig a query on old table takes nigh 45 seconds,on开发者_JAVA技巧 the new table with same structure (keys and indexes) and half count of records, it takes over 30 minuts to running same query. where we have mistake or missed some important issues?

Did you remember to migrate the indexes from the larger table and re-generate statistics on the new table?

If not, start there. That is usually the issue in these cases (especially with large tables).