GAE text search with quadratic sorting
Instead of full-text search on GAE, I use the solution below to return a sorted result set, first by keyword relevance and then by date (although the second sort can actually be anything). It feels a bit clunky, and I’m worried about performance at scale, so I’m looking for optimization suggestions or a completely different approach.
Quadratic sorting is important for my use case because a given search may have multiple results of the same relevance (measured by the number of keyword matches), but keeping the original query order now adds a lot of complexity. Any ideas?
Step 1: Get a list of keys that match each search term
results_key_list =  search_terms = ['a','b','c'] #User's search query, split into a list of strings #query each search term and add the results to a list #yields a list of keys with frequency of occurance indicating relevance for item in search_terms: subquery = SomeEntity.all(keys_only=True) subquery.filter('SearchIndex = ', item) #SearchIndex is a StringListProperty #more filters... subquery.order('-DateCreated') for returned_item in subquery: results_key_list.append(str(returned_item))
Step 2: Group the list by frequency while maintaining the original order
#return a dictionary of keys, with their frequency of occurrence grouped_results = defaultdict(int) for key in results_key_list: grouped_results[key] += 1 sorted_results =  known = set() #creates an empty list for each match frequency for i in range(len(search_terms)): sorted_results.append() #using the original results ordering, #construct an array of results grouped and ordered by descending frequency for key in results_key_list: if key in known: continue frequency = grouped_results[key] sorted_results[len(search_terms) - frequency].append(key) known.add(key) #combine into a single list ordered_key_list =  for l in sorted_results: ordered_key_list.extend(l) del ordered_key_list[:offset] del ordered_key_list[limit:] result = SomeEntity.get(ordered_key_list)
search_terms = ['a','b','c'] #User's search query, split into a list of strings
Keys can be accumulated in the order in which they appear
And all key frequencies can be established at once.
With sorting stability, reduce the frequency first, and then sort in the order in which they appear:
keys_in_order_of_appearance =  key_frequency = defaultdict(int) for item in search_terms: subquery = SomeEntity.all(keys_only=True) subquery.filter('SearchIndex = ', item) #SearchIndex is a StringListProperty #more filters... subquery.order('-DateCreated') for returned_item in subquery: key = str(returned_item) if key not in key_frequency: key_order_of_appearance.append(key) key_frequency[key] += 1 keys = keys_in_order_of_appearance[:] # order of appearance kept as secondary sort keys.sort(key=key_frequency.__getitem__, reverse=True) # descending freq as primary sort result = SomeEntity.get(ordered_key_list)