Add ancestors_* tables, for faster 'toroot' lookupancestors-tables

Speedup seemed minor, and for a non-wide range of situations.
It also roughly quadrupled the database size.

5 files changed, 51 insertions, 22 deletions

diff --git a/backend/cgi-bin/data.py b/backend/cgi-bin/data.py
index 1334dfc..16f7b01 100755
--- a/backend/cgi-bin/data.py
+++ b/backend/cgi-bin/data.py
@@ -22,8 +22,8 @@ Query parameters:
     If 'node', reply with a name-to-TolNode map, describing the named node and it's children.
     If 'sugg', reply with a SearchSuggResponse, describing search suggestions for the possibly-partial name.
     If 'info', reply with an InfoResponse, describing the named node.
-- toroot: Used with type=node, and causes inclusion of nodes upward to the root, and their children.
-    If specified, the value should be 'true'.
+- toroot: Used with type=node, and causes inclusion of ancestors, and their children.
+	The value names a node whose ancestors need not be included.
 - limit: Used with type=sugg to specify the max number of suggestions.
 - tree: Specifies which tree should be used.
     May be 'trimmed', 'images', or 'picked', corresponding to the
@@ -88,7 +88,7 @@ def lookupNodes(names, tree, dbCur):
 	" For a set of node names, returns a name-to-TolNode map that describes those nodes "
 	# Get node info
 	nameToNodes = {}
-	tblSuffix = "t" if tree == "trimmed" else "i" if tree == "images" else "p"
+	tblSuffix = getTableSuffix(tree)
 	nodesTable = f"nodes_{tblSuffix}"
 	edgesTable = f"edges_{tblSuffix}"
 	queryParamStr = ",".join(["?"] * len(names))
@@ -143,8 +143,7 @@ def lookupSuggs(searchStr, suggLimit, tree, dbCur):
 	hasMore = False
 	# Get node names and alt-names
 	query1, query2 = (None, None)
-	tblSuffix = "t" if tree == "trimmed" else "i" if tree == "images" else "p"
-	nodesTable = f"nodes_{tblSuffix}"
+	nodesTable = f"nodes_{getTableSuffix(tree)}"
 	query1 = f"SELECT DISTINCT name FROM {nodesTable}" \
 		f" WHERE name LIKE ? AND name NOT LIKE '[%' ORDER BY length(name) LIMIT ?"
 	query2 = f"SELECT DISTINCT alt_name, names.name FROM" \
@@ -221,6 +220,8 @@ def lookupInfo(name, tree, dbCur):
 		) if n != None else None for n in [name] + subNames
 	]
 	return InfoResponse(nodeInfoObjs[0], nodeInfoObjs[1:])
+def getTableSuffix(tree):
+	return "t" if tree == "trimmed" else "i" if tree == "images" else "p"
 
 # For handling request
 def respondJson(val):
@@ -254,8 +255,8 @@ def handleReq(dbCur):
 		return
 	# Get data of requested type
 	if reqType == "node":
-		toroot = "toroot" in queryDict and queryDict["toroot"][0] == "true"
-		if not toroot:
+		toroot = queryDict["toroot"][0] if "toroot" in queryDict else None
+		if toroot == None:
 			tolNodes = lookupNodes([name], tree, dbCur)
 			if len(tolNodes) > 0:
 				tolNode = tolNodes[name]
@@ -264,6 +265,11 @@ def handleReq(dbCur):
 				respondJson(childNodeObjs)
 				return
 		else:
+			# Get ancestors to skip inclusion of
+			ancestorTbl = f"ancestors_{getTableSuffix(tree)}"
+			query = f"SELECT ancestor FROM {ancestorTbl} WHERE name = ?"
+			nodesToSkip = {row[0] for row in dbCur.execute(query, (toroot,))}
+			#
 			results = {}
 			ranOnce = False
 			while True:
@@ -288,7 +294,7 @@ def handleReq(dbCur):
 					childNodeObjs = lookupNodes(childNamesToAdd, tree, dbCur)
 					results.update(childNodeObjs)
 				# Check if root
-				if tolNode.parent == None:
+				if tolNode.parent in nodesToSkip or tolNode.parent == None:
 					respondJson(results)
 					return
 				else:
diff --git a/backend/data/README.md b/backend/data/README.md
index 13aeb89..b4b0745 100644
--- a/backend/data/README.md
+++ b/backend/data/README.md
@@ -43,6 +43,8 @@ This directory holds files used to generate data.db, which contains tree-of-life
     These are like `nodes`, but describe the nodes for various reduced trees.
 -   `edges_t`, `edges_i`, `edges_p` <br>
     Like `edges` but for reduced trees.
+-   `ancestors_t`, `ancestors_i`, `ancestors_p` <br>
+    Maps nodes to their ancestors. Used for faster lookup.
 
 # Generating the Database
 
@@ -146,7 +148,6 @@ Some of the python scripts require third-party packages:
         These correspond to entries in the `names` table. `prefAlt` should be 1 or 0.
         A line like `name1|name1|1` causes a node to have no preferred alt-name.
 3.  Run genReducedTrees.py, which generates multiple reduced versions of the tree,
-    adding the `nodes_*` and `edges_*` tables, using `nodes` and `names`. Reads from
-    pickedNodes.txt, which lists names of nodes that must be included (1 per line).
-    The original tree isn't used for web-queries, as some nodes would have over 
-    10k children, which can take a while to render (took over a minute in testing).
+    adding the `nodes_*`, `edges_*`, and `ancestors_*` tables, using `nodes` and
+    `names`. Reads from pickedNodes.txt, which lists names of nodes that must be
+    included (1 per line). The original tree isn't used for web-queries.
diff --git a/backend/data/genReducedTrees.py b/backend/data/genReducedTrees.py
index a921be4..ad73d3c 100755
--- a/backend/data/genReducedTrees.py
+++ b/backend/data/genReducedTrees.py
@@ -88,8 +88,8 @@ def genPickedNodeTree(dbCur, pickedNames, rootName):
 	print(f"Result has {len(nodeMap)} nodes")
 	print("Updating 'tips' values")
 	updateTips(rootName, nodeMap)
-	print("Creating table")
-	addTreeTables(nodeMap, dbCur, "p")
+	print("Creating tables")
+	addTreeTables(nodeMap, dbCur, "p", rootName)
 def genImagesOnlyTree(dbCur, nodesWithImgOrPicked, pickedNames, rootName):
 	print("Getting ancestors")
 	nodeMap = genNodeMap(dbCur, nodesWithImgOrPicked, 1e4)
@@ -107,8 +107,8 @@ def genImagesOnlyTree(dbCur, nodesWithImgOrPicked, pickedNames, rootName):
 	print(f"Result has {len(nodeMap)} nodes")
 	print(f"Updating 'tips' values")
 	updateTips(rootName, nodeMap)
-	print("Creating table")
-	addTreeTables(nodeMap, dbCur, "i")
+	print("Creating tables")
+	addTreeTables(nodeMap, dbCur, "i", rootName)
 def genWeaklyTrimmedTree(dbCur, nodesWithImgDescOrPicked, nodesWithImgOrPicked, rootName):
 	print("Getting ancestors")
 	nodeMap = genNodeMap(dbCur, nodesWithImgDescOrPicked, 1e5)
@@ -139,7 +139,7 @@ def genWeaklyTrimmedTree(dbCur, nodesWithImgDescOrPicked, nodesWithImgOrPicked,
 	print(f"Updating 'tips' values")
 	updateTips(rootName, nodeMap)
 	print("Creating table")
-	addTreeTables(nodeMap, dbCur, "t")
+	addTreeTables(nodeMap, dbCur, "t", rootName)
 # Helper functions
 def genNodeMap(dbCur, nameSet, itersBeforePrint = 1):
 	" Returns a subtree that includes nodes in 'nameSet', as a name-to-Node map "
@@ -256,8 +256,9 @@ def updateTips(nodeName, nodeMap):
 	tips = max(1, tips)
 	node.tips = tips
 	return tips
-def addTreeTables(nodeMap, dbCur, suffix):
+def addTreeTables(nodeMap, dbCur, suffix, rootName):
 	" Adds a tree to the database, as tables nodes_X and edges_X, where X is the given suffix "
+	print("Creating nodes and edges tables")
 	nodesTbl = f"nodes_{suffix}"
 	edgesTbl = f"edges_{suffix}"
 	dbCur.execute(f"CREATE TABLE {nodesTbl} (name TEXT PRIMARY KEY, id TEXT UNIQUE, tips INT)")
@@ -269,6 +270,25 @@ def addTreeTables(nodeMap, dbCur, suffix):
 		for childName in node.children:
 			pSupport = 1 if nodeMap[childName].pSupport else 0
 			dbCur.execute(f"INSERT INTO {edgesTbl} VALUES (?, ?, ?)", (name, childName, pSupport))
+	print("Creating ancestors table")
+	ancestorsTbl = f"ancestors_{suffix}"
+	dbCur.execute(f"CREATE TABLE {ancestorsTbl} (name TEXT, ancestor TEXT, PRIMARY KEY (name, ancestor))")
+	dbCur.execute(f"CREATE INDEX {ancestorsTbl}_idx ON {ancestorsTbl}(name)")
+	iterNum = 0
+	def addAncestors(nodeName, ancestors = []):
+		nonlocal nodeMap, dbCur, iterNum
+		iterNum += 1
+		if iterNum % 1e4 == 0:
+			print(f"At iteration {iterNum}")
+		#
+		node = nodeMap[nodeName]
+		for ancestor in ancestors:
+			dbCur.execute(f"INSERT INTO {ancestorsTbl} VALUES (?, ?)", (nodeName, ancestor))
+		ancestors.append(nodeName)
+		for childName in node.children:
+			addAncestors(childName, ancestors)
+		ancestors.pop()
+	addAncestors(rootName)
 
 print(f"Finding root node")
 query = "SELECT name FROM nodes LEFT JOIN edges ON nodes.name = edges.child WHERE edges.parent IS NULL LIMIT 1"
diff --git a/src/App.vue b/src/App.vue
index 434eb08..e379a1d 100644
--- a/src/App.vue
+++ b/src/App.vue
@@ -49,7 +49,8 @@
 	</div>
 	<!-- Modals -->
 	<transition name="fade">
-		<search-modal v-if="searchOpen" :tolMap="tolMap" :lytMap="layoutMap" :lytOpts="lytOpts" :uiOpts="uiOpts"
+		<search-modal v-if="searchOpen"
+			:tolMap="tolMap" :lytMap="layoutMap" :activeRoot="activeRoot" :lytOpts="lytOpts" :uiOpts="uiOpts"
 			@close="onSearchClose" @search="onSearch" @info-click="onInfoClick" @setting-chg="onSettingChg"
 			@net-wait="primeLoadInd('Loading data')" @net-get="endLoadInd" class="z-10" ref="searchModal"/>
 	</transition>
@@ -542,7 +543,7 @@ export default defineComponent({
 				layoutNode.addDescendantChain(nodesToAdd, this.tolMap, this.layoutMap);
 				// Expand-to-view on target-node's parent
 				targetNode = this.layoutMap.get(name);
-				if (targetNode.parent != this.activeRoot){
+				if (targetNode!.parent != this.activeRoot){
 					await this.onLeafClickHeld(targetNode!.parent!, true);
 				} else {
 					await this.onLeafClick(targetNode!.parent!, true);
@@ -864,7 +865,7 @@ export default defineComponent({
 			let urlParams = new URLSearchParams({type: 'node', tree: this.uiOpts.tree});
 			if (nodeName != null){
 				urlParams.append('name', nodeName);
-				urlParams.append('toroot', 'true');
+				urlParams.append('toroot', this.activeRoot.name);
 			}
 			let responseObj: {[x: string]: TolNode} = await this.loadFromServer(urlParams);
 			if (responseObj == null){
diff --git a/src/components/SearchModal.vue b/src/components/SearchModal.vue
index de6bc75..990312a 100644
--- a/src/components/SearchModal.vue
+++ b/src/components/SearchModal.vue
@@ -43,6 +43,7 @@ import {queryServer, SearchSugg, SearchSuggResponse, UiOptions} from '../lib';
 export default defineComponent({
 	props: {
 		lytMap: {type: Object as PropType<LayoutMap>, required: true}, // Used to check if a searched-for node exists
+		activeRoot: {type: Object as PropType<LayoutNode>, required: true}, // Sent to server to reduce response size
 		tolMap: {type: Object as PropType<TolMap>, required: true}, // Upon a search response, gets new nodes added
 		lytOpts: {type: Object as PropType<LayoutOptions>, required: true},
 		uiOpts: {type: Object as PropType<UiOptions>, required: true},
@@ -205,7 +206,7 @@ export default defineComponent({
 			let urlParams = new URLSearchParams({
 				type: 'node',
 				name: tolNodeName,
-				toroot: 'true',
+				toroot: this.activeRoot.name,
 				tree: this.uiOpts.tree,
 			});
 			this.$emit('net-wait'); // Allows the parent component to show a loading-indicator