diff options
author | Charles Krinke | 2008-08-10 16:44:25 +0000 |
---|---|---|
committer | Charles Krinke | 2008-08-10 16:44:25 +0000 |
commit | 54af3b4f4dd8a2885dcc57904f04d603bb444f24 (patch) | |
tree | c66693db07a1452595c08c509b818f94003fe3c2 | |
parent | Mantis#1910. Thank you kindly, HomerHorwitz for a patch that: (diff) | |
download | opensim-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.cs | 113 | ||||
-rw-r--r-- | OpenSim/Data/SQLite/SQLiteInventoryStore.cs | 97 |
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 | ||