Feature Proposal: Search results pagination

TWiki currently lacks a way to control a set of search results. I would like to be able to show results 1-10, then 11-20, etc.

Motivation

It might be useful to present a subset of search results, but I think it is really fit for TWiki applications: for instance to show blog entries/comments across pages, a subset of results in table format, only 5 topic in bookview per page, etc.

Implementation

Bugs:Item3931

Visual schema for specification:

We can discern these entities: Collection, Result set, Sorted result list, Display page

Collection

All searchable items: topics, form fields, table rows, etc.

(Raw) result set

Unsorted. For performance this set might be cached (so a new sorted result list can be created from the set). The maximum number of results is defined by SEARCH parameter limit.

Properties:

• items

It would be tremendously powerful if we could merge search results from different plugins and core. For instance a combination of TagMePlugin search resuls with core search results.

Sorted result list

When no sort is specified the default sort. For performance this set might also be cached.

Properties:

• (sorted) items
  • Follows from this: item count

(Display) pages

Proposed parameters for pages: pagesize and showpage. Users should not be bothered with implementation specific terms like offset.

Properties:

• pagesize: the number of items displayed per 'page'
  • When no pagesize is given, the page size is item count
  • When pagesize > item count, the page size is item count
  • page size can not be smaller than 1
• showpage: the first page that is displayed
  • When no showpage is given, the start page is 1 (using one-based index, so array position 0)
  • When start page is larger than the number of pages, showpage is the last page
  • showpage cannot be smaller than 1

Page decoration

• Display of the start and end of the page. For example: "Results: 1-10".
• Links to pages (as page numbers). The current page is not clickable.
• Link to previous page. Is disabled or not shown on the first page.
• Link to next page. Is disabled or not shown on the last page.

See also: Search Pagination Pattern (Yahoo! Design Pattern Library)

-- ArthurClemens - 22 Apr 2007

Discussion

This can be realized relatively easily with a new offset="10" parameter. Combined with limit="20" you can do a paginated search.

For speed, the resulting list of topics of the first search could be cached and re-used in follow-up searches that have an offset.

-- PeterThoeny - 01 Dec 2006

To provide interface feedback it would be useful to know if there are any more results, so a Next button can be showed.

-- ArthurClemens - 01 Dec 2006

It is easy to determine the total number of topics. Spec-wise, not sure how that info can be returned by a %SEARCH{}%.

-- PeterThoeny - 02 Dec 2006

I proposed the exact same a year ago in SearchOrderAndLimitBehavour.

I just called it start instead of offset. But note the proposal that a negative start/offset would start from the other end and resolve some additional needs.

An up2date rewrite of my old proposal would then be

An enhancement which will be 100% backwards compatible we create an additional SEARCH option called "offset" which is the first hit in the list of found topic to show. This offset value can be positive which means it counts from the beginning. Or negative which means it counts from the end. Default must be 0 which makes it backwards compatible with Cairo.

Examples:

• Show the latest 10 bug reports in ascending order: order="modified" reverse="off" offset="-10"
• Show the latest 10 bug reports before the last 10. order="modified" reverse="off" offset="-20" limit="10"
• Show all bugs. Browse 20 at a time. Newest first order="modified" reverse="on" offset="0" limit="20" and then you browse by having a link that contains a twiki variable which increases by 20. This use is actually so common that the search itself should have the feature of setting a variable that can be used for this purpose.

-- KennethLavrsen - 02 Dec 2006

And then you would require running the search again for the next, say 10 items? If you have a 1000 item search, you are wasting a lot of time.

Maybe we should move to a scheme as in FormQueryPlugin where the search is done once and can be rendered in different ways over and over again. (YetAnotherFormQueryPlugin is 100% compatible with Cairo search, but I have not gotten around adding new Dakar search features, by the way.)

-- ThomasWeigert - 03 Dec 2006

Kenneth: I do not understand the need for a negative offset. I think it is not necessary if we apply the offset after the limit, this way there is no need to compensate for the reverse flag.

Thomas: That is what I meant by "for speed, the resulting list of topics of the first search could be cached and re-used in follow-up searches that have an offset." Technically, the resulting topic list of a search can be cached (cache ID based on user name and all search parameters except offset parameter), and cache is re-used if same search is applied (with same/different offset) within a certain timeframe (say 10 min.)

-- PeterThoeny - 05 Dec 2006

As an example, pagination of search results has been part of the BlogPlugin for quite some time now. It is based on the skip and limit parameter of the DBCachePlugin. Here is a rewrite of TWiki's WebChanges. All kinds of pages are paginated with "next" and "prev" links showing up at the bottom and the top, but only if there are next or previous items. More examples: the frontpage showing the 5 most recent postings; category pages showing the 5 most recent postings in that category; the blog author pages; each posting is double linked; news feeds are double linked. There's an implementation of NEXTDOC and PREVDOC in the BlogPlugin (making use of the DBCacheContrib API) that compute the double linkage used for paginating forward and backward which could be externalized to be reused in other applications.

Very essential to pagination is the proper integration of sort and limit. As far as I remember SEARCH first limits the search result and sorts the remaining hit set afterwards ... which will result in an incorrect pagination. So there might be some more "gotchas" using SEARCH for pagination. Another one is, that a SEARCH spanning multiple webs does not merge all results from all webs properly. Sortion is done per web only and then all is concatenated.

-- MichaelDaum - 05 Dec 2006

This feature request is listed for some time now in TWikiFeature04x02. It looks like all are in agreement to add a pagination feature to SEARCH. It just needs a clearly defined spec and a person driving it.

-- PeterThoeny - 26 Mar 2007

I'd prefer short and descriptive parameters. Google uses a simple start parameter for the hit number, not page number, and a hardcoded size parameter. How about something like poffset="50" psize="25"?

Suggestion for implementation when pagination is used: For speed, do the complete search the first time and cache the list of topics for the next pages. A hash string can be built from the full search string (with all parameters, excluding header and format parameters) and user name. (Something similar has been done for the HeadlinesPlugin)

Example:

• TWikiGuest does a search for %SEARCH{ "faq" scope="topic" web="all, -Sandbox" nonoise="on" format="| $topic: $summary |" poffset="%URLPARAM{poffset}%" psize="25" }%.
• Do the search, build the list of topics
• Build a hash string of Main.TWikiGuest and "faq" scope="topic" web="all, -Sandbox" nonoise="on".
• Use the hash string as the file name of the cache; in it store the topic list.
• For poffset other than 0:
  • build the hash string
  • if cache file exist of same has string, and if not older than 15 min, use cache

-- PeterThoeny - 22 Apr 2007

How about skip and limit instead of poffset and psize. That's what DBCachePlugin uses.

-- MichaelDaum - 24 Apr 2007

poffset, psize and skip forces you to think in individual results instead of in pages. When the end goal is to show results in pages of n size we shouldn't force the user of SEARCH to think in numbers.
limit is already taken.

-- ArthurClemens - 24 Apr 2007

Which users are you talking about: the TWikiApplication developer or the visitor to your wiki? The first should be able to think either way. The latter shouldn't have to think about poffsets, psizes or pagesizes at all.

-- MichaelDaum - 24 Apr 2007

The users of SEARCH: so I am talking about the public interface of the search function. I think pagesize and showpage are all you need. But perhaps you can give usage examples where finegrained control is necessary and can't be done with these 2 parameters?

-- ArthurClemens - 24 Apr 2007

Well, using skip and limit (or psize) you could skip fragments of a page: the last half of page one and the first half of page two ... but I am not sure if that is of much use.

-- MichaelDaum - 24 Apr 2007

I worked on this way long time ago, then something happened that prevented me from commit it ( I think that there was a problem with multiple searchs on the same page, or something like that, followed by a major refactoring of the codebase or I just forgot about it).

For what is worth, I'm attaching the resulting patch, against a pre-Dakar version of TWiki. It uses "start" and "step" to define the initial element and how many rows to display.

Hope it helps.

-- RafaelAlvarez - 24 Apr 2007

Could perhaps MapReduce be of use?

-- ArthurClemens - 07 May 2007

We don't have thousands of CPUs where we can parallelize a reduce() call.

-- MichaelDaum - 07 May 2007

I am currently looking for a new implementer. Sven has too many things on his plate to take it to 4.2.

-- ArthurClemens - 21 May 2007

Feature not implemented before the deadline for 4.2.0. So deferred to Georgetown.

-- KennethLavrsen - 29 May 2007

Yes, the train left the station. In the future I hope accepted usability enhancements like this one make it into a pending release.

-- PeterThoeny - 29 May 2007

Search pagination is a feature that is very much expected. This feature proposal is accepted but lacks a developer to implement it.

I removed the developers from the CommittedDeveloper field so that a new developer can step in. Anybody interested?

-- PeterThoeny - 2009-05-11

At the minimum, if the offset (or skip) parameter is there to specify how many items to skip, and the limit parameter is to specify maximum number of results excluding skipped items, you can implement pagination with a couple of additional helper variables.

For example:

• %FORLOOP{"item1,item2,..." format="..."}% :
  iterate through the comma separated items
• %RANGE{[start="START"] "STOP"}% :
  yields a comma separated list of items. %RANGES{"5"}% yields "0, 1, 2, 3, 4"
• %ENTRIES_PER_PAGE% :
  How many items are displayed per page
• part URL parameter :
  Which page to display. 0 base. If it's 'all', all items are displayed on one page.

%SEARCH{
...
offset="%IF{"$'URLPARAM{part}' != 'all' and $'URLPARAM{part}' != '0'" then="%CALCULATE{"$INT(%URLPARAM{part}% * %IF{"defined ENTRIES_PER_PAGE" then="%ENTRIES_PER_PAGE%" else="10"}%)"}%"}%"
limit="%IF{"$'URLPARAM{part}' != 'all'" then="%IF{"defined ENTRIES_PER_PAGE" then="%ENTRIES_PER_PAGE%" else="10"}%"}%"
footer="$percntIF{\"$ntopics > %IF{"defined ENTRIES_PER_PAGE" then="%ENTRIES_PER_PAGE%" else="10"}%\" then=\"$n---++$n$percntFORLOOP{\"$percntRANGE{$percntCALCULATE{\"$INT(($ntopics - 1) / %IF{"defined ENTRIES_PER_PAGE" then="%ENTRIES_PER_PAGE%" else="10"}% + 1)\"}$percnt}$percnt\" format=\"$dollarpercntIF{$dollarquot$i = '%URLPARAM{part}%'$dollarquot then=$dollarquot*$iplus1*$dollarquot else=$dollarquot[[%SCRIPTURLPATH{view}%/%BASEWEB%/%BASETOPIC%?part=$i][$iplus1]]$dollarquot}$dollarnop%   \"}$percnt$percntIF{\"$'URLPARAM{part}' = 'all'\" then=\"*all*\" else=\"[[%SCRIPTURLPATH{view}%/%BASEWEB%/%BASETOPIC%?part=all][all]]\"}$percnt\"}$percnt"
}%

This is a bit complex.

-- HideyoImazu - 2012-11-05

Agreed, just adding an offset/skip/start parameter should be sufficient. Google calls the parameter start, Bing calls it first, Yahoo calls it pstart. I don't have a strong opinion, start sounds good.

As I mentioned before, for performance it would be good to cache the result so that the next page can be rendered without delay.

-- PeterThoeny - 2012-11-05

I think it is not too difficult to add "Previous" and "Next" navigation before and after the paginated SEARCH if you use CALCULATE to glue stuff together. Here is an untested example:

%CALCULATE{$SET(start, %URLPARAM{ "start" default="1" }%)}%
%CALCULATE{$SET(limit, %URLPARAM{ "limit" default="10" }%)}%<!-- entries per page -->
<div id="searchTopNav"></div>
%SEARCH{
 "%URLPARAM{ "search" encode="quote" }%"
 nonoise="on"
 start="%CALCULATE{$GET(start)}%"
 limit="%CALCULATE{$GET(limit)}%"
 footer="$percntCALCULATE{$SET(max, $ntopics)}$percnt"
}%
%CALCULATE{
  $SET(prevText, $IF(
    $GET(start)>1,
    <a href="%SCRIPTURL{view}%/%WEB%/%TOPIC%?%URLPARAM{ "search" encode="url" }%;start=$INT($GET(start)+$GET(limit));limit=$GET(limit)">&laquo;Previous</a>,
    %GRAY% &laquo;Previous %ENDCOLOR%
  ))
  $GET(prevText)
}%
%CALCULATE{
  $SET(nextText, $IF(
    $GET(start)<$GET(max),
    <a href="%SCRIPTURL{view}%/%WEB%/%TOPIC%?%URLPARAM{ "search" encode="url" }%;start=$INT($GET(start)+$GET(limit));limit=$GET(limit)">Next&raquo;</a>,
    %GRAY% Next&raquo; %ENDCOLOR%
  ))
  $GET(nextText)
}%
<script>
  $('#searchTopNav').html(%CALCULATE{$GET(prevText) $GET(nextText)}%);
</script>

(I added newlines to CALCULATE to make it easier to read; white-space needs to be removed in actual use)

With some more CALCULATE magic it is possible to create a Google-like list of page links, like:

«Previous   1 2 3 4 5 6 7 8 9 10   Next»

-- PeterThoeny - 2012-11-05

OK. Let's use start.

-- HideyoImazu - 2012-11-06

I've realized that $ntopics does not exceed limit. For pagination, you need the total number of topics matching the criteria. I plan to introduce $tntopics (the initial t is for total). Somebody has a better name?

-- HideyoImazu - 2012-11-07

$tntopics sounds good. Please look into performance impact. The limit parameter might have a positive effect on performance, so looking at all topics just to get $tntopics could be expensive if pagination is not used. Meaning, if there is a performance impact, we could implement $tntopics to be made valid only if the start parameter is present.

-- PeterThoeny - 2012-11-07

No performance impact by $tntopics because the value is obtained by $tntopics = @topicList;

-- HideyoImazu - 2012-11-07

Now the start parameter and $tntopics in format/header/footer are there in my environment, the following proof-of-concept WebTopicList with pagination is working. It shows the following line.

«Prev   1   2   3   4   5   Next»

• The minimum number of start is zero.
• This uses %FORLOOP{...}% and %RANGE{...}% as mentioned above. Do you think these should be in a plug-in or can be in the TWiki core?

%SEARCH{"." type="regex" scope="topic" format="   * $topic" separator="$n" nonoise="on"
start="%URLPARAM{start}%"
limit="%IF{"defined showall" then="0" else="%PERPAGE%"}%"
footer="%PAGINATION%"
}%
   * Set PERPAGE = %URLPARAM{"perpage" default="10"}%
   * Set START = %URLPARAM{"start" default="0"}%
   * Set PAGINATIONBODY = %IF{"%START% >= %PERPAGE%"
   then="[[%SCRIPTURLPATH{view}%/%WEB%/%BASETOPIC%?start=%CALCULATE{"$INT(%START% - %PERPAGE%)"}%%IF{"defined perpage" then=";perpage=%URLPARAM{perpage}%"}%][« Prev]]"
   else="« Prev"
   }%   %FORLOOP{"%RANGE{"%CALCULATE{"$INT((%DEFAULT% - 1) / %PERPAGE% + 1)"}%"}%"
   format="$percntIF{\"$percntCALCULATE{\"$INT(%URLPARAM{"start" default="0"}%/%PERPAGE%)\"}$percnt = $i\"
     then=\"*$iplus1*\"
     else=\"[[%SCRIPTURLPATH{view}%/%WEB%/%BASETOPIC%?start=$percntCALCULATE{\"$INT($i * %PERPAGE%)\"}$percnt%IF{"defined perpage" then=";perpage=%URLPARAM{perpage}%"}%][$iplus1]]\"}$percnt"
   separator="   "
   }% &nbsp; %IF{"%CALCULATE{"$INT(%START% + %PERPAGE%)"}% < %DEFAULT%"
   then="[[%SCRIPTURLPATH{view}%/%WEB%/%BASETOPIC%?start=%CALCULATE{"$INT(%START% + %PERPAGE%)"}%%IF{"defined perpage" then=";perpage=%URLPARAM{perpage}%"}%][Next &raquo;]]"
   else="Next &raquo;"
   }%
   * Set PAGINATION = %$percntIF{\"$tntopics > %PERPAGE% and not defined showall\" then=\"PAGINATIONBODY{\" else=\"HIDE{\"}$percnt \"$tntopics\"}%

-- HideyoImazu - 2012-11-08

I don't recommend using preferences settings because TWiki includes the WebSearch page content from the TWiki web.

I created a Sandbox.PaginationDemo that relies purely on CALCULATE. Here is the actual raw text of the search page, including «Prev   1   2   3   4   5   Next» before and after the search. Use this if you like:

<form action="%SCRIPTURL{view}%/%WEB%/%TOPIC%">
<input type="text" name="search" value="%URLPARAM{ "search" encode="html" }%" class="twikiInputField" size="40" />
<input type="submit" value="Search" class="twikiSubmit" />
</form>
%CALCULATE{$SET(start, %URLPARAM{ "start" default="1" }%)}%<!-- number of first hit -->
%CALCULATE{$SET(limit, %URLPARAM{ "limit" default="10" }%)}%<!-- entries per page -->
<div id="searchTopNav"></div>
%SEARCH{
 "%URLPARAM{ "search" encode="quote" }%"
 nonoise="on"
 start="%CALCULATE{$GET(start)}%"
 limit="%CALCULATE{$GET(limit)}%"
 nonoise="on"
 footer="$percntCALCULATE{$SET(max, $ntopics)}$percnt"
}%
%CALCULATE{$SET(prevText, $IF($INT($GET(start)-$GET(limit))>0, <a href="%SCRIPTURL{view}%/%WEB%/%TOPIC%?%URLPARAM{ "search" encode="url" }%;start=$INT($GET(start)-$GET(limit));limit=$GET(limit)">&laquo;Previous</a>, %GRAY% &laquo;Previous %ENDCOLOR%))$GET(prevText)}%
&nbsp;
%CALCULATE{$SET(stepsText,)$SET(pages, $INT(1+$GET(max)/$GET(limit)))$SET(i, 1)$WHILE($counter<=$GET(pages), $SET(stepsText, $GET(stepsText) $IF($GET(i)==$GET(start), &nbsp;<b>$counter</b>, &nbsp;<a href="%SCRIPTURL{view}%/%WEB%/%TOPIC%?%URLPARAM{ "search" encode="url" }%;start=$GET(i);limit=$GET(limit)">$counter</a>))$SETM(i, +$GET(limit)))$GET(stepsText)}%
&nbsp;
%CALCULATE{$SET(nextText, $IF($INT($GET(start)+$GET(limit))<=$GET(max), &nbsp;<a href="%SCRIPTURL{view}%/%WEB%/%TOPIC%?%URLPARAM{ "search" encode="url" }%;start=$INT($GET(start)+$GET(limit));limit=$GET(limit)">Next&raquo;</a>, %GRAY% &nbsp;Next&raquo; %ENDCOLOR%))$GET(nextText)}%
<script>
  $('#searchTopNav').html('%CALCULATE{$GET(prevText) &nbsp; $GET(stepsText) &nbsp; $GET(nextText)'}%);
</script>

In regards to FORLOOP and RANGE, they warrant new feature proposals if for core, or could be implemented as plugin(s).

-- PeterThoeny - 2012-11-08

start parameter is not getting applied in the following search query

 %SEARCH{search="parent.name='BugGR'" nosearch="on" start="5" limit="5" type="query" sort="modified" reverse="on"}% 

am I missing anything?

-- TWiki Guest - 2013-02-03

This is only available in SVN trunk version; it will be released later this year in the next major production release.

Masilamani, please register with your real first name and last name.

-- Peter Thoeny - 2013-02-03