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/SQLite/SQLiteInventoryStore.cs | 97 +++++++++++++++++++++++++++--
1 file changed, 93 insertions(+), 4 deletions(-)
(limited to 'OpenSim/Data/SQLite/SQLiteInventoryStore.cs')
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