Rekurencja w SQL jest zła

Prawdopodobnie nieraz zdarzyło się wam budować drzewiaste struktury danych w bazach danych. Typowa tabela do tego celu wygląda mniej więcej tak:

id | parent_id | name
---+-----------+-------------
 1 |         0 | Lorem
 2 |         0 | Ipsum
 3 |         1 | Dolor
 4 |         1 | Sit
 5 |         2 | Consectetuer
 6 |         4 | Adipiscing
 7 |         4 | Elit

Pozwala na dowolnie głębokie zagnieżdżanie danych, zaś obiekty o parent_id równym 0 są elementami najwyższego poziomu hierarchii.

Problem pojawia się, kiedy dane te trzeba zwizualizować w postaci drzewa. Początkujący programiści często używają do tego celu rekursji (właściwie, to używają jej do wszystkiego), jednak ma ona podstawową wadę. O ile w przypadku powyższej tabeli nie ma zasadniczo różnicy, czy dane będą pobierane rekurencyjnie czy liniowo, o tyle przy tysiącu kategorii, gdzie w najwyższym poziomie znajduje się ich kilkaset, liczba zapytań wywoływanych przez skrypt sięga setek na każde wyświetlenie strony.

Jest to problemem zwłaszcza, kiedy serwer SQL znajduje się na innej maszynie i każde zapytanie wymaga przesyłania danych w obie strony połączenia. Wprowadza to dodatkowe opóźnienia, a z czasem staje się nader widoczne.

Rozwiązaniem jest jednorazowe pociągniecie wszystkich potrzebnych danych za pomocą jednego zapytania, a następnie przebudowanie w strukturę drzewiastą po stronie serwera docelowego.

Jako przykład takiego działania posłużyć może poniższy skrypt PHP:

require_once('arraySort.class.php');

/**
 * Create a tree structure from an SQL query
 */

class sqlTree
{
	var $conn;

	function sqlTree(&$conn)
	{
		$this->conn = & $conn;
	}

	/**
	 * Sort an array
	 * @access private
	 */
	function _multiSort(&$array, $key, $asc = true)
	{
		$sorter = & new arraySort($array, $key, $asc);
		return $sorter->sortit();
	}

	/**
	 * Sort a tree
	 * @access private
	 */
	function _treeSort(&$item)
	{
		reset($item);
		foreach($item as $key => $val)
		{
			if (isset($val['tree']))
				$this->_treeSort($item[$key]['tree']);
		}
		$item = $this->_multiSort($item, 'sort', true);
	}

	/**
	 * Build the tree, elements with no known parent are ignored
	 * @param string SQL query, has to contain fields 'id' and 'parent_id'
	 * @param int parent_id to be considered root level
	 * @return array the tree structure
	 */
	function build($query, $root = 0)
	{
		$result = mysql_query($query, $this->conn);

		$queue = array();
		while($item = mysql_fetch_assoc($result))
		{
			array_push($queue, $item);
		}

		$queue = $this->_multiSort($queue, 'id', false);
		$effect = array();

		while($queue)
		{
			$found = false;
			reset($queue);
			$nextIter = $queue;
			foreach($queue as $key => $item)
			{
				if ($item['parent_id'] != $root)
				{
					reset($nextIter);
					foreach($nextIter as $keyTarg => $target)
					if ($target['id'] == $item['parent_id'])
					{
						if (!isset($nextIter[$keyTarg]['tree']))
							$nextIter[$keyTarg]['tree'] = array();

						array_push($nextIter[$keyTarg]['tree'], $item);
						unset($nextIter[$key]);
						$found = true;
						break;
					}

					if ($found)
						break;

					// not found
					unset($nextIter[$key]);
				}
				else
				{
					array_push($effect, $item);
					unset($nextIter[$key]);
					break;
				}
			}
			$queue = $nextIter;
		}
		$this->_treeSort($effect);
		return $effect;
	}
}

Jest to klasa, która jako parametr konstruktora pobiera identyfikator połączenia do bazy danych MySQL i udostępnia funkcję build(), która jako pierwszy parametr przyjmuje zapytanie wybierające dane, zaś jako drugi opcjonalny identyfikator korzenia drzewa.

Wymagania odnośnie zapytania są następujące: musi ono zawierać w wynikach kolumny o nazwach id, parent_id i sort, przy czym ten ostatni decyduje o kolejności pozycji drzewa. Dodatkowym ograniczeniem (powyższej implementacji) jest założenie, że dla każdego elementu zachodzi parent_id < id.

Przykładowe użycie:

$st = & new sqlTree($connection);
$tree = $st->build(
'
	SELECT id, parent_id, name AS sort
	FROM przykladowa_tabela
');

print_r($tree);

Do działania wymagany jest jeszcze plik arraySort.class.php, czyli skrypt sortowania wielowymiarowych tablic autorstwa Oliwiera Ptaka:

/**
 * Handles multidimentional array sorting by a key (not recursive)
 *
 * @author Oliwier Ptak <aleczapka at gmx dot net>
 */

class arraySort
{
	var $skey = false;
	var $sarray = false;
	var $sasc = true;

	/**
	 * Constructor
	 *
	 * @access public
	 * @param mixed $array array to sort
	 * @param string $key array key to sort by
	 * @param boolean $asc sort order (ascending or descending)
	 */
	function arraySort(&$array, $key, $asc = true)
	{
		$this->sarray = $array;
		$this->skey = $key;
		$this->sasc = $asc;
	}

	/**
	 * Sort method
	 *
	 * @access public
	 * @param boolean $remap if true reindex the array to rewrite indexes
	 */
	function sortit($remap = true)
	{
		$array = &$this->sarray;
		uksort($array, array(&$this, "_as_cmp"));
		if ($remap)
		{
			$tmp = array();
			while (list($id, $data) = each($array))
				array_push($tmp, $data);
			return $tmp;
		}
		return $array;
	}

	/**
	 * Custom sort function
	 *
	 * @access private
	 * @param mixed $a an array entry
	 * @param mixed $b an array entry
	 */
	function _as_cmp($a, $b)
	{
		//since uksort will pass here only indexes get real values from our array
		if (!is_array($a) && !is_array($b))
		{
			$a = $this->sarray[$a][$this->skey];
			$b = $this->sarray[$b][$this->skey];
		}

		//if string - use string comparision
		if (!is_numeric($a) && !is_numeric($b))
		{
			if ($this->sasc)
				return strcasecmp($a, $b);
			else
				return strcasecmp($b, $a);
		}
		else
		{
			if (intval($a) == intval($b))
				return 0;

			if ($this->sasc)
				return (intval($a) > intval($b)) ? 1 : -1;
			else
				return (intval($a) > intval($b)) ? -1 : 1;
		}
	}
}

Zapraszam do analizy kodu. Zaproponowana implementacja nie jest oczywiście najdoskonalsza, ale służyć ma jedynie za przykład, że zadanie jest do rozwiązania bez stosowania rekursji w zapytaniach do bazy danych, co jest operacją bardzo kosztowną czasowo.

software code