title: Optimizing SQL statement for a large table
body: <p>I have a database with the following tables: </p>
  
  <pre><code>Courses(course varchar(10));
  Prerequisite(course varchar(10), prereq varchar(10));
  StudentRecord(student varchar(10), course varchar(10), PRIMARY KEY (student, course));
  </code></pre>
  
  <p>Courses holds all the courses in the database. Prerequisite holds all the prerequisites for a given course. And StudentRecord holds all the students who have completed a given course. </p>
  
  <p>I came up with the following query to find courses that a student can take based on the prerequisites he/she has already completed: </p>
  
  <pre><code>SELECT DISTINCT s.student, c.course from StudentRecord s, Courses c 
  WHERE NOT EXISTS(SELECT * FROM Prerequisite p where p.course = c.course AND
                   p.prereq NOT IN(SELECT course from StudentRecord 
                   WHERE student = s.student)) 
                   AND NOT EXISTS(SELECT * FROM StudentRecord s2 WHERE 
                   s2.student = s.student AND s2.course = c.course);
  </code></pre>
  
  <p>This query does what it's supposed to and returns a list of courses the student can take based on the prerequisites completed. However, when "StudentRecord" is a large table with over 500+ entries, my query chokes and takes forever to run. Is there an alternative query that runs faster? Can I optimize my current query to run faster? Any help is appreciated. </p>