Bug: Discrepancy between MySQL/Python string sorting leads to incorrect histograms and cardinality estimates

### Environment Setup

MySQL: 8.0
MariaDB: 11.8
VIDEX: main

### Observed vs Expected Behavior

#### 1. Summary

A fundamental discrepancy exists between Python's default string sorting (binary/Unicode code point order) and MySQL/MariaDB's collation-aware string sorting. This causes all three histogram generation methods in VIDEX to produce incorrect results, leading to flawed bucket boundaries and inaccurate cardinality estimates.

#### 2. Root Cause

- **Database Sorting:** MySQL/MariaDB's string comparison is determined by the column's `charset` and `collation`. Collations can introduce complex rules, such as case-insensitivity, accent-insensitivity, and "natural sorting" for numbers within strings.
- **Python Sorting:** Python's built-in `sorted()` function defaults to lexicographical ordering based on Unicode code points, which is equivalent to a binary sort. It is unaware of database-specific collation rules.

This semantic mismatch becomes a problem when VIDEX uses Python-sorted values to construct SQL queries or interpret results from the database.

A simple example of this discrepancy:
```sql
-- This query may return 1 in MySQL/MariaDB with certain collations (e.g., utf8mb3_unicode_ci),
-- indicating the DB considers 'Category_155_Mouse' to be less than 'Category_1_Desk'.
SELECT 1 WHERE 'Category_155_Mouse' < 'Category_1_Desk' COLLATE utf8mb3_unicode_ci;
```
In Python, the expression `'Category_155_Mouse' < 'Category_1_Desk'` evaluates to `False`, directly contradicting the database's logic.

#### 3. Impact on VIDEX

This issue affects all histogram generation methods:

1. **Fetching Native Histograms:** When VIDEX ingests a histogram from the database engine, the bucket boundaries are sorted according to the DB's collation. However, VIDEX's `HistogramStats.find_nearest_key_pos` method uses Python's comparison logic to locate keys, leading to incorrect bucket lookups.

2. **Uniform Buckets (`videx_histogram._get_uniform_buckets`):** VIDEX samples data, sorts it in Python (`sorted(samples)`), and uses the sorted list to define bucket boundaries. It then generates SQL queries with these boundaries, for example:
```sql
-- This range is based on Python's sort order.
WHERE name > 'Category_155_Mouse' AND name < 'Category_1_Desk'
```
For a database using a collation where `'Category_1_Desk'` is smaller than `'Category_155_Mouse'`, this `WHERE` clause defines an empty set. This results in buckets with zero counts and incorrect cardinality estimates.

3. **Sampling-based Estimation:** Bucket intervals are constructed using Python's sort order. These intervals do not align with the database's actual data ordering, resulting in misaligned bucket boundaries and an inaccurate final histogram.

#### 4. Proposed Solution

To ensure consistency, we must align string comparison logic with the target database's collation.

1. **Introduce a `Comparator` Abstraction:**
- Create a unified string comparator class that is initialized with `charset`, `collation`, and `db_version`.
- It must provide two key methods:
- `compare(a: str, b: str) -> int`: Implements comparison logic that mirrors the target database collation.
- `sort(values: List[str]) -> List[str]`: Provides a stable sort based on the `compare` method.

2. **Integrate the Comparator:**
- Use this comparator for all string sorting and comparison operations within VIDEX, including:
- Sorting sampled data to create bucket boundaries.
- The `find_nearest_key_pos` lookup logic.
- Validating the order of boundaries when constructing `WHERE` clauses for SQL queries.

3. **Implementation Strategy:**
- **Primary Option:** Delegate sorting to the database itself via `ORDER BY ... COLLATE` to get a ground-truth ordering.
- **Alternative:** Use a library like `PyICU` to implement the `Comparator`, configuring its `Collator` to match the behavior of the target database collation.

#### 5. Reproduction Test Case

The code for reproduction is attached.

We have added a comprehensive test suite with two primary validation methods. The full suite covers **36 charset & collation combinations**, with **55 distinct test pairs for each combination.**

For practical engineering purposes, we have selected a more focused set of 9 common charset & collation combinations, each with 41 test pairs.

Our findings show that neither Python's default sort nor a generic "natural sort" algorithm can solve this problem. Although Python's default sort has a relatively high accuracy rate, it is ineffective for the critical test cases where this bug was originally observed, such as:

```
Coverage by charset/collation combination:
utf8mb4/utf8mb4_0900_bin : 41/ 41 (100.0%)
utf8mb4/utf8mb4_general_ci : 39/ 41 ( 95.1%)
utf8mb4/utf8mb4_bin : 39/ 41 ( 95.1%)
utf8mb3/utf8mb3_general_ci : 39/ 41 ( 95.1%)
utf8mb4/utf8mb4_0900_ai_ci : 37/ 41 ( 90.2%)
utf8mb4/utf8mb4_0900_as_ci : 37/ 41 ( 90.2%)
utf8mb4/utf8mb4_unicode_ci : 35/ 41 ( 85.4%)
utf8mb4/utf8mb4_unicode_520_ci : 35/ 41 ( 85.4%)
utf8mb4/utf8mb4_0900_as_cs : 30/ 41 ( 73.2%)

Overall Coverage: 332/369 (90.0%)

Natsort Natural:
Total test cases executed: 369

Coverage by charset/collation combination:
utf8mb4/utf8mb4_0900_bin : 32/ 41 ( 78.0%)
utf8mb4/utf8mb4_bin : 30/ 41 ( 73.2%)
utf8mb4/utf8mb4_0900_ai_ci : 23/ 41 ( 56.1%)
utf8mb4/utf8mb4_0900_as_ci : 23/ 41 ( 56.1%)
utf8mb4/utf8mb4_0900_as_cs : 23/ 41 ( 56.1%)
utf8mb4/utf8mb4_general_ci : 23/ 41 ( 56.1%)
utf8mb3/utf8mb3_general_ci : 23/ 41 ( 56.1%)
utf8mb4/utf8mb4_unicode_ci : 21/ 41 ( 51.2%)
utf8mb4/utf8mb4_unicode_520_ci : 21/ 41 ( 51.2%)

Overall Coverage: 219/369 (59.3%)

```

[comparator_base.py](https://github.com/user-attachments/files/23453938/comparator_base.py)
[test_comparator.py](https://github.com/user-attachments/files/23453939/test_comparator.py)