Programming Thoughts
J2EE - Pagination
By Index

Displaying search results in pages

Most applications are data driven, users search large tables and expect search results split into multiple pages. This series of articles describes a simplified version of a Template helper class, named list cache, that was developed over the years according to user requirements. This articles extends a previous, basic design for displaying search results in pages.

The opportunity

If the columns of a query's ORDER BY clause match an index and only a small number of records are needed, the query optimizer in most databases will retrieve only the required records and in the correct order, rather than retrieve and sort the entire result set. This is explained by Markus Winand at Querying Top-N Rows. Further, such databases support the OFFSET keyword to skip a number of records from the result set.

If set up correctly, this creates an opportunity for lazy load pagination where the user gets the results in a desired order.

Lazy loading

Consider the following query, which finds games published in 1990 in order of rank.

SELECT g.* FROM game g WHERE g.year_published = 1990 ORDER BY g.year, g.rank

If there's an index based on year_published and rank, the query optimizer will use the index order, rather than sort the entire result set. The size of the result set can be obtained with following query.

SELECT COUNT(*) FROM game g WHERE g.year_published = 1990

The query to obtain a page varies between databases. For the popular MySQL, the OFFSET value is (pageNo - 1) * pageSize, so the example for page 3 of size 10 pages becomes the following.

SELECT g.* FROM game g WHERE g.year_published = 1990 ORDER BY g.year, g.rank OFFSET 20 LIMIT 10

Query strategies

Like the list finder in the previous article, client supplied queries are Strategies and uses the following interfaces, where T is the class describing records.

/** * Strategy for finding the size of a list of records. This is useful for pages using pagination with some instance * of {@link PageByIndexRangeFinder} lazy loading the current page. */ @FunctionalInterface public interface ListSizeFinder extends Serializable { /** * Returns size of list records according to implementing search criteria. */ public int getSize() throws Exception; } /** * Strategy for lazy loading a page of records to display from an index range (0 based), typically with list size * found by {@link ListSizeFinder}. This is particularly useful for reading MySQL tables traversing an index using * OFFSET and LIMIT keywords. */ @FunctionalInterface public interface PageByIndexRangeFinder<T extends Serializable> extends Serializable { /** * Returns items within a range of indices, where indices start at 0. If the range covers indices that don't exist, * any records that are in range should be returned. No item should ever be null. For convenience of MySQL * adapters, OFFSET is startIndex and LIMIT is endIndex - startIndex + 1. * * @param startIndex Start of index range, where indices start at zero. * @param endIndex End of index range (inclusive), where indices start at zero. */ public List<T> getItems(int startIndex, int endIndex) throws Exception; }

An example of a list size finder and page by index finder are shown below.

public static class GameListSizeFinderByRank implements ListSizeFinder { private Integer rankRangeStart; private Integer rankRangeEnd; public GameListSizeFinderByRank(Integer rankRangeStart, Integer rankRangeEnd) { this.rankRangeStart = rankRangeStart; this.rankRangeEnd = rankRangeEnd; } @Override public int getSize() throws Exception { GameTable gameTable; int workingStart, workingEnd; workingStart = (rankRangeStart != null)?rankRangeStart:0; workingEnd = (rankRangeEnd != null)?rankRangeEnd:999999; gameTable = Model.getInstance().getGameTable(); return gameTable.getListSizeByRankAll(workingStart, workingEnd); } public Integer getRankRangeStart() { return rankRangeStart; } public Integer getRankRangeEnd() { return rankRangeEnd; } } public static class GamePageFinderByRank implements PageByIndexRangeFinder<Game> { private Integer rankRangeStart; private Integer rankRangeEnd; public GamePageFinderByRank(Integer rankRangeStart, Integer rankRangeEnd) { this.rankRangeStart = rankRangeStart; this.rankRangeEnd = rankRangeEnd; } @Override public List<Game> getItems(int startIndex, int endIndex) throws Exception { GameTable gameTable; int workingStart, workingEnd; workingStart = (rankRangeStart != null)?rankRangeStart:0; workingEnd = (rankRangeEnd != null)?rankRangeEnd:999999; gameTable = Model.getInstance().getGameTable(); return gameTable.findPageByRankAll(workingStart, workingEnd, startIndex, endIndex); } public Integer getRankRangeStart() { return rankRangeStart; } public Integer getRankRangeEnd() { return rankRangeEnd; } }

Updating member fields

The member variables become the following

public class ListCache<K extends Serializable,T extends Serializable> implements Serializable { public enum PaginationMode {BASE_RECORD_LIST, FULL_LIST, PAGE_BY_IDS, PAGE_BY_INDEX_RANGE} 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 ListSizeFinder listSizeFinder; // Strategy to get list size for page by index pagination mode private PageByIdsFinder<K,T> pageByIdsFinder; // Strategy to retrieve page in page by ids pagination mode private PageByIndexRangeFinder<T> pageByIndexRangeFinder; // Strategy to retrieve page by indices 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

Like paging by id, the results for a page can be smaller than expected due to deleted records. However, as a specific size is requested, a shortage means thee are no remaining records and the list must be truncated to match.

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; case PAGE_BY_INDEX_RANGE: checkPageListDataByIndexRange(startIndex, endIndex); break; } } /** * Loads any missing records from their indices. */ private void checkPageListDataByIndexRange(int startIndex, int endIndex) throws Exception { ItemData<K,T> itemData; T item; List<T> loadingItemList; int i, listSize, rangeSize, lowestNotLoaded, highestNotLoaded; listSize = list.size(); // Find what needs to be loaded. If that's multiple ranges, one big load is done anyway as it's probably faster // multiple loads lowestNotLoaded = -1; highestNotLoaded = -1; for (i = startIndex; i <= endIndex; i++) { if (list.get(i).getReload()) { if (lowestNotLoaded < 0) { lowestNotLoaded = i; } highestNotLoaded = i; } } if (lowestNotLoaded > -1) { rangeSize = highestNotLoaded - lowestNotLoaded + 1; loadingItemList = pageByIndexRangeFinder.getItems(lowestNotLoaded, highestNotLoaded); // If result size less than requested range, end of source list unexpectedly reached, so shrink our list if (rangeSize > loadingItemList.size()) { list.subList(startIndex + loadingItemList.size(), listSize).clear(); } // If result size greater than requested range, WTF?, ignore the excess // Load items from page-by-index-range finder for (i = 0; i < loadingItemList.size() && i < rangeSize; i++) { item = loadingItemList.get(i); itemData = list.get(i + lowestNotLoaded); itemData.setId(keyExtractor.getKey(item)); itemData.setItem(item); } } }

Updating core functions

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, missing records means the list must be truncated.

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; case PAGE_BY_INDEX_RANGE: checkEntireListDataByIndexRange(); break; } } /** * Loads any missing records for items in a range of indices, usually the current page, from the indices. */ private void checkEntireListDataByIndexRange() throws Exception { ItemData<K,T> itemData; T item; List<T> loadingItemList; int i, size, rangeSize, lowestNotLoaded, highestNotLoaded; size = list.size(); // Find what needs to be loaded. If that's multiple ranges, one big load is done anyway as it's probably faster // than multiple loads lowestNotLoaded = -1; highestNotLoaded = -1; for (i = 0; i < size; i++) { if (list.get(i).getReload()) { if (lowestNotLoaded < 0) { lowestNotLoaded = i; } highestNotLoaded = i; } } if (lowestNotLoaded > -1) { rangeSize = highestNotLoaded - lowestNotLoaded + 1; loadingItemList = pageByIndexRangeFinder.getItems(lowestNotLoaded, highestNotLoaded); // If result size less than requested range, end of source list unexpectedly reached, so shrink our list if (rangeSize > loadingItemList.size()) { list.subList(lowestNotLoaded + loadingItemList.size(), size).clear(); } // If result size greater than requested range, WTF?, ignore the excess // Load items from page-by-index-range finder for (i = 0; i < loadingItemList.size() && i < rangeSize; i++) { item = loadingItemList.get(i); itemData = list.get(i + lowestNotLoaded); itemData.setId(keyExtractor.getKey(item)); itemData.setItem(item); itemData.setPageExtensionReload(false); itemData.setReload(false); } } }

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, false); break; case FULL_LIST: itemList = listFinder.getList(); if (itemList == null) { itemList = new ArrayList<T>(); } setList(itemList, true); break; case PAGE_BY_IDS: idList = idListFinder.getIds(); if (idList == null) { idList = new ArrayList<K>(); } setIdList(idList); break; case PAGE_BY_INDEX_RANGE: listSize = listSizeFinder.getSize(); setListSize(listSize); break; } } /** * Caches page-by-index-range record markers. */ private synchronized void setListSize(int listSize) { ItemData<K,T> itemData; int i; reload = false; list = new ArrayList<ItemData<K,T>>(listSize); for (i = 0; i < listSize; i++) { itemData = new ItemData<K,T>(); itemData.setId(null); itemData.setItem(null); itemData.setPageExtensionReload(false); itemData.setReload(true); list.add(itemData); } checkSelectedIndex(); }

Setting list size

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

/** * Sets list size, the list size finder used to find that, page by index range finder that will be used to find * pages from list, and sets page by index pagination mode. * * @param listSize Size of list to cache. * @param listSizeFinder Command that found list size. * @param pageByIndexRangeFinder Command that will load pages of list.. */ public synchronized void setListSizeAndFinder(int listSize, ListSizeFinder listSizeFinder, PageByIndexRangeFinder<T> pageByIndexRangeFinder) { setListSize(listSize); this.baseRecordListFinder = null; this.idListFinder = null; this.listFinder = null; this.listSizeFinder = listSizeFinder; this.pageByIndexRangeFinder = pageByIndexRangeFinder; this.paginationMode = PaginationMode.PAGE_BY_INDEX; setSelectedIndex(0); } /** * Sets the list size finder, sets accompanying page by index range finder that will be used to find pages from list, * sets page by index pagination mode, and marks list for reload. * * @param listSizeFinder Command that found list size. * @param pageByIndexRangeFinder Command that will load pages of list.. */ public void setListSizeFinder(ListSizeFinder listSizeFinder, PageByIndexRangeFinder<T> pageByIndexRangeFinder) { setListSize(0); this.baseRecordListFinder = null; this.idListFinder = idListFinder; this.listFinder = null; this.listSizeFinder = listSizeFinder; this.pageByIndexRangeFinder = pageByIndexRangeFinder; this.paginationMode = PaginationMode.PAGE_BY_INDEX; markReload(); }

Notes and Limitations

Unlike page by ids, list size finders must be paired with its own page by index finder.

Use of OFFSET for pagination, though convenient, performs poorly. To find a page, the database must trawl the records used for previous pages. The higher the page number, the slower it is to retrieve it. This is explained in Paging Through Results by Markus Winand.

Next part

Continued in Example.