what do I use to perform SQL-like lookups on a java table?

Question

I have a 2D array

public static class Status{
public static String[][] Data= {
{ "FriendlyName","Value","Units","Serial","Min","Max","Mode","TestID","notes" },
{ "PIDs supported [01 – 20]:",null,"Binary","0",null,null,"1","0",null },
{ "Online Monitors since DTCs cleared:",null,"Binary","1",null,null,"1","1",null },
{ "Freeze DTC:",null,"NONE IN MODE 1","2",null,null,"1","2",null },

I want to

SELECT "FriendlyName","Value" FROM Data WHERE "Mode" = "1" and "TestID" = "2"

How do I do it? The fastest execution time is important because there could be hundreds of these per minute.

Answer 1

Think about how general it needs to be. The solution for something truly as general as SQL probably doesn't look much like the solution for a few very specific queries.

As you present it, I'd be inclined to avoid the 2D array of strings and instead create a collection - probably an ArrayList, but if you're doing frequent insertions & deletions maybe a LinkedList would be more appropriate - of some struct-like class. So

 List<MyThing> list = new ArrayList<MyThing>();

and index the fields on which you want to search using a HashMap:

 Map<Integer, MyThing> modeIndex = new HashMap<Integer, MyThing>()
 for (MyThing thing : list)
     modeIndex.put(thing.mode, thing);

Writing it down makes me realize that won't do, in and of itself, because multiple things could have the same mode. So probably a multimap instead - or roll your own by making the value type of the map not MyThing, but rather List. Google Collections has a fine multimap implementation.

Answer 2

This doesn't exactly answer your question, but it is possible to run some Java RDBMs with their tables entirely in your JVM's memory. For example, HSQLDB. This will give you the full power of SQL selects without the overheads of disc access. The only catch is that you won't be able to query a raw Java data structure like you are asking. You'll first have to insert the data into the DB's in-memory tables.

(I've not tried this ... perhaps someone could comment if this approach is really viable.)

Answer 3

As to your actual question, in C# they used to use LINQ (Language Integrated Query) for this, which takes benefit of the language's support for closures. Right now with Java 6 as the latest official release, Java doesn't support closures, but it's going to come in the shortly upcoming Java 7. The Java 7 based equivalent for LINQ is likely going to be JaQue.

As to your actual problem, you're definitely using a wrong datastructure for the job. Your best bet will be to convert the String[][] into a List<Entity> and using convenient searching/filtering API's provided by Guava, as suggested by Carl Manaster. The Iterables#filter() would be a good start.

Answer 4

EDIT: I took a look at your array, and I think this is definitely a job for RDBMS. If you want in-memory datastructure like features (fast/no need for DB server), embedded in-memory databases like HSQLDB, H2 can provide those.

If you want good execution time, you MUST have a good datastructure. If you just have data stored in a 2D array unordered, you'll be mostly stuck with O(n).

What you need is indexes for example, just like other RDBMS. For example, if you use a lot of WHERE clause like this WHERE name='Brian' AND last_name='Smith' you could do something like this (kind of a pseudocode):

Set<Entry> everyEntry = //the set that contains all data
Map<String, Set<Entry>> indexedSet = newMap();
for(String name : unionSetOfNames){
    Set<Entry> subset = Iterables.collect(new HasName(name), everyEntries);
    indexedSet.put(name, subset);
}
//and later...
Set<Entry> brians = indexedSet.get("Brian");
Entry target = Iterables.find(new HasLastName("Smith"),brians);

(Please forgive me if the Guava API usage is wrong in the example code (it's pseudo-code!, but you get the idea).

In the above code, you'll be doing a lookup of O(1) once, and then another O(n) lookup, but on a much much smaller subset. So this can be more effective than doing a O(n) lookup on the entire set, etc. If you use a ordered Set, ordered by the last_name and use binary search, that lookup will become O(log n). Things like that. There are bunch of datastructures out there and this is only a very simple example.

So in conclusion, if I were you, I'll define my own classes and create a datastructure using some standard datastructures available in JDK. If that doesn't suffice, I might look at some other datastructures out there, but if it gets really complex, I think I'd just use some in-memory RDBMS like HSQLDB or H2. They are easy to embed, so there are quite close to having your own in-memory datastructure. And as more and more you do complex stuff, chances are that that option provides better performance.

Note also that I used the Google Guava library in my sample code.. They are excellent, and I highly recommend to use them because it's so much nicer. Of course don't forget to look at the java.utli.collections package, too..

Answer 5

I ended up using a lookup table. 90% of the data is referenced from near the top.

    public static int lookupReferenceInTable (String instanceMode, String instanceTID){
        int ModeMatches[]=getReferencesToMode(Integer.parseInt(instanceMode));
        int lineLookup = getReferenceFromPossibleMatches(ModeMatches, instanceTID);
        return lineLookup;
    }



        private static int getReferenceFromPossibleMatches(int[] ModeMatches, String instanceTID) {
      int counter = 0;
      int match = 0;
      instanceTID=instanceTID.trim();
      while ( counter < ModeMatches.length ){
         int x = ModeMatches[counter];
         if (Data[x][DataTestID].equals(instanceTID)){
         return ModeMatches[counter];
         }
         counter ++ ;
      }
      return match;

    }

It can be further optimized so that instead of looping through all of the arrays it will loop on column until it finds a match, then loop the next, then the next. The data is laid out in a flowing and well organized manner so a lookup based on 3 criteria should only take a number of checks equal to the rows.