Solr
  1. Solr
  2. SOLR-3652

Range Faceting will infinite loop if gap is too small relative to lower bounds of range (underflow occurs on add)

    Details

    • Type: Bug Bug
    • Status: Closed
    • Priority: Major Major
    • Resolution: Fixed
    • Affects Version/s: 3.6.1, 4.0-ALPHA
    • Fix Version/s: 4.0-BETA, 6.0
    • Component/s: None
    • Labels:
    • Environment:

      OSX Lion, Macbook Pro, 8GB Ram

      Description

      Executing the following query will lock up the java process running solr.

      facet=true&facet.range=item_search_creation_event_facet_range_ftm&f.item_searchcreation_event_facet_range_ftm.facet.range.start=100000000000.0&f.item_searchcreation_event_facet_range_ftm.facet.range.end=100000086200.0&f.item_search_creation_event_facet_range_ftm.facet.range.gap=2160.0&q=%2A%3A%2A

      But decreasing the size of the min and max works fine

      facet=true&facet.range=item_search_creation_event_facet_range_ftm&f.item_searchcreation_event_facet_range_ftm.facet.range.start=10000000000.0&f.item_searchcreation_event_facet_range_ftm.facet.range.end=10000086200.0&f.item_search_creation_event_facet_range_ftm.facet.range.gap=2160.0&q=%2A%3A%2A

      And so does increasing the range gap

      facet=true&facet.range=item_search_creation_event_facet_range_ftm&f.item_searchcreation_event_facet_range_ftm.facet.range.start=100000000000.0&f.item_searchcreation_event_facet_range_ftm.facet.range.end=100000086200.0&f.item_search_creation_event_facet_range_ftm.facet.range.gap=21600.0&q=%2A%3A%2A

        Activity

        Hide
        Hoss Man added a comment -

        Trivial to reproduce in the example (even with an empty index)

        Works fine...

        These (small gap w/ long and double) work fine...

        This (small gap w/ int) fails fast as expected because the value is too big to parse...

        • this (small gap w/ float) seems to go into an infinite loop...

        http://localhost:8983/solr/select?q=*:*&facet=true&facet.range=foo_f&facet.range.start=100000000000&facet.range.end=100000086200&facet.range.gap=2160

        ...i'm pretty sure the problem is that we aren't checking for float/double underflow and adding the small gap to the large start value is equivilent to adding a gap of "0" (Which is evidently also a problem ... facet.range.gap=0 isn't throwing an exception either)

        Show
        Hoss Man added a comment - Trivial to reproduce in the example (even with an empty index) Works fine... These (small gap w/ long and double) work fine... http://localhost:8983/solr/select?q=*:*&facet=true&facet.range=foo_l&facet.range.start=100000000000&facet.range.end=100000086200&facet.range.gap=2160 http://localhost:8983/solr/select?q=*:*&facet=true&facet.range=foo_d&facet.range.start=100000000000&facet.range.end=100000086200&facet.range.gap=2160 This (small gap w/ int) fails fast as expected because the value is too big to parse... http://localhost:8983/solr/select?q=*:*&facet=true&facet.range=foo_i&facet.range.start=100000000000&facet.range.end=100000086200&facet.range.gap=21600 this (small gap w/ float) seems to go into an infinite loop... http://localhost:8983/solr/select?q=*:*&facet=true&facet.range=foo_f&facet.range.start=100000000000&facet.range.end=100000086200&facet.range.gap=2160 ...i'm pretty sure the problem is that we aren't checking for float/double underflow and adding the small gap to the large start value is equivilent to adding a gap of "0" (Which is evidently also a problem ... facet.range.gap=0 isn't throwing an exception either)
        Hide
        Hoss Man added a comment -

        patch that fixes both facet.date and facet.range to check that the computed "high" value of each range is not equal to the computed "low" value to ensure there is no underflow when adding the gap (there was already a check that "high" was not less then "low" in case of overflow adding the gap)

        patch includes test case - but all it realy does is ensure that if we return, we return an error (no special trickery in the test about interrupt the thread if it takes too long)

        Show
        Hoss Man added a comment - patch that fixes both facet.date and facet.range to check that the computed "high" value of each range is not equal to the computed "low" value to ensure there is no underflow when adding the gap (there was already a check that "high" was not less then "low" in case of overflow adding the gap) patch includes test case - but all it realy does is ensure that if we return, we return an error (no special trickery in the test about interrupt the thread if it takes too long)
        Hide
        Nicholas Jakobsen added a comment -

        Looking at the patch, this seems to just raise an exception with large numbers, not actually support them. Would it be possible to support large ranges? If not, could you suggest a workaround? If I divided all the numbers by a known factor, and then multiplied them in my app, could that tie me over until the behaviour is actually fixed? Or is it a limitation with sig figs, and not the absolute value?

        Show
        Nicholas Jakobsen added a comment - Looking at the patch, this seems to just raise an exception with large numbers, not actually support them. Would it be possible to support large ranges? If not, could you suggest a workaround? If I divided all the numbers by a known factor, and then multiplied them in my app, could that tie me over until the behaviour is actually fixed? Or is it a limitation with sig figs, and not the absolute value?
        Hide
        Hoss Man added a comment -

        Looking at the patch, this seems to just raise an exception with large numbers, not actually support them.

        There isn't actually a problem with "large" numbers – the real problem is actually with "small" numbers – specifically the root cause of the infinite looping was when the "gap" was too small, relative to the the start/end, for the field type in use (float), and became effectively the same as "zero".

        That's what this patch fixes. If adding the gap to the lower bound of a range produces a value that is still equal to the lower bound, it fails rather the going into an infinite loop.

        Would it be possible to support large ranges?

        large ranges can work fine – use a "big" gap and you will never see this problem. what doesn't work is having a range so small that for the field type being used, the lower and upper bounds are equivalent for some values.

        ...could that tie me over until the behaviour is actually fixed? Or is it a limitation with sig figs, and not the absolute value?

        This is really a fundamental limitation based on the underlying data types being used. If you use a "float" field type in Solr, the underlying representation is constrained by the valid values that can be represented by a java Float. likewise for "double" ...

        http://docs.oracle.com/javase/6/docs/api/java/lang/Float.html
        http://docs.oracle.com/javase/6/docs/api/java/lang/Double.html

        ...if your field type is "float" and you ask for something like facet.range.start=100000000000&facet.range.end=100000086200&facet.range.gap=2160} then eventually, as FacetComponent computes the individual ranges, it's going to try and compute a range where the lower bound is "9.9999998E10" – but for float values, "9.9999998E10 + 2160 = 9.9999998E10" and that's where the infinite loop underflow error check will abort the request. There's really nothing else it can do.

        If you try the same request with a "double" field or a "long" field and everything will work fine for this particular example, but a java "float" can't express a difference between "9.9999998E10" and "9.9999998E10 + 2160"

        Show
        Hoss Man added a comment - Looking at the patch, this seems to just raise an exception with large numbers, not actually support them. There isn't actually a problem with "large" numbers – the real problem is actually with "small" numbers – specifically the root cause of the infinite looping was when the "gap" was too small, relative to the the start/end , for the field type in use (float), and became effectively the same as "zero". That's what this patch fixes. If adding the gap to the lower bound of a range produces a value that is still equal to the lower bound, it fails rather the going into an infinite loop. Would it be possible to support large ranges? large ranges can work fine – use a "big" gap and you will never see this problem. what doesn't work is having a range so small that for the field type being used, the lower and upper bounds are equivalent for some values. ...could that tie me over until the behaviour is actually fixed? Or is it a limitation with sig figs, and not the absolute value? This is really a fundamental limitation based on the underlying data types being used. If you use a "float" field type in Solr, the underlying representation is constrained by the valid values that can be represented by a java Float. likewise for "double" ... http://docs.oracle.com/javase/6/docs/api/java/lang/Float.html http://docs.oracle.com/javase/6/docs/api/java/lang/Double.html ...if your field type is "float" and you ask for something like facet.range.start=100000000000&facet.range.end=100000086200&facet.range.gap=2160 } then eventually, as FacetComponent computes the individual ranges, it's going to try and compute a range where the lower bound is "9.9999998E10" – but for float values, "9.9999998E10 + 2160 = 9.9999998E10" and that's where the infinite loop underflow error check will abort the request. There's really nothing else it can do. If you try the same request with a "double" field or a "long" field and everything will work fine for this particular example, but a java "float" can't express a difference between "9.9999998E10" and "9.9999998E10 + 2160"
        Hide
        Hoss Man added a comment -

        Committed revision 1365363. - trunk
        Committed revision 1365365. - 4x

        Show
        Hoss Man added a comment - Committed revision 1365363. - trunk Committed revision 1365365. - 4x
        Hide
        Nicholas Jakobsen added a comment -

        Ah, I see, it's a problem of scale between the range and the gap. I'll try a double instead. The reason for the large numbers is I'm storing UTC times for dates far in the past, e.g. 5000 BCE.

        Thanks for the quick response!

        Show
        Nicholas Jakobsen added a comment - Ah, I see, it's a problem of scale between the range and the gap. I'll try a double instead. The reason for the large numbers is I'm storing UTC times for dates far in the past, e.g. 5000 BCE. Thanks for the quick response!
        Hide
        Hoss Man added a comment -

        Nicholas: If you are working with ancient dates, double doesn't really make sense – i would suggest using a "long" representing whatever precision you care about (year, day, minute, millisecond ... even at millisecond granularity you can go as far back as Dec 02, 292269055 BC)

        FWIW: not many people i've talked to in the past have ever really cared about indexing years prior to 1AD and doing anything meaningful with them, but if you are interested in faceting dates going back that far, and being able to use DateField and DateMath, contributions to SOLR-2773 would certainly be appreciated. (There's already a test demonstrating the problems, we just need someone to help write the code)

        Show
        Hoss Man added a comment - Nicholas: If you are working with ancient dates, double doesn't really make sense – i would suggest using a "long" representing whatever precision you care about (year, day, minute, millisecond ... even at millisecond granularity you can go as far back as Dec 02, 292269055 BC) FWIW: not many people i've talked to in the past have ever really cared about indexing years prior to 1AD and doing anything meaningful with them, but if you are interested in faceting dates going back that far, and being able to use DateField and DateMath, contributions to SOLR-2773 would certainly be appreciated. (There's already a test demonstrating the problems, we just need someone to help write the code)
        Hide
        Nicholas Jakobsen added a comment -

        I have a more generic DSL that I use to specify fields for faceting. For simplicity, all the values from range facets (including dates, datetimes, integers, floats, doubles, etc...) are converted to a float for indexing. This is why I haven't explored other data types.

        As for SOLR-2773, Ha! The amount of time I've spent dealing with BCE to signed-year conversions, gregorian calendars, and far past dates. Jumping into the conversation in SOLR-1899 is a little confusing. Why don't you email me and explain the issue, and I'll see if I can help.

        Show
        Nicholas Jakobsen added a comment - I have a more generic DSL that I use to specify fields for faceting. For simplicity, all the values from range facets (including dates, datetimes, integers, floats, doubles, etc...) are converted to a float for indexing. This is why I haven't explored other data types. As for SOLR-2773 , Ha! The amount of time I've spent dealing with BCE to signed-year conversions, gregorian calendars, and far past dates. Jumping into the conversation in SOLR-1899 is a little confusing. Why don't you email me and explain the issue, and I'll see if I can help.

          People

          • Assignee:
            Hoss Man
            Reporter:
            Nicholas Jakobsen
          • Votes:
            0 Vote for this issue
            Watchers:
            1 Start watching this issue

            Dates

            • Created:
              Updated:
              Resolved:

              Development