title: Select random sampling from sqlserver quickly
body: <p>I have a huge table of > 10 million rows. I need to efficiently grab a random sampling of 5000 from it. I have some constriants that reduces the total rows I am looking for to like 9 millon. </p>
  
  <p>I tried using order by NEWID(), but that query will take too long as it has to do a table scan of all rows. </p>
  
  <p>Is there a faster way to do this? </p>