This implies that paging is not slowing us down, it is time spend comparing values that we already have - this function isn't blocked by anything, and the compare is fixed width, we are just calling it a lot. I had this problem previously (which I found the good old fashioned way - no profiler) and it was caused by me failing to specify the bucket count for tables - defaulting to 100. So basically linear search on the store size.