JEP-0059: Result Set Management

This document defines an XMPP protocol extension to enable entities to page through and otherwise manage the receipt of large result sets.

WARNING: This Standards-Track JEP is Experimental. Publication as a Jabber Enhancement Proposal does not imply approval of this proposal by the Jabber Software Foundation. Implementation of the protocol described herein is encouraged in exploratory implementations, but production systems should not deploy implementations of this protocol until it advances to a status of Draft.

JEP Information

Author Information

Legal Notice

Discussion Venue

Relation to XMPP

The Extensible Messaging and Presence Protocol (XMPP) is defined in the XMPP Core (RFC 3920) and XMPP IM (RFC 3921) specifications contributed by the Jabber Software Foundation to the Internet Standards Process, which is managed by the Internet Engineering Task Force in accordance with RFC 2026. Any protocol defined in this JEP has been developed outside the Internet Standards Process and is to be understood as an extension to XMPP rather than as an evolution, development, or modification of XMPP itself.

Conformance Terms

The following keywords as used in this document are to be interpreted as described in RFC 2119: "MUST", "SHALL", "REQUIRED"; "MUST NOT", "SHALL NOT"; "SHOULD", "RECOMMENDED"; "SHOULD NOT", "NOT RECOMMENDED"; "MAY", "OPTIONAL".

1. Introduction
2. Use Cases
3. Examples
4. Determining Support
5. Security Considerations
6. IANA Considerations
7. Jabber Registrar Considerations
8. XML Schema
9. Acknowledgements
Notes
Revision History

1. Introduction

In Jabber Search [1], Service Discovery [2], Publish-Subscribe [3], Message Archiving [4], and perhaps other future XMPP extensions, it is possible to receive large result sets in response to information requests (e.g., a user directory search on a common first name or a service discovery items request sent to a Multi-User Chat [5] service). Thus it would be helpful to define an XMPP protocol extension that enables the following functionality:

2. Use Cases

2.1 Getting the Item Count

In order to get the item count of a result set without retrieving the items themselves, the requesting entity specifies a request type of "count":

Example 1. Requesting the Item Count

<iq type='get' from='stpeter@jabber.org/roundabout' to='users.jabber.org' id='count1'>
  <query xmlns='jabber:iq:search'>
    <nick>Peter</first>
    <count xmlns='http://jabber.org/protocol/rsm'/>
  </query>
</iq>

The responding entity then returns the item count, which MAY be approximate rather than precise (since determining the exact number of items may be resource-intensive):

Example 2. Returning the Item Count

<iq type='result' from='users.jabber.org' to='stpeter@jabber.org/roundabout' id='count1'>
  <query xmlns='jabber:iq:search'>
    <count xmlns='http://jabber.org/protocol/rsm'>800</count>
  </query>
</iq>

If there are no items in the full result set, the responding entity MUST return a response that adheres to the definition of the wrapper protocol (e.g., "jabber:iq:search", "http://jabber.org/protocol/disco#items", or "http://jabber.org/protocol/pubsub"). For both JEP-0055 and JEP-0030, that means the responding entity shall return an empty <query/> element; for JEP-0060, that means the responding entity shall return an empty <pubsub/> element.

2.2 Limiting the Size of a Result Set

In order to limit the number of items to be returned in a result set, the requesting entity specifies a request type of "set" and the maximum size of the desired result set (via XML character data of the <max/> element):

Example 3. Requesting a Limit to the Result Set

<iq type='get' from='stpeter@jabber.org/roundabout' to='users.jabber.org' id='limit1'>
  <query xmlns='jabber:iq:search'>
    <nick>Pete</nick>
    <set xmlns='http://jabber.org/protocol/rsm'>
      <max>10</max>
    </set>
  </query>
</iq>

The responding entity then returns a result set limited to the requested size:

Example 4. Returning a Limited Result Set

<iq type='result' from='users.jabber.org' to='stpeter@jabber.org/roundabout' id='limit1'>
  <query xmlns='jabber:iq:search'>
    <item jid='stpeter@jabber.org'>
      <first>Peter</first>
      <last>Saint-Andre</last>
      <nick>Pete</nick>
    </item>
    .
    [8 more items]
    .
    <item jid='peterpan@neverland.lit'>
      <first>Peter</first>
      <last>Pan</last>
      <nick>Pete</nick>
    </item>
  </query>
</iq>

2.3 Paging Forwards Through a Result Set

Note: The set of items that match a query MAY change over time, even during the time that a requesting entity pages through a result set (e.g., a set of chatrooms, since rooms can be created and destroyed at any time). The paging protocol outlined in this section is designed to make the following features possible:

Each result page is up-to-date at the time it is sent (not just at the time the first page was sent).
No items will be omitted from pages not yet sent (even if, after earlier pages were sent, some of the items they contained were removed from the set).
When paging through the list in order, duplicate items are never received.
Responding entity maintains no state (or a single minimal state for all requestors containing the positions of all recently deleted items).
Rapid calculation of which items should appear on a requested page by responding entity (even for large result sets).

Note: If a responding entity implements dynamic result sets then receiving entities paging through the complete result set should be aware that it may not correspond to the result set as it existed at any one point in time.

The request for the first page is the same as when Limiting the Size of a Result Set:

Example 5. Requesting the First Page of a Result Set

<iq type='get' from='stpeter@jabber.org/roundabout' to='users.jabber.org' id='page1'>
  <query xmlns='jabber:iq:search'>
    <nick>Pete</nick>
    <set xmlns='http://jabber.org/protocol/rsm'>
      <max>10</max>
    </set>
  </query>
</iq>

Responding entity support for paging through a result set is optional. If it does support paging (not just Limiting the Size of a Result Set), then in each result set it returns, the responding entity MUST include <first/> and <last/> elements that specify the unique ID (UID) for the first and last items in the page. If there is only one item in the page the first and last UIDs MUST be the same. If there are no items in the page then the <first/> and <last/> elements MUST NOT be included.

The responding entity may generate these UIDs in any way, as long as the UIDs are unique in the context of all possible members of the full result set. Each UID MAY be based on part of the content of its associated item, as shown below, or on an internal table index. Another possible method is to serialize the XML of the item and then hash it to generate the UID. Note: The requesting entity MUST treat all UIDs as opaque.

The responding entity MUST also include the number of items in the full set (which MAY be approximate) encapsulated in a <count/> element.

The <first/> element MUST include an 'index' attribute. This integer specifies the position within the full set (which MAY be approximate) of the first item in the page. If that item is the first in the full set then the index MUST be '0'. If the last item in the page is the last item in the full set then the index MUST equal the specified count minus the number of items in the page.

Example 6. Returning the First Page of a Result Set

<iq type='result' from='users.jabber.org' to='stpeter@jabber.org/roundabout' id='page1'>
  <query xmlns='jabber:iq:search'>
    <item jid='stpeter@jabber.org'>
      <first>Peter</first>
      <last>Saint-Andre</last>
      <nick>Pete</nick>
    </item>
    .
    [8 more items]
    .
    <item jid='peterpan@neverland.lit'>
      <first>Peter</first>
      <last>Pan</last>
      <nick>Pete</nick>
    </item>
    <set xmlns='http://jabber.org/protocol/rsm'>
      <first index='0'>stpeter@jabber.org</first>
      <last>peterpan@neverland.lit</last>
      <count>800</count>
    </set>
  </query>
</iq>

The requesting entity can then ask for the next page in the result set by including in its request the UID of the last item from the previous page (encapsulated in an <after/> element), and the maximum number of items to return. Note: if no <after/> element is specified then the UID defaults to "before the first item in the result set".

Example 7. Requesting the Second Page of a Result Set

<iq type='get' from='stpeter@jabber.org/roundabout' to='users.jabber.org' id='page2'>
  <query xmlns='jabber:iq:search'>
    <nick>Pete</nick>
    <set xmlns='http://jabber.org/protocol/rsm'>
      <max>10</max>
      <after>peterpan@neverland.lit</after>
    </set>
  </query>
</iq>

The first item in the page returned by the responding entity MUST be the item that immediately follows the item that the requesting entity indicated it has already received:

Example 8. Returning the Second Page of a Result Set

<iq type='result' from='users.jabber.org' to='stpeter@jabber.org/roundabout' id='page2'>
  <query xmlns='jabber:iq:search'>
    <item jid='peter@pixyland.org'>
      <first>Peter</first>
      <last>Pan</last>
      <nick>Pete</nick>
    </item>
    .
    [8 more items]
    .
    <item jid='peter@rabbit.lit'>
      <first>Peter</first>
      <last>Rabbit</last>
      <nick>Pete</nick>
    </item>
    <set xmlns='http://jabber.org/protocol/rsm'>
      <first index='10'>peter@pixyland.org</first>
      <last>peter@rabbit.lit</last>
      <count>800</count>
    </set>
  </query>
</iq>

It may sometimes be necessary to return an empty page to the requesting entity. For example, with dynamic result sets, the responding entity MAY delete some items from the full result set between requests. Note: If there are no items in the full result set then the responding entity MUST return a response that adheres to the definition of the wrapper protocol (see Getting the Item Count).

Example 9. Returning an Empty Page

<iq type='result' from='users.jabber.org' to='stpeter@jabber.org/roundabout' id='page80'>
  <query xmlns='jabber:iq:search'>
    <set xmlns='http://jabber.org/protocol/rsm'>
      <count>790</count>
    </set>
  </query>
</iq>

2.4 Paging Backwards Through a Result Set

The requesting entity MAY ask for the previous page in a result set by including in its request the UID of the first item from the page that has already been received (encapsulated in a <before/> element), and the maximum number of items to return.

Example 10. Requesting the Previous Page of a Result Set

<iq type='get' from='stpeter@jabber.org/roundabout' to='users.jabber.org' id='back1'>
  <query xmlns='jabber:iq:search'>
    <nick>Pete</nick>
    <set xmlns='http://jabber.org/protocol/rsm'>
      <max>10</max>
      <before>peter@pixyland.org</before>
    </set>
  </query>
</iq>

The last item in the page returned by the responding entity MUST be the item that immediately preceeds the item that the requesting entity indicated it has already received:

Example 11. Returning the Previous Page of a Result Set

<iq type='result' from='users.jabber.org' to='stpeter@jabber.org/roundabout' id='back1'>
  <query xmlns='jabber:iq:search'>
    <item jid='stpeter@jabber.org'>
      <first>Peter</first>
      <last>Saint-Andre</last>
      <nick>Pete</nick>
    </item>
    .
    [8 more items]
    .
    <item jid='peterpan@neverland.lit'>
      <first>Peter</first>
      <last>Pan</last>
      <nick>Pete</nick>
    </item>
    <set xmlns='http://jabber.org/protocol/rsm'>
      <first index='0'>stpeter@jabber.org</first>
      <last>peterpan@neverland.lit</last>
      <count>800</count>
    </set>
  </query>
</iq>

2.5 Page Not Found

The responding entity MUST reply with an 'item-not-found' error if all the following circumstances apply:

The item specified by the requesting entity via the UID in the <after/> or <before/> element no longer exists (it was deleted after the previous page was sent)
The UID itself cannot be used to derive directly the next item within the set (e.g. the alphabetical or numerical order of the UIDs do not specify the order of the items)
The responding entity does not remember the position of the deleted item within the full list. (Even if the responding entity bothers to remember the position of each deleted item, it will typically be necessary to expire that 'state' after an implementation-specific period of time.)

Example 12. Returning a Page-not-Found Error

<iq type='error' from='users.jabber.org' to='stpeter@jabber.org/roundabout' id='page2'>
  <query xmlns='jabber:iq:search'>
    <nick>Pete</nick>
    <set xmlns='http://jabber.org/protocol/rsm'>
      <max>10</max>
      <after>peterpan@neverland.lit</after>
    </set>
  </query>
  <error type='cancel'>
    <item-not-found xmlns='urn:ietf:params:xml:ns:xmpp-stanzas'/>
  </error>
</iq>

2.6 Requesting the Last Page in a Result Set

The requesting entity MAY ask for the last page in a result set by including in its request an empty <before/> element, and the maximum number of items to return.

Example 13. Requesting the Last Page of a Result Set

<iq type='get' from='stpeter@jabber.org/roundabout' to='users.jabber.org' id='page1'>
  <query xmlns='jabber:iq:search'>
    <nick>Pete</nick>
    <set xmlns='http://jabber.org/protocol/rsm'>
      <max>10</max>
      <before/>
    </set>
  </query>
</iq>

2.7 Retrieving a Page Out of Order

The requesting entity MAY choose not to retrieve pages from the result set in order. (For example, when its user drags the user interface slider to a radically new position within a very large result set.)

If the UID before the start (or after the end) of a desired result set page is not known, then the requesting entity MAY request the page that starts at a particular index within the result set by including in its request the index of the first item (encapsulated in an <index/> element), and the maximum number of items to return.

Example 14. Requesting a Result Page by Index

<iq type='get' from='stpeter@jabber.org/roundabout' to='users.jabber.org' id='index10'>
  <query xmlns='jabber:iq:search'>
    <nick>Pete</nick>
    <set xmlns='http://jabber.org/protocol/rsm'>
      <max>10</max>
      <index>10</index>
    </set>
  </query>
</iq>

The responding entity MUST derive the first UID from the specified index (the method used MAY be approximate), before returning the requested result set page in the normal way. Note: The 'index' attribute of the <first/> element MUST be the same as the index specified in the request. If the index specified by the requesting entity is greater than or equal to the number of items in the full set then the responding entity MUST return an empty page (see Paging Forwards Through a Result Set).

Example 15. Returning a Result Page at an Index

<iq type='result' from='users.jabber.org' to='stpeter@jabber.org/roundabout' id='index10'>
  <query xmlns='jabber:iq:search'>
    <item jid='peter@pixyland.org'>
      <first>Peter</first>
      <last>Pan</last>
      <nick>Pete</nick>
    </item>
    .
    [8 more items]
    .
    <item jid='peter@rabbit.lit'>
      <first>Peter</first>
      <last>Rabbit</last>
      <nick>Pete</nick>
    </item>
    <set xmlns='http://jabber.org/protocol/rsm'>
      <first index='10'>peter@pixyland.org</first>
      <last>peter@rabbit.lit</last>
      <count>800</count>
    </set>
  </query>
</iq>

3. Examples

The foregoing examples show the use of result set management in the context of Jabber Search.. Therefore in the following examples we show the use of result set management in the context of Service Discovery. A future version of this document may also include examples from Publish-Subscribe and Message Archiving and other XMPP protocol extensions.

<iq type='get' from='stpeter@jabber.org/roundabout' to='conference.jabber.org' id='ex1'>
  <query xmlns='http://jabber.org/protocol/disco#items'>
    <count xmlns='http://jabber.org/protocol/rsm'/>
  </query>
</iq>

<iq type='result' from='conference.jabber.org' to='stpeter@jabber.org/roundabout' id='ex1'>
  <query xmlns='http://jabber.org/protocol/disco#items'>
    <count xmlns='http://jabber.org/protocol/rsm'>150</count>
  </query>
</iq>

<iq type='get' from='stpeter@jabber.org/roundabout' to='conference.jabber.org' id='ex2'>
  <query xmlns='http://jabber.org/protocol/disco#items'>
    <set xmlns='http://jabber.org/protocol/rsm'>
      <max>20</max>
    </set>
  </query>
</iq>

<iq type='result' from='conference.jabber.org' to='stpeter@jabber.org/roundabout' id='ex2'>
  <query xmlns='http://jabber.org/protocol/disco#items'>
    <item jid='12@conference.jabber.org'/>
    <item jid='adium@conference.jabber.org'/>
    <item jid='airhitch@conference.jabber.org'/>
    <item jid='alphaville@conference.jabber.org'/>
    <item jid='apache@conference.jabber.org'/>
    <item jid='argia@conference.jabber.org'/>
    <item jid='armagetron@conference.jabber.org'/>
    <item jid='atticroom123@conference.jabber.org'/>
    <item jid='banquise@conference.jabber.org'/>
    <item jid='bar_paradise@conference.jabber.org'/>
    <item jid='beer@conference.jabber.org'/>
    <item jid='blondie@conference.jabber.org'/>
    <item jid='bpnops@conference.jabber.org'/>
    <item jid='brasileiros@conference.jabber.org'/>
    <item jid='bulgaria@conference.jabber.org'/>
    <item jid='cantinalivre@conference.jabber.org'/>
    <item jid='casablanca@conference.jabber.org'/>
    <item jid='chinortpcrew@conference.jabber.org'/>
    <item jid='coffeetalk@conference.jabber.org'/>
    <item jid='council@conference.jabber.org'/>
    <set xmlns='http://jabber.org/protocol/rsm'>
      <first index='0'>acc3594e844c77696f7a7ba9367ae324b6b958ad</first>
      <last>4da91d4b330112f683dddaebf93180b1bd25e95f</last>
      <count>150</count>
    </set>
  </query>
</iq>

<iq type='get' from='stpeter@jabber.org/roundabout' to='conference.jabber.org' id='ex3'>
  <query xmlns='http://jabber.org/protocol/disco#items'>
    <set xmlns='http://jabber.org/protocol/rsm'>
      <max>20</max>
      <after>4da91d4b330112f683dddaebf93180b1bd25e95f</after>
    </set>
  </query>
</iq>

4. Determining Support

In order for a requesting entity to determine if a responding entity supports result set management, it SHOULD send a Service Discovery information request to the responding entity:

Example 21. Requesting entity queries responding entity regarding protocol support

<iq from='stpeter@jabber.org/roundabout'
    to='conference.jabber.org'
    id='disco1'>
  <query xmlns='http://jabber.org/protocol/disco#info'/>
</iq>

<iq from='conference.jabber.org'
    to='stpeter@jabber.org/roundabout'
    id='disco1'>
  <query xmlns='http://jabber.org/protocol/disco#info'>
    ...
    <feature var='http://jabber.org/protocol/rsm'/>
    ...
  </query>
</iq>

A requesting entity SHOULD NOT include result set management extensions if it does not have positive knowledge that the responding entity supports the protocol defined herein. If the responding entity does not understand result set management, it MUST ignore the extension.

Note: Even if a responding entity understands the result set management protocol, its support for result set management in the context of any given using protocol is OPTIONAL (e.g., an implementation could support it in the context of the 'jabber:iq:search' namespace but not in the context of the 'http://jabber.org/protocol/disco#items' namespace). Currently the only way for a requesting entity to determine if a responding entity supports result set management in the context of a given using protocol is to include result set management extensions in its request. If the responding entity does not include result set management extensions in its response, then the requesting entity SHOULD NOT include such extensions in future requests wrapped by the using protocol namespace.

5. Security Considerations

Security considerations are the responsibility of the using ("wrapper") protocol, such as JEP-0030 for the 'http://jabber.org/protocol/disco#items' namespace and JEP-0055 for the 'jabber:iq:search' namespace.

6. IANA Considerations

This JEP requires no interaction with the Internet Assigned Numbers Authority (IANA) [6].

7. Jabber Registrar Considerations

7.1 Protocol Namespaces

The Jabber Registrar [7] shall include 'http://jabber.org/protocol/rsm' in its registry of protocol namespaces.

8. XML Schema

<?xml version='1.0' encoding='UTF-8'?>

<xs:schema
    xmlns:xs='http://www.w3.org/2001/XMLSchema'
    targetNamespace='http://jabber.org/protocol/rsm'
    xmlns='http://jabber.org/protocol/rsm'
    elementFormDefault='qualified'>

  <xs:element name='set'>
    <xs:complexType>
      <xs:sequence>
        <xs:element name='after' type='xs:string' minOccurs='0' maxOccurs='1'/>
        <xs:element name='before' type='xs:string' minOccurs='0' maxOccurs='1'/>
        <xs:element ref='count' minOccurs='0' maxOccurs='1'/>
        <xs:element ref='first' minOccurs='0' maxOccurs='1'/>
        <xs:element name='index' type='xs:int' minOccurs='0' maxOccurs='1'/>
        <xs:element name='last' type='xs:string' minOccurs='0' maxOccurs='1'/>
        <xs:element name='max' type='xs:int' minOccurs='0' maxOccurs='1'/>
      </xs:sequence>
    </xs:complexType>
  </xs:element>

  <xs:element name='count' type='xs:int'/>

  <xs:element name='first'>
    <xs:complexType>
      <xs:simpleContent>
        <xs:extension base='xs:string'>
          <xs:attribute name='index' type='xs:int' use='required'/>
        </xs:extension>
      </xs:simpleContent>
    </xs:complexType>
  </xs:element>

</xs:schema>

9. Acknowledgements

Notes

1. JEP-0055: Jabber Search <http://www.jabber.org/jeps/jep-0055.html>.

2. JEP-0030: Service Discovery <http://www.jabber.org/jeps/jep-0030.html>.

3. JEP-0060: Publish-Subscribe <http://www.jabber.org/jeps/jep-0060.html>.

4. JEP-0136: Message Archiving <http://www.jabber.org/jeps/jep-0136.html>.

5. JEP-0045: Multi-User Chat <http://www.jabber.org/jeps/jep-0045.html>.

6. The Internet Assigned Numbers Authority (IANA) is the central coordinator for the assignment of unique parameter values for Internet protocols, such as port numbers and URI schemes. For further information, see <http://www.iana.org/>.

7. The Jabber Registrar maintains a list of reserved Jabber protocol namespaces as well as registries of parameters used in the context of protocols approved by the Jabber Software Foundation. For further information, see <http://www.jabber.org/registrar/>.

Revision History

Version 0.10 (2006-08-24)

Added 'before' and 'first' elements, specified how to return an empty page and how to request the last page, removed reverse order sets, added out-of-order page access.

(ip)

Version 0.9 (2006-08-23)

Eliminated static result sets, justified expanded and clarified dynamic result sets, added page-not-found error, described when minimal state is necessary, added reverse order sets.

(ip)

Version 0.8 (2006-08-22)

Added optional method for handling dynamic result sets.

(psa)

Version 0.7 (2006-08-10)

Updated implementation note to clarify handling of result sets (static vs. dynamic).

(psa)

Version 0.6 (2006-07-12)

Updated implementation note to clarify handling of result sets (static vs. dynamic).

(psa)

Version 0.5 (2006-05-02)

Clarified error handling, determination of support in the context of using protocols, and security considerations.

(psa)

Version 0.4 (2006-04-24)

Specified that an item count may be approximate; specified that an item count may be returned with a page of results.

(psa)

Version 0.3 (2006-04-21)

Added <end/> element to specify last result set; added service discovery information; added more examples.

(psa/vm)

Version 0.2 (2005-12-22)

Revived and renamed the JEP; modified syntax; added use case for getting number of items; defined XML schema.

(psa/vm)

Version 0.1 (2002-11-12)

Initial version.

(jls)

JEP-0059: Result Set Management

JEP Information

Author Information

Jean-Louis Seguineau

Peter Saint-Andre

Valerie Mercier

Ian Paterson

Legal Notice

Discussion Venue

Relation to XMPP

Conformance Terms

Table of Contents

1. Introduction

2. Use Cases

2.1 Getting the Item Count

2.2 Limiting the Size of a Result Set

2.3 Paging Forwards Through a Result Set

2.4 Paging Backwards Through a Result Set

2.5 Page Not Found

2.6 Requesting the Last Page in a Result Set

2.7 Retrieving a Page Out of Order

3. Examples

4. Determining Support

5. Security Considerations

6. IANA Considerations

7. Jabber Registrar Considerations

7.1 Protocol Namespaces

8. XML Schema

9. Acknowledgements

Notes

Revision History

Version 0.10 (2006-08-24)

Version 0.9 (2006-08-23)

Version 0.8 (2006-08-22)

Version 0.7 (2006-08-10)

Version 0.6 (2006-07-12)

Version 0.5 (2006-05-02)

Version 0.4 (2006-04-24)

Version 0.3 (2006-04-21)

Version 0.2 (2005-12-22)

Version 0.1 (2002-11-12)