feat: Make queries utilise secondary indexes

[islamaliev]

Relevant issue(s)

Resolves #1555

Description

With this change the the secondary indexes are utilised during querying data.

A dedicated Indexer fetcher is implemented to perform fetching of values of indexed fields.

Now there is a separate filter package that houses a lot of methods for working with filters.

A new metric indexesFetched is introduced into @explain to provide information about how many indexes has been fetched.

It also includes an update to the testing framework to allow adding custom asserters.
The new ExplainResultsAsserter is used with this new feature.

Benchmark

I ran some query benchmarks with regular fetching and indexed fetching on 10k docs and here is the summary:

Time per Operation (ns/op)
Indexed: Took approximately 2,196,481 nanoseconds (~2.2 ms) per operation
Original: Took approximately 74,037,628 nanoseconds (~74 ms) per operation
Boost Factor: Indexed is approximately 33.7 times faster than the original.

Memory Allocation (B/op)
Indexed: Allocated approximately 1,053,403 bytes (~1 MB) per operation
Original: Allocated approximately 45,218,327 bytes (~45 MB) per operation
Boost Factor: Indexed uses approximately 42.9 times less memory than the original.

Number of Allocations (allocs/op)
Indexed: Made 13,331 memory allocations per operation
Original: Made 494,494 memory allocations per operation
Boost Factor: Indexed has approximately 37.1 times fewer memory allocations than the original.

Summary
The indexed approach is 33.7 times faster, uses 42.9 times less memory, and has 37.1 times fewer memory allocations compared to the original approach.

Tasks

• I made sure the code is well commented, particularly hard-to-understand areas.
• I made sure the repository-held documentation is changed accordingly.
• I made sure the pull request title adheres to the conventional commit style (the subset used in the project can be found in tools/configs/chglog/config.yml).
• I made sure to discuss its limitations such as threats to validity, vulnerability to mistake and misuse, robustness to invalidation of assumptions, resource requirements, ...

How has this been tested?

Integration tests

Specify the platform(s) on which this was tested:

• MacOS

[AndrewSisley]

todo: The purpose of indexes is performance gains on read, at the cost of performance on write (and storage space). I really think performance tests should be included in this PR.

I would like to see performance tests for non-indexed vs indexed queries, on both read and write. Without these we are not really testing that this code change is doing anything useful, and could be seen as an explain-feature or a simple refactor.

praise: What I have seen so far of the production code looks good, but I have left a few comments dotted about. Will finish my review a bit later once some of them have been addressed.

[islamaliev]

I would like to see performance tests for non-indexed vs indexed queries, on both read and write. Without these we are not really testing that this code change is doing anything useful, and could be seen as an explain-feature or a simple refactor.

Do you mean adding tests to tests/bench?

[AndrewSisley]

Do you mean adding tests to tests/bench?

Adding to tests/bench would probably be the simplest for now, we could also assert on one being faster than the other (with appropriate protections against variation).

At the moment there is nothing that really tests the behaviour change that the users care about (query speed).

[codecov]

Codecov Report

Attention: 121 lines in your changes are missing coverage. Please review.

Comparison is base (bc4c704) 74.67% compared to head (869f867) 74.98%.

@@             Coverage Diff             @@
##           develop    #1925      +/-   ##
===========================================
+ Coverage    74.67%   74.98%   +0.30%     
===========================================
  Files          234      241       +7     
  Lines        23044    23616     +572     
===========================================
+ Hits         17208    17707     +499     
- Misses        4661     4709      +48     
- Partials      1175     1200      +25     

Flag	Coverage Δ
all-tests	74.98% <86.34%> (+0.30%)	⬆️

Flags with carried forward coverage won't be shown. Click here to find out more.

Files	Coverage Δ
client/index.go	100.00% <100.00%> (ø)
datastore/errors.go	100.00% <100.00%> (ø)
db/collection_index.go	97.24% <100.00%> (+0.60%)	⬆️
db/fetcher/fetcher.go	76.54% <100.00%> (+0.23%)	⬆️
db/index.go	97.25% <100.00%> (-0.35%)	⬇️
errors/defraError.go	100.00% <100.00%> (ø)
planner/datasource.go	83.33% <100.00%> (-8.33%)	⬇️
planner/filter/complex.go	100.00% <ø> (ø)
planner/filter/copy_field.go	96.36% <100.00%> (+1.01%)	⬆️
planner/filter/extract_properties.go	100.00% <100.00%> (ø)
... and 14 more

... and 7 files with indirect coverage changes

---

Continue to review full report in Codecov by Sentry.

Legend - Click here to learn more
Δ = absolute <relative> (impact), ø = not affected, ? = missing data
Powered by Codecov. Last update bc4c704...869f867. Read the comment docs.

[AndrewSisley]

Submitting a few comments now, as they are pilling up a bit and I need a breather.

Overall it looks good, but the tests in particular need so work I think.

[fredcarle]

LGTM. Nice work Islam. Just one minor thought on the extra param ion the bench tests.

[fredcarle]

LGTM. Nice work Islam. Just one minor thought on the extra param ion the bench tests.

Note: Make sure all conversations with Andy are resolved before merging.

[AndrewSisley]

LGTM, please resolve the remaining conversations before merge though.

I have a request for future PRs too - when resolving a conversation, can you please comment in the conversation/thread what you have done to resolve it. It makes it easier to review, as I don't have to then go and re-find the location (which can sometimes be tricky due to github/other changes), and then figure out what has been done to resolve it (also sometimes tricky and occasionally requiring guesswork).