Adaptive lazy merging
US8676865B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | May 20, 2008 |
| Grant date | Mar 18, 2014 |
| Priority date | — |
| Expiry date | Jun 30, 2031 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F16/9024
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A query processing method intersects two or more unsorted lists based on a conjunction of predicates. Each list comprises a union of multiple sorted segments. The method performs lazy segment merging and an adaptive n-ary intersecting process. The lazy segment merging comprises starting with each list being a union of completely unmerged segments, such that lookups into a given list involve separate lookups into each segment of the given list. The method intersects the lists according to the predicates while performing the lazy segment merging, such that the lazy segment merging reads in only those portions of each segment that are needed for the intersecting. As the intersecting proceeds and the lookups are performed, the intersecting selectively merges the segments together, based on a cost-benefit analysis of the cost of merging compared to the benefit produced by reducing a number of lookups.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.