MySQL 5.0.18 Benchmark

Hallo
Ich habe eben mit einem Freund auf 64bit linux dual core opteron 2x2.7Ghz +raid0 diese Tabelle angelegt:

CREATE TABLE `blubb` (

`x` SMALLINT UNSIGNED NOT NULL ,
`y` SMALLINT UNSIGNED NOT NULL ,
`type` TINYINT UNSIGNED NOT NULL ,
) TYPE = MYISAM ;
X und Y sind die Koordinaten für eine Karte und type legt fest ob es nun Wasser, Land, Berg, Soldat, ... ist.
Wir haben die Werte von 1-3200 für X und Y eingetragen, also 3200² was 10 240 000 Einträge ergibt.
Dann:

SELECT * FROM `blubb` WHERE (x > 101 AND x < 400 ) AND (y > 101 AND y < 400 )

Dauer: 1,58sec
Danach haben wir auf X und Y einen Index gesetzt.
Dauer: 1,38sec
Anschließend haben wir den Ram gemountet und die Daten Ramdisk kopiert.
Dauer: 1,4sec
So und jetzt die Frage: Andere Datenbank oder ganz was anderes
Lg Kudi

Ich glaube kaum, dass es noch wesentlich schneller geht. Warum ruft ihr da auch 88804 Datensätze ab?
Wenn man nur ein paar Datensätze abruft, ist die Zeit auch wesentlich niedriger.
Hier ist ja nicht die Tabellen-Struktur oder das Verfahren die Bremse, sondern einfach die Menge an Daten.

ich hab mal was ähnliches gemacht, allerdings hab ich die daten "der reihe nach" in die db eingetragen und jedem feld eine ID gegeben und bei der db abfrage rechne ich vorher per script die IDs aus und rufe es damit ab, bringt bei mir etwa das vierfache an geschwindigkeit wie vorher, allerdings werden dadurch die db abfragen "ein wenig" größer. Die IDs dürfen dann natürlich nicht vertauscht werden.

und leg mal einen index über x und y
(key "yx" (y,x) )
sollte er auch verwenden können (nachtestbar mit explain select blah)
(falls 1. nicht so gemacht wurde, ist bissle undeutlich)

Original von mifritscher
und leg mal einen index über x und y
(key "yx" (y,x) )
sollte er auch verwenden können (nachtestbar mit explain select blah)
(falls 1. nicht so gemacht wurde, ist bissle undeutlich)

Um 0,03sek schneller
Aber die Idee mit den ID's find ich interessant. Das werde ich mal testen.

Ich wette, dass es nicht großartig schneller wird ...aus oben genannten Gründen.
Ich warte mit Spannung auf das Ergebnis

mysql hat intern einen schnellenwert, ab dem die ganze tabelle ausgelesen wird. da das dann schneller geht, als jede zeile nach bestimmten kriterien zu überprüfen. dürfte so um die 30% liegen, hängt aber von vielen faktoren ab.
überprüfe mal, obs nicht schneller ist, alle datensätze zu holen und dann im script die frage zu machen.

hä? die ganzen Daten übertragen? Das sind doch sicher ein paar MB die PHP da zu zerkauen hat.
Außerdem wo ist der Unterschied zwischen dem Auslesen der ganzen Tabelle und der Überprüfung auf einzelne Zeilen? MySQL muss auf jeden Fall beides machen um *alle relevaten* Zeilen zu übergeben.

Das mit den IDs ist auf jeden Fall schneller bei kleineren Datenmengen. Damit die SQL Abfrage nicht zu groß wird kannst du aber auch über die IDs Zeilenweise abfragen: WHERE id > a && id < b || id > c && id < d usw. [Anzahl der Zeilen].
Ein Mehrspaltenindex ist ne gute Idee, wird von MySQL aber in dem Fall nicht richtig genutzt, warum auch immer. Wenn man eine große performante Karte will und nicht über den Weg per Unique ID gegen will kann man auch eine sehr breite und niedrige Karte erstellen (z.B. 5000x250) und dann über den x Key abfragen. Auch nicht optimal aber besser als eine gleichgroße quadratische Karte.

hmm, viellecht statt 2 getrennte Vergleiche (obere/untere Grenze) between verwenden? Vielleicht klappts dann auch mit dem Index

Wenns alles nichts hilft und es auf Teufel komm raus eine sehr große Karte sein soll, bietet sich noch an, vom Allerweltswerkzeug Datenbank auf spezialisierte Werkzeuge umzusteigen, sprich eine eigens dafür entworfene Applikation zu nutzen.
TheUndeadable hat hier eine Lösung skizziert.
Wenn es dir auf ein paar (Dutzend) Megabytes nicht drauf ankommt kannst du die Karte auch im Ram behalten, dann brauchst du aber sinnvolle Datenstrukturen. Wenn die Karte genügend wenig diversifiziert ist, kann man einen Quadtree nehmen, wenn du nur wenige verschiedene Arten von Geländeeinträgen hast, kann man das Fliegengewichtmuster (Gruß an Martin ;-)) einsetzen (moderne Variante von Bitpatterns) oder mit dem Tree kombinieren.
Überlege dir auch, sowas wie Soldaten nicht in die selbe Tabelle/die selbe Datenstruktur zu speichern (hattest du unten erwähnt) wie die Landschaft, typischerweise hat man nur sehr wenig Einträge auf der Karte, so dass eine Datenbankabfrage mit Hilfe von Koordinaten wieder sehr schnell wird.
Für so eine Extraapplikation muss man natürlich auch die richtige Sprache können. Wenn es nur auf Geschwindigkeit ankommt ist php meiner bescheidenen Halbbildung nicht die richtige Wahl, da helfen Compilersprachen weiter (ohne jetzt wieder die Debatte vom Zaun brechen zu wollen).
Das ganze Thema wurde auch auf Browsergames.net diskutiert, leider ist auch dieses Thema flöten gegangen... Müsste vielleicht wirklich mal wer Klaas um die ForenDB anbetteln...

Also ich würde einfach einmal wenn die karte wirklich 10mio und mehr einträge haben muss das teil eins zweimal rastern das du auf handliche Datenmengen runterkommst und schon sollte sone abfrage die ja höchstwahrscheinlich in einem Raster liegt oder zumindest in einer begrenzten anzahl an benachbarten Rastern flutschen wie ne normale kleine Karte ...
Achja solch späße wie die Datenbank files in Ram zu mounten kannst du dir definitiv sparen
Heutige Datenbanksysteme sind nicht ganz dämlich...
und blum meinte wohl eher das ein heutiges Datenbanksystem in der Lage sein sollte zu erkennen das es desöfteren geschickter ist Indezes obwohl sie vorhanden sind zu ignorieren und lieber gleich squentiell über die (ganze/teil) tabelle zu gehen und einzeln zu überprüfen da dies perfomanter sein kann sich immer wieder an einem Index entlangzuhangeln.
Die ganze Tabelle wird dir die Datenbank sicher nicht zurückgeben denn das wäre schlichtweg einfach falsch

Original von Sarge
Die ganze Tabelle wird dir die Datenbank sicher nicht zurückgeben denn das wäre schlichtweg einfach falsch

das ist klar, mysql liefert nur die zeilen, die man auch anfordert. aber die die db holt sich ab einem bestimmten wert alle daten und überprüft diese dann gegebenenfalls mit where-klauseln. kann man nachlesen in "High Performance MySQL" von oreilly. hab das buch leider nicht zur hand, sonst könnt ich genaueres schreiben.

ist eigentlich auch die frage wozu man knapp 90k rows in einem result braucht und ob man nicht dies reduzieren sollte.

Wenn die Tabelle nichts anderes machen soll als zu jeder X,Y Position einen Wert zu speichern, würde ich ja komplett auf eine Datenbank verzichten und einfach das hernehmen, was es ist, nämlich eine Bitmap.
Eine Relation zur Speicherung einer Bitmap herzunehmen ist nämlich ziemlicher Overkill.

Man könnte also für jede Spalte aus der Tabelle (vorausgesetzt man benutzt nur TinyInt) eine gif-Datei anlegen. Eine 3200² große Grafik mit 6 Farben ist nur 100 KB groß. Das Auslesen sollte also extrem fix gehen.

Original von Klaus
Man könnte also für jede Spalte aus der Tabelle (vorausgesetzt man benutzt nur TinyInt) eine gif-Datei anlegen. Eine 3200² große Grafik mit 6 Farben ist nur 100 KB groß. Das Auslesen sollte also extrem fix gehen.

Mit "Bitmap" ist hier nicht "Bild" gemeint.
Siehe erster Punkt unter de.wikipedia.org/wiki/Bitmap.

Mh wäre ein Bitmap nicht immer ein Pixel?
Bei mir ist jeder X:Y-Wert eine Grafik die 80*80px groß ist.

unter bitmap kann man vieles verstehen.
du kannst zum beispiel eine graik anlegen, die 400x400 pixel gross ist. und dann zum beispiel den farbwert an einer bestimmten position ermitteln. zum beispiel #ffffff für wiese, #000000 für wasser usw.
oder vielleicht noch einfacher, eine textdatei mit 400 zeichen pro zeile und 400 zeilen.
0 steht dann für wiese, 1 für wasser, 2 für berg usw

Ich glaub nich das es schneller ist eine Textdatei zu bearbeiten die 3200 Zeilen und 3200 Spalten hat.

Auf eine Grafik kann man aber einfacher zugreifen und direkt einen Farbwert holen.

> Ich glaub nich das es schneller ist eine Textdatei zu bearbeiten die 3200 Zeilen und 3200 Spalten hat.
Ich glaube schon!
Mit exakter Positionierung mit Hilfe der Dateimethoden kannst du sehr schnell bestimme Positionen erreichen.

Original von kudi
Ich glaub nich das es schneller ist eine Textdatei zu bearbeiten die 3200 Zeilen und 3200 Spalten hat.

wieso 3200? im obigen beispiel warens 398 zeilen à 398 spalten

Es geht um die im Thema gestellte Frage, also sehr große Karten.

Hi kudi
Könnten wir bitte nochmal etwas genauer auf das eigentliche Problem eingehen?
Ich denke die Menge der Daten in der Datenbank ist noch nicht im kritischen Bereich..
..aber die 89401 Resultate bei jedem Aufruf!
Ich würde wenn deine Anwendung das zulässt, nur die Felder Speichern, die sich von dem Normalzustand unterscheiden.
Also du speicherst zum Beispiel bei in einem Wald nicht Leerräume zwischen den Bäumen ab sondern nur die Felder auf denen auch tatsächlich ein Baum steht.
reg4rds
chojin

Ich kann mich nur wiederholen...rastert es einfach mal und ihr braucht überhaupt nicht mit solch großen Datenmengen rumzuhantieren...
Also du hast nun nen 1000x1000 Koordinaten Feld. anstatt die 10 Mio felder in eine Tabelle zu jagen legst du ein Raster drüber meinetwegen 10x10 ... ... nun hast du nurnoch Tabellen die 100x100 = 10k Einträge besitzen. für die meißten fälle wird es immer reichen ein Rasterstück zu betrachten.. in seltenen Fällen brauchst du das Nachbarrasterstück und in ganz seltenen Fällen wirst du 4 Rasterstücke = 4x 10k Einträge betrachten müssen.
Das sind nun reine Beispielswerte..
Eine Bitmap (nein kein Bild -.-) kann sehr sinnvoll sein, allerdings kommt das drauf an wieviele Daten ein eintrag hat und wie die Verteilung der Einträge sind. Außerdem müsstest du das selbst realisieren und ansprechen.

Als erstes würde ich mich mal Chpojin anschließen und fragen warum es notwendig sein soll knapp 90000 Datensätze einer Karte gleichzeitig zu selektieren.
Zum Thema speichern einer Karte, ich würde hier für die statischen Daten auch eine "Bild" Datei verwenden. Zu empfehlen ist hier das gd2 Format, das optimiert ist um partiell darauf zuzugreifen, Stichwort für PHP User "imagecreatefromgd2part".
Zu Sarges Lösung, die Idee ansich ist gut aber das aufteilen auf mehrere Tabellen halte ich für problematisch. Eine zusätzliche Spalte mit einem Indizierten Hash könnte hier auch schon einiges bringen wenn keine partitioning Option zur Verfügung steht. MySql hat dieses Feature glaub ich seit 5.1.

Die Bitmap könnte z.B. in einem Shared Memory Segment (SHM) liegen und somit ist der Zugriff sehr schnell. Die GD Lib kann man wohl verwenden, muß man aber nicht. Um ein 400x400 großes Stück aus der 3200x3200 Bitmap zu lesen, kann man 400x den Lesepointer setzen und 400x lesen - im SHM geht das wirklich Ratzfatz wenn man das ordentlich implementiert.
Nur beim Schreiben muß man dann aufpassen, daß man den Speicherbereich ordentlich sperrt. Dazu sollte man den Speicherbereich in mehrere Unterbereiche aufteilen und jedem dieser Unterbereiche eine Semaphore zuweisen, über die dieser Teil gelockt werden kann.
Bei Bedarf könnte ich eine entsprechende Library (PHP oder C) erstellen

Ich bin auch beim rumspielen mit sehr großen maps.
Meine Lösungsansatz sieht vor verschiedene Feldgrößen zu verwenden.
Meistens lohnt es sich nicht einen ganzen Ozean mit 1Mio Einzelfelder, die alle identisch sind, zu codieren.
Ich habe 2 Tabellen verwendet, eine für dern großen Hintergrund und eine für die Einzelfelder die wirklich gebraucht werden. In dieser Hintergrundmap wird die Größe des Feldes (in meinem Fall 256) mit angegeben.
Ich habe der Einfachheit halber nur eine Größe verwendet und auch diese Felder als Quadratisch angenommen.
Benötige ich nun ein Feld wird erst nach einem Einzelfeld gefragt.
Falls nicht vorhanden wird ein Datensatz aus der Hintergrundmap generiert.
Beliebige Variationen mit Feldgrößen wären auch möglich, verkomplizieren aber etwas die Abfragen.
Hubble

Ich habe zwar "nur" nen Weltraumspiel, aber hier mal mein Lösungsansatz:
STATISCHE Daten (hintergrund etc. pp.) werden in vorgerenderte Bilder ausgelagert, die dann (vllt. per CSS) teilweise eingeblendet werden.
DYNAMISCHE Daten werden aus der Datenbank gelesen und als objekte (imgs, div-layer, etc.) per CSS über die ganze Map gelegt.
Für algorithmen wie automatische Wegberechnung/umfahren von Hinternissen müsste man einmal die statischen sachen als "polygon-Eckpunkte" in die Datenbank schreiben und die einheiten können dann z.B. nur innerhalb oder außerhalb des definierten Polygones fahren und man kann so effektiv den schnellsten weg bestimmen (vorrausgesetzt innerhalb des Polygoned ist die geschwindigkeit gleich).
Wenn man nun aber wieder auf Felder zurückfallen möchte, dann kann cih nur das empfehlen, was meine Vorredner bereits gesagt haben.

Drezil genau so habe ich es vor.