Does it have to be a spreadsheet? You might be better off using Access. Before I retired I worked for an insurance company with 3 million policy holders. They were using Excel but, like you it took ages to do searches. I got them to switch to Access and the difference was amazing.