New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

optimize has_child query when matching parent count is low #3190

Closed
mattweber opened this Issue Jun 15, 2013 · 4 comments

Comments

Projects
None yet
3 participants
@mattweber
Contributor

mattweber commented Jun 15, 2013

Currently the has_child query loops over every single document of the parent type looking for the parents matched in child query. In situations where the child query only matches few parents, this loop is expensive.

I feel this loop can be eliminated or short-circuited early since we already know the matching parent ids (the keys of the uidToScore map).

I am currently testing a few approaches and will submit a PR when ready.

/cc @martijnvg @s1monw

@martijnvg

This comment has been minimized.

Show comment
Hide comment
@martijnvg

martijnvg Jun 30, 2013

Member

I added a benchmark (ChildSearchShortCircutBenchmark) to test the short circuit mechanisms @mattweber came up with and the results look promising. The benchmark inserts 10M parent docs and a bunch of child docs. Child docs are inserted in groups from a group containing 1 doc to 1M docs (each group has double amount of child docs as previous group), this allows to show the performance impact between short circuits in place and no short circuits in place.

Test results without the short circuits:

--> has_child filter with 1 parent hits, query Avg: 139ms
--> has_child filter with 2 parent hits, query Avg: 287ms
--> has_child filter with 4 parent hits, query Avg: 448ms
--> has_child filter with 8 parent hits, query Avg: 641ms
--> has_child filter with 16 parent hits, query Avg: 849ms
--> has_child filter with 32  parent hits, query Avg: 1063ms
--> has_child filter with 64 parent hits, query Avg: 1268ms
--> has_child filter with 128 parent hits, query Avg: 1469ms
--> has_child filter with 256 parent hits, query Avg: 1660ms
--> has_child filter with 512 parent hits, query Avg: 1851ms
--> has_child filter with 1024 parent hits, query Avg: 2048ms
--> has_child filter with 2048 parent hits, query Avg: 2236ms
--> has_child filter with 4096 parent hits, query Avg: 2428ms
--> has_child filter with 8192 parent hits, query Avg: 2612ms
--> has_child filter with 16384 parent hits, query Avg: 2803ms
--> has_child filter with 32768 parent hits, query Avg: 3007ms
--> has_child filter with 65536 parent hits, query Avg: 3230ms

Test results with the short circuit:

--> has_child filter with 1 parent hits, query Avg: 3ms
--> has_child filter with 2 parent hits, query Avg: 6ms
--> has_child filter with 4 parent hits query Avg: 9ms
--> has_child filter with 8 parent hits query Avg: 13ms
--> has_child filter with 16 parent hits query Avg: 17ms
--> has_child filter with 32 parent hits query Avg: 20ms
--> has_child filter with 64 parent hits query Avg: 24ms
--> has_child filter with 128 parent hits query Avg: 28ms
--> has_child filter with 256 parent hits query  Avg: 33ms
--> has_child filter with 512 parent hits query  Avg: 37ms
--> has_child filter with 1024 parent hits query  Avg: 49ms
--> has_child filter with 2048 parent hits query  Avg: 62ms
--> has_child filter with 4096 parent hits query  Avg: 80ms
--> has_child filter with 8192 parent hits query  Avg: 111ms
--> has_child filter with 16384 parent hits query  Avg: 172ms
--> has_child filter with 32768 parent hits query  Avg: 275ms
--> has_child filter with 65536 parent hits query  Avg: 453ms
Member

martijnvg commented Jun 30, 2013

I added a benchmark (ChildSearchShortCircutBenchmark) to test the short circuit mechanisms @mattweber came up with and the results look promising. The benchmark inserts 10M parent docs and a bunch of child docs. Child docs are inserted in groups from a group containing 1 doc to 1M docs (each group has double amount of child docs as previous group), this allows to show the performance impact between short circuits in place and no short circuits in place.

Test results without the short circuits:

--> has_child filter with 1 parent hits, query Avg: 139ms
--> has_child filter with 2 parent hits, query Avg: 287ms
--> has_child filter with 4 parent hits, query Avg: 448ms
--> has_child filter with 8 parent hits, query Avg: 641ms
--> has_child filter with 16 parent hits, query Avg: 849ms
--> has_child filter with 32  parent hits, query Avg: 1063ms
--> has_child filter with 64 parent hits, query Avg: 1268ms
--> has_child filter with 128 parent hits, query Avg: 1469ms
--> has_child filter with 256 parent hits, query Avg: 1660ms
--> has_child filter with 512 parent hits, query Avg: 1851ms
--> has_child filter with 1024 parent hits, query Avg: 2048ms
--> has_child filter with 2048 parent hits, query Avg: 2236ms
--> has_child filter with 4096 parent hits, query Avg: 2428ms
--> has_child filter with 8192 parent hits, query Avg: 2612ms
--> has_child filter with 16384 parent hits, query Avg: 2803ms
--> has_child filter with 32768 parent hits, query Avg: 3007ms
--> has_child filter with 65536 parent hits, query Avg: 3230ms

Test results with the short circuit:

--> has_child filter with 1 parent hits, query Avg: 3ms
--> has_child filter with 2 parent hits, query Avg: 6ms
--> has_child filter with 4 parent hits query Avg: 9ms
--> has_child filter with 8 parent hits query Avg: 13ms
--> has_child filter with 16 parent hits query Avg: 17ms
--> has_child filter with 32 parent hits query Avg: 20ms
--> has_child filter with 64 parent hits query Avg: 24ms
--> has_child filter with 128 parent hits query Avg: 28ms
--> has_child filter with 256 parent hits query  Avg: 33ms
--> has_child filter with 512 parent hits query  Avg: 37ms
--> has_child filter with 1024 parent hits query  Avg: 49ms
--> has_child filter with 2048 parent hits query  Avg: 62ms
--> has_child filter with 4096 parent hits query  Avg: 80ms
--> has_child filter with 8192 parent hits query  Avg: 111ms
--> has_child filter with 16384 parent hits query  Avg: 172ms
--> has_child filter with 32768 parent hits query  Avg: 275ms
--> has_child filter with 65536 parent hits query  Avg: 453ms
@mattweber

This comment has been minimized.

Show comment
Hide comment
@mattweber

mattweber Jul 1, 2013

Contributor

Wow this is even better than what I observed in my tests. Very cool.

Contributor

mattweber commented Jul 1, 2013

Wow this is even better than what I observed in my tests. Very cool.

martijnvg added a commit to martijnvg/elasticsearch that referenced this issue Jul 17, 2013

@martijnvg martijnvg closed this in 4d05c9c Jul 18, 2013

@martijnvg

This comment has been minimized.

Show comment
Hide comment
@martijnvg

martijnvg Jul 18, 2013

Member

Thanks @mattweber for bringing this optimisations up!

Member

martijnvg commented Jul 18, 2013

Thanks @mattweber for bringing this optimisations up!

martijnvg added a commit that referenced this issue Jul 18, 2013

Optimize `has_child` query & filter execution with two short circuit …
…mechanisms:

* If all parent ids have been emitted as hit, abort the query / filter execution.
* If the a relative small number of parent ids have been collected in the first phase then limit the number of second phase parent id lookups by putting a short circuit filter before parent document evaluation or omit the it in the case of the filter. This is contrable via the `short_circuit_cutoff` option which is exposed in the `has_child` query & filter.

All parent / child queries and filters (expect `top_children` query) abort execution if no parent ids have been collected in the first phase.

Closes #3190
@kaliseo

This comment has been minimized.

Show comment
Hide comment
@kaliseo

kaliseo Jun 3, 2015

i there,

Very interesting.

Do you have and example of your has_child request ?

Thanks a lot !

kaliseo commented Jun 3, 2015

i there,

Very interesting.

Do you have and example of your has_child request ?

Thanks a lot !

mute pushed a commit to mute/elasticsearch that referenced this issue Jul 29, 2015

Optimize `has_child` query & filter execution with two short circuit …
…mechanisms:

* If all parent ids have been emitted as hit, abort the query / filter execution.
* If the a relative small number of parent ids have been collected in the first phase then limit the number of second phase parent id lookups by putting a short circuit filter before parent document evaluation or omit the it in the case of the filter. This is contrable via the `short_circuit_cutoff` option which is exposed in the `has_child` query & filter.

All parent / child queries and filters (expect `top_children` query) abort execution if no parent ids have been collected in the first phase.

Closes elastic#3190
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment