2010-11-29 33 views
7

Ich habe eine Tabelle "Test" mit Millionen von Einträgen. Jede Zeile enthält ein Gleitkomma "Feature" und eine "Anzahl", wie oft diese Funktion im Element "id" vorhanden ist. Der Primärschlüssel für diese Tabelle ist die Kombination von "ID" und "Merkmal", d. H. Jeder Gegenstand kann mehrere Merkmale aufweisen. Es gibt normalerweise ein paar hundert bis ein paar tausend Feature-Einträge pro Artikel-ID.mySQL: Ist es möglich, diese Abfrage schneller zu machen?

create table test 
(
    id  int not null, 
    feature double not null, 
    count int not null 
); 

Die Aufgabe ist es, die 500 am ähnlichsten Elemente zu einem bestimmten Referenzelement zu finden. Die Ähnlichkeit wird in der Anzahl identischer Merkmalswerte in beiden Elementen gemessen. Die Abfrage, die ich gefunden habe, ist unten zitiert, aber trotz der korrekten Verwendung von Indizes enthält der Ausführungsplan immer noch "temporary verwenden" und "using filesort", was eine unakzeptable Leistung für meinen Anwendungsfall ergibt.

select 
    t1.id, 
    t2.id, 
    sum(least(t1.count, t2.count)) as priority 
from test as t1 
inner join test as t2 
    on t2.feature = t1.feature 
where t1.id = {some user supplied id value} 
group by t1.id, t2.id 
order by priority desc 
limit 500; 

Irgendwelche Ideen, wie man das verbessert? Das Schema kann geändert und Indizes nach Bedarf hinzugefügt werden.

+0

Könnten Sie bitte die Ausgabe von SHOW CREATE TABLE test' posten? – Quassnoi

+0

CREATE TABLE 'test' ( ' id' int (11) NOT NULL, 'feature' Doppel NOT NULL, ' count' int (11) NOT NULL, KEY 'idx_one' (' feature'), KEY 'idx_two' (' id') ) ENGINE = InnoDB DEFAULT CHARSET = utf8 ' – BuschnicK

+0

Ich kann Ihnen auch eine 2MB 1.000.000 Zeile datadump senden, wenn Sie es wollen ... – BuschnicK

Antwort

4

Mit dem aktuellen Schema, diese Abfrage kann kaum verbessert werden.

Sie haben bereits einen Index für feature und dies ist das Beste, was Sie mit dem aktuellen Schemadesign tun können.

Das Problem ist mehr als ist keine Beziehung der Reihenfolge.Wenn ab ähnlicher ist als c, bedeutet dies nicht, dass c weniger ähnlich zu a ist als zu b. Daher können Sie keinen einzelnen Index erstellen, der diese Beziehung beschreibt, und Sie müssen dies für jeden einzelnen Artikel separat durchführen, wodurch Ihr Index N^2 Einträge lang wird, wobei N die Anzahl der Elemente ist.

Wenn Sie immer nur die obersten 500 Elemente benötigen, können Sie Ihren Index auf diese Zahl beschränken (in diesem Fall enthält er 500 * N Einträge).

MySQL unterstützt nicht indizierte oder materialisierte Ansichten, so dass Sie es selbst tun müssen:

  1. eine Tabelle wie folgt erstellen:

    CREATE TABLE similarity 
         (
         id1 INT NOT NULL, 
         id2 INT NOT NULL, 
         similarity DOUBLE NOT NULL, 
         PRIMARY KEY (id1, id2), 
         KEY (id1, similarity) 
         ) 
    
  2. Jedes Mal, wenn Sie eine neue Funktion einfügen in die Tabelle, spiegeln die Änderungen in der similarity:

  3. Auf zeitnah, entfernen Sie die überschüssigen Ähnlichkeiten:

    DELETE s 
    FROM (
         SELECT id1, 
           (
           SELECT similarity 
           FROM similarity si 
           WHERE si.id1 = s.id1 
           ORDER BY 
             si.id1 DESC, si.similarity DESC 
           LIMIT 499, 1 
           ) AS cs 
         FROM (
           SELECT DISTINCT id1 
           FROM similarity 
           ) s 
         ) q 
    JOIN similarity s 
    ON  s.id1 = q.id1 
         AND s.similarity < q.cs 
    
  4. Abfrage Ihrer Daten:

    SELECT id2 
    FROM similarity 
    WHERE id1 = @myid 
    ORDER BY 
         similarity DESC 
    LIMIT 500 
    
2

Eine Optimierung wäre das Element sich von der auszuschließen Selbst beitreten:

inner join test as t2 
    on t2.feature = t1.feature and t2.id <> t1.id 
            ^^^^^^^^^^^^^^ 

Für weitere Beschleunigung, einen abdeckenden Index auf (feature, id, count) erstellen.

+1

Ich hatte den Self-Join bereits vermieden, aber entfernt, um die Abfrage einfacher zu machen. In dem größeren Schema der Dinge ist der Leistungseinfluss davon minimal. – BuschnicK

+0

Ich habe gerade einen Covering Index anstelle von einzelnen Indizes versucht, aber es beseitigt nicht den temporären/filesort, so dass es nicht viel hilft. Ich fürchte, das Provisorium kann nicht vermieden werden, solange ich nach einem berechneten Wert sortiere. Also die Frage nach einer Schemaänderung oder alternativen Abfrage. – BuschnicK

+0

@BuschnicK: Wie oft ändern sich die Daten in der Tabelle? Müssen die Änderungen sofort in der Abfrage sichtbar sein? – Andomar

3

Eine Gleitkommazahl als Teil des Primärschlüssels (PK) ist ein Mörder. Ändern Eindeutiger Schlüssel (UK), Foreign Key (FK) usw.

Um die Leistung Ihrer SQL-Abfrage ein Vielfaches zu verbessern, versuchen Sie Ihr Schema wie unten - was das betrifft, ein Teil jeden Zwang es sollte nicht sein:

Mit Ihrer Testtabelle wie oben normalisiert, habe ich Elemente und Features zu eigenen separaten Tabellen getrennt und dies wird mehr als eine Mapping-Tabelle mit der Anzahl der einzelnen Zuordnung.

Wenn Sie jetzt die zuvor gesendete SQL-Abfrage mit kleinen Änderungen wie unten erwähnt auslösen, sollten Sie eine deutliche/drastische Verbesserung der SQL-Abfrageleistung sehen.

select t1.id, t2.id, sum(least(t1.count, t2.count)) as priority 
from test as t1 inner join test as t2 on t2.feature_id = t1.feature_id 
where t1.id = {some user supplied id value} 
group by t1.id, t2.id 
order by priority desc 
limit 500; 

Prost!

+1

Ich werde es versuchen, sobald ich wieder im Büro bin - danke für den Vorschlag, es klingt plausibel! – BuschnicK

+0

Warum genau ist Floating Point Killer hier? Es ist nur zu vergleichen. Es wird keine Fließkomma-Arithmetik durchgeführt. –

+0

Ok, ich habe das getestet und es scheint ein wenig zu helfen, aber nicht viel. Die Abfragepläne sehen in beiden Fällen identisch aus. Das einzige, was besser sein kann, ist die Behandlung von Ganzzahlen gegenüber Gleitkommazahlen in Indizes/Vergleichen. Eine lohnende Optimierung auf der Mikroebene, aber ich fürchte, ich brauche zuerst einen effizienteren Algorithmus/Abfrage. – BuschnicK

-1

Kannst du es auf einen einzigen Tisch bringen? Durch die Verwendung von Unterabfragen können Sie den Join vermeiden, und es wird ein Gewinn, wenn die Unterabfragen schneller, indizierter und genau einmal ausgeführt werden. So etwas (ungetestet).

select
t2.id,
SUM(t2.count) as priority
from test as t2
where t2.id = {some user supplied id value} AND
t2.count > (SELECT MIN(count) FROM test t1 WHERE id= {some user supplied value}) AND
t2.feature IN (SELECT feature FROM test t1 WHERE id= {some user supplied value})
group by t1.id
order by priority desc
limit 500;

Wenn das nicht funktioniert Mysql konstanten Tabellen schrecklich sind die inneren wählt bei der Realisierung und wird sie für jede Zeile erneut auszuführen. Wenn Sie sie erneut in eine Auswahl einfügen, wird eine konstante Tabellensuche erzwungen. Heres ein Hack:


select
t1.id,
SUM(t2.count) as priority
from test as t2
where t2.id = {some user supplied id value} AND
t2.count > (
SELECT * FROM (
SELECT MIN(count) FROM test t1 WHERE id= {some user supplied
value}) as const) AND
t2.feature IN (SELECT * from (
SELECT feature FROM test t1 WHERE id= {some user supplied value}
) as const)
group by t1.id
order by priority desc
limit 500;

+0

Sorry, aber ich sehe nicht, wie diese Abfrage möglicherweise äquivalente Ergebnisse liefern könnte? – BuschnicK

+0

Ich denke, du hast Recht. Es entfernt den Join korrekt, indem er die Join-Bedingung in eine WHERE-Klausel mit einem Subselect verschiebt, repliziert jedoch nicht die korrekte Summenlogik (least()). – bot403

0

ich damit anfangen würde ... Liebe auf der Leistung zurück zu hören Sie anschauen. Ich glaube nicht, dass Sie die LEAST (von t1 vs t2 counts) benötigten. Wenn Sie die WHERE zuerst basierend auf ID = {ein Wert} qualifizieren, werden Sie offensichtlich alle diese "Features" erhalten. Dann über einen Self-Join zu sich selbst nur mit den passenden "Features", erhalten Sie eine Zählung. Da Sie es mit ID1 und ID2 abbrechen, wird jedes "Feature" einmal gezählt. Am Ende dieser Abfrage, da ich t2.ID nicht explizit ausschließe, gleich dem {einige Benutzerwert}, sollte die Zählung die GENAUE Anzahl von Merkmalen in t1 sein, und alles andere darunter wäre deine nächste nächste Übereinstimmung .

Ich würde sicherstellen, dass ich einen Index über ID und FEATURE hatte.

select STRAIGHT_JOIN 
     t1.id, 
     t2.id, 
     count(*) as MatchedInBoth 
    from 
     test as t1, 
     test as t2 
    where 
      t1.id = {some user value} 
     and t1.feature = t2.feature 
    group by 
     t1.id, 
     t2.id 
    order by 
     MatchedInBoth desc 
    limit 
     500; 

Das Ergebnis geben könnte so etwas wie

t1   t2   MatchedInBoth 
{user value} {user value} 275 
{user value} Other ID 1 270 
{user value} Other ID 2 241 
{user value} Other ID 3 218 
{user value} Other ID 4 197 
{user value} Other ID 5 163, etc 
Verwandte Themen