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

32

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.

Giorgio
źródło
2
2 miliony rekordów * 500 bajtów = 1 GB danych. Jest to dużo danych do przeszukiwania, niezależnie od tego, w jaki sposób to robisz - czy każda wartość X może być unikalna, czy też będziesz mieć wiele rekordów o tej samej wartości X?
1
Byłoby to również dużo danych, które należy zapisać w pamięci jako pamięć podręczną do szybkiego wyszukiwania. Oznaczałoby to więcej niż 1 GB na sesję użytkownika.
wałek klonowy
Mój poprzedni komentarz zakłada aplikację internetową. Czy to aplikacja internetowa?
wałek klonowy
Jest to aplikacja komputerowa. Wartości w rekordach niekoniecznie są unikalne. Ponadto szukam podłańcucha, nie pasującego dokładnie.
Giorgio
@maple_shaft: Buforowałbym tylko te rekordy, do których ostatnio miałem dostęp. Jeśli zmienię ciąg zapytania, a rekord nadal pasuje, nadal znajduje się w pamięci podręcznej.
Giorgio,

Odpowiedzi:

20

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.

Dipan Mehta
źródło
2
Jest to ciekawa koncepcja, ale wydaje się mało prawdopodobne, aby deweloper mógł z łatwością przeszukiwać 1 GB danych tekstowych szybciej i wydajniej niż silnik bazy danych. O wiele mądrzejsi ludzie niż ty i ja pracowaliśmy nad optymalizatorami zapytań, aby to zrobić i myślenie, że możesz to zrobić bardziej efektywnie, jest trochę naiwne.
wałek klonowy
4
@maple_shaft Podane przeze mnie przykłady nie są silnikami baz danych RDBMS. Są bardziej jak „wyszukiwarki”, jeśli chcesz to nazwać. Istnieje ogromna różnica pojęciowa między pobieraniem listy z indeksu (lub tabeli skrótów) a przeszukiwaniem 1 GB danych od nowa za każdym razem, gdy uruchamiane jest zapytanie. To, co sugeruję, nie jest drobną poprawką.
Dipan Mehta
To wydaje się interesujący pomysł, ale zastanawiam się, jak by to działało. Miałbym ponad 2 000 000 plików, każdy o wielkości około pół kilobajta. A może sugerujesz mieć więcej niż jeden rekord na plik? Jaka byłaby różnica w stosunku do bazy danych?
Giorgio
Nie jestem przekonany, że to niekoniecznie działałoby lepiej niż, powiedzmy, indeks pełnotekstowy SQL.
Kirk Broadhurst,
@Giorgio - tak, tak działałyby wyszukiwarki pełnotekstowe. Kluczową różnicą są tutaj strony wstępnie indeksowane w porównaniu z wyszukiwaniem w pamięci (ponownie za każdym razem, gdy pojawia się zapytanie).
Dipan Mehta 10.11.11
21

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.

Wyatt Barnett
źródło
1
Moim zdaniem opcje pełnego tekstu w dowolnym RDBMS są obejściem, dzięki któremu można zrobić coś, do czego nie jest przeznaczony: „przeszukać stos nieuporządkowanych niepowiązanych danych”. Jeśli budujesz wyszukiwarkę, po prostu nie używasz RDBMS. Może działać dla małych zestawów danych, ale umożliwia skalowanie dowolnego rodzaju. Przeszukiwanie stosów nieustrukturyzowanych danych nie jest gwoździem, więc nie używaj młotka. Użyj odpowiedniego narzędzia do pracy.
Pieter B
8

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.

TMN
źródło
1
TAK! Myślałem o strukturze drzewa i przypomniałem sobie, że może mi się podobać coś podobnego, ale nie pamiętałem trie, ponieważ nigdy z nich nie korzystałem. Jeśli chodzi o wymagania dotyczące miejsca: pamiętaj, że muszę pobrać tylko pierwsze N ​​wpisów (np. N = 100), ponieważ nie ma sensu zapełnianie tabeli 20000 trafieniami. Tak więc każdy węzeł trie wskazywałby co najwyżej N pozycji. Zapomniałem też wspomnieć, że potrzebuję szybkiego dostępu, ale nie potrzebuję szybkiej aktualizacji, ponieważ dane są ładowane tylko raz. Pomysł trie na indeksie permutacyjnym może naprawdę zadziałać!
Giorgio
1
Dobra odpowiedź, ale jak zauważysz, trie świetnie nadaje się do dopasowania początku słów, ale szybko stanie się złożona i bardzo duża, jeśli dopasuje dowolny podłańcuch ...
Kirk Broadhurst
Jako pierwszy eksperyment próbowałem zbudować zestaw wszystkich podłańcuchów pojawiających się w ciągach, które muszę przeszukiwać, które, jeśli dobrze rozumiem, odpowiadają ścieżkom trie. Dostałem wyjątek braku pamięci (z 256 mln sterty dla JVM) przy podciągu o długości 6. Obawiam się, że to rozwiązanie nie jest możliwe, chyba że robię coś złego.
Giorgio
5

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.

wałek klonowy
źródło
maple_shaft i @Wyatt Barnett: Bardzo dziękuję za sugestie. Będę musiał przeczytać i wypróbować różne rozwiązania. Nie wszystkie bazy danych obsługują pełne indeksowanie, MySQL (którego obecnie używam) obsługuje ( dev.mysql.com/doc/refman/5.5/en/fulltext-search.html ). Spróbuję wykonać kilka testów, a następnie zgłosić się tutaj.
Giorgio
2

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.

Poinformowano
źródło
1
Jak już wspomniano, problem nie wydaje się dobrze pasować do RDMS.
Pieter B
1

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.

twigg
źródło
3
a głosowanie w dół jest za?
twigg 21.04.16
1

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.

juhist
źródło