Efficiently query an embedded database in a loop w

I asked a similar question the other day but have since realized I was getting ahead of myself. I'm seeking advice on the proper way to handle the following scenario. I'm trying to SELECT the correct longitude and latitude for a given address and city, in the fastest way possible.

My COORDINATES table has 25,000 rows and looks like this:

I have a Java HashMap<Integer, List<String>> which contains an Integer as the key, and an ArrayList containing 2 entries, an address and city. The HashMap has a size of 500.

There are 4 different types of SELECT statements I need to use, since each one is a little more lenient than the previous, like so:

SELECT LATITUDE, LONGITUDE FROM coordinates WHERE(address::text = ? AND community::text = ?) 
UNION ALL
SELECT LATITUDE, LONGITUDE FROM coordinates WHERE (address::text = ? AND community::text LIKE ?)
UNION ALL
SELECT LATITUDE, LONGITUDE FROM coordinates WHERE (address::text LIKE ? AND community::text = ?)
UNION ALL
SELECT LATITUDE, LONGITUDE FROM coordinates WHERE (address::text LIKE ? AND community::text LIKE ?)

Notice the use of LIKE and =. Also notice I'm using UNION ALL which aggregates all the results, whereas I'm actually only interested in the single, best matching result as to avoid continuing to query if a match is found. Perhaps a LIMIT could be helpful.

If I merely loop through my HashMap and hit the database 500+ times (with a 4-part query)... that seems painfully inefficent since I'm not leveraging the SQL server. It's taking over a minute right now. I'm using H2 as my embedded DB but am willing to use Derby or Hyper if needed.

What is the fastest way to loop through the HashMap and retrieve the corresponding, best matching longitude/latitude (if any) for each entry? Notice I have to match up ? in the prepared statements with the corresponding address and city for each entry. Once again, you can view my current approach here.
I'm leaning toward a stored procedure but the tutorials like this mention creating a JAR file of the stored procedure's class and then installing it to Derby. How do you deploy a standalone Java app that has an embedded DB relying on JAR stored procedure?