FYI; we replied to a critical ticket that duplicated this, but in case anyone is reading this... We have a SQL patch available, but aren't totally sure if it will help. We can send it. We are really struggling to reproduce this in any consistent matter; we believe the issue might be related to sql server's plan caching. we're seeing inappropriate execution plans being used , and then suddenly changing, for the same input. The patch simplifies the queries we're using, so hopefully it will result in a more consistent query plan. Our next idea , is to try forcing some join hints. We're also asking for a backup of the database? That will help us analyze your data. We're thinking maybe you have some unique distributions (like tons of versions for one package, just a few for another).