(mysql php) Geschwindigkeitsoptimierung bei Suche? oder Anzeige?

[Fabian]

Hallo Forumaner,

ich habe eine Frage zum Optimieren von Suchanfragen.

Der User soll bei Eingabe seiner Daten min. 1 und max. 3 von 15 Kategorien anwählen können, in welchen bei einer Suche die Daten dann erscheinen sollen.

Auf der Sucheseite soll man entsprechend aus 1-15 Kategorien auswählen können wobei man entweder nur nach einem Kriterium oder auch nach allen 15 Kriterien suchen kann.

Ist es nun sinvoll, bei der Kategorisierung alle 15 Kategorien in eine Tabelle zu übernehmen und diese mit 1 bzw. 0 zu füllen.

Variante A
Kategorie
Auto Fahrrad Flugzeug Moped ... bis 15
  0    1       1        0

Suche: Wenn z.B. Fahrrad ausgewählt: Gehe in Spalte Fahrrad und gib alle Spalten mit einer "1" aus.

Oder sollte man in der Tabelle lieber nur drei Spalten für die Kategorien belegen und die Kategorien z.B. zuvor mit einem Index belegen?
Variante B
Kategorie 1         Kategorie  2         Kategorie 3
   Fahrrad            Flugzeug                leer

Suche: Wenn z.B. Fahrrad ausgewählt: Gehe in Spalte Kategorie 1 und suche nach Fahrrad, gehe dann in Kategorie 2 suche nach Fahrrad und gehe in Kategorie 3 und suche nach Fahrrad.

Optmiert werden soll die Suchzeit bei sehr vielen gleichzeitigen Suchanfragen.

Vielen Dank für Eure Antworten

Grüße aus Braunschweig

Fabian

[Cheatah]

Hi,

Oder sollte man in der Tabelle lieber nur drei Spalten für die Kategorien belegen

nah dran, aber doch leicht daneben :-)

Du hast hier eine typische n:m Beziehung: n (1 bis oo) Datensätze werden mit je m (1 bis 3) Kategorien verknüpft. Das heißt, Du hast eine Tabelle "Daten", u.a. mit einer ID, eine Tabelle "Kategorien", ebenfalls mit einer (eigenen) ID, und eine Verknüpfungstabelle "Daten_Kategorien" mit den beiden Spalten "ref_Daten" und "ref_Kategorien" ("ref" für "Referenz" - den Namen kannst Du natürlich beliebig wählen).

und die Kategorien z.B. zuvor mit einem Index belegen?

Dass Du sinnvolle Indizes erstellst, die auf die SQL-Statements passen, ist eh klar.

Suche: Wenn z.B. Fahrrad ausgewählt: Gehe in Spalte Kategorie 1 und suche nach Fahrrad, gehe dann in Kategorie 2 suche nach Fahrrad und gehe in Kategorie 3 und suche nach Fahrrad.

Problematisch wird es spätestens dann, wenn Du eine vierte Kategorie erlauben willst - und wenn Du eine Suche über mehrere Kategorien zulässt, wird _dieses_ Statement kaum noch les-, geschweige denn wartbar :-)

Optmiert werden soll die Suchzeit bei sehr vielen gleichzeitigen Suchanfragen.

Welches DBMS verwendest Du eigentlich?

Cheatah

[Fabian]

Ich verwende Mysql und PHP.

Insgesamt hätte ich 15 Kategorien. Man kann mein Vorhaben gut mit einem Anzeigenmarkt vergleichen.

Der Bietende kann aus 15 Kategorien 1-3 Kategorien auswählen. Z.b. wenn er einen Fernseher verkaufen will: TV, Elektronik, neuwertig

Jetzt frage ich mich nur, wie ich die Daten am effizientesten speichern soll.

Drei Spalten mit der ausgewählten Kategorie des Bietenden
tv        elektronik      neuwertig
brot        alt               tv
.
.
.

oder alle Kategorien in 15 Spalten
radio auto tv brot elektronik   alt neuwertig ...
 0     0   1    0     1          0     1      ...
 0     0   1    1     0          1     0      ...
.
.
.

Entscheidend soll die Suchzeit sein

Grüße Fabian

[Kerstin]

Hallo Fabian,

schau Dir mal diese Doku über Datenbanken an
http://ffm.junetz.de/members/reeg/

Gruss Kerstin

[Cheatah]

Hi,

Ich verwende Mysql und PHP.

ah. MySQL kann keine Subselects, das macht die Sache etwas schwieriger.

Jetzt frage ich mich nur, wie ich die Daten am effizientesten speichern soll.
Drei Spalten mit der ausgewählten Kategorie des Bietenden
oder alle Kategorien in 15 Spalten

Weder noch. Wie bereits in meiner vorherigen Antwort erläutert, gehören die Daten in eine Kreuztabelle.

Neben Kerstins Tipp: Suche auch mal im Netz nach "SQL in 21 Tagen". Das ist quasi eine Standard-Lektüre für Einsteiger.

Cheatah

[Kerstin]

Hi

Neben Kerstins Tipp: Suche auch mal im Netz nach "SQL in 21 Tagen". Das ist quasi eine Standard-Lektüre für Einsteiger.

der Link dazu is http://www.mut.de/media/buecher/SQL/data/start.htm
und speziell für mysql interessant is auch
http://www.little-idiot.de/mysql/

Gruss Kerstin

[Michael Schröpl]

Hi Cheatah,

ah. MySQL kann keine Subselects, das macht die Sache etwas schwieriger.

Nicht unbedingt - je nach konkreter Ausprägung des Falls läßt sich mit JOINs bze. temporären Tabellen das meiste ziemlich gut hinkriegen.
(Ich habe selbst so eine Architektur in einer Suchmaschine.)

Nachfolgend gehe ich mal grundsätzlich auf das beschriebene Problem ein, wobei die entsprechenden Ausführungen auf Millionen von Datensätzen ausgelegt sind - bei kleinen Mengen wäre das hier Ausgeführte sicherlich Overkill. Mir geht es aber mal um's Prinzip ...

Interessant für die Beantwortung der Frage finde ich Aussagen über die Projektivität der einzelnen Felder.
Das Problem ist ja, daß ein Boolean-Feld offensichtlich genau zwei Werte enthält - ein Filter über dieses Feld liefert also im Erwartungswert die Hälfte aller Treffer der Tabelle. (Sollte ein dritter "don't know"-Wert möglich sein, ändert das nur die konkreten Werte meiner nachfolgenden Formeln, nicht aber die grundlegenden Aussagen.)
Das ist aber viel zuviel, um mit Indexbäumen noch irgend etwas zu gewinnen - der Indexzugriff ist in diesem Fall bereits wesentlich langsamer als ein ganz trivialer full table scan.
Wenn die Treffermenge einer Spalte im Schnitt nicht signifikant kleiner als 10-15% ist, dann sind Indexzugriffe nur über diese eine Spalte meistens verkehrt.

Wesentlich besser wird es, wenn ein gemeinsamer Index über sämtliche 15 Flags-Spalten verwendet wird. Denn in diesem Falle liegen größenordnungsmäßig 2^15 Index-Werte vor, und die Projektivität wird folglich ganz ausgezeichnet sein, weil der Indexzugriff nur 2^-15 der vorliegenden Daten zurück liefert. Innerhalb von 15 Vergleichen kann die Menge aller Datensätze mit exakt dieser Flag-Belegung aus beliebig vielen (!) vorliegenden Datensätzen berechnet werden - die Suchdauer ist praktisch unabhängig von der Größe des zu durchsuchenden Datenbestands.

Für die konkrete Anwendung bedeutet dies, daß eine Suche nach allen 15 Kriterien _sehr_ viel schneller sein muß als eine Suche nach nur einem Kriterium (und nebenbei auch noch viel bessere Ergebnisse liefern wird, denn die Hälfte aller Daten überflutet den Betrachter üblicherweise.
Falls es vom Inhalt der Anwendung also möglich ist, sollten die Benutzer ermutigt werden (Formular-Defaults?), möglichst viele Flags tatsächlich zu setzen - je kleiner die Treffermenge, desto schneller kann sie berechnet werden.

Schwierig wird das, wenn die Flags inhaltlich derartig sind, daß bei einigen typischerweise "don't care" durch den Anwender erwünscht oder gar notwendig ist. In diesem Falle wird der Nutzen eines Indexzugriffs wieder dramatisch einbrechen, weil bereits 5 von 15 don't cares die Treffermenge um Faktor 2^5 aufblasen und die Projektivität des Indexzugriffs entsprechend reduzieren.

Und schlimmer noch: Ein Abstieg innerhalb eines Indexbaums erfolgt sinnvollerweise durch fortgesetzte Teilung der verbleibenden potentiellen Trefferdaten. Genau das wird aber gleich ein Problem werden.

Der Indexschlüssel enthalte im vorliegenden Modell also die 15 Flags als 15 Bits (z. B. einer Integer-Zahl oder was auch immer). Ist bereits das 2. Flag in der Anforderung nicht gesetzt, dann kann der Indexzugriff an dieser Stelle nicht mehr unterteilen - er müßte parallele Suchvorgänge in mehrere Richtungen starten, und das werden die mir bekannten RDBMS-Implementierungen wahrscheinlich einfach nicht können (das ist Kristallkugel-KI - ein _sehr_ schlauer query optimizer _könnte_ begreifen, daß von den 15 Flags immerhin 14 gesetzt sind und sich das von mir beschriebene Verfahren lohnen würde ... aber wo gibt es den?).
Deshalb wäre es sinnvoll, innerhalb des Indexes die 15 Flags wenigstens in absteigender Wahrscheinlichkeit für die Nicht-Angabe durch den Anwender zu _sortieren_ - je länger der Präfix von fortlaufend gesetzten Flags sind, desto höher ist die Chance, daß ein effizienter Indexzugriff dabei zustande kommt.

Die Gefahr, daß relativ viele katastrophal schlechte Zugriffe entstehen, weil der query analyzer nicht begreift, wann ein full table scan besser wäre, ist allerdings nicht von der Hand zu weisen.
In Oracle gibt es ein zusätzliches Sprachelement namens "hints" - das sind syntaktisch gesehen Kommentare für SQL, welche aber dem query optimizer sagen können, welche Indexe er verwenden soll und ähnliches Zeug. (Jaja, wir machen von hinten durch die Brust ins Auge aus einer 4GL wieder eine 3GL, weil es Performance bringt ... ;-)
Und die PHP-Anwendung könnte durch Analyse der gesetzten Flags sehr wohl erkennen, ob eine solche Super-GAU-Anfrage vorliegt oder ob hinreichend viele Präfix-Flags gesetzt sind.
Ob aber mySQL ein Sprachmittel besitzt, um die Verwendung bestimmter Indexe zu steuern, da bin ich überfragt.

Viele Grüße
      Michael

P.S.: Solange genau _ein_ Indexbaum über diese 15-Tupel existiert, wird
      das Fehlen eines der "vorderen" Flags einen GAU auslösen.
      Falls die entsprechenden Ressourcen verfügbar sind (inklusive der
      Möglichkeit, Indexzugriffe bedingt zu formulieren), wäre es eine
      enorm performance-steigernde Maßnahme, mehrere (redundante) Index-
      bäume (mit verschieden angeordneten Flag-Listen) anzubieten.
      Leider erfordert die _perfekte_ Lösung dann 2^15 solcher Bäume ...
      das wird sich beim besten Willen nicht realisieren lassen.

[Michael Schröpl]

Hi Fabian,

Auf der Sucheseite soll man entsprechend aus 1-15 Kategorien auswählen
können wobei man entweder nur nach einem Kriterium oder auch nach allen
15 Kriterien suchen kann.

oha - also doch 1 aus N. Denn ...

Kategorie
Auto Fahrrad Flugzeug Moped ... bis 15
  0    1       1        0

... diese Tabelle suggerierte mir das Gegenteil.

Suche: Wenn z.B. Fahrrad ausgewählt: Gehe in Spalte Fahrrad und gib
alle Spalten mit einer "1" aus.

Ich fürchte, für diesen Fall habe ich mit meinem anderen Beitrag in diesem Thread weit über Dein Ziel hinaus geschossen.

In Deinem Fall steht und fällt die Tuning-Fähigkeit mit der Wahrschein-
lichkeit für eine "1" innerhalb _jeder_ einzelnen Spalte.
Wenn diese im Bereich von 10-15% liegt, ist Index oder full table scan
wahrscheinlich ähnlich schnell; sind es deutlich weniger Einsen, dann
wird ein Index entsprechend viel besser - vorausgesetzt, Du suchst immer
nur nach Einsen und nie nach Nullen. (Wenn Du nach Nullen suchst, dann
hast Du ohnehin verloren - und Deine Benutzer ebenfalls.)

Oder sollte man in der Tabelle lieber nur drei Spalten für die Kategorien
belegen und die Kategorien z.B. zuvor mit einem Index belegen?
Variante B
Kategorie 1         Kategorie  2         Kategorie 3
   Fahrrad            Flugzeug                leer

Wenn es um die grundlegende Architektur Deiner Tabellen geht (also dort
noch nicht alles in Stein gemeißelt ist), dann fehlen mir etliche Infor-
mationen über die Semantik der Daten.
Das, was ich bisher gesehen habe, sieht nun alles andere als normalform-
artig aus (leider) - aber eine konkrete Alternative vorzuschlagen, dafür
müßte ich die _vollständige_ Aufgabenstellung kennen.
Ich halte es aber für durchaus wahrscheinlich, daß diese Architektur der
wichtigste Tuning-Aspekt Deiner gesamten Anwendung wird.

Stell Dir mal vor, Du würdest Deine bisher einzige Tabelle in eine Viel-
zahl von Tabellen zerschlagen, so daß in jeder Tabelle überhaupt nur
noch diejenigen Zeilen drin sind, welche in der entsprechenden Deiner
15 Spalten eine Eins aufweisen - plus weitere Spalten für JOINs zu den
anderen Tabellen. Das würde eine Suche enorm beschleunigen!
Es würde Dich andererseits zwingen, zugehörige Attribute der Treffer
über JOINs aus anderen Tabellen zu holen. Deine gesamte Anwendung würde
anders arbeiten - vor allem UPDATEs auf diese Tabellensysteme würden
völlig anders funktionieren, Du bräuchtest transaktionssichere Tabellen
und tausend andere Dinge mehr.
Falls Such-Geschwindigkeit ein wesentlicher Teil der Anforderung ist,
kann es durchaus bedeuten, daß sich die gesamte Tabellen-Architektur
dieser Anforderung unterordnen muß.

Ich selbst habe gerade in einer Anwendung die Daten einer Tabelle auf
vier identisch formatierte Tabellen verteilt, um Performance beim Suchen
zu gewinnen - quasi als vierstufiges Caching-Systen. Damit habe ich die
heilige Normalformeigschaft der Tabellen zugunsten einer auf die wahr-
scheinliche Verteilung der Suchanfragen optimierten Struktur geopfert.
Meine SQL-Statements sind natürlich wesentlich komplexer geworden, aber
die generiere ich sowieso mit einem Programm, und ob das dann eine
Schleife über mehrere Tabellen macht (und abbricht, wenn es merkt, daß
es das darf) oder nur ein einziges SQL-Statement abfeuert, das macht in
Perl auch nur ein paar Dutzend Zeilen mehr aus. Und ist ist sauschnell
geworden!

Optmiert werden soll die Suchzeit bei sehr vielen gleichzeitigen
Suchanfragen.

Die Gleichzeitigkeit der Anfragen ist relativ egal (wenn ich mal abstra-
hiere, wieviel RAM eine bestimmte Implementierungstechnik erfordert -
aber das herauszufinden, dafür sind Kenntnisse weit unterhalb der SQL-
Ebene erforderlich), weil Du ja ausschließlich Lesezugriffe machst.

Tune eine einzige Abfrage, dann tunest Du den Schnitt aus allen; gib
aber vor allem auf den worst case acht - es darf nicht eine einzige
unegschickte Anfrage so viel Last erzeugen wie tausend geschickte.
(Genau das war mein Problem vor der Verteilung auf mehrere Tabellen ...)

Viele Grüße
      Michael

P.S.:

Wenn Du hochparallel arbeiten willst, dann mach Dir mal Gedanken über
eine entsprechende Hardware-Unterstützung. Du willst beispielsweise
ganz bestimmt nicht, daß Tabelle und Index auf derselben physikalischen
Festplatte liegen und der Festplattenkopf ständig hin- und herpositioniert.
Je mehr parallele Festplattenzugriffe Du ermöglichst (durch striping der
Objekte), desto weniger Verlust an Kopfpositionierungen wirst Du haben.
Tuning findet auf _allen_ Ebenen statt - Du kannst Dir nicht aussuchen,
auf welcher Ebene der größe Faktor an Beschleunigung zu finden ist - das
kann SQL sein, muß aber nicht. Überhaupt ist für Tuning immer ein ganz-
heitlicher Blick auf das System zu empfehlen - denn es ist ein Unter-
schied, ob Du die mittlere Antwortzeit optimieren oder ob Du für einen
möglichst hohen Anteil der Anfragen eine bestimmte Höchst-Antwortzeit
garantieren willst.
Ich selbst habe beispielsweise durch meine Cache-Architektur bewußt die
"schnellsten" Anfragen etwas gebremst (das ist aber egal, die sind immer
noch schnell genug), weil ich gleichzeitig bei den langsamsten (auch wenn
das wenige sind!) einen riesigen Faktor gewonnen habe. In der Summe habe
ich zwar vielleicht trotzdem noch eine höhere mittlere Antwortzeit, aber
wahrscheinlich mehr zufriedene Anwender ...