If you want to consider an alternative approach:

1. Export the gene table from MySQL to a UCSC-formatted BED file (you'll want at least four tab-delimited columns: chromosome, start, stop and gene name)
2. Export your regulatory elements to another UCSC-formatted BED file (you'll want at least three columns: chromosome, start and stop)

3. Both BED files should first be sorted, _e.g._ with BEDOPS sort-bed or alternatives:

   $ sort-bed rawRegulatoryElements.bed > regulatoryElements.bed

   $ sort-bed rawGenes.bed > genes.bed

   Sorting allows other BEDOPS tools (like the one I'm about to mention shortly) to operate and return results very quickly.

4. Run BEDOPS closest-features on the regulatory elements and gene table BED files, _e.g._:

   $ closest-features --delim '\t' --shortest regulatoryElements.bed genes.bed > answer.bed

This command reports the nearest gene upstream or downstream to each regulatory element. Results are stored in a file called answer.bed, which is also BED-formatted.

I spent a lot of time digging down that rabbit hole. If you want to follow, you can use something like this:

SELECT * from (
 (SELECT * FROM ((SELECT * FROM feature WHERE start<= ? ORDER BY start DESC  LIMIT 1) UNION (SELECT * FROM feature where start>= ?
ORDER BY start LIMIT 1)) as u)
 UNION
 (SELECT * FROM ((SELECT * FROM feature where stop<= ? ORDER BY stop   DESC  LIMIT 1) UNION (SELECT * FROM feature where stop>= ?
ORDER BY stop LIMIT 1)) as v)
) as w
ORDER BY ABS((start + stop)/2 - ?) LIMIT 1

To get the nearest neighbor using indexes (if your table has btree indexes on start and end). But, unless you have only a few intervals, it's simpler and faster to read the database features into some kind of an interval tree and query from there.

You would need to "nail down" in the SQL query the coordinate and say that you want to get all the entities with a position above or below the specified one, then you need to LIMIT the set which SQL returns to 1 entity, something like:

select * from `gene` where `start` >10000 order by `start` limit 1;

If you need to see which gene is closer, upstream or downstream, - do it in Perl. Don't worry about performance in Perl, MySQL is pretty smart to figure out that stuff for you. But, I would recommend to index your table by the gene start/end positions.

p.s editing - forgot to put order by....

If you want to use mysql, consider using either spatial indexing or hack indexes using code such as that used by UCSC and tabix. See the last section of the SAM format document for details on creating and using a simple indexing scheme. In UCSC tables, you will often see a column with the name "bin"; this is another implementation of the same scheme.

Take a look at the ChiPpeakAnno Bioconductor package here: http://www.bioconductor.org/packages/release/bioc/html/ChIPpeakAnno.html. The second use case in the vignette is on finding the nearest gene to a feature.

Since Sean is breaking out the R package :). There's also a python package that can do this: https://pypi.python.org/pypi/cruzdb

Syntax would be something like:

hg19 = Genome('hg19')
for chrom, start, end in list_of_intervals:
    print hg19.knearest('refGene', chrom, start, end, k=2)

or if you want upstream only, replace "knearest" with "upstream".