Patent ID: 7516117
Filing Date: 2009-04-07
Classification: G06F,Y10S

Abstract:
1. A computer implemented method for accelerating range queries using monotonic properties of non-monotonic functions, comprising: at least one processor for executing the steps of: mapping a base column x to an existing index on a column y that is correlated with column x through a piecewise monotonic function F(x); rewriting an index construction statement to force the existing index on column y to track a piecewise monotonic property by assigning identical values of F(x) to different periods to different ranges to create an annotated index; rewriting range queries over the annotated index on F(x) by modifying a derived predicate, constructing said existing index; wherein said constructing said existing index comprises: recognizing said piecewise monotonic function and a periodicity of said piecewise monotonic function; and building an index over the monotonic function, wherein said recognizing said piecewise monotonic function is accomplished from explicit user input, recognizing semantically that a function is known to be a piecewise monotonic function and verifying a relationship between values of the base column x and an a derived column, and wherein during said building an index over the monotonic function if a derived column is known to be a monotonic function by observation, at each of a plurality of updates a relationship should be verified.