title: SQL query to get random unused combination
body: <p><strong>Background:</strong></p>
  
  <p>I want to create a database that can run a tournament of 1 vs 1 matchups. It needs to keep track of who won and lost each matchup and any comments about that matchup as well as decide the next unique matchup randomly.  </p>
  
  <p><strong>Rules:</strong> </p>
  
  <p>There are x number of players. Each player will eventually play every other player once, in effect covering all possible unique combinations of players.  </p>
  
  <p><strong>Database Tables (with Sample data):</strong></p>
  
  <pre><code>DECLARE @Players TABLE (
      ID INT PRIMARY KEY IDENTITY,
      Name VARCHAR(50)
  )
  
  ID Name  
  -- ----- 
  1  Alex  
  2  Bob   
  3  Chris 
  4  Dave 
  
  DECLARE @Matches TABLE (
      ID INT PRIMARY KEY IDENTITY,
      WinnerId INT,
      LoserId INT
  )
  
  ID WinnerId LoserId 
  -- -------- ------- 
  1  1        2       
  2  4        2       
  3  3        1    
  
  DECLARE @Comments TABLE (
      ID INT PRIMARY KEY IDENTITY,
      MatchId INT,
      Comment VARCHAR(MAX)
  )
  
  ID MatchId Comment                        
  -- ------- ------------------------------ 
  1  2       That was a close one.          
  2  3       I did not expect that outcome. 
  </code></pre>
  
  <p><strong>Problem:</strong></p>
  
  <ul>
  <li>How can I efficiently query to get a single random match up that has not yet occurred? </li>
  </ul>
  
  <p>The major problem is that the number of player can and will grow over time. Right now in my example data I only have 4 players which leaves 6 possible matches. </p>
  
  <pre><code>Alex,Bob
  Alex,Chris
  Alex,Dave
  Bob,Chris
  Bob,Dave
  Chris,Dave
  </code></pre>
  
  <p>That would be small enough to simply keep grabbing 2 random numbers that correspond to the Player's id and then check the matchups table if that matchup has already occurred. If it has: get 2 more and repeat the process. If it hasn't then use it as the next matchup. However if I have 10,000 players that would be 49995000 possible matchups and it would simply become too slow.</p>
  
  <p>Can anyone point me in the right direction for a more efficient query? I am open to changes in the database design if that would help make things more efficient as well.</p>