Document sorting with bitmap indexes

A system comprising:

• a first one or more electronic devices to implement a data store in a provider network;
• and
• a second one or more electronic devices to implement a service in the provider network, the service including instructions that upon execution cause the service to:
• receive a request to sort a set of documents;
• obtain a bitmap that identifies the set of documents to be sorted;
• obtain an ordered set of sort bitmaps, each sort bitmap in the ordered set of sort bitmaps corresponding to a bit in an encoding of a data type to be sorted;
• obtain an indication of a last document on a page of sort results:
• perform an initial series of passes of bitwise operations with the ordered set of sort bitmaps to identify a pass that includes the last document as a result, wherein the initial series of passes skips operations associated with bitmaps of at least some character positions;
• perform, at an end of the initial series of passes, a series of passes of bitwise operations with the ordered set of sort bitmaps, each pass to identify a next document identifier to add to a sorted set of document identifiers by processing an initial bitmap with bitwise operations in order against at least a portion of the ordered set of sort bitmaps, and wherein the initial bitmap of a first pass in the series of passes is initialized with the obtained bitmap;
• and
• store the sorted set of document identifiers in the data store.

A computer-implemented method comprising:

• receiving a request to sort a set of documents;
• obtaining a bitmap that identifies the set of documents to be sorted;
• obtaining an ordered set of sort bitmaps, each sort bitmap in the ordered set of sort bitmaps corresponding to a bit in an encoding of a data type to be sorted;
• performing a series of passes of bitwise operations with the ordered set of sort bitmaps, each pass to identify a next document identifier to add to a sorted set of document identifiers by processing an initial bitmap with bitwise operations in order against at least a portion of the ordered set of sort bitmaps, and wherein the initial bitmap of a first pass in the series of passes is initialized with the obtained bitmap, wherein each bitwise operation within a pass generates an intermediate bitmap result, and further comprising, within a given pass:
• storing an intermediate bitmap result that preceded a next intermediate bitmap result with a removed document identifier;
• and
• storing an index of a sort bitmap used in a bitwise operation with the intermediate bitmap result;
• and
• storing the sorted set of document identifiers.