Patent ID: 8676865

Claim:
A computer-implemented query processing method comprising: receiving a query into a computing device, said query containing predicates identifying constraints on said query; identifying, by said computing device, lists of values comprising data satisfying a predicate of said query, each list of values comprising one or more segments, each segment comprising an ordered group of elements; forming, by said computing device, a list of page numbers of leaf pages associated with said lists of values; forming, by said computing device, an array of highest row identifications (RIDs) for each leaf page; performing, by said computing device, lazy segment merging of two or more lists of values, said lazy segment merging starting with each list of values being a union of completely unmerged segments, such that lookups into a given list of values involve separate lookups into each segment of said given list of values, said lazy segment merging comprising merging only ones of said segments having index leaf pages that possibly contain RIDs corresponding to a predicate, based on said array of highest RIDs; intersecting, by said computing device, portions of said lists of values, according to a conjunction of said predicates, while performing said lazy segment merging, such that said lazy segment merging reads in only those portions of each segment that contain RIDs for said intersecting, said intersecting comprising an adaptive n-ary intersection process that dynamically varies which leg to process based on relative density of RIDs within said lists of values, said intersecting comprising separately intersecting each segment of a list having a row identification (RID) corresponding to a predicate; and outputting, by said computing device, intersections of said portions of said lists when each of said portions contains a matching RID.