Jak szybko przeszukiwać bardzo dużą listę ciągów / rekordów w bazie danych

Mam następujący problem: Mam bazę danych zawierającą ponad 2 miliony rekordów. Każdy rekord ma pole ciągu X i chcę wyświetlić listę rekordów, dla których pole X zawiera określony ciąg. Każdy rekord ma rozmiar około 500 bajtów.

Mówiąc konkretniej: w GUI mojej aplikacji mam pole tekstowe, w którym mogę wpisać ciąg znaków. Nad polem tekstowym mam tabelę wyświetlającą (pierwsze N, np. 100) rekordy pasujące do ciągu w polu tekstowym. Kiedy wpisuję lub usuwam jeden znak w polu tekstowym, zawartość tabeli musi być aktualizowana na bieżąco.

Zastanawiam się, czy istnieje skuteczny sposób na wykonanie tego przy użyciu odpowiednich struktur indeksu i / lub buforowania. Jak wyjaśniono powyżej, chcę wyświetlić tylko pierwsze N ​​elementów, które pasują do zapytania. Dlatego, dla N wystarczająco małych, ładowanie pasujących elementów z bazy danych nie powinno być dużym problemem. Poza tym buforowanie elementów w pamięci głównej może przyspieszyć pobieranie.

Myślę, że głównym problemem jest to, jak szybko znaleźć pasujące elementy, biorąc pod uwagę ciąg wzorca. Czy mogę polegać na niektórych funkcjach DBMS, czy też muszę samodzielnie budować indeks w pamięci? Jakieś pomysły?

EDYTOWAĆ

Przeprowadziłem pierwszy eksperyment. Podzieliłem rekordy na różne pliki tekstowe (maksymalnie 200 rekordów na plik) i umieściłem pliki w różnych katalogach (wykorzystałem zawartość jednego pola danych do określenia drzewa katalogów). Skończyłem z około 50000 plików w około 40000 katalogów. Następnie uruchomiłem Lucene, aby zindeksować pliki. Wyszukiwanie łańcucha za pomocą programu demo Lucene jest dość szybkie. Podział i indeksowanie zajęło kilka minut: jest to dla mnie całkowicie akceptowalne, ponieważ jest to statyczny zestaw danych, o który chcę zapytać.

Następnym krokiem jest zintegrowanie Lucene z programem głównym i użycie trafień zwróconych przez Lucene do załadowania odpowiednich rekordów do pamięci głównej.

Zamiast umieszczać dane w bazie danych, możesz przechowywać je jako zestaw dokumentów (pliki tekstowe) osobno i zachować link (ścieżkę / adres URL itp.) W bazie danych.

Jest to niezbędne, ponieważ zapytanie SQL w fazie projektowania będzie bardzo wolne zarówno w wyszukiwaniu podciągu, jak i podczas pobierania.

Teraz twój problem został sformułowany jako przeszukiwanie plików tekstowych, które zawierają zestaw ciągów. Istnieją tutaj dwie możliwości.

1. Dopasowanie podciągu Jeśli twoje plamy tekstowe są pojedynczym żądłem lub słowem (bez spacji) i musisz wyszukać w nim dowolny podciąg. W takich przypadkach musisz przeanalizować każdy plik, aby znaleźć najlepsze możliwe pliki, które pasują. Jeden wykorzystuje algorytmy takie jak algorytm Boyera Moora. Zobacz to i to po szczegóły. Jest to również równoważne z grep - ponieważ grep używa podobnych rzeczy w środku. Ale przed powrotem możesz jeszcze uzyskać przynajmniej 100 grep (najgorszy przypadek 2 miliony).

2. Wyszukiwanie indeksowane. Zakładasz, że tekst zawiera zestaw słów, a wyszukiwanie ogranicza się do ustalonych długości słów. W takim przypadku dokument jest indeksowany we wszystkich możliwych wystąpieniach słów. Jest to często nazywane „wyszukiwaniem pełnotekstowym”. Istnieje wiele algorytmów do wykonania tego i liczba projektów typu open source, z których można bezpośrednio korzystać. Wiele z nich obsługuje również wyszukiwanie z
   użyciem symboli wieloznacznych, wyszukiwanie przybliżone itp., Jak poniżej: a. Apache Lucene: http://lucene.apache.org/java/docs/index.html
   b. OpenFTS: http://openfts.sourceforge.net/
   c. Sfinks http://sphinxsearch.com/

Najprawdopodobniej, jeśli potrzebujesz „ustalonych słów” jako zapytań, podejście drugie będzie bardzo szybkie i skuteczne.

Technologia, której szukasz, to indeksowanie pełnotekstowe. Większość RDBMS ma wbudowane funkcje, które mogłyby tu działać, lub możesz użyć czegoś takiego jak Lucene, jeśli chcesz uzyskać bardziej wyszukany i / lub po prostu uruchomić go w pamięci.

Czy zastanawiałeś się nad trie ? Zasadniczo budujesz drzewo, używając wspólnych prefiksów, więc wszystkie słowa zaczynające się na te same litery są dziećmi tego samego węzła. Jeśli masz zamiar wesprzeć dopasowanie na dowolnym podciągu, musisz wygenerować jakiś permutowany indeks i zbudować z niego trie. Może to jednak skończyć z wyczerpaniem wymagań dotyczących przechowywania.

Chciałbym dodać do odpowiedzi Wyatta Barnetta, że ​​rozwiązanie RDBMS z indeksowaniem pełnotekstowym w odpowiedniej kolumnie będzie działać, ale jeśli chcesz użyć lokalnej pamięci podręcznej wcześniej pobranych rekordów, musisz zaplanować wykorzystanie tych buforowanych rekordów na twoją korzyść.

Jedną z opcji jest zebranie unikalnych identyfikatorów tych rekordów, których WYRAŹNIE nie chcesz odzyskać z zapytania i dołączyć je, ewentualnie w a NOT INlub a NOT EXISTS.

Należy jednak zachować ostrożność, używając NOT INlub NOT EXISTSnie jest to tanie i MOŻE negatywnie wpływać na wydajność lub plan zapytań w zależności od używanego silnika bazy danych. Uruchom plan wyjaśniania dla ostatniego zapytania, aby upewnić się, że wszystkie indeksy w odpowiednich kolumnach są wykorzystywane.

Nie zaszkodzi również porównanie wydajności między dwoma podejściami, aby sprawdzić, która jest szybsza. Możesz być zaskoczony, gdy dowiesz się, że utrzymywanie lokalnej pamięci podręcznej i jawne filtrowanie tych z zapytania może mieć gorszą wydajność niż dokładnie dostrojone zapytanie, które pobiera wszystkie rekordy.

Na wypadek, gdybyś to przegapił. Jeśli używasz Lucene dla swojej bazy danych zamiast wyszukiwania tekstowego obsługiwanego w DB, będziesz musiał zachować szczególną ostrożność podczas modyfikowania swojego DB. Jak upewnić się, że możesz mieć atomowość, gdy musisz dokonywać zmian zarówno w DB, jak i zasobach zewnętrznych (Lucene)? Tak, można to zrobić, ale będzie dużo pracy.

Krótko mówiąc, tracisz obsługę transakcji DB, jeśli umieścisz Lucene w swoim schemacie danych.

Czy rozważałeś Sfinksa? http://sphinxsearch.com, jeśli możesz użyć narzędzia innej firmy, byłoby to idealne rozwiązanie do tego, co próbujesz osiągnąć, jest znacznie bardziej wydajne w wyszukiwaniu pełnotekstowym niż jakiekolwiek RDBMS, którego osobiście używałem.

Dziwne jest to, że żadna z odpowiedzi nie przedstawiła terminu „indeks odwrócony” , technologii leżącej u podstaw wszystkich rozwiązań podobnych do Apache Lucene i innych.

Indeks odwrócony to odwzorowanie słów na dokumenty („indeks odwrócony na poziomie rekordu”) lub nawet dokładne lokalizacje słów w dokumencie („indeks odwrócony na poziomie słów”).

Operacje logiczne AND i OR są łatwe do wdrożenia. Jeśli masz dokładne lokalizacje słów, możesz szukać sąsiednich słów, umożliwiając w ten sposób wyszukiwanie fraz.

Pomyśl więc o indeksie zawierającym krotki (słowo, plik, lokalizacja). Kiedy masz np. („Odwrócony”, „foo.txt”, 123), po prostu sprawdzasz, czy („indeks”, „foo.txt”, 124) jest częścią indeksu, aby wyszukać pełną frazę „indeks odwrócony” .

Chociaż nie polecam Ci od nowa zaimplementować wyszukiwarki pełnotekstowej, warto wiedzieć, jak działają takie technologie, jak Apache Lucene.

Dlatego zalecam, aby dowiedzieć się, jak działają indeksy odwrócone i wybrać technologię, która je wykorzystuje, na przykład Apache Lucene. Wtedy przynajmniej dobrze rozumiesz, co można zrobić, a czego nie.