Patent ID: 7480646

Claim:
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.