diff -crN pgsql/contrib/fulldisjunctions/algstructs.c pgsql-fd/contrib/fulldisjunctions/algstructs.c *** pgsql/contrib/fulldisjunctions/algstructs.c 1969-12-31 19:00:00.000000000 -0500 --- pgsql-fd/contrib/fulldisjunctions/algstructs.c 2006-07-30 15:28:47.000000000 -0400 *************** *** 0 **** --- 1,1071 ---- + /* + * Copyright (c) 2006 Itzhak Fadida. All Rights Reserved. + * See the README file for a detailed BSD License. + * This file and all related files are under the BSD license. + * */ + + #include "postgres.h" + #include + #include + #include "algstructs.h" + #include "queues.h" + #include "queuesfuncs.h" + #include "algutils.h" + #include "catalog/pg_namespace.h" + #include "utils/memutils.h" + #include "parser/parse_coerce.h" + + /* a helper function to convert time var to pretty text time */ + static char * + str_time(time_t tnow) + { + static char buf[128]; + + strftime(buf, sizeof(buf), "%Y-%m-%d %H:%M:%S %Z", localtime(&tnow)); + return buf; + } + + /* here we parse the relations parameter the user gives + * into a list of Oid of these tables */ + Oid * + parseOIDs(text *relsStr, int *numOfRels) + { + if (relsStr == NULL) + elog(ERROR, "Something is wrong with the relations inputed"); + + int relsStrSize = VARATT_SIZEP(relsStr) - VARHDRSZ + 1; + char relsStrCp[relsStrSize]; + + memcpy(relsStrCp, VARDATA(relsStr), relsStrSize - 1); + relsStrCp[relsStrSize - 1] = (char) NULL; + return parseOIDs_(relsStrCp, numOfRels); + } + + /* we just convert text to str */ + char * + getRelsCharStr(text *relsStr) + { + if (relsStr == NULL) + elog(ERROR, "Something is wrong with the relations inputed"); + int relsStrSize = VARATT_SIZEP(relsStr) - VARHDRSZ + 1; + char *relsStrCp = (char *) palloc(relsStrSize * sizeof(char)); + + memcpy(relsStrCp, VARDATA(relsStr), relsStrSize - 1); + relsStrCp[relsStrSize - 1] = (char) NULL; + return relsStrCp; + } + + /* here we parse the relations into a list of its Oids */ + Oid * + parseOIDs_(char *relsStrCp, int *numOfRels) + { + Oid oids[MaxHeapAttributeNumber]; + const char delimiters[] = ","; + const char tokenDelimiters[] = "."; + char *token = NULL; + char *relsStrSvpt = NULL; + char *tokenSvpt = NULL; + + token = strtok_r(relsStrCp, delimiters, &relsStrSvpt); + + char *namespace = NULL; + char *relname = NULL; + int i = -1; + Oid namespaceId = -1; + + while (token != NULL) + { + namespace = strtok_r(token, tokenDelimiters, &tokenSvpt); + relname = strtok_r(NULL, tokenDelimiters, &tokenSvpt); + if (relname == NULL) + { + relname = namespace; + namespace = NULL; + } + if (relname == NULL) + elog(ERROR, "Something is wrong with the relations inputed, check delimiters , and ."); + i++; + if (namespace != NULL) + namespaceId = GetSysCacheOid(NAMESPACENAME, + CStringGetDatum(namespace), 0, 0, 0); + else + namespaceId = PG_PUBLIC_NAMESPACE; + if (!OidIsValid(namespaceId)) + elog(ERROR, "Something is wrong with the relations inputed\ + ,possibly no such namespace "); + if (!OidIsValid(oids[i] = get_relname_relid(relname, namespaceId))) + elog(ERROR, "Something is wrong with the relations inputed, not such namespace or\ + no such relation "); + token = strtok_r(NULL, delimiters, &relsStrSvpt); + } + *numOfRels = i + 1; + Oid *relsOID = (Oid *) palloc(*numOfRels * sizeof(Oid)); + + for (i = 0; i < *numOfRels; i++) + relsOID[i] = oids[i]; + return relsOID; + } + + /* Here we pass the inputted mapping parameter into a Dictionary (see .h file */ + Dictionary * + parseAttributeDictionary(char *mappingStrCp, Oid *relsOid, int numOfRels) + { + int i, + j; + int numAtts[numOfRels]; + int maxNumAtts = 0; + char *attName; + int numPotentialAttNames = 0; + Mapping ***relsAttsMappings = (Mapping ***) palloc(numOfRels * sizeof(Mapping **)); + int *numMappings = (int *) palloc(numOfRels * sizeof(int)); + + for (i = 0; i < numOfRels; i++) + { + numAtts[i] = 0; + numMappings[i] = 0; + HeapTuple attTuple; + + for (j = 1;; j++) + { + attName = (char *) get_attname(relsOid[i], j); + if (attName != NULL) + { + attTuple = SearchSysCacheAttName(relsOid[i], attName); + if (attTuple != NULL) + { + ReleaseSysCache(attTuple); + numAtts[i]++; + } + } + else + break; + } + maxNumAtts += numAtts[i]; + relsAttsMappings[i] = (Mapping **) palloc(numAtts[i] * sizeof(Mapping *)); + } + + char *resultTuplePotentialAttNames[maxNumAtts]; + const char delimiters[] = ","; + const char tokenDelimiters[] = "=."; + char *token = NULL; + char *mappingStrSvpt = NULL; + char *tokenSvpt = NULL; + + token = strtok_r(mappingStrCp, delimiters, &mappingStrSvpt); + char *namespace = NULL; + char *relname = NULL; + char *resultTupleAttName; + char *relAttName; + + i = -1; + Oid namespaceId = -1; + Oid relOid = -1; + int relid; + + while (token != NULL) + { + resultTupleAttName = strtok_r(token, tokenDelimiters, &tokenSvpt); + if (resultTupleAttName == NULL) + elog(ERROR, "problem parsing mapping string! check your format. e.g lastname=public.rel1.username"); + namespace = strtok_r(NULL, tokenDelimiters, &tokenSvpt); + if (namespace == NULL) + elog(ERROR, "problem parsing mapping string! check your format. e.g lastname=public.rel1.username"); + relname = strtok_r(NULL, tokenDelimiters, &tokenSvpt); + if (relname == NULL) + elog(ERROR, "problem parsing mapping string! check your format. e.g lastname=public.rel1.username"); + relAttName = strtok_r(NULL, tokenDelimiters, &tokenSvpt); + if (relAttName == NULL) + elog(ERROR, "problem parsing mapping string! check your format. e.g lastname=public.rel1.username"); + if (namespace != NULL) + namespaceId = GetSysCacheOid(NAMESPACENAME, + CStringGetDatum(namespace), 0, 0, 0); + if (!OidIsValid(namespaceId)) + elog(ERROR, "Something is wrong with the relations inputed\ + ,possibly no such namespace %s ", namespace); + if (!OidIsValid(relOid = get_relname_relid(relname, namespaceId))) + elog(ERROR, "Something is wrong with the relations inputed, not such namespace or\ + no such relation: %s ", relname); + HeapTuple attTuple = SearchSysCacheAttName(relOid, relAttName); + + if (attTuple != NULL) + ReleaseSysCache(attTuple); + else + elog(ERROR, "Something is wrong with the relations inputed, not such namespace or\ + no such relation or no such att:%s ", relAttName); + + relid = -1; + for (i = 0; i < numOfRels; i++) + { + if (relOid == relsOid[i]) + { + relid = i; + break; + } + } + if (relid == -1) + elog(ERROR, "No such relation - %s.%s - in the inputted relations", namespace, relname); + int nameLocation = -1; + + for (i = 0; i < numPotentialAttNames; i++) + if (strcmp(resultTuplePotentialAttNames[i], resultTupleAttName) == 0) + { + nameLocation = i; + break; + } + if (nameLocation == -1) + { + resultTuplePotentialAttNames[numPotentialAttNames] = resultTupleAttName; + nameLocation = numPotentialAttNames; + numPotentialAttNames++; + } + + Mapping *mapping = palloc(sizeof(Mapping)); + + mapping->resultTuplePotnetialAttNamesID = nameLocation; + mapping->relAttName = relAttName; + relsAttsMappings[relid][numMappings[relid]] = mapping; + numMappings[relid]++; + token = strtok_r(NULL, delimiters, &mappingStrSvpt); + } + Dictionary *dictionary = palloc(sizeof(Dictionary)); + + dictionary->resultTuplePotentialAttNames = palloc(numPotentialAttNames * sizeof(char *)); + + for (i = 0; i < numPotentialAttNames; i++) + dictionary->resultTuplePotentialAttNames[i] = resultTuplePotentialAttNames[i]; + + dictionary->numPotentialAttNames = numPotentialAttNames; + dictionary->relsAttsMappings = relsAttsMappings; + dictionary->numMappings = numMappings; + + int k; + for (i = 0; i < numOfRels; i++) + for (j = 0; j < numMappings[i]; j++) + { + for (k = 0; k < numMappings[i]; k++) + if ((j != k) && + (strcmp(resultTuplePotentialAttNames[relsAttsMappings[i][j]->resultTuplePotnetialAttNamesID], + relsAttsMappings[i][k]->relAttName) == 0)) + elog(ERROR, "circular mappings:%s,%s", + resultTuplePotentialAttNames[relsAttsMappings[i][j]->resultTuplePotnetialAttNamesID], + relsAttsMappings[i][k]->relAttName); + if (strcmp(resultTuplePotentialAttNames[relsAttsMappings[i][j]->resultTuplePotnetialAttNamesID], + relsAttsMappings[i][j]->relAttName) != 0) + { + HeapTuple attTuple = SearchSysCacheAttName(relsOid[i], + resultTuplePotentialAttNames[relsAttsMappings[i][j]->resultTuplePotnetialAttNamesID]); + + if (attTuple != NULL) + { + ReleaseSysCache(attTuple); + elog(ERROR, "circular mappings:%s", + resultTuplePotentialAttNames[relsAttsMappings[i][j]->resultTuplePotnetialAttNamesID]); + } + } + } + return dictionary; + } + + /* we take a dictionary and map an attribute name from a relation + * to another name using the dictionary */ + char * + mapAttName(Dictionary * dictionary, int relid, char *attname) + { + if (dictionary == NULL) + return attname; + else + { + int i; + int numMappings = dictionary->numMappings[relid]; + Mapping *mapping = NULL; + + if (numMappings == 0) + return attname; + for (i = 0; i < numMappings; i++) + { + mapping = dictionary->relsAttsMappings[relid][i]; + if (strcmp(mapping->relAttName, attname) == 0) + { + return dictionary->resultTuplePotentialAttNames[mapping->resultTuplePotnetialAttNamesID]; + } + } + return attname; + } + } + + /* just a convinience call */ + void + initialize_general_structures(PG_FUNCTION_ARGS, alg_fctx * fctx, FuncCallContext *funcctx) + { + initialize_general_structures_(fcinfo, fctx, true, funcctx); + } + + /* initialized the fd general required structures */ + void + initialize_general_structures_(PG_FUNCTION_ARGS, alg_fctx * fctx, bool parsing, FuncCallContext *funcctx) + { + unsigned int tmpTime = (unsigned) time(NULL); + + srand(tmpTime); + + #ifdef DEBUG + ereport(LOG, (errmsg(" "))); + ereport(LOG, (errmsg("FD-DEBUG: %s", str_time(time(NULL))))); + ereport(LOG, (errmsg("FD-DEBUG-SRAND:%d", tmpTime))); + ereport(LOG, (errmsg("FD-DEBUG-Relations:%s", getRelsCharStr(PG_GETARG_TEXT_P(0))))); + #endif + + fctx->per_query_ctx = AllocSetContextCreate(CurrentMemoryContext, + "tuplestore2", + ALLOCSET_DEFAULT_MINSIZE, + ALLOCSET_DEFAULT_INITSIZE, + ALLOCSET_DEFAULT_MAXSIZE); + fctx->nargs = PG_NARGS(); + char *mappingStr = NULL; + + if (fctx->nargs >= 1) + { + char *policy = NULL; + + switch (fctx->nargs) + { + case 9: + case 8: + case 7: + case 6: + case 5: + { + text *policyText = PG_GETARG_TEXT_P(4); + int policyTextSize = VARATT_SIZEP(policyText) - VARHDRSZ; + + if (policyTextSize == 0) + policy = NULL; + else + { + policy = (char *) palloc(policyTextSize * sizeof(char) + 1); + memcpy(policy, VARDATA(policyText), policyTextSize); + policy[policyTextSize] = '\0'; + } + } + case 4: + fctx->noIndexScans = PG_GETARG_BOOL(3); + case 3: + if (fctx->nargs <= 3) + fctx->noIndexScans = false; + fctx->noDuplicates = PG_GETARG_BOOL(2); + case 2: + { + text *mappingText = PG_GETARG_TEXT_P(1); + int mappingTextSize = VARATT_SIZEP(mappingText) - VARHDRSZ; + + if (mappingTextSize > 0) + { + mappingStr = (char *) palloc(mappingTextSize * sizeof(char) + 1); + memcpy(mappingStr, VARDATA(mappingText), mappingTextSize); + mappingStr[mappingTextSize] = '\0'; + } + } + case 1: + if (fctx->nargs <= 2) + { + fctx->noIndexScans = false; + fctx->noDuplicates = true; + } + } + #ifdef DEBUG + if (policy != NULL) + ereport(LOG, (errmsg("FD-DEBUG-Policy:%s", policy))); + #endif + fctx->query = NULL; + fctx->querySize = 0; + fctx->queryParams = NULL; + fctx->queryParamsTypes = NULL; + fctx->queryParamsSize = 0; + + fctx->policyWorkNode = NULL; + fctx->policySequence = 0; + fctx->extendingPolicy = -1; + if ((policy != NULL) && strcmp(policy, "majority") == 0) + fctx->extendingPolicy = POLICY_MAJORITY; + else if ((policy != NULL) && strcmp(policy, "mincost") == 0) + fctx->extendingPolicy = POLICY_MINCOST; + else if ((policy != NULL) && strcmp(policy, "random") == 0) + fctx->extendingPolicy = POLICY_RANDOM; + else if ((policy != NULL) && strcmp(policy, "naive") == 0) + fctx->extendingPolicy = POLICY_NAIVE; + else + { + if (policy != NULL) + elog(ERROR, "No such policy:%s", policy); + fctx->extendingPolicy = POLICY_MAJORITY; + } + if (policy != NULL) + pfree(policy); + } + + int i = 0, + j = 0, + k = 0; + char *attName = NULL; + + { + if (parsing) + fctx->relsOid = parseOIDs(PG_GETARG_TEXT_P(0), &fctx->numRels); + fctx->relsPages = (int *) palloc(fctx->numRels * sizeof(int)); + fctx->relsHasIndex = (bool *) palloc(fctx->numRels * sizeof(bool)); + fctx->sortedRelsByRelsPages = (int *) palloc(fctx->numRels * sizeof(int)); + + fctx->relsMaxTupleSize = (int *) palloc(fctx->numRels * sizeof(int)); + for (i = 0; i < fctx->numRels; i++) + fctx->relsMaxTupleSize[i] = 0; + + fctx->relsNAtt = (int *) palloc(fctx->numRels * sizeof(int)); + fctx->relsAttNumsAtTupleSet + = (int **) palloc(fctx->numRels * sizeof(int *)); + fctx->relsAttTypes = (Oid **) palloc(fctx->numRels * sizeof(Oid *)); + fctx->resultTupleAttNames = NULL; + fctx->tupleSetAttTypes = NULL; + + fctx->resultTupleDesc = NULL; + fctx->tupleSetDesc = NULL; + + fctx->resultTupleNAtt = 0; + fctx->tupleSetMaxSize = RESULT_TUPLE_ASSUMED_MAX_SIZE_IN_BYTES; + fctx->assumingResultTupleMaxSize = true; + fctx->relsValidAttNumAtRelation = (int **) palloc(fctx->numRels * sizeof(int *)); + + fctx->bits_scheme_graph = (RBITS *) palloc(fctx->numRels * sizeof(RBITS)); + + fctx->dynamic_extend_cap = (adaptive_extend_upperbound *) palloc(sizeof(adaptive_extend_upperbound)); + fctx->dynamic_extend_cap->previousScore = 0; + fctx->dynamic_extend_cap->nextUpperBound = 0; + fctx->dynamic_extend_cap->stage = 0; + fctx->dynamic_extend_cap->maxInputedExtendTuples = 0; + + fctx->printedTSet = NULL; + fctx->startedPrintingQueue = false; + fctx->printedTupleAddress = NULL; + } + + /* sort the array of relations, i.e. their oids */ + sortOidArray(fctx->relsOid, fctx->numRels); + + /* Lets parse the dictionary. */ + if (mappingStr == NULL) + { + fctx->dictionary = NULL; + } + else + fctx->dictionary = parseAttributeDictionary(mappingStr, fctx->relsOid, fctx->numRels); + + /* get each rel number of pages. */ + { + Form_pg_class pgcform; + HeapTuple ctup; + int tmpRelsPages[fctx->numRels]; + + for (i = 0; i < fctx->numRels; i++) + { + ctup = SearchSysCache(RELOID, + ObjectIdGetDatum(fctx->relsOid[i]), + 0, 0, 0); + pgcform = (Form_pg_class) GETSTRUCT(ctup); + fctx->relsHasIndex[i] = pgcform->relhasindex; + fctx->relsPages[i] = pgcform->relpages; + ReleaseSysCache(ctup); + tmpRelsPages[i] = fctx->relsPages[i]; + fctx->sortedRelsByRelsPages[i] = i; + } + + /* + * Here we create a sorted array of the relations, sorted by the + * number of pages they contain. + */ + int swapint; + + for (i = 0; i < (fctx->numRels - 1); i++) + for (j = (i + 1); j < fctx->numRels; j++) + if (tmpRelsPages[i] > tmpRelsPages[j]) + { + swapint = tmpRelsPages[i]; + tmpRelsPages[i] = tmpRelsPages[j]; + tmpRelsPages[j] = swapint; + swapint = fctx->sortedRelsByRelsPages[i]; + fctx->sortedRelsByRelsPages[i] = fctx->sortedRelsByRelsPages[j]; + fctx->sortedRelsByRelsPages[j] = swapint; + } + } + + /* + * here we get the number of attributes for each relation And we also + * creating the resultTuple Attribute names. we exploit the fact that + * attributes of relations that are first in the order comes first in the + * result tuple so do not change that! + */ + { + int relsValidAttNumAtRelation[MaxHeapAttributeNumber]; + bool foundAtt = 0; + bool skipped = false; + char *mappedAttName = NULL; + + fctx->resultTupleAttNames = (char **) palloc(MaxHeapAttributeNumber * sizeof(char *)); + for (i = 0; i < fctx->numRels; i++) + { + fctx->relsNAtt[i] = 0; + for (j = 1;; j++) + { + attName = (char *) get_attname(fctx->relsOid[i], j); + skipped = false; + if (attName != NULL) + { + /* + * here we check if an attribute was dropped by using the + * special SearchSysCacheAttName + */ + HeapTuple attTuple = SearchSysCacheAttName(fctx->relsOid[i], attName); + + if (attTuple != NULL) + ReleaseSysCache(attTuple); + else + { + pfree(attName); + attName = NULL; + skipped = true; + } + } + /* Ok so the attribute is valid. For example, an attribute of dropped + * column is not valid.*/ + if (attName != NULL) + { + relsValidAttNumAtRelation[fctx->relsNAtt[i]] = j; + fctx->relsNAtt[i]++; + foundAtt = 0; + /* lets map the attribute of the relation using the mappings entered + * by the user */ + mappedAttName = mapAttName(fctx->dictionary, i, attName); + /* let us see if we already added this attribute to the result tuple */ + for (k = 0; k < fctx->resultTupleNAtt; k++) + { + if (strcmp(fctx->resultTupleAttNames[k], mappedAttName) == 0) + { + foundAtt = 1; + break; + } + } + if (!foundAtt) + { + fctx->resultTupleAttNames[fctx->resultTupleNAtt] = mappedAttName; + fctx->resultTupleNAtt++; + } + } + else if (!skipped) + break; + } + fctx->relsValidAttNumAtRelation[i] = (int *) palloc(fctx->relsNAtt[i] * sizeof(int)); + for (j = 0; j < fctx->relsNAtt[i]; j++) + fctx->relsValidAttNumAtRelation[i][j] = relsValidAttNumAtRelation[j]; + } + fctx->tupleSetNatt = fctx->resultTupleNAtt + 1; + } + + /* lets free the wasted resources. */ + { + char **resultTupleAttNamesTemp + = (char **) palloc(fctx->resultTupleNAtt * sizeof(char *)); + + for (k = 0; k < fctx->resultTupleNAtt; k++) + { + resultTupleAttNamesTemp[k] = fctx->resultTupleAttNames[k]; + } + pfree(fctx->resultTupleAttNames); + fctx->resultTupleAttNames = resultTupleAttNamesTemp; + } + + /* + * here we get the types of each attribute in each relation. And we also + * assign the location of each attribute in each relation in the result + * tuple, in their respective relation search table. + */ + { + char *mappedAttName = NULL; + + for (i = 0; i < fctx->numRels; i++) + { + fctx->relsAttNumsAtTupleSet[i] + = (int *) palloc(fctx->relsNAtt[i] * sizeof(int)); + fctx->relsAttTypes[i] = (Oid *) palloc(fctx->relsNAtt[i] * sizeof(Oid)); + for (j = 0; j < fctx->relsNAtt[i]; j++) + { + fctx->relsAttTypes[i][j] = get_atttype(fctx->relsOid[i], fctx->relsValidAttNumAtRelation[i][j]); + attName = (char *) get_attname(fctx->relsOid[i], fctx->relsValidAttNumAtRelation[i][j]); + mappedAttName = mapAttName(fctx->dictionary, i, attName); + for (k = 0; k < fctx->resultTupleNAtt; k++) + { + if (strcmp(fctx->resultTupleAttNames[k], mappedAttName) == 0) + { + fctx->relsAttNumsAtTupleSet[i][j] = k + 1; + break; + } + } + } + } + } + + /* + * Here we create a sorted relsAttNumsAtTupleSet by a key of the order of + * the tuple set attribute positions per relation + */ + int ***sortedRelsAttNumsAtTupleSet + = (int ***) palloc(fctx->numRels * sizeof(int **)); + + { + int min, + minAttNum = -1, + curr; + + for (i = 0; i < fctx->numRels; i++) + { + sortedRelsAttNumsAtTupleSet[i] = (int **) palloc(fctx->relsNAtt[i] * sizeof(int *)); + curr = -1; + for (j = 0; j < fctx->relsNAtt[i]; j++) + { + min = MaxHeapAttributeNumber; + for (k = 0; k < fctx->relsNAtt[i]; k++) + { + if ((fctx->relsAttNumsAtTupleSet[i][k] > curr) && + (fctx->relsAttNumsAtTupleSet[i][k] < min)) + { + min = fctx->relsAttNumsAtTupleSet[i][k]; + minAttNum = k; + } + } + curr = min; + sortedRelsAttNumsAtTupleSet[i][j] = (int *) palloc(2 * sizeof(int)); + /* tuple set att num */ + sortedRelsAttNumsAtTupleSet[i][j][0] = min; + /* matching rel att num */ + sortedRelsAttNumsAtTupleSet[i][j][1] = minAttNum; + } + } + fctx->sortedRelsAttNumsAtTupleSet = sortedRelsAttNumsAtTupleSet; + } + + /* + * here we find the proper casting for each attribute in each relation so + * that the equality function will be of same type. Also we setup the + * attribute types for the tuple set and setup the equality functions we + * are going to use. + */ + { + /* tuple set attribute types (oid types) */ + fctx->tupleSetAttTypes = (Oid *) palloc(fctx->tupleSetNatt * sizeof(Oid)); + + /* + * the first attribute is an internal fixed type (bytea, no need to + * specify it) + */ + fctx->tupleSetAttTypes[LABELS] = (Oid) NULL; + /* tuple set per attribute proper equality functions */ + fctx->tupleSetAttEQFunctions + = (TypeCacheEntry **) palloc(fctx->tupleSetNatt * sizeof(TypeCacheEntry *)); + /* no need for an equality function for the lables slot */ + fctx->tupleSetAttEQFunctions[LABELS] = NULL; + + /* + * a pointer to the attribute we are currently dealing with per + * relation. + */ + int relsAttPointer[fctx->numRels]; + + /* + * a structure were each slot is a relation id for the set of + * attribute with the same name we are currently dealing with. Not all + * slots are filled, in any one time we deal with the number of slots + * as the number of attributes with the same name shared among the + * relations + */ + int sharedAttRelIDs[fctx->numRels]; + + /* + * same as last but contains the original attribute number in the + * relsAttType structure + */ + int sharedAttAttNum[fctx->numRels]; + + /* + * num of attributes with the same name that can cast to the type of + * the slot relID + */ + int numCanCastToAttType[fctx->numRels]; + + /* + * number of attribute from the above that must be cast, i.e., have a + * different attribute type than the slot + */ + int numMustCastToAttType[fctx->numRels]; + Oid stype; + Oid ttype; + int numSharedRelIDs = 0; + bool simpleCast; + int minMustCast; + int minMustCastSharedRelID = -1; + + for (i = 0; i < fctx->numRels; i++) + relsAttPointer[i] = -1; + /* we do the casting checks per tuple set attribute */ + for (i = FIRSTATT; i < fctx->tupleSetNatt; i++) + { + numSharedRelIDs = 0; + + /* + * here we locate the attribute in each relation with the same + * name and put it in sharedAtt* + */ + for (j = 0; j < fctx->numRels; j++) + { + if ((relsAttPointer[j] + 1) >= fctx->relsNAtt[j]) + relsAttPointer[j] = -2; + else if ((relsAttPointer[j] > -2) && (i == sortedRelsAttNumsAtTupleSet[j][relsAttPointer[j] + 1][0])) + { + relsAttPointer[j]++; + sharedAttAttNum[numSharedRelIDs] = sortedRelsAttNumsAtTupleSet[j][relsAttPointer[j]][1]; + sharedAttRelIDs[numSharedRelIDs] = j; + numSharedRelIDs++; + } + } + /* here we find who can cast to whom */ + for (j = 0; j < numSharedRelIDs; j++) + { + numCanCastToAttType[j] = 0; + numMustCastToAttType[j] = 0; + stype = fctx->relsAttTypes[sharedAttRelIDs[j]][sharedAttAttNum[j]]; + for (k = 0; k < numSharedRelIDs; k++) + { + ttype = fctx->relsAttTypes[sharedAttRelIDs[k]][sharedAttAttNum[k]]; + if ((j != k) && (can_coerce_type(1, &stype, &ttype, COERCION_IMPLICIT))) + { + numCanCastToAttType[j]++; + if (stype != ttype) + numMustCastToAttType[j]++; + } + } + } + simpleCast = false; + minMustCast = MaxHeapAttributeNumber; + + /* + * here we find the minimal number of casts absolutely neccessary + * in the queries, however, a future policy might consider casting + * smallest size in pages of relations or those with the most + * edges in the scheme graph to other relations + */ + for (j = 0; j < numSharedRelIDs; j++) + { + if (numCanCastToAttType[j] == (numSharedRelIDs - 1)) + { + simpleCast = true; + if (numMustCastToAttType[j] < minMustCast) + minMustCast = numMustCastToAttType[j]; + minMustCastSharedRelID = j; + } + } + + /* + * if we can't cast all the attributes with the same name to the + * same type we go out in error. However, sometimes there are + * equality functions that can check for this but are difficult to + * identify. Therefore we give the user the option to explicity + * tell us that this attribute indeed can be casted. He does that + * by first handing out to the FD function an already explicity + * casted relations + */ + if (!simpleCast) + elog(ERROR, "Same names at different relations but with differnt types\ + that are difficult to cast.You can use CAST to explicitly change the attributes\ + to the same type.The name of the last problematic attribute is:%s ", + fctx->resultTupleAttNames[i - 1]); + else + fctx->tupleSetAttTypes[i] + = fctx->relsAttTypes[sharedAttRelIDs[minMustCastSharedRelID]][sharedAttAttNum[minMustCastSharedRelID]]; + } + + /* here we get the equality function for same types for each attribute in the result tuple.*/ + for (i = 0; i < fctx->resultTupleNAtt; i++) + fctx->tupleSetAttEQFunctions[i + 1] + = getEQFunction(fctx->tupleSetAttTypes[i + 1]); + } + + /* Here we create the scheme graph */ + { + int k, + z; + + for (i = 0; i < fctx->numRels; i++) + fctx->bits_scheme_graph[i] = 0; + for (i = 0; i < fctx->numRels; i++) + { + for (j = i + 1; j < fctx->numRels; j++) + { + k = 0; + z = 0; + while ((k < fctx->relsNAtt[i]) && (z < fctx->relsNAtt[j])) + { + if (sortedRelsAttNumsAtTupleSet[i][k][0] == + sortedRelsAttNumsAtTupleSet[j][z][0]) + { + fctx->bits_scheme_graph[i] = (fctx->bits_scheme_graph[i] | nthBitFromLeft(j)); + fctx->bits_scheme_graph[j] = (fctx->bits_scheme_graph[j] | nthBitFromLeft(i)); + break; + } + else if (sortedRelsAttNumsAtTupleSet[i][k][0] < + sortedRelsAttNumsAtTupleSet[j][z][0]) + k++; + else + z++; + } + } + } + } + + /* Lets check that the scheme graph is a connected scheme graph. + * Because, the FD is only useful on connected scheme graphs. + * If it is not, we must exit.*/ + { + RBITS relsMask = (~0x0); + + relsMask >>= fctx->numRels; + relsMask = ~relsMask; + RBITS repository = nthBitFromLeft(0); + + repository |= fctx->bits_scheme_graph[0]; + RBITS wereChecked = nthBitFromLeft(0); + bool wasAddition = false; + + for (i = 0; i < fctx->numRels; i++) + { + wasAddition = false; + for (j = 1; j < fctx->numRels; j++) + { + if ((!(varNthBitFromLeft(wereChecked, j))) && (varNthBitFromLeft(repository, j))) + { + repository |= fctx->bits_scheme_graph[j]; + varSetNthBitFromLeft(repository, j); + varSetNthBitFromLeft(wereChecked, j); + wasAddition = true; + if (repository == relsMask) + break; + } + } + if ((!wasAddition) || (repository == relsMask)) + break; + } + if (repository != relsMask) + elog(ERROR, "The relations must be connected to each other! for example A=(attribute1,attribute2), B=(attribute2,attribute3). A and B are connected because they share a common attribute2. Let C=(attribute4,attribute5). C is not connected to either A or B thus, the relations are not connected to each other. Make sure they do before you run the algorithm again."); + } + + /* lets generate the result tuple, tuple description. */ + { + TupleDesc desc = CreateTemplateTupleDesc(fctx->resultTupleNAtt, false); + TupleDesc tupleSetDesc = CreateTemplateTupleDesc(NUMATT, false); + + /* This is the added labels part of a tuple set. A tuple set is composed of a set + * of lables that represent the tuples from different relations in the set. And of + * course the attributes of these tuples. Since the attributes are the result of + * the join of these tuples, we do not need to repeat columns or actually keep + * the tuples in their original form. */ + TupleDescInitEntry(tupleSetDesc, LABELS_ALIGNED, "participatingRelationsOIDs" + ,BYTEAOID, -1, 0); + for (i = 0; i < fctx->resultTupleNAtt; i++) + if (!is_array_type(fctx->tupleSetAttTypes[i + 1])) + { + TupleDescInitEntry(desc, (i + 1), fctx->resultTupleAttNames[i] + ,fctx->tupleSetAttTypes[i + 1], -1, 0); + TupleDescInitEntry(tupleSetDesc, (i + 2), fctx->resultTupleAttNames[i] + ,fctx->tupleSetAttTypes[i + 1], -1, 0); + } + else + { + TupleDescInitEntry(desc, (i + 1), fctx->resultTupleAttNames[i] + ,fctx->tupleSetAttTypes[i + 1], -1, 1); + + /* + * if its an array then lets give it 3 dim will occur in any + * array. more than we will need to support at later + */ + TupleDescInitEntry(tupleSetDesc, (i + 2), fctx->resultTupleAttNames[i] + ,fctx->tupleSetAttTypes[i + 1], -1, 1); + } + fctx->resultTupleDesc = desc; + fctx->tupleSetDesc = tupleSetDesc; + /* HERE WE REGISTER THE OUTPUT SCHEME!!! */ + } + } + + /* Here we initialize the SPI structures that will allow us to read the relations. + * Basically, we open them once here and iterate on them by moving the cursor to the + * start of the portal each time without reopening them. The use of cursors is important + * because of transactional issues where because the FD is a long operation we must always + * work with the same data and thus, we must use the same initial snapshot. Basically opening + * a read only cursor should do the trick */ + void + initialize_SPI_structures(PG_FUNCTION_ARGS, alg_fctx * fctx, bool noDuplicatesTest + ,FuncCallContext *funcctx) + { + SPI_connect(); + fctx->portals = (Portal *) palloc(fctx->numRels * sizeof(Portal)); + fctx->plans = (void **) palloc(fctx->numRels * sizeof(void *)); + int i = 0; + + { + /* checking if there are duplicates in the relations. Only if the user requested. */ + if (noDuplicatesTest) + { + bool noDuplicates = true; + + for (i = 0; i < fctx->numRels; i++) + { + char query[255]; + char *to = query; + + to = (char *) stpcpy(to, "SELECT 'a' FROM pg_class WHERE relname='"); + to = (char *) stpcpy(to, get_rel_name(fctx->relsOid[i])); + to = (char *) stpcpy(to, "' and relhaspkey='t' and relnamespace='"); + char charNameSpaceOID[20]; + + sprintf(charNameSpaceOID, "%d", get_rel_namespace(fctx->relsOid[i])); + to = (char *) stpcpy(to, charNameSpaceOID); + to = (char *) stpcpy(to, "'"); + void *plan; + Portal portal; + + if ((plan = SPI_prepare(query, 0, NULL)) == NULL) + elog(ERROR, "initialize_SPI_structures: SPI_prepare('%s') returns NULL", + query); + if ((portal + = SPI_cursor_open(NULL, plan, NULL, NULL, true)) == NULL) + elog(ERROR, "initialize_SPI_structures: SPI_cursor_open('%s') returns NULL", + query); + SPI_cursor_fetch(portal, true, 1); + if (SPI_processed <= 0) + noDuplicates = false; + else + SPI_freetuptable(SPI_tuptable); + SPI_cursor_close(portal); + SPI_freeplan(plan); + if (!noDuplicates) + { + to = query; + to = (char *) stpcpy(to, "SELECT 'a' FROM "); + to = (char *) stpcpy(to, get_namespace_name(get_rel_namespace(fctx->relsOid[i]))); + to = (char *) stpcpy(to, "."); + to = (char *) stpcpy(to, get_rel_name(fctx->relsOid[i])); + to = (char *) stpcpy(to, " HAVING count(*)>1"); + if ((plan = SPI_prepare(query, 0, NULL)) == NULL) + elog(ERROR, "initialize_SPI_structures: SPI_prepare('%s') returns NULL", + query); + if ((portal + = SPI_cursor_open(NULL, plan, NULL, NULL, true)) == NULL) + elog(ERROR, "initialize_SPI_structures: SPI_cursor_open('%s') returns NULL", + query); + SPI_cursor_fetch(portal, true, 1); + if (SPI_processed <= 0) + noDuplicates = false; + else + noDuplicates = true; + SPI_freetuptable(SPI_tuptable); + SPI_cursor_close(portal); + SPI_freeplan(plan); + } + if (!noDuplicates) + break; + } + fctx->noDuplicates = noDuplicates; + } + } + + /* Here we actually setup the query and open the cursors. We also handle + * the proper castings and formulate a different query for the event there + * are duplicates. */ + { + fctx->queries = (char **) palloc(fctx->numRels * sizeof(char *)); + int j, + k; + char *query; + char *to; + int querySize; + bool toFreeQuery; + bool firstAtt = true; + + for (i = 0; i < fctx->numRels; i++) + { + querySize = 1024; + fctx->queries[i] = (char *) palloc(querySize * sizeof(char)); + query = fctx->queries[i]; + to = query; + int iterateNoDuplicates = 1; + + if (fctx->noDuplicates) + query = addAndExpandStringBy(query, &querySize, "SELECT " + ,querySize, &to, &toFreeQuery); + else + { + query = addAndExpandStringBy(query, &querySize, "SELECT DISTINCT ON (" + ,querySize, &to, &toFreeQuery); + iterateNoDuplicates = 2; + } + bool closed = false; + + for (k = 0; k < iterateNoDuplicates; k++) + { + firstAtt = true; + for (j = 0; j < fctx->relsNAtt[i]; j++) + { + if (!firstAtt) + { + query = addAndExpandStringBy(query, &querySize, "," + ,querySize, &to, &toFreeQuery); + } + firstAtt = false; + query = addAndExpandStringBy(query, &querySize, + (char *) get_attname(fctx->relsOid[i], fctx->relsValidAttNumAtRelation[i][j]) + ,querySize, &to, &toFreeQuery); + if (fctx->relsAttTypes[i][j] != fctx->tupleSetAttTypes[fctx->relsAttNumsAtTupleSet[i][j]]) + { + query = addAndExpandStringBy(query, &querySize, "::" + ,querySize, &to, &toFreeQuery); + query = addAndExpandStringBy(query, &querySize, + format_type_with_typemod(fctx->tupleSetAttTypes[fctx->relsAttNumsAtTupleSet[i][j]], -1) + ,querySize, &to, &toFreeQuery); + } + } + if (!fctx->noDuplicates && !closed) + { + query = addAndExpandStringBy(query, &querySize, ") " + ,querySize, &to, &toFreeQuery); + closed = true; + } + } + /* CTID is used as the label of a tuple (together with the table id) thus, + * we must have it */ + query = addAndExpandStringBy(query, &querySize, ",CTID FROM " + ,querySize, &to, &toFreeQuery); + query = addAndExpandStringBy(query, &querySize, get_namespace_name(get_rel_namespace(fctx->relsOid[i])) + ,querySize, &to, &toFreeQuery); + query = addAndExpandStringBy(query, &querySize, "." + ,querySize, &to, &toFreeQuery); + query = addAndExpandStringBy(query, &querySize, get_rel_name(fctx->relsOid[i]) + ,querySize, &to, &toFreeQuery); + if ((fctx->plans[i] = SPI_prepare(query, 0, NULL)) == NULL) + elog(ERROR, "initialize_SPI_structures: SPI_prepare('%s') returns NULL", query); + if ((fctx->portals[i] + = SPI_cursor_open(NULL, fctx->plans[i], NULL, NULL, true)) == NULL) + + /* + * note that read_only in cursor_open must be true otherwise + * ctid can change. + */ + elog(ERROR, "initialize_SPI_structures: SPI_cursor_open('%s') returns NULL", + query); + } + } + } diff -crN pgsql/contrib/fulldisjunctions/algstructs.h pgsql-fd/contrib/fulldisjunctions/algstructs.h *** pgsql/contrib/fulldisjunctions/algstructs.h 1969-12-31 19:00:00.000000000 -0500 --- pgsql-fd/contrib/fulldisjunctions/algstructs.h 2006-07-30 13:30:11.000000000 -0400 *************** *** 0 **** --- 1,214 ---- + /* + * Copyright (c) 2006 Itzhak Fadida. All Rights Reserved. + * See the README file for a detailed BSD License. + * This file and all related files are under the BSD license. + * */ + + #ifndef ALGSTRUCTS_H + #define ALGSTRUCTS_H + + #ifdef DEBUG + #else + #define NDEBUG + #endif + + #include + + #include "postgres.h" + #include "utils/palloc.h" + #include "funcapi.h" + #include "fmgr.h" + #include "catalog/pg_type.h" + #include "executor/spi.h" + #include "executor/spi_priv.h" + #include "utils/lsyscache.h" + #include "utils/typcache.h" + #include "queues.h" + + /* a safety measure if we do not calculate the max size of the result tuple */ + #define RESULT_TUPLE_ASSUMED_MAX_SIZE_IN_PAGES 1 + #define RESULT_TUPLE_ASSUMED_MAX_SIZE_IN_BYTES (RESULT_TUPLE_ASSUMED_MAX_SIZE_IN_PAGES*BLCKSZ) + + /* Mapping from a relation attribute to an alias */ + typedef struct + { + int resultTuplePotnetialAttNamesID; + char *relAttName; + } Mapping; + + /* a dictionary of mappings */ + typedef struct + { + /* list of unique aliases.*/ + char **resultTuplePotentialAttNames; + int numPotentialAttNames; + /* Holds a list of mappings for each relation. */ + Mapping ***relsAttsMappings; + int *numMappings; + } Dictionary; + + /* a persistant state strucutre between calls to the OnDemand Procedure. */ + typedef struct + { + /* index in Q */ + int q; + /* index in P */ + int p; + memQueue *Q; + /* pointer in Q */ + memQueueNode *qPtr; + /* current relation tuple we work with */ + DTuple P; + TupleDesc Pdesc; + int PrelID; + /* we keep the last SPI (P) tuptable so we can free it properly. */ + SPITupleTable *lastTuptable; + /* current relation we are scanning */ + int cur_rel; + /* The portals of all the relations. They are the same as in the SPI structures in algstructs + * but we need to scan them seperately here with a seperate cursor. */ + Portal *portals; + } OnDemandState; + + /* This is the structure of the adaptive upper bound on how many tuple sets we are + * going to extend at once. */ + typedef struct + { + double previousScore; + int nextUpperBound; + int stage; + int maxInputedExtendTuples; + int actualInputedExtendTuples; + } adaptive_extend_upperbound; + + /* This is the general context of the algorithm. + * Most of the algorithms structures are here. */ + typedef struct + { + /* number of arguments in the input */ + int nargs; + /* number of inputted relations */ + int numRels; + /* a portal for each relation */ + Portal *portals; + /* a query for each relation */ + char **queries; + /* a plan for each relation */ + void **plans; + /* relations oid's */ + Oid *relsOid; + /* the size in pages of each relation. */ + int *relsPages; + /* true if relation has an index, false otherwise. */ + bool *relsHasIndex; + + /* + * the array will contain RELIDS where cell 0 will contain the smallest + * paged size relation ID. + */ + int *sortedRelsByRelsPages; + /* the estimated or real maximum tuple size for each relation */ + int *relsMaxTupleSize; + /* number of attributes of each relation. */ + int *relsNAtt; + + /* + * for each relation and each of its attributes, specifies the attribute + * number at the result tuple. + */ + int **relsAttNumsAtTupleSet; + /* same as last but sorted by tuple set att num key. */ + int ***sortedRelsAttNumsAtTupleSet; + /* does not include dropped columns of relations */ + int **relsValidAttNumAtRelation; + /* for each relation lets save its attributes types; */ + Oid **relsAttTypes; + /* The result tuple attribute names. */ + char **resultTupleAttNames; + /* The result tupl attribute types. */ + Oid *tupleSetAttTypes; + /* equality functions for same types of the respected tuple set type */ + TypeCacheEntry **tupleSetAttEQFunctions; + /* tuple description of the result tuple */ + TupleDesc resultTupleDesc; + /* The result tuple number of attributes. */ + int resultTupleNAtt; + /* in bytes. how much its HeapTuple occuppies in memory. */ + int tupleSetMaxSize; + /* how many result tuples can fit in one page. */ + int m_NumResultTuplesInOnePage; + + /* indicate if we use the default value */ + bool assumingResultTupleMaxSize; + /* The tuple set description (used to dumb tuple set to storage) */ + TupleDesc tupleSetDesc; + /* tuple set number of attributes */ + int tupleSetNatt; + /* dictionary of inputted mappings */ + Dictionary *dictionary; + /* 0 not connected, 1 connected. */ + RBITS *bits_scheme_graph; + /* tuple store of outputted result tuples */ + storageQueue complete; + /* tuple store of not yet outputted result tuples */ + storageQueue precomplete; + /* indicates if there is a need to check for duplicates and later after testing + * if there are in fact duplicates. */ + bool noDuplicates; + /* The algorithm state in the state machine. */ + int algorithm_state; + /* a queue for reading from virtual incomplete (precomplete with the relations) */ + memQueue Q; + /* a queue for extending */ + memQueue E; + /* a pointer to the last sent tset for printing or pipelining. */ + memQueueNode *printedTSet; + + /* + * if you are using queue to print then this signifies that we started + * printing when we come back from backend. + */ + bool startedPrintingQueue; + /* pointer to the printed tuple */ + HeapTuple printedTupleAddress; + /* indicates if we want to use indices in the relations for extending */ + bool noIndexScans; + double startTime; + double endTime; + /* the persistent state for the on demand procedure */ + OnDemandState *onDemandState; + /* the MB input parameter */ + int MB; + /* the policy used for extending - inputted */ + int extendingPolicy; + /* the last relation we have scanned in extending */ + int extendingLastRelScanned; + /* statistical variable */ + int extendingNaivePolicyNumCompleteScans; + /* used for extending with complex policies */ + memQueueNode *policyWorkNode; + RBITS policySequence; + RBITS relationsToScan; + /* query for extending when using indices */ + char *query; + int querySize; + Datum *queryParams; + Oid *queryParamsTypes; + int queryParamsSize; + /* future indicator, not really used currently. */ + bool trueIndexFalseNonIndexBasedAlgorithm; + /* adaptive upper bound for extending structures */ + adaptive_extend_upperbound *dynamic_extend_cap; + /* an additional memory context to handle accesses to the tuple store. + * Needed to prevent leaking and all kinds of weird issues */ + MemoryContext per_query_ctx; + } alg_fctx; + + extern Oid *parseOIDs(text *relsStr, int *numOfRels); + extern Oid *parseOIDs_(char *relsStrCp, int *numOfRels); + extern void initialize_general_structures(PG_FUNCTION_ARGS, alg_fctx * fctx, FuncCallContext *funcctx); + extern void initialize_general_structures_(PG_FUNCTION_ARGS, alg_fctx * fctx, bool parsing, FuncCallContext *funcctx); + extern void initialize_SPI_structures(PG_FUNCTION_ARGS, alg_fctx * fctx, bool noDuplicatesTest + ,FuncCallContext *funcctx); + + #endif /* ALGSTRUCTS_H */ diff -crN pgsql/contrib/fulldisjunctions/algutils.c pgsql-fd/contrib/fulldisjunctions/algutils.c *** pgsql/contrib/fulldisjunctions/algutils.c 1969-12-31 19:00:00.000000000 -0500 --- pgsql-fd/contrib/fulldisjunctions/algutils.c 2006-07-30 13:30:12.000000000 -0400 *************** *** 0 **** --- 1,1731 ---- + /* + * Copyright (c) 2006 Itzhak Fadida. All Rights Reserved. + * See the README file for a detailed BSD License. + * This file and all related files are under the BSD license. + * */ + + #include "postgres.h" + #include "algutils.h" + #include "catalog/heap.h" + #include "tset.h" + #include "tsetfuncs.h" + #include "queues.h" + #include "queuesfuncs.h" + #include "utils/datum.h" + #include + + /* Just copying a datum */ + Datum + myDatumCopy(Datum value, bool typByVal, int typLen) + { + Datum res; + + if (typByVal) + res = value; + else + { + Size realSize; + char *s; + + if (DatumGetPointer(value) == NULL) + return PointerGetDatum(NULL); + realSize = datumGetSize(value, typByVal, typLen); + s = (char *) palloc(realSize); + memcpy(s, DatumGetPointer(value), realSize); + res = PointerGetDatum(s); + } + return res; + } + + /* Freeing a datum */ + void + myDatumFree(Datum value, bool typByVal, int typLen) + { + if (!typByVal) + { + Pointer s = DatumGetPointer(value); + + pfree(s); + } + } + + /* sorting an array of Oids */ + void + sortOidArray(Oid *array, int numElements) + { + int swapint, + i, + j; + + for (i = 0; i < (numElements - 1); i++) + for (j = (i + 1); j < numElements; j++) + if (array[i] > array[j]) + { + swapint = array[i]; + array[i] = array[j]; + array[j] = swapint; + } + } + + /* updating the max tuple size */ + void + updateMaxTupleSize(alg_fctx * fctx, int relID, HeapTuple tuple) + { + int size = tupleSize(tuple); + + if (fctx->relsMaxTupleSize[relID] < size) + fctx->relsMaxTupleSize[relID] = size; + } + + /* updating the max result tuple size*/ + void + updateResultTupleMaxSize(alg_fctx * fctx) + { + int tmpSize = 0; + int i = 0; + + for (i = 0; i < fctx->numRels; i++) + tmpSize += fctx->relsMaxTupleSize[i]; + fctx->tupleSetMaxSize = tmpSize; + double blcksz = BLCKSZ; + + if (tmpSize > 0) + fctx->m_NumResultTuplesInOnePage = (int) (blcksz / (double) tmpSize); + else + fctx->m_NumResultTuplesInOnePage = 1; + if (fctx->m_NumResultTuplesInOnePage < 1) + fctx->m_NumResultTuplesInOnePage = 1; + } + + /* getting an equality function for same type */ + TypeCacheEntry * + getEQFunction(Oid typeid) + { + TypeCacheEntry *typentry; + + /* + * Find the data type in the typcache, and ask for eq_opr info. + */ + typentry = lookup_type_cache(typeid, TYPECACHE_EQ_OPR_FINFO); + if (!OidIsValid(typentry->eq_opr_finfo.fn_oid)) + ereport(ERROR, (errcode(ERRCODE_UNDEFINED_FUNCTION), + errmsg("could not identify an equality operator for type %s", + format_type_be(typeid)))); + return typentry; + } + + /* auto expanding a datum array in memory */ + Datum * + getAndExpandDatumArray(Datum *oldDatumArr, int oldDatumArraySize, int newDatumArraySize) + { + if (oldDatumArr == NULL) + return (Datum *) palloc(newDatumArraySize * sizeof(Datum)); + else + { + if (oldDatumArraySize < newDatumArraySize) + { + Datum *newArr = (Datum *) palloc(newDatumArraySize * sizeof(Datum)); + + memcpy(newArr, oldDatumArr, oldDatumArraySize * sizeof(Datum)); + return newArr; + } + } + return oldDatumArr; + } + + /* auto expanding an Oid array in memory */ + Oid * + getAndExpandOidArray(Oid *oldOidArr, int oldOidArraySize, int newOidArraySize) + { + if (oldOidArr == NULL) + return (Oid *) palloc(newOidArraySize * sizeof(Oid)); + else + { + if (oldOidArraySize < newOidArraySize) + { + Oid *newArr = (Oid *) palloc(newOidArraySize * sizeof(Oid)); + + memcpy(newArr, oldOidArr, oldOidArraySize * sizeof(Oid)); + return newArr; + } + } + return oldOidArr; + } + + /* auto expanding a string array in memory */ + char * + addAndExpandStringBy(char *oldStr, int *oldStrAllocSize, char *addStr, int sizeToAdd + ,char **relative_ptr, bool *free_old_str) + { + int oldStrSize = (int) *relative_ptr - (int) oldStr; + int addStrSize = strlen(addStr); + + /* +1 for null at the end */ + if (*oldStrAllocSize >= (oldStrSize + addStrSize + 1)) + { + *relative_ptr = (char *) stpcpy(*relative_ptr, addStr); + return oldStr; + } + *oldStrAllocSize = *oldStrAllocSize + addStrSize + sizeToAdd * sizeof(char); + char *newStr = (char *) palloc(*oldStrAllocSize); + char *to = newStr; + + to = (char *) stpcpy(to, oldStr); + to = (char *) stpcpy(to, addStr); + if (relative_ptr != NULL) + *relative_ptr = to; + else + elog(ERROR, "Error in addAndExpandStringBy"); + if (*free_old_str) + pfree(oldStr); + *free_old_str = true; + return newStr; + } + + /* checks if an attribute in the result tuple also appear in the relation specified + * in the relID */ + bool + isResultTupleAttOccursInRelID(alg_fctx * fctx, int resultTupleAttID, int relID) + { + int i = 0; + + for (i = 0; i < fctx->relsNAtt[relID]; i++) + { + if (fctx->relsAttNumsAtTupleSet[relID][i] == resultTupleAttID) + return true; + } + return false; + } + + /* + * in some RelID of a tuple set of course. Where the tuple set is represented + * by the relsID. + */ + bool + isResultTupleAttOccursInSomeRelID(alg_fctx * fctx, int resultTupleAttID, bytea *relsID) + { + int numIDs = numOfTuplesInTSet(fctx, relsID); + int j = 0; + + for (j = 0; j < numIDs; j++) + if (isResultTupleAttOccursInRelID(fctx, resultTupleAttID + ,getTableIdOfRelsOidInTSet(fctx, relsID, j))) + return true; + return false; + } + + /* Same as isResultTupleAttOccursInSomeRelID but using a BITS array instead of a bytea set + * of lables. */ + bool + isResultTupleAttOccursInSomeRelIDWithSpecifiedRelations(alg_fctx * fctx, int resultTupleAttID, + RBITS relationsToCheck) + { + int i = 0, + j = 0; + RBITS localRelationsToCheck = relationsToCheck; + + while (localRelationsToCheck) + { + if (varNthBitFromLeft(localRelationsToCheck, 0)) + for (j = 0; j < fctx->relsNAtt[i]; j++) + { + if (fctx->relsAttNumsAtTupleSet[i][j] == resultTupleAttID) + return true; + } + i++; + localRelationsToCheck <<= 1; + } + return false; + } + + /* + * A policy to choose the next relation to extend to. + * majority is to extend to the relation most tuple set currently needs + * to extend to. + * -1 means, no relation was chosen + */ + int + policy_majority_Q_one_tuple_set_at_a_time(alg_fctx * fctx, memQueue * Q, int tsetsNum) + { + int j = 0, + maxSum = 0, + i = 0; + RBITS tmp = 0, + tmpRels = 0; + int relsSum[fctx->numRels]; + + for (j = 0; j < fctx->numRels; j++) + relsSum[j] = 0; + memQueueNode *ptr = NULL; + + if (fctx->policyWorkNode) + ptr = fctx->policyWorkNode; + else + { + ptr = getMemQueueFirstElementPtr(Q); + if (!(ptr)) + return -1; + } + tmp = ptr->toVisit; + if (!(tmp)) + elog(ERROR, "Unexpecteed problem1"); + fctx->policyWorkNode = ptr; + ptr = getMemQueueFirstElementPtr(Q); + while (ptr != NULL) + { + tmpRels = ((ptr->toVisit) & tmp); + j = 0; + while (tmpRels) + { + varNthBitFromLeft(tmpRels, 0) && relsSum[j]++; + tmpRels <<= 1; + j++; + } + ptr = getMemQueueNextElementPtr(ptr); + } + for (j = 0; j < fctx->numRels; j++) + if (relsSum[j] > maxSum) + { + i = j; + maxSum = relsSum[j]; + } + return i; + } + + /* + * same as with policy_majority_Q_one_tuple_set_at_a_time but with sequencing. + * -1 means, no relation was chosen + */ + int + policy_majority_Q_one_tuple_set_at_a_time_with_sequencing(alg_fctx * fctx, memQueue * Q, + int tsetsNum) + { + int j = 0, + maxSum = 0, + i = 0; + int relsSum[fctx->numRels]; + + for (j = 0; j < fctx->numRels; j++) + relsSum[j] = 0; + RBITS tmp = 0; + RBITS tmpRels = 0; + RBITS relsMask = (~0x0); + + relsMask >>= fctx->numRels; + relsMask = ~relsMask; + bool wasAddToSum = false; + memQueueNode *ptr = NULL; + + if (fctx->policyWorkNode) + { + ptr = fctx->policyWorkNode; + tmp = ptr->toVisit; + } + else + { + ptr = getMemQueueFirstElementPtr(Q); + if (!(ptr)) + return -1; + if (fctx->policySequence) + { + tmp = fctx->policySequence; + } + else + { + fctx->policySequence = relsMask; + tmp = ptr->toVisit; + if (!(tmp)) + elog(ERROR, "Unexpecteed problem21"); + } + } + if (!(tmp)) + elog(ERROR, "Unexpecteed problem2"); + fctx->policyWorkNode = ptr; + ptr = getMemQueueFirstElementPtr(Q); + while (ptr != NULL) + { + tmpRels = ((ptr->toVisit) & tmp); + j = 0; + while (tmpRels) + { + varNthBitFromLeft(tmpRels, 0) && relsSum[j]++; + varNthBitFromLeft(tmpRels, 0) && (wasAddToSum = true); + tmpRels <<= 1; + j++; + } + ptr = getMemQueueNextElementPtr(ptr); + } + if (wasAddToSum) + { + for (j = 0; j < fctx->numRels; j++) + if (relsSum[j] > maxSum) + { + i = j; + maxSum = relsSum[j]; + } + varUnSetNthBitFromLeft(fctx->policySequence, i); + return i; + } + else + { + fctx->policySequence = 0; + fctx->policyWorkNode = NULL; + return policy_majority_Q_one_tuple_set_at_a_time_with_sequencing(fctx, Q, tsetsNum); + } + } + + /* + * mincost policy choose the relations the tuple sets needs to extend to but that has + * the least pages in it. + * -1 means, no relation was chosen + */ + int + policy_mincost_Q_one_tuple_set_at_a_time(alg_fctx * fctx, memQueue * Q, int tsetsNum) + { + int j = 0; + RBITS tmp = 0; + memQueueNode *ptr = NULL; + + if (fctx->policyWorkNode) + ptr = fctx->policyWorkNode; + else + { + ptr = getMemQueueFirstElementPtr(Q); + if (!(ptr)) + return -1; + } + tmp = ptr->toVisit; + if (!(tmp)) + elog(ERROR, "Unexpecteed problem3"); + fctx->policyWorkNode = ptr; + for (j = 0; j < fctx->numRels; j++) + if (varNthBitFromLeft(tmp, fctx->sortedRelsByRelsPages[j])) + return fctx->sortedRelsByRelsPages[j]; + return -1; + } + + /* + * same as one at a time, but with sequencing. + * -1 means, no relation was chosen + */ + int + policy_mincost_Q_one_tuple_set_at_a_time_with_sequencing(alg_fctx * fctx, memQueue * Q, + int tsetsNum) + { + int j = 0, + relID = 0; + RBITS tmp = 0; + RBITS tmpRels = 0; + RBITS relsMask = (~0x0); + + relsMask >>= fctx->numRels; + relsMask = ~relsMask; + memQueueNode *ptr = NULL; + RBITS sequence = fctx->policySequence; + + if (fctx->policyWorkNode) + { + ptr = fctx->policyWorkNode; + tmp = ptr->toVisit; + } + else + { + ptr = getMemQueueFirstElementPtr(Q); + if (!(ptr)) + return -1; + if (sequence) + { + for (j = 0; j < fctx->numRels; j++) + { + relID = fctx->sortedRelsByRelsPages[j]; + if (varNthBitFromLeft(sequence, relID)) + { + tmp = nthBitFromLeft(relID); + break; + } + } + while (ptr != NULL) + { + tmpRels |= (ptr->toVisit); + if (tmpRels & tmp) + { + varUnSetNthBitFromLeft(fctx->policySequence, relID); + return relID; + } + if ((tmpRels & sequence) == sequence) + break; + ptr = getMemQueueNextElementPtr(ptr); + } + ptr = NULL; + tmp = fctx->policySequence & tmpRels; + if (!(tmp)) + { + ptr = getMemQueueFirstElementPtr(Q); + fctx->policySequence = relsMask; + tmp = ptr->toVisit; + } + } + else + { + fctx->policySequence = relsMask; + tmp = ptr->toVisit; + } + } + if (!(tmp)) + elog(ERROR, "Unexpecteed problem4"); + fctx->policyWorkNode = ptr; + for (j = 0; j < fctx->numRels; j++) + if (varNthBitFromLeft(tmp, fctx->sortedRelsByRelsPages[j])) + { + varUnSetNthBitFromLeft(fctx->policySequence, fctx->sortedRelsByRelsPages[j]); + return fctx->sortedRelsByRelsPages[j]; + } + return -1; + } + + /* + * random relation choice but only from those the tuple sets needs to extend to. + * (the tuple sets in Q) + * -1 means, no relation was chosen + */ + int + policy_random_Q(alg_fctx * fctx, memQueue * Q, int tsetsNum) + { + int i = 0; + int j = 0; + int numRelsToExtend = 0; + RBITS tmpRels = 0; + RBITS tmp; + RBITS relsMask = (~0x0); + + relsMask >>= fctx->numRels; + relsMask = ~relsMask; + memQueueNode *ptr = getMemQueueFirstElementPtr(Q); + + while (ptr != NULL) + { + tmpRels |= (ptr->toVisit); + if (tmpRels == relsMask) + break; + ptr = getMemQueueNextElementPtr(ptr); + } + tmp = tmpRels; + while (tmp) + { + if (varNthBitFromLeft(tmp, 0)) + numRelsToExtend++; + tmp <<= 1; + } + if (numRelsToExtend > 0) + { + int k = 0; + + i = ((int) (numRelsToExtend * (rand() / (RAND_MAX + 1.0)))) + 1; + if (i > numRelsToExtend) + elog(ERROR, "policy_random_Q (i>numRelsToExtend)"); + j = 0; + while ((j < i) && (j < numRelsToExtend)) + { + if (varNthBitFromLeft(tmpRels, k)) + { + j++; + } + k++; + } + k--; + return k; + } + return -1; + } + + /* + * naive policy. mostly useless. + * -1 means, no relation was chosen + */ + int + policy_naive_Q(alg_fctx * fctx, memQueue * Q, int tsetsNum) + { + if (fctx->extendingLastRelScanned < 0) + return 0; + if ((fctx->extendingLastRelScanned + 1) < fctx->numRels) + return (fctx->extendingLastRelScanned + 1); + fctx->extendingNaivePolicyNumCompleteScans++; + if (fctx->extendingNaivePolicyNumCompleteScans == fctx->numRels) + return -1; + return 0; + } + + /* naive policy, chooses the relation in a deterministic manner with no regard to the + * tuple sets.*/ + int + policy_naive(alg_fctx * fctx, int **checkTable, int tsetsNum) + { + if (fctx->extendingLastRelScanned < 0) + return 0; + if ((fctx->extendingLastRelScanned + 1) < fctx->numRels) + return (fctx->extendingLastRelScanned + 1); + fctx->extendingNaivePolicyNumCompleteScans++; + if (fctx->extendingNaivePolicyNumCompleteScans == fctx->numRels) + return -1; + return 0; + } + + /* checks using a tree search the plantree if it contains a sequence scan. and return + * true if it does.*/ + bool + isPlanUsingSeqScan(Plan *planTree) + { + if (nodeTag(planTree) == T_SeqScan) + return true; + if (nodeTag(planTree) == T_Append) + { + Append *appendplan = (Append *) planTree; + ListCell *lst; + + foreach(lst, appendplan->appendplans) + { + Plan *subnode = (Plan *) lfirst(lst); + + return (isPlanUsingSeqScan(subnode)); + } + } + if (nodeTag(planTree) == T_SubqueryScan) + { + SubqueryScan *subqueryscan = (SubqueryScan *) planTree; + Plan *subnode = subqueryscan->subplan; + + return (isPlanUsingSeqScan(subnode)); + } + if (innerPlan(planTree)) + if (isPlanUsingSeqScan(innerPlan(planTree)) == true) + return true; + if (outerPlan(planTree)) + if (isPlanUsingSeqScan(outerPlan(planTree)) == true) + return true; + return false; + } + + /*simply recombines queues using their head and tail pointers.*/ + void + recombineQueues(memQueue * destQ, int numQueues,...) + { + memQueue *sourceQ = NULL; + memQueue destQtmp; + + _initializeMemQueue(&destQtmp, destQ->allocatedBytes); + int i; + va_list ap; + + va_start(ap, numQueues); + for (i = 0; i < numQueues; i++) + { + sourceQ = va_arg(ap, memQueue *); + if (sourceQ->head != NULL) + { + if (destQtmp.head == NULL) + destQtmp.head = sourceQ->head; + else + destQtmp.tail->next = (struct memQueueNode *) sourceQ->head; + destQtmp.numElements += sourceQ->numElements; + destQtmp.sizeInBytes += sourceQ->sizeInBytes; + destQtmp.tail = sourceQ->tail; + } + } + _initializeMemQueue(destQ, destQ->allocatedBytes); + destQ->head = destQtmp.head; + destQ->tail = destQtmp.tail; + destQ->numElements = destQtmp.numElements; + destQ->sizeInBytes = destQtmp.sizeInBytes; + va_end(ap); + } + + /* + * a random policy to choose a relation. However, only those that the tuple sets in Q needs + * to extend to. + * -1 means, no relation was chosen + */ + int + policy_random_Q_one_tuple_set_at_a_time(alg_fctx * fctx, memQueue * Q, int tsetsNum) + { + int i = 0; + int j = 0; + int numRelsToExtend = 0; + RBITS tmp; + RBITS relsMask = (~0x0); + + relsMask >>= fctx->numRels; + relsMask = ~relsMask; + memQueueNode *ptr = NULL; + + if (fctx->policyWorkNode) + ptr = fctx->policyWorkNode; + else + ptr = getMemQueueFirstElementPtr(Q); + if (!(ptr)) + { + fctx->policyWorkNode = NULL; + return -1; + } + tmp = ptr->toVisit; + if (!(tmp)) + elog(ERROR, "Unexpecteed problem5"); + fctx->policyWorkNode = ptr; + while (tmp) + { + if (varNthBitFromLeft(tmp, 0)) + numRelsToExtend++; + tmp <<= 1; + } + tmp = ptr->toVisit; + if (numRelsToExtend > 0) + { + int k = 0; + + i = ((int) (numRelsToExtend * (rand() / (RAND_MAX + 1.0)))) + 1; + if (i > numRelsToExtend) + elog(ERROR, "policy_random_Q_one_tuple_set_at_a_time (i>numRelsToExtend)"); + j = 0; + while ((j < i) && (j < numRelsToExtend)) + { + if (varNthBitFromLeft(tmp, k)) + { + j++; + } + k++; + } + k--; + return k; + } + return -1; + } + + /* + * same as one at a time but with sequencing support. + * -1 means, no relation was chosen + */ + int + policy_random_Q_one_tuple_set_at_a_time_with_sequencing(alg_fctx * fctx, memQueue * Q, + int tsetsNum) + { + int i = 0; + int j = 0; + int numRelsToExtend = 0; + RBITS tmp = 0, + tmp2 = 0; + RBITS tmpRels = 0; + RBITS relsMask = (~0x0); + + relsMask >>= fctx->numRels; + relsMask = ~relsMask; + memQueueNode *ptr = NULL; + + if (fctx->policyWorkNode) + { + ptr = fctx->policyWorkNode; + tmp = ptr->toVisit; + } + else + { + ptr = getMemQueueFirstElementPtr(Q); + if (!(ptr)) + return -1; + if (fctx->policySequence) + { + while (ptr != NULL) + { + tmpRels |= (ptr->toVisit); + if (tmpRels == relsMask) + break; + ptr = getMemQueueNextElementPtr(ptr); + } + ptr = NULL; + tmp = fctx->policySequence & tmpRels; + if (!(tmp)) + { + ptr = getMemQueueFirstElementPtr(Q); + fctx->policySequence = relsMask; + tmp = ptr->toVisit; + } + } + else + { + fctx->policySequence = relsMask; + tmp = ptr->toVisit; + } + } + Assert(tmp); + if (!(tmp)) + elog(ERROR, "Unexpecteed problem6"); + fctx->policyWorkNode = ptr; + tmp2 = tmp; + while (tmp) + { + if (varNthBitFromLeft(tmp, 0)) + numRelsToExtend++; + tmp <<= 1; + } + if (numRelsToExtend > 0) + { + int k = 0; + + i = ((int) (numRelsToExtend * (rand() / (RAND_MAX + 1.0)))) + 1; + if (i > numRelsToExtend) + elog(ERROR, "policy_random_Q_one_tuple_set_at_a_time_with_sequencing (i>numRelsToExtend)"); + j = 0; + while ((j < i) && (j < numRelsToExtend)) + { + if (varNthBitFromLeft(tmp2, k)) + { + j++; + } + k++; + } + k--; + varUnSetNthBitFromLeft(fctx->policySequence, k); + return k; + } + return -1; + } + + /* helper macro for the policies functions */ + #define update_policy_status(fctx, policy, updateCode, nodePtr)\ + { if (fctx->policyWorkNode==nodePtr)\ + fctx->policyWorkNode=NULL;} + + /* Simply get a string from a datum directly. + * must be non null value. check in advance. also check num of attr=>fnumber*/ + char * + getCStrvalueFromDatum(Datum origval, TupleDesc tupdesc, int fnumber) + { + Datum val, + result; + Oid typoid, + foutoid; + bool typisvarlena; + + if (fnumber > 0) + typoid = tupdesc->attrs[fnumber - 1]->atttypid; + else + typoid = (SystemAttributeDefinition(fnumber, true))->atttypid; + getTypeOutputInfo(typoid, &foutoid, &typisvarlena); + + /* + * If we have a toasted datum, forcibly detoast it here to avoid memory + * leakage inside the type's output routine. + */ + if (typisvarlena) + val = PointerGetDatum(PG_DETOAST_DATUM(origval)); + else + val = origval; + result = OidFunctionCall1(foutoid, + val); + /* Clean up detoasted copy, if any */ + if (val != origval) + pfree(DatumGetPointer(val)); + return DatumGetCString(result); + } + + /* algorithm's extend procedure. + * The extending operation is to take tuple sets and add to them tuples from the inputted + * relations that the resulting set is join consistend and connected (JCC). + * Finally stop when all the tuple sets are maximal in that respect.*/ + void + Extend(alg_fctx * fctx, memQueue * Q) + { + int QNumElements = getMemQueueNumElements(Q); + + if (!(QNumElements)) + return; + + /* an estimate for the average size of a tuple set in memory. */ + int avgTSetSize = (int) (getMemQueueSize(Q) / (QNumElements + 1)) + QNumElements; + int i = 0; + + /* The first element in Q */ + memQueueNode *nodePtr = getMemQueueFirstElementPtr(Q); + + /* a pointer to a queue which we need to set visited a relation to each of its tuple sets */ + memQueue *setVisitedQ = NULL; + + TSet retTSet = NULL; + DTuple tuple = newDTuple(fctx, fctx->resultTupleNAtt); + + /* a structure that deforms a tuple one attribute at a time until it is deformed completly. + * However, we can abort in the middle */ + deformTupleIterativeState *dsTuple + = (deformTupleIterativeState *) palloc(sizeof(deformTupleIterativeState)); + bool endScan = false; + bool firstPass = true; + bool isNull = false; + memQueueNode *prevNodePtr = NULL; + TSet tset = NULL; + + i = 0; + bool scanNotEmpty = false; + int relToCheck = -1; + char *query = fctx->query; + int querySize = fctx->querySize; + bool toFreeQuery = true; + POLICY_FUNC policy = NULL; + + /* Lets choose the inputted policy function to use, + * these functions all have the same interface */ + switch (fctx->extendingPolicy) + { + case POLICY_MAJORITY: + if (fctx->trueIndexFalseNonIndexBasedAlgorithm) + policy = &policy_majority_Q_one_tuple_set_at_a_time_with_sequencing; + else + policy = &policy_majority_Q_one_tuple_set_at_a_time; + break; + case POLICY_MINCOST: + if (fctx->trueIndexFalseNonIndexBasedAlgorithm) + policy = &policy_mincost_Q_one_tuple_set_at_a_time_with_sequencing; + else + policy = &policy_mincost_Q_one_tuple_set_at_a_time; + break; + case POLICY_RANDOM: + if (fctx->trueIndexFalseNonIndexBasedAlgorithm) + policy = &policy_random_Q_one_tuple_set_at_a_time_with_sequencing; + else + policy = &policy_random_Q_one_tuple_set_at_a_time; + break; + case POLICY_NAIVE: + policy = &policy_naive_Q; + fctx->extendingNaivePolicyNumCompleteScans = 0; + break; + default: + elog(ERROR, "POLICY FUNCTION ASSIGNENT ERRORED!"); + } + + /* the queues for the extending process */ + memQueue needsChanging; + memQueue notInvolved; + memQueue maximalyExtended; + + _initializeMemQueue(&needsChanging, INFINITY); + _initializeMemQueue(¬Involved, INFINITY); + _initializeMemQueue(&maximalyExtended, INFINITY); + + /* Here we work under the assumption that Q is ALREADY MERGED!!!!!!!!!!1 */ + nodePtr = getMemQueueFirstElementPtr(Q); + /* here we find all the already maximally extended tuple sets and move them to the result */ + prevNodePtr = nodePtr; + while (nodePtr != NULL) + { + if (!(nodePtr->toVisit)) + { + detachNodeFromMemQueueNode(prevNodePtr, nodePtr, Q); + update_policy_status(fctx, policy, POLICY_CODE_MAXIMALLY_EXTENDED_6, nodePtr); + addNodeToMemQueue(nodePtr, &maximalyExtended); + nodePtr = prevNodePtr; + } + getMemQueueNextElementAfterRemovalPtr(prevNodePtr, nodePtr, Q); + } + QNumElements = getMemQueueNumElements(Q); + fctx->extendingLastRelScanned = -1; + + /* this is the main iteration loop where we choose the next relation to extend to and + * indeed extend to it all the tuple sets that needs to extend to it */ + while ((relToCheck = policy(fctx, Q, QNumElements)) > -1) + { + _initializeMemQueue(&needsChanging, INFINITY); + _initializeMemQueue(¬Involved, INFINITY); + + /* The last relation we checked. */ + fctx->extendingLastRelScanned = relToCheck; + bool attemptIndexScan = true; + + /* before attempting to scan a relation using indices, we check it it has indices at all */ + if (fctx->noIndexScans || (!fctx->relsHasIndex[relToCheck])) + attemptIndexScan = false; + + bool firstTSet = true; + bool firstAtt = true; + int paramNum = -1; + + nodePtr = getMemQueueFirstElementPtr(Q); + /* Here we check if we SHOULD scan using an index and formulate a proper + * query to retrieve the needed tuples */ + if (attemptIndexScan) + { + int numTSetsInQuery = 0; + + while (nodePtr) + { + tset = getMemQueueElement(nodePtr); + if (varNthBitFromLeft(nodePtr->toVisit, relToCheck)) + { + numTSetsInQuery++; + } + nodePtr = getMemQueueNextElementPtr(nodePtr); + } + + if (!(numTSetsInQuery > 0)) + attemptIndexScan = false; + else + { + if (fctx->relsPages[relToCheck] > + (INDEX_AND_PLAN_BASE_FACTOR + + ((INDEX_AND_PLAN_PER_TUPLE_FACTOR_CPU_COST + INDEX_AND_PLAN_PER_TUPLE_FACTOR) * numTSetsInQuery))) + attemptIndexScan = true; + else + attemptIndexScan = false; + } + + if (query == NULL && attemptIndexScan) + { + if (fctx->querySize < 1) + { + int resultAttNamesSize = 0; + + for (i = 0; i < fctx->resultTupleNAtt; i++) + resultAttNamesSize += strlen(fctx->resultTupleAttNames[i]); + querySize = 256 + (avgTSetSize * numTSetsInQuery) + + (10 + resultAttNamesSize) * fctx->relsNAtt[relToCheck]; + fctx->querySize = querySize; + } + query = (char *) palloc(querySize); + } + + /* so we confirmed we think we should use an index. Here we formulate a proper query*/ + if (attemptIndexScan) + { + fctx->queryParams = getAndExpandDatumArray(fctx->queryParams + ,fctx->queryParamsSize, numTSetsInQuery * fctx->resultTupleNAtt); + fctx->queryParamsTypes = getAndExpandOidArray(fctx->queryParamsTypes + ,fctx->queryParamsSize, numTSetsInQuery * fctx->resultTupleNAtt); + if (fctx->queryParamsSize < numTSetsInQuery * fctx->resultTupleNAtt) + fctx->queryParamsSize = numTSetsInQuery * fctx->resultTupleNAtt; + Datum *params = fctx->queryParams; + Oid *types = fctx->queryParamsTypes; + char paramStr[12]; + + paramNum = 0; + char *to = (char *) query; + + nodePtr = getMemQueueFirstElementPtr(Q); + while (nodePtr) + { + tset = getMemQueueElement(nodePtr); + if (varNthBitFromLeft(nodePtr->toVisit, relToCheck)) + { + if (!firstTSet) + query = addAndExpandStringBy(query, &querySize, " UNION ALL", BLCKSZ, &to + ,&toFreeQuery); + firstTSet = false; + query = addAndExpandStringBy(query, &querySize, "(" + ,BLCKSZ, &to, &toFreeQuery); + query = addAndExpandStringBy(query, &querySize, fctx->queries[relToCheck] + ,BLCKSZ, &to, &toFreeQuery); + firstAtt = true; + for (i = 0; i < fctx->relsNAtt[relToCheck]; i++) + { + if (tset->n[fctx->relsAttNumsAtTupleSet[relToCheck][i]] != 'n') + { + if (firstAtt) + { + query = addAndExpandStringBy(query, &querySize, " WHERE " + ,BLCKSZ, &to, &toFreeQuery); + firstAtt = false; + } + else + { + query = addAndExpandStringBy(query, &querySize, " AND " + ,BLCKSZ, &to, &toFreeQuery); + } + query = addAndExpandStringBy(query, &querySize, + (char *) get_attname(fctx->relsOid[relToCheck], + fctx->relsValidAttNumAtRelation[relToCheck][i]) + ,BLCKSZ, &to, &toFreeQuery); + params[paramNum] = tset->v[fctx->relsAttNumsAtTupleSet[relToCheck][i]]; + types[paramNum] = fctx->relsAttTypes[relToCheck][i]; + paramNum++; + sprintf(paramStr, "%d", paramNum); + query = addAndExpandStringBy(query, &querySize, "=$" + ,BLCKSZ, &to, &toFreeQuery); + query = addAndExpandStringBy(query, &querySize, paramStr + ,BLCKSZ, &to, &toFreeQuery); + } + } + query = addAndExpandStringBy(query, &querySize, " LIMIT 1)", BLCKSZ, &to + ,&toFreeQuery); + } + nodePtr = getMemQueueNextElementPtr(nodePtr); + } + } + fctx->querySize = querySize; + fctx->query = query; + } + + _SPI_plan *plan = NULL; + Portal portal = NULL; + bool usingSeqScan = true; + /* here we prepare the index based query. and check if the plan includes a sequential + * scan, in which case we should just use our already opened cursor to the relation. + * This is done because of deficiency in the capability of the planner to accommodate + * our complex index based query */ + if (attemptIndexScan) + { + if ((plan = SPI_prepare(query, paramNum, fctx->queryParamsTypes)) == NULL) + elog(ERROR, "PSFD: SPI_prepare('%s') returns NULL", query); + Plan *planTree; + ListCell *plan_list_item = list_head(plan->ptlist); + + planTree = lfirst(plan_list_item); + usingSeqScan = isPlanUsingSeqScan(planTree); + } + else + { + usingSeqScan = true; + } + + + if (usingSeqScan) + { + if (attemptIndexScan) + { + SPI_freeplan(plan); + } + plan = fctx->plans[relToCheck]; + portal = fctx->portals[relToCheck]; + SPI_cursor_move(portal, false, FETCH_ALL); + SPI_freetuptable(SPI_tuptable); + } + else + { + if ((portal + = SPI_cursor_open(NULL, plan, fctx->queryParams, NULL, true)) == NULL) + elog(ERROR, "PSFD: SPI_cursor_open('%s') returns NULL", query); + } + + /* Lets remove a tuple from either our usual portal or specially opened index + * based portal */ + SPI_cursor_fetch(portal, true, 1); + + retTSet = NULL; + endScan = false; + firstPass = true; + prevNodePtr = NULL; + scanNotEmpty = false; + + /* This loop handles extending of all the tuple sets to the relation we are currently + * attempting to extend to. */ + while ((SPI_processed > 0) && (!endScan)) + { + tuple->t = SPI_tuptable->vals[0]; + tuple->deformed = false; + dsTuple->firstIteration = true; + scanNotEmpty = true; + isNull = false; + if (fctx->extendingPolicy == POLICY_NAIVE) + endScan = false; + else + endScan = true; + /* basically we move tuple sets based on their charecteristics of their potential + * to be extended (need extend, already extend, cannot extend...) + * The first pass does the initial redirections and attempt to extend to the first tuple */ + if (firstPass) + { + detachHeadNodeFromMemQueue(nodePtr, Q); + while (nodePtr) + { + if (varNthBitFromLeft(nodePtr->toVisit, relToCheck)) + { + tset = getMemQueueElement(nodePtr); + endScan = false; + retTSet = JCCTSetAndTupleAndReturnTSet(fctx, tset, tuple + ,SPI_tuptable->tupdesc, relToCheck, dsTuple); + if (retTSet != NULL) + { + varSetNthBitFromLeft(nodePtr->relsOfTuples, relToCheck); + varUnSetNthBitFromLeft(nodePtr->toVisit, relToCheck); + nodePtr->toVisit |= ((fctx->bits_scheme_graph[relToCheck]) + & (~(nodePtr->relsOfTuples)) & (~(nodePtr->visited))); + if (nodePtr->toVisit) + { + mergeOutOfMemQueueIntoNode(fctx, &needsChanging, nodePtr, false, true); + mergeOutOfMemQueueIntoNode(fctx, Q, nodePtr, false, true); + if (nodePtr->toVisit) + { + update_policy_status(fctx, policy, POLICY_CODE_NOT_INVOLVED_1, nodePtr); + addNodeToMemQueue(nodePtr, ¬Involved); + } + else + { + update_policy_status(fctx, policy, POLICY_CODE_MAXIMALLY_EXTENDED_0, + nodePtr); + addNodeToMemQueue(nodePtr, &maximalyExtended); + } + } + else + { + update_policy_status(fctx, policy, POLICY_CODE_MAXIMALLY_EXTENDED_1, + nodePtr); + addNodeToMemQueue(nodePtr, &maximalyExtended); + } + } + else + addNodeToMemQueue(nodePtr, &needsChanging); + } + else if (!(nodePtr->toVisit)) + { + update_policy_status(fctx, policy, POLICY_CODE_MAXIMALLY_EXTENDED_2, nodePtr); + addNodeToMemQueue(nodePtr, &maximalyExtended); + } + else + { + update_policy_status(fctx, policy, POLICY_CODE_NOT_INVOLVED_2, nodePtr); + addNodeToMemQueue(nodePtr, ¬Involved); + } + detachHeadNodeFromMemQueue(nodePtr, Q); + } + firstPass = false; + } + else + { + nodePtr = getMemQueueFirstElementPtr(&needsChanging); + prevNodePtr = nodePtr; + while (nodePtr) + { + tset = getMemQueueElement(nodePtr); + endScan = false; + retTSet = JCCTSetAndTupleAndReturnTSet(fctx, tset, tuple + ,SPI_tuptable->tupdesc, relToCheck, dsTuple); + if (retTSet != NULL) + { + varSetNthBitFromLeft(nodePtr->relsOfTuples, relToCheck); + varUnSetNthBitFromLeft(nodePtr->toVisit, relToCheck); + nodePtr->toVisit |= ((fctx->bits_scheme_graph[relToCheck]) + & (~(nodePtr->relsOfTuples)) & (~(nodePtr->visited))); + detachNodeFromMemQueueNode(prevNodePtr, nodePtr, &needsChanging); + if (nodePtr->toVisit) + { + mergeOutOfMemQueueIntoNode(fctx, &needsChanging, nodePtr, false, true); + if (nodePtr->toVisit) + { + update_policy_status(fctx, policy, POLICY_CODE_NOT_INVOLVED_3, nodePtr); + addNodeToMemQueue(nodePtr, ¬Involved); + } + else + { + update_policy_status(fctx, policy, POLICY_CODE_MAXIMALLY_EXTENDED_3, + nodePtr); + addNodeToMemQueue(nodePtr, &maximalyExtended); + } + } + else + { + update_policy_status(fctx, policy, POLICY_CODE_MAXIMALLY_EXTENDED_4, + nodePtr); + addNodeToMemQueue(nodePtr, &maximalyExtended); + } + nodePtr = prevNodePtr; + } + getMemQueueNextElementAfterRemovalPtr(prevNodePtr, nodePtr, &needsChanging); + } + } + SPI_freetuptable(SPI_tuptable); + SPI_cursor_fetch(portal, true, 1); + } + SPI_freetuptable(SPI_tuptable); + + /* we finished here extending to the specific relation. + * we now set all the non extended tuple sets to being visited. */ + if (!scanNotEmpty) + setVisitedQ = Q; + else + setVisitedQ = &needsChanging; + nodePtr = getMemQueueFirstElementPtr(setVisitedQ); + prevNodePtr = nodePtr; + while (nodePtr != NULL) + { + if (varNthBitFromLeft(nodePtr->toVisit, relToCheck)) + { + varUnSetNthBitFromLeft(nodePtr->toVisit, relToCheck); + varSetNthBitFromLeft(nodePtr->visited, relToCheck); + } + if (!(nodePtr->toVisit)) + { + detachNodeFromMemQueueNode(prevNodePtr, nodePtr, setVisitedQ); + update_policy_status(fctx, policy, POLICY_CODE_MAXIMALLY_EXTENDED_5, nodePtr); + addNodeToMemQueue(nodePtr, &maximalyExtended); + nodePtr = prevNodePtr; + } + getMemQueueNextElementAfterRemovalPtr(prevNodePtr, nodePtr, setVisitedQ); + } + + /* finally lets return all the tuple sets we redirected based on their extending potential + * to other queues, to Q to start the whole process again. */ + if (scanNotEmpty) + recombineQueues(Q, 2, &needsChanging, ¬Involved); + QNumElements = getMemQueueNumElements(Q); + if (!usingSeqScan) + { + SPI_cursor_close(portal); + SPI_freeplan(plan); + } + } + pfree(tuple); + pfree(dsTuple); + if (!isMemQueueEmpty(Q)) + elog(ERROR, "Q not EMPTY before recombine!"); + if (!isMemQueueEmpty(¬Involved)) + elog(INFO, "NotInvolved NOT EMPTY!"); + if (!isMemQueueEmpty(&needsChanging)) + elog(INFO, "needsChanging NOT EMPTY!"); + + /* finally we move all the maximally extended tuple sets back into Q to return from the function */ + recombineQueues(Q, 1, &maximalyExtended); + } + + /* + * This procedure updates the relations we need to scan for generating + * alternative tuple sets (algorithm FD terminology) which greatly reduces + * the time of the algorithm. + * Note, that here we changed the meaning of ptr->toVisit to mean that + * we have to generate alternative tuple set with a relation in toVisit.*/ + void + updateOnDemandRelationsToScan(alg_fctx * fctx, memQueue * Q) + { + RBITS relationsToScan = 0; + int i = 0, + j = 0, + k = 0; + memQueueNode *ptr = getMemQueueFirstElementPtr(Q); + int numAtt = NUMATT; + int numOfTuples; + int numOfTuplesInIntersection = 0; + int tsetAtt; + int tsetAttributes[numAtt]; + RBITS RNeighboursIntersectTSetRelations = 0; + RBITS relsOfTuples; + RBITS relsMask = (~0x0); + + relsMask >>= fctx->numRels; + relsMask = ~relsMask; + TSet tset = NULL; + bool addRelation = false; + + /* we pass over all the tuple sets we wish to generate alternative tuple sets + * for and update the list of relations we will need to scan if we suspect it + * is possible we will need to scan it for some tuple sets. + * The algorithm itself is in the FD algorithm docs. */ + while (ptr) + { + tset = ptr->tset; + ptr->toVisit = 0; + relsOfTuples = ptr->relsOfTuples; + numOfTuples = numOfTuplesInTSet(fctx, tset->tids); + if (numOfTuples > 1) + { + relationsToScan |= relsOfTuples; + ptr->toVisit |= relsOfTuples; + for (i = 0; i < fctx->numRels; i++) + { + for (k = 0; k < numAtt; k++) + tsetAttributes[k] = 0; + RNeighboursIntersectTSetRelations = (fctx->bits_scheme_graph[i] & relsOfTuples); + if (!(RNeighboursIntersectTSetRelations)) + continue; + j = 0; + numOfTuplesInIntersection = 0; + while (RNeighboursIntersectTSetRelations) + { + if (varNthBitFromLeft(RNeighboursIntersectTSetRelations, 0)) + { + numOfTuplesInIntersection++; + for (k = 0; k < fctx->relsNAtt[j]; k++) + { + tsetAttributes[fctx->relsAttNumsAtTupleSet[j][k]]++; + } + } + j++; + RNeighboursIntersectTSetRelations <<= 1; + } + addRelation = false; + for (k = 0; k < fctx->relsNAtt[i]; k++) + { + tsetAtt = fctx->relsAttNumsAtTupleSet[i][k]; + if (tsetAttributes[tsetAtt] == numOfTuplesInIntersection) + { + if (tsetAttIsNull(tset, tsetAtt)) + { + addRelation = false; + break; + } + } + else if (tsetAttributes[tsetAtt] > 0) + { + addRelation = true; + } + } + if (addRelation) + { + varSetNthBitFromLeft(ptr->toVisit, i); + varSetNthBitFromLeft(relationsToScan, i); + } + } + } + else if (!(relsOfTuples)) + { + ptr->toVisit = relsMask; + relationsToScan = relsMask; + } + ptr = getMemQueueNextElementPtr(ptr); + } + fctx->relationsToScan = relationsToScan; + } + + + /* here we remove one page from preComplete into Q */ + void + onDemandPreCompleteRemovePage(alg_fctx * fctx, FuncCallContext *funcctx, memQueue * Q) + { + clearMemQueue(fctx, Q, true); + bool should_free; + HeapTuple tuptset; + int readSize = 0; + + while (SQNotEmpty(&fctx->precomplete)) + { + tuptset = SQGetNextElement(fctx, funcctx, &fctx->precomplete, &should_free, true); + readSize += tupleSize(tuptset); + if (readSize > (BLCKSZ)) + { + SQSetMemOverflowTuple(&fctx->precomplete, tuptset); + break; + } + else + { + addTupleSetToMemQueue(fctx, Q, newTSet___(fctx, tuptset)); + } + } + updateOnDemandRelationsToScan(fctx, Q); + } + + + /* Here we take a relation to scan from the list of relations to scan for + * the on demand procedure */ + int + getRandomNextRelationToScan(alg_fctx * fctx, int lastScannedRelation) + { + RBITS relationsToScan = fctx->relationsToScan; + RBITS tmp = fctx->relationsToScan; + int numRelsToScan = 0; + + while (tmp) + { + if (varNthBitFromLeft(tmp, 0)) + numRelsToScan++; + tmp <<= 1; + } + if (numRelsToScan > 0) + { + int j = 0; + int k = 0; + int i = ((int) (numRelsToScan * (rand() / (RAND_MAX + 1.0)))) + 1; + + if (i > numRelsToScan) + elog(ERROR, "getRandomNextRelationToScan (i>numRelsToScan)"); + while ((j < i) && (j < numRelsToScan)) + { + if (varNthBitFromLeft(relationsToScan, k)) + { + j++; + } + k++; + } + k--; + varUnSetNthBitFromLeft(fctx->relationsToScan, k); + return k; + } + return -1; + } + + /* Here we retrieve one tuple at a time from the relation we are currently scanning + * and if we reach the end of the relation we cycle to the next relation in the list + * automatically. The name "..NextPage.." is left to accommodate the original terminology + * of the FD algorithm, however, the page is indeed read in the backend and there is no + * actual need to load a whole page again here. */ + void + onDemandRetrieveNextPageFromR(alg_fctx * fctx, FuncCallContext *funcctx) + { + OnDemandState *S = fctx->onDemandState; + + if (S->lastTuptable) + { + SPI_freetuptable(S->lastTuptable); + S->lastTuptable = NULL; + } + if (S->P->t == NULL) + { + S->cur_rel = getRandomNextRelationToScan(fctx, -1); + if (S->cur_rel >= 0) + { + SPI_cursor_move(S->portals[S->cur_rel], false, FETCH_ALL); + SPI_freetuptable(SPI_tuptable); + } + } + while (S->cur_rel >= 0) + { + SPI_cursor_fetch(S->portals[S->cur_rel], true, 1); + if (SPI_processed > 0) + { + S->P->t = SPI_tuptable->vals[0]; + S->P->deformed = false; + S->Pdesc = SPI_tuptable->tupdesc; + S->PrelID = S->cur_rel; + S->lastTuptable = SPI_tuptable; + return; + } + SPI_freetuptable(SPI_tuptable); + if ((S->cur_rel = getRandomNextRelationToScan(fctx, S->cur_rel)) < 0) + break; + SPI_cursor_move(S->portals[S->cur_rel], false, FETCH_ALL); + SPI_freetuptable(SPI_tuptable); + } + S->P->t = NULL; + return; + } + + /* This procedure is the On demand procedure which is a FD algorithm specific + * terminology for generating alternative tuple sets on demand, i.e., retrieving + * enough alternative tuple sets to fit into allocated memory. The implementation + * here is very close to the implementation suggested in the FD algorithm docs. + * The inputs are also documented in the FD algorithm docs.*/ + void + OnDemandGetAlternativeTupleSets(alg_fctx * fctx, FuncCallContext *funcctx, + memQueue * out, bool trueUseMemorySizeFalseUseNumTupleSets, int SZ, + int numTupleSetsToReturn, bool addToComplete) + { + OnDemandState *S = fctx->onDemandState; + TSet memQTSet = NULL; + TSet alternativeTSet = NULL; + + if (isMemQueueEmpty(S->Q)) + { + fctx->relationsToScan = 0; + /* here we read a page from precomplete and a tuple from the relations to scan */ + while (!(fctx->relationsToScan)) + { + onDemandPreCompleteRemovePage(fctx, funcctx, S->Q); + if (addToComplete) + { + memQueueNode *ptr = getMemQueueFirstElementPtr(S->Q); + TSet tset = NULL; + int i; + char nulls[NUMATT]; + + for (i = FIRSTATT; i < NUMATT; i++) + nulls[i] = 'n'; + nulls[LABELS] = ' '; + HeapTuple tempTuple; + + while (ptr != NULL) + { + tset = getMemQueueElement(ptr); + if (numOfTuplesInTSet(fctx, tset->tids) > 0) + { + tempTuple = clearValuesFromTSet(fctx, tset, nulls); + SQAddElement(fctx, funcctx, &fctx->complete, tempTuple); + heap_freetuple(tempTuple); + } + ptr = getMemQueueNextElementPtr(ptr); + } + } + if (isMemQueueEmpty(S->Q)) + return; + } + S->P->t = NULL; + S->p = 1; + S->q = 0; + S->qPtr = getMemQueueFirstElementPtr(S->Q); + onDemandRetrieveNextPageFromR(fctx, funcctx); + } + while (1) + { + if (trueUseMemorySizeFalseUseNumTupleSets && numPagesInMemQueue(out) >= SZ) + return; + else if (!trueUseMemorySizeFalseUseNumTupleSets + && numTupleSetsToReturn <= getMemQueueNumElements(out)) + return; + if (S->q > 0) + S->qPtr = getMemQueueNextElementPtr(S->qPtr); + S->q++; + if (S->q > getMemQueueNumElements(S->Q)) + { + S->p++; + S->q = 1; + S->qPtr = getMemQueueFirstElementPtr(S->Q); + } + if (S->p > 1) + { + S->p = 1; + onDemandRetrieveNextPageFromR(fctx, funcctx); + } + if (S->P->t == NULL) + { + fctx->relationsToScan = 0; + while (!(fctx->relationsToScan)) + { + onDemandPreCompleteRemovePage(fctx, funcctx, S->Q); + if (addToComplete) + { + memQueueNode *ptr = getMemQueueFirstElementPtr(S->Q); + TSet tset = NULL; + int i; + char nulls[NUMATT]; + + for (i = FIRSTATT; i < NUMATT; i++) + nulls[i] = 'n'; + nulls[LABELS] = ' '; + HeapTuple tempTuple; + + while (ptr != NULL) + { + tset = getMemQueueElement(ptr); + if (numOfTuplesInTSet(fctx, tset->tids) > 0) + { + tempTuple = clearValuesFromTSet(fctx, tset, nulls); + SQAddElement(fctx, funcctx, &fctx->complete, tempTuple); + heap_freetuple(tempTuple); + } + ptr = getMemQueueNextElementPtr(ptr); + } + } + if (isMemQueueEmpty(S->Q)) + return; + } + S->p = 1; + S->q = 1; + S->qPtr = getMemQueueFirstElementPtr(S->Q); + onDemandRetrieveNextPageFromR(fctx, funcctx); + } + /* here we generate the alternative tuple set with a tuple set from precomplete + * and a tuple from the relation */ + memQTSet = getMemQueueElement(S->qPtr); + if ((S->qPtr->relsOfTuples) && (varNthBitFromLeft(S->qPtr->toVisit, S->PrelID))) + { + alternativeTSet = generateAlternativeTupleSet(fctx, memQTSet, S->qPtr->relsOfTuples, + S->P, S->Pdesc, S->PrelID); + } + /* this handles the singleton tuple sets that are generated by taking the empty tuple + * set and generating alternative tuple sets to it with tuples from the relations which + * trivially results in the singleton tuple set that holds the tuple from the relation */ + else if (!(S->qPtr->relsOfTuples)) + { + makeSureDeformedTuple(fctx, S->P, S->Pdesc, S->cur_rel); + alternativeTSet = create_tuple_set(fctx, S->P, S->Pdesc, S->PrelID); + } + else + alternativeTSet = NULL; + + /* finally if we indeed generated the alternative tuple set we output it */ + if (alternativeTSet != NULL) + { + addTupleSetToMemQueue(fctx, out, alternativeTSet); + } + } + } + + /* simple floor function */ + int + algFloor(float value) + { + return (int) value; + } + + /* simple ceiling function */ + int + algCeiling(float value) + { + if (value > (int) value) + return (((int) value) + 1); + else + return (int) value; + } + + /* simple max function */ + double + max(double a, double b) + { + if (a > b) + return a; + else + return b; + } + + /*simple min function */ + double + min(double a, double b) + { + if (a < b) + return a; + else + return b; + } + + /* getting the upper bound calculated by the adaptive algorithm */ + int + getAdaptiveUpperBound(alg_fctx * fctx) + { + if (fctx->dynamic_extend_cap->stage > 0) + return fctx->dynamic_extend_cap->nextUpperBound; + else + return ADAPTIVE_EXTEND_UPPER_BOUND_MAX; + } + + /* the core of the adaptive algorithm of an upper bound for the number of + * tuple sets to be extended in the extending process at once. + * This is not documented in the FD algorithm docs but it is an adhoc + * algorithm created for efficiency reasons by using trial and errors. + * It is a mathematical formulation which is straight forward from the code. */ + void + updateAdaptiveScore(alg_fctx * fctx, double time) + { + adaptive_extend_upperbound *ad = fctx->dynamic_extend_cap; + double currentScore = ((ad->actualInputedExtendTuples ^ 2) / time); + + if (ad->stage == 0) + { + ad->previousScore = currentScore; + if ((2 * ad->maxInputedExtendTuples) <= ADAPTIVE_EXTEND_UPPER_BOUND_MAX) + ad->nextUpperBound = 2 * ad->maxInputedExtendTuples; + else + ad->nextUpperBound = ADAPTIVE_EXTEND_UPPER_BOUND_MAX; + ad->stage = 1; + return; + } + if (ad->stage == 1) + { + if (currentScore > ad->previousScore) + { + if (ad->actualInputedExtendTuples > ad->nextUpperBound) + { + ad->nextUpperBound = ad->actualInputedExtendTuples; + } + } + else + { + ad->stage = 2; + } + } + if (ad->stage == 2) + { + int currentUpperBound = ad->nextUpperBound; + double halfNormalizedDiffScore + = (max(currentScore, ad->previousScore) + - min(currentScore, ad->previousScore)) / (2 * max(currentScore, ad->previousScore)); + + if (currentScore > ad->previousScore) + ad->nextUpperBound = ad->nextUpperBound + ADAPTIVE_EXTEND_UPPER_BOUND_FIXED_PENALTY_INC + + (int) (halfNormalizedDiffScore * ad->nextUpperBound); + else + ad->nextUpperBound = ad->nextUpperBound - + (ADAPTIVE_EXTEND_UPPER_BOUND_FIXED_PENALTY_DEC + (int) (halfNormalizedDiffScore * ad->nextUpperBound)); + if (ad->nextUpperBound < 100) + ad->nextUpperBound = currentUpperBound; + } + ad->previousScore = currentScore; + } diff -crN pgsql/contrib/fulldisjunctions/algutils.h pgsql-fd/contrib/fulldisjunctions/algutils.h *** pgsql/contrib/fulldisjunctions/algutils.h 1969-12-31 19:00:00.000000000 -0500 --- pgsql-fd/contrib/fulldisjunctions/algutils.h 2006-07-30 13:30:12.000000000 -0400 *************** *** 0 **** --- 1,111 ---- + /* + * Copyright (c) 2006 Itzhak Fadida. All Rights Reserved. + * See the README file for a detailed BSD License. + * This file and all related files are under the BSD license. + * */ + + #ifndef ALGUTILS_H + #define ALGUTILS_H + + #ifdef DEBUG + #else + #define NDEBUG + #endif + + #include + + #include "postgres.h" + #include "utils/palloc.h" + #include "algstructs.h" + + /* constants to help in the decision if to use an index scan when extending */ + #define INDEX_AND_PLAN_PER_TUPLE_FACTOR 0.1 + #define INDEX_AND_PLAN_PER_TUPLE_FACTOR_CPU_COST (0.001) + #define INDEX_AND_PLAN_BASE_FACTOR 0.1 + + /* + * adaptive upper bound algorithm constants. These are estimates for a pentium 1.6 machine + * which is assumed to be a starting point. Perhaps in a few years these could be increased + * a bit. but these are just a starting point, the algorithm increase them in mid runs anyway. + * */ + #define ADAPTIVE_EXTEND_UPPER_BOUND_MAX 500 + #define ADAPTIVE_EXTEND_UPPER_BOUND_FIXED_PENALTY_INC 25 + #define ADAPTIVE_EXTEND_UPPER_BOUND_FIXED_PENALTY_DEC 15 + + /* note! the numbers matters! only add codes after last code! */ + enum policies_update_codes + { + POLICY_CODE_DELETED_NODE_0 = 0, + POLICY_CODE_DELETED_NODE_1 = 1, + POLICY_CODE_DELETED_NODE_2 = 2, + POLICY_CODE_DELETED_NODE_3 = 3, + POLICY_CODE_DELETED_NODE_4 = 4, + POLICY_CODE_DELETED_NODE_5 = 5, + POLICY_CODE_MAXIMALLY_EXTENDED_0 = 6, + POLICY_CODE_MAXIMALLY_EXTENDED_1 = 7, + POLICY_CODE_MAXIMALLY_EXTENDED_2 = 8, + POLICY_CODE_MAXIMALLY_EXTENDED_3 = 9, + POLICY_CODE_MAXIMALLY_EXTENDED_4 = 10, + POLICY_CODE_MAXIMALLY_EXTENDED_5 = 11, + POLICY_CODE_MAXIMALLY_EXTENDED_6 = 12, + POLICY_CODE_NOT_INVOLVED_1 = 13, + POLICY_CODE_NOT_INVOLVED_2 = 14, + POLICY_CODE_NOT_INVOLVED_3 = 15 + }; + + /* policy functions interface definition. Use this interface for new policy + * functions.*/ + typedef int (*POLICY_FUNC) (alg_fctx * fctx, memQueue * Q, int tsetsNum); + + /* code that symbolises each policy */ + #define POLICY_MAJORITY 0 + #define POLICY_MINCOST 1 + #define POLICY_RANDOM 2 + #define POLICY_NAIVE 3 + + /* calculates a heaptuple size */ + #define tupleSize(tuple)\ + (HEAPTUPLESIZE + tuple->t_len) + + /* + * Call the type specific '=' function\ + */ + #define areAttributesEqual_RT(fctx, attID, lvalue, rvalue)\ + DatumGetBool(\ + FunctionCall2(&(fctx->tupleSetAttEQFunctions[attID]->eq_opr_finfo) \ + ,lvalue, rvalue)) + + /* + * stpcpy is not mine but its difficult to get its header working all the + * time. Thus i am redeclaring it here for safety. No harm anycase. + */ + extern char *stpcpy(char *__dest, const char *__src); + + extern Datum myDatumCopy(Datum value, bool typByVal, int typLen); + extern void myDatumFree(Datum value, bool typByVal, int typLen); + extern void sortOidArray(Oid *array, int numElements); + extern void updateMaxTupleSize(alg_fctx * fctx, int relID, HeapTuple tuple); + extern void updateResultTupleMaxSize(alg_fctx * fctx); + extern TypeCacheEntry *getEQFunction(Oid typeid); + extern char *addAndExpandStringBy(char *oldStr, int *oldStrAllocSize, char *addStr + ,int sizeToAdd, char **relative_ptr, bool *free_old_str); + extern bool isResultTupleAttOccursInRelID(alg_fctx * fctx, int resultTupleAttID, int relID); + extern bool isResultTupleAttOccursInSomeRelID(alg_fctx * fctx, int resultTupleAttID + ,bytea *relsID); + extern bool isResultTupleAttOccursInSomeRelIDWithSpecifiedRelations(alg_fctx * fctx, + int resultTupleAttID, RBITS relationsToCheck); + extern bool isPlanUsingSeqScan(Plan *planTree); + extern void Extend(alg_fctx * fctx, memQueue * Q); + extern void updateOnDemandRelationsToScan(alg_fctx * fctx, memQueue * Q); + extern void onDemandPreCompleteRemovePage(alg_fctx * fctx, FuncCallContext *funcctx, memQueue * Q); + extern int getRandomNextRelationToScan(alg_fctx * fctx, int lastScannedRelation); + extern void onDemandRetrieveNextPageFromR(alg_fctx * fctx, FuncCallContext *funcctx); + extern void OnDemandGetAlternativeTupleSets(alg_fctx * fctx, FuncCallContext *funcctx, + memQueue * out, bool trueUseMemorySizeFalseUseNumTupleSets, int SZ, + int numTupleSetsToReturn, bool addToComplete); + extern int algFloor(float value); + extern int algCeiling(float value); + extern int getAdaptiveUpperBound(alg_fctx * fctx); + extern void updateAdaptiveScore(alg_fctx * fctx, double time); + + #endif /* ALGUTILS_H */ diff -crN pgsql/contrib/fulldisjunctions/createTable.py pgsql-fd/contrib/fulldisjunctions/createTable.py *** pgsql/contrib/fulldisjunctions/createTable.py 1969-12-31 19:00:00.000000000 -0500 --- pgsql-fd/contrib/fulldisjunctions/createTable.py 2006-07-30 15:55:58.000000000 -0400 *************** *** 0 **** --- 1,51 ---- + import random + import time + import datetime + import sys + import os + import csv + import popen2 + import ConfigParser + from sets import Set as set + PSQLDIR="" + TMPDIR=os.getcwd()+"/" + SAMPLE=int(sys.argv[1]) + POPULATION=int(sys.argv[2]) + DBNAME=sys.argv[3] + TABLENAME=sys.argv[4] + ATT1=sys.argv[5] + ATT2=sys.argv[6] + ERRORSLOGFILE=os.getcwd()+"/.randomtest_errors" + def logerrors(ferr): + errfile=open(ERRORSLOGFILE,"a") + errfile.write(ferr.read()) + errfile.close() + + def createTable(db, sampleSize, population, tablename,att1,att2): + rand=[] + rand.append(set([])) + while len(rand[0])resultTupleNAtt; l++) + { + + toh = (char *) stpcpy(toh, fctx->resultTupleAttNames[l]); + + toh = (char *) stpcpy(toh, " "); + + toh = (char *) stpcpy(toh, SPI_gettype(fctx->resultTupleDesc, l + 1)); + + if (l != (fctx->resultTupleNAtt - 1)) + + toh = (char *) stpcpy(toh, ","); + + } + toh = (char *) stpcpy(toh, ")"); + + VARATT_SIZEP(resultTupleRecord) = strlen(header) + VARHDRSZ; + + PG_RETURN_TEXT_P(resultTupleRecord); + + } diff -crN pgsql/contrib/fulldisjunctions/Makefile pgsql-fd/contrib/fulldisjunctions/Makefile *** pgsql/contrib/fulldisjunctions/Makefile 1969-12-31 19:00:00.000000000 -0500 --- pgsql-fd/contrib/fulldisjunctions/Makefile 2006-07-30 16:16:02.000000000 -0400 *************** *** 0 **** --- 1,19 ---- + # $PostgreSQL$ + + MODULE_big = fulldisjunctions + SRCS += algstructs.c algutils.c getfdr.c odmbfd.c queues.c tset.c + OBJS = $(SRCS:.c=.o) + DATA_built = fulldisjunctions.sql + DATA = uninstall_fulldisjunctions.sql + DOCS = README.fulldisjunctions + REGRESS = fulldisjunctions + + ifdef USE_PGXS + PGXS := $(shell pg_config --pgxs) + include $(PGXS) + else + subdir = contrib/fulldisjunctions + top_builddir = ../.. + include $(top_builddir)/src/Makefile.global + include $(top_srcdir)/contrib/contrib-global.mk + endif diff -crN pgsql/contrib/fulldisjunctions/odmbfd.c pgsql-fd/contrib/fulldisjunctions/odmbfd.c *** pgsql/contrib/fulldisjunctions/odmbfd.c 1969-12-31 19:00:00.000000000 -0500 --- pgsql-fd/contrib/fulldisjunctions/odmbfd.c 2006-07-29 20:54:13.000000000 -0400 *************** *** 0 **** --- 1,356 ---- + /* + * Copyright (c) 2006 Itzhak Fadida. All Rights Reserved. + * See the README file for a detailed BSD License. + * This file and all related files are under the BSD license. + * */ + + #include "postgres.h" + #include "funcapi.h" + #include "catalog/pg_type.h" + #include "executor/spi.h" + #include "executor/spi_priv.h" + #include + #include "utils/lsyscache.h" + #include "utils/typcache.h" + #include "utils/elog.h" + #include "utils/memutils.h" + + #ifdef PG_MODULE_MAGIC + PG_MODULE_MAGIC; + #endif /* */ + + #include "algstructs.h" + #include "tset.h" + #include "tsetfuncs.h" + #include "queues.h" + #include "queuesfuncs.h" + #include "algutils.h" + + #define DEFAULT_MB 100 + #define PRINT 1 + + enum odmbfd_algorithm_state + { + ALGORITHM_START = 0, + /* Load all the tuples from the relations into the virtual PreComplete */ + MAIN_PRELOADING, + MAIN_WHILE_PRECOMPLETE_NOTEMPTY, + MAIN_WHILE_Q_NOTEMPTY, + /* Output the result tuple sets */ + MAIN_PRINT, + ALGORITHM_END + }; + + void + initialize_odmbfd_structures(PG_FUNCTION_ARGS, alg_fctx * fctx, FuncCallContext *funcctx) + { + /* initialize tuple stores. */ + SQInitialize(fctx, funcctx, &fctx->complete); + SQInitialize(fctx, funcctx, &fctx->precomplete); + + /* additional, per algorithm arguments (for future algorithms) */ + if (fctx->nargs >= 6) + { + /* MEMORY MUST BE ALLOCATED IN PAGES! */ + fctx->MB = PG_GETARG_INT32(5); + if (fctx->MB < 2) + elog(ERROR, "The memory allocation must be greater than 1, prefferably at least as the number of relations inputted and bigger is faster (commonly at least 100)!"); + } + else + fctx->MB = DEFAULT_MB; + + _initializeMemQueue(&fctx->Q, (fctx->MB * BLCKSZ)); + + /* + * potentially 1 page (= BLCKSZ) and MB pages that could be free (however, + * the algorithm will determine how much to use) + */ + _initializeMemQueue(&fctx->E, ((1 + fctx->MB) * BLCKSZ)); + + /* persistant state for the On Demand procedure. */ + fctx->onDemandState = (OnDemandState *) palloc(sizeof(OnDemandState)); + OnDemandState *S = fctx->onDemandState; + + S->Q = palloc(sizeof(memQueue)); + S->lastTuptable = NULL; + S->portals = (Portal *) palloc(fctx->numRels * sizeof(Portal)); + S->portals[0] = NULL; + { + int i; + int maxRelNatt = 0; + + for (i = 0; i < fctx->numRels; i++) + if (maxRelNatt < fctx->relsNAtt[i]) + maxRelNatt = fctx->relsNAtt[i]; + S->P = newDTuple(fctx, maxRelNatt); + } + int i = 0; + for (i = 0; i < fctx->numRels; i++) + { + if ((S->portals[i] + = SPI_cursor_open(NULL, fctx->plans[i], NULL, NULL, true)) == NULL) + + /* + * note that read_only in cursor_open must be true otherwise ctid + * can change. + */ + elog(ERROR, "ODMBFD: SPI_cursor_open('%d') returns NULL", i); + } + _initializeMemQueue(S->Q, BLCKSZ); + + /* Here we calculate the maximal size of a tuple for each relation. */ + { + int i = 0; + + for (i = 0; i < fctx->numRels; i++) + { + SPI_cursor_move(fctx->portals[i], false, FETCH_ALL); + SPI_cursor_fetch(fctx->portals[i], true, 1); + while (SPI_processed > 0) + { + updateMaxTupleSize(fctx, i, SPI_tuptable->vals[0]); + SPI_freetuptable(SPI_tuptable); + SPI_cursor_fetch(fctx->portals[i], true, 1); + } + SPI_freetuptable(SPI_tuptable); + SPI_cursor_move(fctx->portals[i], false, FETCH_ALL); + } + updateResultTupleMaxSize(fctx); + fctx->assumingResultTupleMaxSize = false; + } + } + + /* + * Here we free the most important to free resources. + */ + void + clean_odmbfd_structures_on_exit(PG_FUNCTION_ARGS, alg_fctx * fctx + ,FuncCallContext *funcctx) + { + SQFinish(fctx, funcctx, &fctx->precomplete); + SPI_finish(); + MemoryContextDelete(fctx->per_query_ctx); + } + + PG_FUNCTION_INFO_V1(odmbfd); + Datum + odmbfd(PG_FUNCTION_ARGS) + { + FuncCallContext *funcctx; + alg_fctx *fctx = NULL; + + /* stuff done only on the first call of the function */ + if (SRF_IS_FIRSTCALL()) + { + MemoryContext oldcontext; + + /* create a function context for cross-call persistence */ + funcctx = SRF_FIRSTCALL_INIT(); + + /* switch to memory context appropriate for multiple function calls */ + oldcontext = MemoryContextSwitchTo(funcctx->multi_call_memory_ctx); + + fctx = (alg_fctx *) palloc(sizeof(alg_fctx)); + + fctx->trueIndexFalseNonIndexBasedAlgorithm = false; + + /* Initialize general to all future algorithms structures */ + initialize_general_structures(fcinfo, fctx, funcctx); + assert(fctx != NULL); + + funcctx->tuple_desc = BlessTupleDesc(fctx->resultTupleDesc); + + /* initialize general SPI structures */ + initialize_SPI_structures(fcinfo, fctx, !fctx->noDuplicates, funcctx); + + /* initialize this algorithm specific structures */ + initialize_odmbfd_structures(fcinfo, fctx, funcctx); + + fctx->algorithm_state = ALGORITHM_START; + + funcctx->user_fctx = fctx; + + MemoryContextSwitchTo(oldcontext); + } + + + /* stuff done on every call of the function */ + funcctx = SRF_PERCALL_SETUP(); + fctx = funcctx->user_fctx; + /* Seems that if i take this off, all kind of leaks. Better to leave this. */ + MemoryContextSwitchTo(funcctx->multi_call_memory_ctx); + + + /* Algorithm starts here. */ + while (fctx->algorithm_state != ALGORITHM_END) + { + switch (fctx->algorithm_state) + { + case ALGORITHM_START: + clearMemQueue(fctx, &fctx->Q, true); + fctx->algorithm_state = MAIN_PRELOADING; + break; + case MAIN_PRELOADING: + { + /* here we load an empty set that its union with each tuple of the relation is + * the singleton tuple of the relation itself */ + TSet emptyTSet = newEmptyTSet(fctx); + + SQAddElement(fctx, funcctx, &fctx->precomplete, emptyTSet->t); + } + fctx->algorithm_state = MAIN_WHILE_PRECOMPLETE_NOTEMPTY; + break; + case MAIN_WHILE_PRECOMPLETE_NOTEMPTY: + /* + * the ondemand->Q check is instead of the uncommited read in + * ondemand function in the thesis. more efficient, + * programming wise. + */ + if (SQNotEmpty(&fctx->precomplete) || !isMemQueueEmpty(fctx->onDemandState->Q)) + { + OnDemandGetAlternativeTupleSets(fctx, funcctx, &fctx->Q, true, fctx->MB, -1, true); + if (!isMemQueueEmpty(&fctx->Q)) + { + HeapTuple tuptset = NULL; + bool should_free = false; + bool isnull; + TSet newtset = newTSet____(fctx); + + /* Q.RemoveSumsumptionsAgainstComplete */ + SQRewindToFirstElement(fctx, funcctx, &fctx->complete); + while (!SQEof(&fctx->complete)) + { + if (isMemQueueEmpty(&fctx->Q)) + break; + tuptset = SQGetNextElement(fctx, funcctx, &fctx->complete, &should_free, false); + setTSet(fctx, newtset, tuptset, isnull); + removeLeftMemQueueNodesSubsumedInRightTSet(fctx, &fctx->Q, newtset); + if (should_free) + heap_freetuple(tuptset); + } + /* Q.RemoveSumsumptionsAgainstPreComplete */ + SQMarkPosition(fctx, funcctx, &fctx->precomplete); + while (!SQEof(&fctx->precomplete)) + { + if (isMemQueueEmpty(&fctx->Q)) + break; + tuptset = SQGetNextElement(fctx, funcctx, &fctx->precomplete, &should_free, false); + setTSet(fctx, newtset, tuptset, isnull); + removeLeftMemQueueNodesSubsumedInRightTSet(fctx, &fctx->Q, newtset); + if (should_free) + heap_freetuple(tuptset); + } + SQRestorePosition(fctx, funcctx, &fctx->precomplete); + pfree(newtset); + } + fctx->algorithm_state = MAIN_WHILE_Q_NOTEMPTY; + } + else + fctx->algorithm_state = ALGORITHM_END; + break; + case MAIN_WHILE_Q_NOTEMPTY: + clearMemQueue(fctx, &fctx->E, true); + if (!isMemQueueEmpty(&fctx->Q)) + { + /* + * New addition: adaptive upper bound on the number of + * tuples being extended at one time. Because of CPU + * constraits and transactional constraints, changing this + * value might be worth it. + */ + struct timeval startTime; + + gettimeofday(&startTime, NULL); + int freePagesInQ = fctx->MB - floorNumPagesInMemQueue(&fctx->Q); + + if (freePagesInQ < 0) + freePagesInQ = 0; + int numTupleSetsToGet + = fctx->m_NumResultTuplesInOnePage * (freePagesInQ + 1); + + if (fctx->dynamic_extend_cap->maxInputedExtendTuples < numTupleSetsToGet) + fctx->dynamic_extend_cap->maxInputedExtendTuples = numTupleSetsToGet; + if (getAdaptiveUpperBound(fctx) < numTupleSetsToGet) + numTupleSetsToGet = getAdaptiveUpperBound(fctx); + fctx->dynamic_extend_cap->actualInputedExtendTuples = numTupleSetsToGet; + memQueueNode *nodePtr; + + while (!isMemQueueEmpty(&fctx->Q) && (getMemQueueNumElements(&fctx->E) < numTupleSetsToGet)) + { + detachHeadNodeFromMemQueue(nodePtr, &fctx->Q); + mergeOutOfMemQueueIntoNode(fctx, &fctx->E, nodePtr, true, true); + addNodeToMemQueue(nodePtr, &fctx->E); + } + + Extend(fctx, &fctx->E); + + removeLeftMemQueueNodesSubsumedInRightMemQueueNodes(fctx, &fctx->Q, &fctx->E); + /* add E to PRECOMPLETE */ + { + memQueueNode *ptr = getMemQueueFirstElementPtr(&fctx->E); + TSet tset = NULL; + + while (ptr != NULL) + { + tset = getMemQueueElement(ptr); + tset->t = heap_formtuple(fctx->tupleSetDesc, tset->v, tset->n); + SQAddElement(fctx, funcctx, &fctx->precomplete, tset->t); + ptr = getMemQueueNextElementPtr(ptr); + } + } + { + struct timeval tim; + + gettimeofday(&tim, NULL); + double length = tim.tv_usec - startTime.tv_usec; + + if (length > 0) + updateAdaptiveScore(fctx, length); + else + updateAdaptiveScore(fctx, 10000); + } + if (PRINT) + fctx->algorithm_state = MAIN_PRINT; + } + else + { + fctx->algorithm_state = MAIN_WHILE_PRECOMPLETE_NOTEMPTY; + } + break; + case MAIN_PRINT: + if (fctx->printedTupleAddress != NULL) + { + pfree(fctx->printedTupleAddress); + fctx->printedTupleAddress = NULL; + } + if (fctx->startedPrintingQueue == false) + { + fctx->printedTSet = fctx->E.head; + fctx->startedPrintingQueue = true; + } + else + fctx->printedTSet = (memQueueNode *) fctx->printedTSet->next; + if (fctx->printedTSet != NULL) + { + fctx->printedTupleAddress + = heap_formtuple(fctx->resultTupleDesc, &fctx->printedTSet->tset->v[FIRSTATT], + &fctx->printedTSet->tset->n[FIRSTATT]); + SRF_RETURN_NEXT(funcctx, HeapTupleGetDatum(fctx->printedTupleAddress)); + } + else + { + fctx->startedPrintingQueue = false; + fctx->algorithm_state = MAIN_WHILE_Q_NOTEMPTY; + } + break; + case ALGORITHM_END: + break; + default: + elog(ERROR, "FUNCTION HAVE UNEXPECTED ERROR, Please contact developers."); + } + } + + /* Algorithm ends here. */ + clean_odmbfd_structures_on_exit(fcinfo, fctx, funcctx); + SRF_RETURN_DONE(funcctx); + } diff -crN pgsql/contrib/fulldisjunctions/queues.c pgsql-fd/contrib/fulldisjunctions/queues.c *** pgsql/contrib/fulldisjunctions/queues.c 1969-12-31 19:00:00.000000000 -0500 --- pgsql-fd/contrib/fulldisjunctions/queues.c 2006-07-30 13:30:12.000000000 -0400 *************** *** 0 **** --- 1,628 ---- + /* + * Copyright (c) 2006 Itzhak Fadida. All Rights Reserved. + * See the README file for a detailed BSD License. + * This file and all related files are under the BSD license. + * */ + + #include "queues.h" + #include "queuesfuncs.h" + #include "tset.h" + #include "tsetfuncs.h" + #include "algutils.h" + #include "utils/tuplestore.h" + #include "utils/memutils.h" + + void + _initializeMemQueue(memQueue * Q, int allocatedBytes) + { + Q->head = NULL; + Q->tail = NULL; + Q->numElements = 0; + Q->sizeInBytes = 0; + Q->allocatedBytes = allocatedBytes; + } + void + removeDuplicatesMemQueueWithSelf(alg_fctx * fctx, memQueue * Q) + { + if (Q->numElements < 2) + return; + memQueueNode *lPtr = Q->head; + memQueueNode *rPtr = Q->head; + memQueueNode *prevRPtr = Q->head; + RBITS lrels; + + while (lPtr != NULL) + { + if (Q->numElements < 2) + return; + lrels = lPtr->relsOfTuples; + rPtr = (memQueueNode *) lPtr->next; + prevRPtr = lPtr; + while (rPtr != NULL) + { + if (lrels == rPtr->relsOfTuples) + if (areTSetsEqual(fctx, lPtr->tset, rPtr->tset)) + { + detachNodeFromMemQueueNode(prevRPtr, rPtr, Q); + freeTSet(fctx, rPtr->tset); + pfree(rPtr); + rPtr = prevRPtr; + } + getMemQueueNextElementAfterRemovalPtr(prevRPtr, rPtr, Q); + } + lPtr = (memQueueNode *) lPtr->next; + } + } + void + removeSubsumptionsMemQueueWithSelf(alg_fctx * fctx, memQueue * Q) + { + if (Q->numElements < 2) + return; + memQueueNode *lPtr = Q->head; + memQueueNode *rPtr = Q->head; + memQueueNode *prevRPtr = Q->head; + + while (lPtr != NULL) + { + if (Q->numElements < 2) + return; + rPtr = Q->head; + prevRPtr = Q->head; + while (rPtr != NULL) + { + if (lPtr != rPtr) + { + if (isLeftSubsumedRightTset(fctx, lPtr->tset, rPtr->tset)) + { + Q->sizeInBytes -= tupleSize(rPtr->tset->t); + if ((memQueueNode *) lPtr->next == (memQueueNode *) rPtr) + lPtr->next = rPtr->next; + if (Q->head == rPtr) + Q->head = (memQueueNode *) rPtr->next; + if (rPtr == Q->tail) + Q->tail = prevRPtr; + prevRPtr->next = rPtr->next; + freeTSet(fctx, rPtr->tset); + pfree(rPtr); + Q->numElements--; + break; + } + } + prevRPtr = rPtr; + rPtr = (memQueueNode *) rPtr->next; + } + lPtr = (memQueueNode *) lPtr->next; + } + } + void + initializeMemQueue(memQueue * Q) + { + _initializeMemQueue(Q, MINIMUM_ALLOCATED_NUM_BYTES); + } + float + numPagesInMemQueue(memQueue * Q) + { + return ((float) Q->sizeInBytes / BLCKSZ); + } + int + ceilNumPagesInMemQueue(memQueue * Q) + { + int floor = ((int) (Q->sizeInBytes / BLCKSZ)); + + if (floor > (int) floor) + return ((int) floor + 1); + else + return (int) floor; + } + int + floorNumPagesInMemQueue(memQueue * Q) + { + return ((int) (Q->sizeInBytes / BLCKSZ)); + } + + /* + * #define NO_MERGE 0 + * #define LEFT_CONTAINED_RIGHT 1 + * #define RIGHT_CONTAINED_LEFT 2 + * #define MERGED_INTO_NEW_TSET 3 + * in all cases of contained or merged. update the status vars + * visited, toVisit, relsOfTuples to the + */ + int + mergeTwoTSets(alg_fctx * fctx, TSet ltset, Datum *ltsetVals, char *ltsetNulls, + bool *ltsetDeformed, RBITS lrelsOfTuples, RBITS ltoVisit, RBITS lvisited, TSet rtset, + RBITS rrelsOfTuples, RBITS rtoVisit, RBITS rvisited, + TSet * mtset, RBITS * mrelsOfTuples, RBITS * mtoVisit, RBITS * mvisited) + { + bytea *ltids = ltset->tids; + bytea *rtids = rtset->tids; + RBITS intersection, + tmp, + tmp2; + + *ltsetDeformed = true; + bool attemptJCCUnify = false; + TSet unifyJCCResult; + int j = 0; + RBITS ltsetBlocked = ((~lrelsOfTuples) & lvisited); + RBITS rtsetBlocked = ((~rrelsOfTuples) & rvisited); + + /* + * if there are tuples in one tuple set that were blocked(visited but no + * tuple) then surely they CANNOT merge. Note, its first because it must + * be done in order. i used a logic that depends on the ORDER ORDER ORDER + * ORDER! + */ + if ((lrelsOfTuples & rtsetBlocked) || (rrelsOfTuples & ltsetBlocked)); + + /* + * Lets check if there is an intersection of relations between the tuple + * sets. If there is an intersection, lets compare the rowids. + */ + else if ((intersection = (lrelsOfTuples & rrelsOfTuples))) + { + int leftPos = 0; + int leftRelOid = 0; + int rightRelOid = 0; + int numRightTuples = numOfTuplesInTSet(fctx, rtids); + + leftRelOid = getTableIdOfRelsOidInTSet(fctx, ltids, leftPos); + for (j = 0; j < numRightTuples; j++) + { + rightRelOid = getTableIdOfRelsOidInTSet(fctx, rtids, j); + if (varNthBitFromLeft(intersection, rightRelOid)) + { + while (leftRelOid != rightRelOid) + { + leftPos++; + leftRelOid = getTableIdOfRelsOidInTSet(fctx, ltids, leftPos); + } + if (memcmp(VARDATA(ltids) + leftPos * (1 + sizeof(ItemPointerData)) + ,VARDATA(rtids) + j * (1 + sizeof(ItemPointerData)), + 1 + (sizeof(ItemPointerData)))) + { + break; + } + } + tmp = (~(0x0)); + if (!(intersection & (tmp >> (rightRelOid + 1)))) + { + j = numRightTuples; + break; + } + } + if (j >= numRightTuples) + { + /* + * if the left side is contained in right side then don't do + * anything but consider it merged. So lets check if one contains + * the other: + */ + if ((rrelsOfTuples | lrelsOfTuples) == rrelsOfTuples) + { + *mrelsOfTuples = rrelsOfTuples; + *mvisited = (~(rrelsOfTuples)) & (rvisited | lvisited); + *mtoVisit = (~(rrelsOfTuples)) & (rtoVisit | ltoVisit) + & (~(rvisited | lvisited)); + return RIGHT_CONTAINED_LEFT; + } + else if ((rrelsOfTuples | lrelsOfTuples) == lrelsOfTuples) + { + /* replace ltset with the rtset. */ + *mrelsOfTuples = lrelsOfTuples; + *mvisited = (~(lrelsOfTuples)) & (rvisited | lvisited); + *mtoVisit = (~(lrelsOfTuples)) & (rtoVisit | ltoVisit) + & (~(rvisited | lvisited)); + return LEFT_CONTAINED_RIGHT; + } + else + { + /* + * Here we want to check if relations of tuples of one of the + * tuple sets that are not in the intesection, are connected + * to tuples of the other tuple set that are not in the + * intersection. Because if so, we cannot use dumb unify and + * we have to check also for JCC. + */ + j = 0; + tmp2 = 0; + /* tuples of rtset not in intersection */ + tmp = (~intersection) & rrelsOfTuples; + + /* + * tmp2 contains relations that relations of tuples not in + * intersection, are connected to. + */ + while (tmp) + { + if (varNthBitFromLeft(tmp, 0)) + tmp2 |= (fctx->bits_scheme_graph[j]); + j++; + tmp <<= 1; + } + + /* + * we check if the tuples of rtset not in the intersections + * are connected to tuples of ltset not in the intersection. f + * not we continue, otherwise we will later attempt Unifying + * with JCC(ELSE CLAUSE). + */ + if (!((~intersection) & lrelsOfTuples & tmp2)) + { + j = 0; + tmp2 = 0; + /* tuples of ltset not in intersection. */ + tmp = (~intersection) & lrelsOfTuples; + while (tmp) + { + if (varNthBitFromLeft(tmp, 0)) + tmp2 |= (fctx->bits_scheme_graph[j]); + j++; + tmp <<= 1; + } + + /* + * we check if the tuples of ltset not in the + * intersections are connected to tuples of rtset not in + * the intersection. if not we will unify the tuple sets + * without checks. otherwise we will proceed to unifying + * with checks (ELSE CLAUSE). + */ + if (!((~intersection) & rrelsOfTuples & tmp2)) + { + unifyJCCResult = simpleUnify(fctx, ltset, ltsetVals, ltsetNulls, rtset); + *mtset = unifyJCCResult; + *mrelsOfTuples = lrelsOfTuples | rrelsOfTuples; + *mvisited = (~(rrelsOfTuples)) & (rvisited | lvisited); + *mtoVisit = (~(rrelsOfTuples)) & (rtoVisit | ltoVisit) + & (~(rvisited | lvisited)); + return MERGED_INTO_NEW_TSET; + } + else + attemptJCCUnify = true; + } + else + attemptJCCUnify = true; + } + } + } + + /* + * Otherwise, there was no intersection of relations: + * ------------------------------ Here we CANNOT merge if all the + * relations, either tuple set wants to visit, were blocked in the other + * tuple set. Note there can be lack of information so blocked only + * reflect the knowledge of visiting if we did try to visit. + */ + else if ((!(ltoVisit & (~rtsetBlocked))) && (!(rtoVisit & (~ltsetBlocked)))); + + /* + * We will only try to unify if both tuple sets needs to visit a tuple in + * the other tuple set. + */ + else if ((ltoVisit & rrelsOfTuples) || (rtoVisit & lrelsOfTuples)) + attemptJCCUnify = true; + if (attemptJCCUnify) + { + if ((unifyJCCResult = + unifyAndJCC(fctx, ltset, ltsetVals, ltsetNulls, rtset, ((~intersection) + & ((lrelsOfTuples & rtoVisit) | (rrelsOfTuples & ltoVisit))), + lrelsOfTuples, rrelsOfTuples)) != NULL) + { + *mtset = unifyJCCResult; + *mrelsOfTuples = lrelsOfTuples | rrelsOfTuples; + *mvisited = (~(rrelsOfTuples)) & (rvisited | lvisited); + *mtoVisit = (~(rrelsOfTuples)) & (rtoVisit | ltoVisit) + & (~(rvisited | lvisited)); + return MERGED_INTO_NEW_TSET; + } + } + return NO_MERGE; + } + bool + mergeOutOfMemQueueIntoNode(alg_fctx * fctx, memQueue * Q, memQueueNode * node, + bool exitAtFirstMerge, bool assumeQueueMerged) + { + RBITS relsOfTuples = node->relsOfTuples; + RBITS toVisit = node->toVisit; + RBITS visited = node->visited; + Datum *tsetVals = node->tset->v; + char *tsetNulls = node->tset->n; + bool deformedTSet = false; + int result; + RBITS mrelsOfTuples, + mtoVisit, + mvisited; + TSet mtset = NULL; + TSet tset = node->tset; + memQueueNode *ptr = Q->head; + memQueueNode *prevPtr = ptr; + bool wasMerging = false; + + while (ptr != NULL) + { + if ((result = mergeTwoTSets(fctx, tset, tsetVals, tsetNulls, + &deformedTSet, relsOfTuples, toVisit, visited, ptr->tset, + ptr->relsOfTuples, ptr->toVisit, ptr->visited, + &mtset, &mrelsOfTuples, &mtoVisit, &mvisited))) + { + switch (result) + { + case LEFT_CONTAINED_RIGHT: + removeMemQueueNode(Q, prevPtr, ptr); + wasMerging = true; + relsOfTuples = mrelsOfTuples; + toVisit = mtoVisit; + visited = mvisited; + break; + case RIGHT_CONTAINED_LEFT: + detachNodeFromMemQueueNode(prevPtr, ptr, (Q)); + freeTSet(fctx, tset); + node->tset = ptr->tset; + tset = ptr->tset; + deformedTSet = false; + wasMerging = true; + relsOfTuples = ptr->relsOfTuples; + toVisit = ptr->toVisit; + visited = ptr->visited; + pfree(ptr); + ptr = prevPtr; + break; + case MERGED_INTO_NEW_TSET: + removeMemQueueNode(Q, prevPtr, ptr); + node->tset = mtset; + tset = mtset; + deformedTSet = false; + wasMerging = true; + relsOfTuples = mrelsOfTuples; + toVisit = mtoVisit; + visited = mvisited; + } + } + if ((exitAtFirstMerge && wasMerging) || (assumeQueueMerged && (result == RIGHT_CONTAINED_LEFT))) + break; + getMemQueueNextElementAfterRemovalPtr(prevPtr, ptr, Q); + } + node->relsOfTuples = relsOfTuples; + node->toVisit = toVisit; + node->visited = visited; + return wasMerging; + } + void + addTupleSetToMemQueue(alg_fctx * fctx, memQueue * Q, TSet tset) + { + RBITS relsOfTuples = 0; + RBITS toVisit = 0; + bytea *b = tset->tids; + int j, + relID; + int numTuples = numOfTuplesInTSet(fctx, b); + + for (j = 0; j < numTuples; j++) + { + relID = getTableIdOfRelsOidInTSet(fctx, b, j); + varSetNthBitFromLeft(relsOfTuples, relID); + } + for (j = 0; j < fctx->numRels; j++) + if ((varNthBitFromLeft(relsOfTuples, j))) + toVisit |= ((~relsOfTuples) & (fctx->bits_scheme_graph[j])); + memQueueNode *newNode = palloc(sizeof(memQueueNode)); + + newNode->tset = tset; + newNode->relsOfTuples = relsOfTuples; + newNode->toVisit = toVisit; + newNode->visited = 0; + newNode->next = NULL; + if (Q->head == NULL) + Q->head = newNode; + if (Q->tail != NULL) + Q->tail->next = (struct memQueueNode *) newNode; + Q->tail = newNode; + Q->numElements++; + Q->sizeInBytes += tset->size; + } + bool + removeLeftMemQueueNodesSubsumedInRightTSet(alg_fctx * fctx, memQueue * Q, TSet tset) + { + memQueueNode *ptr = Q->head; + memQueueNode *prev = ptr; + bool wasRemoval = false; + + while (ptr != NULL) + { + if (isLeftSubsumedRightTset(fctx, ptr->tset, tset)) + { + wasRemoval = true; + removeMemQueueNode(Q, prev, ptr); + } + getMemQueueNextElementAfterRemovalPtr(prev, ptr, Q); + } + return wasRemoval; + } + void + removeLeftMemQueueNodesSubsumedInRightMemQueueNodes(alg_fctx * fctx, memQueue * QLeft, + memQueue * QRight) + { + if (QLeft == QRight) + elog(ERROR, "Not protected against self, use mergeMemQueueWithSelf instead"); + memQueueNode *ptr = QRight->head; + + while (ptr != NULL) + { + removeLeftMemQueueNodesSubsumedInRightTSet(fctx, QLeft, ptr->tset); + ptr = (memQueueNode *) ptr->next; + } + } + void + clearMemQueue(alg_fctx * fctx, memQueue * Q, bool free_tsets) + { + memQueueNode *ptr = Q->head; + memQueueNode *prevPtr = ptr; + + while (ptr != NULL) + { + if (free_tsets) + freeTSet(fctx, ptr->tset); + prevPtr = ptr; + ptr = (memQueueNode *) ptr->next; + pfree(prevPtr); + } + Q->tail = NULL; + Q->head = NULL; + Q->numElements = 0; + Q->sizeInBytes = 0; + } + void + SQInitialize(alg_fctx * fctx, FuncCallContext *funcctx, storageQueue * Q) + { + MemoryContext oldcontext = MemoryContextSwitchTo(fctx->per_query_ctx); + + Q->tuplestorage = tuplestore_begin_heap(false, false, (int) (BLCKSZ / 1024)); + #ifdef PG_MODULE_MAGIC + Q->slot = MakeSingleTupleTableSlot(fctx->tupleSetDesc); + #endif /* */ + MemoryContextSwitchTo(oldcontext); + Q->numElements = 0; + Q->sizeInBytes = 0; + Q->lastReadPosition = 0; + Q->markedLastReadPosition = -1; + Q->markedNumElements = -1; + Q->markedSizeInBytes = -1; + Q->markedMemOverflowTuple = NULL; + Q->memOverflowTuple = NULL; + } + void + SQFinish(alg_fctx * fctx, FuncCallContext *funcctx, storageQueue * Q) + { + MemoryContext oldcontext = MemoryContextSwitchTo(fctx->per_query_ctx); + + if (Q->tuplestorage != NULL) + tuplestore_end(Q->tuplestorage); + MemoryContextSwitchTo(oldcontext); + Q->tuplestorage = NULL; + Q->numElements = 0; + Q->sizeInBytes = 0; + Q->markedLastReadPosition = -1; + Q->markedNumElements = -1; + Q->markedSizeInBytes = -1; + Q->markedMemOverflowTuple = NULL; + Q->lastReadPosition = 0; + if (Q->memOverflowTuple != NULL) + heap_freetuple(Q->memOverflowTuple); + if (Q->markedMemOverflowTuple != NULL) + heap_freetuple(Q->markedMemOverflowTuple); + } + + /* + * the caller must return the tuple he took out. + */ + void + SQSetMemOverflowTuple(storageQueue * Q, HeapTuple tuple) + { + Q->memOverflowTuple = tuple; + Q->lastReadPosition--; + Q->sizeInBytes += tupleSize(tuple); + } + void + SQAddElement(alg_fctx * fctx, FuncCallContext *funcctx, storageQueue * Q, HeapTuple tuple) + { + MemoryContext oldcontext = MemoryContextSwitchTo(fctx->per_query_ctx); + + tuplestore_puttuple(Q->tuplestorage, tuple); + MemoryContextSwitchTo(oldcontext); + Q->numElements++; + Q->sizeInBytes += tupleSize(tuple); + } + HeapTuple + SQGetNextElement(alg_fctx * fctx, FuncCallContext *funcctx, storageQueue * Q, bool *should_free, + bool copytuple) + { + Q->lastReadPosition++; + HeapTuple tmpTuple = NULL; + + if (Q->memOverflowTuple != NULL) + { + *should_free = true; + tmpTuple = Q->memOverflowTuple; + Q->memOverflowTuple = NULL; + Q->sizeInBytes -= tupleSize(tmpTuple); + return tmpTuple; + } + MemoryContext oldcontext = MemoryContextSwitchTo(fctx->per_query_ctx); + HeapTuple tuple = NULL; + + #ifdef PG_MODULE_MAGIC + ExecClearTuple(Q->slot); + if (tuplestore_gettupleslot(Q->tuplestorage, true, Q->slot)) + { + tuple = ExecFetchSlotTuple(Q->slot); + } + else + elog(ERROR, "In SQGetNextElement unexpected no tuple returned. we do not check here for end of queue"); + #else /* */ + tuple = tuplestore_gettuple(Q->tuplestorage, true, should_free); + #endif /* */ + MemoryContextSwitchTo(oldcontext); + if (copytuple) + { + tmpTuple = (HeapTuple) heap_copytuple(tuple); + #ifndef PG_MODULE_MAGIC + if (*should_free) + heap_freetuple(tuple); + #endif /* */ + *should_free = true; + Q->sizeInBytes -= tupleSize(tmpTuple); + return tmpTuple; + } + else + { + Q->sizeInBytes -= tupleSize(tuple); + return tuple; + } + } + void + SQRewindToFirstElement(alg_fctx * fctx, FuncCallContext *funcctx, storageQueue * Q) + { + MemoryContext oldcontext = MemoryContextSwitchTo(fctx->per_query_ctx); + + tuplestore_rescan(Q->tuplestorage); + MemoryContextSwitchTo(oldcontext); + Q->lastReadPosition = 0; + } + void + SQMarkPosition(alg_fctx * fctx, FuncCallContext *funcctx, storageQueue * Q) + { + MemoryContext oldcontext = MemoryContextSwitchTo(fctx->per_query_ctx); + + tuplestore_markpos(Q->tuplestorage); + MemoryContextSwitchTo(oldcontext); + Q->markedLastReadPosition = Q->lastReadPosition; + Q->markedNumElements = Q->numElements; + Q->markedSizeInBytes = Q->sizeInBytes; + if (Q->memOverflowTuple != NULL) + Q->markedMemOverflowTuple = heap_copytuple(Q->memOverflowTuple); + else + Q->markedMemOverflowTuple = NULL; + } + void + SQRestorePosition(alg_fctx * fctx, FuncCallContext *funcctx, storageQueue * Q) + { + MemoryContext oldcontext = MemoryContextSwitchTo(fctx->per_query_ctx); + + tuplestore_restorepos(Q->tuplestorage); + MemoryContextSwitchTo(oldcontext); + Q->lastReadPosition = Q->markedLastReadPosition; + Q->numElements = Q->markedNumElements; + Q->sizeInBytes = Q->markedSizeInBytes; + if (Q->memOverflowTuple) + { + heap_freetuple(Q->memOverflowTuple); + Q->memOverflowTuple = NULL; + } + if (Q->markedMemOverflowTuple != NULL) + Q->memOverflowTuple = Q->markedMemOverflowTuple; + Q->markedLastReadPosition = -1; + Q->markedNumElements = -1; + Q->markedSizeInBytes = -1; + Q->markedMemOverflowTuple = NULL; + } diff -crN pgsql/contrib/fulldisjunctions/queuesfuncs.h pgsql-fd/contrib/fulldisjunctions/queuesfuncs.h *** pgsql/contrib/fulldisjunctions/queuesfuncs.h 1969-12-31 19:00:00.000000000 -0500 --- pgsql-fd/contrib/fulldisjunctions/queuesfuncs.h 2006-07-29 20:54:13.000000000 -0400 *************** *** 0 **** --- 1,177 ---- + /* + * Copyright (c) 2006 Itzhak Fadida. All Rights Reserved. + * See the README file for a detailed BSD License. + * This file and all related files are under the BSD license. + * */ + + #ifndef QUEUESFUNCS_H + #define QUEUESFUNCS_H + + #ifdef DEBUG + #else + #define NDEBUG + #endif + + #include + + #define MINIMUM_ALLOCATED_NUM_PAGES 2 + #define MINIMUM_ALLOCATED_NUM_BYTES (MINIMUM_ALLOCATED_NUM_PAGES*BLCKSZ) + #define bitsInVariable 32 + #define firstBitFromLeftInHex 0x80000000 + #define firstBitFromLeftInHex 0x80000000 + #define NO_MERGE 0 + #define LEFT_CONTAINED_RIGHT 1 + #define RIGHT_CONTAINED_LEFT 2 + #define MERGED_INTO_NEW_TSET 3 + #include "utils/palloc.h" + #include "queues.h" + #include "algstructs.h" + /* n is starting from zero! */ + #define nthBitFromLeft(n)\ + (firstBitFromLeftInHex >> n) + #define varNthBitFromLeft(var,n)\ + ((var) & (nthBitFromLeft(n))) + #define varSetNthBitFromLeft(var,n)\ + (var = (var) | (nthBitFromLeft(n))) + #define varUnSetNthBitFromLeft(var,n)\ + (var = (var) & (~(nthBitFromLeft(n)))) + #define replaceNodeTSet(fctx,node,retset)\ + do\ + {\ + freeTSet(fctx, (node)->tset);\ + (node)->tset = retset;\ + } while (0) + + #define freeMemQueueNode(node)\ + do\ + {\ + freeTSet(fctx, node->tset); \ + pfree(node);\ + node = NULL;\ + } while (0) + + /* no queue size modifications */ + #define addNodeToMemQueue(node,Q) \ + do\ + {\ + if ((Q)->head == NULL)\ + (Q)->head = (node); \ + else\ + (Q)->tail->next = (struct memQueueNode *) (node);\ + (node)->next = NULL;\ + (Q)->numElements++;\ + (Q)->sizeInBytes += (node)->tset->size;\ + (Q)->tail = (node);\ + } while (0) + + /*node is modified to detached node. + no queue size modifications*/ + #define detachHeadNodeFromMemQueue(node,Q)\ + do\ + {\ + if ((Q)->head != NULL)\ + {\ + node = (Q)->head;\ + (Q)->head = (memQueueNode *) node->next;\ + (Q)->numElements--; \ + (Q)->sizeInBytes -= (node)->tset->size; \ + if ((Q)->head == NULL)\ + (Q)->tail = NULL;\ + } \ + else\ + node = NULL;\ + } while (0) + + /* no queue size modifications */ + #define detachNodeFromMemQueueNode(prevNode,node,Q)\ + do\ + {\ + if ((node) == (prevNode))\ + {\ + if ((prevNode) == (Q)->head)\ + (Q)->head = (memQueueNode *) (prevNode)->next;\ + if ((prevNode) == (Q)->tail)\ + (Q)->tail = NULL;\ + (prevNode) = NULL;\ + }\ + else\ + {\ + (prevNode)->next = (node)->next;\ + if ((node) == (Q)->tail)\ + (Q)->tail = (prevNode);\ + } \ + (Q)->numElements--;\ + (Q)->sizeInBytes -= (node)->tset->size; \ + } while (0) + + #define removeMemQueueNode(Q, prevPtr, ptr)\ + do\ + {\ + detachNodeFromMemQueueNode((prevPtr), (ptr), (Q));\ + freeMemQueueNode(ptr);\ + (ptr) = (prevPtr);\ + } while (0) + + #define getMemQueueNextElementAfterRemovalPtr(prevNodePtr,nodePtr,Q)\ + do\ + {\ + if (!prevNodePtr)\ + {\ + nodePtr = getMemQueueFirstElementPtr((Q));\ + prevNodePtr = nodePtr;\ + }\ + else if (nodePtr)\ + {\ + prevNodePtr = nodePtr;\ + nodePtr = getMemQueueNextElementPtr(nodePtr);\ + }\ + } while (0) + + #define getMemQueueElement(ptr)\ + (ptr->tset) + #define getMemQueueNextElementPtr(ptr)\ + ((memQueueNode *) (ptr->next)) + #define getMemQueueFirstElementPtr(Q)\ + ((Q)->head) + #define getMemQueueLastElementPtr(Q)\ + ((Q)->tail) + #define getMemQueueNumElements(Q)\ + ((Q)->numElements) + #define getMemQueueSize(Q)\ + ((Q)->sizeInBytes) + #define isMemQueueEmpty(Q)\ + (((Q)->numElements) <= 0) + #define SQGetNumElements(Q)\ + ((Q)->numElements) + #define numPagesInSQ(Q)\ + ((Q)->sizeInBytes / BLCKSZ) + #define SQEof(Q)\ + ((Q)->numElements <= (Q)->lastReadPosition) + #define SQNotEmpty(Q)\ + ((Q)->numElements > (Q)->lastReadPosition) + extern void _initializeMemQueue(memQueue * Q, int allocatedBytes); + extern void removeDuplicatesMemQueueWithSelf(alg_fctx * fctx, memQueue * Q); + extern void removeSubsumptionsMemQueueWithSelf(alg_fctx * fctx, memQueue * Q); + extern void initializeMemQueue(memQueue * Q); + extern float numPagesInMemQueue(memQueue * Q); + extern int floorNumPagesInMemQueue(memQueue * Q); + extern int ceilNumPagesInMemQueue(memQueue * Q); + extern bool mergeOutOfMemQueueIntoNode(alg_fctx * fctx, memQueue * Q, memQueueNode * node, + bool exitAtFirstMerge, bool assumeQueueMerged); + extern void addTupleSetToMemQueue(alg_fctx * fctx, memQueue * Q, TSet tset); + extern bool removeLeftMemQueueNodesSubsumedInRightTSet(alg_fctx * fctx + ,memQueue * Q, TSet tset); + extern void removeLeftMemQueueNodesSubsumedInRightMemQueueNodes(alg_fctx * fctx + ,memQueue * QLeft, memQueue * QRight); + extern void clearMemQueue(alg_fctx * fctx, memQueue * Q, bool free_tsets); + extern void SQInitialize(alg_fctx * fctx, FuncCallContext *funcctx, storageQueue * Q); + extern void SQFinish(alg_fctx * fctx, FuncCallContext *funcctx, storageQueue * Q); + extern void SQSetMemOverflowTuple(storageQueue * Q, HeapTuple tuple); + extern void SQAddElement(alg_fctx * fctx, FuncCallContext *funcctx, storageQueue * Q, HeapTuple tuple); + extern HeapTuple SQGetNextElement(alg_fctx * fctx, FuncCallContext *funcctx, storageQueue * Q, bool *should_free, + bool copytuple); + extern void SQRewindToFirstElement(alg_fctx * fctx, FuncCallContext *funcctx, storageQueue * Q); + extern void SQMarkPosition(alg_fctx * fctx, FuncCallContext *funcctx, storageQueue * Q); + extern void SQRestorePosition(alg_fctx * fctx, FuncCallContext *funcctx, storageQueue * Q); + + #endif /* QUEUESFUNCS_H */ diff -crN pgsql/contrib/fulldisjunctions/queues.h pgsql-fd/contrib/fulldisjunctions/queues.h *** pgsql/contrib/fulldisjunctions/queues.h 1969-12-31 19:00:00.000000000 -0500 --- pgsql-fd/contrib/fulldisjunctions/queues.h 2006-07-30 15:27:12.000000000 -0400 *************** *** 0 **** --- 1,66 ---- + /* + * Copyright (c) 2006 Itzhak Fadida. All Rights Reserved. + * See the README file for a detailed BSD License. + * This file and all related files are under the BSD license. + * */ + + #ifndef QUEUES_H + #define QUEUES_H + + #ifdef DEBUG + #else + #define NDEBUG + #endif + + #include + + #include "postgres.h" + #include "tset.h" + + #ifndef INFINITY + #define INFINITY INT_MAX + #endif + + typedef unsigned int RBITS; + typedef struct + { + TSet tset; + unsigned long visited; + unsigned long relsOfTuples; + unsigned long toVisit; + struct memQueueNode *next; + } memQueueNode; + typedef struct + { + memQueueNode *head; + memQueueNode *tail; + int numElements; + int sizeInBytes; + int allocatedBytes; + } memQueue; + typedef struct + { + Tuplestorestate *tuplestorage; + int numElements; + int lastReadPosition; + int sizeInBytes; + int markedLastReadPosition; + int markedNumElements; + int markedSizeInBytes; + HeapTuple markedMemOverflowTuple; + + /* + * we pulled it out of storage but couldn't hold it memory. thus we leave + * it here. potentially i can read half tuples and thus never overflow, + * however, since i don't want to implement the tuplestore again, i + * simulate this by leaving this tuple in the storage structure. the next + * ead will be this tuple. in case of an overflow we do not increment the + * lastReadPosition. + */ + HeapTuple memOverflowTuple; + #ifdef PG_MODULE_MAGIC + TupleTableSlot *slot; + #endif /* */ + } storageQueue; + + #endif /* QUEUES_H */ diff -crN pgsql/contrib/fulldisjunctions/README.fulldisjunctions pgsql-fd/contrib/fulldisjunctions/README.fulldisjunctions *** pgsql/contrib/fulldisjunctions/README.fulldisjunctions 1969-12-31 19:00:00.000000000 -0500 --- pgsql-fd/contrib/fulldisjunctions/README.fulldisjunctions 2006-07-30 16:25:31.000000000 -0400 *************** *** 0 **** --- 1,220 ---- + *************************************************************************** + Copyright (c) 2006 Itzhak Fadida + All rights reserved. + + Redistribution and use in source and binary forms, with or without + modification, are permitted provided that the following conditions are + met: + + * Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + * Redistributions in binary form must reproduce the above + copyright notice, this list of conditions and the following disclaimer + in the documentation and/or other materials provided with the + distribution. + * Neither the name Itzhak Fadida nor the names of its + contributors may be used to endorse or promote products derived from + this software without specific prior written permission. + + THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS + "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT + LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR + A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT + OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, + SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT + LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE + OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + *************************************************************************** + + Full Disjunctions + + License + + BSD + + Short Description + The full-disjunction operation is a variation of the join operator that + maximally combines tuples from connected relations, while preserving all + information in the relations. Full disjunctions can be very useful for + integrating heterogeneous data sources (e.g., web sources) since such data + sources are often incomplete. Under certain conditions full disjunctions + can be expressed using a series of natural outer joins. However, the + general case full disjunctions cannot be expressed using standard + relational operators, and thus, special algorithms are needed. + + Additional Details + Full Disjunctions (FD) is an SQL operator that has a top-down approach to + extracting the maximum information without duplication of information or + subsumptions (information of one tuple is contained in another tuple). + The FD operator generates information that cannot be expressed using + standard SQL statements (including natural full outer joins). + + Example of an input and output of a full disjunctions: + INPUT: + --A---|---B---|---C-- + X---Y-|-Y---Z-|-X---Z + a-|-b-|-b-|-c-|-a-|-d + + A,B and C are relations. X,Y and Z are attributes. a,b,c and d are values. + Note that A,B and C are connected in a cycle. That is: + A is connected to B on attribute Y, + B is connected to C on attribute Z, + C is connected to A on attribute X. + + The output of the full disjunctions FD(A,B,C): + FD + X---Y---Z + a-|-b-|-c + a-|-b-|-d + + This output cannot be generated using standard SQL statements. + The closest operator is a natural full join and even it cannot + generate this output. Following is all the possible ways to use a + natural outer join (noj): + + (A noj B) noj C = C noj (A noj B): + X----Y-----Z + a-|-b----|-c + a-|-Null-|-d + + (A noj C) noj B = B noj (A noj C): + X------Y---Z + a----|-b-|-d + Null-|-b-|-c + + (B noj C) noj A = A noj (B noj C): + X------Y------Z + Null-|-b----|-c + a----|-Null-|-d + a----|-b----|-Null + + As can be clearly seen, we get incomplete information. + + + Installation + + Execute the following to use Full Disjunctions: + + make + make install + make installcheck + + After the Full Disjunction libraries are installed, you then need + to execute the following SQL script as a superuser: + + psql databasename -f fulldisjunctions.sql + + Usage + + An example of a run: + + The function getfdr will return a string containing the RECORD + which is the schema that will be returned. + "SELECT getfdr('relation1,relation2,relation3')" + + Let STR be that string. + + Replace with the actual string. + "SELECT * FROM fulldisjunction('relation1,relation2,relation3') AS RECORD " + + You can run the following functions: + getfdr() - returns the schema that will be returned by the + full disjunctions of the . + NOTE that can be any number of connected + relations (currently limited to 32) + + getfdr([,mappings]) - returns the schema that will be returned by the + full disjunctions of the . However, it is the common case + that relations will not contain the same names of attribute that you know + needs to be joined. For example, id and identification are the same attributes + in different relations but the function cannot know that. To solve that, we + provide a was, akeen to AS clause, to provide aliases for relations attributes. + Mappings are used as follows: + "result_attribute_name=schema.relation.attribute_name, ..." + Each pair is one alias. If you do not know what a schema is, use public, + e.g. "id=public.people.identification,name=public.people.first_name". + + fulldisjunction() - returns a set of tuples that are the full disjunctions of the relations. + + fulldisjunction([,mappings[,noduplicates[,noindices[,policy[,numPages]]]]]) - same as fd above but + with more control over the parameters used. + text mappings - The same as described for getfdr. However, note that if you want + to use mappings and you want to use getfdr, you have to also use + the same mappings string in getfdr. + boolean noduplicates - true will not remove duplicates from the source when + selecting them. false will remove. If you have a table with duplicates + (whole tuples that are repeated), not removing these tuples will mean + there will also be duplicates in the result of the full disjunction. + This is not an error since it complies with the definition of the + full disjunction when working with tuple sets. If you will allow to + remove them (not physically, just selecting with no duplicates) than + there will not be duplicates in the results of the full disjunctions. + boolean noindices - true will not use indices in the source relations. false will try + to use indices in the source relations where possible. + text policy - three policies can be used when extending tuple sets which depends + on the schemes of the relations and their content, might improve + the overall runtime. policies that can be used: majority,mincost,random, + naive. + int numPages - Number of pages allocated for the algorithm. Theoretically, the more + the better, however there is a CPU dependense thus, there is a balance + depending on your hardware. Recommended to start with 5-10 pages before + experimenting with higher numbers. + + Note that if you only want, for example, noindices, you have to include all those that came + before in the order. In this case, noduplicates. + + Example of using the detailed fd function: + SELECT * FROM fulldisjunction('relation1,relation2,relation3','attnew=public.relation1.oldatt',true,false,'majority',100) + + NOTE: If you do not want to supply a value in a text field you must + NOT! use NULL, use the empty string ''. + + Test Run: + + Using the helper python script createTable.py, you can create tables to test the FD operator. + createTable.py + + + FD is only useful when there is a cycle in the scheme graph of the relations we are trying to compute + FD on. Therefore, we will create a cycle of (a0,a1) (a1,a2) (a2,a0). + Note that this cannot be computed in SQL other than using FD. + + python createTable.py 1000 5000 test t1 a0 a1 + python createTable.py 1000 5000 test t2 a1 a2 + python createTable.py 1000 5000 test t3 a2 a0 + + You can output the record by simply calling: + psql test -c "SELECT getfdr('t1,t2,t3')" + + Which will output: + (a0 int4,a1 int4,a2 int4) + + Now lets run the fd: + psql test -c "SELECT * FROM fulldisjunction('t1,t2,t3') AS RECORD (a0 int4,a1 int4,a2 int4)" + + Expect a long run of about 15 seconds depending on your hardware and available cpu time. + As you can already see, it is recommended to use full disjunctions sparingly or on very small + tables. Usually small tables are derived from XML files or other web sources. + However, sometimes you have to do it on your own internal data, in which case design your applciation + to rarely compute full disjunctions or to materialize it, i.e., store the results in a table and refresh + the table periodically as required. You can use FD on large tables but expect it to run from hours to + days (it was extensively tested for long runs) so it is ill advised to actually use FD in interactive + applications such as web over very large tables. + + Limitation: + + This implementation of the function is limited to 32 relations at the most because of efficiency reasons. + The number of relations supported can be easily extended by redefining RBITS and firstBitFromLeftInHex to + support 64 bits but have not been tested. + + + Developers Corner: + + * For optimization purposes, merging was disabled in On Demand procedure as + opposed to textbook algorithm and instead i also remove duplicates after + the extending process. The reason is because much of the merging operations + is done in Extend anyway. This change does not break the issue of doing more + work than tuple-based algorithm because we are still merging in Extend. diff -crN pgsql/contrib/fulldisjunctions/sql/fulldisjunctions.sql pgsql-fd/contrib/fulldisjunctions/sql/fulldisjunctions.sql *** pgsql/contrib/fulldisjunctions/sql/fulldisjunctions.sql 1969-12-31 19:00:00.000000000 -0500 --- pgsql-fd/contrib/fulldisjunctions/sql/fulldisjunctions.sql 2006-07-30 16:20:37.000000000 -0400 *************** *** 0 **** --- 1,3053 ---- + -- + -- Test Full Disjunctions + -- + + SET client_min_messages = warning; + \set ECHO none + \i fulldisjunctions.sql + SET client_encoding = 'UTF8'; + SET standard_conforming_strings = off; + SET check_function_bodies = false; + SET client_min_messages = warning; + SET escape_string_warning = off; + SET search_path = public; + SET default_tablespace = ''; + SET default_with_oids = false; + + CREATE TABLE t1 ( + a0 integer, + a1 integer + ); + + CREATE TABLE t2 ( + a1 integer, + a2 integer + ); + + CREATE TABLE t3 ( + a2 integer, + a0 integer + ); + + COPY t1 (a0, a1) FROM stdin; + 2951 4148 + 3323 3959 + 355 3937 + 4819 2204 + 1959 4943 + 1446 3135 + 1703 4294 + 3763 2577 + 3707 716 + 574 3389 + 3237 3988 + 2742 2578 + 4712 413 + 4300 915 + 2473 164 + 605 2403 + 2335 4035 + 2420 4590 + 416 3895 + 995 485 + 53 1550 + 1107 3794 + 1236 4172 + 472 4178 + 1624 2684 + 4306 431 + 67 4855 + 2515 1841 + 3632 125 + 3282 2161 + 3936 2562 + 3748 237 + 26 1055 + 2339 3634 + 4486 98 + 512 2853 + 3385 1775 + 782 1166 + 488 4710 + 1434 1126 + 4680 1850 + 1315 2584 + 2378 4094 + 4847 4632 + 1609 2516 + 3515 2168 + 1489 4832 + 3368 2656 + 4416 2797 + 4302 4365 + 807 2647 + 2240 2375 + 2165 17 + 1692 2695 + 3480 1067 + 1678 247 + 3513 2684 + 1056 22 + 264 728 + 1791 872 + 273 4489 + 2577 501 + 1151 1811 + 4701 980 + 1532 1129 + 4836 2512 + 2526 2763 + 2674 4285 + 361 171 + 4618 4187 + 3930 1354 + 3049 312 + 678 4399 + 148 814 + 4795 1643 + 1359 1755 + 688 3371 + 1590 1858 + 771 3564 + 962 3666 + 2860 2893 + 1124 3663 + 4175 4789 + 1877 3650 + 1394 1956 + 2482 3706 + 4137 3645 + 4332 2756 + 3687 1823 + 2302 3717 + 954 2032 + 389 279 + 2335 3711 + 847 1425 + 4184 2057 + 4286 1711 + 4411 21 + 3537 3901 + 4142 423 + 1274 3209 + 1084 4706 + 2633 30 + 4077 3091 + 4147 3578 + 4713 4524 + 1977 1917 + 4204 2917 + 254 3450 + 1889 1430 + 774 1064 + 563 3110 + 2642 1551 + 3202 2731 + 3728 3299 + 1368 4976 + 3773 1610 + 1638 3317 + 1580 4742 + 1816 1721 + 4985 1787 + 4183 4250 + 4364 330 + 518 2316 + 3174 1743 + 19 1227 + 4601 4721 + 131 3631 + 3456 2511 + 4647 332 + 2863 1667 + 4685 2499 + 2601 3255 + 4623 4124 + 3629 1006 + 526 1882 + 3603 4620 + 1419 3931 + 4815 3171 + 783 2905 + 4442 368 + 3494 568 + 1495 4851 + 4138 1157 + 4312 584 + 496 1418 + 912 1798 + 1371 3457 + 2917 1586 + 4199 3217 + 1330 2512 + 2351 4880 + 2295 3008 + 4112 3418 + 330 3073 + 3550 3908 + 4779 1489 + 4443 1673 + 1291 4883 + 1272 63 + 2595 3343 + 3967 1094 + 540 332 + 1910 4951 + 1446 2685 + 3844 1128 + 986 2016 + 165 492 + 4442 1285 + 1370 2338 + 2408 3913 + 3097 4429 + 274 2207 + 2822 4748 + 3585 1568 + 4664 1780 + 1712 242 + 3879 2015 + 2627 4623 + 4253 732 + 19 4541 + 3339 2992 + 3745 1329 + 1200 1174 + 1039 934 + 1947 4742 + 4960 3486 + 1547 4207 + 4956 3980 + 4120 2154 + 4595 3848 + 4947 4703 + 722 1965 + 639 3825 + 1488 4926 + 4817 4928 + 3199 3813 + 1238 879 + 668 4406 + 2991 417 + 3822 2299 + 354 2146 + 250 2407 + 4864 4771 + 1913 1398 + 2024 2123 + 4694 744 + 4033 610 + 808 4483 + 4322 4572 + 5000 4014 + 1548 569 + 3281 3104 + 4214 559 + 397 2544 + 1071 1739 + 4188 4754 + 891 518 + 304 847 + 2745 309 + 2001 141 + 824 780 + 3419 1788 + 1146 4620 + 1463 3801 + 3983 1036 + 1685 1146 + 4172 123 + 3003 2904 + 3328 701 + 3929 4708 + 1524 1662 + 772 1498 + 1075 108 + 1395 726 + 1505 1450 + 3267 1191 + 4749 3092 + 1701 1698 + 1753 4490 + 730 4886 + 4081 4510 + 4542 3010 + 4515 3220 + 4780 4358 + 1351 2898 + 114 1799 + 1498 3975 + 2263 1742 + 4779 4334 + 4198 3670 + 790 4747 + 3126 2204 + 2577 4400 + 1214 685 + 708 3072 + 3756 3477 + 3541 1241 + 849 3560 + 924 2724 + 942 1941 + 2049 3447 + 3325 2185 + 3846 3073 + 3298 4094 + 1102 2797 + 2979 4200 + 4075 3105 + 1995 2772 + 1713 4021 + 332 747 + 3056 4276 + 1700 4725 + 2454 4828 + 2166 1761 + 2162 4510 + 2714 2451 + 1012 1998 + 196 1248 + 3702 4387 + 2625 3833 + 2922 3046 + 1354 306 + 3052 3055 + 4397 3735 + 2567 144 + 1015 3855 + 26 177 + 3942 1935 + 1003 115 + 143 3793 + 3843 2328 + 661 1497 + 3520 410 + 672 1775 + 1237 2395 + 4182 514 + 1041 4491 + 1428 4254 + 4356 3451 + 565 3021 + 2686 2884 + 1667 2545 + 1386 4841 + 1644 4136 + 2979 2200 + 3475 1279 + 2334 4186 + 154 3700 + 981 1275 + 3916 3309 + 1652 4193 + 4806 1344 + 1940 1188 + 1246 1302 + 427 32 + 4556 4511 + 4006 2450 + 3761 716 + 1010 2322 + 3997 3794 + 414 3350 + 2462 1728 + 3133 135 + 1766 2813 + 3993 3775 + 3210 2631 + 2899 1159 + 4930 3949 + 4083 4709 + 3993 539 + 2712 3278 + 3985 2819 + 1373 1409 + 3569 3116 + 122 1286 + 4257 58 + 2944 258 + 2617 3550 + 2870 1016 + 4016 287 + 2200 2908 + 3202 4104 + 4133 2380 + 3642 138 + 1655 4910 + 3346 297 + 4765 4771 + 4698 2189 + 1077 716 + 74 3113 + 1231 4919 + 3606 4707 + 2425 336 + 2996 2179 + 603 1461 + 3235 1280 + 4594 3749 + 3300 932 + 3250 3153 + 1949 4950 + 373 383 + 3059 711 + 3632 1452 + 2504 357 + 4837 2760 + 1715 1205 + 3088 3467 + 4083 1404 + 4792 4988 + 2442 2195 + 4051 2513 + 4803 3467 + 2328 103 + 4082 506 + 63 1548 + 990 1649 + 1806 1114 + 1157 4389 + 4872 370 + 3 551 + 4680 4966 + 3933 2511 + 3297 3188 + 1626 4436 + 504 2952 + 4139 4868 + 4484 3283 + 3275 2594 + 337 4313 + 1930 409 + 1966 3718 + 781 1190 + 2482 304 + 2501 47 + 1885 2601 + 2488 4001 + 2850 227 + 396 732 + 2916 3403 + 2360 276 + 3950 587 + 4699 4826 + 3077 2887 + 3944 3404 + 1195 1800 + 3867 4588 + 3321 4583 + 243 2338 + 4936 184 + 612 1688 + 4350 1683 + 4648 454 + 4132 542 + 4632 9 + 4659 19 + 4665 2949 + 3479 950 + 601 4435 + 2397 4362 + 3036 4790 + 307 3947 + 4957 2380 + 4465 89 + 721 3098 + 3370 1021 + 42 3971 + 3050 3996 + 2168 607 + 4434 2812 + 3799 2052 + 1583 3093 + 2973 189 + 1278 4885 + 2611 1232 + 971 2972 + 1127 3559 + 4058 4809 + 607 2385 + 4571 2449 + 1725 4653 + 1736 470 + 1829 801 + 4423 669 + 3027 1854 + 120 4201 + 17 1320 + 4274 4560 + 1931 351 + 2431 1966 + 4114 1890 + 4138 3475 + 2019 4363 + 3603 78 + 2405 4755 + 4133 2542 + 2270 1564 + 3733 4184 + 2321 78 + 2962 3028 + 4120 3188 + 2815 4764 + 2876 1764 + 2318 117 + 4104 1047 + 4294 4934 + 1436 297 + 2293 1214 + 1647 237 + 4215 3450 + 4477 2051 + 294 923 + 3800 3776 + 2640 1792 + 2497 2242 + 581 3022 + 3944 3481 + 287 317 + 4435 1958 + 4170 153 + 1514 1072 + 1383 4920 + 3991 3079 + 3162 3205 + 848 2229 + 1072 4954 + 779 1582 + 4461 3294 + 2067 1623 + 92 443 + 4472 3060 + 2926 4584 + 2841 4284 + 1060 2246 + 3120 95 + 1383 3395 + 536 3120 + 3381 1729 + 3327 4474 + 4526 155 + 1059 4255 + 217 1160 + 1255 2557 + 3988 1745 + 764 4422 + 3796 1565 + 469 1044 + 646 114 + 800 890 + 1046 127 + 1490 4708 + 3545 2983 + 3034 1809 + 2751 2617 + 4187 4194 + 2316 4073 + 1709 416 + 1688 297 + 4052 1783 + 1622 599 + 4168 3045 + 3593 173 + 2845 2441 + 3399 1042 + 3159 1993 + 3813 3030 + 3857 2947 + 3540 1361 + 3320 3474 + 160 4257 + 776 451 + 4405 1135 + 4197 293 + 3079 3219 + 4280 2961 + 4086 3500 + 3903 1893 + 1351 472 + 3447 4494 + 360 4852 + 3540 893 + 2364 3156 + 2122 489 + 2681 2548 + 614 3323 + 3013 2615 + 1861 1282 + 4196 295 + 2102 4840 + 2502 627 + 3721 4973 + 1744 4008 + 805 864 + 3769 3972 + 1046 3279 + 2902 1178 + 885 1224 + 1399 3663 + 822 517 + 2831 3830 + 1538 3942 + 3993 4574 + 1144 498 + 4128 1405 + 350 649 + 3433 303 + 2516 870 + 1539 939 + 472 431 + 1670 1219 + 3974 1698 + 4559 4968 + 4941 3328 + 2655 2713 + 3924 1170 + 89 449 + 3976 1005 + 1258 2846 + 99 1878 + 51 4701 + 2249 1206 + 2993 3403 + 4970 2956 + 1881 2124 + 775 1331 + 4781 1426 + 4479 3383 + 244 632 + 2363 4867 + 3254 4698 + 1899 2384 + 2439 3189 + 599 1994 + 1638 2228 + 3196 2826 + 927 3088 + 2727 172 + 1371 2890 + 2855 1378 + 732 3350 + 4119 1030 + 2975 949 + 558 759 + 4909 277 + 310 2741 + 2637 2635 + 4886 4916 + 2978 4638 + 3421 3965 + 4064 3862 + 3886 1749 + 3924 2196 + 4446 4573 + 732 2568 + 1248 3696 + 2714 1028 + 2155 1653 + 4270 4675 + 4960 428 + 4202 2178 + 2241 3167 + 1664 3515 + 1046 450 + 3232 2735 + 59 207 + 4975 4606 + 870 3690 + 3547 102 + 366 296 + 2742 1857 + 329 395 + 2580 3891 + 2192 4588 + 1513 2969 + 3008 4604 + 4994 2502 + 279 4383 + 1085 1651 + 1826 4456 + 961 2619 + 4999 263 + 3440 2370 + 3608 1377 + 2982 1975 + 3971 1061 + 1605 4214 + 3542 444 + 126 1432 + 4413 688 + 4927 2785 + 3639 1412 + 2116 2410 + 1797 2559 + 4150 374 + 2038 2732 + 762 1884 + 4523 3382 + 392 4884 + 4352 2926 + 2808 3277 + 1798 4406 + 4658 2696 + 4526 1090 + 2588 2265 + 3674 2290 + 3311 1612 + 1820 594 + 4996 2503 + 3942 1757 + 2020 1778 + 1117 1908 + 1213 4554 + 1764 814 + 907 4406 + 4351 1117 + 2999 3264 + 3092 2323 + 170 1757 + 4006 4858 + 4509 1914 + 1996 3414 + 3448 511 + 4911 1948 + 1342 3346 + 3602 2892 + 2449 1372 + 2061 4803 + 3259 4722 + 2693 2733 + 4093 896 + 3161 4571 + 2034 1427 + 1841 1570 + 4009 4127 + 3586 366 + 4632 703 + 3542 2435 + 2980 3677 + 4308 375 + 2722 294 + 3153 4966 + 3638 2068 + 4779 2051 + 3823 988 + 2790 859 + 1720 2947 + 4758 3490 + 53 488 + 771 1917 + 1435 3688 + 4473 1223 + 3018 2883 + 64 3735 + 653 2798 + 168 3920 + 1724 2219 + 1525 3420 + 1176 1564 + 4266 2860 + 2576 961 + 4103 2398 + 2097 1707 + 3581 3586 + 4507 3051 + 3826 3144 + 2859 3020 + 842 4564 + 2084 3050 + 4987 2772 + 779 3182 + 3154 1445 + 3547 2745 + 4768 4173 + 2365 235 + 2708 605 + 4598 1682 + 1430 2343 + 1199 2794 + 4310 3078 + 4173 2206 + 4545 267 + 325 1762 + 4655 2319 + 4689 1423 + 1163 4554 + 3547 3489 + 1147 3605 + 2641 1066 + 2713 4435 + 532 938 + 1350 2620 + 1689 770 + 2238 4761 + 2062 4578 + 694 863 + 3645 4913 + 707 4185 + 4886 2520 + 3230 2549 + 3894 4187 + 3361 3757 + 964 3759 + 973 4111 + 3594 3027 + 2222 2545 + 2273 1289 + 2391 2741 + 2598 504 + 4040 1500 + 4930 4632 + 4907 4614 + 1011 4211 + 835 431 + 3965 40 + 1380 72 + 2516 145 + 1928 3307 + 2889 2479 + 2395 1164 + 3045 77 + 4336 92 + 526 2459 + 4705 1445 + 361 31 + 969 2008 + 2202 2918 + 4200 2970 + 4580 4747 + 2323 3056 + 3693 2817 + 2936 232 + 1591 2864 + 4068 739 + 4173 2038 + 3510 1437 + 4283 1689 + 373 3362 + 2519 1013 + 1375 4921 + 4384 382 + 879 1070 + 2168 149 + 3877 1933 + 2308 1360 + 2905 2749 + 2776 1501 + 1164 172 + 3458 2866 + 4087 1707 + 996 689 + 242 4378 + 3383 3523 + 3225 704 + 2807 3765 + 3240 2045 + 1777 3357 + 2791 2325 + 2985 51 + 4540 4165 + 3149 1708 + 106 1950 + 4800 2805 + 2033 4169 + 4716 704 + 4436 4824 + 1508 207 + 357 2221 + 656 3874 + 4413 2190 + 4364 4900 + 4985 312 + 208 2159 + 3536 974 + 369 1010 + 2789 194 + 1416 2306 + 3244 981 + 2852 3994 + 1941 3968 + 1051 1909 + 716 4716 + 1998 1415 + 4382 1341 + 4857 3642 + 1162 142 + 1415 368 + 4591 4103 + 2998 2832 + 2203 3034 + 1737 2371 + 2985 4705 + 398 915 + 4084 4607 + 1027 1524 + 2181 3405 + 1097 567 + 1596 795 + 3128 2636 + 3693 3227 + 4076 451 + 3028 1584 + 2495 1676 + 3447 4461 + 1889 4089 + 2514 857 + 3269 4665 + 4167 4588 + 4049 3979 + 1765 2991 + 30 529 + 4407 3802 + 3895 4923 + 3295 2046 + 625 603 + 4100 1822 + 2758 366 + 4743 2382 + 4341 3919 + 1912 4701 + 2345 873 + 3887 2818 + 1701 561 + 4338 1870 + 3681 1934 + 722 3268 + 3872 2288 + 1426 3377 + 2699 4279 + 1916 3981 + 1711 4979 + 930 4837 + 3948 3126 + 345 2263 + 3296 1957 + 1506 1803 + 1424 1008 + 813 1677 + 492 2267 + 3941 1952 + 3428 4719 + 3790 4178 + 3895 759 + 102 1378 + 3094 4373 + 4401 1077 + 1618 285 + 635 2725 + 2281 190 + 3041 2977 + 4283 1216 + 3074 733 + 916 3908 + 3883 3016 + 3337 2240 + 4329 3676 + 41 2135 + 1239 724 + 3620 540 + 3746 89 + 655 3955 + 1573 4758 + 2601 4421 + 3777 4897 + 2860 1539 + 220 4184 + 4203 1157 + 4290 147 + 294 3263 + 3665 2485 + 1388 557 + 1189 2279 + 3793 1246 + 2994 4980 + 2396 2005 + 135 4563 + 4050 3677 + 686 3802 + 2072 4587 + 4083 4747 + 1849 1948 + 999 3822 + 1047 1178 + 1289 2029 + 2184 1461 + 2029 4275 + 4364 623 + 3719 2983 + 3607 4856 + 2001 3606 + 3749 1494 + 2367 2833 + 1731 1797 + 2748 3972 + 3296 4021 + 573 1085 + 3992 71 + 547 128 + 701 649 + 941 1028 + 3735 1794 + 2116 1086 + 3394 1152 + 3415 3925 + 3617 3206 + 257 404 + 4846 4886 + 3691 21 + 237 3241 + 1536 1053 + 2281 4339 + 1498 4559 + 2316 3124 + 1406 533 + 3538 1858 + 4664 1382 + 2231 3446 + 4093 4831 + 2234 1539 + 3446 2543 + 1732 795 + 3106 628 + 2513 1698 + 4387 105 + 2927 4965 + 4394 2597 + 4947 870 + 1002 1514 + 4951 977 + 3053 2714 + 3868 1862 + 1486 155 + 690 304 + 632 3470 + 4540 4929 + 2473 3500 + 72 4327 + 4664 1260 + 3954 1237 + 3880 240 + 580 4574 + 1263 3994 + \. + + COPY t2 (a1, a2) FROM stdin; + 119 1124 + 949 527 + 3979 3780 + 3394 1084 + 791 369 + 3698 4763 + 3118 2029 + 3687 1849 + 125 3990 + 1825 227 + 2306 3618 + 4222 3959 + 373 3603 + 2637 4247 + 3187 1670 + 3844 3451 + 1667 4213 + 4079 1126 + 4292 1452 + 2687 471 + 1345 3331 + 2173 35 + 4576 636 + 4985 3947 + 576 1282 + 1707 3629 + 426 831 + 4469 4827 + 924 3722 + 4965 3451 + 2658 1931 + 2498 852 + 115 1614 + 4638 1119 + 3072 4615 + 3794 3186 + 1553 4621 + 1457 1712 + 1125 3272 + 4547 3515 + 2911 4298 + 1915 2173 + 4261 3774 + 3159 3742 + 2183 4661 + 996 3346 + 1899 4482 + 2272 3629 + 1612 1747 + 548 2320 + 3203 2108 + 4943 3111 + 2691 150 + 340 4356 + 4327 2728 + 4945 3921 + 4758 4309 + 2637 2955 + 499 4626 + 3135 445 + 1654 3495 + 2602 1186 + 4426 1904 + 1072 1163 + 2590 4966 + 998 2610 + 2112 3903 + 270 1710 + 3813 4118 + 4188 4977 + 3344 2643 + 1966 1826 + 1979 3548 + 2177 1697 + 4268 174 + 2105 3235 + 2062 2975 + 3068 2238 + 4030 53 + 935 3009 + 1633 1754 + 3885 4740 + 1315 3489 + 3644 3759 + 4570 1982 + 4389 4283 + 87 1516 + 2533 4929 + 2916 863 + 1914 2374 + 1453 149 + 2653 4667 + 2614 3801 + 4918 4471 + 626 2466 + 3996 2921 + 2220 2456 + 2094 1507 + 2666 4789 + 2487 3685 + 4593 505 + 685 360 + 4527 1481 + 4983 4268 + 4397 1225 + 2526 3597 + 2529 4834 + 549 1742 + 1981 2575 + 3563 4875 + 245 4288 + 4483 503 + 3991 4470 + 2709 4248 + 1189 1485 + 1010 154 + 1607 3908 + 3844 4506 + 2739 2425 + 4400 2804 + 4802 1615 + 1294 606 + 2837 3119 + 3006 1251 + 3794 1838 + 4663 2754 + 617 1111 + 3487 700 + 3925 2948 + 280 728 + 2414 2159 + 355 2054 + 1025 2678 + 3626 2461 + 2726 4574 + 4117 2547 + 2463 3285 + 4618 264 + 1993 639 + 3014 2982 + 3712 4153 + 1638 4444 + 1812 895 + 151 4195 + 2730 4012 + 3031 4546 + 2600 3124 + 253 3710 + 3698 1917 + 3170 2902 + 4312 3298 + 294 4071 + 176 467 + 386 4251 + 3689 3507 + 4930 3047 + 4916 2868 + 3214 3541 + 933 3057 + 105 4776 + 790 4144 + 528 4848 + 1605 1696 + 3205 827 + 4687 676 + 4021 3793 + 4332 3735 + 3306 3714 + 2609 370 + 3266 3822 + 1119 1735 + 4537 2852 + 2673 3157 + 3227 4472 + 4554 80 + 4734 4329 + 3173 847 + 3942 3733 + 484 1292 + 3984 1333 + 2615 3563 + 3576 993 + 3256 2902 + 2784 220 + 2557 506 + 923 1341 + 3806 1281 + 2845 479 + 2661 74 + 3421 56 + 422 2653 + 2901 4374 + 2663 2680 + 1755 377 + 2007 3063 + 77 2279 + 4939 67 + 1068 421 + 741 771 + 3672 1443 + 851 2412 + 4408 4439 + 4376 4204 + 2020 4287 + 1338 593 + 4280 1226 + 1452 3874 + 1897 3155 + 202 235 + 647 4751 + 2516 1507 + 1459 1469 + 4666 2716 + 2158 4936 + 2036 1394 + 2009 315 + 1890 4975 + 2066 1971 + 943 3717 + 2610 3627 + 948 846 + 4278 382 + 991 1355 + 2114 4765 + 3952 1136 + 4659 2419 + 1193 3727 + 2025 770 + 4151 1128 + 1268 1856 + 3395 4297 + 3904 864 + 2371 2982 + 1860 212 + 2305 4564 + 3549 3101 + 4818 921 + 1989 848 + 4628 1688 + 1053 1485 + 910 2814 + 1585 3073 + 1071 4226 + 4650 2895 + 485 4089 + 12 511 + 2819 3081 + 3039 2377 + 1984 4798 + 617 4498 + 410 2925 + 3781 4546 + 2373 4765 + 265 1073 + 129 4121 + 2723 1954 + 3548 1348 + 3531 1995 + 3393 556 + 2743 1149 + 2173 1090 + 1564 3829 + 2802 4019 + 4685 3773 + 2836 5000 + 2481 1965 + 18 1109 + 2044 1670 + 1394 4586 + 3907 3208 + 1631 2773 + 3061 4603 + 4502 4763 + 4366 4196 + 1836 4551 + 3554 2820 + 1249 4978 + 181 2719 + 2472 1000 + 1763 3292 + 4735 2007 + 2982 1601 + 4549 673 + 1412 832 + 4502 2239 + 2829 3637 + 3598 4541 + 2805 1070 + 1375 4870 + 1099 2057 + 26 571 + 2189 845 + 651 4254 + 3962 416 + 3191 3107 + 4936 1555 + 2104 584 + 2292 4264 + 3824 1998 + 1599 3189 + 1563 4736 + 3407 2683 + 3244 3503 + 1420 3868 + 3409 3701 + 2701 4970 + 1135 565 + 4005 3890 + 139 4253 + 1677 3644 + 4685 3154 + 3429 3029 + 4285 3401 + 2262 3563 + 238 4533 + 3168 2099 + 1250 4817 + 3643 2615 + 4358 3721 + 1079 1289 + 934 1717 + 1953 4441 + 371 2982 + 650 2863 + 1791 2611 + 3315 4324 + 1369 4259 + 1768 1907 + 3557 570 + 3561 1809 + 4774 2390 + 511 2275 + 174 3689 + 112 3640 + 1789 29 + 4900 220 + 110 4799 + 4499 4614 + 91 1486 + 4063 2267 + 1146 4823 + 1129 2307 + 2085 2930 + 4287 839 + 516 2445 + 4905 3920 + 1649 4995 + 3155 766 + 2986 4122 + 867 2842 + 4895 1845 + 2302 4967 + 2582 2272 + 1067 4935 + 3013 1055 + 233 2950 + 3561 289 + 1604 2373 + 4584 3701 + 2378 518 + 1051 44 + 3233 1969 + 2688 458 + 1749 1201 + 898 3885 + 1042 3956 + 1423 76 + 526 3887 + 1546 522 + 4036 421 + 2007 395 + 3075 3713 + 513 4558 + 954 1324 + 3818 1752 + 1546 3035 + 235 1791 + 1685 1651 + 2812 4070 + 3780 555 + 2456 2946 + 3655 1934 + 551 3217 + 3993 3026 + 2326 1178 + 1689 4070 + 2859 4042 + 2433 3432 + 1583 3176 + 3600 3887 + 685 4670 + 4527 4723 + 3503 997 + 421 1666 + 985 668 + 1830 324 + 2151 597 + 3618 2520 + 2718 4480 + 2739 2118 + 2459 2130 + 3519 3817 + 3131 4230 + 492 3013 + 1105 2197 + 2722 4845 + 1646 2703 + 272 888 + 2257 2148 + 3008 2646 + 4501 3709 + 2691 4953 + 2689 4985 + 1241 261 + 3033 4088 + 2317 783 + 3086 280 + 429 1296 + 1051 4237 + 3058 2854 + 974 1280 + 2270 4133 + 923 869 + 2458 2640 + 4924 1896 + 3102 2552 + 2472 3074 + 3157 4609 + 2979 2706 + 69 4536 + 713 4925 + 1102 4698 + 4783 3610 + 3245 4168 + 567 3841 + 392 177 + 2670 2260 + 2855 1591 + 4535 2963 + 2606 2801 + 4601 3819 + 1331 486 + 948 725 + 3911 283 + 2484 127 + 3079 1567 + 4513 2289 + 4282 4572 + 4368 1660 + 4503 245 + 256 4234 + 2683 2779 + 2055 854 + 749 2028 + 2943 2589 + 296 3981 + 703 507 + 736 3737 + 3853 4591 + 2097 4801 + 4533 3555 + 3185 4258 + 958 3871 + 2312 4975 + 1473 1628 + 3076 2200 + 1526 4220 + 3300 2783 + 1493 3695 + 394 141 + 500 4987 + 3887 2351 + 577 2837 + 3977 4739 + 3985 3881 + 271 2850 + 2735 4363 + 4995 4105 + 1490 860 + 3078 3217 + 2279 1041 + 600 2845 + 819 3265 + 4746 323 + 4706 3578 + 2032 625 + 3627 160 + 2958 1048 + 3138 659 + 3563 606 + 511 1673 + 972 4587 + 988 2905 + 1207 1762 + 4473 3025 + 2767 2059 + 1828 4279 + 4754 102 + 3161 4796 + 2266 1970 + 541 4089 + 4205 4735 + 4706 4260 + 4236 2056 + 2556 1029 + 523 3367 + 194 4189 + 3104 2255 + 3698 4015 + 4823 1768 + 3347 699 + 3019 718 + 2692 390 + 2435 2096 + 1811 823 + 45 2975 + 4190 2381 + 3498 2532 + 570 2712 + 47 2445 + 3706 2903 + 4841 4296 + 1590 3791 + 4247 3401 + 4910 353 + 3503 776 + 3755 4750 + 1645 2548 + 714 2594 + 2018 1328 + 1444 3751 + 157 677 + 886 80 + 2189 2054 + 1083 403 + 2311 1744 + 376 2903 + 3153 2606 + 2291 2517 + 1762 807 + 737 3861 + 1210 2868 + 2057 797 + 3344 1544 + 4301 3781 + 18 2823 + 712 1662 + 4328 2792 + 2864 1536 + 2863 4680 + 2016 3068 + 617 530 + 2492 1496 + 4612 783 + 549 2563 + 3569 4306 + 3338 640 + 3787 3498 + 684 1953 + 246 3512 + 3364 4328 + 1076 4951 + 3695 490 + 809 407 + 14 4076 + 1668 3383 + 4986 2660 + 4048 3696 + 2625 423 + 3342 1535 + 4672 4291 + 2570 2550 + 1471 3231 + 3088 4103 + 1209 843 + 4867 1612 + 4307 4595 + 4852 2805 + 2802 4517 + 2506 3763 + 262 2848 + 3783 2930 + 2704 3836 + 4158 508 + 2874 1649 + 1257 2725 + 616 2363 + 3563 1977 + 324 2045 + 1722 2165 + 3714 3334 + 4861 722 + 710 2664 + 605 2924 + 4141 2963 + 3015 2360 + 1429 1827 + 2374 4921 + 2490 2833 + 3644 2880 + 2551 3483 + 3475 2858 + 918 795 + 2076 3897 + 2498 2608 + 1181 2898 + 1054 3572 + 3692 4039 + 505 2316 + 338 2170 + 3394 2327 + 4263 3980 + 1443 2569 + 316 782 + 2779 2863 + 3999 2531 + 3849 3288 + 2936 468 + 3863 933 + 696 2333 + 2613 2492 + 150 3725 + 431 3897 + 1586 4463 + 4433 3262 + 2276 2747 + 4032 2088 + 3356 3336 + 175 4285 + 1514 2459 + 2582 2216 + 3898 2503 + 688 4109 + 2136 1510 + 2153 173 + 2756 1107 + 2920 4065 + 2415 1923 + 1296 1027 + 4735 549 + 4400 2690 + 4340 1632 + 3100 2645 + 3613 2295 + 4979 1477 + 2073 783 + 1481 4824 + 3608 1120 + 4420 577 + 2839 3609 + 2876 3333 + 2101 1486 + 1923 2946 + 523 2469 + 285 4638 + 3385 1773 + 2534 3511 + 1125 1589 + 2992 2063 + 3973 571 + 3644 442 + 866 3045 + 2283 4009 + 1970 4307 + 4317 2300 + 1442 2812 + 3399 1388 + 1906 2648 + 1474 2261 + 1773 3111 + 1461 4162 + 3750 4693 + 2446 4673 + 2029 3879 + 2407 4162 + 447 261 + 1508 1251 + 66 4664 + 4464 1432 + 1200 1970 + 159 3942 + 3372 4674 + 2147 3846 + 4706 1766 + 1839 4697 + 3926 1526 + 4588 781 + 4549 1133 + 2559 3990 + 109 663 + 1498 587 + 942 2965 + 1000 987 + 1104 553 + 4109 1184 + 4811 1931 + 2850 4560 + 4579 4515 + 3915 3518 + 1834 664 + 2111 3524 + 4784 1298 + 2691 2293 + 4475 3888 + 2550 2264 + 719 957 + 4103 1215 + 2933 4145 + 1763 4433 + 4022 3487 + 998 718 + 593 1783 + 348 1259 + 4684 3266 + 2474 3757 + 185 3475 + 2731 3580 + 1057 305 + 2497 3727 + 4881 666 + 4719 205 + 1099 1403 + 1309 739 + 4632 519 + 4509 1604 + 1722 2804 + 3539 3368 + 4671 1035 + 2345 4929 + 2670 524 + 661 2625 + 2550 465 + 2712 3856 + 1724 2089 + 858 4492 + 3697 2552 + 1800 2920 + 3139 636 + 4589 4488 + 4457 1170 + 3554 3288 + 890 3052 + 4808 2063 + 2058 1396 + 4394 3078 + 29 1374 + 2944 3346 + 2525 2037 + 2045 1814 + 2962 688 + 288 2123 + 1967 237 + 3413 2410 + 4638 1519 + 3239 2841 + 4252 4345 + 3592 3567 + 3624 320 + 2692 2663 + 1040 3013 + 910 2000 + 2202 3905 + 4821 4289 + 2222 825 + 2623 154 + 4316 733 + 1881 1856 + 2695 4133 + 4256 4580 + 102 2828 + 2370 3705 + 767 4618 + 4445 4710 + 3275 2992 + 3051 740 + 77 4749 + 4508 3600 + 2832 4126 + 1998 3148 + 4746 2866 + 3698 2384 + 3907 498 + 973 871 + 1872 2453 + 4674 4492 + 2035 823 + 3310 383 + 4881 1179 + 2288 2514 + 96 2337 + 3756 4192 + 1628 3519 + 2972 2705 + 3163 3922 + 865 199 + 2764 4191 + 1424 257 + 4148 1479 + 2237 1911 + 4661 2296 + 4454 4727 + 4135 2615 + 189 4880 + 51 1525 + 2907 1568 + 3423 2187 + 2510 3025 + 4809 2427 + 782 933 + 395 3583 + 1807 4853 + 57 3008 + 1958 4856 + 3617 1244 + 221 25 + 1099 3055 + 307 4225 + 1573 2408 + 1511 1615 + 1740 3884 + 4869 1669 + 4892 3735 + 3237 167 + 345 4985 + 2509 3569 + 4319 1922 + 3586 1538 + 4945 1486 + 610 1429 + 3858 936 + 3546 2005 + 3164 2929 + 1386 138 + 4155 4505 + 2063 1119 + 4165 878 + 1408 1515 + 359 1136 + 2647 1903 + 2821 2443 + 2119 1384 + 161 4609 + 2877 880 + 3263 4641 + 4155 4704 + 605 2300 + 4505 1637 + 1980 2448 + 4829 4713 + 4271 1781 + 167 1096 + 2224 3138 + 4077 3349 + 4771 3176 + 4299 3194 + 1834 46 + 619 4340 + 3092 1414 + 3683 1129 + 1418 4067 + 1069 853 + 4238 4477 + 3900 3096 + 712 2201 + 1743 22 + 902 1162 + 3821 2466 + 4675 4707 + 4970 3592 + 3609 2296 + 536 4162 + 2987 842 + 2001 2145 + 249 26 + 3048 2878 + 568 1592 + 531 3606 + 3592 2150 + 4478 1688 + 4141 1920 + 2043 3260 + 3979 2631 + 116 2777 + 2501 4549 + 792 4110 + 2356 1589 + 2200 3110 + 3043 52 + 766 541 + 1472 3052 + 1308 2890 + 4567 853 + 4528 2581 + 655 4007 + 2481 3325 + 2002 2399 + 2767 2611 + 709 3465 + 4639 949 + 4179 1822 + 4664 2825 + 4651 2897 + 1708 481 + 4165 3892 + 4050 933 + 2271 2341 + 864 2226 + 4228 1935 + 961 2063 + 2912 3665 + 1912 3459 + 1155 953 + 930 4441 + 3703 2348 + 553 325 + 4875 1842 + 1222 1626 + 34 4635 + 2246 2097 + 3245 2827 + 281 125 + 1609 4129 + 2552 3623 + 3325 1758 + 1962 4749 + 4961 4424 + 3938 4993 + 4259 1929 + 2832 2170 + 1782 733 + 3273 3071 + 1489 1581 + 3164 3052 + 2985 378 + 551 3171 + 4388 1852 + 3783 3104 + 1300 4310 + 1340 3754 + 1538 1086 + 2408 4851 + 3630 4010 + 613 125 + 3564 4541 + 20 3887 + 2120 3504 + 326 4433 + 4447 2155 + 421 4036 + 336 4016 + 2037 1493 + 1308 1739 + 2325 4455 + 558 3460 + 1295 85 + 4726 2672 + 2180 4219 + 1568 588 + 1452 1669 + 3426 429 + 681 491 + 1190 920 + 3612 795 + 4616 3569 + 749 2729 + 408 1237 + 4340 991 + 3176 3275 + 3587 3535 + 4957 777 + 412 3063 + 2470 864 + 3688 1567 + 4576 3396 + 2492 4877 + 3407 974 + 769 2251 + 4799 862 + 4608 2945 + 2555 2007 + 3439 2390 + 2152 1328 + 1097 2926 + 399 130 + 1112 3797 + 2021 4076 + 3739 1036 + 3636 1278 + 3932 1542 + 3142 4715 + 4030 3441 + 2826 398 + 40 3581 + 3833 2594 + 4587 2799 + 676 223 + 3703 4153 + 697 4150 + 2834 3284 + 2680 31 + \. + + COPY t3 (a2, a0) FROM stdin; + 3834 3604 + 2772 195 + 2301 1022 + 3474 2666 + 99 4637 + 4162 3309 + 3570 1315 + 4797 1792 + 745 1735 + 74 2967 + 4251 2399 + 1296 3124 + 4383 2133 + 2705 1679 + 1372 1941 + 1012 3571 + 1070 4064 + 2385 3994 + 2035 3093 + 3829 3408 + 4487 4873 + 4386 2970 + 3510 3619 + 4347 1079 + 930 3133 + 3570 2691 + 1921 740 + 3807 240 + 274 4113 + 1126 4030 + 1771 984 + 47 4941 + 2746 2193 + 1215 3097 + 1061 1430 + 3966 1031 + 2190 390 + 2967 4324 + 2121 1546 + 3313 1288 + 3854 1695 + 3578 3387 + 1394 313 + 550 1438 + 1181 460 + 2777 1019 + 3112 260 + 3754 1833 + 2717 1595 + 2293 3206 + 956 4100 + 1727 2965 + 3567 2671 + 2768 4455 + 3841 3017 + 4759 1534 + 3661 3501 + 1363 668 + 2260 6 + 1466 1336 + 1086 1752 + 4402 4914 + 1747 474 + 1247 2352 + 4429 3376 + 2973 110 + 3846 2362 + 4974 4794 + 1102 1039 + 2144 260 + 3807 3331 + 1404 1127 + 3342 2560 + 2404 363 + 4357 3870 + 4307 3743 + 4399 1494 + 3023 3422 + 4341 919 + 1819 3123 + 3872 4743 + 311 1513 + 4964 1453 + 4142 627 + 2976 2283 + 3239 2044 + 914 2920 + 1385 435 + 3545 1366 + 3862 480 + 493 3616 + 4696 2548 + 1416 4249 + 3511 3998 + 3422 4335 + 4128 1279 + 806 3009 + 885 1954 + 4660 2251 + 734 918 + 2163 1711 + 688 1808 + 3545 3150 + 3558 4749 + 3911 316 + 2671 4595 + 4863 4149 + 2073 2678 + 3423 4607 + 4379 4352 + 1887 3243 + 2415 2134 + 553 3393 + 4254 2581 + 4026 2074 + 1175 2332 + 684 3642 + 2494 2130 + 2726 1483 + 3721 3504 + 923 4561 + 28 3105 + 193 1449 + 2985 2719 + 1654 4427 + 2245 1505 + 1140 3217 + 1937 4179 + 3602 3299 + 4602 2938 + 2380 1799 + 2174 4290 + 4246 3824 + 319 4602 + 4197 3507 + 2158 1051 + 4296 2149 + 2860 593 + 2016 1534 + 4381 388 + 958 4374 + 1575 648 + 1344 23 + 472 2418 + 530 4247 + 599 2270 + 4017 4563 + 1155 2381 + 4549 4185 + 4451 2441 + 720 2741 + 2126 2848 + 160 2623 + 1665 4423 + 186 3303 + 1959 3286 + 100 3582 + 3708 1875 + 3901 888 + 2157 1400 + 4082 1179 + 916 1567 + 3807 3365 + 1469 202 + 794 2908 + 4547 4245 + 4289 370 + 575 4699 + 3337 2463 + 3962 4525 + 618 2562 + 4265 730 + 1182 1505 + 2703 4837 + 1602 724 + 2950 2923 + 1111 3701 + 3409 2398 + 4266 4716 + 706 2273 + 1525 1507 + 2898 144 + 944 2264 + 3237 4367 + 1697 4166 + 4710 920 + 4101 320 + 3609 4610 + 4654 1428 + 3956 3010 + 673 3838 + 3872 755 + 944 1548 + 68 3622 + 3266 1001 + 2422 27 + 1132 2905 + 1115 1273 + 1802 2540 + 2885 3608 + 1676 1413 + 4683 855 + 528 2811 + 4395 404 + 1088 1895 + 4153 4500 + 4247 2241 + 2907 3624 + 2975 4638 + 864 3772 + 598 419 + 3750 4663 + 3786 3236 + 3394 969 + 1140 3106 + 1835 3785 + 4141 4581 + 3342 3693 + 1650 339 + 4607 3587 + 2703 4453 + 1867 371 + 1494 597 + 2192 3454 + 1163 1584 + 4845 45 + 1954 50 + 899 1303 + 1025 2235 + 3162 4643 + 4925 3222 + 4629 4484 + 1131 4315 + 156 1568 + 2184 1784 + 2988 3100 + 1548 2633 + 4695 3161 + 459 4912 + 1830 4553 + 682 1790 + 1494 3437 + 873 3554 + 2649 1368 + 2730 2451 + 2206 3083 + 3859 4153 + 158 1264 + 2063 3619 + 786 1334 + 1801 38 + 4521 2321 + 2839 3838 + 4539 2209 + 2961 1446 + 4282 724 + 3977 2004 + 2200 2961 + 4279 637 + 791 1935 + 4345 3244 + 4578 3732 + 1578 1207 + 393 3664 + 4590 2490 + 2239 375 + 869 560 + 400 3470 + 2100 1696 + 3004 2841 + 3575 3943 + 3002 4415 + 1264 4619 + 3895 848 + 3223 2623 + 2038 3661 + 4094 809 + 971 3459 + 111 4033 + 685 3367 + 2536 4349 + 3736 1815 + 2366 692 + 3901 4996 + 7 2919 + 148 4678 + 3368 825 + 2447 1592 + 4746 1402 + 494 325 + 2231 11 + 3845 3419 + 504 83 + 1415 2521 + 291 4296 + 2756 3834 + 2645 1707 + 3018 3994 + 4372 694 + 3322 367 + 3388 543 + 4072 4664 + 1115 4372 + 881 519 + 3326 1539 + 4861 853 + 888 3438 + 2546 4413 + 604 4544 + 1147 4776 + 2210 3214 + 4716 4423 + 4533 3128 + 1910 3860 + 3616 922 + 2195 4733 + 3346 1445 + 1088 4728 + 54 80 + 943 4321 + 861 2350 + 550 3767 + 360 3974 + 1174 2382 + 1671 3183 + 2261 3105 + 4888 1223 + 1956 4616 + 4395 2751 + 823 2582 + 1645 4623 + 2558 4919 + 301 2844 + 3248 2642 + 4250 3295 + 348 450 + 4225 1096 + 3261 87 + 2326 4359 + 2279 1823 + 724 4770 + 2013 3449 + 3750 1754 + 3820 1225 + 2754 3441 + 2822 3256 + 527 987 + 207 854 + 2848 2010 + 1775 1538 + 499 2495 + 4321 2810 + 2127 3779 + 4548 548 + 3510 1657 + 3687 3890 + 3997 343 + 4034 2700 + 3244 1520 + 3086 788 + 2223 1518 + 334 4162 + 2457 4342 + 2011 355 + 2325 1134 + 3619 81 + 1342 1824 + 4233 3048 + 2603 3036 + 1427 2747 + 461 3177 + 3355 1438 + 3804 1260 + 440 2293 + 3816 1242 + 2787 398 + 31 727 + 122 1720 + 3879 46 + 3306 3435 + 3953 4472 + 1123 4461 + 1505 1773 + 4652 2220 + 2113 2405 + 876 496 + 79 484 + 1316 1460 + 922 115 + 4141 565 + 3043 3843 + 4339 703 + 3382 3600 + 3418 3974 + 1870 3807 + 2403 2829 + 3764 2530 + 4527 833 + 719 4036 + 4260 1005 + 2221 3623 + 1688 23 + 3472 2516 + 2761 4722 + 2598 1868 + 294 4826 + 1655 1863 + 692 2363 + 2899 597 + 1468 2354 + 562 2537 + 1421 2105 + 1433 312 + 3665 4651 + 2585 3737 + 1223 4836 + 2155 1079 + 744 1554 + 2125 2771 + 2993 3195 + 4822 4088 + 428 500 + 1689 1466 + 4214 151 + 4150 152 + 2047 2290 + 2008 3194 + 3261 1727 + 1402 867 + 4206 856 + 4816 1463 + 3869 2501 + 4107 928 + 1730 3469 + 1422 4026 + 1309 2861 + 128 1311 + 2981 438 + 2608 3470 + 4076 2364 + 1513 710 + 2514 3732 + 1587 3134 + 3878 206 + 110 715 + 197 4041 + 3846 2514 + 24 391 + 3337 3028 + 3977 2287 + 170 2631 + 3900 1194 + 88 123 + 3065 4592 + 188 277 + 2416 2326 + 2019 2748 + 3628 3504 + 3859 924 + 413 619 + 247 4870 + 3935 3850 + 1215 4167 + 1588 1101 + 4318 4140 + 3703 766 + 1699 1891 + 2605 1496 + 87 4939 + 900 644 + 820 2414 + 3521 1562 + 4985 3872 + 2989 2215 + 3726 1588 + 4116 2639 + 2872 2560 + 2832 2279 + 2535 2443 + 4582 4402 + 926 4655 + 1342 4480 + 4952 4901 + 3490 341 + 359 305 + 3909 4324 + 2792 1951 + 3254 14 + 3787 3854 + 3075 880 + 4916 4505 + 4930 4518 + 4215 1528 + 2635 4243 + 161 4095 + 1537 2961 + 3464 311 + 802 1449 + 1858 2324 + 1662 468 + 2059 2473 + 3859 1563 + 3289 3871 + 4974 2913 + 3299 2899 + 1132 1073 + 3264 3017 + 3953 4301 + 2053 4023 + 784 551 + 2768 90 + 2535 3029 + 4793 1648 + 2511 4685 + 2102 976 + 1374 982 + 935 2584 + 4584 2406 + 266 1173 + 4702 3930 + 2143 3992 + 1911 911 + 3464 849 + 2671 3635 + 4258 2277 + 2573 1607 + 1355 29 + 3494 82 + 3196 272 + 2525 1534 + 4953 2862 + 833 4754 + 2812 418 + 4298 1141 + 1246 2026 + 2434 770 + 3924 2608 + 1387 2131 + 3956 441 + 4090 4180 + 2289 4354 + 1903 795 + 2612 4769 + 763 1581 + 963 2508 + 4445 4503 + 4242 4689 + 1815 2138 + 3208 3292 + 3027 2048 + 3690 395 + 2594 1819 + 2212 478 + 1712 208 + 2874 4321 + 1398 3294 + 4802 1640 + 1420 167 + 2525 5 + 876 4178 + 1723 1834 + 1148 3713 + 2004 2149 + 4013 2367 + 1670 1253 + 1520 204 + 834 3111 + 3264 4449 + 1481 2683 + 2 4988 + 4798 2147 + 198 732 + 1819 1357 + 1060 3917 + 1580 319 + 4740 3094 + 907 1806 + 3906 4650 + 1768 101 + 4969 4967 + 231 398 + 4601 3939 + 2090 4107 + 1466 2337 + 3069 851 + 1870 3955 + 2648 102 + 126 2222 + 4019 686 + 1577 3741 + 3016 968 + 4095 2712 + 275 488 + 1974 956 + 1778 690 + 4615 3298 + 3988 2694 + 1892 2333 + 1665 4931 + 1147 3796 + 3637 4560 + 1966 645 + 1515 581 + 1020 2926 + 4537 4901 + 4514 2689 + 2783 4433 + 1588 1405 + 4990 3292 + 4652 2888 + 191 4013 + 1591 3471 + 2932 168 + 2041 4456 + 4552 4720 + 4776 4453 + 4429 4117 + 2824 2375 + 2582 3363 + 3946 4136 + 2995 3745 + 3967 167 + 1865 3087 + 1352 4609 + 960 1646 + 683 4389 + 4735 1456 + 1481 4425 + 3699 2917 + 2430 4657 + 1544 1800 + 1561 1044 + 4743 1425 + 663 3782 + 491 2425 + 1428 4095 + 869 1416 + 4580 2816 + 3364 413 + 1974 3796 + 751 3957 + 3978 2315 + 3899 2126 + 2214 2044 + 1383 2471 + 1717 3459 + 2052 4748 + 4902 1421 + 1844 3858 + 677 1622 + 2978 229 + 3278 380 + 4435 4617 + 4428 3374 + 1580 3808 + 1764 3077 + 1116 4586 + 1649 2215 + 3542 4339 + 2675 4985 + 3958 424 + 720 2452 + 1305 291 + 1536 3946 + 4372 1594 + 2297 1835 + 4114 3363 + 4970 1969 + 471 2417 + 1387 4232 + 4653 4947 + 4693 898 + 3359 2214 + 2240 1298 + 3436 703 + 4073 1227 + 2380 830 + 364 363 + 1681 1015 + 2294 1552 + 787 4606 + 1149 829 + 2497 4280 + 4863 423 + 1769 2388 + 2033 135 + 4727 1579 + 122 2486 + 2286 4365 + 1906 4797 + 2118 4930 + 3263 1688 + 3088 2708 + 2289 2116 + 1277 1649 + 478 4609 + 1081 1459 + 3239 3968 + 4656 1214 + 273 4011 + 3714 4843 + 4268 2406 + 4301 3934 + 4997 2804 + 4498 2268 + 2911 4916 + 3479 742 + 143 2437 + 453 3325 + 689 4914 + 3551 4587 + 4972 2351 + 673 2539 + 1477 3984 + 3593 2242 + 4517 465 + 894 3442 + 3391 1615 + 4097 239 + 40 521 + 3228 1794 + 4007 4421 + 464 1223 + 4668 2811 + 717 2937 + 614 2074 + 55 1696 + 3146 3132 + 3510 675 + 1350 1220 + 3816 3426 + 924 3638 + 1358 4729 + 2662 4895 + 2232 1492 + 2093 1246 + 3460 2636 + 2983 4305 + 716 3422 + 4439 604 + 2474 2909 + 1666 90 + 2459 4224 + 3135 808 + 3126 502 + 3919 1024 + 897 687 + 180 3210 + 196 1687 + 4069 2656 + 1680 660 + 851 3393 + 1004 2825 + 3400 1935 + 2861 1996 + 4437 4207 + 3698 707 + 3376 486 + 991 3155 + 2041 88 + 372 3840 + 2338 512 + 3021 3100 + 993 3750 + 3329 3017 + 4049 2256 + 1020 3064 + 2926 3921 + 3467 2001 + 2158 729 + 1582 670 + 1870 1700 + 1253 3116 + 1653 1307 + 235 3804 + 881 1336 + 4143 444 + 204 4146 + 3445 1637 + 3313 1085 + 1310 6 + 4311 4663 + 2166 3650 + 4486 2396 + 2743 1014 + 4155 3788 + 546 1313 + 825 3687 + 3607 4149 + 1825 4262 + 3654 664 + 2291 1078 + 3288 3564 + 2951 715 + 3765 140 + 2618 2470 + 955 668 + 617 1932 + 525 4907 + 4223 2236 + 2903 2416 + 662 347 + 2029 825 + 2192 2010 + 4708 2029 + 460 626 + 1644 3359 + 3768 3768 + 76 4158 + 1097 1548 + 3431 4586 + 2832 4862 + 3448 2913 + 4220 3783 + 4908 2940 + 2005 4404 + 2053 3109 + 3603 1968 + 2646 2924 + 140 4606 + 2053 4749 + 1654 2117 + 739 2869 + 4747 2752 + 3596 2013 + 1669 1103 + 4195 3315 + 424 1819 + 596 2468 + 1351 431 + 4069 4286 + 3031 261 + 4150 4342 + 2836 2612 + 4994 180 + 1310 4413 + 1229 1028 + 4700 1730 + 4492 1630 + 1835 799 + 4895 2132 + 635 1545 + 4572 2231 + 614 292 + 1299 2409 + 2583 784 + 793 2911 + 1301 3446 + 3933 1539 + 3726 4473 + 49 1365 + 2035 4450 + 4482 65 + 1473 2483 + 2331 547 + 1137 548 + 2150 1323 + 1917 982 + 2756 615 + 1296 1976 + 4094 3125 + 3017 2191 + 2728 1047 + 910 4871 + 626 2180 + 3074 2593 + 1940 1582 + 2564 2213 + 3189 3903 + 2880 2666 + 4592 4591 + 4695 3268 + 2499 1999 + 2899 1458 + 528 3849 + 4416 590 + 2751 2320 + 4829 405 + 1068 4348 + 2015 2412 + 3161 4066 + 2210 1613 + 4482 633 + 2011 3935 + 2173 1742 + 2478 3472 + 152 3465 + 305 1672 + 4172 3751 + 3936 883 + 3596 4512 + 1690 4220 + 3886 4575 + 3276 4822 + 4605 4183 + 2590 4607 + 1182 133 + 2527 467 + 4308 3365 + 631 2208 + 4990 978 + 4975 1008 + 3584 3522 + 1914 402 + 2945 4376 + 170 4126 + 1849 158 + 952 2322 + 2466 3967 + 301 2426 + 1080 2415 + 2941 2859 + 3180 1821 + 2978 2701 + 1352 1448 + 4960 4899 + 4695 3131 + 1686 1473 + 4658 2465 + 3941 4131 + 1622 3683 + 4671 3211 + 4747 529 + 832 3339 + 2396 2685 + 1764 2532 + 4149 1213 + 2221 2640 + 4279 2695 + 2165 4676 + 3731 3417 + 792 610 + 1081 3682 + 438 2044 + 2449 2352 + 4463 3461 + 3110 1392 + 2931 4447 + 3936 315 + 1973 1845 + 2037 1696 + 3000 2682 + 4925 4950 + 809 843 + 4872 893 + 753 4409 + 3098 2026 + 918 1867 + 795 2676 + 3410 3733 + 4634 3443 + 4153 2953 + 3033 2844 + 371 1608 + 3508 2423 + 4415 3530 + 3187 1180 + 3804 3806 + 802 1298 + 3552 974 + 4113 937 + 1563 270 + 4198 2681 + 992 1351 + 289 2226 + 3101 4801 + 580 748 + 394 2004 + 2903 929 + 2237 4569 + 4433 4219 + 4122 4473 + 4700 965 + 2373 2663 + 3051 1223 + 861 500 + 4229 242 + 3024 4311 + 2205 21 + 3985 3170 + 3467 2804 + 1750 1960 + 397 137 + 2243 2992 + 3674 2064 + 880 4019 + 203 1299 + 2621 2278 + 2232 1856 + 455 1074 + 4663 1065 + 587 4960 + 3058 2237 + 1494 3026 + 1365 4613 + 2186 4897 + 4278 966 + 4594 3274 + 3553 3006 + 3146 1716 + \. + + \set ECHO all + RESET client_min_messages; + + -- + -- Test getfdr + -- + SELECT getfdr('t1,t2,t3'); + + -- + -- Test fulldisjunction + -- + SELECT * FROM fulldisjunction('t1,t2,t3') AS RECORD (a0 int4,a1 int4,a2 int4) ORDER BY a0, a1, a2; + diff -crN pgsql/contrib/fulldisjunctions/tset.c pgsql-fd/contrib/fulldisjunctions/tset.c *** pgsql/contrib/fulldisjunctions/tset.c 1969-12-31 19:00:00.000000000 -0500 --- pgsql-fd/contrib/fulldisjunctions/tset.c 2006-07-29 20:54:13.000000000 -0400 *************** *** 0 **** --- 1,1002 ---- + /* + * Copyright (c) 2006 Itzhak Fadida. All Rights Reserved. + * See the README file for a detailed BSD License. + * This file and all related files are under the BSD license. + * */ + + #include "algstructs.h" + #include "tset.h" + #include "tsetfuncs.h" + #include "algutils.h" + #include "queues.h" + #include "queuesfuncs.h" + void + freeTSet(alg_fctx * fctx, TSet tset) + { + if (tset->t == NULL) + { + int i; + + for (i = 0; i < NUMATT; i++) + if (tset->v[i] != (Datum) NULL) + myDatumFree(tset->v[i], fctx->tupleSetDesc->attrs[i]->attbyval, + fctx->tupleSetDesc->attrs[i]->attlen); + } + else + heap_freetuple(tset->t); + if (tset->v != NULL) + { + pfree(tset->v); + pfree(tset->n); + } + pfree(tset); + } + + TSet + newEmptyTSet(alg_fctx * fctx) + { + TSet tset = ((TSet) palloc(sizeof(deformedTSet))); + bytea *b = (bytea *) palloc(VARHDRSZ); + + VARATT_SIZEP(b) = VARHDRSZ; + tset->v = NULL; + tset->n = NULL; + Datum tsetVals[NUMATT]; + char tsetNulls[NUMATT]; + int i; + + for (i = FIRSTATT; i < NUMATT; i++) + tsetNulls[i] = 'n'; + tsetNulls[LABELS] = ' '; + tsetVals[LABELS] = (Datum) b; + tset->t = heap_formtuple(fctx->tupleSetDesc, tsetVals, tsetNulls); + tset->size = tupleSize(tset->t); + bool isnull = false; + + tset->tids = (bytea *) fastgetattr(tset->t, LABELS_ALIGNED, fctx->tupleSetDesc, &isnull); + return tset; + } + Datum + setTSetValue(alg_fctx * fctx, TSet tset, Datum value, int position) + { + if ((tset->v[position] != (Datum) NULL) && (tset->t == NULL)) + { + myDatumFree(tset->v[position], fctx->tupleSetDesc->attrs[position]->attbyval, + fctx->tupleSetDesc->attrs[position]->attlen); + tset->size -= datumGetSize(tset->v[position], fctx->tupleSetDesc->attrs[position]->attbyval, + fctx->tupleSetDesc->attrs[position]->attlen); + } + tset->v[position] = myDatumCopy(value, fctx->tupleSetDesc->attrs[position]->attbyval, + fctx->tupleSetDesc->attrs[position]->attlen); + tset->size += datumGetSize(value, fctx->tupleSetDesc->attrs[position]->attbyval, + fctx->tupleSetDesc->attrs[position]->attlen); + return tset->v[position]; + } + Datum + setTSetValueNoCopy(alg_fctx * fctx, TSet tset, Datum value, int position) + { + if ((tset->v[position] != (Datum) NULL) && (tset->t == NULL)) + { + myDatumFree(tset->v[position], fctx->tupleSetDesc->attrs[position]->attbyval, + fctx->tupleSetDesc->attrs[position]->attlen); + tset->size -= datumGetSize(tset->v[position], fctx->tupleSetDesc->attrs[position]->attbyval, + fctx->tupleSetDesc->attrs[position]->attlen); + } + tset->v[position] = value; + tset->size += datumGetSize(value, fctx->tupleSetDesc->attrs[position]->attbyval, + fctx->tupleSetDesc->attrs[position]->attlen); + return tset->v[position]; + } + + TSet + newTSet_(alg_fctx * fctx) + { + TSet newtset = (TSet) palloc(sizeof(deformedTSet)); + + newtset->t = NULL; + newtset->size = 0; + newtset->v = (Datum *) palloc(NUMATT * sizeof(Datum)); + newtset->n = (char *) palloc(NUMATT * sizeof(char)); + int i = 0; + + for (i = 0; i < NUMATT; i++) + { + newtset->v[i] = (Datum) NULL; + newtset->n[i] = 'n'; + } + newtset->tids = NULL; + return newtset; + } + + DTuple + newDTuple(alg_fctx * fctx, int numAtt) + { + DTuple tuple = (DTuple) palloc(sizeof(deformedTuple)); + + tuple->t = NULL; + tuple->deformed = false; + tuple->v = (Datum *) palloc((numAtt + DTupleTupleHeaderSize) * sizeof(Datum)); + tuple->n = (char *) palloc((numAtt + DTupleTupleHeaderSize) * sizeof(char)); + return tuple; + } + bool + tsetAttIsNull(TSet tset, int pos) + { + if (tset->v != NULL) + return (tset->n[pos] == 'n'); + else + return heap_attisnull(tset->t, pos + 1); + } + + TSet + newTSet(alg_fctx * fctx, HeapTuple tupleTSet) + { + TSet newtset = (TSet) palloc(sizeof(deformedTSet)); + + newtset->size = tupleSize(tupleTSet); + newtset->t = tupleTSet; + newtset->v = (Datum *) palloc(NUMATT * sizeof(Datum)); + newtset->n = (char *) palloc(NUMATT * sizeof(char)); + heap_deformtuple(tupleTSet, fctx->tupleSetDesc, newtset->v, newtset->n); + newtset->tids = (bytea *) newtset->v[LABELS]; + return newtset; + } + + TSet + newTSet___(alg_fctx * fctx, HeapTuple tupleTSet) + { + TSet newtset = (TSet) palloc(sizeof(deformedTSet)); + + newtset->size = tupleSize(tupleTSet); + newtset->t = tupleTSet; + newtset->v = NULL; + newtset->n = NULL; + bool isnull; + + newtset->tids = (bytea *) fastgetattr(tupleTSet, LABELS_ALIGNED, fctx->tupleSetDesc, &isnull); + return newtset; + } + + TSet + newTSet____(alg_fctx * fctx) + { + TSet newtset = (TSet) palloc(sizeof(deformedTSet)); + + newtset->size = 0; + newtset->t = NULL; + newtset->v = NULL; + newtset->n = NULL; + newtset->tids = NULL; + return newtset; + } + char * + printTSetToCStr(alg_fctx * fctx, bytea *b) + { + int numSets = numOfTuplesInTSet(fctx, b); + char *tsetStr; + + if (numSets > 0) + { + int i; + + tsetStr = palloc(1600 * sizeof(char)); + char *to = tsetStr; + ItemPointerData *ctid = palloc(sizeof(ItemPointerData)); + + for (i = 0; i < numSets; i++) + { + memcpy(ctid, VARDATA(b) + i * (sizeof(ItemPointerData) + 1) + 1, sizeof(ItemPointerData)); + char tempStr[100]; + + sprintf(tempStr, "[TRID:%d, ROWID:%d,%d,%d]" + ,getTableIdOfRelsOidInTSet(fctx, b, i), ctid->ip_blkid.bi_hi, + ctid->ip_blkid.bi_lo, ctid->ip_posid); + to = (char *) stpcpy(to, tempStr); + } + pfree(ctid); + } + else + { + tsetStr = palloc(8 * sizeof(char)); + char *to = tsetStr; + + to = (char *) stpcpy(to, "[]"); + } + return tsetStr; + } + void + printTSet(alg_fctx * fctx, HeapTuple tset) + { + if (tset == NULL) + elog(ERROR, "tset in printTSet was NULL!"); + Datum values[NUMATT]; + char nulls[NUMATT]; + + heap_deformtuple(tset, fctx->tupleSetDesc, values, nulls); + bytea *b = (bytea *) values[LABELS]; + char *tsetStr = printTSetToCStr(fctx, b); + bool tofree = true; + int bufSize = tupleSize(tset); + char *buf = (char *) palloc(bufSize); + char *to = buf; + + buf = addAndExpandStringBy(buf, &bufSize, tsetStr, BLCKSZ, &to, &tofree); + pfree(tsetStr); + int i = 0; + + for (i = FIRSTATT; i < fctx->tupleSetNatt; i++) + if (nulls[i] == ' ') + { + buf = addAndExpandStringBy(buf, &bufSize, ",", BLCKSZ, &to, &tofree); + buf = addAndExpandStringBy(buf, &bufSize, SPI_getvalue(tset, fctx->tupleSetDesc, i + 1) + ,BLCKSZ, &to, &tofree); + } + else + buf = addAndExpandStringBy(buf, &bufSize, ", NULL", BLCKSZ, &to, &tofree); + /* PRINT TO SCREEN HERE (DON'T DELETE!!). */ + elog(INFO, "%s", buf); + if (tofree) + pfree(buf); + } + void + printDTSet(alg_fctx * fctx, TSet tset) + { + if (tset == NULL) + elog(ERROR, "tset in printTSet was NULL!"); + Datum *values; + char *nulls; + + values = tset->v; + nulls = tset->n; + bytea *b = (bytea *) values[LABELS]; + char *tsetStr = printTSetToCStr(fctx, b); + bool tofree = true; + int bufSize = 10 * (tset->size + 1); + char *buf = (char *) palloc(bufSize); + char *to = buf; + + buf = addAndExpandStringBy(buf, &bufSize, tsetStr, BLCKSZ, &to, &tofree); + pfree(tsetStr); + int i = 0; + char value[1000]; + + for (i = FIRSTATT; i < fctx->tupleSetNatt; i++) + if (nulls[i] == ' ') + { + buf = addAndExpandStringBy(buf, &bufSize, ",", BLCKSZ, &to, &tofree); + sprintf(value, "%d", (int) values[i]); + buf = addAndExpandStringBy(buf, &bufSize, value + ,BLCKSZ, &to, &tofree); + } + else + buf = addAndExpandStringBy(buf, &bufSize, ", NULL", BLCKSZ, &to, &tofree); + /* PRINT TO SCREEN HERE (DON'T DELETE!!). */ + elog(INFO, "%s", buf); + if (tofree) + pfree(buf); + } + void + printDTuple(alg_fctx * fctx, DTuple dtuple, int tupleRelID) + { + if (dtuple == NULL) + elog(ERROR, "dtuple in printTSet was NULL!"); + Datum *values = dtuple->v; + char *nulls = dtuple->n; + bool tofree = true; + int bufSize = 256 * sizeof(char); + char *buf = (char *) palloc(bufSize); + char *to = buf; + int i = 0; + char value[1000]; + + sprintf(value, "RelID[%d]", tupleRelID); + buf = addAndExpandStringBy(buf, &bufSize, value, BLCKSZ, &to, &tofree); + for (i = 0; i < fctx->relsNAtt[tupleRelID]; i++) + if (nulls[i] == ' ') + { + buf = addAndExpandStringBy(buf, &bufSize, ",", BLCKSZ, &to, &tofree); + sprintf(value, "%d", (int) values[i]); + buf = addAndExpandStringBy(buf, &bufSize, value + ,BLCKSZ, &to, &tofree); + } + else + buf = addAndExpandStringBy(buf, &bufSize, ", NULL", BLCKSZ, &to, &tofree); + /* PRINT TO SCREEN HERE (DON'T DELETE!!). */ + elog(INFO, "%s", buf); + if (tofree) + pfree(buf); + } + + /* + * Creates a bytea containing a the set of Rowids of the tuple set. + * including the tableOidinRelsOID preceding each one. + * we use one byte for each tableOidinRelsOID i.e there could be only + * 256 tables (more than enough). + * remember to FREE the returned value! + */ + bytea * + createNewTSetRowIDs(alg_fctx * fctx, ItemPointer tid, int tupleInRelsOid) + { + bytea *b = palloc(VARHDRSZ + 1 + sizeof(ItemPointerData)); + + VARATT_SIZEP(b) = 1 + sizeof(ItemPointerData) + VARHDRSZ; + VARDATA(b)[0] = (char) tupleInRelsOid; + memcpy(VARDATA(b) + 1, tid, sizeof(ItemPointerData)); + return b; + } + bytea * + addRowIDtoTSet__(alg_fctx * fctx, bytea *baseSet, bytea *setContainingTRID + ,int tupleInRelsOid) + { + int i = 0; + int SCTRIDnumTSets = numOfTuplesInTSet(fctx, setContainingTRID); + int SCTRIDpos = -1; + + for (i = 0; i < SCTRIDnumTSets; i++) + if (tupleInRelsOid == getTableIdOfRelsOidInTSet(fctx, setContainingTRID, i)) + { + SCTRIDpos = i; + break; + } + if (SCTRIDpos < 0) + elog(ERROR, "Incorrect input in addRowIDtoTSet__"); + int biggerPosition = -1; + int numTSets = numOfTuplesInTSet(fctx, baseSet); + int relID = -1; + + for (i = 0; i < numTSets; i++) + { + relID = getTableIdOfRelsOidInTSet(fctx, baseSet, i); + if (relID == tupleInRelsOid) + { + bytea *sameb = palloc(VARATT_SIZEP(baseSet)); + + memcpy(sameb, baseSet, VARATT_SIZEP(baseSet)); + return sameb; + } + else if (relID > tupleInRelsOid) + { + biggerPosition = i; + break; + } + } + if (biggerPosition < 0) + biggerPosition = numTSets + 1; + else + biggerPosition++; + bytea *outb = palloc(VARATT_SIZEP(baseSet) + 1 + sizeof(ItemPointerData)); + + memcpy(outb, baseSet, VARHDRSZ + (biggerPosition - 1) * (1 + sizeof(ItemPointerData))); + VARDATA(outb)[(biggerPosition - 1) * (1 + sizeof(ItemPointerData))] = (char) tupleInRelsOid; + memcpy(VARDATA(outb) + (biggerPosition - 1) * (1 + sizeof(ItemPointerData)) + 1 + ,VARDATA(setContainingTRID) + SCTRIDpos * (1 + sizeof(ItemPointerData)) + 1 + ,sizeof(ItemPointerData)); + memcpy(VARDATA(outb) + (biggerPosition) * (1 + sizeof(ItemPointerData)) + ,VARDATA(baseSet) + (biggerPosition - 1) * (1 + sizeof(ItemPointerData)) + ,VARATT_SIZEP(baseSet) - VARHDRSZ - (biggerPosition - 1) * (1 + sizeof(ItemPointerData))); + VARATT_SIZEP(outb) += 1 + sizeof(ItemPointerData); + return outb; + } + bytea * + addRowIDtoTSet_(alg_fctx * fctx, bytea *b, ItemPointer tid, int tupleInRelsOid) + { + int i = 0; + int biggerPosition = -1; + int numTSets = numOfTuplesInTSet(fctx, b); + int relID = -1; + + for (i = 0; i < numTSets; i++) + { + relID = getTableIdOfRelsOidInTSet(fctx, b, i); + if (relID == tupleInRelsOid) + { + bytea *sameb = palloc(VARATT_SIZEP(b)); + + memcpy(sameb, b, VARATT_SIZEP(b)); + return sameb; + } + else if (relID > tupleInRelsOid) + { + biggerPosition = i; + break; + } + } + if (biggerPosition < 0) + biggerPosition = numTSets + 1; + else + biggerPosition++; + bytea *outb = palloc(VARATT_SIZEP(b) + 1 + sizeof(ItemPointerData)); + + memcpy(outb, b, VARHDRSZ + (biggerPosition - 1) * (1 + sizeof(ItemPointerData))); + VARDATA(outb)[(biggerPosition - 1) * (1 + sizeof(ItemPointerData))] = (char) tupleInRelsOid; + memcpy(VARDATA(outb) + (biggerPosition - 1) * (1 + sizeof(ItemPointerData)) + 1 + ,tid, sizeof(ItemPointerData)); + memcpy(VARDATA(outb) + (biggerPosition) * (1 + sizeof(ItemPointerData)) + ,VARDATA(b) + (biggerPosition - 1) * (1 + sizeof(ItemPointerData)) + ,VARATT_SIZEP(b) - VARHDRSZ - (biggerPosition - 1) * (1 + sizeof(ItemPointerData))); + VARATT_SIZEP(outb) += 1 + sizeof(ItemPointerData); + return outb; + } + bytea * + addRowIDtoTSet(alg_fctx * fctx, TSet tset, ItemPointer tid, int tupleInRelsOid) + { + return ((bytea *) addRowIDtoTSet_(fctx, tset->tids + ,tid, tupleInRelsOid)); + } + bytea * + mergeRowIDs(alg_fctx * fctx, bytea *bLeft, bytea *bRight) + { + bytea *tempOutb = palloc(VARATT_SIZEP(bLeft) + VARATT_SIZEP(bRight) - VARHDRSZ); + int maxl = numOfTuplesInTSet(fctx, bLeft); + int maxr = numOfTuplesInTSet(fctx, bRight); + int l = 0, + r = 0; + int lTID = -1, + rTID = -1; + int pos = 0; + + while (true) + { + lTID = getTableIdOfRelsOidInTSet(fctx, bLeft, l); + rTID = getTableIdOfRelsOidInTSet(fctx, bRight, r); + if (lTID < rTID) + { + memcpy(VARDATA(tempOutb) + pos * (1 + sizeof(ItemPointerData)) + ,VARDATA(bLeft) + l * (1 + sizeof(ItemPointerData)), (1 + sizeof(ItemPointerData))); + l++; + } + else + { + memcpy(VARDATA(tempOutb) + pos * (1 + sizeof(ItemPointerData)) + ,VARDATA(bRight) + r * (1 + sizeof(ItemPointerData)), (1 + sizeof(ItemPointerData))); + if (lTID == rTID) + { + r++; + l++; + } + else + r++; + } + pos++; + if ((l == maxl) && (r == maxr)) + { + break; + } + else if (l == maxl) + { + memcpy(VARDATA(tempOutb) + pos * (1 + sizeof(ItemPointerData)) + ,VARDATA(bRight) + r * (1 + sizeof(ItemPointerData)) + ,VARATT_SIZEP(bRight) - VARHDRSZ - r * (1 + sizeof(ItemPointerData))); + pos += maxr - r; + break; + } + else if (r == maxr) + { + memcpy(VARDATA(tempOutb) + pos * (1 + sizeof(ItemPointerData)) + ,VARDATA(bLeft) + l * (1 + sizeof(ItemPointerData)) + ,VARATT_SIZEP(bLeft) - VARHDRSZ - l * (1 + sizeof(ItemPointerData))); + pos += maxl - l; + break; + } + } + VARATT_SIZEP(tempOutb) = VARHDRSZ + pos * (1 + sizeof(ItemPointerData)); + repalloc(tempOutb, VARATT_SIZEP(tempOutb)); + return tempOutb; + } + bool + areTSetsEqual(alg_fctx * fctx, TSet tset1, TSet tset2) + { + if (VARATT_SIZEP(tset1->tids) != VARATT_SIZEP(tset2->tids)) + return false; + return (memcmp(tset1->tids, tset2->tids, VARATT_SIZEP(tset1->tids)) == 0); + } + bool + isLeftSubsumedRightTset(alg_fctx * fctx, TSet left, TSet right) + { + bytea *bLeft = left->tids; + bytea *bRight = right->tids; + + if (VARATT_SIZEP(bLeft) > VARATT_SIZEP(bRight)) + return false; + int i = 0; + int leftPos = 0; + int leftRelOid = 0; + int rightRelOid = 0; + int numLeftTuples = numOfTuplesInTSet(fctx, bLeft); + int numRightTuples = numOfTuplesInTSet(fctx, bRight); + + leftRelOid = getTableIdOfRelsOidInTSet(fctx, bLeft, leftPos); + for (i = 0; i < numRightTuples; i++) + { + rightRelOid = getTableIdOfRelsOidInTSet(fctx, bRight, i); + if (leftRelOid == rightRelOid && (memcmp(VARDATA(bLeft) + leftPos * (1 + sizeof(ItemPointerData)) + ,VARDATA(bRight) + i * (1 + sizeof(ItemPointerData)), 1 + (sizeof(ItemPointerData))) == 0)) + { + leftPos++; + if (leftPos == numLeftTuples) + return true; + leftRelOid = getTableIdOfRelsOidInTSet(fctx, bLeft, leftPos); + } + } + return false; + } + bool + heap_deformtuple_iterative(HeapTuple tuple, + TupleDesc tupleDesc, + Datum *values, + char *nulls, deformTupleIterativeState * ds, + int tillAttNum, bool finishAll) + { + if (ds->firstIteration) + { + ds->firstIteration = false; + ds->tup = tuple->t_data; + ds->att = tupleDesc->attrs; + ds->tdesc_natts = tupleDesc->natts; + /* ptr to null bitmask in tuple */ + ds->bp = ds->tup->t_bits; + /* can we use/set attcacheoff? */ + ds->slow = false; + ds->natts = ds->tup->t_natts; + + /* + * In inheritance situations, it is possible that the given tuple + * tually has more fields than the caller is expecting. Don't run the + * end of the caller's arrays. + */ + ds->natts = Min(ds->natts, ds->tdesc_natts); + ds->tp = (char *) ds->tup + ds->tup->t_hoff; + ds->off = 0; + ds->attnum = 0; + } + for (; ds->attnum < ds->natts; ds->attnum++) + { + if (HeapTupleHasNulls(tuple) && att_isnull(ds->attnum, ds->bp)) + { + values[ds->attnum] = (Datum) 0; + nulls[ds->attnum] = 'n'; + /* can't use attcacheoff anymore */ + ds->slow = true; + if (!finishAll && ds->attnum >= tillAttNum) + { + ds->attnum++; + if (ds->attnum < ds->natts) + return true; + else + return false; + } + else + continue; + } + nulls[ds->attnum] = ' '; + if (!ds->slow && ds->att[ds->attnum]->attcacheoff >= 0) + ds->off = ds->att[ds->attnum]->attcacheoff; + else + { + ds->off = att_align(ds->off, ds->att[ds->attnum]->attalign); + if (!ds->slow) + ds->att[ds->attnum]->attcacheoff = ds->off; + } + values[ds->attnum] = fetchatt(ds->att[ds->attnum], ds->tp + ds->off); + ds->off = att_addlength(ds->off, ds->att[ds->attnum]->attlen, ds->tp + ds->off); + if (ds->att[ds->attnum]->attlen <= 0) + /* can't use attcacheoff anymore */ + ds->slow = true; + if (!finishAll && ds->attnum >= tillAttNum) + { + ds->attnum++; + if (ds->attnum < ds->natts) + return true; + else + return false; + } + } + + /* + * If tuple doesn't have all the atts indicated by tupleDesc, read the est + * as null + */ + for (; ds->attnum < ds->tdesc_natts; ds->attnum++) + { + values[ds->attnum] = (Datum) 0; + nulls[ds->attnum] = 'n'; + if (!finishAll && ds->attnum >= tillAttNum) + { + ds->attnum++; + if (ds->attnum < ds->tdesc_natts) + return true; + else + return false; + } + } + return false; + } + + /* + * Will return null on failure + */ + TSet + JCCTSetAndTupleAndReturnTSet(alg_fctx * fctx, TSet tset, DTuple tuple + ,TupleDesc tupleTupleDesc, int tupleRelID, deformTupleIterativeState * dsTuple) + { + bytea *b = tset->tids; + int numAtts = fctx->relsNAtt[tupleRelID]; + int i = 0; + int curTSetAtt = -1; + + for (i = 0; i < numAtts; i++) + { + curTSetAtt = fctx->relsAttNumsAtTupleSet[tupleRelID][i]; + if ((tset->n[curTSetAtt] == 'n') || (heap_attisnull(tuple->t, i + 1))) + { + if (isResultTupleAttOccursInSomeRelID(fctx, curTSetAtt, b)) + { + return NULL; + } + } + else + { + if (!tuple->deformed) + heap_deformtuple_iterative(tuple->t, tupleTupleDesc, tuple->v, tuple->n, dsTuple, i, false); + if (!areAttributesEqual_RT(fctx, curTSetAtt + ,tset->v[curTSetAtt] + ,tuple->v[i] + )) + { + return NULL; + } + } + } + if (!tuple->deformed) + { + heap_deformtuple_iterative(tuple->t, tupleTupleDesc, tuple->v, tuple->n, dsTuple, -1, true); + tuple->tid = (ItemPointer) tuple->v[numAtts]; + tuple->deformed = true; + } + for (i = 0; i < numAtts; i++) + { + curTSetAtt = fctx->relsAttNumsAtTupleSet[tupleRelID][i]; + if ((tset->n[curTSetAtt] == 'n') && (tuple->n[i] == ' ')) + { + tset->n[curTSetAtt] = ' '; + setTSetValue(fctx, tset, tuple->v[i], curTSetAtt); + } + } + bytea *outb = + (bytea *) addRowIDtoTSet_(fctx, b, tuple->tid, tupleRelID); + + setTSetValueNoCopy(fctx, tset, (Datum) outb, LABELS); + tset->tids = (bytea *) tset->v[LABELS]; + return tset; + } + + /* + * returns null on failure + * */ + TSet + unifyAndJCC(alg_fctx * fctx, TSet leftTSet, Datum *leftTSetVals, char *leftTSetNulls, + TSet rightTSet, RBITS relationsToCheck, RBITS relationsOfLeft, RBITS relationsOfRight) + { + int i = 0; + deformTupleIterativeState dsLeftTSet; + + dsLeftTSet.firstIteration = true; + bool isLeftAttNull, + isRightAttNull; + + for (i = FIRSTATT; i < NUMATT; i++) + { + isLeftAttNull = (leftTSetNulls[i] == 'n'); + isRightAttNull = (rightTSet->n[i] == 'n'); + if (isLeftAttNull && isRightAttNull) + { + if (isResultTupleAttOccursInSomeRelIDWithSpecifiedRelations(fctx, i, + relationsToCheck)) + { + return NULL; + } + } + else if (isLeftAttNull && (!isRightAttNull)) + { + if (isResultTupleAttOccursInSomeRelIDWithSpecifiedRelations(fctx, i, + (relationsToCheck & relationsOfLeft))) + { + return NULL; + } + } + else if ((!isLeftAttNull) && isRightAttNull) + { + if (isResultTupleAttOccursInSomeRelIDWithSpecifiedRelations(fctx, i, + (relationsToCheck & relationsOfRight))) + { + return NULL; + } + } + else + { + if (!areAttributesEqual_RT(fctx, i, leftTSetVals[i], rightTSet->v[i])) + { + return NULL; + } + } + } + for (i = FIRSTATT; i < NUMATT; i++) + { + if ((leftTSetNulls[i] == 'n') && (rightTSet->n[i] == ' ')) + { + leftTSetNulls[i] = ' '; + setTSetValue(fctx, leftTSet, rightTSet->v[i], i); + } + } + bytea *outb = mergeRowIDs(fctx, leftTSet->tids, rightTSet->tids); + + setTSetValueNoCopy(fctx, leftTSet, (Datum) outb, LABELS); + leftTSet->tids = (bytea *) outb; + return leftTSet; + } + + TSet + simpleUnify(alg_fctx * fctx, TSet leftTSet, Datum *leftTSetVals, + char *leftTSetNulls, TSet rightTSet) + { + int i = 0; + + for (i = FIRSTATT; i < NUMATT; i++) + { + if ((leftTSetNulls[i] == 'n') && (rightTSet->n[i] == ' ')) + { + leftTSetNulls[i] = ' '; + setTSetValue(fctx, leftTSet, rightTSet->v[i], i); + } + } + bytea *outb = mergeRowIDs(fctx, leftTSet->tids, rightTSet->tids); + + setTSetValueNoCopy(fctx, leftTSet, (Datum) outb, LABELS); + leftTSet->tids = (bytea *) outb; + return leftTSet; + } + + TSet + create_tuple_set(alg_fctx * fctx, DTuple inBaseTuple + ,TupleDesc baseTupleDesc, int baseTupleInRelsOid) + { + int i; + TSet returnTSet = newTSet_(fctx); + + returnTSet->n[LABELS] = ' '; + for (i = 0; i < fctx->relsNAtt[baseTupleInRelsOid]; i++) + { + if (inBaseTuple->n[i] == ' ') + { + setTSetValue(fctx, returnTSet, inBaseTuple->v[i], fctx->relsAttNumsAtTupleSet[baseTupleInRelsOid][i]); + returnTSet->n[fctx->relsAttNumsAtTupleSet[baseTupleInRelsOid][i]] = ' '; + } + } + bytea *b = createNewTSetRowIDs(fctx, inBaseTuple->tid, baseTupleInRelsOid); + + setTSetValueNoCopy(fctx, returnTSet, (Datum) b, LABELS); + returnTSet->tids = b; + return returnTSet; + } + bool + JCCTupleInTSetAndDTuple(alg_fctx * fctx, DTuple dtuple, int dtupleRelID, + TSet tset, int tupleRelIDInTSet) + { + int dtupleNumAtts = fctx->relsNAtt[dtupleRelID]; + int tsetTupleNumAtts = fctx->relsNAtt[tupleRelIDInTSet]; + int **dtupleAtts = fctx->sortedRelsAttNumsAtTupleSet[dtupleRelID]; + int **tsetTupleAtts = fctx->sortedRelsAttNumsAtTupleSet[tupleRelIDInTSet]; + int i = 0, + j = 0; + + while (true) + { + if (dtupleAtts[i][0] == tsetTupleAtts[j][0]) + { + if ((tset->n[tsetTupleAtts[j][0]] == 'n') || (dtuple->n[dtupleAtts[i][1]] == 'n')) + return false; + if (!areAttributesEqual_RT(fctx, tsetTupleAtts[j][0], tset->v[tsetTupleAtts[j][0]] + ,dtuple->v[dtupleAtts[i][1]])) + { + return false; + } + i++; + j++; + if ((i == dtupleNumAtts) || (j == tsetTupleNumAtts)) + return true; + } + else if (dtupleAtts[i][0] < tsetTupleAtts[j][0]) + { + i++; + if (i == dtupleNumAtts) + return true; + } + else + { + j++; + if (j == tsetTupleNumAtts) + return true; + } + } + } + + TSet + generateAlternativeTupleSet(alg_fctx * fctx, TSet tset, RBITS relsOfTuples, + DTuple dtuple, TupleDesc tupleDesc, int tupleRelID) + { + /* In phase 1 we find all the JCC tuples in dtset with dtuple */ + RBITS toCheckForJCC = 0; + RBITS tmpBits = relsOfTuples; + int i = -1, + j = -1; + + while (tmpBits) + { + i++; + while (tmpBits && !(varNthBitFromLeft(tmpBits, 0))) + { + i++; + tmpBits <<= 1; + } + if (!tmpBits) + break; + else + tmpBits <<= 1; + j++; + if (tupleRelID == i) + { + makeSureDeformedTuple(fctx, dtuple, tupleDesc, tupleRelID); + if (!(memcmp(dtuple->tid, TSET_GET_CTID(tset, j), (CTID_SIZE)))) + { + return NULL; + } + } + } + toCheckForJCC = fctx->bits_scheme_graph[tupleRelID] & relsOfTuples; + if (toCheckForJCC == 0) + return NULL; + + /* + * in phase 2 we add all the tuples that are connected to the tuples that + * were found JCC without the rejected ones in the component. i.e. we + * create a tuple set that is a connected component that contains dtuple. + */ + RBITS tuplesToAddToNewTSet = 0; + RBITS tuplesRejected = 0; + + makeSureDeformedTSet(fctx, tset); + makeSureDeformedTuple(fctx, dtuple, tupleDesc, tupleRelID); + tmpBits = toCheckForJCC; + i = -1; + while (tmpBits) + { + i++; + while (tmpBits && !(varNthBitFromLeft(tmpBits, 0))) + { + i++; + tmpBits <<= 1; + } + if (!tmpBits) + break; + else + tmpBits <<= 1; + if (JCCTupleInTSetAndDTuple(fctx, dtuple, tupleRelID, tset, i)) + varSetNthBitFromLeft(tuplesToAddToNewTSet, i); + else + varSetNthBitFromLeft(tuplesRejected, i); + } + if (tuplesToAddToNewTSet == 0) + return NULL; + varUnSetNthBitFromLeft(tuplesToAddToNewTSet, tupleRelID); + /* find all the rest of the component */ + tmpBits = ~tuplesToAddToNewTSet; + while (tmpBits != tuplesToAddToNewTSet) + { + tmpBits = tuplesToAddToNewTSet; + for (i = 0; i < fctx->numRels; i++) + if ((i != tupleRelID) && (!varNthBitFromLeft(tuplesRejected, i)) + && (varNthBitFromLeft(relsOfTuples, i))) + if (tuplesToAddToNewTSet & fctx->bits_scheme_graph[i]) + varSetNthBitFromLeft(tuplesToAddToNewTSet, i); + } + /* Lets create a new tuple set with the base tuple */ + int curTSetAtt; + int numAtts = fctx->relsNAtt[tupleRelID]; + TSet newTSet = newTSet_(fctx); + + for (i = FIRSTATT; i < NUMATT; i++) + newTSet->n[i] = 'n'; + newTSet->n[LABELS] = ' '; + for (i = 0; i < numAtts; i++) + { + curTSetAtt = fctx->relsAttNumsAtTupleSet[tupleRelID][i]; + if (dtuple->n[i] == ' ') + { + setTSetValue(fctx, newTSet, dtuple->v[i], curTSetAtt); + newTSet->n[curTSetAtt] = ' '; + } + } + /* Lets add the rest of the tuples. */ + int k; + int numTupleInNewTSet = 1; + + varUnSetNthBitFromLeft(tuplesToAddToNewTSet, tupleRelID); + tmpBits = tuplesToAddToNewTSet; + i = -1; + while (tmpBits) + { + i++; + while (tmpBits && !(varNthBitFromLeft(tmpBits, 0))) + { + i++; + tmpBits <<= 1; + } + if (!tmpBits) + break; + else + tmpBits <<= 1; + numTupleInNewTSet++; + numAtts = fctx->relsNAtt[i]; + for (k = 0; k < numAtts; k++) + { + curTSetAtt = fctx->relsAttNumsAtTupleSet[i][k]; + if ((newTSet->n[curTSetAtt] == 'n') && (tset->n[curTSetAtt] == ' ')) + { + newTSet->n[curTSetAtt] = ' '; + setTSetValue(fctx, newTSet, tset->v[curTSetAtt], curTSetAtt); + } + } + } + /* finally lets build the tableID:CTID pairs array. */ + int z = -1; + RBITS tmpRelsOfTuples = relsOfTuples; + + tmpBits = tuplesToAddToNewTSet; + varSetNthBitFromLeft(tmpBits, tupleRelID); + i = -1, j = -1; + bytea *outb = palloc(VARHDRSZ + (numTupleInNewTSet * TABLEID_CTID_SIZE)); + + VARATT_SIZEP(outb) = VARHDRSZ + (numTupleInNewTSet * TABLEID_CTID_SIZE); + while (tmpBits) + { + i++; + if (varNthBitFromLeft(tmpRelsOfTuples, 0)) + z++; + while (tmpBits && !(varNthBitFromLeft(tmpBits, 0))) + { + i++; + tmpBits <<= 1; + tmpRelsOfTuples <<= 1; + if (varNthBitFromLeft(tmpRelsOfTuples, 0)) + z++; + } + if (!tmpBits) + break; + else + { + tmpBits <<= 1; + tmpRelsOfTuples <<= 1; + } + j++; + VARDATA(outb)[j * TABLEID_CTID_SIZE] = (char) i; + if (i == tupleRelID) + memcpy(VARDATA(outb) + (j * TABLEID_CTID_SIZE) + 1 + ,dtuple->tid + ,CTID_SIZE); + else + memcpy(VARDATA(outb) + (j * TABLEID_CTID_SIZE) + 1 + ,VARDATA(tset->tids) + (z * TABLEID_CTID_SIZE) + 1 + ,CTID_SIZE); + } + newTSet->v[LABELS] = (Datum) outb; + newTSet->tids = outb; + return newTSet; + } + HeapTuple + clearValuesFromTSet(alg_fctx * fctx, TSet tset, char *nulls) + { + Datum valuesTSet[1]; + + valuesTSet[0] = (Datum) tset->tids; + return (heap_formtuple(fctx->tupleSetDesc, valuesTSet, nulls)); + } diff -crN pgsql/contrib/fulldisjunctions/tsetfuncs.h pgsql-fd/contrib/fulldisjunctions/tsetfuncs.h *** pgsql/contrib/fulldisjunctions/tsetfuncs.h 1969-12-31 19:00:00.000000000 -0500 --- pgsql-fd/contrib/fulldisjunctions/tsetfuncs.h 2006-07-29 20:54:13.000000000 -0400 *************** *** 0 **** --- 1,118 ---- + /* + * Copyright (c) 2006 Itzhak Fadida. All Rights Reserved. + * See the README file for a detailed BSD License. + * This file and all related files are under the BSD license. + * */ + #ifndef TSETFUNCS_H + #define TSETFUNCS_H + + #ifdef DEBUG + #else + #define NDEBUG + #endif + + #include + + #include "tset.h" + #include "algstructs.h" + #include "utils/palloc.h" + #define numOfTuplesInTSet(fctx, b)\ + ((VARATT_SIZEP(b) - VARHDRSZ) / (1 + sizeof(ItemPointerData))) + #define getTableIdOfRelsOidInTSet(fctx, b, position)\ + ((int) VARDATA(b)[position * (1 + sizeof(ItemPointerData))]) + #define makeSureFormedTSet(fctx,tset)\ + do\ + {\ + if ((tset)->t == NULL)\ + {\ + (tset)->t = heap_formtuple((fctx)->tupleSetDesc, (tset)->v, (tset)->n); \ + freeDatumArray(fctx, (tset)->v);\ + pfree((tset)->v);\ + pfree((tset)->n);\ + (tset)->v = NULL;\ + (tset)->n = NULL;\ + {\ + bool isnull; \ + (tset)->tids = (bytea *) fastgetattr((tset->t), LABELS_ALIGNED, (fctx)->tupleSetDesc, &isnull);\ + } \ + (tset)->size = tupleSize((tset)->t);\ + } \ + } while (0) + + #define makeSureDeformedTSet(fctx,tset)\ + do\ + {\ + if ((tset)->v == NULL)\ + {\ + (tset)->v = (Datum *) palloc(NUMATT * sizeof(Datum));\ + (tset)->n = (char *) palloc(NUMATT * sizeof(char)); \ + heap_deformtuple((tset->t), (fctx)->tupleSetDesc, (tset)->v, (tset)->n);\ + } \ + } while (0) + + #define makeSureDeformedTuple(fctx,tuple,tupleDesc,relID)\ + do\ + {\ + if ((tuple)->deformed == false)\ + {\ + heap_deformtuple((tuple->t), (tupleDesc), (tuple)->v, (tuple)->n);\ + tuple->tid = (ItemPointer) tuple->v[fctx->relsNAtt[relID]];\ + (tuple)->deformed = true;\ + } \ + } while (0) + + #define freeDatumArray(fctx,arr)\ + do\ + {\ + int i;\ + for (i = 0; i < NUMATT; i++)\ + if ((arr)[i] != (Datum) NULL)\ + myDatumFree((arr)[i], (fctx)->tupleSetDesc->attrs[i]->attbyval, \ + (fctx)->tupleSetDesc->attrs[i]->attlen);\ + } while (0) + + #define setTSet(fctx,tset,tupleTSet,isnull)\ + do\ + {\ + (tset)->size = tupleSize((tupleTSet));\ + (tset)->t = (tupleTSet);\ + (tset)->tids = (bytea *) fastgetattr((tupleTSet), LABELS_ALIGNED, (fctx)->tupleSetDesc, &(isnull));\ + } while (0) + + extern bool tsetAttIsNull(TSet tset, int pos); + extern void freeTSet(alg_fctx * fctx, TSet tset); + extern TSet newEmptyTSet(alg_fctx * fctx); + extern Datum setTSetValue(alg_fctx * fctx, TSet tset, Datum value + ,int position); + extern Datum setTSetValueNoCopy(alg_fctx * fctx, TSet tset, Datum value, int position); + extern TSet newTSet_(alg_fctx * fctx); + extern TSet newTSet(alg_fctx * fctx, HeapTuple tset); + extern DTuple newDTuple(alg_fctx * fctx, int numAtt); + extern TSet newTSet___(alg_fctx * fctx, HeapTuple tset); + extern TSet newTSet____(alg_fctx * fctx); + extern char *printTSetToCStr(alg_fctx * fctx, bytea *b); + extern void printTSet(alg_fctx * fctx, HeapTuple tset); + extern void printDTSet(alg_fctx * fctx, TSet tset); + extern void printDTuple(alg_fctx * fctx, DTuple dtuple, int tupleRelID); + extern bytea *createNewTSetRowIDs(alg_fctx * fctx, ItemPointer tid, int tupleInRelsOid); + extern bytea *addRowIDtoTSet__(alg_fctx * fctx, bytea *baseSet, bytea *setContainingTRID + ,int tupleInRelsOid); + extern bytea *addRowIDtoTSet_(alg_fctx * fctx, bytea *b, ItemPointer tid, int tupleInRelsOid); + extern bytea *addRowIDtoTSet(alg_fctx * fctx, TSet tset, ItemPointer tid, int tupleInRelsOid); + extern bytea *mergeRowIDs(alg_fctx * fctx, bytea *bLeft, bytea *bRight); + extern bool areTSetsEqual(alg_fctx * fctx, TSet tset1, TSet tset2); + extern bool isLeftSubsumedRightTset(alg_fctx * fctx, TSet left, TSet right); + extern TSet JCCTSetAndTupleAndReturnTSet(alg_fctx * fctx, TSet tset, DTuple tuple + ,TupleDesc tupleTupleDesc, int tupleRelID, deformTupleIterativeState * dsTuple); + extern TSet unifyAndJCC(alg_fctx * fctx, TSet leftTSet, Datum *leftTSetVals, + char *leftTSetNulls, TSet rightTSet, RBITS relationsToCheck, + RBITS relationsOfLeft, RBITS relationsOfRight); + extern TSet simpleUnify(alg_fctx * fctx, TSet leftTSet, Datum *leftTSetVals, + char *leftTSetNulls, TSet rightTSet); + extern TSet create_tuple_set(alg_fctx * fctx, DTuple inBaseTuple + ,TupleDesc baseTupleDesc, int baseTupleInRelsOid); + extern TSet generateAlternativeTupleSet(alg_fctx * fctx, TSet tset, RBITS relsOfTuples, + DTuple dtuple, TupleDesc tupleDesc, int tupleRelID); + extern HeapTuple clearValuesFromTSet(alg_fctx * fctx, TSet tset, char *nulls); + + #endif /* TSETFUNCS_H */ diff -crN pgsql/contrib/fulldisjunctions/tset.h pgsql-fd/contrib/fulldisjunctions/tset.h *** pgsql/contrib/fulldisjunctions/tset.h 1969-12-31 19:00:00.000000000 -0500 --- pgsql-fd/contrib/fulldisjunctions/tset.h 2006-07-29 20:54:13.000000000 -0400 *************** *** 0 **** --- 1,73 ---- + /* + * Copyright (c) 2006 Itzhak Fadida. All Rights Reserved. + * See the README file for a detailed BSD License. + * This file and all related files are under the BSD license. + * */ + + #ifndef TSET_H + #define TSET_H + + #ifdef DEBUG + #else + #define NDEBUG + #endif + + #include + + #include "postgres.h" + #include "utils/palloc.h" + #include "funcapi.h" + #define LABELS 0 + #define LABELS_ALIGNED 1 + /* first attribute */ + #define FIRSTATT 1 + #define LASTATT (fctx->tupleSetNatt-1) + #define NUMATT (fctx->tupleSetNatt) + #define CTID_SIZE sizeof(ItemPointerData) + #define TABLEID_CTID_SIZE (1+CTID_SIZE) + typedef struct + { + int size; + /* tuple ids. TID or TID AND ROWID. */ + bytea *tids; + HeapTuple t; + /* values */ + Datum *v; + /* nulls */ + char *n; + } deformedTSet; + typedef deformedTSet *TSet; + + #define TSET_GET_CTID(tset,relative_pos) VARDATA(tset->tids)+relative_pos*(TABLEID_CTID_SIZE)+1 + #define DTupleTupleHeaderSize 1 + typedef struct + { + HeapTuple t; + /* values */ + Datum *v; + /* nulls */ + char *n; + ItemPointer tid; + bool deformed; + } deformedTuple; + typedef deformedTuple *DTuple; + typedef struct + { + HeapTupleHeader tup; + Form_pg_attribute *att; + int tdesc_natts; + /* number of atts to extract */ + int natts; + int attnum; + /* ptr to tuple data */ + char *tp; + /* offset in tuple data */ + long off; + /* ptr to null bitmask in tuple */ + bits8 *bp; + /* can we use/set attcacheoff? */ + bool slow; + bool firstIteration; + } deformTupleIterativeState; + + #endif /* TSET_H */ diff -crN pgsql/contrib/fulldisjunctions/uninstall_fulldisjunctions.sql pgsql-fd/contrib/fulldisjunctions/uninstall_fulldisjunctions.sql *** pgsql/contrib/fulldisjunctions/uninstall_fulldisjunctions.sql 1969-12-31 19:00:00.000000000 -0500 --- pgsql-fd/contrib/fulldisjunctions/uninstall_fulldisjunctions.sql 2006-07-30 15:52:03.000000000 -0400 *************** *** 0 **** --- 1,13 ---- + /* + * Uninstall SQL Script for Full Disjunctions + */ + SET search_path = public; + DROP FUNCTION fulldisjunction(text); + DROP FUNCTION fulldisjunction(text,text); + DROP FUNCTION fulldisjunction(text,text,boolean); + DROP FUNCTION fulldisjunction(text,text,boolean,boolean); + DROP FUNCTION fulldisjunction(text,text,boolean,boolean,text); + DROP FUNCTION fulldisjunction(text,text,boolean,boolean,text,int); + DROP FUNCTION odmbfd(text,text,boolean,boolean,text,int); + DROP FUNCTION getfdr(text); + DROP FUNCTION getfdr(text,text); diff -crN pgsql/contrib/Makefile pgsql-fd/contrib/Makefile *** pgsql/contrib/Makefile 2006-05-30 09:25:57.000000000 -0400 --- pgsql-fd/contrib/Makefile 2006-07-30 16:11:35.000000000 -0400 *************** *** 13,18 **** --- 13,19 ---- dblink \ dbmirror \ earthdistance \ + fulldisjunctions \ fulltextindex \ fuzzystrmatch \ intagg \