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
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
package edu.caltech.nanodb.queryeval;
import java.util.ArrayList;
import java.util.HashSet;
import org.apache.logging.log4j.Logger;
import org.apache.logging.log4j.LogManager;
import edu.caltech.nanodb.expressions.ArithmeticOperator;
import edu.caltech.nanodb.expressions.BooleanOperator;
import edu.caltech.nanodb.expressions.ColumnValue;
import edu.caltech.nanodb.expressions.CompareOperator;
import edu.caltech.nanodb.expressions.Expression;
import edu.caltech.nanodb.expressions.LiteralValue;
import edu.caltech.nanodb.expressions.TypeConverter;
import edu.caltech.nanodb.relations.ColumnInfo;
import edu.caltech.nanodb.relations.SQLDataType;
import edu.caltech.nanodb.relations.Schema;
/**
* This utility class is used to estimate the selectivity of predicates that
* appear on Select and Theta-Join plan-nodes.
*/
public class SelectivityEstimator {
/** A logging object for reporting anything interesting that happens. **/
private static Logger logger = LogManager.getLogger(SelectivityEstimator.class);
/**
* This collection specifies the data-types that support comparison
* selectivity estimates (not including equals or not-equals). It must be
* possible to use the {@link #computeRatio} on the data-type so that an
* estimate can be made about where a value fits within the minimum and
* maximum values for the column.
* <p>
* Note that we can compute selectivity for equals and not-equals simply
* from the number of distinct values in the column.
*/
private static HashSet<SQLDataType> SUPPORTED_TYPES_COMPARE_ESTIMATES;
static {
// Initialize the set of types that support comparison selectivity
// estimates.
SUPPORTED_TYPES_COMPARE_ESTIMATES = new HashSet<SQLDataType>();
SUPPORTED_TYPES_COMPARE_ESTIMATES.add(SQLDataType.INTEGER);
SUPPORTED_TYPES_COMPARE_ESTIMATES.add(SQLDataType.BIGINT);
SUPPORTED_TYPES_COMPARE_ESTIMATES.add(SQLDataType.SMALLINT);
SUPPORTED_TYPES_COMPARE_ESTIMATES.add(SQLDataType.TINYINT);
SUPPORTED_TYPES_COMPARE_ESTIMATES.add(SQLDataType.FLOAT);
SUPPORTED_TYPES_COMPARE_ESTIMATES.add(SQLDataType.DOUBLE);
SUPPORTED_TYPES_COMPARE_ESTIMATES.add(SQLDataType.NUMERIC);
SUPPORTED_TYPES_COMPARE_ESTIMATES.add(SQLDataType.DATE);
SUPPORTED_TYPES_COMPARE_ESTIMATES.add(SQLDataType.TIME);
SUPPORTED_TYPES_COMPARE_ESTIMATES.add(SQLDataType.DATETIME);
SUPPORTED_TYPES_COMPARE_ESTIMATES.add(SQLDataType.TIMESTAMP);
}
/**
* This constant specifies the default selectivity assumed when a select
* predicate is too complicated to compute more accurate estimates. We are
* assuming that generally people are going to do things that limit the
* results produced.
*/
public static final float DEFAULT_SELECTIVITY = 0.25f;
/** This class should not be instantiated. */
private SelectivityEstimator() {
throw new IllegalArgumentException("This class should not be instantiated.");
}
/**
* Returns true if the database supports selectivity estimates for
* comparisons (other than equals and not-equals) on the specified SQL data
* type. SQL types that support these selectivity estimates will include
* minimum and maximum values in their column-statistics.
*
* @param type the SQL data type being considered
*
* @return true if the database supports selectivity estimates for the type
*/
public static boolean typeSupportsCompareEstimates(SQLDataType type) {
return SUPPORTED_TYPES_COMPARE_ESTIMATES.contains(type);
}
/**
* This function computes the selectivity of a selection predicate, using
* table statistics and other estimates to make an educated guess. The
* result is between 0.0 and 1.0, with 1.0 meaning that all rows will be
* selected by the predicate.
*
* @param expr the expression whose selectivity we are estimating
*
* @param exprSchema a schema describing the environment that the expression
* will be evaluated within
*
* @param stats statistics that may be helpful in estimating the selectivity
*
* @return the estimated selectivity as a float
*/
public static float estimateSelectivity(Expression expr, Schema exprSchema,
ArrayList<ColumnStats> stats) {
float selectivity = DEFAULT_SELECTIVITY;
if (expr instanceof BooleanOperator) {
// A Boolean AND, OR, or NOT operation.
BooleanOperator bool = (BooleanOperator) expr;
selectivity = estimateBoolOperSelectivity(bool, exprSchema, stats);
}
else if (expr instanceof CompareOperator) {
// This is a simple comparison between expressions.
CompareOperator comp = (CompareOperator) expr;
selectivity = estimateCompareSelectivity(comp, exprSchema, stats);
}
return selectivity;
}
/**
* This function computes a selectivity estimate for a general Boolean
* expression that may be comprised of one or more components. The method
* treats components as independent, estimating the selectivity of each one
* separately, and then combines the results based on whether the Boolean
* operation is an <tt>AND</tt>, an <tt>OR</tt>, or a <tt>NOT</tt>
* operation. As one might expect, this method delegates to
* {@link #estimateSelectivity} to compute the selectivity of individual
* terms.
*
* @param bool the compound Boolean expression
*
* @param exprSchema a schema specifying the environment that the expression
* will be evaluated within
*
* @param stats a collection of column-statistics to use in making
* selectivity estimates
*
* @return a selectivity estimate in the range [0, 1].
*/
public static float estimateBoolOperSelectivity(BooleanOperator bool,
Schema exprSchema, ArrayList<ColumnStats> stats) {
float selectivity = 1.0f;
switch (bool.getType()) {
case AND_EXPR:
// TODO: Compute selectivity of AND expression.
break;
case OR_EXPR:
// TODO: Compute selectivity of OR expression.
break;
case NOT_EXPR:
// TODO: Compute selectivity of NOT expression.
break;
default:
// Shouldn't have any other Boolean expression types.
assert false : "Unexpected Boolean operator type: " + bool.getType();
}
logger.debug("Estimated selectivity of Boolean operator \"" + bool +
"\" as " + selectivity);
return selectivity;
}
/**
* This function computes a selectivity estimate for a general comparison
* operation. The method examines the types of the arguments in the
* comparison and determines if it will be possible to make a reasonable
* guess as to the comparison's selectivity; if not then a default
* selectivity estimate is used.
*
* @param comp the comparison expression
*
* @param exprSchema a schema specifying the environment that the expression
* will be evaluated within
*
* @param stats a collection of column-statistics to use in making
* selectivity estimates
*
* @return a selectivity estimate in the range [0, 1].
*/
public static float estimateCompareSelectivity(CompareOperator comp,
Schema exprSchema, ArrayList<ColumnStats> stats) {
float selectivity = DEFAULT_SELECTIVITY;
// Move the comparison into a normalized order so that it's easier to
// write the logic for analysis. Specifically, this will ensure that
// if we are comparing a column and a value, the column will always be
// on the left and the value will always be on the right.
comp.normalize();
Expression left = comp.getLeftExpression();
Expression right = comp.getRightExpression();
// If the comparison is simple enough then compute its selectivity.
// Otherwise, just use the default selectivity.
if (left instanceof ColumnValue && right instanceof LiteralValue) {
// Comparison: column op value
selectivity = estimateCompareColumnValue(comp.getType(),
(ColumnValue) left, (LiteralValue) right, exprSchema, stats);
logger.debug("Estimated selectivity of cmp-col-val operator \"" +
comp + "\" as " + selectivity);
}
else if (left instanceof ColumnValue && right instanceof ColumnValue) {
// Comparison: column op column
selectivity = estimateCompareColumnColumn(comp.getType(),
(ColumnValue) left, (ColumnValue) right, exprSchema, stats);
logger.debug("Estimated selectivity of cmp-col-col operator \"" +
comp + "\" as " + selectivity);
}
return selectivity;
}
/**
* This helper function computes a selectivity estimate for a comparison
* between a column and a literal value. Note that the comparison is always
* assumed to have the column-name on the <em>left</em>, and the literal
* value on the <em>right</em>. Examples would be <tt>T1.A > 5</tt>, or
* <tt>T2.C = 15</tt>.
*
* @param compType the type of the comparison, e.g. equals, not-equals, or
* some inequality comparison
*
* @param columnValue the column that is used in the comparison
* @param literalValue the value that the column is being compared to
*
* @param exprSchema a schema specifying the environment that the expression
* will be evaluated within
*
* @param stats a collection of column-statistics to use in making
* selectivity estimates
*
* @return a selectivity estimate in the range [0, 1].
*/
private static float estimateCompareColumnValue(CompareOperator.Type compType,
ColumnValue columnValue, LiteralValue literalValue,
Schema exprSchema, ArrayList<ColumnStats> stats) {
// Comparison: column op value
float selectivity = DEFAULT_SELECTIVITY;
// Pull out the critical values for making the estimates.
int colIndex = exprSchema.getColumnIndex(columnValue.getColumnName());
ColumnInfo colInfo = exprSchema.getColumnInfo(colIndex);
SQLDataType sqlType = colInfo.getType().getBaseType();
ColumnStats colStats = stats.get(colIndex);
Object value = literalValue.evaluate();
switch (compType) {
case EQUALS:
case NOT_EQUALS:
// Compute the equality value. Then, if inequality, invert the
// result.
// TODO: Compute the selectivity. Note that the ColumnStats type
// will return special values to indicate "unknown" stats;
// your code should detect when this is the case, and fall
// back on the default selectivity.
break;
case GREATER_OR_EQUAL:
case LESS_THAN:
// Compute the greater-or-equal value. Then, if less-than,
// invert the result.
// Only estimate selectivity for this kind of expression if the
// column's type supports it.
if (typeSupportsCompareEstimates(sqlType) &&
colStats.hasDifferentMinMaxValues()) {
// TODO: Compute the selectivity. The if-condition ensures
// that you will only compute selectivities if the type
// supports it, and if there are valid stats.
}
break;
case LESS_OR_EQUAL:
case GREATER_THAN:
// Compute the less-or-equal value. Then, if greater-than,
// invert the result.
// Only estimate selectivity for this kind of expression if the
// column's type supports it.
if (typeSupportsCompareEstimates(sqlType) &&
colStats.hasDifferentMinMaxValues()) {
// TODO: Compute the selectivity. Watch out for copy-paste
// bugs...
}
break;
default:
// Shouldn't be any other comparison types...
assert false : "Unexpected compare-operator type: " + compType;
}
return selectivity;
}
/**
* This helper function computes a selectivity estimate for a comparison
* between two columns. Examples would be <tt>T1.A = T2.A</tt>.
*
* @param compType the type of the comparison, e.g. equals, not-equals, or
* some inequality comparison
*
* @param columnOne the first column that is used in the comparison
* @param columnTwo the second column that is used in the comparison
*
* @param exprSchema a schema specifying the environment that the expression
* will be evaluated within
*
* @param stats a collection of column-statistics to use in making
* selectivity estimates
*
* @return a selectivity estimate in the range [0, 1].
*/
private static float estimateCompareColumnColumn(CompareOperator.Type compType,
ColumnValue columnOne, ColumnValue columnTwo,
Schema exprSchema, ArrayList<ColumnStats> stats) {
// Comparison: column op column
float selectivity = DEFAULT_SELECTIVITY;
// Pull out the critical values for making the estimates.
int colOneIndex = exprSchema.getColumnIndex(columnOne.getColumnName());
int colTwoIndex = exprSchema.getColumnIndex(columnTwo.getColumnName());
ColumnStats colOneStats = stats.get(colOneIndex);
ColumnStats colTwoStats = stats.get(colTwoIndex);
// TODO: Compute the selectivity. Note that the ColumnStats type
// will return special values to indicate "unknown" stats;
// your code should detect when this is the case, and fall
// back on the default selectivity.
return selectivity;
}
/**
* This method computes the function
* (<em>high</em><sub>1</sub> - <em>low</em><sub>1</sub>) /
* (<em>high</em><sub>2</sub> - <em>low</em><sub>2</sub>), given
* <tt>Object</tt>-values that can be coerced into types that can
* be used for arithmetic. This operation is useful for estimating the
* selectivity of comparison operations, if we know the minimum and maximum
* values for a column.
* <p>
* The result of this operation is clamped to the range [0, 1].
*
* @param low1 the low value for the numerator
* @param high1 the high value for the numerator
* @param low2 the low value for the denominator
* @param high2 the high value for the denominator
*
* @return the ratio of (<em>high</em><sub>1</sub> - <em>low</em><sub>1</sub>) /
* (<em>high</em><sub>2</sub> - <em>low</em><sub>2</sub>), clamped
* to the range [0, 1].
*/
public static float computeRatio(Object low1, Object high1,
Object low2, Object high2) {
Object diff1 = ArithmeticOperator.evalObjects(
ArithmeticOperator.Type.SUBTRACT, high1, low1);
Object diff2 = ArithmeticOperator.evalObjects(
ArithmeticOperator.Type.SUBTRACT, high2, low2);
diff1 = TypeConverter.getFloatValue(diff1);
diff2 = TypeConverter.getFloatValue(diff2);
Object ratio = ArithmeticOperator.evalObjects(
ArithmeticOperator.Type.DIVIDE, diff1, diff2);
// This should already be a float, but just in case...
float fltRatio = TypeConverter.getFloatValue(ratio);
logger.debug(String.format("Ratio: (%s - %s) / (%s - %s) = %.2f",
high1, low1, high2, low2, fltRatio));
// Clamp the value to the range [0, 1].
if (fltRatio < 0.0f)
fltRatio = 0.0f;
else if (fltRatio > 1.0f)
fltRatio = 1.0f;
return fltRatio;
}
}