Diffa Diffa

We need a generic way of allowing the agent to auto-discover the upper and lower bounds of non-date partition attributes. The use case is for wanting to partition entities that don't have a natural partition. In this case, you would fall back to using the entity id. The downside of this approach is that this means a linear scan of all of the entities.

To mitigate this, it should be possible for the agent to discover the lower and upper bounds for the value range that makes up the id space. In addition to this, the agent can start off with a query that returns the coarsest possible digests (i.e. with the maximum amount of precision loss). Upon a mismatch, the agent re-queries with a higher precision. This descent is continued until the smallest amount of precision loss is applied and the agent needs to query for individual entities.

The main advantage of this approach is to reduce the search space for querying at atomic granularity. The secondary advantage is that the bounds for the descent are auto-discoverable by the agent.

To facilitate the bounds discovery, when a pairing is configured, the configuration should give some indication of a sensible default precision loss. So for example, if a pairing involves integer based entity ids between 1 and 2 million, then an appropriate precision loss would be in the range of millions. If the entity id distribution were much narrower, say between 1 and 1000, the a precision loss in the order of 1000 would be more appropriate. Conversely if the maximum id is currently 1 billion, then the default precision loss should be set at 10 ^ 9.

Examples:

• Integer ids:
  • The precision loss function is x = q * d + r
    • x is a natural number
    • q is the quotient
    • d is the divisor
    • r is the remainder
  • Assume a deployment where the ids of the entity under question are between 1 and 2 million, say
  • Descent is based on successively reducing a pre-defined maximum divisor exponent, e.g. Divisor(6) i.e. d = 10 ^ 6
    
  1. QueryConstraint(lo:null, hi:null, attribute:id, func: Divisor(6)) would return [Digest(1 Million), Digest(2 Million)]
  2. Re-query with QueryConstraint(lo:1M, hi:2M, attribute:id, func: Divisor(5)). This returns digests at a granularity of 10 ^ 5.
  3. Recurse until an individual entity query is required - but with significantly narrowed bounds.
• String ids:
  • The precision loss function is the first character of the string
  • Assume a deployment where the ids of the entity under question are random hex guids, say
  • Descent is based on successively increasing the character prefix of the string, e.g. Prefix(1) is a partition based on the first character
  1. QueryConstraint(lo:null, hi:null, attribute:id, func: Prefix(1)) would return [Digest(A) ... Digest(H), Digest(1) ... Digest(0)] i.e. 16 partitions prefix by each hex symbol
  2. Re-query with QueryConstraint(lo:A, hi:0, attribute:id, func: Prefix(2)). This returns digests partitions on the first two hex symbols.
  3. Same as step(3) above.
• Dates:
  • These are already implemented, but for completeness' sake they shall be described in this context
  • Assume a deployment where the dates of the entity under question occur in 2009 and 2010
  • (In the current implementation) Descent are hard- coded functions that know the next most granular function, i.e. Yearly > Monthly > Daily > Individual
  • We could consider "porting" the current date narrowing to the more generic proposal being made as part of this ticket.

Possible extensions:

• The descent function could define steps that force the agent to make larger decreases in precision loss, e.g.
  • Divisor(n) could be augmented to Divisor(n,m) where the next iteration is Divisor (n-m,m) - i.e. Divisor (6,2) iterates to Divisor (4,2)
  • Prefix (n,m) - i.e. Prefix(1,2) iterates to Prefix(3,2)