Jak odwrócony indeks przyspiesza wyszukiwanie tekstu o 40 razy?

Jako otwarta hurtownia danych w czasie rzeczywistym, Apache Doris zapewnia bogaty wybór indeksów przyspieszających skanowanie i filtrowanie danych. W oparciu o zaangażowanie użytkownika można je podzielić na wbudowane inteligentne indeksy i indeksy tworzone przez użytkownika. Pierwsze z nich są automatycznie generowane przez Apache Doris podczas pobierania danych, takie jak indeks ZoneMap i indeks prefiksów, podczas gdy drugie są indeksami wybieranymi przez użytkowników dla różnych przypadków użycia, w tym indeks odwrócony i indeks NGram BloomFilter.

Ten post jest dogłębnym omówieniem indeksu odwróconego i indeksu NGram BloomFilter, zawierającym praktyczny przewodnik dotyczący ich stosowania w różnych zapytaniach.

Przykładowy zestaw danych

Testowy zbiór danych obejmuje około 130 milionów recenzji klientów Amazon. Jest to kilka skompresowanych przez Snappy plików Parquet o łącznym rozmiarze 37 GB. Oto kilka próbek:

Każdy wiersz zawiera 15 kolumn, w tym customer_id, review_id, product_id, product_category, star_rating, review_headline, oraz review_body.

Wiele z tych kolumn można przyspieszyć za pomocą indeksów opartych na ich strukturach. Na przykład, customer_id jest polem numerycznym o wysokiej kardynalności, podczas gdy product_id jest polem tekstowym o stałej długości o niskiej kardynalności, oraz product_title oraz review_body to odpowiednio krótkie i długie pola tekstowe.

Zapytania dotyczące tych kolumn można z grubsza podzielić na dwa typy:

Wyszukiwania tekstowe: wyszukuje określone treści w review_body pole.
Zapytania dotyczące kolumn niebędących kluczami podstawowymi: zapytanie o opinie na temat niektórych product_id lub od niektórych customer_id.

Są to również główne wątki tego artykułu. Przedstawię Państwu, w jaki sposób indeksy mogą przyspieszyć te zapytania.

Wymagania wstępne

Do szybkiego uruchomienia używamy tutaj klastra z jednym węzłem (1 frontend, jeden backend).

Wdrożenie Apache Doris: proszę odnieść się do Szybki start
Proszę utworzyć tabelę przy użyciu następujących instrukcji:

CREATE TABLE `amazon_reviews` (  
  `review_date` int(11) NULL,  
  `marketplace` varchar(20) NULL,  
  `customer_id` bigint(20) NULL,  
  `review_id` varchar(40) NULL,
  `product_id` varchar(10) NULL,
  `product_parent` bigint(20) NULL,
  `product_title` varchar(500) NULL,
  `product_category` varchar(50) NULL,
  `star_rating` smallint(6) NULL,
  `helpful_votes` int(11) NULL,
  `total_votes` int(11) NULL,
  `vine` boolean NULL,
  `verified_purchase` boolean NULL,
  `review_headline` varchar(500) NULL,
  `review_body` string NULL
) ENGINE=OLAP
DUPLICATE KEY(`review_date`)
COMMENT 'OLAP'
DISTRIBUTED BY HASH(`review_date`) BUCKETS 16
PROPERTIES (
"replication_allocation" = "tag.location.default: 1",
"compression" = "ZSTD"
);

Proszę pobrać zestawy danych: Skompresowane pliki Snappy Parquet o łącznym rozmiarze 37 GB
Proszę wykonać następujące polecenia, aby załadować zbiory danych

curl --location-trusted -u root: -T amazon_reviews_2010.snappy.parquet -H "format:parquet" http://${BE_IP}:${BE_PORT}/api/${DB}/amazon_reviews/_stream_load
curl --location-trusted -u root: -T amazon_reviews_2011.snappy.parquet -H "format:parquet" http://${BE_IP}:${BE_PORT}/api/${DB}/amazon_reviews/_stream_load
curl --location-trusted -u root: -T amazon_reviews_2012.snappy.parquet -H "format:parquet" http://${BE_IP}:${BE_PORT}/api/${DB}/amazon_reviews/_stream_load
curl --location-trusted -u root: -T amazon_reviews_2013.snappy.parquet -H "format:parquet" http://${BE_IP}:${BE_PORT}/api/${DB}/amazon_reviews/_stream_load
curl --location-trusted -u root: -T amazon_reviews_2014.snappy.parquet -H "format:parquet" http://${BE_IP}:${BE_PORT}/api/${DB}/amazon_reviews/_stream_load
curl --location-trusted -u root: -T amazon_reviews_2015.snappy.parquet -H "format:parquet" http://${BE_IP}:${BE_PORT}/api/${DB}/amazon_reviews/_stream_load

Proszę sprawdzić i zweryfikować: Po wykonaniu powyższych kroków, proszę wykonać następujące polecenia w kliencie MySQL, aby sprawdzić rozmiar zbioru danych. Poniżej widać, że załadowano 135589433 wierszy, które zajmują 25,873 GB w Apache Doris, czyli o 30% mniej niż oryginalne pliki Parquet.

mysql> SELECT COUNT() FROM amazon_reviews;
+-----------+
| count(*)  |
+-----------+
| 135589433 |
+-----------+
1 row in set (0.02 sec)
mysql> SHOW DATA FROM amazon_reviews;
+----------------+----------------+-----------+--------------+-----------+------------+
| TableName      | IndexName      | Size      | ReplicaCount | RowCount  | RemoteSize |
+----------------+----------------+-----------+--------------+-----------+------------+
| amazon_reviews | amazon_reviews | 25.873 GB | 16           | 135589433 | 0.000      |
|                | Total          | 25.873 GB | 16           |           | 0.000      |
+----------------+----------------+-----------+--------------+-----------+------------+
2 rows in set (0.00 sec)

Przyspieszanie wyszukiwania tekstu

Brak indeksu

Spróbujmy teraz przeprowadzić wyszukiwanie tekstowe na stronie review_body . W szczególności próbujemy pobrać 5 najlepszych produktów, których recenzje zawierają słowa kluczowe “jest super niesamowity”. Wyniki powinny być posortowane malejąco na podstawie liczby recenzji. Każdy wynik powinien zawierać identyfikator produktu, losowo wybrany tytuł produktu, średnią ocenę w gwiazdkach i całkowitą liczbę recenzji.

To jest instrukcja zapytania:

SELECT
    product_id,
    any(product_title),
    AVG(star_rating) AS rating,
    COUNT() AS count
FROM
    amazon_reviews
WHERE
    review_body LIKE '%is super awesome%'
GROUP BY
    product_id
ORDER BY
    count DESC,
    rating DESC,
    product_id
LIMIT 5;

Ponieważ review_body zawiera długie recenzje, takie przeszukiwanie tekstu może być czasochłonne. Bez włączania indeksów zajęło to 7,6 sekundy zwrócić wyniki:

+------------+------------------------------------------+--------------------+-------+
| product_id | any_value(product_title)                 | rating             | count |
+------------+------------------------------------------+--------------------+-------+
| B00992CF6W | Minecraft                                | 4.8235294117647056 |    17 |
| B009UX2YAC | Subway Surfers                           | 4.7777777777777777 |     9 |
| B00DJFIMW6 | Minion Rush: Despicable Me Official Game |              4.875 |     8 |
| B0086700CM | Temple Run                               |                  5 |     6 |
| B00KWVZ750 | Angry Birds Epic RPG                     |                  5 |     6 |
+------------+------------------------------------------+--------------------+-------+
5 rows in set (7.60 sec)

Indeks NGram BloomFilter

Spróbujmy teraz przyspieszyć takie wyszukiwanie tekstu za pomocą indeksu NGram BloomFilter.

gram_size: wartość “N” w “NGram”, reprezentująca długość kolejnych znaków. W poniższym fragmencie, "gram_size"="10" oznacza, że teksty zostaną podzielone na pewną liczbę 10-znakowych ciągów, które są podstawą indeksu NGram BloomFilter.
bf_size: rozmiar BloomFilter w bajtach. "bf_size"="10240" wskazuje, że BloomFilter zajmuje 10240 bajtów miejsca.

ALTER TABLE amazon_reviews ADD INDEX review_body_ngram_idx(review_body) USING NGRAM_BF PROPERTIES("gram_size"="10", "bf_size"="10240");

Tym razem zapytanie zostało zakończone w ciągu 0,93 sekundy. Oznacza to, że NGram BloomFilter zapewnia przyspieszenie na poziomie 8 razy.

+------------+------------------------------------------+--------------------+-------+
| product_id | any_value(product_title)                 | rating             | count |
+------------+------------------------------------------+--------------------+-------+
| B00992CF6W | Minecraft                                | 4.8235294117647056 |    17 |
| B009UX2YAC | Subway Surfers                           | 4.7777777777777777 |     9 |
| B00DJFIMW6 | Minion Rush: Despicable Me Official Game |              4.875 |     8 |
| B0086700CM | Temple Run                               |                  5 |     6 |
| B00KWVZ750 | Angry Birds Epic RPG                     |                  5 |     6 |
+------------+------------------------------------------+--------------------+-------+
5 rows in set (0.93 sec)

W jaki sposób NGram BloomFilter dokonuje magii? Sposób jego działania można wyjaśnić w dwóch częściach.

Tokenizacja NGram: Kiedy gram_size=5, wyrażenie “hello world” jest podzielone na [“hello”, “ello “, “llo w”, “lo wo”, “o wor”, ” worl”, “world”]. Te podciągi są następnie haszowane i dodawane do filtra BloomFilter typu bf_size. Ponieważ dane w Apache Doris są przechowywane według stron, filtry BloomFilter są również generowane według stron.
Przyspieszenie zapytań: Na przykład, aby zapytać o słowo “hello” w tekstach, “hello” jest tokenizowane i porównywane z BloomFilter każdej strony. Jeśli BloomFilter wykryje potencjalne dopasowanie (mogą wystąpić fałszywe alarmy) na stronie, strona ta jest ładowana w celu dalszego dopasowania. W przeciwnym razie strona ta jest pomijana.

Pomijając nieistotne strony, indeks BloomFilter ogranicza niepotrzebne skanowanie danych, a tym samym znacznie zmniejsza opóźnienie zapytań.

Ilustracja NGram BloomFilter

Jak znaleźć optymalne konfiguracje parametrów dla NGram BloomFilter

gram_size określa skuteczność dopasowania, podczas gdy bf_size wpływa na współczynnik wyników fałszywie dodatnich. Zazwyczaj duży bf_size zmniejsza odsetek wyników fałszywie dodatnich, ale wymaga również więcej miejsca na dysku. Dlatego sugerujemy skonfigurowanie tych dwóch parametrów w oparciu o te dwa czynniki:

Długość tekstu

W przypadku krótkich tekstów (słów lub fraz), niewielki gram_size (2~4) i mały bf_size są zalecane.
W przypadku długich tekstów (zdań lub akapitów), duży gram_size (5~10) i duży bf_size działają lepiej.

Wzorzec zapytania

Jeśli zapytania często zawierają frazy lub pełne słowa, duży gram_size będzie bardziej wydajny.
W przypadku dopasowania rozmytego lub zróżnicowanych zapytań, niewielki gram_size pozwala na bardziej elastyczne dopasowanie.

Odwrócony indeks

Odwrócony indeks to kolejny sposób na przyspieszenie wyszukiwania tekstu. Tworzenie odwróconego indeksu jest proste:

Dodaj odwrócony indeks: Proszę odnieść się do poniższego fragmentu kodu, aby utworzyć odwrócony indeks dla pliku review_body kolumny amazon_reviews tabeli. Odwrócony indeks obsługuje wyszukiwanie fraz, w którym kolejność tokenizowanych słów będzie miała wpływ na wyniki wyszukiwania.
Proszę dodać odwrócony indeks dla danych historycznych: Mogą Państwo również utworzyć odwrócony indeks dla danych historycznych.

ALTER TABLE amazon_reviews ADD INDEX review_body_inverted_idx(`review_body`) 
    USING INVERTED PROPERTIES("parser" = "english","support_phrase" = "true"); 
BUILD INDEX review_body_inverted_idx ON amazon_reviews;

Proszę sprawdzić i zweryfikować: Mogą Państwo sprawdzić i zobaczyć utworzone indeksy za pomocą następującego polecenia:

mysql> show BUILD INDEX WHERE TableName="amazon_reviews";
+-------+----------------+----------------+-----------------------------------------------------------------------------------------------------------------------------------+-------------------------+-------------------------+---------------+----------+------+----------+
| JobId | TableName      | PartitionName  | AlterInvertedIndexes                                                                                                              | CreateTime              | FinishTime              | TransactionId | State    | Msg  | Progress |
+-------+----------------+----------------+-----------------------------------------------------------------------------------------------------------------------------------+-------------------------+-------------------------+---------------+----------+------+----------+
| 10152 | amazon_reviews | amazon_reviews | [ADD INDEX review_body_inverted_idx (
review_body
) USING INVERTED PROPERTIES("parser" = "english", "support_phrase" = "true")],  | 2024-01-23 15:42:28.658 | 2024-01-23 15:48:42.990 | 11            | FINISHED |      | NULL     |
+-------+----------------+----------------+-----------------------------------------------------------------------------------------------------------------------------------+-------------------------+-------------------------+---------------+----------+------+----------+
1 row in set (0.00 sec)

Jeśli chcą Państwo sprawdzić, jak działa tokenizacja, można przetestować za pomocą polecenia TOKENIZE. Wystarczy wprowadzić tekst, który ma zostać tokenizowany oraz parametry:

mysql> SELECT TOKENIZE('I can honestly give the shipment and package 100%, it came in time that it was supposed to with no hasels, and the book was in PERFECT condition.
super awesome buy, and excellent for my college classs', '"parser" = "english","support_phrase" = "true"');
+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| tokenize('I can honestly give the shipment and package 100%, it came in time that it was supposed to with no hasels, and the book was in PERFECT condition. super awesome buy, and excellent for my college classs', '"parser" = "english","support_phrase" = "true"')                                              |
+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
| ["i", "can", "honestly", "give", "the", "shipment", "and", "package", "100", "it", "came", "in", "time", "that", "it", "was", "supposed", "to", "with", "no", "hasels", "and", "the", "book", "was", "in", "perfect", "condition", "super", "awesome", "buy", "and", "excellent", "for", "my", "college", "classs"] |
+---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+
1 row in set (0.05 sec)

Z odwróconym indeksem, możemy teraz pobrać opinie klientów zawierające “jest super niesamowite” za pomocą funkcji MATCH_PHRASE.

SELECT
    product_id,
    any(product_title),
    AVG(star_rating) AS rating,
    COUNT() AS count
FROM
    amazon_reviews
WHERE
    review_body MATCH_PHRASE 'is super awesome'
GROUP BY
    product_id

ORDER BY
    count DESC,
    rating DESC,
    product_id
LIMIT 5;

Klauzula review_body MATCH_PHRASE 'is super awesome' wyszukuje fragmenty tekstu w pliku review_body które zawierają wszystkie trzy słowa kluczowe “is”, “super” i “awesome” w dokładnie takiej kolejności, bez żadnych innych słów pomiędzy nimi.

The MATCH nie uwzględnia wielkości liter, co również odróżnia je od zapytania LIKE . The MATCH jest bardziej wydajne w przypadku dużych zbiorów danych.

Wyniki pokazują, że odwrócony indeks zmniejszył opóźnienie zapytań do 0,19 sekundy, przynosząc 4-krotny wzrost wydajności w porównaniu do indeksu NGram BloomFilter i prawie 40-krotny wzrost w porównaniu do braku indeksów w ogóle.

+------------+------------------------------------------+-------------------+-------+
| product_id | any_value(product_title)                 | rating            | count |
+------------+------------------------------------------+-------------------+-------+
| B00992CF6W | Minecraft                                | 4.833333333333333 |    18 |
| B009UX2YAC | Subway Surfers                           |               4.7 |    10 |
| B00DJFIMW6 | Minion Rush: Despicable Me Official Game |                 5 |     7 |
| B0086700CM | Temple Run                               |                 5 |     6 |
| B00KWVZ750 | Angry Birds Epic RPG                     |                 5 |     6 |
+------------+------------------------------------------+-------------------+-------+
5 rows in set (0.19 sec)

Jak odwrócony indeks to umożliwia?

Indeks odwrócony dzieli tekst na słowa i mapuje każde słowo na numer wiersza. Następnie tokenizowane słowa są sortowane alfabetycznie i tworzony jest indeks listy pominięć. Podczas wykonywania zapytań dotyczących określonych słów, system lokalizuje numery wierszy w tym uporządkowanym mapowaniu przy użyciu indeksu listy pominięć i metod wyszukiwania binarnego. Na podstawie numerów wierszy system pobiera cały rekord danych.

Takie podejście pozwala uniknąć dopasowywania wiersz po wierszu i zmniejsza złożoność obliczeniową z O(n) do O(logn). W ten sposób odwrócony indeks przyspiesza zapytania dotyczące dużych zbiorów danych.

Ilustracja odwróconego indeksu

Aby zapewnić głębsze zrozumienie odwróconego indeksu, zacznę od jego logiki odczytu/zapisu. W Doris, logicznie, odwrócony indeks jest stosowany na poziomie kolumny tabeli. Jednak z punktu widzenia fizycznego przechowywania i implementacji, jest on faktycznie zbudowany na plikach danych.

Pisanie: Gdy dane są zapisywane do pliku danych, są one również synchronicznie zapisywane do odwróconego pliku indeksu, a numery wierszy są dopasowywane.
Zapytanie: W zapytaniu, jeśli WHERE warunek dotyczy kolumny, dla której zbudowano odwrócony indeks, Doris przejdzie bezpośrednio do pliku indeksu i zwróci odpowiednie numery wierszy. Następnie, w oparciu o numery wierszy, pomija nieistotne strony i wiersze i odczytuje tylko wiersze docelowe.

Krótko mówiąc, odwrócony indeks umożliwia szybkie wyszukiwanie tekstu poprzez mapowanie, a jego implementacja opiera się na koordynacji plików danych i plików indeksu.

Przyspieszanie zapytań o kolumny bez klucza głównego

Aby pokazać wpływ odwróconego indeksu na zapytania dotyczące kolumn bez klucza głównego, wypróbujmy kilka zapytań wielowymiarowych.

Brak indeksu

Proszę pobrać recenzję z ID klienta 13916588 o ID produktu B002DMK1R0. Bez indeksów system musi przeskanować całą tabelę. Zapytanie jest zakończone w ciągu 1,81 sekundy.

mysql> SELECT product_title,review_headline,review_body,star_rating 
FROM amazon_reviews 
WHERE product_id='B002DMK1R0' AND customer_id=13916588;
+-----------------------------------------------------------------+----------------------+-----------------------------------------------------------------------------------------------------------------------------+-------------+
| product_title                                                   | review_headline      | review_body                                                                                                                 | star_rating |
+-----------------------------------------------------------------+----------------------+-----------------------------------------------------------------------------------------------------------------------------+-------------+
| Magellan Maestro 4700 4.7-Inch Bluetooth Portable GPS Navigator | Nice Features But... | This is a great GPS. Gets you where you are going. Don't forget to buy the seperate (grr!) cord for the traffic kit though! |           4 |
+-----------------------------------------------------------------+----------------------+-----------------------------------------------------------------------------------------------------------------------------+-------------+
1 row in set (1.81 sec)

Odwrócony indeks

To zapytanie jest wykonywane w inny sposób niż opisano powyżej, ponieważ system nie musi tokenizować zapytania product_id i customer_id, ale tworzy tabelę indeksów odwróconych Value→RowID.

Przede wszystkim należy utworzyć indeks odwrócony za pomocą następującej instrukcji:

ALTER TABLE amazon_reviews ADD INDEX product_id_inverted_idx(product_id) USING INVERTED ;
ALTER TABLE amazon_reviews ADD INDEX customer_id_inverted_idx(customer_id) USING INVERTED ;
BUILD INDEX product_id_inverted_idx ON amazon_reviews;
BUILD INDEX customer_id_inverted_idx ON amazon_reviews;

Z odwróconym indeksem, to samo zapytanie jest zakończone w ciągu 0,06 sekundy. Stanowi to 30-krotny wyższą prędkość w porównaniu z poprzednim wynikiem 1,81 sekundy.

mysql> SELECT product_title,review_headline,review_body,star_rating FROM amazon_reviews WHERE product_id='B002DMK1R0' AND customer_id='13916588';
+-----------------------------------------------------------------+----------------------+-----------------------------------------------------------------------------------------------------------------------------+-------------+
| product_title                                                   | review_headline      | review_body                                                                                                                 | star_rating |
+-----------------------------------------------------------------+----------------------+-----------------------------------------------------------------------------------------------------------------------------+-------------+
| Magellan Maestro 4700 4.7-Inch Bluetooth Portable GPS Navigator | Nice Features But... | This is a great GPS. Gets you where you are going. Don't forget to buy the seperate (grr!) cord for the traffic kit though! |           4 |
+-----------------------------------------------------------------+----------------------+-----------------------------------------------------------------------------------------------------------------------------+-------------+
1 row in set (0.06 sec)

Profil

Jest to fragment profilu SegmentIterator, z którego można dowiedzieć się, dlaczego odwrócony indeks przyspiesza wykonywanie zapytań.

(Proszę zauważyć, że aby sprawdzić profil zapytania, należy upewnić się, że wykonano zapytanie SET enable_profile=true; w kliencie MySQL przed wykonaniem zapytania. Następnie można sprawdzić profil pod adresem http://FE_IP:FE_HTTP_PORT/QueryProfile)

SegmentIterator:
  - FirstReadSeekCount: 0
  - FirstReadSeekTime: 0ns
  - FirstReadTime: 13.119ms
  - IOTimer: 19.537ms
  - InvertedIndexQueryTime: 11.583ms
  - RawRowsRead: 1
  - RowsConditionsFiltered: 0
  - RowsInvertedIndexFiltered: 16.907403M (16907403)
  - RowsShortCircuitPredInput: 0
  - RowsVectorPredFiltered: 0
  - RowsVectorPredInput: 0
  - ShortPredEvalTime: 0ns
  - TotalPagesNum: 27
  - UncompressedBytesRead: 3.71 MB
  - VectorPredEvalTime: 0ns

RowsInvertedIndexFiltered: 16.907403M (16907403) oraz RawRowsRead: 1 oznacza, że indeks odwrócony odfiltrował wiersze 16907403 i odczytał tylko 1 wiersz (wiersz docelowy). FirstReadTime: 13.119ms oznacza, że odczytanie strony, na której znajduje się docelowy wiersz, zajmuje 13,119 ms, a InvertedIndexQueryTime: 11.583ms oznacza, że system odfiltrowuje 16907403 wierszy w ciągu zaledwie 11,58 ms.

Dla porównania, jest to profil SegmentIterator, gdy nie jest używany żaden indeks:

SegmentIterator:
  - FirstReadSeekCount: 9.374K (9374)
  - FirstReadSeekTime: 400.522ms
  - FirstReadTime: 3s144ms
  - IOTimer: 2s564ms
  - InvertedIndexQueryTime: 0ns
  - RawRowsRead: 16.680706M (16680706)
  - RowsConditionsFiltered: 226.698K (226698)
  - RowsInvertedIndexFiltered: 0
  - RowsShortCircuitPredInput: 1
  - RowsVectorPredFiltered: 16.680705M (16680705)
  - RowsVectorPredInput: 16.680706M (16680706)
  - RowsZonemapFiltered: 226.698K (226698)
  - ShortPredEvalTime: 2.723ms
  - TotalPagesNum: 5.421K (5421)
  - UncompressedBytesRead: 277.05 MB
  - VectorPredEvalTime: 8.114ms

Bez odwróconego indeksu załadowanie 16680706 wierszy zajmuje 3,14 s (FirstReadTime: 3s144ms). Następnie system przeprowadza filtrowanie za pomocą funkcji Predicate Evaluate i odsiewa wiersze 16680705. Proces filtrowania warunkowego zajmuje tylko mniej niż 10 ms, co sprawia, że ładowanie oryginalnych danych jest najbardziej czasochłonnym zadaniem.

Podsumowując, odwrócony indeks zwiększa wydajność wykonywania zapytań, umożliwiając szybkie pobieranie docelowych wierszy, a tym samym zmniejszając niepotrzebne ładowanie danych.

Przyspieszanie zapytań do kolumn tekstowych o niskiej kardynalności

Tak więc odwrócony indeks jest dużym akceleratorem dla zapytań dotyczących kolumn tekstowych o wysokiej kardynalności, ale może to budzić obawy: Czy w przypadku kolumn o niskiej kardynalności zbyt duża liczba indeksów spowoduje nadmierne obciążenie i pogorszy wydajność zapytań?

Odpowiedź brzmi: nie. Proszę pozwolić mi pokazać dlaczego i jak. Poniższy przykład wykorzystuje product_categoryjako kolumny predykatu do filtrowania.

mysql> SELECT COUNT(DISTINCT product_category) FROM amazon_reviews ;
+----------------------------------+
| count(DISTINCT product_category) |
+----------------------------------+
|                               43 |
+----------------------------------+
1 row in set (0.57 sec)

Jak pokazano, kolumna product_categoryma tylko 43 odrębne kategorie, co czyni ją typową kolumną tekstową o niskiej kardynalności. Teraz dodajmy do niej odwrócony indeks.

ALTER TABLE amazon_reviews ADD INDEX product_category_inverted_idx(`product_category`) USING INVERTED;
BUILD INDEX product_category_inverted_idx ON amazon_reviews;

Po dodaniu odwróconego indeksu, proszę uruchomić następujące zapytanie SQL, aby pobrać 3 najlepsze produkty z największą liczbą recenzji w kategorii produktów “Mobile_Electronics”.

SELECT 
    product_id,
    product_title,
    AVG(star_rating) AS rating,
    any(review_body),
    any(review_headline),
    COUNT(*) AS count 
FROM 
    amazon_reviews 
WHERE 
    product_category = 'Mobile_Electronics' 
GROUP BY 
    product_title, product_id 
ORDER BY 
    count DESC 
LIMIT 10;

Z odwróconym indeksem, zapytanie trwa 1.54s, aby zakończyć.

+------------+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+--------------------+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+---------------------------------+-------+
| product_id | product_title                                                                                                                                                                                          | rating             | any_value(review_body)                                                                                                                                                                                                                                                                                                                                                                                                                                                                                   | any_value(review_headline)      | count |
+------------+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+--------------------+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+---------------------------------+-------+
| B00J46XO9U | iXCC Lightning Cable 3ft, iPhone charger, for iPhone X, 8, 8 Plus, 7, 7 Plus, 6s, 6s Plus, 6, 6 Plus, SE 5s 5c 5, iPad Air 2 Pro, iPad mini 2 3 4, iPad 4th Gen [Apple MFi Certified](Black and White) | 4.3766233766233764 | Great cable and works well. Exact fit as Apple cable. I would recommend this to anyone who is looking to save money and for a quality cable.                                                                                                                                                                                                                                                                                                                                                             | Apple certified lightning cable |  1078 |
| B004911E9M | Wall AC Charger USB Sync Data Cable for iPhone 4, 3GS, and iPod                                                                                                                                        | 2.4281805745554035 | A total waste of money for me because I needed it for a iPhone 4.  The plug will only go in upside down and thus won't work at all.                                                                                                                                                                                                                                                                                                                                                                      | Won't work with a iPhone 4!     |   731 |
| B002D4IHYM | New Trent Easypak 7000mAh Portable Triple USB Port External Battery Charger/Power Pack for Smartphones, Tablets and more (w/built-in USB cable)                                                        | 4.5216095380029806 | I bought this product based on the reviews that i read and i am very glad that i did. I did have a problem with the product charging my itouch after i received it but i emailed the company and they corrected the problem immediately. VERY GOOD customer service, very prompt. The product itself is very good. It charges my power hungry itouch very quickly and the imax battery power lasts for a long time. All in all a very good purchase that i would recommend to anyone who owns an itouch. | Great product & company         |   671 |
+------------+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+--------------------+----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+---------------------------------+-------+
3 rows in set (1.54 sec)

Spróbujmy teraz ponownie bez włączania indeksu odwróconego. To samo zapytanie trwa 1,8 s. (Można po prostu wyłączyć odwrócony indeks, wykonując polecenie set enable_inverted_index_query=false;w kliencie MySQL).

+------------+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+--------------------+------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+---------------------------------------+-------+
| product_id | product_title                                                                                                                                                                                          | rating             | any_value(review_body)                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                             | any_value(review_headline)            | count |
+------------+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+--------------------+------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+---------------------------------------+-------+
| B00J46XO9U | iXCC Lightning Cable 3ft, iPhone charger, for iPhone X, 8, 8 Plus, 7, 7 Plus, 6s, 6s Plus, 6, 6 Plus, SE 5s 5c 5, iPad Air 2 Pro, iPad mini 2 3 4, iPad 4th Gen [Apple MFi Certified](Black and White) | 4.3766233766233764 | These cables are great. They feel quality, and best of all, they work as they should. I have no issues with them whatsoever and will be buying more when needed.                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                                   | Just like the original from Apple     |  1078 |
| B004911E9M | Wall AC Charger USB Sync Data Cable for iPhone 4, 3GS, and iPod                                                                                                                                        | 2.4281805745554035 | I ordered two of these chargers for an Iphone 4. Then I started experiencing weird behavior from the touch screen. It would select the wrong area of the screen, or it would refuse to scroll beyond a certain point and jump back up to the top of the page. This behavior occurs whenever either of the two that I bought are attached and charging. When I remove them, it works fine once again. Needless to say, these items are being returned.                                                                                                                                                                                                                                                                                                                                                                              | Beware - these chargers are defective |   731 |
| B002D4IHYM | New Trent Easypak 7000mAh Portable Triple USB Port External Battery Charger/Power Pack for Smartphones, Tablets and more (w/built-in USB cable)                                                        | 4.5216095380029806 | I received this in the mail 4 days ago, and after charging it for 6 hours, I've been using it as the sole source for recharging my 3Gs to see how long it would work.  I use my Iphone A LOT every day and usually by the time I get home it's down to 50% or less.  After 4 days of using the IMAX to recharge my Iphone, it finally went from 3 bars to 4 this afternoon when I plugged my iphone in.  It charges the iphone very quickly, and I've been topping my phone off (stopping around 95% or so) twice a day.  This is a great product and the size is very similar to a deck of cards (not like an iphone that someone else posted) and is very easy to carry in a jacket pocket or back pack.  I bought this for a 4 day music festival I'm going to, and I have no worries at all of my iphone running out of juice! | FANTASTIC product!                    |   671 |
+------------+--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+--------------------+------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------+---------------------------------------+-------+
3 rows in set (1.80 sec)

Podsumowując, odwrócony indeks może przynieść 15% przyspieszenie dla zapytań dotyczących kolumn o niskiej kardynalności. Jest to więc nie tylko nieszkodliwe, ale także korzystne dla filtrowania danych o niskiej kardynalności.

Ponadto, Apache Doris stosuje efektywne kodowanie słownikowe i kompresję dla kolumn o niskiej kardynalności. Do filtrowania wykorzystuje również wbudowane indeksy, takie jak ZoneMap. Dzięki temu może zapewnić idealną wydajność zapytań nawet bez odwróconych indeksów.

Wnioski

Odwrócony indeks w Apache Doris optymalizuje filtrowanie danych na podstawie kolumny predykatu (kolumny WHERE w zapytaniach SQL). Redukuje niepotrzebne skanowanie danych, znacznie zwiększając szybkość zapytań dla kolumn o wysokiej kardynalności i gwarantuje brak negatywnych skutków dla kolumn o niskiej kardynalności. Obsługuje lekkie zarządzanie indeksami, w tym ADD/DROP INDEX i BUILD INDEX. Można go łatwo włączyć lub wyłączyć za pomocą enable_inverted_index_query=true/false.

Odwrócony indeks i indeks NGram BloomFilter mają zastosowanie do różnych scenariuszy. W ten sposób można zdecydować, który z nich jest optymalnym wyborem:

Zapytania dotyczące kolumn bez klucza podstawowego: Przypadki te często obejmują bardzo rozproszone wartości i niski współczynnik trafień. Odwrócony indeks może działać w połączeniu z wbudowanymi inteligentnymi indeksami w Doris, aby przyspieszyć te zapytania. Ma ugruntowaną obsługę skalarnych typów danych, w tym znaków, liczb i datetime.
Przeszukiwanie krótkich tekstów: Jeśli zbiór danych zawiera krótkie teksty, które są bardzo zróżnicowane, NGram BloomFilter będzie skutecznym wyborem dla dopasowania rozmytego (LIKE) dla krótkich tekstów. Jeśli krótkie teksty są bardzo podobne (zawierają wiele identycznych treści), odwrócony indeks będzie bardziej wydajny, ponieważ zapewnia mniejszy słownik i szybsze wyszukiwanie numerów wierszy.
Przeszukiwanie długich tekstów: Odwrócony indeks jest lepszym wyborem dla długich tekstów. W porównaniu do brutalnego dopasowywania ciągów znaków, znacznie zmniejsza zużycie zasobów procesora.

Odwrócony indeks jest dostępny w Apache Doris od prawie roku i przetrwał test wielu użytkowników w ich środowisku produkcyjnym z ogromnymi danymi. W przyszłych wersjach Apache Doris dotyczących odwróconego indeksu, planujemy dodać wsparcie dla:

Samodzielnie definiowana tokenizacja: zapewnia tokenizator zdefiniowany przez użytkownika, aby pasował do różnych przypadków użycia.
Więcej typów danych: Użytkownicy będą mogli tworzyć odwrócone indeksy dla złożonych typów danych, w tym Array i Map.

Jeśli napotkają Państwo jakiekolwiek problemy podczas wypróbowywania tego rozwiązania w Apache Doris lub chcieliby Państwo poznać więcej szczegółów, prosimy dołączyć do naszego zespołu. Slack społeczność i proszę z nami porozmawiać!