Sortierte Objekte in einem RDBMS

Alles, was nicht direkt mit Python-Problemen zu tun hat. Dies ist auch der perfekte Platz für Jobangebote.
Benutzeravatar
Leonidas
Administrator
Beiträge: 16023
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Sortierte Objekte in einem RDBMS

Beitragvon Leonidas » Mittwoch 16. Mai 2007, 19:47

Hallo,

diesmal habe ich ein generelles Problem, was die Implementation eines gewissen Features angeht. Ich habe ein RDBMS (in meinem Fall PostgreSQL) und das Django-ORM zur Hand. Nun würde ich gerne Objekte einer Sortierung unterwerfen können, also sie in der Reihenfolge der Ausgabe verstellen können.
Nun fallen mir zwei Möglichkeiten ein:
  • Linked List. Jedes Element hält eine Referenz auf das nächste Element vor. Nachteil: Kette kann brechen, wenn die Implementation nicht gut ist, neue Elemente sind nicht automatisch Teil der Kette, Kette kann sich verschleifen. Vorteil: Objekte einfügen ist ziemlich einfach.
  • Index-Feld. Jedes Objekt hält einen Index, nach dem die Objekte sortiert werden. Wenn man hoch oder runtersortiert muss man aber die Indizies der Objekte ändern.


Habt ihr sonst noch praktikable Ideen? Für den Ersten Punkt habe ich mir zwar eine Referenzimplementation geschrieben, aber 100% zufrieden bin ich nicht. Möglich, dass ich noch den zweiten Fall implementiere und dann noch einmal sehe. Wisst ihr wie die gängigen CMS-Systeme das machen? Dort kann man ja auch Artikel hochsortieren und runtersortieren.
My god, it's full of CARs! | Leonidasvoice vs Modvoice
lunar

Beitragvon lunar » Mittwoch 16. Mai 2007, 20:11

Ich gebe ja zu, weder von Django noch von Postgre etwas zu verstehen... aber warum sagst du nicht einfach dem DBMS, dass es gefälligst sortieren soll? MySQL kann das per SORT BY, an das SELECT angehängt.

PS: Hau mich, wenn ich was Dummes gesagt habe...
Benutzeravatar
mitsuhiko
User
Beiträge: 1790
Registriert: Donnerstag 28. Oktober 2004, 16:33
Wohnort: Graz, Steiermark - Österreich
Kontaktdaten:

Beitragvon mitsuhiko » Mittwoch 16. Mai 2007, 20:12

Ich kenn das Problem. Ich löse es durch Vermeiden :D
Bei Pocoo haben wirs auf der Indexseite, da haben wir jetzt eine Eintrag für "order by"
TUFKAB – the user formerly known as blackbird
thelittlebug
User
Beiträge: 188
Registriert: Donnerstag 20. Juli 2006, 20:46
Wohnort: Wien
Kontaktdaten:

Beitragvon thelittlebug » Donnerstag 17. Mai 2007, 01:11

Das sortieren von Seiten in einem CMS wird meist bereits durch das "nested set" erledigt da hier ja bereits eine "Ordnung" beim Tree mit dabei ist.

MySQL bietet einen Artikel zu Nested Sets. Allerdings würde ich bei einer einfachen Liste einfach eine Positionsangabe speichern. Natürlich muss man bei Einfüge oder Löschoperationen so ziemlich alle Felder anfassen, aber das tut der DB nicht sonderlich weh.

lgherby
Benutzeravatar
gerold
Python-Forum Veteran
Beiträge: 5554
Registriert: Samstag 28. Februar 2004, 22:04
Wohnort: Telfs (Tirol)
Kontaktdaten:

Re: Sortierte Objekte in einem RDBMS

Beitragvon gerold » Donnerstag 17. Mai 2007, 09:06

Leonidas hat geschrieben:Ich habe ein RDBMS (in meinem Fall PostgreSQL) und das Django-ORM zur Hand. Nun würde ich gerne Objekte einer Sortierung unterwerfen können, also sie in der Reihenfolge der Ausgabe verstellen können.

Hallo Leonidas!

Wenn du nicht "Django-ORM" geschrieben hättest (davon habe ich nämlich keine Ahnung), dann hätte ich dir zur einfachsten Lösung mit dem zusätzlichen Feld ("manual_order") in der Tabelle geraten.

Wenn du mit sehr vielen Datensätzen zu tun gehabt hättest, dann hätte ich dir zu einer zusätzlichen Tabelle, statt dem zusätzlichen Feld, geraten. (Tabelle: "xxx_man_ord"; Felder: "xxx_link" und "manual_order") Bei manuellen Änderungen der Reihenfolge, würde man damit die Datenbank evt. nicht so stark belasten.

Ob zusätzliches Feld oder zusätzliche Tabelle: Natürlich müssen die Indizes dementsprechent eingerichtet werden...

Da ich mich aber mit Django-ORM nicht auskenne, könnten diese einfachen Möglichkeiten evt. gar nicht damit funktionieren.

lg
Gerold
:-)
http://halvar.at | Kleiner Bascom AVR Kurs
Wissen hat eine wunderbare Eigenschaft: Es verdoppelt sich, wenn man es teilt.
Benutzeravatar
Leonidas
Administrator
Beiträge: 16023
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Re: Sortierte Objekte in einem RDBMS

Beitragvon Leonidas » Donnerstag 17. Mai 2007, 09:53

Danke schonmal für die Antworten :)

lunar hat geschrieben:Ich gebe ja zu, weder von Django noch von Postgre etwas zu verstehen... aber warum sagst du nicht einfach dem DBMS, dass es gefälligst sortieren soll? MySQL kann das per SORT BY, an das SELECT angehängt.

Jaja, das ist klar. Nur brauche ich dazu en Sortierkriterium, das manuell festlegbar sein muss. Also beispielsweise sowas, wie ich in meiner zweiten Alternative angesprochen habe. Nur weiß ich eben nicht, ob das das Optimum ist.

thelittlebug hat geschrieben:Das sortieren von Seiten in einem CMS wird meist bereits durch das "nested set" erledigt da hier ja bereits eine "Ordnung" beim Tree mit dabei ist.

Danke, das klingt allerdings Interessant. Habe auch eine Postgres-Implementation gefunden. Allerdings scheint es wirklich etwas Overkill zu sein. Muss ich mir genauer unter die Lupe nehmen, danke.

gerold hat geschrieben:Wenn du nicht "Django-ORM" geschrieben hättest (davon habe ich nämlich keine Ahnung), dann hätte ich dir zur einfachsten Lösung mit dem zusätzlichen Feld ("manual_order") in der Tabelle geraten.

Sowas geht mit Django ohne Probleme. Ich denke, dass ich das bald implementiere um zu sehen, wie sich das so verhält.

gerold hat geschrieben:Wenn du mit sehr vielen Datensätzen zu tun gehabt hättest, dann hätte ich dir zu einer zusätzlichen Tabelle, statt dem zusätzlichen Feld, geraten. (Tabelle: "xxx_man_ord"; Felder: "xxx_link" und "manual_order") Bei manuellen Änderungen der Reihenfolge, würde man damit die Datenbank evt. nicht so stark belasten.

Das ist eine Idee, aber da stoße ich vermutlich an die Grenzen des Django-ORMs. Außerdem scheint mir die Lösung noch komplexer zu sein und je einfacher die Lösung desto weniger Fehleranfällig.

Aber danke schonmal für die Ratschläge.
My god, it's full of CARs! | Leonidasvoice vs Modvoice
Benutzeravatar
mitsuhiko
User
Beiträge: 1790
Registriert: Donnerstag 28. Oktober 2004, 16:33
Wohnort: Graz, Steiermark - Österreich
Kontaktdaten:

Beitragvon mitsuhiko » Donnerstag 17. Mai 2007, 10:15

Zwar nicht django, aber für SQLAlchemy gibts da was: http://www.sqlalchemy.org/docs/plugins. ... deringlist
TUFKAB – the user formerly known as blackbird
Benutzeravatar
Leonidas
Administrator
Beiträge: 16023
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Beitragvon Leonidas » Donnerstag 17. Mai 2007, 10:20

blackbird hat geschrieben:Zwar nicht django, aber für SQLAlchemy gibts da was

Ja, da ist es wieder: Der SQLAlchemy-Branch fehlt mal wieder.
Aber ich könnte versuchen, da was zusammenzusetzen, was sich so ähnlich verhält. So wie es aussieht, speichert ``orderinglist`` die Elemente mit einem ``position``-Feld. Das wird wohl der "way to go" sein.
My god, it's full of CARs! | Leonidasvoice vs Modvoice
Benutzeravatar
jens
Moderator
Beiträge: 8458
Registriert: Dienstag 10. August 2004, 09:40
Wohnort: duisburg
Kontaktdaten:

Beitragvon jens » Donnerstag 17. Mai 2007, 13:57

Also in PyLucid mache ich das im Prinzip wie die erste Variante: Jede Page hat eine ID und eine parent-ID... Außerdem gibt es noch eine Gewichtungszahl von -10 bis 10 um die Reihenfolge innerhalb eine Ebene beeinflussen zu können...

Allerdings hab ich immer noch das Problem, diese Daten auch richtig auszuwerten und anzuzeigen. Nicht zuletzt, weil es keinen rekursions Funktion im django Template gibt... Siehe: http://www.python-forum.de/topic-9655.html

btw.: Warum ist dieser Thread in "Offtopic" ?

CMS in Python: http://www.pylucid.org
GitHub | Open HUB | Xing | Linked in
Bitcoins to: 1JEgSQepxGjdprNedC9tXQWLpS424AL8cd
thelittlebug
User
Beiträge: 188
Registriert: Donnerstag 20. Juli 2006, 20:46
Wohnort: Wien
Kontaktdaten:

Beitragvon thelittlebug » Donnerstag 17. Mai 2007, 14:46

Ich hab noch alten Code von mir gefunden der zwar in PHP mit CakePHP ist. Stellt die Backendlogik für das ExtJS Tree "dingsbums" dar.

Wenn du das nach python portierst und die parent_id Sachen weglässt hast du deine sortierbare Liste ( sonst halt einen Baum ohne "nested sets" )

Nested Sets habe ich damals nicht verwendet da CakePHP auch ein ORM bietet und Nested Sets sich da schwer einfügen lassen und mir die sowieso für 5 Kategorien "zu viel" waren.

http://nopaste.php-q.net/294938

und hier die tabelle dazu:

Code: Alles auswählen

CREATE TABLE `categories` (
  `id` int(11) NOT NULL auto_increment,
  `name` varchar(50) character set utf8 collate utf8_unicode_ci NOT NULL,
  `image` varchar(50) NOT NULL,
  `sortorder` int(11) NOT NULL,
  `parent_id` int(11) NOT NULL,
  `created` datetime NOT NULL,
  `modified` datetime NOT NULL,
  PRIMARY KEY  (`id`)
) ENGINE=MyISAM  DEFAULT CHARSET=utf8;


natürlich fehlen hier noch optimierte indexfelder ( z.b. auf sortorder und parent_id ) da ich aber nicht mehr rausfinden will wie CakePHP die qry's erstellt (stichwort: index über mehrere felder) steck ich da auch keine mühe mehr rein, abgesehen davon sollte man auf nested sets umsteigen wenns zu langsam wird :)

lgherby

p.s. ich hoffe das man den Code auch ohne CakePHP Kenntnisse verstehen kann.
Benutzeravatar
Leonidas
Administrator
Beiträge: 16023
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Beitragvon Leonidas » Freitag 18. Mai 2007, 19:12

jens hat geschrieben:btw.: Warum ist dieser Thread in "Offtopic" ?

Naja, weils nicht wirklich ein Python-Problem per se ist, sondern eher die Frage, wie man sowas prinzipiell implementiert.
My god, it's full of CARs! | Leonidasvoice vs Modvoice
Benutzeravatar
Leonidas
Administrator
Beiträge: 16023
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Beitragvon Leonidas » Sonntag 20. Mai 2007, 23:32

So, ich habe das Sortieren mittels ``position``-Feld heute mal implementiert, indem ich meinen Linked-List-Code geforkt habe und dann reihenweise Code rausgeworfen habe. Dieser Ansatz ist auf jeden Fall um einiges simpler als der erste und dadurch sicherlich auch robuster. Bin grade dabei die Implemetation vom Programm rauszulösen, damit ich es auf Django snippets posten kann.

Im Moment hänge ich etwas an der Meta-Magie von Django fest, in diesem Thread wurde mir geraten mich mit DevModelCreation und ModelBase zu beschäftigen. Naja, zur Not werde ich es eben so wie es ist veröffentlichen.
My god, it's full of CARs! | Leonidasvoice vs Modvoice
thelittlebug
User
Beiträge: 188
Registriert: Donnerstag 20. Juli 2006, 20:46
Wohnort: Wien
Kontaktdaten:

Beitragvon thelittlebug » Montag 21. Mai 2007, 17:22

Linked List in SQL klingt unglaublich schnell :)
Da muss sich ja die DB von einem Eintrag zum anderen "weiterhangeln", wobei das nur geht wenn man Stored Procedures hat, sonst müsste man viele QRY's abfeuern. Man stelle sich das bei einer großen Liste vor.

Oder hast du das irgendwie anders realisiert?

lgherby
Benutzeravatar
mitsuhiko
User
Beiträge: 1790
Registriert: Donnerstag 28. Oktober 2004, 16:33
Wohnort: Graz, Steiermark - Österreich
Kontaktdaten:

Beitragvon mitsuhiko » Montag 21. Mai 2007, 17:38

Geht auch mit einem Query wenn alle items eine "list_id" haben. Dann selected man nach der und sortiert in python.
TUFKAB – the user formerly known as blackbird
Benutzeravatar
Leonidas
Administrator
Beiträge: 16023
Registriert: Freitag 20. Juni 2003, 16:30
Kontaktdaten:

Beitragvon Leonidas » Montag 21. Mai 2007, 18:52

thelittlebug hat geschrieben:Linked List in SQL klingt unglaublich schnell :)
Da muss sich ja die DB von einem Eintrag zum anderen "weiterhangeln", wobei das nur geht wenn man Stored Procedures hat, sonst müsste man viele QRY's abfeuern. Man stelle sich das bei einer großen Liste vor.

Richtig, es waren schon einige Queries. Das zu Optimieren war nicht nötig, weil ich es nie im "Produktiveinsatz" hatte und die Liste hinreichen klein war.

Ich bin heute mehr oder weniger damit fertig geworden und habe es als Snippet #245 auf djangosnippets hochgeladen. Möge es so vielen Leuten wie möglich nützen.
My god, it's full of CARs! | Leonidasvoice vs Modvoice

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder