title: Selecting n random rows from a huge database with conditions
body: <p>I have a database of around 8 million plus rows from which I want to select randomly n rows. First of all I've read the popular and similar question here on <a href="https://stackoverflow.com/questions/848872/select-n-random-rows-from-sql-server-table">StackOverflow</a> and the article on <a href="http://msdn.microsoft.com/en-us/library/cc441928.aspx" rel="nofollow noreferrer">MSDN</a>, however I feel that the answers still don't suit my needs.</p>
  
  <p>The offered solutions work great if I want a certain percentage of rows randomly selected without extra conditions. But what I want to select n rows randomly (e.g. at most 5 rows), all matching a certain condition.</p>
  
  <p>My database contains words with information like their part of speech, tag, lemma and token. Now I want to perform a query to select 5 random words all similar to the word in the query (e.g. give me 5 words similar to <em>fuzzy</em>), this is determined by looking only at words with the same part of speech and a value of the levenshtein distance above a certain threshold. I have a function in sql server that can calculate the levenshtein distance.</p>
  
  <p>The problem with the aforementioned methods is that they either have to run over all the records and calculate the levenshtein distance (which takes up a lot of time!) or they only offer me to select a percentage instead of n rows.</p>
  
  <p>A query that works sufficiently well is:</p>
  
  <pre><code>SELECT DISTINCT TOP 5 lower(Words.TOKEN) as LTOKEN, Words.LEMMA, TagSet.POS_Simplified, TagSet.TAG 
  FROM Words JOIN TagSet on Words.TAG = TagSet.TAG 
  WHERE NOT Words.LEMMA = 'monarchie' AND TagSet.POS_Simplified = 'noun' 
  AND TagSet.TAG = 'NOM' AND NOT Words.TOKEN = 'monarchie'
  AND [dbo].edit_distance('monarchie', Words.Token) &gt; 0.5
  </code></pre>
  
  <p>However, with only top I get always the same results. I need my top to be random. Methods like using NEWID() will first go over the entire database and then select randomly, which is not my intended behavior as they take way too long.</p>
  
  <p>Does anyone have an idea to select n random rows fast on a huge database?</p>
  
  <hr>
  
  <p><strong>EDIT:</strong></p>
  
  <p>Someone (not on StackOverflow) may have offered me a solution with the <em>OPTION</em> clause and the <em>fast</em> keyword, which retrieves the first n number of rows it finds. </p>
  
  <p>With the OPTION(fast 5) I get the best performance so far (10 seconds on a 8 million plus row table). I also changed the Levenshtein function from an SQL implementation to a c# written library implementation which sped up the performance considerably.</p>
  
  <pre><code>Select top 5 * from (
  SELECT DISTINCT lower(Words.TOKEN) as LTOKEN, Words.LEMMA, TagSet.POS_Simplified, TagSet.TAG 
  FROM Words JOIN TagSet on Words.TAG = TagSet.TAG 
  WHERE NOT Words.LEMMA = 'monarchie' AND TagSet.POS_Simplified = 'noun' 
  AND TagSet.TAG = 'NOM' AND NOT Words.TOKEN = 'monarchie'
  AND [dbo].clrEditDistance('monarchie', Words.Token) &gt; 0.5
  ) AS T
  ORDER BY NEWID()
  OPTION(fast 5)
  </code></pre>