Skip to content

Open Source alternative to Algolia + Pinecone and an Easier-to-Use alternative to ElasticSearch ⚡ 🔍 ✨ Fast, typo tolerant, in-memory fuzzy Search Engine for building delightful search experiences

19.1 KB
Raw Blame
#include "facet_index.h"
#include <tokenizer.h>
#include "string_utils.h"
#include "array_utils.h"

void facet_index_t::initialize(const std::string& field) {
    const auto facet_field_map_it = facet_field_map.find(field);
    if(facet_field_map_it == facet_field_map.end()) {
        // NOTE: try_emplace is needed to construct the value object in-place without calling the destructor
        facet_field_map.try_emplace(field);
    }
}

void facet_index_t::insert(const std::string& field_name,
                           std::unordered_map<facet_value_id_t, std::vector<uint32_t>, facet_value_id_t::Hash>& fvalue_to_seq_ids,
                           std::unordered_map<uint32_t, std::vector<facet_value_id_t>>& seq_id_to_fvalues,
                           bool is_string_field) {
    
    const auto facet_field_map_it = facet_field_map.find(field_name);
    if(facet_field_map_it == facet_field_map.end()) {
        return; // field is not initialized or dropped
    }

    auto& facet_index = facet_field_map_it->second;
    auto& fvalue_index = facet_index.fvalue_seq_ids;
    auto fhash_index = facet_index.seq_id_hashes;

    for(const auto& seq_id_fvalues: seq_id_to_fvalues) {
        auto seq_id = seq_id_fvalues.first;
        std::vector<uint32_t> real_facet_ids;
        real_facet_ids.reserve(seq_id_fvalues.second.size());

        for(const auto& fvalue: seq_id_fvalues.second) {
            uint32_t facet_id = fvalue.facet_id;
            const auto& fvalue_index_it = fvalue_index.find(fvalue.facet_value);

            if(fvalue.facet_id == UINT32_MAX) {
                // float, int32 & bool will provide facet_id as their own numerical values
                facet_id = (fvalue_index_it == fvalue_index.end()) ? ++next_facet_id : fvalue_index_it->second.facet_id;

                if(!is_string_field) {
                    int64_t val = std::stoll(fvalue.facet_value);
                    facet_index.fhash_to_int64_map[facet_id] = val;
                }
            }

            real_facet_ids.push_back(facet_id);

            auto seq_ids_it = fvalue_to_seq_ids.find(fvalue);
            if(seq_ids_it == fvalue_to_seq_ids.end()) {
                continue;
            }

            auto& seq_ids = seq_ids_it->second;

            if(fvalue_index_it == fvalue_index.end()) {
                facet_id_seq_ids_t fis;
                fis.facet_id = facet_id;

                if(facet_index.has_value_index) {
                    fis.seq_ids = ids_t::create(seq_ids);
                    auto new_count = ids_t::num_ids(fis.seq_ids);
                    fis.facet_count_it = facet_index.counts.emplace(fvalue.facet_value, new_count, facet_id);
                }

                fvalue_index.emplace(fvalue.facet_value, fis);
            } else if(facet_index.has_value_index) {
                for(const auto id : seq_ids) {
                    ids_t::upsert(fvalue_index_it->second.seq_ids, id);
                }

                auto facet_count_it = fvalue_index_it->second.facet_count_it;

                if(facet_count_it->facet_id == facet_id) {
                    auto facet_count_node = facet_index.counts.extract(facet_count_it);
                    facet_count_node.value().count = ids_t::num_ids(fvalue_index_it->second.seq_ids);
                    facet_index.counts.insert(std::move(facet_count_node));
                } else {
                    LOG(ERROR) << "Wrong reference stored for facet " << fvalue.facet_value << " with facet_id " << facet_id;
                }
            }

            fvalue_to_seq_ids.erase(fvalue);
        }

        if(facet_index.has_hash_index && fhash_index != nullptr) {
            fhash_index->upsert(seq_id, real_facet_ids);
        }
    }
}

bool facet_index_t::contains(const std::string& field_name) {
    const auto& facet_field_it = facet_field_map.find(field_name);
    if(facet_field_it == facet_field_map.end()) {
        return false;
    }

    return true;
}

void facet_index_t::erase(const std::string& field_name) {
    facet_field_map.erase(field_name);
}

void facet_index_t::get_stringified_value(const nlohmann::json& value, const field& afield,
                                          std::vector<std::string>& values) {
    if(afield.is_int32()) {
        int32_t raw_val = value.get<int32_t>();
        values.push_back(std::to_string(raw_val));
    }
    else if(afield.is_int64()) {
        int64_t raw_val = value.get<int64_t>();
        values.push_back(std::to_string(raw_val));
    }
    else if(afield.is_string()) {
        const std::string& raw_val = value.get<std::string>().substr(0, 100);
        values.push_back(raw_val);
    }
    else if(afield.is_float()) {
        float raw_val = value.get<float>();
        values.push_back(StringUtils::float_to_str(raw_val));
    }
    else if(afield.is_bool()) {
        bool raw_val = value.get<bool>();
        auto str_val = (raw_val == 1) ? "true" : "false";
        values.emplace_back(str_val);
    }
}

void facet_index_t::get_stringified_values(const nlohmann::json& document, const field& afield,
                                           std::vector<std::string>& values) {
    bool is_array = afield.is_array();

    if(!is_array) {
        return get_stringified_value(document[afield.name], afield, values);
    } else {
        const auto& field_values = document[afield.name];
        for(size_t i = 0; i < field_values.size(); i++) {
            get_stringified_value(field_values[i], afield, values);
        }
    }
}

void facet_index_t::remove(const nlohmann::json& doc, const field& afield, const uint32_t seq_id) {
    const auto facet_field_it = facet_field_map.find(afield.name);
    if(facet_field_it == facet_field_map.end()) {
        return ;
    }

    auto& facet_index_map = facet_field_it->second.fvalue_seq_ids;
    std::vector<std::string> dead_fvalues;
    std::vector<std::string> values;
    get_stringified_values(doc, afield, values);

    for(const auto& value: values) {
        auto fvalue_it = facet_index_map.find(value);
        if(fvalue_it == facet_index_map.end()) {
            continue;
        }

        void*& ids = fvalue_it->second.seq_ids;
        if(ids && ids_t::contains(ids, seq_id)) {
            ids_t::erase(ids, seq_id);
            auto new_count = ids_t::num_ids(ids);
            auto& counts = facet_field_it->second.counts;

            if(new_count == 0) {
                ids_t::destroy_list(ids);
                dead_fvalues.push_back(fvalue_it->first);

                // remove from int64 lookup map first
                auto& fhash_int64_map = facet_field_it->second.fhash_to_int64_map;
                uint32_t fhash = fvalue_it->second.facet_id;
                fhash_int64_map.erase(fhash);

                counts.erase(fvalue_it->second.facet_count_it);
            } else {
                // update count
                auto count_node = counts.extract(fvalue_it->second.facet_count_it);
                count_node.value().count = ids_t::num_ids(ids);
                counts.insert(std::move(count_node));
            }
        }
    }

    for(auto& dead_fvalue: dead_fvalues) {
        facet_index_map.erase(dead_fvalue);
    }

    auto& seq_id_hashes = facet_field_it->second.seq_id_hashes;
    seq_id_hashes->erase(seq_id);
}

size_t facet_index_t::get_facet_count(const std::string& field_name) {
    const auto it = facet_field_map.find(field_name);

    if(it == facet_field_map.end()) {
        return 0;
    }

    return has_hash_index(field_name) ? it->second.seq_id_hashes->num_ids() :  it->second.counts.size();
}

//returns the count of matching seq_ids from result array
size_t facet_index_t::intersect(facet& a_facet, const field& facet_field,
                                bool has_facet_query,
                                bool estimate_facets,
                                size_t facet_sample_interval,
                                const std::vector<std::vector<std::string>>& fvalue_searched_tokens,
                                const std::vector<char>& symbols_to_index, const std::vector<char>& token_separators,
                                const uint32_t* result_ids, size_t result_ids_len,
                                size_t max_facet_count, std::map<std::string, docid_count_t>& found,
                                bool is_wildcard_no_filter_query, const std::string& sort_order) {
    //LOG (INFO) << "intersecting field " << field;

    const auto& facet_field_it = facet_field_map.find(a_facet.field_name);
    if(facet_field_it == facet_field_map.end()) {
        return 0;
    }

    const auto& facet_index_map = facet_field_it->second.fvalue_seq_ids;
    const auto& counter_list = facet_field_it->second.counts;

     //LOG(INFO) << "fvalue_seq_ids size " << facet_index_map.size() << " , counts size " << counter_list.size();

    // We look 2 * max_facet_count when keyword search / filtering is involved to ensure that we
    // try and pick the actual top facets by count.
    size_t max_facets = is_wildcard_no_filter_query ? std::min((size_t)max_facet_count, counter_list.size()) :
                        std::min((size_t)2 * max_facet_count, counter_list.size());

    auto intersect_fn = [&] (std::multiset<facet_count_t>::const_iterator facet_count_it) {
        uint32_t count = 0;
        uint32_t doc_id = 0;
        if(has_facet_query) {
            bool found_search_token = false;
            auto facet_str = facet_count_it->facet_value;
            std::vector<std::string> facet_tokens;
            if(facet_field.is_string()) {
                Tokenizer(facet_str, true, false, facet_field.locale,
                          symbols_to_index, token_separators).tokenize(facet_tokens);
            } else {
                facet_tokens.push_back(facet_str);
            }

            for(const auto& searched_tokens : fvalue_searched_tokens) {
                bool found_all_search_tokens = true;
                for (const auto &searched_token: searched_tokens) {
                    bool facet_tokens_found = false;
                    for(const auto& token : facet_tokens) {
                        if (token.compare(0, searched_token.size(), searched_token) == 0) {
                            facet_tokens_found = true;
                            break;
                        }
                    }
                    if(!facet_tokens_found) {
                        found_all_search_tokens = false;
                    }
                }

                if (found_all_search_tokens) {
                    a_facet.fvalue_tokens[facet_count_it->facet_value] = searched_tokens;
                    found_search_token = true;
                    break;
                }
            }

            if(!found_search_token) {
                return;
            }
        }

        auto ids = facet_index_map.at(facet_count_it->facet_value).seq_ids;
        if (!ids) {
            return;
        }

        if (is_wildcard_no_filter_query) {
            count = facet_count_it->count;
        } else {
            auto val_count = ids_t::num_ids(ids);
            bool estimate_facet_count = (estimate_facets && val_count > 300);
            count = ids_t::intersect_count(ids, result_ids, result_ids_len, estimate_facet_count, facet_sample_interval);
        }

        if (count) {
            doc_id = ids_t::first_id(ids);
            found[facet_count_it->facet_value] = {doc_id, count};
        }
    };

    if(sort_order.empty()) {
        for (auto facet_count_it = counter_list.begin(); facet_count_it != counter_list.end();
             ++facet_count_it) {
            //LOG(INFO) << "checking ids in facet_value " << facet_count.facet_value << " having total count "
            //           << facet_count.count << ", is_wildcard_no_filter_query: " << is_wildcard_no_filter_query;

            intersect_fn(facet_count_it);
            if (found.size() == max_facets) {
                break;
            }
        }
    } else {
        if(sort_order == "asc") {
            for(auto facet_index_map_it = facet_index_map.begin();
                facet_index_map_it != facet_index_map.end(); ++facet_index_map_it) {

                intersect_fn(facet_index_map_it->second.facet_count_it);
                if (found.size() == max_facets) {
                    break;
                }
            }
        } else if(sort_order == "desc") {
            for(auto facet_index_map_it = facet_index_map.rbegin();
                facet_index_map_it != facet_index_map.rend(); ++facet_index_map_it) {

                intersect_fn(facet_index_map_it->second.facet_count_it);
                if (found.size() == max_facets) {
                    break;
                }
            }
        }
    }
    
    return found.size();
}

facet_index_t::~facet_index_t() {
    facet_field_map.clear();    
}

// used for migrating string and int64 facets
size_t facet_index_t::get_facet_indexes(const std::string& field_name,
    std::map<uint32_t, std::vector<uint32_t>>& seqid_countIndexes) {

  const auto& facet_field_it = facet_field_map.find(field_name);
    if(facet_field_it == facet_field_map.end()) {
        return 0;
    }

    auto& facet_index_map = facet_field_it->second.fvalue_seq_ids;

    std::vector<uint32_t> id_list;

    for(auto facet_index_map_it = facet_index_map.begin(); facet_index_map_it != facet_index_map.end(); ++facet_index_map_it) {
        //auto ids = facet_index_map_it->seq_ids;
        auto ids = facet_index_map_it->second.seq_ids;
        if(!ids) {
            continue;
        }

        ids_t::uncompress(ids, id_list);

        // emplacing seq_id => next_facet_id
        for(const auto& id : id_list) {
            //seqid_countIndexes[id].emplace_back(facet_index_map_it->facet_id);
            seqid_countIndexes[id].emplace_back(facet_index_map_it->second.facet_id);
        }

        id_list.clear();
    }

    return seqid_countIndexes.size();
}

void facet_index_t::handle_index_change(const std::string& field_name, size_t total_num_docs,
                                        size_t facet_index_threshold, size_t facet_count) {

    // Low cardinality fields will have only value based facet index. Once a field becomes a high cardinality
    // field (exceeding FACET_INDEX_THRESHOLD), we will create a hash based index and populate it.
    // If a field is an id-like field (cardinality_ratio < 5) we will then remove value based index.

    auto& facet_index = facet_field_map.at(field_name);
    posting_list_t*& fhash_index = facet_index.seq_id_hashes;

    if(fhash_index == nullptr && (facet_count > facet_index_threshold) && total_num_docs < 1000000) {
        fhash_index = new posting_list_t(256);
        std::map<uint32_t, std::vector<uint32_t>> seq_id_index_map;

        if(get_facet_indexes(field_name, seq_id_index_map)) {
            for(const auto& kv : seq_id_index_map) {
                fhash_index->upsert(kv.first, kv.second);
            }
        }

        seq_id_index_map.clear();

        facet_index.has_hash_index = true;

        auto cardinality_ratio = total_num_docs / facet_count;

        if(cardinality_ratio != 0 && cardinality_ratio < 5) {
            // drop the value index for this field
            auto& fvalue_seq_ids = facet_index.fvalue_seq_ids;
            for(auto it = fvalue_seq_ids.begin(); it != fvalue_seq_ids.end(); ++it) {
                ids_t::destroy_list(it->second.seq_ids);
            }
            fvalue_seq_ids.clear();
            facet_index.counts.clear();
            facet_index.has_value_index = false;
        }
    }
}

bool facet_index_t::has_hash_index(const std::string &field_name) {
    auto facet_index_it = facet_field_map.find(field_name);
    return facet_index_it != facet_field_map.end() && facet_index_it->second.has_hash_index;
}

bool facet_index_t::has_value_index(const std::string &field_name) {
    auto facet_index_it = facet_field_map.find(field_name);
    return facet_index_it != facet_field_map.end() && facet_index_it->second.has_value_index;
}

posting_list_t* facet_index_t::get_facet_hash_index(const std::string &field_name) {
    auto facet_index_it = facet_field_map.find(field_name);
    if(facet_index_it != facet_field_map.end()) {
        return facet_index_it->second.seq_id_hashes;
    }
    return nullptr;
}

const spp::sparse_hash_map<uint32_t , int64_t >& facet_index_t::get_fhash_int64_map(const std::string& field_name) {
    static const spp::sparse_hash_map<uint32_t, int64_t> empty_map{};
    const auto facet_field_map_it = facet_field_map.find(field_name);

    if(facet_field_map_it == facet_field_map.end()) {
        return empty_map; // field is not initialized or dropped
    }

    const auto& facet_index = facet_field_map_it->second;
    return facet_index.fhash_to_int64_map;
}

bool facet_index_t::facet_value_exists(const std::string& field_name, const std::string& fvalue) {
    const auto facet_field_map_it = facet_field_map.find(field_name);
    if(facet_field_map_it == facet_field_map.end()) {
        return false;
    }

    const auto& facet_index = facet_field_map_it->second;
    return facet_index.fvalue_seq_ids.find(fvalue) != facet_index.fvalue_seq_ids.end();
}

size_t facet_index_t::facet_val_num_ids(const string &field_name, const string &fvalue) {
    const auto facet_field_map_it = facet_field_map.find(field_name);
    if(facet_field_map_it == facet_field_map.end()) {
        return 0;
    }

    if(facet_field_map_it->second.fvalue_seq_ids.count(fvalue) == 0) {
        return 0;
    }

    auto seq_ids = facet_field_map_it->second.fvalue_seq_ids[fvalue].seq_ids;
    return seq_ids ?  ids_t::num_ids(seq_ids) : 0;
}

size_t facet_index_t::facet_node_count(const string &field_name, const string &fvalue) {
    const auto facet_field_map_it = facet_field_map.find(field_name);
    if(facet_field_map_it == facet_field_map.end()) {
        return 0;
    }

    if(facet_field_map_it->second.fvalue_seq_ids.count(fvalue) == 0) {
        return 0;
    }

    return facet_field_map_it->second.fvalue_seq_ids[fvalue].facet_count_it->count;
}

void facet_index_t::check_for_high_cardinality(const string& field_name, size_t total_num_docs) {
    // high cardinality or sparse facet fields must be dropped from value facet index
    const auto facet_field_map_it = facet_field_map.find(field_name);
    if(facet_field_map_it == facet_field_map.end()) {
        return ;
    }

    if(!facet_field_map_it->second.has_value_index) {
        return ;
    }

    size_t value_facet_threshold = 0.8 * total_num_docs;

    auto num_facet_values = facet_field_map_it->second.fvalue_seq_ids.size();
    bool is_sparse_field = false;

    if(total_num_docs > 10*1000) {
        size_t num_docs_with_facet = facet_field_map_it->second.seq_id_hashes->num_ids();
        if(num_docs_with_facet > 0 && num_docs_with_facet < 100) {
            is_sparse_field = true;
        }
    }

    if(num_facet_values > value_facet_threshold || is_sparse_field) {
        // if there are too many unique values, we will drop the value index
        auto& fvalue_seq_ids = facet_field_map_it->second.fvalue_seq_ids;
        for(auto it = fvalue_seq_ids.begin(); it != fvalue_seq_ids.end(); ++it) {
            ids_t::destroy_list(it->second.seq_ids);
            it->second.seq_ids = nullptr;
        }

        facet_field_map_it->second.counts.clear();
        facet_field_map_it->second.has_value_index = false;
        //LOG(INFO) << "Dropped value index for field " << field_name;
    }
}