[SQL] Kategorie - optymalnie? Opcje

[sniver]

Pierwowzorem w kategoriach N zagłębienia dla mnie są duże serwisy takie jak allegro, amazon, beltal, alibaba, ebay itp.

Chciałem stworzyć coś co będzie działać w/g zasad jakie panują na allegro. Udało mi się zmontować następujące rzeczy:

Struktura tabeli w bazie danych:

[SQL] pobierz, plaintext 
CREATE TABLE IF NOT EXISTS `categories` (
  `CAT_Id` int(11) NOT NULL AUTO_INCREMENT,
  `PARENT_Id` int(11) NOT NULL DEFAULT '0',
  `CAT_Name` varchar(155) NOT NULL,
  `CAT_Url` varchar(75) NOT NULL,
  `CAT_Description` varchar(255) NOT NULL,
  `CAT_Sort` int(11) NOT NULL DEFAULT '0',
  `CAT_Counter` int(11) NOT NULL,
  `CAT_Active` int(11) NOT NULL DEFAULT '1',
  PRIMARY KEY (`CAT_Id`),
  KEY `INDEX_GLOWNY` (`CAT_Id`,`PARENT_Id`,`CAT_Counter`,`CAT_Active`) USING BTREE,
  KEY `SORT` (`PARENT_Id`,`CAT_Sort`)
) ENGINE=InnoDB  DEFAULT CHARSET=utf8 ROW_FORMAT=DYNAMIC AUTO_INCREMENT=106 ;
[SQL] pobierz, plaintext 

Oraz zapytanie które obsługuje:

[SQL] pobierz, plaintext 
SELECT
	`CAT_Id` AS `id`,
	`PARENT_Id` AS `parent`,
	`CAT_Name` AS `name`,
	`CAT_Url` AS `url`,
	`CAT_Counter` AS `licznik`	
 
FROM
	`categories` AS `c`
 
WHERE
	(
		(`c`.`CAT_Active` = 1)
		AND (`c`.`CAT_Counter` > 0)
	)
	AND (
		(`c`.`CAT_Id` = {#ID})
		OR (`c`.`PARENT_Id` = {#ID})
		OR (`c`.`PARENT_Id` = (
				SELECT
					`c2`.`CAT_Id`
				FROM
					`categories` AS `c2`
				WHERE
					(`c2`.`CAT_Id` = (
							SELECT 
								`c3`.`PARENT_Id`
							FROM
								`categories` AS `c3`
							WHERE
								(`c3`.`CAT_Id` = {#ID})
							LIMIT 1
						)
					)
				LIMIT 1		
			)
		)
 
		OR (`c`.`PARENT_Id` = (
				SELECT 
					`c3`.`PARENT_Id`
				FROM
					`categories` AS `c3`
				WHERE
					(`c3`.`CAT_Id` = {#ID})
				LIMIT 1
			)
		)
	)
 
ORDER BY 
	`c`.`PARENT_Id` ASC, 
	`c`.`CAT_Sort` ASC
[SQL] pobierz, plaintext 

W miejscu gdzie występuje ciąg {#ID} należy wprowadzić wybraną kategorie...

Licznik jest wyliczany cyklicznie w cronie raz na kilka minut...

Póki co chcę się dowiedzieć co sądzicie o takim czymś - dobrze czy źle?

[nospor]

zastosowana przez ciebie metoda jest najgorsza ze wszystkich mozliwych. Nie wiem jakim cudem sie wzorowales na alegro (IMG:style_emoticons/default/winksmiley.jpg)

poczytaj o strukturach drzewiastych w bazie danych, np. o drzewkach IP

[sniver]

wzorować czyt. efekt końcowy (IMG:style_emoticons/default/biggrin.gif)
no bo jak sie tu inaczej wzorować - skoro ich kod nie jest dostępny (IMG:style_emoticons/default/smile.gif)

Ten post edytował sniver 23.04.2010, 10:50:23

[Wykrywacz]

Myślę że ktokolwiek kto będzie czekał na wynik tego zapytania zaśnie... Nie wiem na dobrą sprawę po co ci te zagnieżdżenia, skoro odbierasz od nich tylko 1 element. i to co ciekawe cały czas z tej samej tablicy.
Weź rozrysuj sobie to na kartce

[phpion]

zastosowana przez ciebie metoda jest najgorsza ze wszystkich mozliwych. Nie wiem jakim cudem sie wzorowales na alegro (IMG:style_emoticons/default/winksmiley.jpg)

Czy przypadkiem Allegro nie ma również struktury opartej o parent_id? Pobierając strukturę kategorii mamy identyfikator kategorii nadrzędnej oraz poziom zagłębienia czyli sugeruje to jednak rozwiązanie z parent_id. Zakładam oczywiście, że zwracane dane są w miarę wiernym odwzorowaniem bazy danych.

[nospor]

@phpion moze i ma parentId. Ale na pewno nie ma tylko parentId (IMG:style_emoticons/default/smile.gif)
Ja tez uzywam parentId ale tylko pomocniczo, by przyspieszyc pewne rzeczy. Tutaj zas, w tym temacie, mamy tylko i wyłącznie parentId. Przeciez na czyms takim nie da sie napisac serwisu pokroju alegro - baza zostanie zarżnieta zywcem (IMG:style_emoticons/default/smile.gif)

[phpion]

Może to dobry moment na debatę (IMG:style_emoticons/default/smile.gif) sam jestem jednak zwolennikiem rozwiązania z parent_id. Podaj może przykład, w którym to rozwiązanie jest gorsze od Twojego/innego. Żeby było jasne: nie chcę na upartego bronić "mojej" teorii, chciałbym dojść do jak najlepszego rozwiązania.

[nospor]

ok, pierwszy lepszy przyklad z brzegu:
Masz produkt ktory nalezy do kategori o id 5.
Kategoria 5 ma rodzica 4, ten ma rodzica 3,ten ma rodzica 2, ten ma rodzica 1
Podaj mi teraz kod, którym pobierze wszystkich przodkow kategori 5, czyli 1/2/3/4/5

[sniver]

ale w tym przypadku ten kod ma tak nie działać (IMG:style_emoticons/default/smile.gif)

gdyby miał tak działać odwołał bym sie prostymi 2 funkcjami które od "najmłodszego" dziecka idą w stronę najstarszego rodzica.. - tak by zbudować drzewo, to ma być lista (IMG:style_emoticons/default/winksmiley.jpg)

[phpion]

(IMG:style_emoticons/default/dry.gif) może coś bardziej życiowego? Nie spotkałem się jeszcze z koniecznością pobierania produktów należących do kategorii nadrzędnych, a jedynie podrzędnych hehe (IMG:style_emoticons/default/winksmiley.jpg) Tak więc dla mnie osobiście ten problem nie istnieje.

[sniver]

Sam box na stronie z listą "aktualnych" kategorii mam zrobiony. Mogę na priv podesłać zainteresowanym adres i porównanie względem np. allegro (na priv ze względu na erotyczny typ serwisu który robię...)

[nospor]

@phpion "niezyciowy" problem?

http://allegro.pl/item996992105_aurora_g01...ka_4_wzory.html

Biżuteria i Zegarki › Ozdoby do włosów › Gumki

myslisz ze ten Breadcrumb to czym jest? To jest wlasnie po kolei lista kategorii nadrzednych (IMG:style_emoticons/default/tongue.gif)

gdyby miał tak działać odwołał bym sie prostymi 2 funkcjami które od "najmłodszego" dziecka idą w stronę najstarszego rodzica.. - tak by zbudować drzewo

Super...zrob to i policz ile w rekurencji wykonales zapytan - wlasnie dlatego ten algorytm jest nieoptymalny.

Podalem tu tylko jeden z przykladow. Jest tego masa. Weźcie poczytajcie o strukturach drzewiastych w bazie danych, o np. drzewkach IP. Jak to zrobicie to wroccie i wtedy porozmawiamy, bo teraz nie widze wiekszego sensu (IMG:style_emoticons/default/smile.gif)

[sniver]

znalazłem ciekawą opowieść na ten temat (IMG:style_emoticons/default/winksmiley.jpg)

http://blog.mwojcik.pl/2008/02/17/drzewa-k...-php-metoda-ip/

mówiąc szczerze jest to ciekawe, ale w praktyce powiem czy lepiej sie to sprawuje od parent_id

[nospor]

ale w praktyce powiem czy lepiej sie to sprawuje od parent_id

No nie wiem.... spytaj sie allegro. Napewno korzystają tylko z parentID (IMG:style_emoticons/default/winksmiley.jpg)

Tak, drzewka IP powstaly wlasnie po to, by w praktyce sprawowaly się znacznie lepiej od zwyklego parentID.

Jak zaczynalem to sam przy pierwszym projekcie uzywalem tylko parentID. Nikt mi nie powidzial o niczym innym. Juz przy tym pierwszym projekcie okazalo sie, ze ma same wady taka struktura. Poprawialem wiec ją, modyfikowalem. Nie szukalem w necie zadnych rozwiązan. Po kilku latach okazalo sie, ze to do czego doprowadzily moje wlasne modyfikacje to ni mniej nie wiecej a wlasnie drzewko IP.
Tak wiem, skromny jestem (IMG:style_emoticons/default/smile.gif)

[sniver]

hehehe...już przerobilem w głowie o co w tym chodzi (IMG:style_emoticons/default/biggrin.gif)
do drzewa nie ma problemów - to się zgadzam :-)

wysyłam ci na priv moich kawałek wypocin (IMG:style_emoticons/default/biggrin.gif)

[phpion]

@phpion "niezyciowy" problem?

http://allegro.pl/item996992105_aurora_g01...ka_4_wzory.html
myslisz ze ten Breadcrumb to czym jest? To jest wlasnie po kolei lista kategorii nadrzednych (IMG:style_emoticons/default/tongue.gif)

Aj, źle Cię zrozumiałem: myślałem, że chcesz wyświetlić produkty ze wszystkich kategorii nadrzędnych dla aktualnie przeglądanej stąd napisałem, że przykład lekko naciągany (zazwyczaj wyświetla się produkty ze wszystkich podkategorii, a nie "nadkategorii"). Breadcrumb można pobrać jedynie rekurencyjnie, zgadza się. Jednak można ścieżkę zapisać do cache i później odwoływać się do gotowych danych (IMG:style_emoticons/default/smile.gif)

[nospor]

Jednak można ścieżkę zapisać do cache i później odwoływać się do gotowych danych

Wszystko mozna zapisac do cache i olac wogole baze, nie zakladac indexow, nie dbac o optymalne zapytania - przeciez zawsze mozna zapisac do cache.... (IMG:style_emoticons/default/winksmiley.jpg)
cache jednak sie czysci, niektorych zapytan nie zapiszesz do cache i wiele innych.

Jak tylko z parentID rozwiązesz liczbę produktów w kategoriach?
zakladam ze uzyjesz dodatkowe pole na liczbę produktów. No ale to pole też trzeba aktualizowac - znowu rekurencja. A jak nie daj boze trzeba bedzie zaktualizowac z jakiegos powodu te pole we wszystkich kategoriach.... (IMG:style_emoticons/default/winksmiley.jpg)

zazwyczaj wyświetla się produkty ze wszystkich podkategorii, a nie "nadkategorii"

Podsunales kolejny przyklad:
wyswietl mi proszę wszystkie produkty dla danej kategorii. Zauwaz, ze podam ci kategorię poczatkową, a produkty są przypisywane tylko do kategorii glęboko podrzędnych. Znowu cache? Ok, niech bedzie cache (juz mocno naciągane ale niech bedzie). Dodaj do tego wyszukiwanie. Znowu cache?

[phpion]

W obu przypadkach można zastosować to samo rozwiązanie: przypisując produkt do kategorii równocześnie przypisujemy go do wszystkich kategorii nadrzędnych czyli mając strukturę kategorii:

Kod

1
-- 1.1
-- 1.2
----1.2.1

i chcąc przypisać produkt do kategorii 1.2.1 zaznaczamy 1.2.1, 1.2 oraz 1.1. Można to rozwiązać ładnym JSem, który automatycznie zaznaczy całą ścieżkę do kategorii. Co nie zmienia jednak faktu, że pewnie przyjrzę się bliżej drzewkom IP. Może, bazując na doświadczeniu, podałbyś ich minusy?

[nospor]

chcąc przypisać produkt do kategorii 1.2.1 zaznaczamy 1.2.1, 1.2 oraz 1.1. Można to rozwiązać ładnym JSem, który automatycznie zaznaczy całą ścieżkę do kategorii.

a co ma js do tego?
czyli ze co, w bazie tworzysz tabele: kategoria-produkt i robisz tyle wpisow dla danego produktu ile ma on kategorii nadrzędnych?
Mozna i tak, nie wnikam czy to dobre czy nie. Ale juz sam widzisz, ze nie korzystasz w tym momecne z samego parentID. Juz kombinujesz. I bardzo dobrze, to juz jest rozwiniecie metody "samo parentID".
A ja wlasnie to mowie przez caly czas: samo "parentID" jest cholernie nieoptymalne (IMG:style_emoticons/default/smile.gif)

Może, bazując na doświadczeniu, podałbyś ich minusy?

drzewek IP?

[phpion]

(IMG:style_emoticons/default/rolleyes.gif) pewnie masz rację, aż sobie poczytam o tych drzewkach (IMG:style_emoticons/default/smile.gif)

PS: Tak, minusy drzewek IP.

// Edit:
No i poczytałem tutaj:
http://blog.mwojcik.pl/2008/02/17/drzewa-k...-php-metoda-ip/
Wygląda to całkiem prosto i ciekawie, nie to co nested sets (IMG:style_emoticons/default/dry.gif) . Co prawda "troszkę" naruszona jest 3. postać normalna, ale coś za coś.

Ten post edytował phpion 23.04.2010, 13:17:10

[nospor]

minus drzewek IP... w porównaniu z parentID nie widze (IMG:style_emoticons/default/winksmiley.jpg)

A juz powaznie:
ja drzewka IP uzywam lekko zmodyfikowane. jak juz pisalem sam na to wpadlem a dopiero potem sie okazalo ze do drzewko IP jest. Ja dodaje do tego jeszcze parentID oraz firstID.
firstID to id kategorii pierwszej. Czyli jak mam kategorie na poziomi 10 to firstID wskazuje na kategorię z poziomu 1. I tak jest niezaleznie od poziomu kategorii.

Zabawy jest trochę przy zarządzaniu: np. przy przenoszeniu kategorii trzeba pamietac, by zmodyfikowac rownież wpisy we wszystkich jej kategoriach podrzednych. Przy samym parentID juz bys tego nie mial. No ale trudno to uznac za wadę - trzeba to zrobic i tyle. przy kolejnych projektach jest tylko kopiuj-wklej i juz (IMG:style_emoticons/default/smile.gif)

Żeby powaznie pomowic o wadach, musialbym uzywac innych struktur drzewiastych i miec jakies porownanie. A ja nie uzywam. Kiedys doszedlem do tego etapu struktury i jak do tej pory mi się sprawdzał. Jak kiedys na trafie na sytuacje ze nie bedzie sie sprawdzal - zmienie strukture (IMG:style_emoticons/default/smile.gif)

[6nom]

http://www.depesz.com/various/various-sqltrees.php

[Mchl]

A jeśli ma się możliwość, to najlepiej z drzewkami itp radzi sobie to ustrojstwo (IMG:style_emoticons/default/winksmiley.jpg)

http://openquery.com/graph-engine-mysql-mariadb-and-drizzle

[cojack]

http://www.depesz.com/index.php/2008/04/11...n-trees-in-sql/

[sniver]

ma ktoś gotowy kod który przerobi parent id na te ip (IMG:style_emoticons/default/biggrin.gif)

jak byłby gotowy to nie musiał bym pisać (IMG:style_emoticons/default/biggrin.gif)

[aio]

ma ktoś gotowy kod który przerobi parent id na te ip (IMG:style_emoticons/default/biggrin.gif)

jak byłby gotowy to nie musiał bym pisać (IMG:style_emoticons/default/biggrin.gif)

query napisane w zasadzie do odczytu hierarchii 'na żywca' a nie jako konwerter ale może się przyda
INPUT
- nodes - tabela wejściowa (id, parent)
- kolumna sort - umozliwia własne sortowanie, aby tworzyć path z id najprościej potrzeba zamienić '(@S:=@S+1) sort' na 'id sort' (można wyrzucić całe sortowanie ale więcej tłumaczenia)
- w parametrach (setup) @XS oznacza separator ścieżki

OUTPUT
- kolumn hierarchy - path do danego id
- kolumna level - wiadomo

Kod

--
-- Solution 2 optimizing 1 - S2.1 - WINNER Solution
--
-- One Query Hierarchy Harvester (OQHH), by mba/aio(c)2010, SolutionID:OQHH/S2.1
--
--      Features:
--          - needs parent-child relation only
--          - no level nor other preordered data structure (i.e. left+right) needed
--          - sorting of sibling nodes (see notes below for info)
--          - speed optimization on preordered data
--          - produces level of depth of a node
--;
SELECT  id, parent, @L level, CONCAT(REPEAT('    ', @L - 1),CAST(id AS CHAR)) name, @H hierarchy
FROM    (
        SELECT  @H:='', @F:=0, @L:=0, -- internals
                @XS:='.', @XP:='0', -- xpath options
                @R:= LENGTH((IFNULL(@S,(SELECT MAX(id) FROM nodes)))) -- auto xpath size
        ) setup, nodes
WHERE   ((@L:=0) | (@H:='') | @P:=id) AND
        (
        SELECT  1
        FROM    nodes
        WHERE   (
                SELECT  1
                FROM    (
                        SELECT  id, parent, sort
                        FROM    (
                                    SELECT  id, parent, (@S:=@S+1) sort -- replace with 'id sort' to build xpath by id
                                    FROM    (SELECT @S:=0) init, nodes
                                    ORDER BY id DESC -- custom order: see notes on sorting techniques
                                ) sorting
                        ORDER BY id DESC
                        ) core -- optimization sequence 1: see notes
                WHERE   @P=id AND
                        ((@H:=CONCAT(REPEAT(@XP,@R-LENGTH(sort)),sort,IF(@H,@XS,''),@H)) | (@P:=parent) | (@L:=@L+1)) AND
                        NOT @P
                LIMIT 1 -- optimization trap 1: root found
                ) AND
                NOT @P
        LIMIT 1 -- optimization trap 2: root found
        )
ORDER BY hierarchy
--
-- Notes
-- * not used optimization trap 0 (see S1.2) - to allow sorting at lower level subquery
-- * optimization sequence 1 - assumes the child id > parent id, otherwise can slow down, needs core subquery to be ordered DESC
-- * CONCAT+REPEAT+LENGTH executes faster than LPAD
-- TODO
--
--;

O dziwo ten (po)twór przy dużej ilości rekordów jest 2x szybszy od obsługi drzewek Left Right - no i sortuje! (IMG:style_emoticons/default/winksmiley.jpg)
Pozdro

[cojack]

Ja bym poprosił o źródło pochodzenia tego przykładu powyżej.

[aio]

Ja bym poprosił o źródło pochodzenia tego przykładu powyżej.

źródło samo przyszło napisać przykład powyżej! Jak z czegoś korzystałem zawsze podawałem źródło!
pozdrawiam

[cojack]

Hmmm to ja jeszcze poproszę funkcje do przesuwania kategorii wraz z dziećmi, dodawania nowych kategorii, usuwania kategorii, aktualizacji kategorii i sprawdzimy wydajność Twojego działa.

Najchętniej to zobaczyłbym to wszystko w postaci pl/sql + widoki bym się za dużo bawić nie musiał przy portowaniu tego do postgresql.

[aio]

Hmmm to ja jeszcze poproszę funkcje do przesuwania kategorii wraz z dziećmi, dodawania nowych kategorii, usuwania kategorii, aktualizacji kategorii i sprawdzimy wydajność Twojego działa.

Najchętniej to zobaczyłbym to wszystko w postaci pl/sql + widoki bym się za dużo bawić nie musiał przy portowaniu tego do postgresql.

Ty się chociaż zastanowiłeś nad swoim postem? Nie proś tylko sam napisz i wklej.

[sniver]

Napisałem bardzo byle jakąś procedure (można odpalić z cron'a) aby przerobić drzewo typu Parent Id na Drzewo IP, oto kod - może sie komuś przyda:

plik np. cron/Category-ParentId-to-TreeIp.php

[PHP] pobierz, plaintext 
<?php
 
   include_once 'db.class.php';
   cronDB::categoriesIP( $link );
 
?>
[PHP] pobierz, plaintext 

plik db.class.php

[PHP] pobierz, plaintext 
	abstract 
		class cronDBExp {
 
 
			protected function categoriesIP( $category, $id ) {
				try {
 
					if( $category[$id]['isset'] ) {
						$parent = self::categoriesIP( $category, $category[$id]['parent'] );
					}
 
					$parent.= $id;
					$parent.= '.';
 
					return $parent;					
				}
				catch( Exception $e ) {
					err($e);
				}
			}
 
 
		}
 
 
	/**
	 *	Klasa łączy modul z baza danych
	 */
	class cronDB 
		extends cronDBExp {
 
 
               /**
		 * Zmienna przechowuje informacje o drzewie IP
		 *
		 * @var array
		 */
		static public $categoryIp = array();
 
 
		/**
		 * Budowanie drzewa IP
		 *
		 * @param object $link
		 * @param int $catId
		 */
		public function categoriesIP( $link ) {
			try {
 
				$query = '
  			              SELECT
				            `c`.`CAT_Id` AS `id`,
				            `c`.`PARENT_Id` AS `parent`,
				            (
					            SELECT COUNT(1) FROM `categories` AS `c2` WHERE (`c2`.`CAT_Id` = `c`.`PARENT_Id`)
				            ) AS `isset`
 
			            FROM 
				            `categories` AS `c`
                                ';
 
				if( !$result = db::__connect()->query( $query  ) ) {
					throw new Exception('Blad bazy danych');
				}
 
 
				$category = array();
				while( $row = $result->fetch_assoc() ) {
					$category[ $row['id'] ] = array(
						'parent' => $row['parent'],
						'isset' => (bool)$row['isset']
					);
 
					self::$categoryIp[$row['id']] = $row['id'];
				}
 
 
				foreach( self::$categoryIp as $key => $value ) {
					if( $category[$key]['isset'] ) {
						self::$categoryIp[$key] = parent::categoriesIP( $category, $category[$key]['parent'] );
						self::$categoryIp[$key].= $key;
					}
				}
 
				$query = '
					UPDATE
						`categories` AS `c`
					SET
						`c`.`CAT_Ip` = '%s'
					WHERE
						`c`.`CAT_Id` = %d
                                ';
 
				foreach( self::$categoryIp as $key => $value ) {				
					if( !db::__connect()->query( sprintf($query, self::$categoryIp[$key], $key)  ) ) {
						throw new Exception('Blad bazy danych');
					}
				}
 
			}
			catch( Exception $e ) {
				err($e);
			}
		}
 
 
	}
?>
[PHP] pobierz, plaintext 

elementy:
a) db::__connect() - jest znany zapewne większości osób z forum - to gotowiec z php.net - dotyczący połączenia z mysql'em z wzorcem singleton,
(IMG:style_emoticons/default/cool.gif) funkcja err - wyświetla ewentualne błędy na ekranie (może zapisywać loga do pliku/bazy

Zapytanie Update zostawiem bez komentarza - nie zależy mi w tym przypadku na szybkości działania :-)

Jak mówiłem może sie komuś przyda, jest to tylko część kodu i może nie działać...(IMG:style_emoticons/default/winksmiley.jpg)