ToC path:

Index Searches in Java

Search interfaces locate desired objects or groups of objects by unique identifier or by index. Exact match lookups by unique identifier (including HashTable and autoid ) using the Cursor method find() are extremely efficient for locating individual objects. eXtremeDB also offers a rich set of specialized indexes that employ Cursors to navigate a group of objects as an ordered result set with tree-based (including patricia, rtree and trigram) , or an unordered sequence of objects with HashTable indexes declared as unique=false or List indexes.

Find

The Cursor method find() searches an index for an exact match. By definition, an exact match lookup on a unique index returns exactly one result or zero if no match is found. Note that an autoid is by definition unique. So an internally managed unique HashTable index is implemented for it and only the exact match find() method is appropriate for autoid object lookups.

Autoid Lookup

As explained in the Indexes and Cursors page, only "exact match" searches are possible for autoid indexes which are performed using the Cursor method find(). To demonstrate, consider the following schema:
 
    @Persistent(autoid = true)
    class Department
    {
        @Indexable(type=Database.IndexType.BTree, unique=true) // Declare unique tree index by "code" field
        String code;
        String name;
    }
     
    @Persistent()
    class Employee
    {
        @Indexable(type=Database.IndexType.BTree, unique=true) // Declare unique tree index by "name" field
        String name;
        long dept;
    }
     
Note that a one-to-many relationship between Department and Employee objects can be implemented through the reference field dept of type long in class Employee. If each Employee object stores the autoid value of the Department object to which it belongs, the owner Department object could be quickly found with code like the following:
 
    con.startTransaction(Database.TransactionType.ReadOnly);
    // 1. Find the Employee object by name
    Cursor<Employee> cursor = new Cursor<Employee>(con, Employee.class, "name");
    Employee emp;
    emp = cursor.find(search_name);
 
    // 2. Find the Department object by its autoid and display the Department name
    Cursor<Department> cursor2 = new Cursor<Department>(con, Department.class);
    Department d = cursor2.find(emp1.dept);
    System.out.println("\n\nFind " + search_name + "'s co-workers in " + d.name + " :\n");
    con.commitTransaction();
    cursor.close();
 
Note that here the Cursor cursor2 is instantiated on class Department without specifying an index, which means "use the class autoid index".

Search

A Cursor is essentially an iterator over the collection of objects in a result set. For each non-unique index declared for a class a Cursor can be instantiated. The Cursor method search() positions it based on some value(s), and the current() method provides a handle to the database object at the current position. Most index types provide an ordered result set; List-based and non-unique HashTable-based cursors allow navigation in sequential order (first to last, or last to first), though the order of the sequence is not defined; it is simply a mechanism to iterate over the unordered list of objects .

Cursor Navigation

After positioning a cursor with the search() method or one of the cursor positioning functions (moveFirst(), moveLast(), moveNext() or movePrev()), the current() method can be used to obtain a handle to the object in order to then use object interface methods.

BTree Index Search

To demonstrate a common BTree index search scenario, consider the following database class definition:
 
    @Persistent()
    class Employee
    {
        @Indexable(type=Database.IndexType.BTree, unique=true) // Declare unique tree index by "name" field
        String name;
        int dept_no;
    }
     
To lookup an Employee object by the BTree index name, we could use code like the following:
 
    Employee emp;
    String search_name = "William";
     
    con.startTransaction(Database.TransactionType.ReadOnly);
    Cursor<Employee> cursor = new Cursor<Employee>(con, Employee.class, "name");
    emp = cursor.find(search_name);
    con.commitTransaction();
    cursor.close();
     
Patricia Index Search

As explained in the Indexes and Cursors page, the Patricia index can be declared unique; in the absence of the unique keyword it defaults to allowing duplicates.

Searches on Patricia indexes are performed using the Cursor operations ExactMatch, BestMatch, PrefixMatch and NextMatch.

Please refer to the Patricia Index page for explanations and examples of how these Patricia-specific search operations work. To demonstrate use of the Patricia Java APIs, the SDK sample Indexes_Patricia is provided. Code snippets from this sample are used below to illustrate the different types of Patricia index searches.

Consider the class AreaCode with string fields like the following:
 
    @Persistent 
    class AreaCode
    {
        @Indexable(type=Database.IndexType.Patricia) // Declare patricia index by "areaCode" field
        String areaCode;
 
        @Dimension(4)
        String strAreaCode;
    }
     
Sequential search

To sequentially list the contents of the database using the Patricia index areaCode, we could use code like the following:
 
    con.startTransaction(Database.TransactionType.ReadOnly);
    Cursor<AreaCode> cursor = new Cursor<AreaCode>(con, AreaCode.class, "areaCode");
    for (AreaCode ac : cursor) 
    {
        System.out.println(ac.toString());
    }
    cursor.close();
    con.commitTransaction();
     
Note that here the search() method is not needed as the Cursor is simply instantiated and the sequential navigation of database objects is performed by standard Java iteration of the Cursor.

Exact Match, Prefix Match and Best Match searches

To perform an "exact match" search, we could use code like the following:
 
    con.startTransaction(Database.TransactionType.ReadOnly);
    Cursor<AreaCode> cursor = new Cursor<AreaCode> (con, AreaCode.class, "areaCode");
    if (cursor.search(Cursor.Operation.ExactMatch, strAreaCode)) 
    {
        System.out.println("\tFound " + op + " for key " + strAreaCode);
        do 
        {
            System.out.println(cursor.next().toString());
        } while (cursor.search(Cursor.Operation.NextMatch, strAreaCode));
    } 
    else 
    {
        System.out.println("\t" + op + " not found for key " + strAreaCode);
    }
    cursor.close();
    con.commitTransaction();
     
To perform a "prefix match" search, we could use code like the above, simply substituting Cursor.Operation.PrefixMatch as the search() operation. Likewise, substitute Cursor.Operation.BestMatch for a "best match" search. Note that to advance the Cursor, the operation Cursor.Operation.NextMatch is used.

RTree Index Search

As explained in the Indexes and Cursors page, the RTree index is commonly used to speed spatial searches. Searches on RTree indexes are performed using the Cursor method search() with one of the four operations Equals, Overlaps, Contains or Neighborhood.

Please refer to the RTree Index page for explanations and examples of how these RTree-specific search operations work. To demonstrate use of the RTree Java APIs, the SDK sample Indexes_RTree is provided. Code snippets from this sample are used below to illustrate the different types of RTree index searches.

Consider the class Rect with a definition like the following:
     
    @Persistent(list=true) // Store class in eXtremeDB database, declare list index
    class Rect
    {
        @Dimension(4)
        @Indexable(type=Database.IndexType.RTree) // Declare rtree index on "square" field
        public short[] square;
    }
     
Sequential search

To sequentially list the contents of the Cursor using the RTree index, we could use code like the following:
 
    // Print out objects in direct or reverse order
    static int iterateRects(Cursor<Rect> cursor, boolean reverse_order) 
    {
        int i = 0;
 
        for (Rect rect = (reverse_order) ? cursor.last() : cursor.first();
        rect != null;
        rect = (reverse_order) ? cursor.prev() : cursor.next())
        {
            if (i++ < SHOW_FIRST) 
            {
                System.out.println("\t" + i + "." + rect);
            }
        }
        if (i > SHOW_FIRST) 
        {
            System.out.println("\t...");
        }
        return i;
    }
     
Note that here the search() method is not needed as the Cursor is simply positioned using the first() or last() method depending on the value of flag reverse_order and the sequential navigation of database objects is performed by calling method next() or prev().

Exact Match, Overlaps, Contains and Neighbourhood searches

To perform an "exact match" search, we use operation Equals with code like the following:
 
    con.startTransaction(Database.TransactionType.ReadWrite);
    cursor = new Cursor<Rect> (con, Rect.class, "square");
    System.out.println("\n\n\tSearch(Operation.Equals, '" + rect3 + "');");
    if (cursor.search(Cursor.Operation.Equals, rect3.square)) 
    {
        i = iterateRects(cursor, false);
        System.out.println("\tFound " + i + " rect(s)");
    }
    cursor.close();
    con.commitTransaction();
     
To perform an "overlaps" search, we could use code like the above, simply substituting Cursor.Operation.Overlaps as the search() operation. Likewise, substitute Cursor.Operation.Contains for a "contains" search. To list the entire contents of the Rect class in order of each object's distance from a point, we specify the point coordinates in rect3.square and use search() operation Cursor.Operation.Neighbourhood.

Trigram Index Search

As explained in the Indexes and Cursors page, Trigram indexes are ideal for text searches when the exact spelling of the target object is not precisely known.

Please refer to the Trigram Index page for explanations and examples of how these Trigram-specific search operations work. To demonstrate use of the Trigram Java APIs, the SDK sample Indexes_Trigram is provided. Code snippets from this sample are used below to illustrate the different types of Trigram index searches.

Consider the class TrigramObj with a definition like the following:
     
    @Persistent 
    class TrigrmObj
    {
        @Indexable(type=Database.IndexType.Trigram)
        String carid;
    }
     
To perform a search() using a Trigram index we might use code like the following:
 
    String[] search_pattern = { "768", " 77", "4pi", "8cc", "7u7", " 77a474ko" };
 
    for (String ptrn : search_pattern) 
    {
        con.startTransaction(Database.TransactionType.ReadOnly);
        cursor = new Cursor<TrigrmObj>(con, TrigrmObj.class, "carid");
        System.out.println("\nObjects with pattern (" + ptrn + "):");
        if (cursor.search(Cursor.Operation.Contains, ptrn)) 
        {
            for (TrigrmObj o : cursor) 
            {
                System.out.println("\t(" + o.carid + ") ");
            }
        }
        cursor.close();
        con.rollbackTransaction();
    }
     
HashTable Index Search

As explained in the Indexes and Cursors page, HashTable indexes are generally used for efficient object lookups. Also, as explained in the Search section above, a HashTable index declared unique=false allows Cursor navigation in sequential order (first to last, or last to first) over the unordered list of objects of a class. To demonstrate use of the HashTable Java APIs, the SDK sample Indexes_HashTable is provided. Code snippets from this sample are used below.

Consider the database schema presented in the Indexes and Cursors page:
 
    @Persistent 
    class Record
    {
        @Indexable(type=Database.IndexType.Hashtable, unique=true, initSize=10000) // Declare unique hash index 
        int iIdx;
 
        @Indexable(type=Database.IndexType.Hashtable, unique=false, initSize=10000) // Declare non-unique hash index 
        int iSeries;
    }
     
The unique index iIdx in this class can be used only for exact lookups with Cursor method find(). For example:
 
    int findValue = 10;
    Record rec;
     
    // Find a specific value in unique index
    System.out.println("\n\n\tFind record with index == " + findValue);
 
    Connection con = new Connection(db);
    con.startTransaction(Database.TransactionType.ReadOnly);
    // Open the cursor
    Cursor cursor = new Cursor<Record>(con, Record.class, "iIdx");
    rec = cursor.find(findValue);
    if ( rec != null )  
    {
        System.out.println("\tIndex " + rec.iIdx + " Series " + rec.iSeries);
    } 
    else 
    {
        System.out.println("\tnot found");
    }
    cursor.close();
    con.rollbackTransaction();
     
The following code snippet demonstrates how to use a non-unique HashTable index iSeries to search for all objects having a specified value:
 
    con.startTransaction(Database.TransactionType.ReadOnly);
    cursor = new Cursor<Record>(con, Record.class, "iSeries");
    // Search for records with specified value for iSeries */
    if (cursor.search(Cursor.Operation.Equals, findValue)) 
    {
        // Show all records in cursor
        rec = cursor.first();
        for (i = 0; i < nRecs && rec != null; ++i) 
        {
            System.out.println("\tIndex " + rec.iIdx + " Series " + rec.iSeries);
            rec = cursor.next();
        }
    } 
    else 
    {
        System.out.println("\tno records found.");
    }
    cursor.close();
    con.rollbackTransaction();
     
List Index Search

As explained in the Indexes and Cursors page, the List index, like a non-unique HashTable, allows navigation in sequential order (first to last, or last to first) over the unordered list of objects of a class.

Consider the class Rect used above for the RTree example:
     
    @Persistent(list=true) // Store class in eXtremeDB database, declare list index
    class Rect
    {
        @Dimension(4)
        @Indexable(type=Database.IndexType.RTree) // Declare rtree index on "square" field
        public short[] square;
    }
     
Note the @Persistent(list=true) annotation. This causes a List index to be maintained internally as a non-unique HashTable index).

Sequential search

To sequentially list the contents of the Cursor using the List index, we could use code like the following:
 
    con.StartTransaction(Database.TransactionType.ReadWrite);
    // Create List cursor 
    Cursor cursor = new Cursor<Rect> (con, Rect.class, "square");
            
    System.out.println("\n\tIterate through cursor with no search condition : ");
    i = iterateRects(cursor, false);
    System.out.println("\tFound " + i + " rect(s)");
    cursor.close();
    con.rollbackTransaction();
     
Note that here the Cursor is instantiated on class Rect without specifying an index, which means use the class List index. Then method iterateRects() is called to perform the sequential navigation of database objects as above in the RTree example .