Well, if u have 10M rows, and all your queries use the same column in the query and the data can split pretty even between the partitions, any specific reason not to use is ? An index will help u reach a complexity of (logn) while partition + index can be in complexity of (logm) when m = rows in partition , n=total rows