Repository: meilisearch/meilisearch
File: crates/milli/src/update/new/words_prefix_docids.rs (Rust)

Code before:
                    // Is prefix for another thread?
                    if prefix_index % thread_count != thread_id {
                        continue;
                    }

                    let mut bitmaps_bytes_at_positions = HashMap::new();
                    let mut prev_pos = None;
                    for result in self
                        .database
                        .remap_data_type::<Bytes>()
                        .prefix_iter(&rtxn, prefix.as_bytes())?
                    {
                        let (key, bitmap_bytes) = result?;
                        let (_word, pos) =
                            StrBEU16Codec::bytes_decode(key).map_err(Error::Decoding)?;

                        // Track positions with no corresponding bitmap bytes,
                        // these means that the prefix no longer exists in the database
                        // and must, therefore, be removed from the index.
                        if let Some(prev_pos) = prev_pos {
                            // A range with the left bigger than the right bound results in an empty range.
                            for pos in prev_pos..pos {
                                // They are represented by an empty set of bitmaps.
                                bitmaps_bytes_at_positions.entry(pos).or_insert_with(Vec::new);
                            }
                        }

                        bitmaps_bytes_at_positions
                            .entry(pos)
                            .or_insert_with(Vec::new)
                            .push(bitmap_bytes);

                        prev_pos = Some(pos);
                    }

                    for (pos, bitmaps_bytes) in bitmaps_bytes_at_positions {
                        if bitmaps_bytes.is_empty() {
                            indexes.push(PrefixIntegerEntry {
                                prefix,
                                pos,
                                serialized_length: None,
                            });
                        } else {
                            let output = bitmaps_bytes
                                .into_iter()
                                .map(CboRoaringBitmapCodec::deserialize_from)
                                .union()?;
                            buffer.clear();
                            CboRoaringBitmapCodec::serialize_into_vec(&output, &mut buffer);
                            indexes.push(PrefixIntegerEntry {
                                prefix,

Review comment (suggestion):
What do you think about this @ManyTheFish. Previously, in the non-multi-threaded algorithm, we never deleted prefixes because we never created entries for positions that we did not encounter while looping over the words. Now we create an empty list of bitmaps in the HashMap and therefore enter the special case to delete (probably non-existing) prefix entries.

However, now that I think a bit more about this, I see two issues:
- Deleting non-existing entries in LMDB in the wtxn loop will do more useless IOs.
- I do not generate empty entries (tombstones) for positions that are higher than the highest I encounter. This means that we will never delete entries for a prefix at high positions that are more likely to disappear (i.e., a small number of documents with a lot of prefix far in a field).

What I propose is to use a BTreeMap or a Vec with all possible positions for a prefix (I think we have a maximum somewhere), perform the entire prefix loop, and fill the different _prefix at position_ lists of bitmaps without interruption. Once we are done, we go through the prefixes and verify that the ones that must be deleted actually exist before deleting them (writing the deletion in the operation file). The advantage is that we perform all these checks in parallel, rather than in a single transaction loop.

Code after:
                    // Is prefix for another thread?
                    if prefix_index % thread_count != thread_id {
                        continue;
                    }

                    let mut bitmap_bytes_at_positions = HashMap::new();
                    for result in self
                        .database
                        .prefix_iter(&rtxn, prefix.as_bytes())?
                        .remap_types::<StrBEU16Codec, Bytes>()
                    {
                        let ((_word, pos), bitmap_bytes) = result?;
                        bitmap_bytes_at_positions
                            .entry(pos)
                            .or_insert_with(Vec::new)
                            .push(bitmap_bytes);
                    }

                    // We track positions with no corresponding bitmap bytes,
                    // these means that the prefix no longer exists in the database
                    // and must, therefore, be removed from the index.
                    for result in self
                        .prefix_database
                        .prefix_iter(&rtxn, prefix.as_bytes())?
                        .remap_types::<StrBEU16Codec, DecodeIgnore>()
                    {
                        let ((_word, pos), ()) = result?;
                        // They are represented by an empty set of bitmaps.
                        bitmap_bytes_at_positions.entry(pos).or_insert_with(Vec::new);
                    }

                    for (pos, bitmaps_bytes) in bitmap_bytes_at_positions {
                        if bitmaps_bytes.is_empty() {
                            indexes.push(PrefixIntegerEntry {
                                prefix,
                                pos,
                                serialized_length: None,
                            });
                        } else {
                            let output = bitmaps_bytes
                                .into_iter()
                                .map(CboRoaringBitmapCodec::deserialize_from)
                                .union()?;
                            buffer.clear();
                            CboRoaringBitmapCodec::serialize_into_vec(&output, &mut buffer);
                            indexes.push(PrefixIntegerEntry {
                                prefix,
                                pos,
                                serialized_length: Some(buffer.len()),
                            });
                            file.write_all(&buffer)?;