Build application search features modeled on Web searches

Most applications include some form of search functionality, and often, application navigation begins with the execution of a search query. Users then navigate around the application after establishing a context by selecting a particular item from the search results. An application’s usability vastly improves if searching is enabled from different navigational depths.

To make the searching feature ubiquitous in an application, the user interface components must be kept simple and lightweight, thereby making the search dialog easily portable across the application. Many applications provide query options based on specific attributes or a combination thereof. But in this scenario, users are constrained in their queries by the limited set of attributes presented to them on the search page. Plus, the addition of new attributes to a page makes searching less intuitive and, in some cases, clutters the search page. An example of a simple but extremely effective search UI can be found in Web searching. Extending such a concept to application searches is only logical and practical, and is the topic of this article’s discussion.

This article presents a framework that can be used to develop search features modeled on Web searches. The framework simplifies the client code and is easily extensible in that implementations can extend the framework to provide various application-specific search features. A single application can contain several different implementations of this framework, each corresponding to a search by different business objects.

Goals behind the design

The framework enables the building of search functionality that accepts an arbitrary query string. The string could contain words and/or phrases corresponding to attributes of a business object. The client interface to a search implementation in its simplest form takes in a query string and returns a java.util.Collection of some arbitrary key objects as in the following method signature:

 public Collection getKeys(String searchStr); 

The key objects in the result set uniquely identify the business objects returned from the search execution and can then be used to retrieve other details of the business objects.

Search functionality in most applications allows only searching a business object by a few attributes. In database applications, this means only a few columns of a given table are used in query predicates, and often, for performance reasons, the table is indexed on these columns. The mechanism used to execute the search could vary from having separate queries for each attribute to building a complex query at runtime that includes all the predicates. Regardless of the querying functionality’s mechanics, the fact remains that an attribute and a search string are matched at design time by mapping user interface fields to attributes.

In the proposed scheme, however, by providing a single string interface, the association between the search string and the search object’s attribute has been eliminated. This begs the question: What attribute do I search against? One possible solution for overcoming this lost association is for the search string to query all the attributes with the expectation that one or more queries would return a result set. This would entail executing all the queries all the time.

It is important to note that with this solution, all the attributes are being queried against the same string, more specifically, the entire search string. We will see later how we can be more specific and allow for searching multiple attributes with sets of words/phrases extracted from the search string. Nevertheless, executing these queries sequentially would prove impractical as the response time would be determined by the total of all the individual query execution times. To circumvent this problem, the queries must be executed in multiple threads and the final result set formulated when all query threads return. This way, the response time is determined by the slowest query execution. Since we assume the attributes being searched are indexed, even the slowest query’s performance must be within an application’s acceptable responsiveness. Thus, one of the major design goals of this framework is to contain a multithreaded query execution component without burdening the implementer with writing multithreaded code.

To allow for multithreaded query execution, the framework is designed around the notion of “search methods.” Each search method corresponds to a query execution and returns a collection of key objects. The search methods run on separate threads and, generally speaking, each method functionally maps to a single attribute search of the business object in question. For example, if the business object being queried is a Customer, then the implementation class would contain methods for searching by name, address, phone, etc.

As result sets are returned by these concurrently executing search threads, the final result set must be formulated after applying some kind of ranking methodology. The ranking methodology must sort, rank, and eliminate duplicate key objects from all the result sets. Higher ranked keys signify the most appropriate search results, while lower ranked keys are least significant, and, obviously, the final result set is ordered from highest ranking to lowest ranking. Therefore, providing the ability to define and implement a ranking method is another design goal.

As mentioned earlier, since the association between a search string and an attribute is lost with this simplified interface, a brute force solution to this problem would query the entire search string against all the attributes all the time. For many searches, this would prove superfluous and inefficient as the search string’s context can be attributed to just a few attributes. If you could determine the possible contexts to which the search string can be applied, then any given search would be limited to querying on a subset of attributes. In other words, instead of executing all the search methods, only a few search methods would execute with the specific words/phrases extracted from the search string as their input. These words/phrases would have to result from some sort of contextual analysis of the search string. This approach’s benefit is improved performance and a low thread count. Hence, contextual analysis of the search string is yet another design goal.

The pieces of the puzzle

Based on the identified design goals, the framework contains the following characteristics.

• Multithreaded query execution
• Contextual analysis of search string
• Search result ranking methodology

The figure below shows a class diagram of the framework. For brevity, the diagram does not show all the methods and attributes.

We will use the class diagram in conjunction with code listings to examine the framework components. (Note: You can download this article’s complete source code from Resources.) The first class to examine is SearchContext. It is a container class for the search string and could optionally contain additional application-specific contextual information in a java.util.HashMap. The client first needs to instantiate a SearchContext object prior to performing a search. The Searchable interface contains a single method that returns a java.util.Collection of key objects taking in a SearchContext object.

Searching functionality is exposed to the framework’s clients through the Searchable interface, shown in Listing 1:

Listing 1. The Searchable interface

 public interface Searchable {
  public Collection getKeys(SearchContext cntx);
}

As you can see, the Searchable interface defines a single method that accepts an instance of a SearchContext class and returns a java.util.Collection of key objects. Clients use this method to perform searches on specific business objects—for example a Customer object—that implement the Searchable interface indirectly through the AbstractSearch class. AbstractSearch, an abstract class, is one of the framework’s extension points. We will get to this class later, as it glues together all the pieces of the framework.

Now let’s examine the SearchMethod class, which defines a search method and is used by the business object’s implementation class to define its search methods. This class is used by the framework to determine a search method’s qualifying substrings extracted from a search string and the handling of its result set. Listing 2 shows this class’s code:

Listing 2. The SearchMethod class

 public class SearchMethod {
  private String methodName = null;
  private SearchQualifier qualifier = null; //Reference to contextual analyzer
  private SearchResult result = null; //Reference to result handler
  
  public SearchMethod(String name, SearchQualifier qualifier, SearchResult result) {
    this.methodName = name;
    this.result = result;
    this.qualifier = qualifier;
  }
  
  public SearchMethod(String name, SearchQualifier qualifier) {
   //Use DefaultSearchResult when as default result handler
   this(name, qualifier, new DefaultSearchResult(1.0));
  }
  public SearchMethod(String name) {
   //Use PatternQualifier as default contextual analyzer and DefaultSearchResult
   //as default result handler
   this(name, new PatternQualifier(), new DefaultSearchResult(1.0));
  }
  public String getMethodName() {return methodName;}
  
  public SearchResult getSearchResult() { return result; }
 
  public String[] qualifyingSearches(SearchContext searchCntx) {
   //Run the analyzer and return array of qualifying strings
   return qualifier.qualifyingSearches(searchCntx);
  }  
}

This class contains two important objects, an object that implements the SearchQualifier interface and an object that implements the SearchResult interface. The SearchQualifier interface is an extension point that enables methods to define qualifying string patterns. Implementations of this interface carry out the contextual analysis of the search string. Listing 3 shows the code for the interface:

Listing 3. SearchQualifier

 public interface SearchQualifier {
  public String[] qualifyingSearches(SearchContext searchCntx);
}

The interface’s single method returns an array of qualifying substrings extracted from the search string contained within the SearchContext object. You can implement your own qualifying class by implementing this interface. For example, PatternQualifier (included in this article’s source code) is an implementation class that extracts qualifying substrings based on regular expression patterns as defined by java.util.regex.

The SearchResult interface allows for individual method executions to alert their completion and also manage their result sets. DefaultSearchResult implements this interface and demonstrates one such scheme. You could implement interesting algorithms for collecting result sets. For example, as demonstrated in Listing 4, you could include circuit breaker-like features to prevent long-running queries, which might not affect the result set’s usefulness, from degrading the performance. Notice the functionality for ignoring long-running irrelevant queries. To add this functionality, set a minimum percentage for threads to return results before deeming the search complete for the method in question:

Listing 4. The SearchResult interface and a default implementation class, DefaultSearchResult

 public interface SearchResult {
  public boolean isComplete();
  public Collection getResultSet();
  public Hashtable getStatusTable();
  public void setStatus(String key, boolean flag);
  public void add(Object obj);
}
public class DefaultSearchResult implements SearchResult {
  private Collection resultSet;  //Collection for result sets.
  private Hashtable statusTable; //Table to record completion status.
  private double threshold;  //Minimum percentage of threads to return results.
  public DefaultSearchResult(double threshold) {
    this.threshold = threshold;
    this.resultSet = new ArrayList();
    this.statusTable = new Hashtable();
  }
  public void setStatus(String key, boolean flag) {
    statusTable.put(key, new Boolean(flag));
  }
    
 /*SearchResult interface method implementation. Result is deemed complete if a minimum percentage of threads return results. The minimum *percentage is identified by threshold value.
  */
  public boolean isComplete() {
      
    if (statusTable.isEmpty()) return true; //If no thread, return as complete.
      
    Enumeration en = statusTable.keys();
    int searchThreadCount = statusTable.size(); //Total thread count.
    if (searchThreadCount==0) return true;
  
    double completedThreads = 0; //Completed threads.
    //Determine completed threads
    while(en.hasMoreElements()) {
      boolean completeFlag = 
           ((Boolean) statusTable.get((String) en.nextElement())).booleanValue();
      if (completeFlag) completedThreads++;
    }
    double threadsWithResults=0; //Threads with results.
    for(int i = 0; i < resultSet.size(); i++) {
      if (!resultSet.isEmpty()) threadsWithResults++;
    }
    
    //If minimum satisfied, mark as completed.
    if ((threadsWithResults/searchThreadCount) >= threshold) return true;
      
    //If all threads complete with or without results, mark as completed.
    if (completedThreads == searchThreadCount)  return true;
    else return false;
  }
  public Collection getResultSet() { return resultSet; }
  //Add individual result set from each thread to collection.
  public void add(Object obj) { resultSet.add(obj); }
  public Hashtable getStatusTable() { return statusTable; }
}

The framework’s ranking component is defined through the RankingMethod interface. As shown in Listing 5, this interface contains a single method to rank result sets. Implementation classes can provide the algorithms to rank and order result sets. The DefaultRankingMethod class, not shown in the listing, implements a possible algorithm for ranking.

Listing 5. The RankingMethod interface

 public interface RankingMethod {
  public Collection rank(Collection resultSet);
}

The framework’s multithreading functionality is implemented in the SearchThreadManager and SearchThread classes. Listing 6 contains code for both these classes:

Listing 6. Thread plumbing in SearchThreadManager and SearchThread

 public class SearchThreadManager implements Runnable {
  
  private SearchMethod sm = null;  
  private AbstractSearch searchObj = null; //Reference to implementation object
  private SearchContext cntx = null;
  private SearchResult result = null;
  private boolean isActive = true; //Flag to identify if thread manager is active
  public SearchThreadManager(AbstractSearch searchObj, SearchMethod sm, SearchContext cntx) {
    this.sm = sm;
    this.searchObj = searchObj;
    this.cntx = cntx;
    this.sm.qualifyingSearches(cntx);
    this.result = sm.getSearchResult();
    //Initialize the result's status table using the qualifying strings as the key
    for(int i = 0; i < sm.qualifyingSearches(cntx).length; i++)
      this.result.setStatus(sm.qualifyingSearches(cntx)[i],false);
  }
  //Method to allow threads to add result sets as they complete 
  public synchronized void addResultSet(Collection coll) { 
    result.getResultSet().add(coll);
  }
  public Collection getResultSet() {return result.getResultSet();}
  
  //Method to allow threads to mark their completion
  public synchronized void setThreadStatus(String str,boolean flag) {
    result.getStatusTable().put(str,new Boolean(flag));
  }
  
  public boolean isActive() {return isActive;}
  
  //Run method from the Runnable interface
  public void run() {
    //Spawn threads, one for each qualifying string
    for(int i = 0; i < sm.qualifyingSearches(cntx).length; i++) {
      SearchContext context = new SearchContext(cntx.getContext(), sm.qualifyingSearches(cntx)[i]);
      Thread t = new Thread(new SearchThread(this, searchObj, sm.getMethodName(), context));
      t.start();
    }
    while(!isComplete()); //Poll till complete
    setActive(false); //Inactive to ensure ignored threads complete gracefully
    searchObj.addResultSet(result.getResultSet()); //Escalate result set
    searchObj.setMethodStatus(sm.getMethodName(),true); //Mark method as complete
  }
  //Method for AbstractSearch object to determine if thread manager is complete
  public synchronized boolean isComplete() { return result.isComplete(); }
  private synchronized void setActive(boolean flag) {isActive = flag;}
}
//SearchThread class to invoke a single method with a string
public class SearchThread implements Runnable {
  AbstractSearch searchObj=null; //Reference to implementation object
  SearchContext context=null;
  String methodName=null; //Method name
  SearchThreadManager manager = null; //Reference to manager
  public SearchThread(SearchThreadManager manager, AbstractSearch searchObj, String methodName, SearchContext context) {
    this.manager = manager;
    this.searchObj = searchObj;
    this.context = context;
    this.methodName = methodName;
  }
    
   //Run method from the Runnable interface
  public void run() {
    /*Invoke the implementation method using reference to implementation object*/
    Collection coll = searchObj.search(methodName,context);
    if ((manager.isActive()) && (coll != null)){ 
      //If manager still active and have result
      manager.addResultSet(coll);
      manager.setThreadStatus(context.getSearchStr(),true);
    }
  }
}

Upon parsing the search string and assigning contexts to words/phrases, you will have a set of methods that must be executed and a set of one or more strings for each of these methods. In other words, the outcome of parsing the search string determines two pieces of information:

• A set of search methods that must be executed
• A set of strings for each method to execute those methods’ searches

Each method/string combination is spawned in a separate thread, with the SearchThreadManager controller class managing the threads for a single method. Several instances of this class could exist, depending on the number of qualified methods. This class controls the lifecycle of the individual threads and consolidates the result sets returned by them, thereby presenting a single result set for each method.

As can be seen from Listing 6, SearchThreadManager implements the java.lang.Runnable interface and is itself spawned as a thread. The actual method execution occurs in the SearchThread class. The implementation object’s reference is passed to this class’s constructor, and it invokes the implementation’s search method using the registration process described above. AbstractSearch hides these details from the implementation by using the Java Reflection API; hence, the search execution’s mechanics are transparent to the developer extending this framework.

Putting the pieces together

The AbstractSearch class in Listing 7 glues together all the pieces and is the main extension point for implementing a search feature. As mentioned earlier, it implements the Searchable interface and, in addition, hides the threading and method invocation aspects from the implementer. Business objects extend this class and implement search methods. Notice the registration method that allows implementations to register their search methods:

Listing 7. AbstractSearch, the gluing class

 public abstract class AbstractSearch implements Searchable {
  private Hashtable methods=new Hashtable(); //Method table.
  private SearchResult resultSet 
            = new DefaultSearchResult(1.0); //Result set.
  protected RankingMethod ranking 
            = new DefaultRanking(); //Ranking method.
      
  //Implementation method of Searchable interface.
  public Collection getKeys(SearchContext cntx) {
    Enumeration en = methods.keys(); //Get methods to invoke.
    while(en.hasMoreElements()) {
      SearchMethod sm = (SearchMethod) en.nextElement();
      //Spawn thread managers only for methods having qualifying strings.
      if (sm.qualifyingSearches(cntx).length > 0) {
           resultSet.setStatus(sm.getMethodName(),false);
        SearchThreadManager manager = new SearchThreadManager(this, sm, cntx);
      Thread stm = new Thread(manager);
      stm.start();
      }
    }
    while(!isComplete()); //Poll until thread managers complete.
   
    //Rank and return result set.
    return ranking.rank(resultSet.getResultSet());
  }
  /*Callback function to allow threads to invoke search methods. This   
   *function uses Reflection API to call the registered method.
   */
  public Collection search(String methodName, SearchContext cntx) {
    try {
      return (Collection) getMethod(methodName).invoke(this,new Object[] {cntx});
    } catch(IllegalAccessException e) {}
      catch(InvocationTargetException e) {}
    return null;
  }
  //Registration method for implementation to register search methods.
  protected void registerMethod(SearchMethod method) {
    try {
      methods.put(method,
      this.getClass().getMethod(method.getMethodName(),new Class[] {Class.forName("SearchContext")}));
    } catch(NoSuchMethodException e) {}
      catch(ClassNotFoundException e) {}
  }
  
  public synchronized void setMethodStatus(String methodName, boolean flag) {
    resultSet.setStatus(methodName,flag);
  }
  public synchronized void addResultSet(Collection coll) {
    Iterator it = coll.iterator();
    while(it.hasNext()) resultSet.add(it.next());
  }
  private Method getMethod(String methodName) {
    Enumeration en = methods.keys();
    while(en.hasMoreElements()) {
      SearchMethod sm = (SearchMethod) en.nextElement();
      if(sm.getMethodName().equals(methodName)) return (Method) methods.get(sm);
    }
     return null;
  }
  private SearchMethod getSearchMethod(String methodName) {
    Enumeration en = methods.keys();
    while(en.hasMoreElements()) {
      SearchMethod sm = (SearchMethod) en.nextElement();
      if(sm.getMethodName().equals(methodName)) return sm;
    }
       return null;
  }
  private synchronized boolean isComplete() {
      return resultSet.isComplete();
  }
  
  protected void setRankingMethod(RankingMethod ranking) {
    this.ranking = ranking; 
  } 
  
  protected void setSearchResult(SearchResult resultSet) {
    this.resultSet = resultSet; 
  }
}

AbstractSearch is an abstract class and must be extended with a concrete implementation that provides the actual queries. Since this class implements the Searchable interface, it provides an implementation to the getKeys(...) method. Classes that extend AbstractSearch can register their search methods using registerMethod(...). The registration process allows the implementation class to describe its individual methods and register them so that a candidate list of methods can be prepared for search execution. As mentioned earlier, the method invocation plumbing is performed here using the Reflection API. Executing a search entails the following:

• Get a list of registered methods
• Spawn SearchThreadManager threads only for the qualifying methods
• Poll until all the ThreadManagers alert completion
• Rank and order result set

The getKeys(...) method accomplishes all the above tasks. In the case of database applications, the registered search methods contain the Java Database Connectivity (JDBC) code to query the database. A datastructure like java.util.TreeSet should be used for storing the key objects as it bodes well for the type of access required during the ranking process.

An implementation example is shown in Listing 8 with Customer being used as a business object. Notice that the constructor calls the registerMethod(...) to register its search methods. Also note that three search methods are registered, and that the body of the getByCustomerName() provides an example of how to retrieve customer IDs by name. The body of the search methods is missing from the listing, but, in practice, JDBC code to retrieve customer IDs would be placed there. Also, note that the getByState() method uses a StateQualifier (not listed in the article) as a qualifier. You could perform lookups in this qualifier class against a list of state/province codes.

Listing 8. An example of a class implementing a customer search feature

 public class CustomerSearch extends AbstractSearch {
    
  public CustomerSearch() {
    /*Constructor registers individual search methods. Notice the use of    
     *pattern qualifiers with java.util.regex regular expressions. You 
     *can define your own qualifier for extracting state codes. Code not 
     *shown for StateQualifier.
     */
    registerMethod(new SearchMethod("getByName",
       new PatternQualifier(new String[] {"^[^0-9][p{Alpha}s]*"},true)));
    registerMethod(new SearchMethod("getByPhone",
       new PatternQualifier(new String[] {"([0-9]{3})[s-.]?[0-9]{3}[s-.]?[0-9]{4}","+?[0-9]{10,}"})));
    registerMethod(new SearchMethod("getByState",new StateQualifier());
  }
  
  public Collection getByCustomerName(SearchContext cntx){
    TreeSet set = new TreeSet();
    String clntId = (String)cntx.getContext().get("CLIENT_ID");
    String searchStr = cntx.getSearchStr() + "%";
    String query = "SELECT customer_id FROM customers " +
                      " WHERE customer_client_id = ? " +
                      " AND customer_name like ?";
    try{
      Connection conn = getConnection();
      PreparedStatement ps = conn.prepareStatement(query);
      ps.setInt(1,(new Integer(clntId)).intValue());      
      ps.setString(2,searchStr);
      ResultSet rs = ps.executeQuery();
      while (rs.next()){
        set.add(new Integer(rs.getInt(1)));
      }
      conn.close();
    } catch(SQLException e){e.printStackTrace();}
    return set;
  }
  public Collection getByPhone(SearchContext cntx){
    TreeSet set = new TreeSet();
    //TODO: Add JDBC code for extracting Customers by Phone.
    ....
    ....
    return set;
   }
  
  public Collection getByState(SearchContext cntx){
    TreeSet set = new TreeSet();
    //TODO: Add JDBC code for extracting Customers by State.
    ....
    ....
    return set;
   }
   
}

The client

Listing 9 shows the client code for the search. For brevity, I have omitted a discussion on the usage of patterns like Factory and Builder. First, an object of the search implementation class is instantiated and the getKeys(...) method is invoked with an object of type SearchContext. The SearchContext object contains the query string and any other contextual information passed in a java.util.HashMap. A java.util.Collection of key objects is returned. The application can then use this collection for further processing.

Listing 9. The client code

 public class Test {
  public static void main(String[] args) {
  try {
    Searchable search = new CustomerSearch(); //Doing customer search
    HashMap hm = new HashMap();  //Optional Context info
    hm.put("CLIENTID","ACME INC");  //Adding Client context
    //Instantiate Search Context with search string and client context
    context = new SearchContext(hm,"John Doe CA (412) 555-1212");
    Collection coll = search.getKeys(context);  //Execute search
    Iterator it = coll.iterator();
    while(it.hasNext()){
      System.out.println(it.next());
    }
  } catch(Exception e) {e.printStackTrace();}
}

Deployment tips for database applications

JDBC connection creation is expensive for database applications in terms of performance. With this scheme, the individual methods create separate connections because the methods run in parallel threads. Threads could share a single connection by serializing access to it, but that defeats the purpose of parallelizing query execution. A better solution would use connection pooling, and the individual search methods would grab and release connections from and to the pool. Also, the framework needs J2SE 1.4.x or higher as it uses the java.util.regex package. Finally, it is important that the database queries be optimized

Conclusion

Developing search functionality in applications modeled on commonly used Web searches provides users with a familiar way of searching. It renders a simple user interface and can be easily included in different parts of an application. Applications can benefit from the consistency of such a user interface. Being very intuitive, such an interface allows users to enter as much detail as is available to them to perform searches. When provided details that are not specific, the application offers a larger result set that includes the most desired result at the top of the list. Moreover, building on top of this framework eases the development of search features as developers can focus on providing the implementation details while the framework handles the more complex functionality of multithreading and result set handling.