<?php
/**
* SeekQuarry/Yioop --
* Open Source Pure PHP Search Engine, Crawler, and Indexer
*
* Copyright (C) 2009 - 2026 Chris Pollett chris@pollett.org
*
* LICENSE:
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see <https://www.gnu.org/licenses/>.
*
* END LICENSE
*
* @author Chris Pollett chris@pollett.org
* @license https://www.gnu.org/licenses/ GPL3
* @link https://www.seekquarry.com/
* @copyright 2009 - 2026
* @filesource
*/
namespace seekquarry\yioop\library\index_bundle_iterators;
use seekquarry\yioop\configs as C;
use seekquarry\yioop\library as L;
use seekquarry\yioop\library\IndexManager;
use seekquarry\yioop\library\language_processing\PhraseParser;
/**
* UnionIterator walks the documents that hold any of the parts of a query,
* each part walked by an iterator of its own, and gives them back a block
* at a time with the relevance each part adds.
*
* @author Chris Pollett
* @see IndexArchiveBundle
*/
class UnionIterator extends IndexBundleIterator
{
/**
* JOINED_WORD_ACCUMULATORS is the fewest new accumulators a part of
* the query with a joined word may open in a block, even when earlier
* parts have used up the block. A joined word, such as tiktok for a
* search for tik tok, holds a word of an earlier part. Without this,
* a page with only the joined word, such as tiktok.com, never gets an
* accumulator.
*/
const JOINED_WORD_ACCUMULATORS = 10;
/**
* MAX_JOINED_WORD_PARTS is how many parts with a joined word, at
* most, get JOINED_WORD_ACCUMULATORS. The first ones in posting list
* order get them.
*/
const MAX_JOINED_WORD_PARTS = 3;
/**
* THRESHOLD_INTERVAL is how many postings of a part are read between
* one working out of its threshold for a new accumulator and the next.
*/
const THRESHOLD_INTERVAL = 128;
/**
* RELEVANCE_STEPS is how many steps one unit of relevance is cut into
* when the relevances of a part's postings are counted to work out
* its threshold for a new accumulator.
*/
const RELEVANCE_STEPS = 10;
/**
* $index_bundle_iterators holds the iterators of the query's parts,
* whose union this iterator gives, shortest posting list first
* @var array
*/
public $index_bundle_iterators;
/**
* $max_solution_docs is the sum of the parts' numbers of documents,
* the most documents the union could give, from which advance
* estimates how many it will give
* @var int
*/
public $max_solution_docs;
/**
* $num_iterators is how many parts the union has
* @var int
*/
public $num_iterators;
/**
* $count_block_unfiltered is how many postings the parts stepped over
* while making the current block, before pages held by two parts were
* counted once
* @var int
*/
public $count_block_unfiltered;
/**
* $seen_docs_unfiltered is the sum of $count_block_unfiltered over the
* blocks given so far, used by advance to estimate the number of
* documents
* @var int
*/
public $seen_docs_unfiltered;
/**
* $index_name is the timestamp of the index the union reads
* @var string
*/
public $index_name;
/**
* $joined_word_parts lists the positions in $index_bundle_iterators of
* the parts with a joined word, at most MAX_JOINED_WORD_PARTS of them,
* which may always open JOINED_WORD_ACCUMULATORS new accumulators
* @var array
*/
public $joined_word_parts = [];
/**
* $relevance_counts holds, for each part, how many of its postings
* read so far without an accumulator fell in each step of relevance
* (see RELEVANCE_STEPS). findDocsWithWord works out the part's
* threshold for a new accumulator from it.
* @var array
*/
public $relevance_counts = [];
/**
* $postings_seen holds, for each part, how many of its postings have
* been read
* @var array
*/
public $postings_seen = [];
/**
* $thresholds holds, for each part, the step of relevance a posting
* without an accumulator must reach to get a new one
* @var array
*/
public $thresholds = [];
/**
* $field_partners holds, for each part that walks a word's field key,
* the position in $index_bundle_iterators of the part that walks the
* same word's other key. A page is filed under a word's field key when
* the word is in the page's host, title or path, and its field posting
* points at the same position list as its other posting. So once a
* block has no room for new pages, findDocsWithWord scores the field
* key from the other key's postings rather than reading the field
* key's own.
* @var array
*/
public $field_partners = [];
/**
* __construct makes a union iterator with the given
* parameters. The iterators are taken shortest posting list first, as
* term at a time query processing takes its terms. A part with a word
* that holds a word of an earlier part, as tiktok holds tik, is noted
* as a part with a joined word. A pair of a word's field key part and
* other key part is noted in $field_partners.
*
* @param object $index_bundle_iterators to use as a source of documents
* to iterate over
* @param string $index_name time_stamp of the index to use
* @param array $part_words for each iterator, in the same order, the
* words of the part of the query it looks up
* @param array $field_parts for each iterator that walks a word's field
* key, by its position in $index_bundle_iterators, the position of
* the iterator that walks the same word's other key
*/
public function __construct($index_bundle_iterators,
$index_name, $part_words = [], $field_parts = [])
{
/*
estimate number of results by sum of all iterator counts,
then improve estimate as iterate
*/
$num_iterators = count($index_bundle_iterators);
$this->num_iterators = $num_iterators;
$this->num_docs = 0;
/*
result_per_block is at most the sum of
results_per_block of things we are iterating. Value
is already init'd in base class.
*/
$this->results_per_block = intval(C\p('MIN_RESULTS_TO_GROUP'));
$this->seen_docs = 0;
$this->seen_docs_unfiltered = 0;
$this->index_name = $index_name;
$this->max_solution_docs = 0;
$order = [];
for ($i = 0; $i < $num_iterators; $i++) {
$index_bundle_iterators[$i]->setResultsPerBlock(1);
$this->max_solution_docs += $index_bundle_iterators[$i]->num_docs;
$order[] = $i;
}
usort($order, fn($first, $second) =>
$index_bundle_iterators[$first]->num_docs <=>
$index_bundle_iterators[$second]->num_docs);
$sorted_positions = array_flip($order);
foreach ($field_parts as $field_part => $other_part) {
if (isset($sorted_positions[$field_part],
$sorted_positions[$other_part])) {
$this->field_partners[$sorted_positions[$field_part]] =
$sorted_positions[$other_part];
}
}
foreach ($order as $i => $index) {
$this->index_bundle_iterators[$i] =
$index_bundle_iterators[$index];
for ($j = 0; $j < $i && count($this->joined_word_parts) <
self::MAX_JOINED_WORD_PARTS; $j++) {
if (self::holdsWordOf($part_words[$index] ?? [],
$part_words[$order[$j]] ?? [])) {
$this->joined_word_parts[] = $i;
break;
}
}
}
}
/**
* holdsWordOf says if one of $words contains one of $other_words
* inside it and is longer, as tiktok contains tik. The UnionIterator
* constructor uses it to find the parts of a query with a joined
* word.
*
* @param array $words the words of one part of a query
* @param array $other_words the words of a part placed before it
* @return bool true if a word of $words holds a word of $other_words
*/
public static function holdsWordOf($words, $other_words)
{
foreach ($words as $word) {
foreach ($other_words as $other_word) {
if (strlen($word) > strlen($other_word) &&
$other_word != "" && str_contains($word, $other_word)) {
return true;
}
}
}
return false;
}
/**
* getDirection says which way the union walks the index: forward,
* CrawlConstants::ASCENDING, or backward, CrawlConstants::DESCENDING.
* It is the direction of the first part, which all parts share.
*
* @return int the direction the union walks the index
*/
public function getDirection()
{
if (!empty($this->index_bundle_iterators[0])) {
return $this->index_bundle_iterators[0]->getDirection();
}
return self::ASCENDING;
}
/**
* reset puts every part back at its first document, empties the
* counts findDocsWithWord keeps for pruning, and makes the first block.
*/
public function reset()
{
for ($i = 0; $i < $this->num_iterators; $i++) {
$this->index_bundle_iterators[$i]->reset();
}
$this->seen_docs = 0;
$this->seen_docs_unfiltered = 0;
$this->relevance_counts = [];
$this->postings_seen = [];
$this->thresholds = [];
$doc_block = $this->currentDocsWithWord();
}
/**
* findDocsWithWord makes the next block of documents by term at a time
* query processing with accumulator pruning, after Lester et al.
* (2005). The parts of the query are taken shortest posting list first.
* The first part's documents become accumulators until the block's
* results_per_block are used up. Each later part adds its relevance to
* the accumulators that hold its documents. Where room is left, a
* document only a later part has gets a new accumulator if its
* relevance reaches the part's threshold, worked out by
* workOutThreshold from the postings read so far. A part with a joined
* word may always open JOINED_WORD_ACCUMULATORS new ones.
* currentDocsWithWord calls it when the block it holds is used up.
*
* @return mixed doc ids and score if there are docs left, -1 otherwise
*/
public function findDocsWithWord()
{
$iterators = $this->index_bundle_iterators;
$this->count_block_unfiltered = 0;
$direction = $this->getDirection();
$max_accumulators = intval($this->results_per_block);
$to_accumulators = [];
/* $deferred lists, under the position of a part, the field key
parts waiting to be scored from its postings, and $field_hits
and $field_prune keep, for each of those, how many pages it
scored and whether it was pruning, as its own walk would have. */
$deferred = [];
$field_hits = [];
$field_prune = [];
foreach ($iterators as $i => $iterator) {
$from_accumulators = $to_accumulators;
$to_accumulators = [];
$num_from = count($from_accumulators);
/* $room is what the block has left; documents past the last
accumulator may only fill that, or a later block would see
the earlier parts' share of them as other documents. */
$room = max(0, $max_accumulators - $num_from);
$quota_left = in_array($i, $this->joined_word_parts) ?
max($room, self::JOINED_WORD_ACCUMULATORS) : $room;
$prune = $num_from > 0 && $iterator->num_docs -
($this->postings_seen[$i] ?? 0) > $quota_left;
if ($quota_left == 0 && $num_from > 0 &&
$this->deferField($i)) {
/* The field key part can only add relevance to pages
already held, and each of those it holds is also held by
its partner, walked later. The partner's walk scores it,
so here the part only moves past the block, where its
own walk would have stopped. */
$last = $from_accumulators[$num_from - 1][self::GEN_OFFSET];
$step = ($this->getDirection() == self::ASCENDING) ? 1 : -1;
$iterator->advance([$last[0], $last[1] + $step]);
$deferred[$this->field_partners[$i]][] = $i;
$field_hits[$i] = 0;
$field_prune[$i] = $prune;
$to_accumulators = $from_accumulators;
continue;
}
$in_pos = 0;
while (($offset = $iterator->currentGenDocOffsetWithWord()) !=
-1) {
$cmp = -1;
if ($in_pos < $num_from) {
$accumulator_offset =
$from_accumulators[$in_pos][self::GEN_OFFSET];
$cmp = $this->genDocOffsetCmp($offset,
$accumulator_offset, $direction);
if ($cmp > 0) {
$to_accumulators[] = $from_accumulators[$in_pos++];
continue;
}
if ($cmp < 0 && $quota_left == 0) {
$iterator->advance($accumulator_offset);
/* $iterator lists the documents of one query
term. Its current document comes before
$accumulator_offset, the next document already
being scored, and no new documents may be
scored in this block. So the iterator skips
ahead to $accumulator_offset. If advance() leaves
the iterator on the same document, this while
loop calls advance() with the same offset
forever, and the query hangs. In that case the
iterator moves to its next document instead,
and query statistics count it as "union parts
that did not advance". */
if ($iterator->currentGenDocOffsetWithWord() ==
$offset) {
$iterator->advance();
L\AnalyticsManager::addTiming(
"union parts that did not advance",
microtime(true));
}
$this->count_block_unfiltered++;
continue;
}
} else if ($room == 0) {
break;
}
$docs = $iterator->findDocsWithWord();
$doc = (is_array($docs) && count($docs) == 1) ?
reset($docs) : null;
$iterator->advance();
$this->count_block_unfiltered++;
$this->postings_seen[$i] =
($this->postings_seen[$i] ?? 0) + 1;
if ($cmp == 0) {
$accumulator = $from_accumulators[$in_pos++];
$accumulator[self::RELEVANCE] +=
$doc[self::RELEVANCE] ?? 0;
foreach ($deferred[$i] ?? [] as $field_part) {
$field_relevance = ($doc === null) ? null :
$iterators[$field_part]->fieldRelevance($doc);
if ($field_relevance !== null) {
$accumulator[self::RELEVANCE] += $field_relevance;
$field_hits[$field_part]++;
}
}
$to_accumulators[] = $accumulator;
} else if ($doc !== null) {
$step = intval(floor(($doc[self::RELEVANCE] ?? 0) *
self::RELEVANCE_STEPS));
if (!$prune || $in_pos >= $num_from ||
$step >= ($this->thresholds[$i] ?? 0)) {
$doc[self::GEN_OFFSET] = $offset;
$to_accumulators[] = $doc;
$quota_left--;
$room = max(0, $room - 1);
}
$this->relevance_counts[$i][$step] =
($this->relevance_counts[$i][$step] ?? 0) + 1;
}
if ($prune && $this->postings_seen[$i] %
self::THRESHOLD_INTERVAL == 0) {
$this->workOutThreshold($i, $quota_left);
}
}
while ($in_pos < $num_from) {
$to_accumulators[] = $from_accumulators[$in_pos++];
}
/* The counts a field key part's own walk keeps are kept for it
here: each page it scored is a posting read, and when it
prunes, a threshold is worked out on passing each multiple
of THRESHOLD_INTERVAL. With no room left, that threshold
depends only on counts this block does not change, so one
working out stands for all of them. */
foreach ($deferred[$i] ?? [] as $field_part) {
$seen_before = $this->postings_seen[$field_part] ?? 0;
$this->postings_seen[$field_part] = $seen_before +
$field_hits[$field_part];
$this->count_block_unfiltered += $field_hits[$field_part];
if ($field_prune[$field_part] && intdiv($seen_before +
$field_hits[$field_part], self::THRESHOLD_INTERVAL) >
intdiv($seen_before, self::THRESHOLD_INTERVAL)) {
$this->workOutThreshold($field_part, 0);
}
}
}
$pages = [];
foreach ($to_accumulators as $accumulator) {
if (!empty($accumulator[self::KEY])) {
$accumulator[self::SCORE] = $accumulator[self::DOC_RANK] +
$accumulator[self::RELEVANCE];
$page_acc = $pages[$accumulator[self::KEY]] ?? null;
if (empty($page_acc)) {
$page_acc = $accumulator;
} else if (!empty($accumulator[self::IS_DOC]) &&
!empty($page_acc[self::IS_DOC])) {
/* two copies of one page, as a recrawl leaves, which
WordIterator gives the latest copy's key: keep one */
if ($accumulator[self::SCORE] > $page_acc[self::SCORE]) {
$page_acc = $accumulator;
}
} else if (empty($accumulator[self::IS_DOC]) &&
$page_acc[self::SCORE] > $accumulator[self::SCORE]) {
$page_acc[self::DOC_RANK] += $accumulator[self::DOC_RANK];
$page_acc[self::RELEVANCE] += $accumulator[self::RELEVANCE];
$page_acc[self::SCORE] = $page_acc[self::DOC_RANK] +
$page_acc[self::RELEVANCE];
} else {
$accumulator[self::DOC_RANK] += $page_acc[self::DOC_RANK];
$accumulator[self::RELEVANCE] += $page_acc[self::RELEVANCE];
$page_acc = $accumulator;
$page_acc[self::SCORE] = $page_acc[self::DOC_RANK] +
$page_acc[self::RELEVANCE];
}
$pages[$accumulator[self::KEY]] = $page_acc;
}
}
if (empty($pages)) {
return -1;
}
$this->pages = $pages;
$this->count_block = count($pages);
return $pages;
}
/**
* deferField says if the part at position $i walks a word's field key
* whose scoring findDocsWithWord can leave to the walk of the same
* word's other key. That is so when the other key's part comes later,
* and no part in between may open new accumulators, as a part with a
* joined word may. Then the pages the field key part could score are
* all still held when the other key's part is walked. findDocsWithWord
* calls it for a part when the block has no room left.
*
* @param int $i position of the part in $index_bundle_iterators
* @return bool whether the part's scoring is left to its partner
*/
public function deferField($i)
{
$partner = $this->field_partners[$i] ?? -1;
if ($partner <= $i) {
return false;
}
foreach ($this->joined_word_parts as $joined_part) {
if ($joined_part > $i && $joined_part < $partner) {
return false;
}
}
return true;
}
/**
* workOutThreshold sets the step of relevance a posting of part $i
* without an accumulator must reach to get a new one. From the
* postings read so far it estimates how many of the rest reach each
* step, scaling the counts by q, the postings left over the postings
* read. The threshold is the lowest step at which that estimate stays
* under the accumulators the part may still open. findDocsWithWord
* calls it every THRESHOLD_INTERVAL postings of the part.
*
* @param int $i position of the part in $index_bundle_iterators
* @param int $quota_left how many new accumulators the part may still
* open in this block
*/
public function workOutThreshold($i, $quota_left)
{
$seen = max(1, $this->postings_seen[$i] ?? 0);
$left_over_read = max(0,
$this->index_bundle_iterators[$i]->num_docs - $seen) / $seen;
$counts = $this->relevance_counts[$i] ?? [];
krsort($counts);
$expected = 0;
$threshold = empty($counts) ? 0 : array_key_first($counts) + 1;
foreach ($counts as $step => $count) {
$expected += $count * $left_over_read;
if ($expected >= $quota_left) {
break;
}
$threshold = $step;
}
$this->thresholds[$i] = $threshold;
}
/**
* advance moves the union on to its next block of documents. It adds
* the block's counts to the counts of documents seen, from which it
* estimates the number of documents the union gives, and, when given
* a place in the index, moves every part to it.
*
* @param array $gen_doc_offset a partition and document offset pair.
* If set, the next block holds only documents at or after it.
*/
public function advance($gen_doc_offset = null)
{
$this->current_block_fresh = false;
$this->seen_docs += $this->count_block;
$this->seen_docs_unfiltered += $this->count_block_unfiltered;
$this->num_docs =
floor(($this->seen_docs * $this->max_solution_docs) /
$this->seen_docs_unfiltered);
if ($gen_doc_offset != null) {
foreach ($this->index_bundle_iterators as $iterator) {
$iterator->advance($gen_doc_offset);
}
}
}
/**
* setResultsPerBlock would set the most documents one block of the
* union holds. A union's block size cannot be set this way and still
* work with an IntersectIterator, so calling it raises a user error.
*
* @param int $num the most documents a block would hold
*/
public function setResultsPerBlock($num) {
trigger_error("Cannot set the results per block of
a union iterator", E_USER_ERROR);
}
/**
* currentGenDocOffsetWithWord gives the partition and document offset
* of the first part that still has documents, the place the union
* has reached.
*
* @return mixed the partition and document offset pair, or -1 when
* every part has run out
*/
public function currentGenDocOffsetWithWord() {
$gen_doc_offset = -1;
$index_bundle_iterators = $this->index_bundle_iterators;
foreach ($index_bundle_iterators as $iterator) {
$gen_doc_offset = $iterator->currentGenDocOffsetWithWord();
if ($gen_doc_offset != -1) {
break;
}
}
return $gen_doc_offset;
}
}
- Yioop Repo - Seekquarry