"Normal" time for query execution
It would be helpful to have SHOW CREATE TABLE, but I will make some guesses...

You have INDEX(QualityLevel), and that index is smaller than the buffer_pool?
You have been doing a bunch of queries; these were not the first?  (Hence some things are cached.)
You did not use SQL_NO_CACHE to avoid the Query cache?  

How much RAM do you have?  innodb_buffer_pool_size=4GB is rather small unless you have only 6GB.

The COUNT(DISTINCT ..) seems too fast -- probably caching helped.

When doing timing tests:

SELECT SQL_NO_CACHE ...   -- to avoid the Query cache.


and run the query twice -- to compensate for I/O caching.

Responding to comments

You should switch to InnoDB.  Then, with 250GB of RAM, set innodb_buffer_pool_size = 200G.  This will help InnoDB performance.  (Note: MyISAM does not use that at all; instead, it uses key_buffer_size, which should be set to about 50G for a MyISAM-only setup.)

In general, adding a useful index is worth doing -- in spite of the negative cost considerations (disk space an insert cost).

When building a composite (multi-column) index, the cardinality of the individual columns is irrelevant.  The index becomes a unit, the components of which are not noticed.

For this query:

select count(recordID) from patient_records
      where QualityLevel&gt;10.14 and snpID='.';


the following is optimal in this order:

INDEX(snpID, ,      -- because of `=`
      QualityLevel, -- a range, so comes after `=`
      recordID)     -- tacked on to make it "covering"


A note about COUNT(recordID) -- that checks which rows have a non-NULL value for recordID.  This test is unnecessary since it is declared NOT NULL.  I suggest getting in the habit of simply saying COUNT(*).

With COUNT(*), INDEX(snpID, QualityLevel) would be as good.

To design the optimal indexes, you need to know the SELECTs, DELETEs, and UPDATEs.  You cannot pre-guess.  See my Cookbook .

Another note:  The order of WHERE clauses does not matter; the Optimizer tries all reorderings of the AND clauses.  It will try all reorderings of multiple tables JOINed together.  (LEFT may or may not limit what the Optimizer will try.)

need to build a web interface for these queries

It is passe to say "Exactly 56627747 widgets" in a web interface.  Even "About 56 million" is rarely used these days.  And that could be efficiently achieved by a nightly job that recomputes that, and other, statistics about your data.

If you do need both precision and speed, then build a Summary Table and query it.  That table could, for example, have daily counts for the number of widgets in various quality brackets.

Summary Tables are the key to billion-row datasets.