opensci
/
gStore
1
0
Fork 0
Code Issues Pull Requests Releases Wiki Activity
gStore/Database/Strategy.cpp

865 lines
29 KiB
C++
Raw Permalink Blame History

/*=============================================================================
# Filename: Strategy.cpp
# Author: Bookug Lobert
# Mail: zengli-bookug@pku.edu.cn
# Last Modified: 2016-05-07 16:31
# Description: implement functions in Strategy.h
=============================================================================*/
#include "Strategy.h"
using namespace std;
Strategy::Strategy()
{
this->method = 0;
this->kvstore = NULL;
this->vstree = NULL;
this->fp = NULL;
this->export_flag = false;
//this->prepare_handler();
}
Strategy::Strategy(KVstore* _kvstore, VSTree* _vstree, TYPE_TRIPLE_NUM* _pre2num, TYPE_TRIPLE_NUM* _pre2sub,
TYPE_TRIPLE_NUM* _pre2obj, TYPE_PREDICATE_ID _limitID_predicate, TYPE_ENTITY_LITERAL_ID _limitID_literal,
TYPE_ENTITY_LITERAL_ID _limitID_entity)
{
this->method = 0;
this->kvstore = _kvstore;
this->vstree = _vstree;
this->pre2num = _pre2num;
this->pre2sub = _pre2sub;
this->pre2obj = _pre2obj;
this->limitID_predicate = _limitID_predicate;
this->limitID_literal = _limitID_literal;
this->limitID_entity = _limitID_entity;
this->fp = NULL;
this->export_flag = false;
//this->prepare_handler();
}
Strategy::~Strategy()
{
//delete[] this->dispatch;
}
//void
//Strategy::prepare_handler()
//{
//this->dispatch = new QueryHandler[Strategy::QUERY_HANDLER_NUM];
//this->dispatch[0] = Strategy::handler0;
//}
//NOTICE: 2-triple case ?s1 p1 c0 ?s2 p2 c0 is viewed as an unconnected graph
//however, this can be dealed due to several basic queries and linking
bool
Strategy::handle(SPARQLquery& _query)
{
#ifdef MULTI_INDEX
Util::logging("IN GeneralEvaluation::handle");
vector<BasicQuery*>& queryList = _query.getBasicQueryVec();
// enumerate each BasicQuery and retrieve their variables' mapping entity in the VSTree.
vector<BasicQuery*>::iterator iter = queryList.begin();
for (; iter != queryList.end(); iter++)
if ((**iter).getEncodeBasicQueryResult()) {
this->method = -1;
vector<unsigned*>& result_list = (*iter)->getResultList();
//int select_var_num = (*iter)->getSelectVarNum();
//the num of vars needing to be joined, i.e. selectVarNum if only one triple
int varNum = (*iter)->getVarNum();
//all variables(not including pre vars)
int total_num = (*iter)->getTotalVarNum();
int pre_varNum = (*iter)->getPreVarNum();
int selected_pre_var_num = (*iter)->getSelectedPreVarNum();
int selected_var_num = (*iter)->getSelectVarNum();
//NOTICE: special case - query vertices only connected via same variables
//all constant triples will be viewed as unconnected, if a triple has no variable,
//then this triple is a BGP(no other triples in this BGP)
if (total_num == 0 && pre_varNum == 0) {
this->method = 5;
} else if ((*iter)->getTripleNum() == 1 && pre_varNum == 1) {
if (this->export_flag)
this->method = 6;
else
this->method = 4;
}
if (this->method < 0 && pre_varNum == 0 && (*iter)->getTripleNum() == 1) //only one triple and no predicates
{
//only one variable and one triple: ?s pre obj or sub pre ?o
if (total_num == 1) {
this->method = 1;
}
//only two vars: ?s pre ?o
else if (total_num == 2) {
if (varNum == 1) //the selected id should be 0
{
this->method = 2;
} else //==2
{
this->method = 3;
}
}
//cout << "this BasicQuery use query strategy 2" << endl;
//cout<<"Final result size: "<<(*iter)->getResultList().size()<<endl;
//continue;
}
if (this->method < 0) {
this->method = 0;
}
//QueryHandler dispatch;
//dispatch[0] = handler0;
cout << "run the method:" << this->method << endl;
switch (this->method) {
//BETTER: use function pointer array in C++ class
case 0:
//default:filter by vstree and then verified by join
this->handler0(*iter, result_list);
break;
case 1:
this->handler1(*iter, result_list);
break;
case 2:
this->handler2(*iter, result_list);
break;
case 3:
this->handler3(*iter, result_list);
break;
case 4:
this->handler4(*iter, result_list);
break;
case 5:
this->handler5(*iter, result_list);
break;
case 6:
this->handler6(*iter, result_list);
break;
default:
cout << "not support this method" << endl;
}
if (this->method == 6) {
cout << "BasicQuery -- Final result size: " << (*iter)->getResultList()[0][0] << endl;
(*iter)->getResultList().clear();
} else {
cout << "BasicQuery -- Final result size: " << (*iter)->getResultList().size() << endl;
}
}
#else
cout << "this BasicQuery use original query strategy" << endl;
//VSTREE:
//long tv_handle = Util::get_cur_time();
//(this->vstree)->retrieve(_query);
//cout << "after Retrieve, used " << (tv_retrieve - tv_handle) << "ms." << endl;
long tv_retrieve = Util::get_cur_time();
this->join = new Join(kvstore, pre2num, this->limitID_predicate, this->limitID_literal);
this->join->join_sparql(_query);
delete this->join;
long tv_join = Util::get_cur_time();
cout << "after Join, used " << (tv_join - tv_retrieve) << "ms." << endl;
#endif
Util::logging("OUT Strategy::handle");
return true;
}
bool
Strategy::pre_handler(BasicQuery* basic_query, KVstore* kvstore, TYPE_TRIPLE_NUM* pre2num,
TYPE_TRIPLE_NUM* pre2sub, TYPE_TRIPLE_NUM* pre2obj, bool* dealed_triple)
{
int triple_num = basic_query->getTripleNum();
int var_num = basic_query->getVarNum();
// use constant filter to estimate now many ffits exist
vector<int> estimate_num(var_num, 10000000);
cout << "start constant filter here " << endl << endl;
for (int _var_i = 0; _var_i < var_num; _var_i++) {
//filter before join here
int var_degree = basic_query->getVarDegree(_var_i);
IDList& _list = basic_query->getCandidateList(_var_i);
cout << "\tVar" << _var_i << " " << basic_query->getVarName(_var_i) << endl;
// this->basic_query->setReady(_var_i);
for (int j = 0; j < var_degree; j++) {
int neighbor_id = basic_query->getEdgeNeighborID(_var_i, j);
//-1: constant or variable not in join; otherwise, variable in join
if (neighbor_id != -1) {
continue;
}
char edge_type = basic_query->getEdgeType(_var_i, j);
int triple_id = basic_query->getEdgeID(_var_i, j);
Triple triple = basic_query->getTriple(triple_id);
string neighbor_name;
if (edge_type == Util::EDGE_OUT) {
neighbor_name = triple.object;
} else {
neighbor_name = triple.subject;
}
bool only_preid_filter = (basic_query->isOneDegreeNotJoinVar(neighbor_name));
//NOTICE: we only need to consider constants here
if (only_preid_filter) {
continue;
} else {
dealed_triple[triple_id] = true;
basic_query->setReady(_var_i);
}
TYPE_PREDICATE_ID pre_id = basic_query->getEdgePreID(_var_i, j);
TYPE_ENTITY_LITERAL_ID lit_id = (kvstore)->getIDByEntity(neighbor_name);
if (lit_id == INVALID_ENTITY_LITERAL_ID) {
lit_id = (kvstore)->getIDByLiteral(neighbor_name);
}
unsigned id_list_len = 0;
unsigned* id_list = NULL;
if (pre_id >= 0) {
if (edge_type == Util::EDGE_OUT) {
kvstore->getsubIDlistByobjIDpreID(lit_id, pre_id, id_list, id_list_len, true);
} else {
kvstore->getobjIDlistBysubIDpreID(lit_id, pre_id, id_list, id_list_len, true);
}
} else if (pre_id == -2) {
if (edge_type == Util::EDGE_OUT) {
kvstore->getsubIDlistByobjID(lit_id, id_list, id_list_len, true);
} else {
kvstore->getobjIDlistBysubID(lit_id, id_list, id_list_len, true);
}
} else {
id_list_len = 0;
}
//WARN: this may need to check, end directly
if (id_list_len == 0) {
_list.clear();
delete[] id_list;
return false;
}
//updateList(_list, id_list, id_list_len);
if (_list.size() == 0)
_list.unionList(id_list, id_list_len);
else
_list.intersectList(id_list, id_list_len);
delete[] id_list;
if (_list.size() == 0) {
return false;
}
}
// skip pre_filter when the candidate of a variable is small
// enough after constant_filter
if (_list.size() > 0) {
for (int j = 0; j < var_degree; j++) {
int neighbor_id = basic_query->getEdgeNeighborID(_var_i, j);
//-1: constant or variable not in join; otherwise, variable in join
if (neighbor_id == -1) {
continue;
}
TYPE_PREDICATE_ID pre_id = basic_query->getEdgePreID(_var_i, j);
char edge_type = basic_query->getEdgeType(_var_i, j);
int estimate_val;
if (edge_type == Util::EDGE_OUT)
estimate_val = _list.size() * pre2num[pre_id] / pre2sub[pre_id];
else
estimate_val = _list.size() * pre2num[pre_id] / pre2obj[pre_id];
if (estimate_val < estimate_num[neighbor_id])
estimate_num[neighbor_id] = estimate_val;
}
}
cout << "\t\t[" << _var_i << "] after constant filter, candidate size = " << _list.size() << endl << endl << endl;
}
cout << "pre filter start here" << endl;
//TODO:use vector instead of set
for (int _var = 0; _var < var_num; _var++) {
if (basic_query->isSatelliteInJoin(_var))
continue;
cout << "\tVar" << _var << " " << basic_query->getVarName(_var) << endl;
IDList& cans = basic_query->getCandidateList(_var);
unsigned size = basic_query->getCandidateSize(_var);
//result if already empty for non-literal variable
/*
if (size == 0)
{
if(!is_literal_var(_var))
return false;
else
return true;
}
*/
int var_degree = basic_query->getVarDegree(_var);
//NOTICE:maybe several same predicates
set<TYPE_PREDICATE_ID> in_edge_pre_id;
set<TYPE_PREDICATE_ID> out_edge_pre_id;
for (int i = 0; i < var_degree; i++) {
char edge_type = basic_query->getEdgeType(_var, i);
int triple_id = basic_query->getEdgeID(_var, i);
Triple triple = basic_query->getTriple(triple_id);
string neighbor;
if (edge_type == Util::EDGE_OUT) {
neighbor = triple.object;
} else {
neighbor = triple.subject;
}
//not consider edge with constant neighbors here
if (neighbor[0] != '?') {
//cout << "not to filter: " << neighbor_name << endl;
continue;
}
//else
//cout << "need to filter: " << neighbor_name << endl;
TYPE_PREDICATE_ID pre_id = basic_query->getEdgePreID(_var, i);
//WARN+BETTER:invalid(should be discarded in Query) or ?p(should not be considered here)
if (pre_id < 0) {
continue;
}
//size:m<n; time:mlgn < n-m
//The former time is computed because the m should be small if we select this p, tending to use binary-search
//when doing intersectList operation(mlgn < m+n).
//The latter time is computed due to the unnecessary copy cost if not using this p
//TYPE_TRIPLE_NUM border = size / (Util::logarithm(2, size) + 1);
//not use inefficient pre to filter
if (dealed_triple[triple_id]) {
continue;
}
double border = size / (Util::logarithm(2, size) + 1);
if (pre2num[pre_id] > border) {
cout << "skip the prefilter because the pre var is not efficent enough" << endl;
continue;
}
int prefilter_num;
if ((edge_type == Util::EDGE_OUT && (prefilter_num = pre2obj[pre_id]) > estimate_num[_var]) || (edge_type == Util::EDGE_IN && (prefilter_num = pre2sub[pre_id]) > estimate_num[_var])) {
cout << "skip the prefilter because the constant filter is strong enough" << endl;
// cout << "estimate_num:" << estimate_num[_var] << endl;
// cout << "prefilter_num:" << prefilter_num << endl;
continue;
}
if (basic_query->isOneDegreeVar(neighbor)) {
dealed_triple[triple_id] = true;
}
if (edge_type == Util::EDGE_OUT) {
out_edge_pre_id.insert(pre_id);
} else {
in_edge_pre_id.insert(pre_id);
}
}
if (in_edge_pre_id.empty() && out_edge_pre_id.empty()) {
continue;
}
basic_query->setReady(_var);
//NOTICE:use p2s here, use s2p in only_pre_filter_after_join because pres there are not efficient
set<TYPE_PREDICATE_ID>::iterator it;
unsigned* list = NULL;
unsigned len = 0;
for (it = in_edge_pre_id.begin(); it != in_edge_pre_id.end(); ++it) {
// if there exists a variable with limited matches in the query, then skip the filter of other
// variables as soon as possible
if (pre2num[*it] < 1000000 || cans.size() > 1000000 || cans.size() == 0) {
kvstore->getobjIDlistBypreID(*it, list, len, true);
if (cans.size() == 0)
cans.unionList(list, len);
else
cans.intersectList(list, len);
delete[] list;
if (cans.size() == 0) {
return false;
}
} else {
int can_size = cans.size();
for (std::vector<unsigned>::iterator i = cans.begin(); i != cans.end();) {
kvstore->getpreIDlistByobjID(*i, list, len, true);
bool can_matched = false;
int s = 0, e = len - 1;
int mid = (s + e) / 2;
while (s <= e) {
if (list[mid] == *it) {
can_matched = true;
break;
} else if (list[mid] < *it) {
s = mid + 1;
} else {
e = mid - 1;
}
mid = (s + e) / 2;
}
if (can_matched == false) {
i = cans.eraseAt(i);
} else {
i++;
}
}
}
}
if (in_edge_pre_id.size() != 0 && cans.size() == 0) {
// cout << "after in_edge_filter, the cans size = 0" << endl;
return false;
}
for (it = out_edge_pre_id.begin(); it != out_edge_pre_id.end(); ++it) {
// if there exists a variable with limited matches in the query, then skip the filter of other
// variables as soon as possible
if (pre2num[*it] < 1000000 || cans.size() > 1000000 || cans.size() == 0) {
kvstore->getsubIDlistBypreID(*it, list, len, true);
if (cans.size() == 0)
cans.unionList(list, len);
else
cans.intersectList(list, len);
delete[] list;
if (cans.size() == 0) {
return false;
}
} else {
int can_size = cans.size();
for (std::vector<unsigned>::iterator i = cans.begin(); i != cans.end();) {
kvstore->getpreIDlistBysubID(*i, list, len, true);
bool can_matched = false;
int s = 0, e = len - 1;
int mid = (s + e) / 2;
while (s <= e) {
if (list[mid] == *it) {
can_matched = true;
break;
} else if (list[mid] < *it) {
s = mid + 1;
} else {
e = mid - 1;
}
mid = (s + e) / 2;
}
if (can_matched == false) {
i = cans.eraseAt(i);
} else {
i++;
}
}
}
}
//this is a core vertex, so if not literal var, exit when empty
if (cans.empty()) {
return false;
}
cout << "\t\t[" << _var << "] after pre var filter, candidate size = " << cans.size() << endl << endl << endl;
}
return true;
}
void
Strategy::handler0(BasicQuery* _bq, vector<unsigned*>& _result_list)
{
//long before_filter = Util::get_cur_time();
cout << "this BasicQuery use query strategy 0" << endl;
//BETTER:not all vars in join filtered by vstree
//(A)-B-c: B should by vstree, then by c, but A should be generated in join(first set A as not)
//if A not in join, just filter B by pre
//divided into star graphs, join core vertices, generate satellites
//join should also start from a core vertex(neighbor can be constants or vars) if available
//
//QUERY: is there any case that a node should be retrieved by other index?(instead of vstree or generate whne join)
//
//we had better treat 1-triple case(no ?p) as special, and then in other cases, core vertex exist(if connected)
//However, if containing ?p and 1-triple, we should treat it also as a special case, or select a variable as core vertex
//and retrieved (for example, ?s ?p o or s ?p ?o, generally no core vertex in these cases)
long tv_handle = Util::get_cur_time();
int varNum = _bq->getVarNum(); //the num of vars needing to be joined
//TODO:parallel by pthread, requiring that index is parallelable
//for (int i = 0; i < varNum; ++i)
//{
//if (_bq->if_need_retrieve(i) == false)
//continue;
//bool flag = _bq->isLiteralVariable(i);
//const EntityBitSet& entityBitSet = _bq->getVarBitSet(i);
//IDList* idListPtr = &(_bq->getCandidateList(i));
//this->vstree->retrieveEntity(entityBitSet, idListPtr);
//if (!flag)
//{
//cout<<"set ready: "<<i<<endl;
//_bq->setReady(i);
//}
//the basic query should end if one non-literal var has no candidates
//if (idListPtr->size() == 0 && !flag)
//{
//break;
//}
//}
//BETTER:end directly if one is empty!
long tv_retrieve = Util::get_cur_time();
cout << "after Retrieve, used " << (tv_retrieve - tv_handle) << "ms." << endl;
bool* d_triple = (bool*)calloc(_bq->getTripleNum(), sizeof(bool));
bool ret2 = pre_handler(_bq, kvstore, pre2num, pre2sub, pre2obj, d_triple);
long after_prehandler = Util::get_cur_time();
cout << "after prehandler: used " << (after_prehandler - tv_retrieve) << " ms" << endl;
if (!ret2) {
cout << "after the prehandler, the canlist size is 0." << endl;
}
Join* join = new Join(kvstore, pre2num, this->limitID_predicate, this->limitID_literal, this->limitID_entity);
join->join_basic(_bq, d_triple);
delete join;
long tv_join = Util::get_cur_time();
cout << "after Join, used " << (tv_join - tv_retrieve) << "ms." << endl;
}
void
Strategy::handler1(BasicQuery* _bq, vector<unsigned*>& _result_list)
{
long before_filter = Util::get_cur_time();
cout << "this BasicQuery use query strategy 1" << endl;
//int neighbor_id = (*_bq->getEdgeNeighborID(0, 0); //constant, -1
char edge_type = _bq->getEdgeType(0, 0);
int triple_id = _bq->getEdgeID(0, 0);
Triple triple = _bq->getTriple(triple_id);
TYPE_PREDICATE_ID pre_id = _bq->getEdgePreID(0, 0);
unsigned* id_list = NULL;
unsigned id_list_len = 0;
if (edge_type == Util::EDGE_OUT) {
//cout<<"edge out!!!"<<endl;
TYPE_ENTITY_LITERAL_ID nid = (this->kvstore)->getIDByEntity(triple.object);
//if (nid == -1)
if (nid == INVALID_ENTITY_LITERAL_ID) {
nid = (this->kvstore)->getIDByLiteral(triple.object);
}
this->kvstore->getsubIDlistByobjIDpreID(nid, pre_id, id_list, id_list_len);
} else {
//cout<<"edge in!!!"<<endl;
this->kvstore->getobjIDlistBysubIDpreID(this->kvstore->getIDByEntity(triple.subject), pre_id, id_list, id_list_len);
}
long after_filter = Util::get_cur_time();
cout << "after filter, used " << (after_filter - before_filter) << "ms" << endl;
_result_list.clear();
//cout<<"now to copy result to list"<<endl;
for (unsigned i = 0; i < id_list_len; ++i) {
unsigned* record = new unsigned[1]; //only this var is selected
record[0] = id_list[i];
//cout<<this->kvstore->getEntityByID(record[0])<<endl;
_result_list.push_back(record);
}
long after_copy = Util::get_cur_time();
cout << "after copy to result list: used " << (after_copy - after_filter) << " ms" << endl;
delete[] id_list;
cout << "Final result size: " << _result_list.size() << endl;
}
void
Strategy::handler2(BasicQuery* _bq, vector<unsigned*>& _result_list)
{
long before_filter = Util::get_cur_time();
cout << "this BasicQuery use query strategy 2" << endl;
int triple_id = _bq->getEdgeID(0, 0);
Triple triple = _bq->getTriple(triple_id);
TYPE_PREDICATE_ID pre_id = _bq->getEdgePreID(0, 0);
//NOTICE:it is ok for var1 or var2 to be -1, i.e. not encoded
int var1_id = _bq->getIDByVarName(triple.subject);
int var2_id = _bq->getIDByVarName(triple.object);
unsigned* id_list = NULL;
unsigned id_list_len = 0;
if (var1_id == 0) //subject var selected
{
//use p2s directly
this->kvstore->getsubIDlistBypreID(pre_id, id_list, id_list_len);
} else if (var2_id == 0) //object var selected
{
//use p2o directly
this->kvstore->getobjIDlistBypreID(pre_id, id_list, id_list_len);
} else {
cout << "ERROR in Database::handle(): no selected var!" << endl;
}
long after_filter = Util::get_cur_time();
cout << "after filter, used " << (after_filter - before_filter) << "ms" << endl;
_result_list.clear();
for (unsigned i = 0; i < id_list_len; ++i) {
unsigned* record = new unsigned[1]; //only one var
record[0] = id_list[i];
_result_list.push_back(record);
}
long after_copy = Util::get_cur_time();
cout << "after copy to result list: used " << (after_copy - after_filter) << " ms" << endl;
delete[] id_list;
cout << "Final result size: " << _result_list.size() << endl;
}
void
Strategy::handler3(BasicQuery* _bq, vector<unsigned*>& _result_list)
{
long before_filter = Util::get_cur_time();
cout << "this BasicQuery use query strategy 3" << endl;
int triple_id = _bq->getEdgeID(0, 0);
Triple triple = _bq->getTriple(triple_id);
TYPE_PREDICATE_ID pre_id = _bq->getEdgePreID(0, 0);
unsigned* id_list = NULL;
unsigned id_list_len = 0;
_result_list.clear();
this->kvstore->getsubIDobjIDlistBypreID(pre_id, id_list, id_list_len);
int var1_id = _bq->getSelectedVarPosition(triple.subject);
int var2_id = _bq->getSelectedVarPosition(triple.object);
if (var1_id < 0 || var2_id < 0) {
delete[] id_list;
return;
}
long after_filter = Util::get_cur_time();
cout << "after filter, used " << (after_filter - before_filter) << "ms" << endl;
for (unsigned i = 0; i < id_list_len; i += 2) {
unsigned* record = new unsigned[2]; //2 vars and selected
record[var1_id] = id_list[i];
record[var2_id] = id_list[i + 1];
_result_list.push_back(record);
}
long after_copy = Util::get_cur_time();
cout << "after copy to result list: used " << (after_copy - after_filter) << " ms" << endl;
delete[] id_list;
cout << "Final result size: " << _result_list.size() << endl;
}
void
Strategy::handler4(BasicQuery* _bq, vector<unsigned*>& _result_list)
{
cout << "Special Case: consider pre var in this triple" << endl;
int varNum = _bq->getVarNum();
//all variables(not including pre vars)
int total_num = _bq->getTotalVarNum();
int pre_varNum = _bq->getPreVarNum();
int selected_pre_var_num = _bq->getSelectedPreVarNum();
int selected_var_num = _bq->getSelectVarNum();
Triple triple = _bq->getTriple(0);
int pvpos = _bq->getSelectedPreVarPosition(triple.predicate);
unsigned* id_list = NULL;
unsigned id_list_len = 0;
_result_list.clear();
//cout<<"total num: "<<total_num <<endl;
if (total_num == 2) {
cout << "Special Case 1" << endl;
int svpos = _bq->getSelectedVarPosition(triple.subject);
int ovpos = _bq->getSelectedVarPosition(triple.object);
cout << "subject: " << triple.subject << " " << svpos << endl;
cout << "object: " << triple.object << " " << ovpos << endl;
cout << "predicate: " << triple.predicate << " " << pvpos << endl;
//very special case, to find all triples, select ?s (?p) ?o where { ?s ?p ?o . }
//filter and join is too costly, should enum all predicates and use p2so
for (TYPE_PREDICATE_ID i = 0; i < this->limitID_predicate; ++i) {
TYPE_PREDICATE_ID pid = i;
this->kvstore->getsubIDobjIDlistBypreID(pid, id_list, id_list_len);
int rsize = selected_var_num;
if (selected_pre_var_num == 1) {
rsize++;
}
//always place s/o before p in result list
for (unsigned j = 0; j < id_list_len; j += 2) {
unsigned* record = new unsigned[rsize];
//check the s/o var if selected, need to ensure the placement order
if (ovpos >= 0) {
record[ovpos] = id_list[j + 1];
}
if (svpos >= 0) {
record[svpos] = id_list[j];
}
if (pvpos >= 0) {
record[pvpos] = pid; //for the pre var
}
_result_list.push_back(record);
}
delete[] id_list;
}
id_list = NULL;
} else if (total_num == 1) {
cout << "Special Case 2" << endl;
int vpos = -1;
if (triple.subject[0] != '?') //constant
{
TYPE_ENTITY_LITERAL_ID sid = (this->kvstore)->getIDByEntity(triple.subject);
this->kvstore->getpreIDobjIDlistBysubID(sid, id_list, id_list_len);
vpos = _bq->getSelectedVarPosition(triple.object);
} else if (triple.object[0] != '?') //constant
{
TYPE_ENTITY_LITERAL_ID oid = (this->kvstore)->getIDByEntity(triple.object);
//if (oid == -1)
if (oid == INVALID_ENTITY_LITERAL_ID) {
oid = (this->kvstore)->getIDByLiteral(triple.object);
}
this->kvstore->getpreIDsubIDlistByobjID(oid, id_list, id_list_len);
vpos = _bq->getSelectedVarPosition(triple.subject);
}
int rsize = varNum;
if (selected_pre_var_num == 1) {
rsize++;
}
//always place s/o before p in result list
for (unsigned i = 0; i < id_list_len; i += 2) {
unsigned* record = new unsigned[rsize];
if (vpos >= 0) {
record[vpos] = id_list[i + 1]; //for the s/o var
}
if (pvpos >= 0) {
record[pvpos] = id_list[i]; //for the pre var
}
_result_list.push_back(record);
}
} else if (total_num == 0) //only ?p and it must be selected
{
cout << "Special Case 3" << endl;
//just use so2p
unsigned sid = (this->kvstore)->getIDByEntity(triple.subject);
unsigned oid = (this->kvstore)->getIDByEntity(triple.object);
if (oid == -1) {
oid = (this->kvstore)->getIDByLiteral(triple.object);
}
this->kvstore->getpreIDlistBysubIDobjID(sid, oid, id_list, id_list_len);
//copy to result list
for (unsigned i = 0; i < id_list_len; ++i) {
unsigned* record = new unsigned[1];
record[0] = id_list[i];
_result_list.push_back(record);
}
}
delete[] id_list;
}
//TODO:if any constants in a query are not found in kvstore, then this BGP should end to speed up the processing
void
Strategy::handler5(BasicQuery* _bq, vector<unsigned*>& _result_list)
{
cout << "Special Case: consider constant triple" << endl;
Triple triple = _bq->getTriple(0);
_result_list.clear();
TYPE_ENTITY_LITERAL_ID subid = this->kvstore->getIDByEntity(triple.subject);
//if(subid == -1) //not found
if (subid == INVALID_ENTITY_LITERAL_ID) //not found
{
return;
}
TYPE_PREDICATE_ID preid = this->kvstore->getIDByPredicate(triple.predicate);
//if(preid == -1) //not found
if (preid == INVALID_PREDICATE_ID) //not found
{
return;
}
TYPE_ENTITY_LITERAL_ID objid = this->kvstore->getIDByEntity(triple.object);
//if(objid == -1)
if (objid == INVALID_ENTITY_LITERAL_ID) {
objid = this->kvstore->getIDByLiteral(triple.object);
}
//if(objid == -1)
if (objid == INVALID_ENTITY_LITERAL_ID) {
return;
}
unsigned* id_list = NULL;
unsigned id_list_len = 0;
(this->kvstore)->getobjIDlistBysubIDpreID(subid, preid, id_list, id_list_len);
if (Util::bsearch_int_uporder(objid, id_list, id_list_len) != INVALID) {
unsigned* record = new unsigned[3];
record[0] = subid;
record[1] = preid;
record[2] = objid;
_result_list.push_back(record);
}
delete[] id_list;
}
void
Strategy::handler6(BasicQuery* _bq, vector<unsigned*>& _result_list)
{
cout << "Special Case:select * and write to stream" << endl;
int varNum = _bq->getVarNum();
//all variables(not including pre vars)
int total_num = _bq->getTotalVarNum();
int pre_varNum = _bq->getPreVarNum();
int selected_pre_var_num = _bq->getSelectedPreVarNum();
int selected_var_num = _bq->getSelectVarNum();
Triple triple = _bq->getTriple(0);
int pvpos = _bq->getSelectedPreVarPosition(triple.predicate);
unsigned* id_list = NULL;
unsigned id_list_len = 0;
_result_list.clear();
int svpos = _bq->getSelectedVarPosition(triple.subject);
int ovpos = _bq->getSelectedVarPosition(triple.object);
cout << "subject: " << triple.subject << " " << svpos << endl;
cout << "object: " << triple.object << " " << ovpos << endl;
cout << "predicate: " << triple.predicate << " " << pvpos << endl;
//very special case, to find all triples, select ?s (?p) ?o where { ?s ?p ?o . }
//filter and join is too costly, should enum all predicates and use p2so
unsigned* rsize = new unsigned[1];
rsize[0] = 0;
for (TYPE_PREDICATE_ID i = 0; i < this->limitID_predicate; ++i) {
TYPE_PREDICATE_ID pid = i;
string p = this->kvstore->getPredicateByID(pid);
string pre = Util::node2string(p.c_str());
this->kvstore->getsubIDobjIDlistBypreID(pid, id_list, id_list_len);
for (unsigned j = 0; j < id_list_len; j += 2) {
string s = this->kvstore->getEntityByID(id_list[j]);
string sub = Util::node2string(s.c_str());
string o;
if (id_list[j + 1] >= Util::LITERAL_FIRST_ID)
o = this->kvstore->getLiteralByID(id_list[j + 1]);
else
o = this->kvstore->getEntityByID(id_list[j + 1]);
string obj = Util::node2string(o.c_str());
string record = sub + "\t" + pre + "\t" + obj + ".\n";
fprintf(this->fp, "%s", record.c_str());
rsize[0] += 1;
}
delete[] id_list;
}
id_list = NULL;
_result_list.push_back(rsize);
}
Reference in New Issue View Git Blame Copy Permalink