Start line:  
End line:  

Snippet Preview

Snippet HTML Code

Stack Overflow Questions
  /*-
   * See the file LICENSE for redistribution information.
   *
   * Copyright (c) 2002, 2013 Oracle and/or its affiliates.  All rights reserved.
   *
   */
  
  package com.sleepycat.je;
  
 
A specialized join cursor for use in performing equality or natural joins on secondary indices.

A join cursor is returned when calling Database.join.

To open a join cursor using two secondary cursors:

     Transaction txn = ...
     Database primaryDb = ...
     SecondaryDatabase secondaryDb1 = ...
     SecondaryDatabase secondaryDb2 = ...
     

SecondaryCursor cursor1 = null; SecondaryCursor cursor2 = null; JoinCursor joinCursor = null; try { DatabaseEntry key = new DatabaseEntry(); DatabaseEntry data = new DatabaseEntry();

cursor1 = secondaryDb1.openSecondaryCursor(txn, null); cursor2 = secondaryDb2.openSecondaryCursor(txn, null);

key.setData(...); // initialize key for secondary index 1 OperationStatus status1 = cursor1.getSearchKey(key, data, LockMode.DEFAULT); key.setData(...); // initialize key for secondary index 2 OperationStatus status2 = cursor2.getSearchKey(key, data, LockMode.DEFAULT);

if (status1 == OperationStatus.SUCCESS && status2 == OperationStatus.SUCCESS) {

SecondaryCursor[] cursors = {cursor1, cursor2}; joinCursor = primaryDb.join(cursors, null);

while (true) { OperationStatus joinStatus = joinCursor.getNext(key, data, LockMode.DEFAULT); if (joinStatus == OperationStatus.SUCCESS) { // Do something with the key and data. } else { break; } } } } finally { if (cursor1 != null) { cursor1.close(); } if (cursor2 != null) { cursor2.close(); } if (joinCursor != null) { joinCursor.close(); } }

The join algorithm is described here so that its cost can be estimated and compared to other approaches for performing a query. Say that N cursors are provided for the join operation. According to the order they appear in the array the cursors are labeled C(1) through C(n), and the keys at each cursor position are labeled K(1) through K(n).

  1. Using C(1), the join algorithm iterates sequentially through all records having K(1). This iteration is equivalent to a Cursor.getNextDup operation on the secondary index. The primary key of a candidate record is determined in this manner. The primary record itself is not retrieved and the primary database is not accessed.
  2. For each candidate primary key found in step 1, a Btree lookup is performed using C(2) through C(n), in that order. The Btree lookups are exact searches to determine whether the candidate record also contains secondary keys K(2) through K(n). The lookups are equivalent to a Cursor.getSearchBoth(com.sleepycat.je.DatabaseEntry,com.sleepycat.je.DatabaseEntry,com.sleepycat.je.LockMode) operation on the secondary index. The primary record itself is not retrieved and the primary database is not accessed.
  3. If any lookup in step 2 fails, the algorithm advances to the next candidate record using C(1). Lookups are performed in the order of the cursor array, and the algorithm proceeds to the next C(1) candidate key as soon as a single lookup fails.
  4. If all lookups in step 2 succeed, then the matching key and/or data is returned by the getNext method. If the getNext(com.sleepycat.je.DatabaseEntry,com.sleepycat.je.DatabaseEntry,com.sleepycat.je.LockMode) method signature is used, then the primary database is read to obtain the record data, as if Cursor.getSearchKey(com.sleepycat.je.DatabaseEntry,com.sleepycat.je.DatabaseEntry,com.sleepycat.je.LockMode) were called for the primary database. If the getNext(com.sleepycat.je.DatabaseEntry,com.sleepycat.je.LockMode) method signature is used, then only the primary key is returned and the primary database is not accessed.
  5. The algorithm ends when C(1) has no more candidate records with K(1), and the getNext method will then return OperationStatus.NOTFOUND.
public class JoinCursor implements Closeable {
    private JoinConfig config;
    private Database priDb;
    private Cursor[] secCursors;
    private DatabaseEntry scratchEntry;
    private DatabaseEntry firstSecKey;
    private boolean[] cursorFetchedFirst;

    
Creates a join cursor without parameter checking.
    JoinCursor(Locker locker,
               Database primaryDb,
               final Cursor[] cursors,
               JoinConfig configParam)
        throws DatabaseException {
         = primaryDb;
         = (configParam != null) ? configParam.clone()
                                       : .;
         = new DatabaseEntry();
         = new DatabaseEntry();
         = new DatabaseEntry[cursors.length];
        for (int i = 0; i < cursors.lengthi += 1) {
            [i] = new DatabaseEntry();
        }
         = new boolean[cursors.length];
        Cursor[] sortedCursors = new Cursor[cursors.length];
        System.arraycopy(cursors, 0, sortedCursors, 0, cursors.length);
        if (!.getNoSort()) {
            /*
             * Sort ascending by duplicate count.  Collect counts before
             * sorting so that countEstimate is called only once per cursor.
             */
            final long[] counts = new long[cursors.length];
            for (int i = 0; i < cursors.lengthi += 1) {
                counts[i] = cursors[i].countEstimateInternal();
                assert counts[i] >= 0;
            }
            Arrays.sort(sortedCursorsnew Comparator<Cursor>() {
                public int compare(Cursor o1Cursor o2) {
                    long count1 = -1;
                    long count2 = -1;
                    /*
                     * Scan for objects in cursors not sortedCursors since
                     * sortedCursors is being sorted in place.
                     */
                    for (int i = 0; i < cursors.length &&
                                    (count1 < 0 || count2 < 0); i += 1) {
                        if (cursors[i] == o1) {
                            count1 = counts[i];
                        } else if (cursors[i] == o2) {
                            count2 = counts[i];
                        }
                    }
                    assert count1 >= 0 && count2 >= 0;
                    long cmp = count1 - count2;
                    return (cmp < 0) ? (-1) : ((cmp > 0) ? 1 : 0);
                }
            });
        }
        /*
         * Dup cursors last.  If an error occurs before the constructor is
         * complete, close them and ignore exceptions during close.
         */
        try {
             = new Cursor[cursors.length];
            for (int i = 0; i < cursors.lengthi += 1) {
                [i] = sortedCursors[i].dup(true);
            }
        } catch (DatabaseException e) {
            close(e); /* will throw e */
        }
    }

    
Closes the cursors that have been opened by this join cursor.

The cursors passed to Database.join are not closed by this method, and should be closed by the caller.

WARNING: To guard against memory leaks, the application should discard all references to the closed handle. While BDB makes an effort to discard references from closed objects to the allocated memory for an environment, this behavior is not guaranteed. The safe course of action for an application is to discard all references to closed BDB objects.

Throws:
EnvironmentFailureException if an unexpected, internal or environment-wide failure occurs.
    public void close()
        throws DatabaseException {
        if ( == null) {
            return;
        }
        close(null);
    }

    
Close all cursors we own, throwing only the first exception that occurs.

Parameters:
firstException an exception that has already occured, or null.
    private void close(DatabaseException firstException)
        throws DatabaseException {
         = null;
        for (int i = 0; i < .i += 1) {
            if ([i] != null) {
                try {
                    [i].close();
                } catch (DatabaseException e) {
                    if (firstException == null) {
                        firstException = e;
                    }
                }
                [i] = null;
            }
        }
        if (firstException != null) {
            throw firstException;
        }
    }

    
For unit testing.
    Cursor[] getSortedCursors() {
        return ;
    }

    
Returns the primary database handle associated with this cursor.

Returns:
the primary database handle associated with this cursor.
    public Database getDatabase() {
        return ;
    }

    
Returns this object's configuration.

Returns:
this object's configuration.
    public JoinConfig getConfig() {
        return .clone();
    }

    
Returns the next primary key resulting from the join operation.

An entry is returned by the join cursor for each primary key/data pair having all secondary key values that were specified using the array of secondary cursors passed to Database.join.

In a replicated environment, an explicit transaction must have been specified when opening each cursor, unless read-uncommitted isolation is specified via the CursorConfig or LockMode parameters.

Parameters:
key the primary key returned as output. Its byte array does not need to be initialized by the caller.
lockMode the locking attributes; if null, default attributes are used.
Returns:
OperationStatus.NOTFOUND if no matching key/data pair is found; otherwise, OperationStatus.SUCCESS.
Throws:
OperationFailureException if one of the Read Operation Failures occurs.
EnvironmentFailureException if an unexpected, internal or environment-wide failure occurs.
java.lang.IllegalArgumentException if an invalid parameter is specified, for example, if a DatabaseEntry parameter is null or does not contain a required non-null byte array.
                                   LockMode lockMode)
        throws DatabaseException {
        [0].checkEnv();
        DatabaseUtil.checkForNullDbt(key"key"false);
        [0].trace(."JoinCursor.getNext(key): ",
                            lockMode);
        return retrieveNext(keynulllockMode);
    }

    
Returns the next primary key and data resulting from the join operation.

An entry is returned by the join cursor for each primary key/data pair having all secondary key values that were specified using the array of secondary cursors passed to Database.join.

In a replicated environment, an explicit transaction must have been specified when opening each cursor, unless read-uncommitted isolation is specified via the CursorConfig or LockMode parameters.

Parameters:
key the primary key returned as output. Its byte array does not need to be initialized by the caller.
data the primary data returned as output. Its byte array does not need to be initialized by the caller.
lockMode the locking attributes; if null, default attributes are used.
Returns:
OperationStatus.NOTFOUND if no matching key/data pair is found; otherwise, OperationStatus.SUCCESS.
Throws:
OperationFailureException if one of the Read Operation Failures occurs.
EnvironmentFailureException if an unexpected, internal or environment-wide failure occurs.
java.lang.IllegalArgumentException if an invalid parameter is specified, for example, if a DatabaseEntry parameter is null or does not contain a required non-null byte array.
                                   DatabaseEntry data,
                                   LockMode lockMode)
        throws DatabaseException {
        [0].checkEnv();
        DatabaseUtil.checkForNullDbt(key"key"false);
        DatabaseUtil.checkForNullDbt(data"data"false);
        [0].trace(."JoinCursor.getNext(key,data): ",
                            lockMode);
        return retrieveNext(keydatalockMode);
    }

    
Internal version of getNext(), with an optional data param.

Since duplicates are always sorted and duplicate-duplicates are not allowed, a natural join can be implemented by simply traversing through the duplicates of the first cursor to find candidate keys, and then looking for each candidate key in the duplicate set of the other cursors, without ever reseting a cursor to the beginning of the duplicate set.

This only works when the same duplicate comparison method is used for all cursors. We don't check for that, we just assume the user won't violate that rule.

A future optimization would be to add a SearchMode.BOTH_DUPS operation and use it instead of using SearchMode.BOTH. This would be the equivalent of the undocumented DB_GET_BOTHC operation used by DB core's join() implementation.

    private OperationStatus retrieveNext(DatabaseEntry keyParam,
                                         DatabaseEntry dataParam,
                                         LockMode lockMode)
        throws DatabaseException {
        boolean readUncommitted =
            [0].isReadUncommittedMode(lockMode);
        outerLoop: while (true) {
            /* Process the first cursor to get a candidate key. */
            Cursor secCursor = [0];
            DatabaseEntry candidateKey = [0];
            OperationStatus status;
            if (![0]) {
                /* Get first duplicate at initial cursor position. */
                status = secCursor.getCurrentInternal(,
                                                      candidateKeylockMode);
                if (readUncommitted && status == .) {
                    /* Deleted underneath read-uncommitted cursor; skip it. */
                    [0] = true;
                    continue;
                }
                [0] = true;
            } else {
                /* Already initialized, move to the next candidate key. */
                status = secCursor.retrieveNext(candidateKey,
                                                lockMode.);
            }
            if (status != .) {
                /* No more candidate keys. */
                return status;
            }
            /* Process the second and following cursors. */
            for (int i = 1; i < .i += 1) {
                secCursor = [i];
                DatabaseEntry secKey = [i];
                if (![i]) {
                    status = secCursor.getCurrentInternal(secKey,
                                                          lockMode);
                    if (readUncommitted &&
                        status == .) {
                        /* Deleted underneath read-uncommitted; skip it. */
                        status = secCursor.retrieveNext(secKey,
                                                        lockMode,
                                                        .);
                        if (status != .) {
                            /* All keys were deleted; no possible match. */
                            return status;
                        }
                    }
                    assert status == .;
                    [i] = true;
                }
                .setData(secKey.getData(), secKey.getOffset(),
                                     secKey.getSize());
                status = secCursor.search(candidateKeylockMode,
                                          .);
                if (status != .) {
                    /* No match, get another candidate key. */
                    continue outerLoop;
                }
            }
            /* The candidate key was found for all cursors. */
            if (dataParam != null) {
                status = [0].readPrimaryAfterGet
                    (candidateKeydataParamlockMode, 0);
                if (status == .) {
                    /* Deleted underneath read-uncommitted cursor; skip it. */
                    continue;
                }
                assert status == .;
            }
            keyParam.setData(candidateKey.getData(), candidateKey.getOffset(),
                             candidateKey.getSize());
            return .;
        }
    }
New to GrepCode? Check out our FAQ X