Distinct value estimation for query planning
US10853368B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Apr 2, 2018 |
| Grant date | Dec 1, 2020 |
| Priority date | — |
| Expiry date | Jan 30, 2039 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F16/24549
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
The problem of distinct value estimation has many applications, but is particularly important in the field of database technology where such information is utilized by query planners to generate and optimize query plans. Introduced is a novel technique for estimating the number of distinct values in a given dataset without scanning all of the values in the dataset. In an example embodiment, the introduced technique includes gathering multiple intermediate probabilistic estimates based on varying samples of the dataset, 2) plotting the multiple intermediate probabilistic estimates against indications of sample size, 3) fitting a function to the plotted data points, and 4) determining an overall distinct value estimate by extrapolating the objective function to an estimated or known total number of values in the dataset.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.