Skip to content

web search done right

18.5 KB
Raw Blame
// Stract is an open source web search engine.
// Copyright (C) 2024 Stract ApS
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU Affero 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 Affero General Public License for more details.
//
// You should have received a copy of the GNU Affero General Public License
// along with this program.  If not, see <https://www.gnu.org/licenses/>.

//! The ranking computer is responsible for computing the core ranking signals for
//! each potential page in the result set. This module handles the initial ranking phase
//! that runs independently on each search node in the distributed search cluster.
//!
//! The computer evaluates a set of core ranking signals for each candidate page,
//! including text-based relevance scores like BM25 and authority scores (harmonic centrality).
//! These signals are combined using a linear model to produce an initial ranking score.
//! The top pages are passed to the coordinator node for the final ranking phase.
//!
//! The core signals computed here are designed to be fast to calculate while still
//! providing strong relevance signals. More expensive ranking features are deferred
//! to the final ranking phase on the coordinator.

use crate::query::optic::AsSearchableRule;
use crate::query::{Query, MAX_TERMS_FOR_NGRAM_LOOKUPS};
use crate::ranking::bm25f::MultiBm25FWeight;
use crate::schema::text_field::TextField;
use crate::Result;
use crate::{enum_map::EnumMap, numericalfield_reader, schema::TextFieldEnum, webpage::Webpage};

use std::cell::RefCell;

use std::sync::Arc;

use itertools::Itertools;
use lending_iter::LendingIterator;
use tantivy::fieldnorm::FieldNormReader;
use tantivy::postings::SegmentPostings;
use tantivy::query::{Query as _, Scorer};
use tantivy::tokenizer::Tokenizer as _;

use tantivy::DocSet;
use tantivy::{postings::Postings, DocId};

use crate::webpage::region::RegionCount;

use crate::ranking::bm25::MultiBm25Weight;
use crate::ranking::models::linear::LinearRegression;

use super::{ComputedSignal, CoreSignal, CoreSignalEnum, Signal, SignalCoefficients, SignalEnum};

mod order;
pub use order::SignalComputeOrder;

fn posting_contains(posting: &mut SegmentPostings, doc: DocId) -> bool {
    posting.doc() == doc || (posting.doc() < doc && posting.seek(doc) == doc)
}

#[derive(Clone)]
pub struct TextFieldData {
    postings: Vec<SegmentPostings>,
    num_query_terms: usize,
    bm25: MultiBm25Weight,
    bm25f: MultiBm25FWeight,
    fieldnorm_reader: FieldNormReader,
    signal_coefficient: f64,
}

impl TextFieldData {
    pub fn positions(&mut self, doc: DocId) -> Vec<Vec<u32>> {
        self.postings
            .iter_mut()
            .map(|posting| {
                if posting_contains(posting, doc) {
                    let mut positions = Vec::new();
                    posting.positions(&mut positions);
                    positions
                } else {
                    Vec::new()
                }
            })
            .collect()
    }

    pub fn coverage(&mut self, doc: DocId) -> f64 {
        if self.postings.is_empty() {
            return 0.0;
        }

        self.postings
            .iter_mut()
            .map(|posting| {
                if posting_contains(posting, doc) {
                    1.0
                } else {
                    0.0
                }
            })
            .sum::<f64>()
            / self.num_query_terms as f64
    }

    pub fn bm25(&mut self, doc: DocId) -> f64 {
        if self.postings.is_empty() {
            return 0.0;
        }

        let fieldnorm_id = self.fieldnorm_reader.fieldnorm_id(doc);

        self.bm25
            .score(self.postings.iter_mut().map(move |posting| {
                if posting_contains(posting, doc) {
                    (fieldnorm_id, posting.term_freq())
                } else {
                    (fieldnorm_id, 0)
                }
            })) as f64
    }

    pub fn idf_sum(&mut self, doc: DocId) -> f64 {
        if self.postings.is_empty() {
            return 0.0;
        }
        let idf = self.bm25.idf();

        self.postings
            .iter_mut()
            .zip_eq(idf)
            .filter_map(|(posting, idf)| {
                if posting_contains(posting, doc) {
                    Some(idf)
                } else {
                    None
                }
            })
            .sum::<f32>() as f64
    }

    pub fn bm25f(&mut self, doc: DocId) -> f64 {
        if self.postings.is_empty() {
            return 0.0;
        }

        let fieldnorm_id = self.fieldnorm_reader.fieldnorm_id(doc);

        self.bm25f.score(
            self.signal_coefficient as f32,
            self.postings.iter_mut().map(move |posting| {
                if posting.doc() == doc || (posting.doc() < doc && posting.seek(doc) == doc) {
                    (fieldnorm_id, posting.term_freq())
                } else {
                    (fieldnorm_id, 0)
                }
            }),
        ) as f64
    }
}
pub struct RuleBoost {
    docset: Box<dyn Scorer>,
    boost: f64,
}

pub struct OpticBoosts {
    rules: Vec<RuleBoost>,
}

pub struct SegmentReader {
    text_fields: EnumMap<TextFieldEnum, TextFieldData>,
    optic_boosts: OpticBoosts,
    numericalfield_reader: numericalfield_reader::SegmentReader,
}

impl SegmentReader {
    pub fn text_fields_mut(&mut self) -> &mut EnumMap<TextFieldEnum, TextFieldData> {
        &mut self.text_fields
    }

    pub fn numericalfield_reader(&self) -> &numericalfield_reader::SegmentReader {
        &self.numericalfield_reader
    }

    pub fn prepare_for_doc(&mut self, doc: DocId) {
        self.numericalfield_reader.prepare_row_for_doc(doc);
    }
}

#[derive(Clone)]
pub struct QueryData {
    simple_terms: Vec<String>,
    optic_rules: Vec<optics::Rule>,
    selected_region: Option<crate::webpage::Region>,
    lang: Option<whatlang::Lang>,
}
impl QueryData {
    pub fn selected_region(&self) -> Option<crate::webpage::Region> {
        self.selected_region
    }

    pub fn simple_terms(&self) -> &[String] {
        &self.simple_terms
    }
}

pub struct SignalComputer {
    query_data: Option<QueryData>,
    query_signal_coefficients: Option<SignalCoefficients>,
    segment_reader: Option<RefCell<SegmentReader>>,
    fetch_time_ms_cache: Vec<f64>,
    update_time_cache: Vec<f64>,
    region_count: Option<Arc<RegionCount>>,
    current_timestamp: Option<usize>,
    linear_regression: Option<Arc<LinearRegression>>,
    order: SignalComputeOrder,
}

impl Clone for SignalComputer {
    fn clone(&self) -> Self {
        Self {
            query_data: self.query_data.clone(),
            query_signal_coefficients: self.query_signal_coefficients.clone(),
            segment_reader: None,
            fetch_time_ms_cache: self.fetch_time_ms_cache.clone(),
            update_time_cache: self.update_time_cache.clone(),
            region_count: self.region_count.clone(),
            current_timestamp: self.current_timestamp,
            linear_regression: self.linear_regression.clone(),
            order: self.order.clone(),
        }
    }
}

impl std::fmt::Debug for SignalComputer {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        f.debug_struct("SignalComputer")
            .field(
                "query",
                &self
                    .query_data
                    .as_ref()
                    .map(|q| q.simple_terms.clone())
                    .unwrap_or_default(),
            )
            .finish()
    }
}

impl SignalComputer {
    pub fn new(query: Option<&Query>) -> Self {
        let query_signal_coefficients = query.as_ref().map(|q| q.signal_coefficients());

        let fetch_time_ms_cache: Vec<_> = (0..1000)
            .map(|fetch_time| 1.0 / (fetch_time as f64 + 1.0))
            .collect();

        let update_time_cache = (0..(3 * 365 * 24))
            .map(|hours_since_update| {
                super::signals::time_cache_calculation(hours_since_update as f64)
            })
            .collect();

        let query = query.as_ref().map(|q| QueryData {
            simple_terms: q.simple_terms().to_vec(),
            optic_rules: q
                .optics()
                .iter()
                .flat_map(|o| o.rules.iter())
                .filter(|rule| match rule.action {
                    optics::Action::Downrank(b) | optics::Action::Boost(b) => b != 0,
                    optics::Action::Discard => false,
                })
                .cloned()
                .collect(),
            selected_region: q.region().cloned(),
            lang: q.lang(),
        });

        let mut s = Self {
            segment_reader: None,
            query_signal_coefficients,
            fetch_time_ms_cache,
            update_time_cache,
            region_count: None,
            current_timestamp: None,
            linear_regression: None,
            query_data: query,
            order: SignalComputeOrder::new(),
        };

        s.set_current_timestamp(chrono::Utc::now().timestamp() as usize);

        s
    }

    fn prepare_textfields(
        &self,
        tv_searcher: &tantivy::Searcher,
        segment_reader: &tantivy::SegmentReader,
    ) -> Result<EnumMap<TextFieldEnum, TextFieldData>> {
        let mut text_fields = EnumMap::new();
        let schema = tv_searcher.schema();

        if let Some(query) = &self.query_data {
            if !query.simple_terms.is_empty() {
                let mut bm25f_weight_cache = super::bm25f::WeightCache::new();

                for signal in CoreSignalEnum::all() {
                    if let Some((text_field, tv_field)) = signal
                        .as_textfield()
                        .and_then(|f| (f.tantivy_field(schema).map(|tv_field| (f, tv_field))))
                    {
                        if text_field.ngram_size() > 1
                            && query.simple_terms.len() > MAX_TERMS_FOR_NGRAM_LOOKUPS
                        {
                            continue;
                        }

                        let simple_query = itertools::intersperse(
                            query.simple_terms.iter().map(|s| s.as_str()),
                            " ",
                        )
                        .collect::<String>();

                        let mut terms = Vec::new();
                        let mut bm25f_terms = Vec::new();
                        let mut tokenizer = text_field.query_tokenizer(query.lang.as_ref());
                        let mut stream = tokenizer.token_stream(&simple_query);
                        let mut it = tantivy::tokenizer::TokenStream::iter(&mut stream);

                        while let Some(token) = it.next() {
                            let term = tantivy::Term::from_field_text(tv_field, &token.text);
                            terms.push(term.clone());
                            bm25f_terms.push(super::bm25f::PreparedTerm::new(
                                term,
                                bm25f_weight_cache.get(&token.text, tv_searcher),
                            ));
                        }

                        if terms.is_empty() {
                            continue;
                        }

                        let fieldnorm_reader = segment_reader.get_fieldnorms_reader(tv_field)?;
                        let inverted_index = segment_reader.inverted_index(tv_field)?;

                        let mut postings = Vec::with_capacity(terms.len());
                        for term in &terms {
                            if let Some(p) =
                                inverted_index.read_postings(term, text_field.record_option())?
                            {
                                postings.push(p);
                            } else {
                                postings.push(SegmentPostings::empty())
                            }
                        }
                        let bm25 = MultiBm25Weight::for_terms(
                            tv_searcher,
                            &terms,
                            text_field.bm25_constants(),
                        )?;
                        let bm25f = MultiBm25FWeight::for_terms(
                            tv_searcher,
                            &bm25f_terms,
                            text_field.bm25_constants(),
                        );

                        text_fields.insert(
                            text_field,
                            TextFieldData {
                                postings,
                                bm25,
                                bm25f,
                                fieldnorm_reader,
                                signal_coefficient: self.coefficient(&signal.into()),
                                num_query_terms: terms.len(),
                            },
                        );
                    }
                }
            }
        }

        Ok(text_fields)
    }

    fn prepare_optic(
        &self,
        tv_searcher: &tantivy::Searcher,
        segment_reader: &tantivy::SegmentReader,
        numericalfield_reader: &numericalfield_reader::NumericalFieldReader,
    ) -> Vec<RuleBoost> {
        let mut optic_rule_boosts = Vec::new();

        if let Some(query) = &self.query_data {
            optic_rule_boosts = query
                .optic_rules
                .iter()
                .filter_map(|rule| {
                    rule.as_searchable_rule(tv_searcher.schema(), numericalfield_reader)
                })
                .map(|(_, rule)| RuleBoost {
                    docset: rule
                        .query
                        .weight(tantivy::query::EnableScoring::Enabled {
                            searcher: tv_searcher,
                            statistics_provider: tv_searcher,
                        })
                        .unwrap()
                        .scorer(segment_reader, 0.0)
                        .unwrap(),
                    boost: rule.boost,
                })
                .collect();
        }

        optic_rule_boosts
    }

    pub fn register_segment(
        &mut self,
        tv_searcher: &tantivy::Searcher,
        segment_reader: &tantivy::SegmentReader,
        numericalfield_reader: &numericalfield_reader::NumericalFieldReader,
    ) -> Result<()> {
        let numericalfield_segment_reader = numericalfield_reader
            .borrow_segment(&segment_reader.segment_id())
            .clone();
        let text_fields = self.prepare_textfields(tv_searcher, segment_reader)?;
        let optic_rule_boosts =
            self.prepare_optic(tv_searcher, segment_reader, numericalfield_reader);

        self.segment_reader = Some(RefCell::new(SegmentReader {
            text_fields,
            numericalfield_reader: numericalfield_segment_reader,
            optic_boosts: OpticBoosts {
                rules: optic_rule_boosts,
            },
        }));

        Ok(())
    }

    pub fn set_region_count(&mut self, region_count: RegionCount) {
        self.region_count = Some(Arc::new(region_count));
    }

    pub fn set_current_timestamp(&mut self, current_timestamp: usize) {
        self.current_timestamp = Some(current_timestamp);
    }

    pub fn set_linear_model(&mut self, linear_model: Arc<LinearRegression>) {
        self.linear_regression = Some(linear_model);
    }

    /// Computes the scored signals for a given document.
    ///
    /// Important: This function assumes that the docs a scored in ascending order of docid
    /// within their segment. If this invariant is not upheld, the documents will not have
    /// scores calculated for their text related signals. The wrong ranking will most likely
    /// be returned.
    /// This function also assumes that the segment reader has been set.
    pub fn compute_signals(&self, doc: DocId) -> impl Iterator<Item = ComputedSignal> + '_ {
        self.order.compute(doc, self)
    }

    pub fn boosts(&mut self, doc: DocId) -> Option<f64> {
        self.segment_reader.as_ref().map(|segment_reader| {
            let mut downrank = 0.0;
            let mut boost = 0.0;

            for rule in &mut segment_reader.borrow_mut().optic_boosts.rules {
                if rule.docset.doc() > doc {
                    continue;
                }

                if rule.docset.doc() == doc || rule.docset.seek(doc) == doc {
                    if rule.boost < 0.0 {
                        downrank += rule.boost.abs();
                    } else {
                        boost += rule.boost;
                    }
                }
            }

            if downrank > boost {
                let diff = downrank - boost;
                1.0 / (1.0 + diff)
            } else {
                boost - downrank + 1.0
            }
        })
    }

    pub fn precompute_score(&self, webpage: &Webpage) -> f64 {
        CoreSignalEnum::all()
            .filter_map(|signal| {
                signal.precompute(webpage, self).map(|calc| ComputedSignal {
                    signal: signal.into(),
                    calc,
                })
            })
            .map(|computed| self.coefficient(&computed.signal) * computed.calc.score)
            .sum()
    }

    pub fn coefficient(&self, signal: &SignalEnum) -> f64 {
        self.query_signal_coefficients
            .as_ref()
            .map(|coefficients| coefficients.get(signal))
            .or_else(|| {
                self.linear_regression
                    .as_ref()
                    .and_then(|model| model.weights.get(*signal).copied())
            })
            .unwrap_or(signal.default_coefficient())
    }

    pub fn segment_reader(&self) -> Option<&RefCell<SegmentReader>> {
        self.segment_reader.as_ref()
    }

    pub fn get_field_positions(
        &mut self,
        field: TextFieldEnum,
        doc: DocId,
    ) -> Option<Vec<Vec<u32>>> {
        self.segment_reader
            .as_mut()
            .and_then(|reader| reader.get_mut().text_fields_mut().get_mut(field))
            .map(|textfield_data| textfield_data.positions(doc))
    }

    pub fn fetch_time_ms_cache(&self) -> &[f64] {
        &self.fetch_time_ms_cache
    }

    pub fn current_timestamp(&self) -> Option<usize> {
        self.current_timestamp
    }

    pub fn update_time_cache(&self) -> &[f64] {
        &self.update_time_cache
    }

    pub fn region_count(&self) -> Option<&RegionCount> {
        self.region_count.as_deref()
    }

    pub fn query_data(&self) -> Option<&QueryData> {
        self.query_data.as_ref()
    }
}