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 ++++++++++++++++++++++++++--
OpenSim/Data/SQLite/SQLiteInventoryStore.cs | 97 +++++++++++++++++++++++-
2 files changed, 201 insertions(+), 9 deletions(-)
(limited to 'OpenSim/Data')
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;
+ }
}
///
diff --git a/OpenSim/Data/SQLite/SQLiteInventoryStore.cs b/OpenSim/Data/SQLite/SQLiteInventoryStore.cs
index ef4ef99..e29b99c 100644
--- a/OpenSim/Data/SQLite/SQLiteInventoryStore.cs
+++ b/OpenSim/Data/SQLite/SQLiteInventoryStore.cs
@@ -392,6 +392,7 @@ namespace OpenSim.Data.SQLite
{
folders.Add(buildFolder(row));
}
+
}
}
@@ -414,12 +415,100 @@ namespace OpenSim.Data.SQLite
///
public List getFolderHierarchy(LLUUID parentID)
{
- List folders = new List();
- getInventoryFolders(ref folders, Util.ToRawUuidString(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
+ - Francis
+ */
- for (int i = 0; i < folders.Count; i++)
- getInventoryFolders(ref folders, Util.ToRawUuidString(folders[i].ID));
+ List folders = new List();
+ DataRow[] folderRows = null, parentRow;
+ InventoryFolderBase parentFolder = null;
+ lock (ds)
+ {
+ /* Fetch the parent folder from the database to determine the agent ID.
+ * Then fetch all inventory folders for that agent from the agent ID.
+ */
+ DataTable inventoryFolderTable = ds.Tables["inventoryfolders"];
+ string selectExp = "UUID = '" + Util.ToRawUuidString(parentID) + "'";
+ parentRow = inventoryFolderTable.Select(selectExp); // Assume at most 1 result
+ if (parentRow.GetLength(0) >= 1) // No result means parent folder does not exist
+ {
+ parentFolder = buildFolder(parentRow[0]);
+ LLUUID agentID = parentFolder.Owner;
+ selectExp = "agentID = '" + Util.ToRawUuidString(agentID) + "'";
+ folderRows = inventoryFolderTable.Select(selectExp);
+ }
+ if ( folderRows!=null && folderRows.GetLength(0)>=1 ) // No result means parent folder does not exist
+ { // or has no children
+ /* if we're querying the root folder, just return an unordered list of all folders in the user's
+ * inventory
+ */
+ if (parentFolder.ParentID == LLUUID.Zero)
+ {
+ foreach (DataRow row in folderRows)
+ {
+ InventoryFolderBase curFolder = buildFolder(row);
+ if (curFolder.ID != parentID) // Return all folders except the parent folder of heirarchy
+ folders.Add(buildFolder(row));
+ }
+ } // If requesting root folder
+ /* else we are querying a non-root folder. We currently have a list of all of the user's folders,
+ * we must construct a list of all folders in the heirarchy below parentID.
+ * Our first step will be to construct a hash table of all folders, indexed by parent ID.
+ * Once we have constructed the hash table, we will do a breadth-first traversal on the tree using the
+ * hash table to find child folders.
+ */
+ else
+ { // Querying a non-root folder
+
+ // Build a hash table of all user's inventory folders, indexed by each folder's parent ID
+ Dictionary> hashtable =
+ new Dictionary>(folderRows.GetLength(0));
+
+ foreach (DataRow row in folderRows)
+ {
+ InventoryFolderBase curFolder = buildFolder(row);
+ if (curFolder.ParentID != LLUUID.Zero) // Discard root of tree - not needed
+ {
+ if ( hashtable.ContainsKey(curFolder.ParentID ) )
+ {
+ // Current folder already has a sibling - append to sibling list
+ hashtable[curFolder.ParentID].Add( curFolder );
+ }
+ else {
+ List siblingList = new List();
+ siblingList.Add( curFolder );
+ // Current folder has no known (yet) siblings
+ hashtable.Add( curFolder.ParentID, siblingList );
+ }
+ }
+ } // For all inventory folders
+
+ // Note: Could release the ds lock here - we don't access folderRows or the database anymore.
+ // This is somewhat of a moot point as the callers of this function usually lock db anyways.
+
+ if ( hashtable.ContainsKey( parentID ) ) // if requested folder does have children
+ folders.AddRange( hashtable[parentID] );
+
+ // BreadthFirstSearch build inventory tree **Note: folders.Count is *not* static
+ for ( int i = 0; i < folders.Count; i++ )
+ if (hashtable.ContainsKey(folders[i].ID))
+ folders.AddRange(hashtable[folders[i].ID]);
+
+ } // if requesting a subfolder heirarchy
+ } // if folder parentID exists and has children
+ } // lock ds
return folders;
}
--
cgit v1.1