It's a 2-fold situation you're describing: one is related to procedure cache, and the other is the data cache. Execution of a procedure for the first time generates an execution plan for that procedure and stores it in procedure cache. If parameters supplied for the consecutive executions are different, then a new copy of the execution plan gets created and stored in cache. Once the amount of cache has reached the limit, the FIFO rule applies and the oldest plan gets paged out. Cache misses that you're describing are related to the data cache. It means that the optimizer does not find the data in cache, thus forces a physical read directly from the disk. In high volume OLTP systems it is not unusual, so there is nothing to worry about.