aboutsummaryrefslogtreecommitdiffstatshomepage
diff options
context:
space:
mode:
authorCharles Krinke2008-08-10 16:44:25 +0000
committerCharles Krinke2008-08-10 16:44:25 +0000
commit54af3b4f4dd8a2885dcc57904f04d603bb444f24 (patch)
treec66693db07a1452595c08c509b818f94003fe3c2
parentMantis#1910. Thank you kindly, HomerHorwitz for a patch that: (diff)
downloadopensim-SC-54af3b4f4dd8a2885dcc57904f04d603bb444f24.zip
opensim-SC-54af3b4f4dd8a2885dcc57904f04d603bb444f24.tar.gz
opensim-SC-54af3b4f4dd8a2885dcc57904f04d603bb444f24.tar.bz2
opensim-SC-54af3b4f4dd8a2885dcc57904f04d603bb444f24.tar.xz
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.
-rw-r--r--OpenSim/Data/MySQL/MySQLInventoryData.cs113
-rw-r--r--OpenSim/Data/SQLite/SQLiteInventoryStore.cs97
2 files changed, 201 insertions, 9 deletions
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
704 /// <returns></returns> 704 /// <returns></returns>
705 public List<InventoryFolderBase> getFolderHierarchy(LLUUID parentID) 705 public List<InventoryFolderBase> getFolderHierarchy(LLUUID parentID)
706 { 706 {
707 List<InventoryFolderBase> folders = new List<InventoryFolderBase>(); 707 /* Note: There are subtle changes between this implementation of getFolderHierarchy and the previous one
708 getInventoryFolders(ref folders, parentID); 708 * - We will only need to hit the database twice instead of n times.
709 * - We assume the database is well-formed - no stranded/dangling folders, all folders in heirarchy owned
710 * by the same person, each user only has 1 inventory heirarchy
711 * - The returned list is not ordered, instead of breadth-first ordered
712 There are basically 2 usage cases for getFolderHeirarchy:
713 1) Getting the user's entire inventory heirarchy when they log in
714 2) Finding a subfolder heirarchy to delete when emptying the trash.
715 This implementation will pull all inventory folders from the database, and then prune away any folder that
716 is not part of the requested sub-heirarchy. The theory is that it is cheaper to make 1 request from the
717 database than to make n requests. This pays off only if requested heirarchy is large.
718 By making this choice, we are making the worst case better at the cost of making the best case worse.
719 This way is generally better because we don't have to rebuild the connection/sql query per subfolder,
720 even if we end up getting more data from the SQL server than we need.
721 - Francis
722 */
723 try
724 {
725 List<InventoryFolderBase> folders = new List<InventoryFolderBase>();
726 Dictionary<LLUUID, List<InventoryFolderBase>> hashtable
727 = new Dictionary<LLUUID, List<InventoryFolderBase>>(); ;
728 List<InventoryFolderBase> parentFolder = new List<InventoryFolderBase>();
729 lock (database)
730 {
731 MySqlCommand result;
732 MySqlDataReader reader;
733 bool buildResultsFromHashTable = false;
734
735 database.CheckConnection();
709 736
710 for (int i = 0; i < folders.Count; i++) 737 /* Fetch the parent folder from the database to determine the agent ID, and if
711 getInventoryFolders(ref folders, folders[i].ID); 738 * we're querying the root of the inventory folder tree */
739 result = new MySqlCommand("SELECT * FROM inventoryfolders WHERE folderID = ?uuid",
740 database.Connection);
741 result.Parameters.AddWithValue("?uuid", parentID.ToString());
742 reader = result.ExecuteReader();
743 while (reader.Read()) // Should be at most 1 result
744 parentFolder.Add(readInventoryFolder(reader));
745 reader.Close();
746 result.Dispose();
712 747
713 return folders; 748 if (parentFolder.Count >= 1) // No result means parent folder does not exist
749 {
750 if (parentFolder[0].ParentID == LLUUID.Zero) // We are querying the root folder
751 {
752 /* Get all of the agent's folders from the database, put them in a list and return it */
753 result = new MySqlCommand("SELECT * FROM inventoryfolders WHERE agentID = ?uuid",
754 database.Connection);
755 result.Parameters.AddWithValue("?uuid", parentFolder[0].Owner.ToString());
756 reader = result.ExecuteReader();
757 while (reader.Read())
758 {
759 InventoryFolderBase curFolder = readInventoryFolder(reader);
760 if (curFolder.ID != parentID) // Do not need to add the root node of the tree to the list
761 folders.Add(curFolder);
762 }
763 reader.Close();
764 result.Dispose();
765 } // if we are querying the root folder
766 else // else we are querying a subtree of the inventory folder tree
767 {
768 /* Get all of the agent's folders from the database, put them all in a hash table
769 * indexed by their parent ID */
770 result = new MySqlCommand("SELECT * FROM inventoryfolders WHERE agentID = ?uuid",
771 database.Connection);
772 result.Parameters.AddWithValue("?uuid", parentFolder[0].Owner.ToString());
773 reader = result.ExecuteReader();
774 while (reader.Read())
775 {
776 InventoryFolderBase curFolder = readInventoryFolder(reader);
777 if (hashtable.ContainsKey(curFolder.ParentID)) // Current folder already has a sibling
778 hashtable[curFolder.ParentID].Add(curFolder); // append to sibling list
779 else // else current folder has no known (yet) siblings
780 {
781 List<InventoryFolderBase> siblingList = new List<InventoryFolderBase>();
782 siblingList.Add(curFolder);
783 // Current folder has no known (yet) siblings
784 hashtable.Add(curFolder.ParentID, siblingList);
785 }
786 } // while more items to read from the database
787 reader.Close();
788 result.Dispose();
789
790 // Set flag so we know we need to build the results from the hash table after
791 // we unlock the database
792 buildResultsFromHashTable = true;
793
794 } // else we are querying a subtree of the inventory folder tree
795 } // if folder parentID exists
796
797 if (buildResultsFromHashTable)
798 {
799 /* We have all of the user's folders stored in a hash table indexed by their parent ID
800 * and we need to return the requested subtree. We will build the requested subtree
801 * by performing a breadth-first-search on the hash table */
802 if (hashtable.ContainsKey(parentID))
803 folders.AddRange(hashtable[parentID]);
804 for (int i = 0; i < folders.Count; i++) // **Note: folders.Count is *not* static
805 if (hashtable.ContainsKey(folders[i].ID))
806 folders.AddRange(hashtable[folders[i].ID]);
807 }
808 } // lock(database)
809 return folders;
810 }
811 catch (Exception e)
812 {
813 database.Reconnect();
814 m_log.Error(e.ToString());
815 return null;
816 }
714 } 817 }
715 818
716 /// <summary> 819 /// <summary>
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
392 { 392 {
393 folders.Add(buildFolder(row)); 393 folders.Add(buildFolder(row));
394 } 394 }
395
395 } 396 }
396 } 397 }
397 398
@@ -414,12 +415,100 @@ namespace OpenSim.Data.SQLite
414 /// <returns></returns> 415 /// <returns></returns>
415 public List<InventoryFolderBase> getFolderHierarchy(LLUUID parentID) 416 public List<InventoryFolderBase> getFolderHierarchy(LLUUID parentID)
416 { 417 {
417 List<InventoryFolderBase> folders = new List<InventoryFolderBase>(); 418 /* Note: There are subtle changes between this implementation of getFolderHierarchy and the previous one
418 getInventoryFolders(ref folders, Util.ToRawUuidString(parentID)); 419 * - We will only need to hit the database twice instead of n times.
420 * - We assume the database is well-formed - no stranded/dangling folders, all folders in heirarchy owned
421 * by the same person, each user only has 1 inventory heirarchy
422 * - The returned list is not ordered, instead of breadth-first ordered
423 There are basically 2 usage cases for getFolderHeirarchy:
424 1) Getting the user's entire inventory heirarchy when they log in
425 2) Finding a subfolder heirarchy to delete when emptying the trash.
426 This implementation will pull all inventory folders from the database, and then prune away any folder that
427 is not part of the requested sub-heirarchy. The theory is that it is cheaper to make 1 request from the
428 database than to make n requests. This pays off only if requested heirarchy is large.
429 By making this choice, we are making the worst case better at the cost of making the best case worse
430 - Francis
431 */
419 432
420 for (int i = 0; i < folders.Count; i++) 433 List<InventoryFolderBase> folders = new List<InventoryFolderBase>();
421 getInventoryFolders(ref folders, Util.ToRawUuidString(folders[i].ID)); 434 DataRow[] folderRows = null, parentRow;
435 InventoryFolderBase parentFolder = null;
436 lock (ds)
437 {
438 /* Fetch the parent folder from the database to determine the agent ID.
439 * Then fetch all inventory folders for that agent from the agent ID.
440 */
441 DataTable inventoryFolderTable = ds.Tables["inventoryfolders"];
442 string selectExp = "UUID = '" + Util.ToRawUuidString(parentID) + "'";
443 parentRow = inventoryFolderTable.Select(selectExp); // Assume at most 1 result
444 if (parentRow.GetLength(0) >= 1) // No result means parent folder does not exist
445 {
446 parentFolder = buildFolder(parentRow[0]);
447 LLUUID agentID = parentFolder.Owner;
448 selectExp = "agentID = '" + Util.ToRawUuidString(agentID) + "'";
449 folderRows = inventoryFolderTable.Select(selectExp);
450 }
422 451
452 if ( folderRows!=null && folderRows.GetLength(0)>=1 ) // No result means parent folder does not exist
453 { // or has no children
454 /* if we're querying the root folder, just return an unordered list of all folders in the user's
455 * inventory
456 */
457 if (parentFolder.ParentID == LLUUID.Zero)
458 {
459 foreach (DataRow row in folderRows)
460 {
461 InventoryFolderBase curFolder = buildFolder(row);
462 if (curFolder.ID != parentID) // Return all folders except the parent folder of heirarchy
463 folders.Add(buildFolder(row));
464 }
465 } // If requesting root folder
466 /* else we are querying a non-root folder. We currently have a list of all of the user's folders,
467 * we must construct a list of all folders in the heirarchy below parentID.
468 * Our first step will be to construct a hash table of all folders, indexed by parent ID.
469 * Once we have constructed the hash table, we will do a breadth-first traversal on the tree using the
470 * hash table to find child folders.
471 */
472 else
473 { // Querying a non-root folder
474
475 // Build a hash table of all user's inventory folders, indexed by each folder's parent ID
476 Dictionary<LLUUID, List<InventoryFolderBase>> hashtable =
477 new Dictionary<LLUUID, List<InventoryFolderBase>>(folderRows.GetLength(0));
478
479 foreach (DataRow row in folderRows)
480 {
481 InventoryFolderBase curFolder = buildFolder(row);
482 if (curFolder.ParentID != LLUUID.Zero) // Discard root of tree - not needed
483 {
484 if ( hashtable.ContainsKey(curFolder.ParentID ) )
485 {
486 // Current folder already has a sibling - append to sibling list
487 hashtable[curFolder.ParentID].Add( curFolder );
488 }
489 else {
490 List<InventoryFolderBase> siblingList = new List<InventoryFolderBase>();
491 siblingList.Add( curFolder );
492 // Current folder has no known (yet) siblings
493 hashtable.Add( curFolder.ParentID, siblingList );
494 }
495 }
496 } // For all inventory folders
497
498 // Note: Could release the ds lock here - we don't access folderRows or the database anymore.
499 // This is somewhat of a moot point as the callers of this function usually lock db anyways.
500
501 if ( hashtable.ContainsKey( parentID ) ) // if requested folder does have children
502 folders.AddRange( hashtable[parentID] );
503
504 // BreadthFirstSearch build inventory tree **Note: folders.Count is *not* static
505 for ( int i = 0; i < folders.Count; i++ )
506 if (hashtable.ContainsKey(folders[i].ID))
507 folders.AddRange(hashtable[folders[i].ID]);
508
509 } // if requesting a subfolder heirarchy
510 } // if folder parentID exists and has children
511 } // lock ds
423 return folders; 512 return folders;
424 } 513 }
425 514