From 54af3b4f4dd8a2885dcc57904f04d603bb444f24 Mon Sep 17 00:00:00 2001
From: Charles Krinke
Date: Sun, 10 Aug 2008 16:44:25 +0000
Subject: Mantis#1903. Thank you kindly, CMickeyb for a patch that: patch
attached replaces the tree walk algorithm used to build the folder hierarchy
with a single database query. That is, we replace 1 database query per folder
with 1 query for the root folder's properties and 1 query to retrieve the
entire collection of folders for a user.
---
OpenSim/Data/MySQL/MySQLInventoryData.cs | 113 +++++++++++++++++++++++++++++--
1 file changed, 108 insertions(+), 5 deletions(-)
(limited to 'OpenSim/Data/MySQL')
diff --git a/OpenSim/Data/MySQL/MySQLInventoryData.cs b/OpenSim/Data/MySQL/MySQLInventoryData.cs
index 0fb49c1..59d7858 100644
--- a/OpenSim/Data/MySQL/MySQLInventoryData.cs
+++ b/OpenSim/Data/MySQL/MySQLInventoryData.cs
@@ -704,13 +704,116 @@ namespace OpenSim.Data.MySQL
///
public List getFolderHierarchy(LLUUID parentID)
{
- List folders = new List();
- getInventoryFolders(ref folders, parentID);
+ /* Note: There are subtle changes between this implementation of getFolderHierarchy and the previous one
+ * - We will only need to hit the database twice instead of n times.
+ * - We assume the database is well-formed - no stranded/dangling folders, all folders in heirarchy owned
+ * by the same person, each user only has 1 inventory heirarchy
+ * - The returned list is not ordered, instead of breadth-first ordered
+ There are basically 2 usage cases for getFolderHeirarchy:
+ 1) Getting the user's entire inventory heirarchy when they log in
+ 2) Finding a subfolder heirarchy to delete when emptying the trash.
+ This implementation will pull all inventory folders from the database, and then prune away any folder that
+ is not part of the requested sub-heirarchy. The theory is that it is cheaper to make 1 request from the
+ database than to make n requests. This pays off only if requested heirarchy is large.
+ By making this choice, we are making the worst case better at the cost of making the best case worse.
+ This way is generally better because we don't have to rebuild the connection/sql query per subfolder,
+ even if we end up getting more data from the SQL server than we need.
+ - Francis
+ */
+ try
+ {
+ List folders = new List();
+ Dictionary> hashtable
+ = new Dictionary>(); ;
+ List parentFolder = new List();
+ lock (database)
+ {
+ MySqlCommand result;
+ MySqlDataReader reader;
+ bool buildResultsFromHashTable = false;
+
+ database.CheckConnection();
- for (int i = 0; i < folders.Count; i++)
- getInventoryFolders(ref folders, folders[i].ID);
+ /* Fetch the parent folder from the database to determine the agent ID, and if
+ * we're querying the root of the inventory folder tree */
+ result = new MySqlCommand("SELECT * FROM inventoryfolders WHERE folderID = ?uuid",
+ database.Connection);
+ result.Parameters.AddWithValue("?uuid", parentID.ToString());
+ reader = result.ExecuteReader();
+ while (reader.Read()) // Should be at most 1 result
+ parentFolder.Add(readInventoryFolder(reader));
+ reader.Close();
+ result.Dispose();
- return folders;
+ if (parentFolder.Count >= 1) // No result means parent folder does not exist
+ {
+ if (parentFolder[0].ParentID == LLUUID.Zero) // We are querying the root folder
+ {
+ /* Get all of the agent's folders from the database, put them in a list and return it */
+ result = new MySqlCommand("SELECT * FROM inventoryfolders WHERE agentID = ?uuid",
+ database.Connection);
+ result.Parameters.AddWithValue("?uuid", parentFolder[0].Owner.ToString());
+ reader = result.ExecuteReader();
+ while (reader.Read())
+ {
+ InventoryFolderBase curFolder = readInventoryFolder(reader);
+ if (curFolder.ID != parentID) // Do not need to add the root node of the tree to the list
+ folders.Add(curFolder);
+ }
+ reader.Close();
+ result.Dispose();
+ } // if we are querying the root folder
+ else // else we are querying a subtree of the inventory folder tree
+ {
+ /* Get all of the agent's folders from the database, put them all in a hash table
+ * indexed by their parent ID */
+ result = new MySqlCommand("SELECT * FROM inventoryfolders WHERE agentID = ?uuid",
+ database.Connection);
+ result.Parameters.AddWithValue("?uuid", parentFolder[0].Owner.ToString());
+ reader = result.ExecuteReader();
+ while (reader.Read())
+ {
+ InventoryFolderBase curFolder = readInventoryFolder(reader);
+ if (hashtable.ContainsKey(curFolder.ParentID)) // Current folder already has a sibling
+ hashtable[curFolder.ParentID].Add(curFolder); // append to sibling list
+ else // else current folder has no known (yet) siblings
+ {
+ List siblingList = new List();
+ siblingList.Add(curFolder);
+ // Current folder has no known (yet) siblings
+ hashtable.Add(curFolder.ParentID, siblingList);
+ }
+ } // while more items to read from the database
+ reader.Close();
+ result.Dispose();
+
+ // Set flag so we know we need to build the results from the hash table after
+ // we unlock the database
+ buildResultsFromHashTable = true;
+
+ } // else we are querying a subtree of the inventory folder tree
+ } // if folder parentID exists
+
+ if (buildResultsFromHashTable)
+ {
+ /* We have all of the user's folders stored in a hash table indexed by their parent ID
+ * and we need to return the requested subtree. We will build the requested subtree
+ * by performing a breadth-first-search on the hash table */
+ if (hashtable.ContainsKey(parentID))
+ folders.AddRange(hashtable[parentID]);
+ for (int i = 0; i < folders.Count; i++) // **Note: folders.Count is *not* static
+ if (hashtable.ContainsKey(folders[i].ID))
+ folders.AddRange(hashtable[folders[i].ID]);
+ }
+ } // lock(database)
+ return folders;
+ }
+ catch (Exception e)
+ {
+ database.Reconnect();
+ m_log.Error(e.ToString());
+ return null;
+ }
}
///
--
cgit v1.1