I worked with a design for several years that allowed for versioned data and queries that ran extremely fast. You just have to make sure that you index the tables appropriately and write the queries in an optimal fashion. I've got two articles on Simple-Talk about these mechanisms. The first talks about the index structure[/url]. The second talks about the various methods of querying the versioned data[/url].

Short answer, instead of a main table and a history table, just have one table that stores everything. The methods outlined above have been in production, successfully, for years.