Efficiently Compiling Efficient Query Plans for Modern Hardware

1
2
3
4
5

Entry* iter=hashTable[hash];
while (iter) {
	... // inspect the entry
	iter=iter->next;
}

1
2
3
4
5

Entry* iter=hashTable[hash];
if (iter) do {
	... // inspect the entry
	iter=iter->next;
} while (iter);

 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

void TableScanTranslator::produce(CodeGen& codegen,Context& context) const {
	// Access all relation fragments
	llvm::Value∗ dbPtr=codegen.getDatabasePointer();
	llvm::Value∗ relationPtr=codegen.getPtr(dbPtr,db.layout.relations[table]);
	auto& required=scanConsumer.getPartitionPtr();
	ScanConsumer scanConsumer(codegen,context)
	for (;db.relations[table]−>generateScan(codegen,relationPtr,scanConsumer);) {
		// Prepare accessing the current fragment
		llvm::Value∗ partitionPtr=required;
		ColumnAccess columnAccess(partitionPtr,required);

		// Loop over all tuples
		llvm::Value∗ tid=codegen.const64(0);
		llvm::Value∗ limit=codegen.load(partitionPtr,getLayout().size);
		Loop loop(codegen,codegen−>CreateICmpULT(tid,limit),{{tid,”tid”}}); {
			tid=loop.getLoopVar(0);
		
			// Prepare column access code
			PartitionAccess::ColumnAccess::Row rowAccess(columnAccess,tid);
			vector<ValueAccess> access;
			for (auto iter=required.begin(),limit=required.end();iter!=limit;++iter)
				access.push back(rowAccess.loadAttribute(∗iter));
			
				// Register providers in new inner context
				ConsumerContext consumerContext(context);
				unsigned slot=0;
				for (auto iter=required.begin(),limit=required.end();iter!=limit;++iter,++slot)
					consumerContext.registerIUProvider(&(getOutput()[∗iter].iu),&access[slot]);

					// Push results to consuming operators
					getParent()−>consume(codegen,consumerContext);

					// Go to the next tuple
					tid=codegen−>CreateAdd(tid,codegen.const64(1));
					loop.loopDone(codegen−>CreateICmpULT(tid,limit),{tid});
			}
		}
	}
}	

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

void SelectTranslator::produce(CodeGen& codegen,Context& context) const {
	// Ask the input operator to produce tuples
	AddRequired addRequired(context,getCondition().getUsed());
	input−>produce(codegen,context);
}

void SelectTranslator::consume(CodeGen& codegen,Context& context) const {
	// Evaluate the predicate
	ResultValue value=codegen.deriveValue(getCondition(),context);

	// Pass tuple to parent if the predicate is satisfied
	CodeGen::If checkCond(codegen,value); {
		getParent()−>consume(codegen,context);
	}
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

void ProjectTranslator::produce(CodeGen& codegen,Context& context) const {
	// Ask the input operator to produce tuples
	SetRequired setRequired(context,getOutput());
	input−>produce(codegen,context);
}

void ProjectTranslator::consume(CodeGen& codegen,Context& context) const {
	// No code required here, pass to parent
	getParent()−>consume(codegen,context);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

void MapTranslator::produce(CodeGen& codegen,Context& context) const {
	// Figure out which columns have to be provided by the input operator
	IUSet required=context.getRequired();
	for (auto iter=functions.begin(),limit=functions.end();iter!=limit;++iter) {
		(*iter).function−>getUsed(required);
		required.erase((∗iter).result);
	}

	// Ask the input operator to produce tuples
	SetRequired setRequired(context,required);
	input−>produce(codegen,context);
}

void MapTranslator::consume(CodeGen& codegen,Context& context) const {
	// Offer new columns
	vector<ExpressionAccess> accessors;
	for (auto iter=functions.begin(),limit=functions.end();iter!=limit;++iter)
		accessors.push back(ExpressionAccess(codegen,∗(∗iter).function));
	for (unsigned index=0,limit=accessors.size();index<limit;index++)
		context.registerIUProvider(functions[index].result,&accessors[index]);
	
	// Pass to parent
	getParent()−>consume(codegen,context);
}

 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

void HashJoin::Inner::produce() {
	// Read the build side
	initMem();
	produceLeft();
	if (inMem) {
		buildHashTable();
	} else {
		// Spool remaining tuples to disk
		spoolLeft();
		finishSpoolLeft();
	}

	// Is a in−memory join possible?
	if (inMem) {
		produceRight();
		return;
	}

	// No, spool the right hand side, too
	spoolRight();
	// Grace hash join
	loadPartition(0);
	while (true) {
		// More tuples on the right?
		for (;rightScanRemaining;) {
			const void∗ rightTuple=nextRight();
			for (LookupHash lookup(rightTuple);lookup;++lookup) {
				join(lookup.data(),rightTuple);
			}
		}

		// Handle overflow in n:m case
		if (overflow) {
			loadPartitionLeft();
			resetRightScan();
			continue;
		}

		// Go to the next partition
		if ((++inMemPartition)>=partitionCount) {
			return;
		} else {
			loadPartition(inMemPartition);
		}
	}
}

 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

void HJTranslatorInner::produce(CodeGen& codegen,Context& context) const {
	// Construct functions that will be be called from the C++ code
	{
		AddRequired addRequired(context,getCondiution().getUsed().limitTo(left));
		produceLeft=codegen.derivePlanFunction(left,context);
	}
	{
		AddRequired addRequired(context,getCondiution().getUsed().limitTo(right));
		produceRight=codegen.derivePlanFunction(right,context);
	}
	// Call the C++ code
	codegen.call(HashJoinInnerProxy::produce.getFunction(codegen),
		{context.getOperator(this)});
}

void HJTranslatorInner::consume(CodeGen& codegen,Context& context) const {
	llvm::Value∗ opPtr=context.getOperator(this);

	// Left side
	if (source==left) {
		// Collect registers from the left side
		vector<ResultValue> materializedValues;
		matHelperLeft.collectValues(codegen,context,materializedValues);

		// Compute size and hash value
		llvm::Value∗ size=matHelperLeft.computeSize(codegen,materializedValues);
		llvm::Value∗ hash=matHelperLeft.computeHash(codegen,materializedValues);
		// Materialize in hash table, spools to disk if needed
		llvm::Value∗ ptr=codegen.callBase(HashJoinProxy::storeLeftInputTuple,
		{opPtr,size,hash});
		matHelperLeft.materialize(codegen,ptr,materializedValues);
		
	// Right side
	} else {
		// Collect registers from the right side
		vector<ResultValue> materializedValues;
		matHelperRight.collectValues(codegen,context,materializedValues);

		// Compute size and hash value
		llvm::Value∗ size=matHelperRight.computeSize(codegen,materializedValues);
		llvm::Value∗ hash=matHelperRight.computeHash(codegen,materializedValues);
	
		// Materialize in memory, spools to disk if needed, implicitly joins
		llvm::Value∗ ptr=codegen.callBase(HashJoinProxy::storeRightInputTuple, {opPtr,size});
		matHelperRight.materialize(codegen,ptr,materializedValues);
		codegen.call(HashJoinInnerProxy::storeRightInputTupleDone,{opPtr,hash});
	}
}

void HJTranslatorInner::join(CodeGen& codegen,Context& context) const {
	llvm::Value∗ leftPtr=context.getLeftTuple(),∗rightPtr=context.getLeftTuple();
	// Load into registers. Actual load may be delayed by optimizer
	vector<ResultValue> leftValues,rightValues;
	matHelperLeft.dematerialize(codegen,leftPtr,leftValues,context);
	matHelperRight.dematerialize(codegen,rightPtr,rightValues,context);

	// Check the join condition, return false for mismatches
	llvm::BasicBlock∗ returnFalseBB=constructReturnFalseBB(codegen);
	MaterializationHelper::testValues(codegen,leftValues,rightValues,
		joinPredicateIs,returnFalseBB);
	for (auto iter=residuals.begin(),limit=residuals.end();iter!=limit;++iter) {
		ResultValue v=codegen.deriveValue(∗∗iter,context);
		CodeGen::If checkCondition(codegen,v,0,returnFalseBB);
	}

	// Found a match, propagate up
	getParent()−>consume(codegen,context);
}

1
2

select d_tax from warehouse, district
where w_id=d_w_id and w_zip=’137411111’

1
2
3

select count(*)
from orderline
where ol_o_id>0 and ol_d_id>0 and ol_w_id>0

1
2

select sum(ol_o_id*ol_d_id*ol_w_id)
from orderline

1

-O3 -fgcse-las -funsafe-loop-optimizations.

1

-ftree-vectorize

1
2
3
4
5
6

llvm::createInstructionCombiningPass()
llvm::createReassociatePass()
llvm::createGVNPass()
llvm::createCFGSimplificationPass()
llvm::createAggressiveDCEPass()
llvm::createCFGSimplificationPass()