1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
|
// Copyright Yahoo. Licensed under the terms of the Apache 2.0 license. See LICENSE in the project root.
package com.yahoo.search.predicate.index;
import com.yahoo.document.predicate.PredicateHash;
/**
* Expands range terms from a query to find the set of features they translate to.
*
* @author bjorncs
* @author Magnar Nedland
*/
public class PredicateRangeTermExpander {
private final int arity;
private final int maxPositiveLevels;
private final int maxNegativeLevels;
private final long lowerBound;
private final long upperBound;
/**
* Creates a PredicateRangeTermExpander with default value range.
*
* @param arity The arity used to index the predicates
*/
public PredicateRangeTermExpander(int arity) {
this(arity, Long.MIN_VALUE, Long.MAX_VALUE);
}
/**
* @param arity The arity used to index the predicates
* @param lowerBound The minimum value used by any range predicate in the system
* @param upperBound The maximum value used by any range predicate in the system
*/
public PredicateRangeTermExpander(int arity, long lowerBound, long upperBound) {
this.arity = arity;
this.lowerBound = lowerBound;
this.upperBound = upperBound;
this.maxPositiveLevels = calculateMaxLevels(upperBound);
this.maxNegativeLevels = calculateMaxLevels(-lowerBound);
}
private int calculateMaxLevels(long t) {
int maxLevels = 1;
while ((t /= this.arity) != 0) {
maxLevels++;
}
return maxLevels;
}
/**
* Expands a range term to a set of features (ranges and edges) to be used in a query.
*
* @param key The term key
* @param value The term value
* @param rangeHandler Handler for range features (long)
* @param edgeHandler Handler for edge features (long, int)
*/
public void expand(String key, long value, RangeHandler rangeHandler, EdgeHandler edgeHandler) {
if (value < lowerBound || value > upperBound) {
// Value outside bounds -> expand to nothing.
return;
}
int maxLevels = value > 0 ? maxPositiveLevels : maxNegativeLevels;
int sign = value > 0 ? 1 : -1;
// Append key to feature string builder
StringBuilder builder = new StringBuilder(128);
builder.append(key).append('=');
long levelSize = arity;
long edgeInterval = (value / arity) * arity;
edgeHandler.handleEdge(createEdgeFeatureHash(builder, edgeInterval), (int) Math.abs(value - edgeInterval));
for (int i = 0; i < maxLevels; ++i) {
long start = (value / levelSize) * levelSize;
if (Math.abs(start) + levelSize - 1 < 0) { // overflow
break;
}
rangeHandler.handleRange(createRangeFeatureHash(builder, start, start + sign * (levelSize - 1)));
levelSize *= arity;
if (levelSize <= 0 && levelSize != Long.MIN_VALUE) { //overflow
break;
}
}
}
private long createRangeFeatureHash(StringBuilder builder, long start, long end) {
int prefixLength = builder.length();
String feature = end > 0
? builder.append(start).append('-').append(end).toString()
: builder.append(end).append('-').append(Math.abs(start)).toString();
builder.setLength(prefixLength);
return PredicateHash.hash64(feature);
}
private long createEdgeFeatureHash(StringBuilder builder, long edgeInterval) {
int prefixLength = builder.length();
String feature = builder.append(edgeInterval).toString();
builder.setLength(prefixLength);
return PredicateHash.hash64(feature);
}
/**
* Callback for ranges generated by the expansion.
*/
@FunctionalInterface
public interface RangeHandler {
void handleRange(long featureHash);
}
/**
* Callback for edges generated by the expansion.
*/
@FunctionalInterface
public interface EdgeHandler {
void handleEdge(long featureHash, int value);
}
}
|
