tree c24f2cfe0ecd4f2596bb0a04c6a2dfc41d5ec4aa
parent 1e31259812dd195015f4e415675ed97b804829a6
author Nan Zhou <nanzhoumails@gmail.com> 1659502675 +0000
committer Ed Tanous <ed@tanous.net> 1659633699 +0000

query: $select : use trie

The previous implementation has a downside: it stores all intermediate
paths in a hashset. This increases the space complexity. This commit
implements a more efficient (both time and space) algorithm: Trie.

The commit contructs a trie from the values of $select. Upon delegation,
it delegates the whole trie for now. When doing recursive select, now we
only need to keep the current JSON node and corresponding TrieNode.

Given the following assumption:
1. size of the JSON tree (#nodes) is N
2. length of the $select properties is M
3. average length of a single $select property is K

The previous implementation has the following complexity:
1. time: worst case O(N + M * K), when a property is like /a/a/a/a/a
2. space: O(N + M * K^2), when a property is like /a/a/a/a/a

The current implementation improves complexity to:
1. time: O(N + M * K)
2. space: O(N + M * K)

The total image (squashfs) decreases 4096 bytes. The binaray size
also decreases 4096 bytes.

Tested:
1. $select works on real hardware
2. No new service validator failures
3. Added more unit tests

Signed-off-by: Nan Zhou <nanzhoumails@gmail.com>
Change-Id: If9f09db8c76e4e1abb6fa9b760be3816d9eb9f96