Programming Thoughts
J2EE - Pagination
By Ids

The problem

Loading search results into a simple list usually works well for a small, single table as databases just need to read one continuous block on the disk. Alas, users often want data from remote services, related tables, and even statistics calculated on-the-fly. Complex queries returning large result sets can create database and network strain as well as frustrating UI delays.

Lazy loading

Users viewing results in pages has the possibility of lazy loading. If a list cache has a list of placeholder ids, it could lazy load the records for the requested page. Whether obtaining just the placeholder ids and lazy loading pages is usefully faster than reading the entire result set is a question answered by experience. However, sometimes the answer is obvious. Consider the following query, which finds games designed by a specific designer and designer_game is a many-to-many table.

SELECT g.* FROM game g INNER JOIN designer_game dg ON g.id = dg.game_id WHERE dg.designer_id = ?

Some designers are prolific and have designed hundreds of games in an industry of tens of thousands of games. The results are unlikely to be in a single block on disk. Consider the following query to obtain just the game ids.

SELECT dg.game_id FROM designer_game dg WHERE dg.designer_id = ?

This is bound to be faster simply but not using a large table.

Query strategies

Like the list finder in the previous article, client supplied queries are Strategies and uses the following interfaces, where K is the class of record id, usually Integer, and T is the class describing records. The page by ids finder does not receive ids or return records in display order as queries don't consider input parameter order. The list cache will rearrange records in the order defined by the id list finder.

/** * Strategy for finding list of ids or other primary keys. This is useful for pages using pagination with some * instance of {@link PageByIdsFinder} lazy loading the current page. */ @FunctionalInterface public interface IdListFinder<K extends Serializable> extends Serializable { /** * Returns list of ids of record according to implementing search criteria. Null may be returned if nothing found. */ public List<K> getIds() throws Exception; } /** * Strategy for lazy loading a page of records to display from their ids (or other unique key), typically found by a * paired {@link IdListFinder} instance. */ @FunctionalInterface public interface PageByIdsFinder<K extends Serializable,T extends Serializable> extends Serializable { /** * Returns items from their ids. If any records are missing, the successfully retrieved ones must still be * returned. No item should ever be null. */ public Collection<T> getItems(Collection<K> keys) throws Exception; }

An example of an id finder and page by ids finder are shown below.

public static class GameIdFinderByDesigner implements IdListFinder<Integer> { private static final long serialVersionUID = 9106528005887125428L; private int designerId; private String designerName; public GameIdFinderByDesigner(int designerId, String designerName) { this.designerId = designerId; this.designerName = designerName; } @Override public List<Integer> getIds() throws Exception { DesignerGameTable designerGameTable; designerGameTable = DesignerGameTable.getInstance(); return designerGameTable.getGameIdsByDesignerId(designerId); } public int getDesignerId() { return designerId; } public String getDesignerName() { return designerName; } } public static class GamePageByIdsFinder implements PageByIdsFinder<Integer,GameDTO> { private static final long serialVersionUID = 4032331794734656685L; @Override public Collection<GameDTO> getItems(Collection<Integer> keys) throws Exception { GameTable gameTable; Collection<GameDTO> result; gameTable = GameTable.getInstance(); result = gameTable.findByPrimaryKeys(keys, GameOption.DESIGNERS); return result; } }

Updating member fields

The list cache must include another generic type, K, for the record id, which is usually Integer. As record and id type are only known at run-time, the client must supply an adapter for linking a record with its id. The interface for this is shown below

/** * Generic Adapter definition for extracting the id or primary key from a Data Transfer Object or entity bean. */ @FunctionalInterface public interface KeyExtractor<K extends Serializable,V extends Serializable> extends Serializable { public K getKey(V value); }

The ItemData class identified by the previous article must now include the id placeholder and whether the record needs to be lazy loaded

private static class ItemData<K,T> implements Serializable { private K id; private T item; private boolean pageExtensionReload; private boolean reload; public ItemData() { id = null; item = null; pageExtensionReload = false; reload = false; } public K getId() { return id; } public void setId(K value) { id = value; } public T getItem() { return item; } public void setItem(T value) { item = value; } public boolean getPageExtensionReload() { return pageExtensionReload; } public void setPageExtensionReload(boolean pageExtensionReload) { this.pageExtensionReload = pageExtensionReload; } public boolean getReload() { return reload; } public void setReload(boolean reload) { this.reload = reload; } }

List cache must also include more member variables for the query strategies.

public class ListCache<K extends Serializable,T extends Serializable> implements Serializable { public enum PaginationMode {BASE_RECORD_LIST, FULL_LIST, PAGE_BY_IDS} private ListFinder<T> baseRecordListFinder; // Strategy to load base record list in base record list pagination mode private IdListFinder<K> idListFinder; // Strategy to load ids of list for page by ids pagination mode private KeyExtractor<K,T> keyExtractor; private List<ItemData<K,T>> list; // List of records or placeholders private ListFinder<T> listFinder; // Strategy to load entire list in full list pagination mode private PageByIdsFinder<K,T> pageByIdsFinder; // Strategy to retrieve page in page by ids pagination mode private PageExtensionAssembler<T> pageExtensionAssembler; // Adds additional data for current page for base record list pagination mode private int pageSize; private PaginationMode paginationMode; private boolean reload; // Whether list must be reloaded private int selectedIndex; // Index of currently selected record, 0 based, or -1 for no selected record

Updating core functions

Like base record list mode, reading a page requires checking which records must be loaded. However, when retrieving a page by ids, expected records may be deleted. If so, ids must be deleted and the next records retrieved till the page is full or no more records remain.

private void checkPageListData(int startIndex, int endIndex) throws Exception { switch (paginationMode) { case BASE_RECORD_LIST: checkPageListDataByBaseRecords(startIndex, endIndex); break; case FULL_LIST: // Entire list already loaded break; case PAGE_BY_IDS: checkPageListDataByIds(startIndex, endIndex); break; } } /** * Loads any missing records for items in a range of indices, usually the current page, from their ids. */ private void checkPageListDataByIds(int startIndex, int endIndex) throws Exception { ItemData<K,T> itemData; Collection<K> ids; Collection<T> loadingItems; List<Integer> removalIndices; Map<K,Integer> loadingIds; K id; T item; int i, index, listSize; boolean loadFailed; do { loadFailed = false; listSize = list.size(); // Find items that need to be loaded ids = new ArrayList<K>(); loadingIds = new HashMap<K,Integer>(); for (i = startIndex; i <= endIndex; i++) { if (i >= 0 && i <= listSize - 1) { itemData = list.get(i); if (itemData.getReload()) { ids.add(itemData.getId()); loadingIds.put(itemData.getId(), i); } } } if (ids.size() > 0) { // Load items from multi item finder loadingItems = pageByIdsFinder.getItems(ids); for (T loadingItem: loadingItems) { id = keyExtractor.getKey(loadingItem); index = loadingIds.get(id); itemData.setItem(loadingItem); itemData.setReload(false); itemData.setPageExtensionReload(false); } // Delete items that multi item finder did not load as they no longer exist removalIndices = new ArrayList<Integer>(); for (K loadingId: loadingIds.keySet()) { index = loadingIds.get(loadingId); item = list.get(index).getItem(); if (item == null) { removalIndices.add(index); loadFailed = true; } } Collections.sort(removalIndices, Collections.reverseOrder()); for (int removalIndex: removalIndices) { list.remove(removalIndex); } } } // If there any failed items, which are removed, higher entries may // shift to take their place in the requested page and some may be unloaded. while (loadFailed); }

Client code using pagination shouldn't read the entire list at once but reading the entire list is shown for completeness. Like retrieving a page, the ids for deleted records must be discarded.

private void checkEntireListData() throws Exception { switch (paginationMode) { case BASE_RECORD_LIST: checkEntireListDataByBaseRecords(); break; case FULL_LIST: // Entire list already loaded break; case PAGE_BY_IDS: checkEntireListDataByIds(); break; } } /** * Loads any missing records from their ids. */ private void checkEntireListDataByIds() throws Exception { ItemData<K,T> itemData; K id; T item; Collection<K> ids; Collection<T> loadingItems; List<Integer> removalIndices; Map<K,Integer> loadingIds; int i, index, size; size = list.size(); // Find items that need to be loaded ids = new ArrayList<K>(); loadingIds = new HashMap<K,Integer>(); for (i = 0; i < size; i++) { itemData = list.get(i); if (itemData.getReload()) { ids.add(itemData.getId()); loadingIds.put(itemData.getId(), i); } } // Load items from page-by-id finder loadingItems = pageByIdsFinder.getItems(ids); for (T loadingItem: loadingItems) { id = keyExtractor.getKey(loadingItem); index = loadingIds.get(id); itemData = list.get(index); itemData.setItem(loadingItem); } // Delete items that page-by-id finder did not load as they no longer exist removalIndices = new ArrayList<Integer>(); for (K loadingId: loadingIds.keySet()) { index = loadingIds.get(loadingId); item = list.get(index).getItem(); if (item == null) { removalIndices.add(index); } } Collections.sort(removalIndices, Collections.reverseOrder()); for (int removeIndex: removalIndices) { list.remove(removeIndex); } }

The existence of new pagination modes means other functions must be updated.

private void loadList() throws Exception { List<K> idList; List<T> itemList; int listSize; switch (paginationMode) { case BASE_RECORD_LIST: itemList = baseRecordListFinder.getList(); if (itemList == null) { itemList = new ArrayList<T>(); } setList(itemList); break; case FULL_LIST: itemList = listFinder.getList(); if (itemList == null) { itemList = new ArrayList<T>(); } setList(itemList, listFinder.getLoadsDetails()); break; case PAGE_BY_IDS: idList = idListFinder.getIds(); if (idList == null) { idList = new ArrayList<K>(); } setIdList(idList); break; } } /** * Caches page-by-id record markers, which are usually the record primary keys. */ private synchronized void setIdList(List<K> ids) { ItemData<K,T> itemData; reload = false; list = new ArrayList<ItemData<K,T>>(ids.size()); for (K id: ids) { itemData = new ItemData<K,T>(); itemData.setId(id); itemData.setItem(null); itemData.setPageExtensionReload(false); itemData.setReload(true); list.add(itemData); } checkSelectedIndex(); } private synchronized void setList(List<T> value, boolean pageExtensionsLoaded) { ItemData<K,T> itemData; reload = false; list = new ArrayList<ItemData<K,T>>(value.size()); for (T item: value) { itemData = new ItemData<K,T>(); itemData.setId(keyExtractor.getKey(item)); itemData.setItem(item); itemData.setPageExtensionReload(!pageExtensionsLoaded); itemData.setReload(false); list.add(itemData); } checkSelectedIndex(); }

Setting id list

Like other list setters, the id list cannot be set without its finder and resets other finders.

/** * Caches id list already loaded, sets id list finder Strategy used to load it, and sets page by ids pagination mode. */ public synchronized void setIdListAndFinder(List<K> idList, IdListFinder idListFinder) { setIdList(idList); this.baseRecordListFinder = null; this.idListFinder = idListFinder; this.listFinder = null; this.paginationMode = PaginationMode.PAGE_BY_IDS; setSelectedIndex(0); } /** * Sets Strategy used to retrieve ids, sets page by ids pagination mode and marks list for reload. */ public void setIdListFinder(IdListFinder<K> idListFinder) { setIdList(new ArrayList<>()); this.baseRecordListFinder = null; this.idListFinder = idListFinder; this.listFinder = null; this.paginationMode = PaginationMode.PAGE_BY_IDS; markReload(); } /** * Sets Strategy used to retrieve page by their record ids. */ public void setPageByIdsFinder(PageByIdsFinder<K,T> value) { pageByIdsFinder = value; }

Notes and Limitations

The use of the term 'id' is a convenience but is a bit misleading. Despite what the term suggests, the key need not be a serial number and can be any unique key, as well as the record's primary key.

The relationship between key and record is fixed, so the page by ids finder is also fixed. In contrast, different search criteria must set their own id list finders.

Keys are in whatever order the database returns, which may not be what the user prefers, such as alphabetical name order or descending creation date. Unless the page query includes table joins or on-the-fly calculations, expanding the id query with an ORDER BY clause will mean reading the table that pagination is trying to lazy load.

Next part

Continued in By Index.