Repository: meilisearch/meilisearch
File: crates/milli/src/search/facet/filter.rs (Rust)

Code before:
                                })
                                .into()))
                            }
                        }
                    })
                    .union()?;

                return Ok(docids);
            }
            Condition::StartsWith { keyword: _, word } => {
                // There are two algorithms:
                //
                // - The first one is recursive over levels.
                //   This is more efficient when the prefix is common among many values.
                //
                // - The second one looks directly at level 0 of the facet group database.
                //   This pessimistic approach is more efficient when the value is unique.
                //   It's used as a fallback.

                let value = crate::normalize_facet(word.value());

                let mut value2 = value.as_bytes().to_owned();
                if let Some(last) = value2.last_mut() {
                    if *last != 255 {
                        *last += 1;
                        if let Ok(value2) = String::from_utf8(value2) {
                            // The idea here is that "STARTS WITH baba" is the same as "baba <= value < babb".
                            // We just increase the last letter to find the upper bound.
                            // The result could be invalid utf8, so it can fallback.
                            let mut docids = RoaringBitmap::new();
                            find_docids_of_facet_within_bounds(
                                rtxn,
                                strings_db,
                                field_id,
                                &Included(&value),
                                &Excluded(&value2),
                                universe,
                                &mut docids,
                            )?;

                            return Ok(docids);
                        }
                    }
                }

                let base = FacetGroupKey { field_id, level: 0, left_bound: value.as_str() };
                let docids = strings_db
                    .prefix_iter(rtxn, &base)?
                    .map(|result| -> Result<RoaringBitmap> {
                        match result {
                            Ok((_facet_group_key, FacetGroupValue { bitmap, .. })) => Ok(bitmap),

Review comment (bug):
Since we increased a random byte, our string won't always be UTF-8 here.

I agree that LMDB works over random bytes, but this can definitely fail and should not force us to change the algorithm to something way slower on a large dataset.

I guess we should update `find_docids_of_facet_within_bounds` so it works with bytes or something 🤔 

Code after:
                                .into()))
                            }
                        }
                    })
                    .union()?;

                return Ok(docids);
            }
            Condition::StartsWith { keyword: _, word } => {
                // The idea here is that "STARTS WITH baba" is the same as "baba <= value < babb".
                // We just incremented the last letter to find the upper bound.
                // The upper bound may not be valid utf8, but lmdb doesn't care as it works over bytes.

                let value = crate::normalize_facet(word.value());
                let mut value2 = value.as_bytes().to_owned();

                let last = match value2.last_mut() {
                    Some(last) => last,
                    None => {
                        // The prefix is empty, so all documents that have the field will match.
                        return index
                            .exists_faceted_documents_ids(rtxn, field_id)
                            .map_err(|e| e.into());
                    }
                };

                if *last == u8::MAX {
                    // u8::MAX is a forbidden UTF-8 byte, we're guaranteed it cannot be sent through a filter to meilisearch, but just in case, we're going to return something
                    tracing::warn!(
                        "Found non utf-8 character in filter. That shouldn't be possible"
                    );
                    return Ok(RoaringBitmap::new());
                }
                *last += 1;

                // This is very similar to `heed::Bytes` but its `EItem` is `&[u8]` instead of `[u8]`
                struct BytesRef;
                impl<'a> BytesEncode<'a> for BytesRef {
                    type EItem = &'a [u8];

                    fn bytes_encode(
                        item: &'a Self::EItem,
                    ) -> std::result::Result<Cow<'a, [u8]>, heed::BoxedError> {
                        Ok(Cow::Borrowed(item))
                    }
                }

                let mut docids = RoaringBitmap::new();
                let bytes_db =
                    index.facet_id_string_docids.remap_key_type::<FacetGroupKeyCodec<BytesRef>>();
                find_docids_of_facet_within_bounds::<BytesRef>(