Back to results
US 7,480,646 B2Granted
Type path indexing
AssigneeMicrosoft Corporation
InventorsConor J. Cunningham, Ramachandran Venkatesh, Eric N. Hanson
Life of this patent
Estimating the term…
Abstract
Efficient hierarchical searching is based on object type. By pre-computing additional information and storing it in a fast-lookup structure, it is possible to quickly identify objects that satisfy an object retrieval request. Furthermore, it is also possible to use this technique to avoid object hydration for operations in the store. Moreover, it is possible to leverage database statistical structures such as histograms to estimate the number of qualifying objects without having to examine each object.
Claims14
A computer system for processing a query, the computer system comprising:
- a processor;
- a memory;
- a data store comprising a table of documents and associated pre-computed values, the pre-computed values comprising information to discern objects based on type pursuant to a hierarchical search, each document having an associated document type in a hierarchy of document types, the document type associated with a document being used to compute a pre-computed value, wherein the pre-computed value is generated by concatenating type values of the document types along a path from a root document type to the document type associated with the document, and wherein the pre-computed value is compressed by separating the concatenated type values by a reserved separator byte;
- and
- a document retrieval system that accesses the table in the data store to determine, for each document, if the pre-computed value associated with said each document satisfies the query, generates query results comprising the pre-computed value that satisfies the query, wherein the document retrieval system generates an estimate of selectivity of the query at least in part by creating a histogram over the pre-computed values, the histogram having a plurality of elements representing document types in the hierarchy of document types, each element associated with a quantity of documents of the document type represented by said each element,
- encoding the query to describe one or more documents to retrieve based on an encoded query type,
- for each element of the histogram, determining whether the encoded query type is a prefix of the document type represented by said each element of the histogram,
- for said each element of the histogram which the encoded query type is determined to be a prefix of the document type represented by said each element of the histogram, adding an associated quantity to a sum of matching elements,
- for each element of the histogram which the encoded query type is determined not to be a prefix of the document type, adding the associated quantity to a sum of non-matching elements
- generating the estimate of the selectivity of the query as a function of the sums of matching elements and non-matching elements.
7 more elements
A computer-readable storage medium storing computer-executable instructions that executed, cause a computer system to process a query by:
- accessing a data store comprising a table of documents and associated pre-computed values, the associated pre-computed values comprising information used to discern objects based on type pursuant to a hierarchical search, each document in the table of documents having an associated document type in a hierarchy of document types, the associated document type being used to compute a pre-computed value associated with said each document, wherein the pre-computed value is generated by concatenating type values of the document types along a path from a root document type to the document type associated with the document, and wherein the pre-computed value is compressed by separating the concatenated type values by a reserved separator byte;
- determining, for each document, if the pre-computed value associated with said each document satisfies the query, generating query results comprising the pre-computed value that satisfies the query;
- generating an estimate of selectivity of the query at least in part by creating a histogram over the pre-computed values, the histogram having a plurality of elements representing document types in the hierarchy of document types;
- encoding the query to describe one or more documents to retrieve based on an encoded query type for each element associated with a quantity of documents of the document type represented by said each element,
- for each element of the histogram, determining whether the encoded query type is a prefix of the document type represented by said each element of the histogram,
- for said each element of the histogram which the encoded query type is determined to be a prefix of the document type represented by said each element of the histogram, adding an associated quantity to a sum of matching elements;
- for each element of the histogram which the encoded query type is determined not to be a prefix of the document type, adding the associated quantity to a sum of non-matching elements;
- and generating the estimate of the selectivity of the query as a function of the sums of matching elements and non-matching elements.
5 more elements
A computer implemented method for processing a query, the method comprising:
- accessing a data store comprising a table of documents and associated pre-computed values, the associated pre-computed values comprising information used to discern objects based on type pursuant to a hierarchical search, each document in the table of documents having an associated document type in a hierarchy of document types, the associated document type being used to compute a pre-computed value associated with said each document, wherein the pre-computed value is generated by concatenating type values of the document types along a path from a root document type to the document type associated with the document, and wherein the pre-computed value is compressed by separating the concatenated type values by a reserved separator byte;
- determining, for each document, if the pre-computed value associated with said each document satisfies the query, generating query results comprising the pre-computed value that satisfies the query;
- generating an estimate of selectivity of the query at least in part by creating a histogram over the pre-computed values, the histogram having a plurality of elements representing document types in the hierarchy of document types;
- encoding the query to describe one or more documents to retrieve based on an encoded query type for each element associated with a quantity of documents of the document type represented by said each element,
- for each element of the histogram, determining whether the encoded query type is a prefix of the document type represented by said each element of the histogram,
- for said each element of the histogram which the encoded query type is determined to be a prefix of the document type represented by said each element of the histogram, adding an associated quantity to a sum of matching elements;
- for each element of the histogram which the encoded query type is determined not to be a prefix of the document type, adding the associated quantity to a sum of non-matching elements;
- and
- generating the estimate of the selectivity of the query as a function of the sums of matching elements and non-matching elements.
6 more elements
Dependencies are inferred from the claim text.