Lazy Retrievals

Purpose of Lazy Retrieval
The Lazy Invocation of move()
Use With AndSpaces
Example
Propagation of Laziness

Purpose of Lazy Retrieval

Some retrieval operations on ItemSpaces may be expensive, depending on the underlying data and algorithms. There can be problems if the data in such slow ItemSpaces are presented to the user for interactive browsing, for example, or are nested inside an OrSpace or in other situations. These difficulties can be mostly overcome by 'Lazy' retrieval operations. Lazy retrievals move the Cu cursor in the proper direction but not all the way to the next Item actually in the ItemSpace. Some ItemSpaces can easily produce this kind of intermediate result. Not all ItemSpaces implement lazy retrieval: it always is optional. Virtual ItemSpaces frequently pass on the 'laziness' to the base ItemSpaces they wrap.

The Lazy Invocation of move()

An additional retrieval method, beyond

first(), next(), 
last()

and previous(), is move(), which can do any of the things the previous methods do, but also has a special mode controlled by an isLazy parameter:

	int move(Cu cu, protectedPrefixLength, boolean isForwards, boolean isFirst,
		boolean isLazy) throws IOException

The semantics are: If isForwards is true, motion is forwards. If isFirst is true, the given Item is not skipped if it is present. The return value is >=0 if an Item was found, or ItemSpace.FINAL_ITEM if none was found. If isLazy is true, the method has the option of returning ItemSpace.LAZY_RETURN and leaving the cu changed but not corresponding to any Item actually in the ItemSpace. The change must be in the direction corresponding to isForwards, and it must be between the given Item and the nearest Item in the ItemSpace.

Use With AndSpaces

Suppose an AndSpace is used to compute a query having a set of conjoined predicates. Several input ItemSpaces are being intersected, but, as described in AndOrSpaces, some of the individual retrievals may loop for a long time (not inefficiently - the AndSpace algorithm is quite effective, but the delay on any given retrieval is data dependent). In this case, lazy invocations of move() on the AndSpace can be used to provide the user frequent opportunities to cancel the query. Or, a status display can show the progress with better resolution. The invoker just loops on the lazy move() as long as it does not return ItemSpace.FINAL_ITEM: this identical to looping on next(Cu,int) until it returns false. However, the looper has the additional opportunity to do something when ItemSpace.LAZY_RETURN comes back.

Example Query: Customers Given State and Part Purchased

The following is a possible query for customers who buy a given part and who buy from a given supplier:

	ItemSpace andSpace = new AndSpace();
	andSpace.add(customersPurchasingGivenPart); // these ItemSpaces represent query criteria
	andSpace.add(customersInGivenState);
	cu.clear();
	int n = 0;
	while (true) {
		int rslt = andSpace.move(cu, 0, false/*isFirst*/, true/*isForwards*/, true/*isLazy*/);
		if (rslt == ItemSpace.FINAL_ITEM) {
			break; // done
		}
		if (userInterrupt()) {
			break;
		}
		updateStatusDisplay(++n); // show # results so far
		if (rslt != ItemSpace.LAZY_MOVE) {
			// the Item in cu is valid: a matching customer
			printCustomer(cu); // cu contains cust id.
		}
	}

Above, customersPurchasingGivenPart can be any ItemSpace that contains a set of customer ids. The source of such an input ItemSpace would almost always be an ItemSubspace over some prefix. In the EAV model, set-valued Attributes would be the inputs. For example, the customersInGivenState ItemSubspace might be:

	cu.clear().append(STATE).append(state).append(CUSTOMERS_IN_STATE);
	ItemSubspace customersInGivenState = new ItemSubspace(db,cu);

Propagation of Laziness

AndSpace recognizes the isLazy parameter to move() and invokes its inputs using isLazy as well, returning from its input scanning loop early when an input returns ItemSpace.LAZY_MOVE or when the loop has moved forwards. OrSpace also propagates laziness.

There are situations in nesting AndSpaces inside OrSpaces that are sped up significantly using laziness. If lazy invocation is used on any complex nested AndSpace or OrSpace the computation may be much more efficient. In particular, AndSpaces that have small intersections compared to the smallest input set, and which have a large smallest input set, and which are nested in an OrSpace may benefit from laziness.

Previous Next