For testing the correctness of SQL queries, a standard practice is to execute the query in question on some test database instance and compare its result with that of the correct query. Given two queries Q_1 and Q_2, we say that a database instance D is a counterexample (for Q_1 and Q_2) if Q_1(D) differs from Q_2(D); such a counterexample can serve as an explanation of why Q_1 and Q_2 are not equivalent. While the test database instance may serve as a counterexample, it may be too large or complex to understand where the inequivalence arises. Therefore, in this paper, given a known counterexample D for Q_1 and Q_2, we aim to find the smallest counterexample D' subseteq D where Q_1(D') neq Q_2(D'). The problem in general is NP-hard. Drawing techniques from provenance and constraint solving, we develop a suite of algorithms for finding small counterexamples for different classes of queries, including those involving negation and aggregation. We evaluate the effectiveness and scalability of our algorithms on student queries from an undergraduate database course, and on queries from the TPC-H benchmark. We also report a user study from the course where we deployed our tool to help students with an assignment on relational algebra.