// top docid info

m_q = NULL;

m_topDocIdPtrs2 = NULL;

m_topScores2 = NULL;

m_topExplicits2 = NULL;

m_topHardCounts2= NULL;

m_buf = NULL;

m_bigBuf = NULL;

reset();

m_initialized = false;

m_numTiers = 0;

//m_alreadySet = false;

m_estimatedTotalHits = -1;

m_doRecall = true;

// filterTopDocIds is now in msg3a, and so we need to init some stuff

// or else it cores when addlists2_r is not executed.

for ( int32_t i = 0; i < MAX_TIERS; i++ ){

m_numTopDocIds[i] = 0;

m_numExactExplicitMatches[i] = 0;

m_numExactImplicitMatches[i] = 0;

}

freeMem();

bool requireAllTerms , TopTree *topTree ) {

// bail if already initialized

if ( m_initialized ) return;

// clear everything

reset();

// we are now

m_initialized = true;

// set debug flag

m_isDebug = isDebug;

// list heads are not swapped yet

for ( int32_t i = 0 ; i < q->getNumTerms() ; i++ )

// loop over all lists in this term's tiers

for ( int32_t j = 0 ; j < MAX_TIERS ; j++ )

m_swapped[j][i] = false;

// . are we default AND? it is much faster.

// . using ~/queries/queries.X.rex on rex:

// . 81q/s raw=8&sc=0&dr=0&rat=1 sum = 288.0 avg = 0.3 sdev = 0.5

// . 70q/s raw=8&sc=1&dr=1&rat=1 sum = 185.0 avg = 0.4 sdev = 0.5

// . -O2 sum = 204.00 avg = 0.15 sdev = 0.26

// . 45q/s raw=8&sc=0&dr=0&rat=0 sum = 479.0 avg = 1.1 sdev = 1.1

// . 38q/s raw=8&sc=1&dr=1&rat=0 sum = 429.0 avg = 1.2 sdev = 1.2

// . -O2 raw=8&sc=0&dr=0&rat=0 sum = 351.00 avg = 0.60 sdev = 0.69

// . speed up mostly from not having to look up as many title recs?

// . the Msg39 reported time to intersect is 4 times higher for rat=0

// . grep "intersected lists took" rat1 | awk '{print $8}' | add

// . do this on host0c for speed testing:

// ?q=windows+2000+server+product+key&usecache=0&debug=1&rat=1

m_requireAllTerms = requireAllTerms;

// make sure our max score isn't too big

//int32_t a = MAX_QUERY_TERMS * MAX_QUERY_TERMS * 300 * 255 + 255;

//int64_t aa=MAX_QUERY_TERMS * MAX_QUERY_TERMS * 300LL * 255LL + 255;

//if ( a != aa ) {

//log("IndexTable::set: MAX_QUERY_TERMS too big"); exit(-1); }

// save it

m_topTree = topTree;

//g_topTree = topTree;

// . HACK: we must always get the top 500 results for now

// . so next results page doesn't have same results as a previous page

// . TODO: refine this

// . this is repeated in IndexReadInfo.cpp

// . HACK: this prevents dups when clicking "Next X Results" link

//if ( docsWanted < 500 ) docsWanted = 500;

// remember the query class, it has all the info about the termIds

m_q = q;

// just a int16_t cut

m_componentCodes = m_q->m_componentCodes;

// for debug msgs

m_logstate = (int32_t)logstate;

// after this many docids for a term, we start dropping some

//int32_t truncLimit = g_indexdb.getTruncationLimit();

// . set score weight for each term based on termFreqs

// . termFreqs is just the max size of an IndexList

setScoreWeights ( m_q );

// . HACK: date hack

// . set termSigns of the special date termIds to 'd' so addList()

// knows to throw these scores into the highest tier (just for them)

// . also re-set the weights so the most significant 8-bits of our

// 16-bit date is weighted by 256, and the low by 1

/*

// set weights for phrases and singletons independently

setScoreWeights ( q , true );

setScoreWeights ( q , false );

// get an estimate on # of docs in the database

//int64_t numDocs = g_titledb.getGlobalNumDocs();

// this should only be zero if we have 0 docs, so make it 1 if so

//if ( numDocs <= 0 ) numDocs = 1;

// . compute the total termfreqs

// . round small termFreqs up to half a GB_PAGE_SIZE

double minFreq = 0x7fffffffffffffffLL;

for ( int32_t i = 0 ; i < q->getNumTerms() ; i++ ) {

// ignore termIds we should

//if ( q->m_ignore[i] ) continue;

// component lists are merged into one compound list

if ( m_componentCodes[i] >= 0 ) continue;

// . if we're setting phrases, it must be an UNQUOTED phrase

// . quoted phrases have a term sign!

if ( phrases ) {

if ( q->isInQuotes (i) ) continue;

if ( ! q->isPhrase (i) ) continue;

if ( q->getTermSign(i) != '\0' ) continue;

}

else if ( ! q->isInQuotes (i) &&

q->isPhrase (i) &&

q->getTermSign(i) == '\0' )

continue;

// is this the new min?

if ( q->getTermFreq(i) < minFreq ) minFreq = q->getTermFreq(i);

}

// to balance things out don't allow minFreq below "absMin"

double absMin = GB_PAGE_SIZE/(2*sizeof(key_t));

if ( minFreq < absMin ) minFreq = absMin;

// loop through each term computing the score weight for it

for ( int32_t i = 0 ; i < q->getNumTerms() ; i++ ) {

// reserve half the weight for up to 4 plus signs

//int64_t max = MAX_SCORE_WEIGHT / 3;

// i eliminated the multi-plus thing

//int64_t max = MAX_SCORE_WEIGHT ;

// . 3 extra plusses can triple the score weight

// . each extra plus adds "extra" to the score weight

//int32_t extra = (2 * MAX_SCORE_WEIGHT) / 9;

// add 1/6 for each plus over 1

//if ( q->m_numPlusses[i] > 0 )

// max += (q->m_numPlusses[i] - 1) * extra;

// but don't exceed the absolute max

//if ( max > MAX_SCORE_WEIGHT ) max = MAX_SCORE_WEIGHT;

// ignore termIds we should

//if ( q->m_ignore[i] ) { m_scoreWeights[i] = 0; continue; }

// component lists are merged into one compound list

if ( m_componentCodes[i] >= 0 ) continue;

// if we're setting phrases, it must be a phrase

if ( phrases ) {

if ( q->isInQuotes (i) ) continue;

if ( ! q->isPhrase (i) ) continue;

if ( q->getTermSign(i) != '\0' ) continue;

}

else if ( ! q->isInQuotes (i) &&

q->isPhrase (i) &&

q->getTermSign(i) == '\0' )

continue;

// increase small term freqs to the minimum

double freq = q->getTermFreq(i);

if ( freq < absMin ) freq = absMin;

// get ratio into [1,inf)

double ratio1 = 2.71828 * freq / minFreq; // R1

// . natural log it

// . gives a x8 whereas log10 would give a x4 for a wide case

double ratio2 = log ( ratio1 ); // R2

// square

// ratio = ratio * ratio;

// make bigger now for '"warriors of freedom" game' query

// so it weights 'game' less

//double ratio3 = pow ( ratio2 , 2.6 ); // R3

double ratio3 = pow ( ratio2, (double)g_conf.m_queryExp );// R3

// now invert

double ratio4 = 1.0 / ratio3; // R4

// don't exceed multiplier

//if ( ratio < 1.0 / g_conf.m_queryMaxMultiplier )

// ratio = 1.0 / g_conf.m_queryMaxMultiplier;

// get the pure weight

int32_t weight= (int32_t)(((double)MAX_SCORE_WEIGHT/3) * ratio4);//W1

// ensure at least 1

if ( weight < 1 ) weight = 1;

// don't breech MAX_SCORE

if ( weight > MAX_SCORE_WEIGHT ) weight = MAX_SCORE_WEIGHT;

// store it for use by addLists_r

m_scoreWeights[i] = weight; // (300 - score) + 100 ;

// . if this is a phrase then give it a boost

// . NOTE: this might exceed MAX_SCORE_WEIGHT then!!

if ( q->isPhrase(i) )

m_scoreWeights[i] = (int32_t)

( ( (float)m_scoreWeights[i] *

g_conf.m_queryPhraseWeight )/

100.0 ) ;

// . apply user-defined weights

// . we add this with completed disregard with date weighting

QueryTerm *qt = &q->m_qterms[i];

int64_t w ;

if ( qt->m_userType == 'r' ) w = (int64_t)m_scoreWeights[i] ;

else w = 1LL;

w *= (int64_t)qt->m_userWeight;

// it can be multiplied by up to 256 (the term count)

int64_t max = 0x7fffffff / 256;

if ( w > max ) {

log("query: Weight breech. Truncating to %"UINT64".",max);

w = max;

}

m_scoreWeights[i] = w;

// . stop words always get a weight of 1 regardless

// . we don't usually look them up unless all words in the

// query are stop words

//if ( q->m_isStopWords[i] ) weight = 1;

// log it

if ( m_isDebug || g_conf.m_logDebugQuery )

logf(LOG_DEBUG,"query: [%"UINT32"] term #%"INT32" has freq=%"INT64" "

"r1=%.3f r2=%.3f r3=%.3f r4=%.3f score weight=%"INT32"",

m_logstate,i,q->m_termFreqs[i],

ratio1,ratio2,ratio3,ratio4,m_scoreWeights[i]);

}

char **docIdPtrs ,

int32_t *scores ,

qvec_t *explicitBits ,

int16_t *hardCounts ,

uint32_t mask ,

int32_t numSlots ) {

// if none left to hash, we're done

if ( m_nexti >= m_numTopDocIds2 ) {

*maxDocId = (uint32_t)0xffffffff;

return;

}

*maxDocId = 0;

int32_t maxi = m_nexti + (numSlots >> 1);

if ( maxi > m_numTopDocIds2 ) maxi = m_numTopDocIds2;

int32_t oldmaxi = maxi;

// move maxi down to a maxDocId slot

while ( maxi > 0 && m_topScores2[maxi-1] != 0 ) maxi--;

// sometimes, the block can be bigger than numSlots when we

// overestimate maxDocIds and the second list hits the first like 80%

// or more of the time or so

if ( maxi == 0 || maxi <= m_nexti ) {

maxi = oldmaxi;

int32_t bigmax = m_nexti + numSlots;

if ( bigmax > m_numTopDocIds2 ) bigmax = m_numTopDocIds2;

// we can equal bigmax if we have exactly m_numSlots(1024)

// winners!! VERY RARE!! but it happened for me on the query

// 'https://www.highschoolalumni.com/'. we filled up our hash

// table exactly so we got m_numSlots winners, and before this

// was "maxi < bigmax" which stopped int16_t of what we needed.

// maxi should technically allowed to equal m_numTopDocIds2

while ( maxi <= bigmax && m_topScores2[maxi-1] != 0 ) maxi++;

if ( m_topScores2[maxi-1] != 0 ) {

log(LOG_LOGIC,"query: bad top scores2.");

char *xx = NULL; *xx = 0; }

}

// set maxDocId

*maxDocId = (int32_t)m_topDocIdPtrs2[maxi-1];

// sanity check

if ( *maxDocId == 0 ) {

log(LOG_LOGIC,"query: bad maxDocId.");

char *xx = NULL; *xx = 0; }

// debug msg

if ( m_isDebug || g_conf.m_logDebugQuery )

logf(LOG_DEBUG,"query: Hashing %"INT32" top docids2, [%"INT32", %"INT32")",

maxi-m_nexti,m_nexti,maxi);

int32_t nn;

// we use a score of 0 to denote docid blocks

for ( int32_t i = m_nexti ; i < maxi ; i++ ) {

// . if score is zero that's a tag block

// . all the docids before this should be < this max

if ( m_topScores2[i] == 0 ) continue;

// hash the top 32 bits of this docid

nn = (*(uint32_t *)(m_topDocIdPtrs2[i]+1) ) & mask ;

chain:

// . if empty, take right away

// . this is the most common case so we put it first

if ( docIdPtrs[nn] == NULL ) {

// hold ptr to our stuff

docIdPtrs [ nn ] = m_topDocIdPtrs2[i];

// store score

scores [ nn ] = m_topScores2 [i];

// now we use the explicitBits!

explicitBits [ nn ] = m_topExplicits2[i];

// and hard counts

hardCounts [ nn ] = m_topHardCounts2[i];

// add the next one

continue;

}

// if docIds bits don't match, chain to next bucket

// since we don't have dups and this is the first list we do

// not need to check for matching docids

if ( ++nn >= numSlots ) nn = 0;

goto chain;

}

// save the old one in case of a panic and rollback

m_oldnexti = m_nexti;

// advance next i

m_nexti = maxi;

int32_t numTiers ,

int32_t numListsPerTier ,

int32_t docsWanted ,

bool sortByDate ) {

// pre-allocate all the space we need for intersecting the lists

int64_t need = 0;

int32_t nqt = numListsPerTier; // number of query terms

// component lists are merged into compound lists

nqt -= m_q->getNumComponentTerms();

int32_t ntt = nqt * MAX_TIERS;

need += ntt * 256 * sizeof(char *) ; // ptrs

need += ntt * 256 * sizeof(char *) ; // pstarts

need += ntt * 256 * sizeof(char *) ; // oldptrs

need += nqt * 256 * sizeof(int32_t ) + nqt * sizeof(int32_t *);// scoretbls

need += ntt * sizeof(char ) ; // listSigns

need += ntt * sizeof(char ) ; // listHardCount

need += ntt * sizeof(int32_t *) ; // listScoreTablePtrs

need += ntt * sizeof(qvec_t) ; // listExplicitBits

need += ntt * sizeof(char *) ; // listEnds

need += ntt * sizeof(char ) ; // listHash

need += ntt * sizeof(qvec_t) ; // listPoints

// mark spot for m_topDocIdPtrs2 arrays

int32_t off = need;

// if sorting by date we need a much larger hash table than normal

if ( sortByDate ) {

// we need a "ptr end" (ptrEnds[i]) for each ptr since the

// buckets are not delineated by a date or score

need += ntt * 256 * sizeof(char *) ;

// get number of docids in largest list

int32_t max = 0;

for ( int32_t i = 0 ; i < numTiers ; i++ ) {

for ( int32_t j = 0 ; j < numListsPerTier ; j++ ) {

// datedb lists are 10 bytes per half key

int32_t nd = lists[i][j].getListSize() / 10;

if ( nd > max ) max = nd;

}

}

// how big to make hash table?

int32_t slotSize = 4+4+2+sizeof(qvec_t);

int64_t need = slotSize * max;

// have some extra slots in between for speed

need = (need * 5 ) / 4;

// . do not go overboard

// . let's try to keep it in the L2 cache

// . we can only do like 1 million random access to main

// memory per second. L2 mem should be much higher.

//if ( need > 30*1024*1024 ) need = 30*1024*1024;

//if ( need > 512*1024 ) need = 512*1024;

//if ( need > 1024*1024 ) need = 1024*1024;

// . this is balance between two latency functions. with more

// "need" we can have a bigger hash table which decrease

// m_numLoops, but increases our memory access latency since

// we'll be hitting more of main memory. use hashtest.cpp

// with a high # of slots to see the affects of increasing

// the size of the hash table. every loop in m_numLoops

// means we read the entire datedb lists and we can only do

// that at most at 2.5GB/sec or so on the current hardware.

// . i don't expect memory access times to improve as fast as

// memory throughput, so in the future to maintain optimal

// behaviour, we should decrease the max for "need"???

//if ( need > 4*1024*1024 ) need = 4*1024*1024;

if ( need > 2*1024*1024 ) need = 2*1024*1024;

//if ( need > 512*1024 ) need = 512*1024;

// we need to have AT LEAST 1024 slots in our hash table

if ( need < slotSize*1024 ) need = slotSize*1024;

// clear this out in case it was set

if ( m_bigBuf ) {

mfree ( m_bigBuf , m_bigBufSize , "IndexTable2" );

m_bigBuf = NULL;

}

tryagain:

// alloc again

m_bigBuf = (char *)mmalloc ( need , "IndexTable2" );

if ( ! m_bigBuf && need > 1024*1024 ) {

need >>= 1; goto tryagain; }

// set it

m_bigBufSize = need;

if ( ! m_bigBuf ) {

log("query: Could not allocate %"INT64" for query "

"resolution.",need);

return false;

}

}

// if not default AND no need for the list of docids from intersecting

// the last two termlists (and their associated phrase termlists)

if ( ! m_requireAllTerms ) {

// do it

m_bufSize = need;

m_buf = (char *) mmalloc ( m_bufSize , "IndexTable" );

if ( ! m_buf ) return log("query: Table alloc(%"INT64")"

": %s",need,mstrerror(g_errno));

// save it for error checking

m_bufMiddle = m_buf + off;

m_topDocIdPtrs2 = NULL;

m_topScores2 = NULL;

m_topExplicits2 = NULL;

m_topHardCounts2= NULL;

return true;

}

// sanity check

if ( m_topDocIdPtrs2 ) {

log(LOG_LOGIC,"query: bad top docid ptrs2.");

char *xx = NULL; *xx = 0; }

// calc list sizes

for ( int32_t i = 0 ; i < m_q->m_numTerms ; i++ ) {

m_sizes[i] = 0;

// component lists are merged into one compound list

if ( m_componentCodes[i] >= 0 ) continue;

for ( int32_t j = 0 ; j < numTiers ; j++ )

m_sizes [i] += lists[j][i].getListSize();

}

// . get imap here now so we can get the smallest block size to

// set m_maxNumTopDocIds2

// . get the smallest list (add all its tiers) to find least number

// of docids we'll have in m_topDocIdPtrs2

m_nb = m_q->getImap ( m_sizes , m_imap , m_blocksize );

// bail now if we have none!

if ( m_nb <= 0 ) return true;

int64_t min = 0;

for ( int32_t i = 0 ; i < m_blocksize[0]; i++ )

for ( int32_t j = 0 ; j < numTiers ; j++ )

min += lists[j][m_imap[i]].getListSize() / 6 ;

// debug msg

//log("minSize = %"INT32" docids q=%s",min,m_q->m_orig);

// now add in space for m_topDocIdPtrs2 (holds winners of a

// 2 list intersection (more than 2 lists if we have phrases) [imap]

int64_t nd = (105 * min) / 100 + 10 ;

need += (4+ // m_topDocIdPtrs2

4+ // m_topScores2

sizeof(qvec_t)+ // m_topExplicits2

2 // m_topHardCounts2

) * nd;

// do it

m_bufSize = need;

m_buf = (char *) mmalloc ( m_bufSize , "IndexTable" );

if ( ! m_buf ) return log("query: table alloc(%"INT64"): %s",

need,mstrerror(g_errno));

// save it for error checking

m_bufMiddle = m_buf + off;

// . allow for 5% more for inserting maxDocIds every block

// so hashTopDocIds2() can use that

// . actually, double in case we get all the termIds, but only one

// per slot scan/hash, so every other guy is a maxdocid

// . no, now we use lastGuy/lastGuy2 to check if our new maxDocId

// is within 50 or less of the second last maxDocId added, and

// if it is, we bury the lastGuy and replace him.

char *p = m_buf + off;

m_topDocIdPtrs2 = (char **)p ; p += 4 * nd;

m_topScores2 = (int32_t *)p ; p += 4 * nd;

m_topExplicits2 = (qvec_t *)p ; p += sizeof(qvec_t) * nd;

m_topHardCounts2= (int16_t *)p ; p += 2 * nd;

m_maxTopDocIds2 = nd;

m_numTopDocIds2 = 0;

return true;

if ( m_bigBuf ) {

mfree ( m_bigBuf , m_bigBufSize , "IndexTable2" );

m_bigBuf = NULL;

}

if ( ! m_buf ) return;

//mfree ( (char *)m_topDocIdPtrs2 , m_maxTopDocIds2 * 10,"IndexTable");

mfree ( m_buf , m_bufSize , "IndexTable" );

m_buf = NULL;

m_topDocIdPtrs2 = NULL;

m_topScores2 = NULL;

m_topExplicits2 = NULL;

m_topHardCounts2= NULL;

m_maxTopDocIds2 = 0;

m_numTopDocIds2 = 0;

int32_t numTiers ,

int32_t numListsPerTier ,

Query *q ,

int32_t docsWanted ,

int32_t *totalListSizes ,

bool useDateLists ,

bool sortByDate ,

float sortByDateWeight ) {

// sanity check

if ( ! useDateLists && sortByDate ) {

log(LOG_LOGIC,"query: bad useDateLists/sortByDate.");

char *xx = NULL; *xx = 0; }

// if we don't get enough results should we grow the lists and recall?

m_doRecall = true;

// bail if nothing to intersect... if all lists are empty

if ( ! m_buf /*m_nb <= 0*/ ) return;

// set start time

int64_t t1 = gettimeofdayInMilliseconds();

char hks = 6; // half key size (size of everything except the termid)

char fks = 12;

// dateLists are 4 more bytes per key than standard 12-byte key lists

if ( useDateLists ) { hks += 4; fks += 4; }

// set up for a pointer (array index actually) sort of the lists

//int32_t imap [ MAX_QUERY_TERMS ];

// now swap the top 12 bytes of each list back into original order

for ( int32_t i = 0 ; i < numListsPerTier ; i++ ) {

// loop over all lists in this term's tiers

for ( int32_t j = 0 ; j < numTiers ; j++ ) {

// skip if list is empty, too

if ( lists[j][i].isEmpty() ) continue;

// skip if already swapped

if ( m_swapped[j][i] ) continue;

// flag it

m_swapped[j][i] = true;

// point to start

char *p = lists[j][i].getList();

// remember to swap back when done!!

//char ttt[6];

//gbmemcpy ( ttt , p , 6 );

//gbmemcpy ( p , p + 6 , 6 );

//gbmemcpy ( p + 6 , ttt , 6 );

char ttt[10];

gbmemcpy ( ttt , p , hks );

gbmemcpy ( p , p + hks , 6 );

gbmemcpy ( p + 6 , ttt , hks );

// point to the low "hks" bytes now

p += 6;

// turn half bit on

*p |= 0x02;

}

}

// if query is boolean, turn off rat

if ( m_q->m_isBooleanQuery ) m_requireAllTerms = false;

// count # of panics

m_numPanics = 0;

// and # of collisions

m_numCollisions = 0;

// count # loops we do

m_numLoops = 0;

// . set m_q->m_bitScores[]

// . see Query.h for description of m_bitScores[]

// . this is now preset in Msg39.cpp since it may now require an

// alloc since we allow more than 16 query terms for metalincs

if ( ! m_q->m_bmap || ! m_q->m_bitScores ) { //alreadySet ) {

//m_q->setBitScores();

//m_alreadySet = true;

log (LOG_LOGIC,"query: bit map or scores is NULL. Fix this.");

return;

}

int32_t minHardCount = 0;

// if not rat, do it now

if ( ! m_requireAllTerms ) {

// no re-arranging the query terms for default OR searches

// because it is only beneficial when doing sequential

// intersectinos to minimize the intersection and speed up

int32_t count = 0;

for ( int32_t i = 0 ; i < m_q->m_numTerms ; i++ ) {

// component lists are merged into one compound list

if ( m_componentCodes[i] >= 0 ) continue;

m_imap[count++] = i;

}

addLists2_r ( lists ,

numTiers ,

count , // numListsPerTier

q ,

docsWanted ,

m_imap ,

true ,

0 ,

useDateLists ,

sortByDate ,

sortByDateWeight,

&minHardCount );

goto swapBack;

}

{ // i added this superfluous '{' so we can call "goto swapBack" above.

// TODO: use ptrs to score so when hashing m_topDocIdPtrs2 first and

// another non-required list second we can just add to the scores

// directly? naahhh. too complicated.

// get a map that sorts the query terms for optimal intersectioning

//int32_t blocksize [ MAX_QUERY_TERMS ];

//int32_t nb = m_q->getImap ( sizes , imap , blocksize );

// . if first list is required and has size 0, no results

// . 'how do they do that' is reduced to a signless phrase

// . careful, i still saw some chinese crap whose two terms were

// both signless phrases somehow... hmmm, m_nb was 0 and m_imap

// was not set

//if (m_nb <= 0||/*m_q->isRequired(imap[0])&&*/ m_sizes[m_imap[0]]<12){

if (m_nb <=0 || /*m_q->isRequired(imap[0])&&*/ m_sizes[m_imap[0]]<fks){

m_doRecall = false;

goto swapBack;

}

// count number of base lists

int32_t numBaseLists = m_blocksize[0];

// how many lists to intersect initially? that is numLists.

int32_t numLists = m_blocksize[0];

// if we got a second block, add his lists (single term plus phrases)

if ( m_nb > 1 ) numLists += m_blocksize[1];

// component lists are merged into one compound list

int32_t total = 0;

for ( int32_t i = 0 ; i < m_nb ; i++ ) // q->m_numTerms ; i++ )

//if ( m_componentCodes[i] < 0 ) total++;

total += m_blocksize[i];

// if this is true we set m_topDocIds/m_topScores/etc. in addLists2_r()

bool lastRound = (numLists == total); // numListsPerTier);

addLists2_r ( lists , numTiers , numLists , q , docsWanted ,

m_imap , lastRound , numBaseLists , useDateLists ,

sortByDate , sortByDateWeight , &minHardCount );

// . were both lists under the sum of tiers size?

// . if they were and we get no results, no use to read more, so we

// set m_doRecall to false to save time

bool underSized = true;

int32_t m0 = m_imap[0];

int32_t m1 = 0 ;

if ( m_nb > 1 ) m1 = m_imap[m_blocksize[0]];

if ( m_sizes[m0] >= totalListSizes[m0]&&m_q->getTermSign(m0)!='-')

underSized = false;

if(m_nb>1&& m_sizes[m1]>=totalListSizes[m1]&&m_q->getTermSign(m1)!='-')

underSized = false;

// . offset into imap

// . imap[off] must NOT be a signless phrase term

int32_t off = numLists;

// follow up calls

for ( int32_t i = 2 ; i < m_nb ; i++ ) {

// if it is the lastRound then addLists2_r() will compute

// m_topDocIds/m_topScores arrays

lastRound = (i == m_nb - 1);

// . if we have no more, might as well stop!

// . remember, maxDocIds is stored in here, so it will be at

// least 1

if ( m_numTopDocIds2 <= 1 ) break;

// is this list undersized?

int32_t mx = m_imap[off];

if (m_sizes[mx]>=totalListSizes[mx]&&m_q->getTermSign(mx)!='-')

underSized = false;

// set number of lists

numLists = m_blocksize[i];

// add it to the intersection

addLists2_r ( lists , numTiers , numLists , q , docsWanted ,

m_imap + off , lastRound, 0 , useDateLists ,

sortByDate , sortByDateWeight , &minHardCount );

// skip to next block of lists

off += m_blocksize[i];

}

// . now if we have no results and underSize is true, there is no

// use to read more for each list... pointless

// . remember, maxDocIds is stored in here, so it will be at least 1

if ( m_numTopDocIds2 <= 1 && underSized ) {

// debug

//fprintf(stderr,"UNDERSIZED quitting\n");

m_doRecall = false;

}

}

swapBack:

// compute total number of docids we dealt with

m_totalDocIds = 0;

// now swap the top 12 bytes of each list back into original order

for ( int32_t i = 0 ; i < numListsPerTier ; i++ ) {

// loop over all lists in this term's tiers

for ( int32_t j = 0 ; j < numTiers ; j++ ) {

// skip if list is empty, too

if ( lists[j][i].isEmpty() ) continue;

// compute total number of docids we dealt with

//m_totalDocIds += (lists[j][i].getListSize()-6)/6;

// date lists have 5 bytes scores, not 1 byte scores

m_totalDocIds += (lists[j][i].getListSize()-6)/hks;

// point to start

//char *p = lists[j][i].getList();

// remember to swap back when done!!

//char ttt[6];

//gbmemcpy ( ttt , p , 6 );

//gbmemcpy ( p , p + 6 , 6 );

//gbmemcpy ( p + 6 , ttt , 6 );

// turn half bit off again

//*p &= 0xfd;

}

}

// get time now

int64_t now = gettimeofdayInMilliseconds();

// store the addLists time

m_addListsTime = now - t1;

// . measure time to add the lists in bright green

// . use darker green if rat is false (default OR)

int32_t color;

if ( ! m_requireAllTerms ) color = 0x00008000 ;

else color = 0x0000ff00 ;

g_stats.addStat_r ( 0 , t1 , now , color );

int32_t numTiers ,

int32_t numListsPerTier ,

Query *q ,

int32_t docsWanted ,

int32_t *imap ,

bool lastRound ,

int32_t numBaseLists ,

bool useDateLists ,

bool sortByDate ,

float sortByDateWeight ,

int32_t *minHardCountPtr ) {

// set up for rat

int32_t rat = m_requireAllTerms;

m_nexti = 0;

// sanity test -- fails if 2nd guy is int16_t negative

/*

// getting 100 takes same time as getting 1

if ( docsWanted < 100 ) docsWanted = 100;

qvec_t requiredBits = m_q->m_requiredBits ;

unsigned char *bitScores = m_q->m_bitScores;

qvec_t *bmap = m_q->m_bmap;

// . keep track of max tier we've processed

// . if Msg39 finds that too many docids are clustered away it

// will recall us with docsWanted increased and the numTiers will

// be the same as the previous call

if ( numTiers < m_numTiers || numTiers > m_numTiers + 1 )

log(LOG_LOGIC,"query: indextable: Bad number of tiers."

" %"INT32" vs. %"INT32"", numTiers, m_numTiers );

else if ( numTiers == m_numTiers + 1 )

m_numTiers++;

// current tier #

int32_t tier = numTiers - 1;

// sanity check

if ( ! rat &&

numListsPerTier != m_q->getNumTerms()-m_q->getNumComponentTerms())

log(LOG_LOGIC,"query: indextable: List count mismatch.");

// truncate this

if (!m_topTree) if (docsWanted > MAX_RESULTS) docsWanted = MAX_RESULTS;

// convenience ptrs

char **topp = m_topDocIdPtrs [ tier ];

int32_t *tops = m_topScores [ tier ];

unsigned char *topb = m_topBitScores [ tier ];

char *tope = m_topExplicits [ tier ];

// assume no top docIds now

int32_t numTopDocIds = 0;

////////////////////////////////////

// begin hashing setup

////////////////////////////////////

// count # of docs that EXPLICITLY have all query singleton terms

int32_t explicitCount = 0;

// count # of docs that IMPLICITLY have all query singleton terms

int32_t implicitCount = 0;

// highest bscore we can have

//unsigned char maxbscore = bitScores [ requiredBits ];

// . count all mem that should be in the L1 cache

// . the less mem we use the more will be available for the hash table

int32_t totalMem = 0;

// . we mix up the docIdBits a bit before hashing using this table

// . TODO: what was the reason for this? particular type of query

// was too slow w/o it?

// . a suburl:com collision problem, where all docids have the same

// score and are spaced equally apart somehow made us have too

// many collisions before, probably because we included the score

// in the hash...? use bk revtool IndexTable.cpp to see the old file.

/*

// s_mixtab should be in the L1 cache cuz we use it to hash

//totalMem += 256 * sizeof(int32_t);

// . now form a set of ptrs for each list

// . each ptr points to the first 6-byte key for a particular score

char *p = m_buf;

int32_t nqt = numListsPerTier; // q->getNumQueryTerms();

int32_t ntt = numListsPerTier * numTiers;

// we now point into m_buf to save stack since we're in a thread

//char *ptrs [ MAX_QUERY_TERMS * MAX_TIERS * 256 ];

//char *pstarts [ MAX_QUERY_TERMS * MAX_TIERS * 256 ];

//int32_t scoreTable [ MAX_QUERY_TERMS ] [ 256 ];

//char *oldptrs [ MAX_QUERY_TERMS * MAX_TIERS * 256 ];

//char listSigns [ MAX_QUERY_TERMS * MAX_TIERS ];

//int32_t *listScoreTablePtrs [ MAX_QUERY_TERMS * MAX_TIERS ];

//qvec_t listExplicitBits [ MAX_QUERY_TERMS * MAX_TIERS ];

//char *listEnds [ MAX_QUERY_TERMS * MAX_TIERS ];

//char listHash [ MAX_QUERY_TERMS * MAX_TIERS ];

//qvec_t listPoints [ MAX_QUERY_TERMS * MAX_TIERS ];

char **ptrs = (char **)p; p += ntt * 256 * sizeof(char *);

char **pstarts = (char **)p; p += ntt * 256 * sizeof(char *);

char **ptrEnds = NULL;

if ( useDateLists ) {

ptrEnds = (char **)p; p += ntt * 256 * sizeof(char *);

}

char **oldptrs = (char **)p; p += ntt * 256 * sizeof(char *);

int32_t **scoreTable = (int32_t **)p; p += nqt * sizeof(int32_t *);

// one score table per query term

for ( int32_t i = 0 ; i < nqt ; i++ ) {

scoreTable [ i ] = (int32_t *)p; p += 256 * sizeof(int32_t); }

// we have to keep this info handy for each list

char *listSigns = (char *)p; p += ntt * sizeof(char );

char *listHardCount = (char *)p; p += ntt * sizeof(char );

int32_t **listScoreTablePtrs = (int32_t **)p; p += ntt * sizeof(int32_t *);

char **listEnds = (char **)p; p += ntt * sizeof(char *);

char *listHash = (char *)p; p += ntt * sizeof(char );

qvec_t *listExplicitBits = (qvec_t *)p; p += ntt * sizeof(qvec_t);

qvec_t *listPoints = (qvec_t *)p; p += ntt * sizeof(qvec_t);

// do not breech

if ( p > m_bufMiddle ) {

log(LOG_LOGIC,"query: indextable: Got table "

"mem breech.");

char *xx = NULL; *xx = 0;

}

char hks = 6; // half key size (size of everything except the termid)

// dateLists are 4 more bytes per key than standard 12-byte key lists

if ( useDateLists ) hks += 4;

int32_t numPtrs = 0;

int32_t numLists = 0;

uint32_t numDocIds = 0;

int32_t numSorts = 0;

// . make the ebitMask

// . used when rat=1 to determine the hits from both (or the) list

qvec_t ebitMask = 0;

// how many of the terms we are intersecting are "required" and

// therefore do not have an associated explicit bit. this allows us

// to support queries of many query terms.

int32_t minHardCount = *minHardCountPtr;

// each list can have up to 256 ptrs, corrupt data may mess this up