Document id reordering is a well-known technique in web search for improving index compressibility and reducing query processing time. We explore and evaluate the benefits of document id reordering for large-scale e-Commerce search. We observe that many e-Commerce sites organize oferings according to an ontology (i.e. product category). We then present a simple extension to document-id reordering: ordering based on item category. Our results show that we not only achieve the expected index size reduction, but also achieve a latency reduction of over 20% (on average) per query.
The search engine plays an essential role in e-Commerce: it connects the user’s need with a set of relevant items based on a query. This is not a simple task, millions of queries per second need to be processed over possibly billions of items. Moreover, it is expected that every query will be executed in just a few hundred milliseconds.
In order to solve this problem, search engines are implemented
as large distributed systems where there is a limited budget in CPU
and memory that every machine can use. Any improvement in
eficiency could potentially be translated into a reduction in hardware,
networking, and operating costs. Tremendous research and
engineering eforts has gone into addressing performance challenges:
reduction of memory requirements by improving data
compression, reduction the CPU use by implementing early termination
techniques, and massively parallel execution engines are just a few
of the techniques that have been extensively studied in the past.
In this paper, we focus on one technique originally designed to
improve data compression and reduce the size of the data that is
loaded into main memory, document id reordering [
The inverted index is an old and simple, yet very eficient data
structure that is at the heart of most search engines and is used
to support various search tasks. From a collection of documents,
an inverted index stores for each unique term (or word) a list of
postings. Each posting stores pairs ⟨d, w(t , d)⟩, where d is a unique
document identifier (doc_id) and w(t , d) is a relevance measure of
the term t with respect to document d (often the number of times
term t occurs in document d). These posting lists can be extended to
store additional information such as the positions of the term within
the document. Posting lists are usually stored sorted by doc_id and
processed document at a time. To help with compression, doc_ids
are often stored diference encoded - the value stored in the list
is the diference (or d-gap) between this id and the preceding id.
These d-gaps are further compressed using a variable-width integer
codec such as variable byte encoding, PForDelta [
The final compression ratio depends on the number of bits required to represent the d-gaps, which depends on how the doc_ids are assigned to documents. If the d-gaps are small they compress better than if they are large. That is, if all the documents containing a given term have document ids that are close to each other then the index is smaller that if they are randomly distributed throughout the collection, simply because the d-gaps are smaller and so compress better.
This has motivated several authors in the past [
A popular e-Commerce search technique to improve precision is to constrain a query to a particular set of categories in a category tree. This can be done automatically by a trained classifier, or manually by the user. For example, the results of the query iphone case can be constrained so that all the resulting items belong to the category “Cell Phones & Accessories Cases, Covers & Skins”. These categories also form a natural partitions, clustering items according to popular search dimensions.
In this paper we explore a document id reordering technique for structured and categorized data that both improves compression and decreases query latency. Our results show that document id ordering on category substantially reduces the size of the index. It also reduces mean latency per query by 27% and 99th percentile latency by 45%. Latency improvements are seen both with and without category constraints applied. 2 2.1
Given a collection D = {d1, d2, . . . , dD } of text documents, a document di can be considered to be a sequence of terms (or words), the number of words, and an unique document identifier (doc_id) ∈ [1, D]. The number of words in a document is represented by |di |, and the total number of words in the collection is then ÍD i=1 |di | = n.
An inverted index maintains the set of distinct terms of the collection (the vocabulary), which in most cases is small compared to the total number of words contained in the collection. More precisely, it is of size O(nβ ), for 0 < β < 1 depending on the text type (β is normally small).
For every distinct word, the inverted index stores a list of postings. Each posting stores the document identifier (doc_id), the weight of the term in the document w(t , d) and, if needed, the positions of the term within the document. The weight w(t , d) of term t in d is a utility function that represents the importance of that word inside the document. That utility function is often just the number of times the term occurs in the document – the term frequency.
There are many diferent ways to encode posting lists including term-frequency ordered, impact ordered, and so on, but the most common way appears to be ordering on increasing document id. Either way, in order to improve eficiency the inverted index is typically loaded into main memory when the search engine starts up, and parts of it are compressed in order to reduce the memory footprint.
The weights are hard to compress and usually small so they are often stored uncompressed in a fixed number of bytes (often 1). The document ids, however have been the subject of much research.
The list of doc_ids ⟨d1, d2, d3, . . . dn ⟩, is a strictly monotonically increasing sequence. These integers can be decreased in size by calculating the diferences between each document id and the preceding document id, resulting in a list of d-gaps ⟨d1, d2 − d1, d3 − d2, . . . , dn − dn−1⟩. The list of d-gaps is then encoded using a variable-length encoding scheme.
Bit-aligned codes were used in the past, but proved to be
inefifcient when decoding. Byte-aligned codes [
Merging lists can be done by traversing the lists from the start to ifnish, but in order to support more complicated query processing techniques random access to postings in a list is needed. A recent approach is postings list encoding using Elias-Fano, but a more common approach is the use of skip-lists.
A skip-list for a postings list is generated by dividing the postings
list into blocks. Each block starts with a given doc-id and is at a
given ofset from the start of the postings list. These ⟨doc-id, ofset ⟩
tuples provide entry points into the postings [
To implement random access to a posting, a binary search is performed on the skip list, then the appropriate block is decompressed and searched linearly. 2.2
Query processing involves a number of processes such as query
parsing, query rewriting and the computation of complex
machinelearned ranking functions that may include hundreds or thousands
of features derived from the documents, the query, and the user. To
rank eficiently, it is common to separate the query processing into
multiple stages. The first stage is responsible for identifying which
documents must be ranked and the subsequent stages rank those
documents. In the first phase, a simple and fast retrieval filtering
such as WAND [
A conjunctive Boolean query of the form “Last AND Jedi”
requires an intersection calculation, whereas a disjunctive query of
the form “Episode OR VIII ” requires a union calculation. Union
queries are solved by linearly traversing all postings lists for all
terms in the expression and returning all documents containing
either term. Eficiently resolving intersection queries requires
complicated traversal of the postings lists and has been examined for
decades [
In the second and subsequent phases, an increasingly expensive set of ranking functions is used to identify the most relevant documents. Each stage provides to the next stage a better ranking of the recall set, but also reduces the number of documents that are ranked (each time the top-k, for decreasing k, are re-ranked). The ifnal stage might just rank the top-10 using thousands of features derived from the document, the query, meta-data (the price), and a user profile (for e-Commerce, a buyer profile and a seller profile).
In general, improving the eficiency of the first stage frees more resources for the subsequent stages, and thus increases the overall performance of the search engine. 2.3
Document reordering is a well studied technique in web search
[
Yan et al. [
Our approach is motivated by the work of Silvestri [
E-Commerce search is a much more structured and constrained scenario than web search. In e-Commerce, much of the document content is given by the item properties such as price, brand, model, category, color, and so on. It is natural to consider these features as ifltering components of a search and it is consequently common practice to generate posting lists for those kind of features. For example, by generating posting lists for each instance of the feature “brand” (i.e brand:apple, brand:samsung, etc) the user can easily constrain their search to just the items made by a given manufacturer – and indeed they expect to be able to do so.
Category is a particularly interesting property of e-Commerce items (and queries), because it is not only used to divide the inventory into distinct types of products but it is also commonly used to improve the precision of the results. Given an user query, the search engine can constrain the results to just those from the most relevant category. This can be done in an automatic way by training query to category classifiers, or by allowing the user to manually select a category. Figure 1 shows an example user query “star wars” being constrained to the category “art” on eBay.com.
If the search engine creates posting lists for each category, the ifrst stage of query processing can be improved significantly, since it can perform a direct boolean intersection between the (possibly term expanded) user query and the posting list for the given category. Since this cuts down the size of the recall base it increases the eficiency of the search engine, but since it restricts to the most likely category it also removes noise from the results list so increases precision. And this is the motivation for document id reordering based on item category.
We re-order the collection so that the doc_ids are assigned in such a way that items belonging to the same category are given contiguous doc_ids. This reduces the size of the d-gaps in posting lists which leads to better compression. However, this is not the only benefit, since posting lists are sorted by doc_id, it creates implicit category “divisions” within each posting list.
Figure 2 illustrates this. On the top left, the collection of documents is shown in “collection order”, where the distinct shades of gray represent diferent categories. The top right gives example posting lists for words (w1, w2, w3). The bottom left of the figure shows the collection category reordered where, for example, collection ordered d2 becomes category ordered d3. The bottom right shows the efect of document reordering on the posting lists, they are now implicitly divided by category.
This document reordering scheme not only helps compression, but also decreases latency: as the d-gaps are smaller the decompression of the integers is faster since, in general, a smaller number of operations is required to decode a smaller integer. Equally, since similar documents are stored together, fewer accesses to the skip-lists are needed. It is obvious that when a query is category constrained the results must lie within a consecutive part of the postings list.
Distribution of Log2(d−gaps) 30 s20 p a g − d f o e g a t n e c r o10 P
Since compression improvements will depend on the d-gaps values, we first analyzed the diferences in the distribution of the d-gaps between random doc_id assignment and category-based doc_id assignment. Figure 3 shows on a log-linear scale the distribution
Avg. log2(d-gaps) 5.73 4.11 -28% d-gaps = 1 890 × 106 1, 510 × 106 +70% Avg. d-gaps 1966 639 -67.5% Avg. Bytes/d-gap (vByte) 1.30 1.22 -6.1% Index Size 29.67 GB 28.72 GB -3.2% Table 1: Space savings and bits per d-gap obtained before and after applying document reordering. of g-gaps. The x-axis is ⌈log2(дapsize)⌉ while the y-axis is the percentage of d-gaps of that size. It can be seen that the reordered distribution has many more d-gaps on the left – the reordered index has substantially more small d-gaps than the random index.
Table 1 presents a summary of the figure. It shows that the number of d-gaps equal to 1 has increased by 70%, that the average d-gap has decreased by 67.5%, and that the average number of bits required to represent d-gaps is reduced by 28%. In practice, the actual size reduction in the index will depend on the integer encoding scheme. For the purpose of this paper, we constructed a special index that uses variable byte encoding to compress doc_ids. We see a reduction of 6.1% in the average number of bytes required to represent a doc_id using this encoding scheme, while this represents a 3.2% space reduction of the complete index. 4.3
In order to evaluate the improvement of query processing, we executed two sets of experiments with the two diferent query sets.
The first experiment considered throughput using the General Queries – that is, its a mirror of the production environment. We computed the average number of queries per second (QPS) that could be resolved when the CPU was held at 80% utilization (the other 20% is used in eBay for processes such as index maintenance). We found that on average the Reordered Index could process about about 30% more queries per second than the Random Index.
Table 2 shows the average search time per query (in milliseconds) at the mean, median, 95th percentile and 99th percentile. In all cases we see a substantial improvement, the mean latency improved by 26.9% while 95th percentile latency is almost halved when compared to the random document Reordering.
Mean 22.43 16.4 26.9% Median 4.35 3.21 28.3% 95th Pct. 57 30.2 47% 99th Pct. 375 224 40% Table 2: Comparison of random doc_id assignment versus category doc_id reordering. Mean, median, 95th and 99th percentiles of query processing times in milliseconds for general queries.
For the second experiment, with user queries, we evaluated the impact of document reordering depending on the recall set size (as output by the first stage of the search process) and the latency before ranking and after ranking. The results are presented in figure 4. The blue plus signs represent the Reordered Index, while the red triangles represent the Random Index. On the left we show the impact post ranking, where it can be seen that the largest latency improvements are obtained when the queries generate a large set of results. On the right we show the recall versus latency results when ranking is disabled, in other words, just recall identification. It can be seen that there is a strict boundary at the bottom, and there is no significant improvement for the queries that are located within that boundary. Latency improvements can be seen overall, but are large for expensive queries.
We also evaluated the impact of applying category constrains to the queries. The results are shown in table 3. The left side shows the latency (in milliseconds) when category constraint is not used. In this case the Reordered index improved mean query latency by 47% and the 95th percentile by 41%. The right shows the efect of enabling category constrain on the queries. There the mean query latency has reduced by 55% when the Reordered Index is used, and a similar efect is observed for the 95th percentile. Clearly both unconstrained and category constrained queries are materially improved. 4.4
Categories naturally cluster both document terms and query terms. Items satisfying a multi-term AND query will tend to come from a small number of categories. Ordering posting lists by category will put documents satisfying these queries near each other both in posting lists and in the forward index. This should improve CPU cache hit rates and even improve the inherent eficiency of the posting list processing algorithms. The latter efect would result from having larger clusters of posting list entries that are either matched or skipped than in a random assignment of the documents.
Query expansion is likely to compound these efects, especially in an e-Commerce environment. As in most search engines, we make extensive use of query expansion to improve recall and precision. Rewritten queries often form a complex Boolean expression involving many posting lists and nested AND / OR constructs. Expansions involve not only text keywords, but also the structured meta-data associated with products. For example, the term “black” may expand to “color:black” and “samsung” to “brand:samsung”.
To examine these efects we used the CPU usage profiling tool perf, while processing a portion of a General Queries collection, to analyze and identify the exact locations where the improvement was more noticeable. We observed the functions performing the task of iterating (and skipping) through posting lists was consuming about 5% of the total CPU time, and we observed a noticeable improvement especially in these parts. We also saw improvements in the doc_id variable byte decoding section. Finally we analyzed the efect of how cache misses were afected by the document reordered index. We observed a 7% reduction in overall cache misses and a 13% reduction in last-level cache misses (LLC). These numbers show that that document ordering by category yielded a significant improvement in overall CPU cache hit rates. These numbers are consistent with our hypothesis for the improvements in latency. Additional analysis is still needed to quantify the efects on posting listing processing.
The probability that any given cluster of posting list entries will be referenced by a query is far from uniform in the General Queries collection, and more likely following something like a zipfian curve. This should reduce the number of CPU cache entries iflled with posting list data during processing of a query, and thus reducing the CPU cache worked set size for the portion of query processing dedicated to processing posting lists. The reduction in CPU cache working set size for posting lists allows a larger amount of CPU cache to be used for other functions performing query processing work, which improves the CPU cache hit rate for those other functions.
The above discussion focuses on the recall component of query processing. As mentioned earlier, document reordering also better co-locates forward index data for items satisfying the recall expression for a query. Forward index data is used extensively in the ranking component of query processing. As such, this is also has potential to improve CPU cache hit rates. We have not measured this efect directly, but it is consistent with the results shown in ifgure 4. These graphs show a latency improvement from ranking beyond the improvement from recall processing alone. 5
We presented a simple, yet eficient, document reordering technique that takes advantage of structured component from the queries and the data. This is particularly common in e-Commerce search engines. We showed that by performing this simple re-arrangement of the doc_ids we can improve the capacity of the system by 30%, and process category-constrained queries in about half the time that it took without the re-arrangement.
As future work, we plan to add more document reordering criteria to other dimensions such as item aspects like color, brand and also the location of the item by ordering by country, another important task is to measure the behavior of the cache in this scenario. We also plan to perform a deeper analysis and quantification of the latency improvements seen in both boolean only queries and when ranking is enabled. A topic for future study is whether there is a material diference between these two cases when considering per-document latency benefits. The current analysis is insuficient to answer this question.