Skip to content

web search done right

21.1 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/>.

mod sidebar;
mod widget;

use std::future::Future;
use std::sync::Arc;
use std::time::Instant;

use itertools::{intersperse, Itertools};
use url::Url;

use ahash::AHashMap as HashMap;

use crate::bangs::{Bang, BangHit};
use crate::collector::{self, approx_count};
use crate::config::{ApiConfig, ApiSpellCheck, ApiThresholds, CollectorConfig, WidgetsConfig};
use crate::distributed::cluster::Cluster;
use crate::enum_map::EnumMap;
use crate::image_store::Image;
use crate::models::dual_encoder::DualEncoder;
use crate::ranking::models::cross_encoder::CrossEncoderModel;
use crate::ranking::pipeline::{PrecisionRankingWebpage, RankableWebpage, RecallRankingWebpage};
use crate::ranking::{
    bitvec_similarity, inbound_similarity, SignalCalculation, SignalCoefficients, SignalEnum,
    SignalScore,
};
use crate::search_prettifier::{DisplayedSidebar, DisplayedWebpage, HighlightedSpellCorrection};
use crate::webgraph::remote::RemoteWebgraph;
use crate::webgraph::EdgeLimit;
use crate::webpage::html::links::RelFlags;
use crate::widgets::{Widget, Widgets};
use crate::{
    bangs::Bangs,
    collector::BucketCollector,
    ranking::{models::lambdamart::LambdaMART, pipeline::RankingPipeline},
};
use crate::{query, webgraph, Result};
use web_spell::SpellChecker;

use self::sidebar::SidebarManager;
use self::widget::WidgetManager;

use super::{distributed, ScoredWebpagePointer, SearchQuery, SearchResult, WebsitesResult};

const NUM_PIPELINE_RANKING_RESULTS: usize = 300;

impl RankableWebpage for ScoredWebpagePointer {
    fn set_raw_score(&mut self, score: f64) {
        self.as_ranking_mut().set_raw_score(score);
    }

    fn unboosted_score(&self) -> f64 {
        self.as_ranking().unboosted_score()
    }

    fn boost(&self) -> f64 {
        self.as_ranking().boost()
    }

    fn set_boost(&mut self, boost: f64) {
        self.as_ranking_mut().set_boost(boost)
    }

    fn as_local_recall(&self) -> &crate::ranking::pipeline::LocalRecallRankingWebpage {
        self.as_ranking().as_local_recall()
    }

    fn signals(&self) -> &EnumMap<SignalEnum, SignalCalculation> {
        self.as_ranking().signals()
    }

    fn signals_mut(&mut self) -> &mut EnumMap<SignalEnum, SignalCalculation> {
        self.as_ranking_mut().signals_mut()
    }
}

impl collector::Doc for ScoredWebpagePointer {
    fn score(&self) -> f64 {
        RankableWebpage::score(self)
    }

    fn hashes(&self) -> collector::Hashes {
        self.as_ranking().hashes()
    }
}

pub fn add_ranking_signals(
    websites: &mut [DisplayedWebpage],
    pointers: &[ScoredWebpagePointer],
    coeffs: &SignalCoefficients,
) {
    for (website, pointer) in websites.iter_mut().zip(pointers.iter()) {
        let mut signals = std::collections::HashMap::new();

        for signal in SignalEnum::all() {
            if let Some(signal_value) = pointer.as_ranking().signals().get(signal) {
                signals.insert(
                    signal.into(),
                    SignalScore {
                        value: signal_value.score,
                        coefficient: coeffs.get(&signal),
                    },
                );
            }
        }

        website.ranking_signals = Some(signals);
    }
}

#[derive(Default)]
pub struct Config {
    pub thresholds: ApiThresholds,
    pub widgets: WidgetsConfig,
    pub collector: CollectorConfig,
    pub spell_check: Option<ApiSpellCheck>,
}

impl From<ApiConfig> for Config {
    fn from(conf: ApiConfig) -> Self {
        Self {
            thresholds: conf.thresholds,
            widgets: conf.widgets,
            collector: conf.collector,
            spell_check: conf.spell_check,
        }
    }
}

pub trait Graph {
    fn batch_raw_ingoing_hosts(
        &self,
        nodes: &[webgraph::NodeID],
        limit: EdgeLimit,
    ) -> impl Future<Output = Vec<Vec<webgraph::SmallEdge>>>;
}

impl Graph for RemoteWebgraph {
    async fn batch_raw_ingoing_hosts(
        &self,
        nodes: &[webgraph::NodeID],
        limit: EdgeLimit,
    ) -> Vec<Vec<webgraph::SmallEdge>> {
        self.batch_search(
            nodes
                .iter()
                .map(|n| webgraph::query::HostBacklinksQuery::new(*n).with_limit(limit))
                .collect(),
        )
        .await
        .unwrap_or_default()
    }
}

impl Graph for webgraph::Webgraph {
    async fn batch_raw_ingoing_hosts(
        &self,
        nodes: &[webgraph::NodeID],
        limit: EdgeLimit,
    ) -> Vec<Vec<webgraph::SmallEdge>> {
        nodes
            .iter()
            .map(|n| {
                self.search(&webgraph::query::HostBacklinksQuery::new(*n).with_limit(limit))
                    .unwrap_or_default()
            })
            .collect()
    }
}

impl<T> Graph for Arc<T>
where
    T: Graph,
{
    fn batch_raw_ingoing_hosts(
        &self,
        nodes: &[webgraph::NodeID],
        limit: EdgeLimit,
    ) -> impl Future<Output = Vec<Vec<webgraph::SmallEdge>>> {
        self.as_ref().batch_raw_ingoing_hosts(nodes, limit)
    }
}

impl<T> bitvec_similarity::Graph for T
where
    T: Graph,
{
    async fn batch_ingoing(&self, nodes: &[webgraph::NodeID]) -> Vec<Vec<webgraph::NodeID>> {
        self.batch_raw_ingoing_hosts(nodes, EdgeLimit::Limit(512))
            .await
            .into_iter()
            .map(|edges| {
                edges
                    .into_iter()
                    .filter(|edge| !edge.rel_flags.contains(RelFlags::NOFOLLOW))
                    .map(|edge| edge.from)
                    .collect()
            })
            .collect()
    }
}

pub struct ApiSearcher<S, G> {
    distributed_searcher: Arc<S>,
    sidebar_manager: Option<SidebarManager>,
    cross_encoder: Option<Arc<CrossEncoderModel>>,
    lambda_model: Option<Arc<LambdaMART>>,
    dual_encoder: Option<Arc<DualEncoder>>,
    bangs: Bangs,
    collector_config: CollectorConfig,
    widget_manager: WidgetManager,
    spell_checker: Option<SpellChecker>,
    webgraph: Option<G>,
}

impl<S, G> ApiSearcher<S, G>
where
    S: distributed::SearchClient,
    G: Graph,
{
    pub async fn new<C>(
        dist_searcher: S,
        cluster: Option<Arc<Cluster>>,
        bangs: Bangs,
        config: C,
    ) -> Self
    where
        C: Into<Config>,
    {
        let config: Config = config.into();
        let dist_searcher = Arc::new(dist_searcher);
        let sidebar_manager = match cluster {
            Some(cluster) => Some(SidebarManager::new(cluster, config.thresholds.clone()).await),
            None => None,
        };

        let widget_manager = WidgetManager::new(Widgets::new(config.widgets).unwrap());

        Self {
            distributed_searcher: dist_searcher,
            sidebar_manager,
            cross_encoder: None,
            lambda_model: None,
            dual_encoder: None,
            bangs,
            collector_config: config.collector,
            widget_manager,
            spell_checker: config
                .spell_check
                .map(|c| SpellChecker::open(c.path, c.correction_config).unwrap()),
            webgraph: None,
        }
    }

    pub fn with_cross_encoder(mut self, cross_encoder: CrossEncoderModel) -> Self {
        self.cross_encoder = Some(Arc::new(cross_encoder));
        self
    }

    pub fn with_dual_encoder(mut self, dual_encoder: DualEncoder) -> Self {
        self.dual_encoder = Some(Arc::new(dual_encoder));
        self
    }

    pub fn with_lambda_model(mut self, lambda_model: LambdaMART) -> Self {
        self.lambda_model = Some(Arc::new(lambda_model));
        self
    }

    pub fn with_webgraph(mut self, webgraph: G) -> Self {
        self.webgraph = Some(webgraph);
        self
    }

    async fn check_bangs(&self, query: &SearchQuery) -> Result<Option<BangHit>> {
        let parsed_terms = query::parser::parse(&query.query)?;

        if parsed_terms.iter().any(|term| match term {
            query::parser::Term::PossibleBang { prefix: _, bang } => bang.is_empty(),
            _ => false,
        }) {
            let q: String = intersperse(
                parsed_terms
                    .iter()
                    .filter(|term| !matches!(term, query::parser::Term::PossibleBang { .. }))
                    .map(|term| term.to_string()),
                " ".to_string(),
            )
            .collect();

            let mut query = query.clone();
            query.query = urlencoding::encode(&q).into_owned();

            let res = self.search_websites(&query).await?;

            return Ok(res.webpages.first().map(|webpage| BangHit {
                bang: Bang {
                    category: None,
                    sub_category: None,
                    domain: None,
                    ranking: None,
                    site: None,
                    tag: String::new(),
                    url: webpage.url.clone(),
                },
                redirect_to: Url::parse(&webpage.url).unwrap().into(),
            }));
        }

        Ok(self.bangs.get(&parsed_terms))
    }

    pub async fn widget(&self, query: &str) -> Option<Widget> {
        self.widget_manager.widget(query).await
    }

    pub async fn sidebar(&self, query: &str) -> Option<DisplayedSidebar> {
        match &self.sidebar_manager {
            Some(sidebar_manager) => sidebar_manager.sidebar(query).await,
            None => None,
        }
    }

    pub fn spell_check(&self, query: &str) -> Option<HighlightedSpellCorrection> {
        let query = query.to_lowercase();

        let terms = query::parser::parse(&query).ok()?;

        let simple_query = terms
            .clone()
            .into_iter()
            .filter_map(|term| match term {
                query::parser::Term::SimpleOrPhrase(query::parser::SimpleOrPhrase::Simple(t)) => {
                    Some(String::from(t))
                }
                _ => None,
            })
            .join(" ");

        let corrections = self
            .spell_checker
            .as_ref()
            .and_then(|s| s.correct(&simple_query, &whatlang::Lang::Eng))?;

        let correction_map: HashMap<String, String> = corrections
            .terms
            .into_iter()
            .filter_map(|t| match t {
                web_spell::CorrectionTerm::Corrected { orig, correction } => {
                    Some((orig, correction))
                }
                web_spell::CorrectionTerm::NotCorrected(_) => None,
            })
            .collect();

        let mut correction = web_spell::Correction::empty(query);

        for term in terms {
            match term {
                query::parser::Term::SimpleOrPhrase(query::parser::SimpleOrPhrase::Simple(t)) => {
                    if let Some(term_correction) = correction_map.get(t.as_str()) {
                        correction.push(web_spell::CorrectionTerm::Corrected {
                            orig: String::from(t),
                            correction: term_correction.to_string(),
                        });
                    } else {
                        correction.push(web_spell::CorrectionTerm::NotCorrected(String::from(t)));
                    }
                }
                _ => {
                    correction.push(web_spell::CorrectionTerm::NotCorrected(term.to_string()));
                }
            }
        }

        Some(HighlightedSpellCorrection::from(correction))
    }

    async fn retrieve_webpages(
        &self,
        query: &str,
        top_websites: &[ScoredWebpagePointer],
    ) -> Vec<PrecisionRankingWebpage> {
        self.distributed_searcher
            .retrieve_webpages(top_websites, query)
            .await
    }

    async fn inbound_vecs(&self, ids: &[webgraph::NodeID]) -> Vec<bitvec_similarity::BitVec> {
        match self.webgraph.as_ref() {
            Some(webgraph) => bitvec_similarity::BitVec::batch_new_for(ids, webgraph).await,
            None => vec![bitvec_similarity::BitVec::default(); ids.len()],
        }
    }

    async fn combine_results(
        &self,
        query: &SearchQuery,
        initial_results: Vec<distributed::InitialSearchResultShard>,
    ) -> (Vec<ScoredWebpagePointer>, bool) {
        let mut collector =
            BucketCollector::new(NUM_PIPELINE_RANKING_RESULTS, self.collector_config.clone());

        let initial_host_nodes = initial_results
            .iter()
            .flat_map(|r| r.local_result.websites.iter())
            .map(|r| *r.host_id())
            .collect::<Vec<_>>();

        let host_nodes = initial_host_nodes.into_iter().unique().collect::<Vec<_>>();

        let inbound_vecs = if !query.fetch_backlinks() {
            HashMap::default()
        } else {
            self.inbound_vecs(&host_nodes)
                .await
                .into_iter()
                .zip_eq(host_nodes)
                .map(|(v, n)| (n, v))
                .collect::<HashMap<_, _>>()
        };

        let mut num_results = 0;

        for result in initial_results {
            num_results += result.local_result.websites.len();
            for website in result.local_result.websites {
                let inbound = inbound_vecs
                    .get(website.host_id())
                    .cloned()
                    .unwrap_or_default();
                let pointer = distributed::ScoredWebpagePointer {
                    website: RecallRankingWebpage::new(website, inbound),
                    shard: result.shard,
                };

                collector.insert(pointer);
            }
        }

        let has_more = query.offset() + query.num_results() < num_results;

        let res = collector
            .into_sorted_vec(true)
            .into_iter()
            .take(NUM_PIPELINE_RANKING_RESULTS)
            .collect::<Vec<_>>();

        (res, has_more)
    }

    async fn inbound_scorer(&self, query: &SearchQuery) -> inbound_similarity::Scorer {
        if !query.fetch_backlinks() {
            return inbound_similarity::Scorer::empty();
        }

        match self.webgraph.as_ref() {
            Some(webgraph) => {
                let host_rankings = query.host_rankings();

                let liked: Vec<_> = host_rankings
                    .liked
                    .iter()
                    .filter_map(|n| {
                        Url::parse(n)
                            .or_else(|_| Url::parse(&format!("http://{}", n)))
                            .ok()
                    })
                    .map(|n| webgraph::Node::from(n).into_host().id())
                    .collect();

                let disliked: Vec<_> = host_rankings
                    .disliked
                    .iter()
                    .filter_map(|n| {
                        Url::parse(n)
                            .or_else(|_| Url::parse(&format!("http://{}", n)))
                            .ok()
                    })
                    .map(|n| webgraph::Node::from(n).into_host().id())
                    .collect();
                inbound_similarity::Scorer::new(webgraph, &liked, &disliked, false).await
            }
            None => inbound_similarity::Scorer::empty(),
        }
    }

    async fn search_websites_approx_offsets(&self, query: &SearchQuery) -> Result<WebsitesResult> {
        let start = Instant::now();

        let search_query = SearchQuery {
            num_results: query.num_results + 1,
            ..query.clone()
        };

        let results = self
            .distributed_searcher
            .search_initial(&search_query)
            .await;

        let has_more_results = results
            .iter()
            .any(|res| res.local_result.websites.len() > query.num_results());

        let num_docs = results
            .iter()
            .map(|result| result.local_result.num_websites)
            .fold(approx_count::Count::Exact(0), |acc, count| acc + count);

        let (combined, _) = self.combine_results(query, results).await;
        let combined: Vec<_> = combined.into_iter().take(query.num_results).collect();

        let mut retrieved_webpages: Vec<_> = self
            .retrieve_webpages(&query.query, &combined)
            .await
            .into_iter()
            .map(|webpage| webpage.into_retrieved_webpage())
            .map(|webpage| DisplayedWebpage::new(webpage, query))
            .collect();

        if query.return_ranking_signals {
            add_ranking_signals(
                &mut retrieved_webpages,
                &combined,
                &query.signal_coefficients(),
            );
        }

        let search_duration_ms = start.elapsed().as_millis();

        Ok(WebsitesResult {
            num_hits: num_docs,
            webpages: retrieved_webpages,
            search_duration_ms,
            has_more_results,
        })
    }

    async fn search_websites(&self, query: &SearchQuery) -> Result<WebsitesResult> {
        let start = Instant::now();

        if query.is_empty() {
            return Err(distributed::Error::EmptyQuery.into());
        }

        if query.offset() + query.num_results() > NUM_PIPELINE_RANKING_RESULTS {
            // this is most likely a bot
            // let's not spend too much time correctly offsetting+ranking results
            return self.search_websites_approx_offsets(query).await;
        }

        let search_query = SearchQuery {
            num_results: NUM_PIPELINE_RANKING_RESULTS,
            page: 0,
            ..query.clone()
        };

        let initial_results = self
            .distributed_searcher
            .search_initial(&search_query)
            .await;

        let num_docs = initial_results
            .iter()
            .map(|result| result.local_result.num_websites)
            .fold(approx_count::Count::Exact(0), |acc, count| acc + count);

        let (top_websites, has_more_results) = self.combine_results(query, initial_results).await;

        let inbound_scorer = self.inbound_scorer(query).await;

        let pipeline: RankingPipeline<ScoredWebpagePointer> =
            RankingPipeline::<ScoredWebpagePointer>::recall_stage(
                query,
                inbound_scorer,
                self.lambda_model.clone(),
                self.dual_encoder.clone(),
            );

        let top_websites = pipeline.apply(top_websites, query);

        let mut retrieved_webpages = self.retrieve_webpages(&query.query, &top_websites).await;

        if let Some(cross_encoder) = self.cross_encoder.clone() {
            if query.page < 2 {
                let query = SearchQuery {
                    page: 1,
                    ..query.clone()
                };

                let reranking_pipeline: RankingPipeline<PrecisionRankingWebpage> =
                    RankingPipeline::<PrecisionRankingWebpage>::reranker(
                        &query,
                        cross_encoder,
                        self.lambda_model.clone(),
                    );

                retrieved_webpages = reranking_pipeline.apply(retrieved_webpages, &query);
            }
        }

        let mut retrieved_webpages: Vec<_> = retrieved_webpages
            .into_iter()
            .map(|webpage| webpage.into_retrieved_webpage())
            .map(|webpage| DisplayedWebpage::new(webpage, query))
            .collect();

        if retrieved_webpages.len() != top_websites.len() {
            return Err(distributed::Error::SearchFailed.into());
        }

        if query.return_ranking_signals {
            add_ranking_signals(
                &mut retrieved_webpages,
                &top_websites,
                &query.signal_coefficients(),
            );
        }

        let search_duration_ms = start.elapsed().as_millis();

        Ok(WebsitesResult {
            num_hits: num_docs,
            webpages: retrieved_webpages,
            search_duration_ms,
            has_more_results,
        })
    }

    pub async fn search(&self, query: &SearchQuery) -> Result<SearchResult> {
        if let Some(bang) = self.check_bangs(query).await? {
            return Ok(SearchResult::Bang(Box::new(bang)));
        }

        Ok(SearchResult::Websites(self.search_websites(query).await?))
    }

    pub async fn get_entity_image(
        &self,
        image_id: &str,
        max_height: Option<u64>,
        max_width: Option<u64>,
    ) -> Result<Option<Image>> {
        match &self.sidebar_manager {
            Some(sidebar_manager) => {
                sidebar_manager
                    .get_entity_image(image_id, max_height, max_width)
                    .await
            }
            None => Ok(None),
        }
    }

    pub async fn warmup(&self, queries: impl Iterator<Item = String>) {
        for query in queries {
            self.search_websites(&SearchQuery {
                query,
                ..Default::default()
            })
            .await
            .ok();
        }
    }
}