Here are some guiding questions: 1) Do you actively need all 100M records, or is there a period after which you can archive them? 2) Have you partitioned data

Here are some guiding questions: 1) Do you actively need all 100M records, or is there a period after which you can archive them? 2) Have you partitioned data across multiple servers, or just multiple tables on one server? 3) What are the nature of your expensive queries? Are you generating reports? User dashboards? I think a general idea of what your application is doing would help us provide some guidance.