Efficient predicate prefilter for high speed data analysis
US8051069B2 · kind B2 · utility
Assignee
Inventors
Key dates
| Filing date | Jan 2, 2008 |
| Grant date | Nov 1, 2011 |
| Priority date | — |
| Expiry date | Sep 7, 2028 |
Classification
- Technology area (CPC G)Physics
- CPC primaryG06F16/24568
- WIPO fieldComputer technology
- WIPO sectorElectrical engineering
Abstract
A method and system are disclosed for operating a high speed data stream management system which runs a query plan including a set of queries on a data feed in the form of a stream of tuples. A predicate prefilter is placed outside the query plan upstream of the set of queries, and includes predicates selected from those used by the queries. Predicates are selected for inclusion in the prefilter based on a cost heuristic, and predicates are combined into composites using a rectangle mapping heuristic. The prefilter evaluates the presence of individual and composite predicates in the tuples and returns a bit vector for each tuple with bits representing the presence or absence of predicates in the tuple. A bit signature is assigned to each query to represent the predicates related to that query, and a query is invoked when the tuple bit vector and the query bit signature are compatible.
Source: USPTO / EPO open patent data. Objective bibliographic and citation counts.