-
Notifications
You must be signed in to change notification settings - Fork 15
/
TableStatsTest.java
155 lines (134 loc) · 6.89 KB
/
TableStatsTest.java
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
package simpledb;
import java.io.IOException;
import java.util.ArrayList;
import org.junit.Before;
import org.junit.Test;
import org.junit.Assert;
import simpledb.Aggregator.Op;
import simpledb.systemtest.SimpleDbTestBase;
import simpledb.systemtest.SystemTestUtil;
public class TableStatsTest extends SimpleDbTestBase {
public static final int IO_COST = 71;
ArrayList<ArrayList<Integer>> tuples;
HeapFile f;
String tableName;
int tableId;
@Before public void setUp() throws Exception {
super.setUp();
this.tuples = new ArrayList<ArrayList<Integer>>();
this.f = SystemTestUtil.createRandomHeapFile(10, 1020, 32, null, tuples);
this.tableName = SystemTestUtil.getUUID();
Database.getCatalog().addTable(f, tableName);
this.tableId = Database.getCatalog().getTableId(tableName);
}
private double[] getRandomTableScanCosts(int[] pageNums, int[] ioCosts) throws IOException, DbException, TransactionAbortedException {
double[] ret = new double[ioCosts.length];
for(int i = 0; i < ioCosts.length; ++i) {
HeapFile hf = SystemTestUtil.createRandomHeapFile(1, 992*pageNums[i], 32, null, tuples);
Assert.assertEquals(pageNums[i], hf.numPages());
String tableName = SystemTestUtil.getUUID();
Database.getCatalog().addTable(hf, tableName);
int tableId = Database.getCatalog().getTableId(tableName);
ret[i] = (new TableStats(tableId, ioCosts[i])).estimateScanCost();
}
return ret;
}
/**
* Verify the cost estimates of scanning various numbers of pages from a HeapFile
* This test checks that the estimateScanCost is:
* +linear in numPages when IO_COST is constant
* +linear in IO_COST when numPages is constant
* +quadratic when IO_COST and numPages increase linearly.
*/
@Test public void estimateScanCostTest() throws IOException, DbException, TransactionAbortedException {
Object[] ret;
int[] ioCosts = new int[20];
int[] pageNums = new int[ioCosts.length];
// IO_COST constant, numPages change
for(int i = 0; i < ioCosts.length; ++i) {
ioCosts[i] = 1;
pageNums[i] = 3*(i+1);
}
double stats[] = getRandomTableScanCosts(pageNums, ioCosts);
ret = SystemTestUtil.checkConstant(stats);
Assert.assertEquals(ret[0], Boolean.FALSE);
ret = SystemTestUtil.checkLinear(stats);
Assert.assertEquals(ret[0], Boolean.TRUE);
// numPages constant, IO_COST change
for(int i = 0; i < ioCosts.length; ++i) {
ioCosts[i] = 10*(i + 1);
pageNums[i] = 3;
}
stats = getRandomTableScanCosts(pageNums, ioCosts);
ret = SystemTestUtil.checkConstant(stats);
Assert.assertEquals(ret[0], Boolean.FALSE);
ret = SystemTestUtil.checkLinear(stats);
Assert.assertEquals(ret[0], Boolean.TRUE);
//numPages & IO_COST increase linearly
for(int i = 0; i < ioCosts.length; ++i) {
ioCosts[i] = 3*(i + 1);
pageNums[i] = (i+1);
}
stats = getRandomTableScanCosts(pageNums, ioCosts);
ret = SystemTestUtil.checkConstant(stats);
Assert.assertEquals(ret[0], Boolean.FALSE);
ret = SystemTestUtil.checkLinear(stats);
Assert.assertEquals(ret[0], Boolean.FALSE);
ret = SystemTestUtil.checkQuadratic(stats);
Assert.assertEquals(ret[0], Boolean.TRUE);
}
/**
* Verify the table-cardinality estimates based on a selectivity estimate
*/
@Test public void estimateTableCardinalityTest() {
TableStats s = new TableStats(this.tableId, IO_COST);
// Try a random selectivity
Assert.assertEquals(306, s.estimateTableCardinality(0.3));
// Make sure we get all rows with 100% selectivity, and none with 0%
Assert.assertEquals(1020, s.estimateTableCardinality(1.0));
Assert.assertEquals(0, s.estimateTableCardinality(0.0));
}
/**
* Verify that selectivity estimates do something reasonable.
* Don't bother splitting this into N different functions for
* each possible Op because we will probably catch any bugs here in
* IntHistogramTest, so we hopefully don't need all the JUnit checkboxes.
*/
@Test public void estimateSelectivityTest() {
final int maxCellVal = 32; // Tuple values are randomized between 0 and this number
final Field aboveMax = new IntField(maxCellVal + 10);
final Field atMax = new IntField(maxCellVal);
final Field halfMaxMin = new IntField(maxCellVal/2);
final Field atMin = new IntField(0);
final Field belowMin = new IntField(-10);
TableStats s = new TableStats(this.tableId, IO_COST);
for (int col = 0; col < 10; col++) {
Assert.assertEquals(0.0, s.estimateSelectivity(col, Predicate.Op.EQUALS, aboveMax), 0.001);
Assert.assertEquals(1.0/32.0, s.estimateSelectivity(col, Predicate.Op.EQUALS, halfMaxMin), 0.015);
Assert.assertEquals(0, s.estimateSelectivity(col, Predicate.Op.EQUALS, belowMin), 0.001);
Assert.assertEquals(1.0, s.estimateSelectivity(col, Predicate.Op.NOT_EQUALS, aboveMax), 0.001);
Assert.assertEquals(31.0/32.0, s.estimateSelectivity(col, Predicate.Op.NOT_EQUALS, halfMaxMin), 0.015);
Assert.assertEquals(1.0, s.estimateSelectivity(col, Predicate.Op.NOT_EQUALS, belowMin), 0.015);
Assert.assertEquals(0.0, s.estimateSelectivity(col, Predicate.Op.GREATER_THAN, aboveMax), 0.001);
Assert.assertEquals(0.0, s.estimateSelectivity(col, Predicate.Op.GREATER_THAN, atMax), 0.001);
Assert.assertEquals(0.5, s.estimateSelectivity(col, Predicate.Op.GREATER_THAN, halfMaxMin), 0.1);
Assert.assertEquals(31.0/32.0, s.estimateSelectivity(col, Predicate.Op.GREATER_THAN, atMin), 0.05);
Assert.assertEquals(1.0, s.estimateSelectivity(col, Predicate.Op.GREATER_THAN, belowMin), 0.001);
Assert.assertEquals(1.0, s.estimateSelectivity(col, Predicate.Op.LESS_THAN, aboveMax), 0.001);
Assert.assertEquals(1.0, s.estimateSelectivity(col, Predicate.Op.LESS_THAN, atMax), 0.015);
Assert.assertEquals(0.5, s.estimateSelectivity(col, Predicate.Op.LESS_THAN, halfMaxMin), 0.1);
Assert.assertEquals(0.0, s.estimateSelectivity(col, Predicate.Op.LESS_THAN, atMin), 0.001);
Assert.assertEquals(0.0, s.estimateSelectivity(col, Predicate.Op.LESS_THAN, belowMin), 0.001);
Assert.assertEquals(0.0, s.estimateSelectivity(col, Predicate.Op.GREATER_THAN_OR_EQ, aboveMax), 0.001);
Assert.assertEquals(0.0, s.estimateSelectivity(col, Predicate.Op.GREATER_THAN_OR_EQ, atMax), 0.015);
Assert.assertEquals(0.5, s.estimateSelectivity(col, Predicate.Op.GREATER_THAN_OR_EQ, halfMaxMin), 0.1);
Assert.assertEquals(1.0, s.estimateSelectivity(col, Predicate.Op.GREATER_THAN_OR_EQ, atMin), 0.015);
Assert.assertEquals(1.0, s.estimateSelectivity(col, Predicate.Op.GREATER_THAN_OR_EQ, belowMin), 0.001);
Assert.assertEquals(1.0, s.estimateSelectivity(col, Predicate.Op.LESS_THAN_OR_EQ, aboveMax), 0.001);
Assert.assertEquals(1.0, s.estimateSelectivity(col, Predicate.Op.LESS_THAN_OR_EQ, atMax), 0.015);
Assert.assertEquals(0.5, s.estimateSelectivity(col, Predicate.Op.LESS_THAN_OR_EQ, halfMaxMin), 0.1);
Assert.assertEquals(0.0, s.estimateSelectivity(col, Predicate.Op.LESS_THAN_OR_EQ, atMin), 0.05);
Assert.assertEquals(0.0, s.estimateSelectivity(col, Predicate.Op.LESS_THAN_OR_EQ, belowMin), 0.001);
}
}
}