Uploaded image for project: 'Solr'
  1. Solr
  2. SOLR-9764

Design a memory efficient DocSet if a query returns all docs

    Details

    • Type: Improvement
    • Status: Closed
    • Priority: Major
    • Resolution: Fixed
    • Affects Version/s: None
    • Fix Version/s: 6.5, 7.0
    • Component/s: None
    • Security Level: Public (Default Security Level. Issues are Public)
    • Labels:
      None

      Description

      In some use cases, particularly use cases with time series data, using collection alias and partitioning data into multiple small collections using timestamp, a filter query can match all documents in a collection. Currently BitDocSet is used which contains a large array of long integers with every bits set to 1. After querying, the resulted DocSet saved in filter cache is large and becomes one of the main memory consumers in these use cases.

      For example. suppose a Solr setup has 14 collections for data in last 14 days, each collection with one day of data. A filter query for last one week data would result in at least six DocSet in filter cache which matches all documents in six collections respectively.

      This is to design a new DocSet that is memory efficient for such a use case. The new DocSet removes the large array, reduces memory usage and GC pressure without losing advantage of large filter cache.

      In particular, for use cases when using time series data, collection alias and partition data into multiple small collections using timestamp, the gain can be large.

      For further optimization, it may be helpful to design a DocSet with run length encoding. Thanks Mostafa Mokhtar for suggestion.

      1. SOLR_9764_no_cloneMe.patch
        13 kB
        David Smiley
      2. SOLR-9764.patch
        19 kB
        Yonik Seeley
      3. SOLR-9764.patch
        17 kB
        Yonik Seeley
      4. SOLR-9764.patch
        15 kB
        Michael Sun
      5. SOLR-9764.patch
        12 kB
        Michael Sun
      6. SOLR-9764.patch
        12 kB
        Michael Sun
      7. SOLR-9764.patch
        9 kB
        Michael Sun
      8. SOLR-9764.patch
        9 kB
        Michael Sun
      9. SOLR-9764.patch
        3 kB
        Michael Sun

        Issue Links

          Activity

          Hide
          michael.sun Michael Sun added a comment -

          Upload a prototype. For further optimization, the MatchAllDocSet can also override intersection() etc.

          Show
          michael.sun Michael Sun added a comment - Upload a prototype. For further optimization, the MatchAllDocSet can also override intersection() etc.
          Hide
          markrmiller@gmail.com Mark Miller added a comment -

          Nice Michael, looks interesting.

          Looks like you need to handle intersection overloads to avoid an infinite loop of method call backs?

          Guessing that is due to:

          BitDocSet.java

                // they had better not call us back!
                return other.intersectionSize(this);
          
          Show
          markrmiller@gmail.com Mark Miller added a comment - Nice Michael, looks interesting. Looks like you need to handle intersection overloads to avoid an infinite loop of method call backs? Guessing that is due to: BitDocSet.java // they had better not call us back! return other.intersectionSize( this );
          Hide
          michael.sun Michael Sun added a comment -

          Thanks Mark Miller. Let me fix it.

          Can you also send me the test case or query that you discovered the issue? Thanks.

          Show
          michael.sun Michael Sun added a comment - Thanks Mark Miller . Let me fix it. Can you also send me the test case or query that you discovered the issue? Thanks.
          Hide
          michael.sun Michael Sun added a comment -

          Upload a patch with more overload methods and tests.

          There is still some room for optimization. There are some clever shortcuts in DocSet subclasses, probably for performance reason. Need to take advantage of it.

          Show
          michael.sun Michael Sun added a comment - Upload a patch with more overload methods and tests. There is still some room for optimization. There are some clever shortcuts in DocSet subclasses, probably for performance reason. Need to take advantage of it.
          Hide
          elyograg Shawn Heisey added a comment -

          I looked at the patch, and I find that I don't understand anything that I'm looking at, except that the bigger newer patch looks like it might be a reverse patch that removes all the new changes.

          An orthogonal idea: One thing I've wondered about is whether filter results might sometimes benefit from one of the most simple compression techniques there is – run-length encoding. There are obviously some cases where it would really suck, such as a filter where every other Lucene document matches, but I suspect that in many circumstances it would produce something much smaller than a simple bitset. On the time series data that was mentioned in the description, a timestamp filter would probably benefit greatly.

          Show
          elyograg Shawn Heisey added a comment - I looked at the patch, and I find that I don't understand anything that I'm looking at, except that the bigger newer patch looks like it might be a reverse patch that removes all the new changes. An orthogonal idea: One thing I've wondered about is whether filter results might sometimes benefit from one of the most simple compression techniques there is – run-length encoding. There are obviously some cases where it would really suck, such as a filter where every other Lucene document matches, but I suspect that in many circumstances it would produce something much smaller than a simple bitset. On the time series data that was mentioned in the description, a timestamp filter would probably benefit greatly.
          Hide
          michael.sun Michael Sun added a comment - - edited

          Shawn Heisey Thanks for reviewing. The patch was wrong. I uploaded an updated one. There was a mistake in git command in patch creation. Apologize for it.

          For run length encoding, it can be a good direction for further memory optimization. Mostafa Mokhtar initially suggested this idea, as mentioned in JIRA description. I am trying to gather some supporting data meanwhile to justify the effort and potential risk. Any help would be great.

          Show
          michael.sun Michael Sun added a comment - - edited Shawn Heisey Thanks for reviewing. The patch was wrong. I uploaded an updated one. There was a mistake in git command in patch creation. Apologize for it. For run length encoding, it can be a good direction for further memory optimization. Mostafa Mokhtar initially suggested this idea, as mentioned in JIRA description. I am trying to gather some supporting data meanwhile to justify the effort and potential risk. Any help would be great.
          Hide
          dsmiley David Smiley added a comment -

          Patch looks good to me. Just eyeing the patch, one thing isn't clear. Why both clone() & cloneMe() methods?

          I suggest not incorporating stuff like RLE into this patch; that feels like incredible scope creep.

          Show
          dsmiley David Smiley added a comment - Patch looks good to me. Just eyeing the patch, one thing isn't clear. Why both clone() & cloneMe() methods? I suggest not incorporating stuff like RLE into this patch; that feels like incredible scope creep.
          Hide
          elyograg Shawn Heisey added a comment -

          I suggest not incorporating stuff like RLE into this patch; that feels like incredible scope creep.

          Good plan. I wasn't suggesting it for this issue, it was merely an idea that's been brewing but hadn't quite surfaced completely. This issue brought it up to more conscious thought.

          Show
          elyograg Shawn Heisey added a comment - I suggest not incorporating stuff like RLE into this patch; that feels like incredible scope creep. Good plan. I wasn't suggesting it for this issue, it was merely an idea that's been brewing but hadn't quite surfaced completely. This issue brought it up to more conscious thought.
          Hide
          markrmiller@gmail.com Mark Miller added a comment -

          Nice patch Michael Sun. What is the issue with intDocSet?

          Show
          markrmiller@gmail.com Mark Miller added a comment - Nice patch Michael Sun . What is the issue with intDocSet?
          Hide
          michael.sun Michael Sun added a comment -

          Thanks David Smiley Mark Miller for reviewing. Here are some of my thoughts.

          Why both clone() & cloneMe() methods?

          What I try to achieve is make clone() public (protected by default). Meanwhile it need to be public at DocSet level which is the main interface used. Unfortunately Java seems not allow this visibility change in interface definition (can change in class). Therefore the current implementation is a small workaround for this problem.

          There are some discussion online for other workarounds. Also another alternative is to override clone() in DocSetBase and convert DocSet to DocSetBase when clone() is used. But I thought the current implementation is easiest to understand. With that said, it's still a workaround. Any suggestion is welcome.

          What is the issue with intDocSet?

          IntDocSet actually works fine. The issue is DocSetBase.equals(), which is marked as for test purposed only. The equals() can't figure out two equal DocSet's are equal sometimes. Some work is need in the DocSetBase.equals() to get this test pass. I would add more details in patch comment for it meanwhile.

          Show
          michael.sun Michael Sun added a comment - Thanks David Smiley Mark Miller for reviewing. Here are some of my thoughts. Why both clone() & cloneMe() methods? What I try to achieve is make clone() public (protected by default). Meanwhile it need to be public at DocSet level which is the main interface used. Unfortunately Java seems not allow this visibility change in interface definition (can change in class). Therefore the current implementation is a small workaround for this problem. There are some discussion online for other workarounds. Also another alternative is to override clone() in DocSetBase and convert DocSet to DocSetBase when clone() is used. But I thought the current implementation is easiest to understand. With that said, it's still a workaround. Any suggestion is welcome. What is the issue with intDocSet? IntDocSet actually works fine. The issue is DocSetBase.equals(), which is marked as for test purposed only. The equals() can't figure out two equal DocSet's are equal sometimes. Some work is need in the DocSetBase.equals() to get this test pass. I would add more details in patch comment for it meanwhile.
          Hide
          dsmiley David Smiley added a comment -

          Simply define clone() as public in DocSet and thus all implementations. Mention in javadoc it's a deep copy (safe to mutate). Implement Cloneable. I did these things locally and had no trouble. I attached the patch; it compiles.

          Show
          dsmiley David Smiley added a comment - Simply define clone() as public in DocSet and thus all implementations. Mention in javadoc it's a deep copy (safe to mutate). Implement Cloneable. I did these things locally and had no trouble. I attached the patch; it compiles.
          Hide
          michael.sun Michael Sun added a comment -

          Cool! Thanks David Smiley, Let me check it out.

          Show
          michael.sun Michael Sun added a comment - Cool! Thanks David Smiley , Let me check it out.
          Hide
          michael.sun Michael Sun added a comment - - edited

          Here are some single user test results for the amount of memory saved.

          Setup: Solr with a collection alias mapping to two collections, each with 4 days of data.
          Test: Restart Solr, run query with filter for last 7 days and collect memory histogram on one server afterwards. The filter hits both collections, with one match all and the other match partially.
          Result (extracted from histogram)

          Patched #BitDocSet instances #MatchAllDocSet instances bytes for [J Mem Saving
          Y 1 1 9998408496 3.4M
          N 2 0 10001843704  
          Y 2 2 10001833664 6.9M or 3.4M per hit
          N 4 0 10008701640  

          Analysis:
          The difference of bytes for long[] is 3435208 bytes(3.4M) if one MatchAllDocSet is hit.. That's the total amount of memory saved by this patch for one query per server per matched collection. The the other side, The core under study has 27M documents. A BitDocSet would require a long[] at the size of 3.4M (27M/8) without patch, which is aligned with the memory saved.

          Show
          michael.sun Michael Sun added a comment - - edited Here are some single user test results for the amount of memory saved. Setup: Solr with a collection alias mapping to two collections, each with 4 days of data. Test: Restart Solr, run query with filter for last 7 days and collect memory histogram on one server afterwards. The filter hits both collections, with one match all and the other match partially. Result (extracted from histogram) Patched #BitDocSet instances #MatchAllDocSet instances bytes for [J Mem Saving Y 1 1 9998408496 3.4M N 2 0 10001843704   Y 2 2 10001833664 6.9M or 3.4M per hit N 4 0 10008701640   Analysis: The difference of bytes for long[] is 3435208 bytes(3.4M) if one MatchAllDocSet is hit.. That's the total amount of memory saved by this patch for one query per server per matched collection. The the other side, The core under study has 27M documents. A BitDocSet would require a long[] at the size of 3.4M (27M/8) without patch, which is aligned with the memory saved.
          Hide
          michael.sun Michael Sun added a comment - - edited

          Ah, I see. The implementation of clone() in DocSetBase makes the difference. It's good to know. Thanks David Smiley for help.

          Uploaded an updated patch with cloneMe() removed, using David Smiley's code as example. The DocSetBase.clone() is simplified though.

          Just curious, what logic in JVM requires clone() to be implemented in DocSetBase in this case. DocSetBase is an abstract class which normally is not required to implement a method.

          Show
          michael.sun Michael Sun added a comment - - edited Ah, I see. The implementation of clone() in DocSetBase makes the difference. It's good to know. Thanks David Smiley for help. Uploaded an updated patch with cloneMe() removed, using David Smiley 's code as example. The DocSetBase.clone() is simplified though. Just curious, what logic in JVM requires clone() to be implemented in DocSetBase in this case. DocSetBase is an abstract class which normally is not required to implement a method.
          Hide
          dsmiley David Smiley added a comment -

          Just curious, what logic in JVM requires clone() to be implemented in DocSetBase in this case. DocSetBase is an abstract class which normally is not required to implement a method.

          I suspect it's because DocSetBase actually does implement clone() – albeit indirectly via Object. But Object's definition is incompatible with the DocSet interface in three ways: visibility & throws & co-variant return

          Show
          dsmiley David Smiley added a comment - Just curious, what logic in JVM requires clone() to be implemented in DocSetBase in this case. DocSetBase is an abstract class which normally is not required to implement a method. I suspect it's because DocSetBase actually does implement clone() – albeit indirectly via Object. But Object's definition is incompatible with the DocSet interface in three ways: visibility & throws & co-variant return
          Hide
          michael.sun Michael Sun added a comment -

          Yeah. Make sense. Now I can understand the error message when building without clone() implementation in DocSetBase, " attempting to assign weaker access privileges; was public". As you said, Javac probably consider clone() is implemented in DocSetBase as a protected method.

          That's a good discussion. Your help is appreciated.

          Show
          michael.sun Michael Sun added a comment - Yeah. Make sense. Now I can understand the error message when building without clone() implementation in DocSetBase, " attempting to assign weaker access privileges; was public". As you said, Javac probably consider clone() is implemented in DocSetBase as a protected method. That's a good discussion. Your help is appreciated.
          Hide
          michael.sun Michael Sun added a comment - - edited

          Uploaded a new patch with all tests passed.

          What is the issue with intDocSet?

          Basic in DocSetBase.equals(), both DocSet are converted to FixedBitSet and then both FixedBitSet are compared. However, both DocSet may go through different code path and resize differently in conversion even these two DocSet are equal. The result is that one FixedBitSet has more zero paddings than the other which makes FixedBitSet.equals() think they are different.

          The fix is to resize both FixedBitSet to the same larger size before comparison in DocSetBase.equals(). Since DocSetBase.equals() is marked for test purpose only, the efficiency of the extra sizing would not be a problem.

          Show
          michael.sun Michael Sun added a comment - - edited Uploaded a new patch with all tests passed. What is the issue with intDocSet? Basic in DocSetBase.equals(), both DocSet are converted to FixedBitSet and then both FixedBitSet are compared. However, both DocSet may go through different code path and resize differently in conversion even these two DocSet are equal. The result is that one FixedBitSet has more zero paddings than the other which makes FixedBitSet.equals() think they are different. The fix is to resize both FixedBitSet to the same larger size before comparison in DocSetBase.equals(). Since DocSetBase.equals() is marked for test purpose only, the efficiency of the extra sizing would not be a problem.
          Hide
          elyograg Shawn Heisey added a comment -

          Something just mentioned for memory efficiency on the mailing list was a roaring bitmap. Lucene does have this implemented already – RoaringDocIdSet. I do not know how it would perform when actually used as a filterCache entry, compared to the current bitset implementation.

          Show
          elyograg Shawn Heisey added a comment - Something just mentioned for memory efficiency on the mailing list was a roaring bitmap. Lucene does have this implemented already – RoaringDocIdSet. I do not know how it would perform when actually used as a filterCache entry, compared to the current bitset implementation.
          Hide
          ddorian43 Dorian added a comment -

          Elasticsearch uses it for filter caching. Some comparisons here: https://www.elastic.co/blog/frame-of-reference-and-roaring-bitmaps

          Show
          ddorian43 Dorian added a comment - Elasticsearch uses it for filter caching. Some comparisons here: https://www.elastic.co/blog/frame-of-reference-and-roaring-bitmaps
          Hide
          michael.sun Michael Sun added a comment -

          Lucene does have this implemented already – RoaringDocIdSet

          That's cool. Let me check it out to understand pros and cons. Thanks Shawn Heisey to point it out.

          I do not know how it would perform when actually used as a filterCache entry, compared to the current bitset implementation.

          For this particular use case (a query matches all docs), the approach in patch should be better than roaring bitmap. The patch designed a MatchAllDocSet for this use case, which uses no memory other than storing the size. In addition, MatchAllDocSet would be faster in creating DocSet, union, intersect etc. since no real bit manipulation is required.

          Show
          michael.sun Michael Sun added a comment - Lucene does have this implemented already – RoaringDocIdSet That's cool. Let me check it out to understand pros and cons. Thanks Shawn Heisey to point it out. I do not know how it would perform when actually used as a filterCache entry, compared to the current bitset implementation. For this particular use case (a query matches all docs), the approach in patch should be better than roaring bitmap. The patch designed a MatchAllDocSet for this use case, which uses no memory other than storing the size. In addition, MatchAllDocSet would be faster in creating DocSet, union, intersect etc. since no real bit manipulation is required.
          Hide
          yseeley@gmail.com Yonik Seeley added a comment -

          Since Solr DocSets don't currently match deleted documents, even a single deletion in the index would circumvent this optimization.

          Also, note that "all non-deleted docs" is a special case that is cached if requested... see SolrIndexSearcher.getLiveDocs() (this is used in a few places).
          So another optimization (inspired by Michael's insight into the size==maxDoc case) would be: if the DocSet just produced has size==numDocs, then just use liveDocs. This would have the effect of making all queries that map onto all documents share the resulting DocSet (as well as working when there were deleted docs in the index).

          Whether it's worth trying to compress that single set (and the best way to do it) is an independent decision.

          Show
          yseeley@gmail.com Yonik Seeley added a comment - Since Solr DocSets don't currently match deleted documents, even a single deletion in the index would circumvent this optimization. Also, note that "all non-deleted docs" is a special case that is cached if requested... see SolrIndexSearcher.getLiveDocs() (this is used in a few places). So another optimization (inspired by Michael's insight into the size==maxDoc case) would be: if the DocSet just produced has size==numDocs, then just use liveDocs. This would have the effect of making all queries that map onto all documents share the resulting DocSet (as well as working when there were deleted docs in the index). Whether it's worth trying to compress that single set (and the best way to do it) is an independent decision.
          Hide
          michael.sun Michael Sun added a comment -

          This would have the effect of making all queries that map onto all documents share the resulting DocSet

          Ah, I see. That's a good idea. Let me check it out. Thanks Yonik Seeley for suggestion.

          Show
          michael.sun Michael Sun added a comment - This would have the effect of making all queries that map onto all documents share the resulting DocSet Ah, I see. That's a good idea. Let me check it out. Thanks Yonik Seeley for suggestion.
          Hide
          michael.sun Michael Sun added a comment - - edited

          I do not know how it would perform when actually used as a filterCache entry, compared to the current bitset implementation.

          RoaringDocIdSet looks pretty interesting. From the link in comments, https://www.elastic.co/blog/frame-of-reference-and-roaring-bitmaps, however, it looks RoaringDocIdSet doesn't save any memory in case a query match all docs.

          Basically the idea of RoaringDocIdSet is to divide the entire bitmap into multiple chunks. For each chunk, either a bitmap or a integer array (using diff compression) can be used depending on number of matched docs in that chunk. If matched doc is higher than a certain number in a chunk, a bitmap is used for that chunk. Otherwise integer array is used. It can help in some use cases but it would fall back to something equivalent to FixedBitMap in this use case.

          In addition, the 'official' website for roaring bitmaps http://roaringbitmap.org mentioned roaring bitmaps can also use run length encoding to store the bitmap chunk but also mentioned one of the main goals of roaring bitmap is to solve the problem of run length encoding, which is expensive random access. Need to dig into source code to understand it better. Any suggestion is welcome.

          Show
          michael.sun Michael Sun added a comment - - edited I do not know how it would perform when actually used as a filterCache entry, compared to the current bitset implementation. RoaringDocIdSet looks pretty interesting. From the link in comments, https://www.elastic.co/blog/frame-of-reference-and-roaring-bitmaps , however, it looks RoaringDocIdSet doesn't save any memory in case a query match all docs. Basically the idea of RoaringDocIdSet is to divide the entire bitmap into multiple chunks. For each chunk, either a bitmap or a integer array (using diff compression) can be used depending on number of matched docs in that chunk. If matched doc is higher than a certain number in a chunk, a bitmap is used for that chunk. Otherwise integer array is used. It can help in some use cases but it would fall back to something equivalent to FixedBitMap in this use case. In addition, the 'official' website for roaring bitmaps http://roaringbitmap.org mentioned roaring bitmaps can also use run length encoding to store the bitmap chunk but also mentioned one of the main goals of roaring bitmap is to solve the problem of run length encoding, which is expensive random access. Need to dig into source code to understand it better. Any suggestion is welcome.
          Hide
          elyograg Shawn Heisey added a comment - - edited

          How much of a performance speedup (forgetting for a moment about memory savings) are we talking about for the "match all docs" enhancement? For my environment, it would only apply to manual queries and the load balancer ping requests (every five seconds), but NOT to queries made by users. The ping handler does a distributed query using q=*:* with no filters and rows=1. If the speedup is significant, then my load balancer health checks might get faster, which would be a good thing.

          Show
          elyograg Shawn Heisey added a comment - - edited How much of a performance speedup (forgetting for a moment about memory savings) are we talking about for the "match all docs" enhancement? For my environment, it would only apply to manual queries and the load balancer ping requests (every five seconds), but NOT to queries made by users. The ping handler does a distributed query using q=*:* with no filters and rows=1. If the speedup is significant, then my load balancer health checks might get faster, which would be a good thing.
          Hide
          elyograg Shawn Heisey added a comment -

          It's worth noting that the ping queries are already VERY fast.

          Show
          elyograg Shawn Heisey added a comment - It's worth noting that the ping queries are already VERY fast.
          Hide
          varunthacker Varun Thacker added a comment -

          Hi Michael,

          I was reading through the blog and the lucene implementation "inverses its encoding when the set becomes very dense" . It's also documented in the Javadocs : https://lucene.apache.org/core/6_3_0/core/org/apache/lucene/util/RoaringDocIdSet.html

          Do you think this will be good enough for this case?

          Show
          varunthacker Varun Thacker added a comment - Hi Michael, I was reading through the blog and the lucene implementation "inverses its encoding when the set becomes very dense" . It's also documented in the Javadocs : https://lucene.apache.org/core/6_3_0/core/org/apache/lucene/util/RoaringDocIdSet.html Do you think this will be good enough for this case?
          Hide
          michael.sun Michael Sun added a comment - - edited

          if the DocSet just produced has size==numDocs, then just use liveDocs

          Yonik Seeley Can you give me some more details how to implement this check. Somehow I can't find a clean way to do it. Thanks.

          Show
          michael.sun Michael Sun added a comment - - edited if the DocSet just produced has size==numDocs, then just use liveDocs Yonik Seeley Can you give me some more details how to implement this check. Somehow I can't find a clean way to do it. Thanks.
          Hide
          michael.sun Michael Sun added a comment -

          Ah, yes, you are right. Thanks Varun Thacker for suggestion. The 'inverse encoding' is a good idea.

          Do you think this will be good enough for this case

          On memory saving side, RoaringIdDocSet looks a good solution. It would only use a small amount of memory in this use case.

          On the other hand, there are some implication on CPU usage, mainly in constructing the DocSet. RoaringIdDocSet saves memory by choosing different data structure based on matched documents in a chunk. However, the code doesn't know what data structure to use before it iterate all documents in a chunk and can result in some expensive 'shift' in data structure and 'resizing'. For example, in this use case, for each chunk, the code basically starts fill a large short[], then shift it to a bitmap, and convert data from short[] to bitmap, then fill bitmap, then later switch back to a small short[]. All these steps can be expensive unless it's optimized for some use cases. In addition, all these steps use iterator to get matched doc one by one.

          The union and intersection using RoaringIdDocSet can be more expensive too in addition the cost of constructing. Of course, it's hard to fully understand the performance implication without testing on a prototype. Any suggestion is welcome.

          Show
          michael.sun Michael Sun added a comment - Ah, yes, you are right. Thanks Varun Thacker for suggestion. The 'inverse encoding' is a good idea. Do you think this will be good enough for this case On memory saving side, RoaringIdDocSet looks a good solution. It would only use a small amount of memory in this use case. On the other hand, there are some implication on CPU usage, mainly in constructing the DocSet. RoaringIdDocSet saves memory by choosing different data structure based on matched documents in a chunk. However, the code doesn't know what data structure to use before it iterate all documents in a chunk and can result in some expensive 'shift' in data structure and 'resizing'. For example, in this use case, for each chunk, the code basically starts fill a large short[], then shift it to a bitmap, and convert data from short[] to bitmap, then fill bitmap, then later switch back to a small short[]. All these steps can be expensive unless it's optimized for some use cases. In addition, all these steps use iterator to get matched doc one by one. The union and intersection using RoaringIdDocSet can be more expensive too in addition the cost of constructing. Of course, it's hard to fully understand the performance implication without testing on a prototype. Any suggestion is welcome.
          Hide
          michael.sun Michael Sun added a comment -

          Inspired by all nice discussions, another good optimization would be to store an inverse of the matched docSet if all or most of docs are matched by a query. If the number of docs matched is close to maxDocs, a HashDocSet would be very efficient. (Thanks Yonik Seeley for suggestion.)

          Show
          michael.sun Michael Sun added a comment - Inspired by all nice discussions, another good optimization would be to store an inverse of the matched docSet if all or most of docs are matched by a query. If the number of docs matched is close to maxDocs, a HashDocSet would be very efficient. (Thanks Yonik Seeley for suggestion.)
          Hide
          michael.sun Michael Sun added a comment -

          hmmm, I think query with q=: doesn't use MatchAllDocSets with the current patch. Let me see if there is a way to optimize this use case as well.

          Show
          michael.sun Michael Sun added a comment - hmmm, I think query with q= : doesn't use MatchAllDocSets with the current patch. Let me see if there is a way to optimize this use case as well.
          Hide
          michael.sun Michael Sun added a comment -

          Uploaded an updated patch. In this patch, if a query matches all docs, MatchAllDocSet is used if there is no deleted docs in collection or LiveDocs if there is deleted docs. Thanks Yonik Seeley for suggestion.

          Show
          michael.sun Michael Sun added a comment - Uploaded an updated patch. In this patch, if a query matches all docs, MatchAllDocSet is used if there is no deleted docs in collection or LiveDocs if there is deleted docs. Thanks Yonik Seeley for suggestion.
          Hide
          michael.sun Michael Sun added a comment -

          Other than the patch, there are some good ideas for memory optimization, such as:

          1. run length encoding.
          2. RoaringBitSet
          3. Inverse DocSet

          Each of them has advantages as well as constraints and limitations. We can open separate JIRAs for each to evaluate these solutions and optimize as need.

          Show
          michael.sun Michael Sun added a comment - Other than the patch, there are some good ideas for memory optimization, such as: 1. run length encoding. 2. RoaringBitSet 3. Inverse DocSet Each of them has advantages as well as constraints and limitations. We can open separate JIRAs for each to evaluate these solutions and optimize as need.
          Hide
          yseeley@gmail.com Yonik Seeley added a comment -

          tldr; the attached patch should make all queries that end up matching all documents use the same DocSet instead of caching different sets.

          Notes on changes from the previous patch:

          • I'm not sure what version this patch was made for, but it won't compile on either trunk or 6x.
            [javac] /opt/code/lusolr/trunk/solr/core/src/java/org/apache/solr/query/SolrRangeQuery.java:157: error: incompatible types: DocSet cannot be converted to BitDocSet
            [javac]     BitDocSet liveDocs = searcher.getLiveDocs();
            
          • Some code currently explicitly relies on BitDocSet from liveDocs (hence the compilation error above)
          • hopefully the following change is just an optimization, and not meant to ensure that the same amount of 0 padding is used for each bitset?
            it's buggy in the general case (size is cardinality, not capacity)
               protected FixedBitSet getBits() {
            -    FixedBitSet bits = new FixedBitSet(64);
            +    FixedBitSet bits = new FixedBitSet(size());
            
          • if MatchAllDocs is used as a lucene filter, it can cause a lot of unnessesary memory use... in fact it would end up creating a new bit set
            for each use. This is one instance of a more generic problem... the BaseDocSet implementations are often very inefficient and should be
            overridden by any DocSet meant for use in any common case. Much of the code was also written for best performance with the knowledge that
            there were only 2 common sets (small and large)... that code will need to be revisited / re-reviewed when adding a 3rd into the mix.
          • Given the current problems with MatchAllDocs, I've backed out that part of the patch for now.
            As detailed above, this is more a problem of the fragility of the current code base than with your class.
            It's probably best handled in a separate issue, and perhaps in a more general way that can handle more cases (like most docs matching or segments with deleted docs),
            or if the robustness of the DocSet hierarchy can be improved, we could even add multiple new implementations (Roaring, MatchMost, MatchAll, etc)
          • The setting of liveDocs was not thread-safe (unsafe object publishing)
          • added size() to DocSetCollector in favor of the more specific isMatchLiveDocs
          • The check for liveDocs was only done in createDocSetGeneric, meaning many instances wouldn't be detected (term query, range query on string,
            non-fq parameters like base queries, etc). I created some DocSetUtil methods to handle these cases and called them
            from most of the appropriate places.
          • just a draft patch, but if people agree, we can add tests for sharing/deduplication of liveDocs (which includes the MatchAllDocs case) and commit.
          Show
          yseeley@gmail.com Yonik Seeley added a comment - tldr; the attached patch should make all queries that end up matching all documents use the same DocSet instead of caching different sets. Notes on changes from the previous patch: I'm not sure what version this patch was made for, but it won't compile on either trunk or 6x. [javac] /opt/code/lusolr/trunk/solr/core/src/java/org/apache/solr/query/SolrRangeQuery.java:157: error: incompatible types: DocSet cannot be converted to BitDocSet [javac] BitDocSet liveDocs = searcher.getLiveDocs(); Some code currently explicitly relies on BitDocSet from liveDocs (hence the compilation error above) hopefully the following change is just an optimization, and not meant to ensure that the same amount of 0 padding is used for each bitset? it's buggy in the general case (size is cardinality, not capacity) protected FixedBitSet getBits() { - FixedBitSet bits = new FixedBitSet(64); + FixedBitSet bits = new FixedBitSet(size()); if MatchAllDocs is used as a lucene filter, it can cause a lot of unnessesary memory use... in fact it would end up creating a new bit set for each use. This is one instance of a more generic problem... the BaseDocSet implementations are often very inefficient and should be overridden by any DocSet meant for use in any common case. Much of the code was also written for best performance with the knowledge that there were only 2 common sets (small and large)... that code will need to be revisited / re-reviewed when adding a 3rd into the mix. Given the current problems with MatchAllDocs, I've backed out that part of the patch for now. As detailed above, this is more a problem of the fragility of the current code base than with your class. It's probably best handled in a separate issue, and perhaps in a more general way that can handle more cases (like most docs matching or segments with deleted docs), or if the robustness of the DocSet hierarchy can be improved, we could even add multiple new implementations (Roaring, MatchMost, MatchAll, etc) The setting of liveDocs was not thread-safe (unsafe object publishing) added size() to DocSetCollector in favor of the more specific isMatchLiveDocs The check for liveDocs was only done in createDocSetGeneric, meaning many instances wouldn't be detected (term query, range query on string, non-fq parameters like base queries, etc). I created some DocSetUtil methods to handle these cases and called them from most of the appropriate places. just a draft patch, but if people agree, we can add tests for sharing/deduplication of liveDocs (which includes the MatchAllDocs case) and commit.
          Hide
          yseeley@gmail.com Yonik Seeley added a comment -

          Here's an updated patch that has tests for the sharing of DocSets that match all documents.

          Show
          yseeley@gmail.com Yonik Seeley added a comment - Here's an updated patch that has tests for the sharing of DocSets that match all documents.
          Hide
          michael.sun Michael Sun added a comment - - edited

          if the robustness of the DocSet hierarchy can be improved, we could even add multiple new implementations (Roaring, MatchMost, MatchAll, etc)

          Thanks for Yonik Seeley for reviewing and improving. I open new JIRAs to evaluate and implement these optimizations.

          SOLR-10057 Evaluate/Design a MatchMost/MatchAll doc set (Use one JIRA since MatchAll can be a special case for MatchMost)
          SOLR-10058 Evaluate/Design a DocSet using Lucene RoaringIdDocSet

          Show
          michael.sun Michael Sun added a comment - - edited if the robustness of the DocSet hierarchy can be improved, we could even add multiple new implementations (Roaring, MatchMost, MatchAll, etc) Thanks for Yonik Seeley for reviewing and improving. I open new JIRAs to evaluate and implement these optimizations. SOLR-10057 Evaluate/Design a MatchMost/MatchAll doc set (Use one JIRA since MatchAll can be a special case for MatchMost) SOLR-10058 Evaluate/Design a DocSet using Lucene RoaringIdDocSet
          Hide
          jira-bot ASF subversion and git services added a comment -

          Commit a43ef8f480c6a32dd77e43d02c2dca2299a05eb3 in lucene-solr's branch refs/heads/master from Yonik Seeley
          [ https://git-wip-us.apache.org/repos/asf?p=lucene-solr.git;h=a43ef8f ]

          SOLR-9764: share liveDocs for any DocSet of size numDocs

          Show
          jira-bot ASF subversion and git services added a comment - Commit a43ef8f480c6a32dd77e43d02c2dca2299a05eb3 in lucene-solr's branch refs/heads/master from Yonik Seeley [ https://git-wip-us.apache.org/repos/asf?p=lucene-solr.git;h=a43ef8f ] SOLR-9764 : share liveDocs for any DocSet of size numDocs
          Hide
          jira-bot ASF subversion and git services added a comment -

          Commit 6a3d7bf37f1b0b6a6ec03ecc20367f8a121ddb81 in lucene-solr's branch refs/heads/branch_6x from Yonik Seeley
          [ https://git-wip-us.apache.org/repos/asf?p=lucene-solr.git;h=6a3d7bf ]

          SOLR-9764: share liveDocs for any DocSet of size numDocs

          Show
          jira-bot ASF subversion and git services added a comment - Commit 6a3d7bf37f1b0b6a6ec03ecc20367f8a121ddb81 in lucene-solr's branch refs/heads/branch_6x from Yonik Seeley [ https://git-wip-us.apache.org/repos/asf?p=lucene-solr.git;h=6a3d7bf ] SOLR-9764 : share liveDocs for any DocSet of size numDocs
          Hide
          yseeley@gmail.com Yonik Seeley added a comment -

          Committed, thanks!

          Show
          yseeley@gmail.com Yonik Seeley added a comment - Committed, thanks!
          Hide
          dsmiley David Smiley added a comment -

          Minor feedback:

          • I think getLiveDocs as implemented here will do a volatile-read twice; it could be improved to do once.
          • It's not obvious that one should use DocSetUtil.getDocSet(docSetCollector, searcher); perhaps instead DocSetCollector.getDocSet should demand an indexSearcher argument? It could even be optional (null) I guess.
          Show
          dsmiley David Smiley added a comment - Minor feedback: I think getLiveDocs as implemented here will do a volatile-read twice; it could be improved to do once. It's not obvious that one should use DocSetUtil.getDocSet(docSetCollector, searcher) ; perhaps instead DocSetCollector.getDocSet should demand an indexSearcher argument? It could even be optional (null) I guess.
          Hide
          jira-bot ASF subversion and git services added a comment -

          Commit 98d1dabcd8c851be507bc374c565a41a829e2c72 in lucene-solr's branch refs/heads/master from Yonik Seeley
          [ https://git-wip-us.apache.org/repos/asf?p=lucene-solr.git;h=98d1dab ]

          SOLR-9764: change getLiveDocs to do a single volatile read

          Show
          jira-bot ASF subversion and git services added a comment - Commit 98d1dabcd8c851be507bc374c565a41a829e2c72 in lucene-solr's branch refs/heads/master from Yonik Seeley [ https://git-wip-us.apache.org/repos/asf?p=lucene-solr.git;h=98d1dab ] SOLR-9764 : change getLiveDocs to do a single volatile read
          Hide
          jira-bot ASF subversion and git services added a comment -

          Commit 64b1d24819371a4e51fb525a4564905b155f41f1 in lucene-solr's branch refs/heads/branch_6x from Yonik Seeley
          [ https://git-wip-us.apache.org/repos/asf?p=lucene-solr.git;h=64b1d24 ]

          SOLR-9764: change getLiveDocs to do a single volatile read

          Show
          jira-bot ASF subversion and git services added a comment - Commit 64b1d24819371a4e51fb525a4564905b155f41f1 in lucene-solr's branch refs/heads/branch_6x from Yonik Seeley [ https://git-wip-us.apache.org/repos/asf?p=lucene-solr.git;h=64b1d24 ] SOLR-9764 : change getLiveDocs to do a single volatile read
          Hide
          yseeley@gmail.com Yonik Seeley added a comment -

          I think getLiveDocs as implemented here will do a volatile-read twice; it could be improved to do once.

          Done.

          It's not obvious that one should use DocSetUtil.getDocSet(docSetCollector, searcher); perhaps instead DocSetCollector.getDocSet should demand an indexSearcher argument? It could even be optional (null) I guess.

          I could go either way on this one... I'll leave it to you to change if you like.

          Show
          yseeley@gmail.com Yonik Seeley added a comment - I think getLiveDocs as implemented here will do a volatile-read twice; it could be improved to do once. Done. It's not obvious that one should use DocSetUtil.getDocSet(docSetCollector, searcher); perhaps instead DocSetCollector.getDocSet should demand an indexSearcher argument? It could even be optional (null) I guess. I could go either way on this one... I'll leave it to you to change if you like.
          Hide
          varunthacker Varun Thacker added a comment -

          I tried running a small benchmark to see how much memory does this save:

          Indexed 10M documents and started solr with 4G of heap. Then on this static index I fired 10k queries

          {!cache=false}*:*

          Freed memory was calculated by firing 10k queries then forcing a GC and reading the freed memory in GC viewer.

          Freed Memory:
          Trunk with this patch: 1301MB
          Solr 6.3 : 1290MB

          A FixedBitSet of 10M entries translates to a long array of size=156250 = 1.2 MB

          The filterCache/queryResultCache didn't have any entries but maybe I'm missing something here. I'll look into the test setup over the next couple of days to see what's wrong

          Show
          varunthacker Varun Thacker added a comment - I tried running a small benchmark to see how much memory does this save: Indexed 10M documents and started solr with 4G of heap. Then on this static index I fired 10k queries {!cache= false }*:* Freed memory was calculated by firing 10k queries then forcing a GC and reading the freed memory in GC viewer. Freed Memory: Trunk with this patch: 1301MB Solr 6.3 : 1290MB A FixedBitSet of 10M entries translates to a long array of size=156250 = 1.2 MB The filterCache/queryResultCache didn't have any entries but maybe I'm missing something here. I'll look into the test setup over the next couple of days to see what's wrong
          Hide
          yseeley@gmail.com Yonik Seeley added a comment -

          The filterCache/queryResultCache didn't have any entries

          The sharing of liveDocs is mostly for the filterCache. It doesn't prevent the building of the set in the first place... it prevents it from being redundantly cached as a separate set.

          Show
          yseeley@gmail.com Yonik Seeley added a comment - The filterCache/queryResultCache didn't have any entries The sharing of liveDocs is mostly for the filterCache. It doesn't prevent the building of the set in the first place... it prevents it from being redundantly cached as a separate set.
          Hide
          steve_rowe Steve Rowe added a comment -

          @yonik: The original commit on this issue included the following CHANGES entry:

          SOLR-9764: All filters that which all documents in the index now share the same memory (DocSet).

          I think that the "which" in that sentence should instead be "match"?

          Show
          steve_rowe Steve Rowe added a comment - @yonik: The original commit on this issue included the following CHANGES entry: SOLR-9764 : All filters that which all documents in the index now share the same memory (DocSet). I think that the "which" in that sentence should instead be "match"?
          Hide
          yseeley@gmail.com Yonik Seeley added a comment -

          Hmmm, yep. I'll fix...

          Show
          yseeley@gmail.com Yonik Seeley added a comment - Hmmm, yep. I'll fix...
          Hide
          jira-bot ASF subversion and git services added a comment -

          Commit 05c17c9a516d8501b2dcce9b5910a3d0b5510bc4 in lucene-solr's branch refs/heads/master from Yonik Seeley
          [ https://git-wip-us.apache.org/repos/asf?p=lucene-solr.git;h=05c17c9 ]

          SOLR-9764: fix CHANGES entry

          Show
          jira-bot ASF subversion and git services added a comment - Commit 05c17c9a516d8501b2dcce9b5910a3d0b5510bc4 in lucene-solr's branch refs/heads/master from Yonik Seeley [ https://git-wip-us.apache.org/repos/asf?p=lucene-solr.git;h=05c17c9 ] SOLR-9764 : fix CHANGES entry
          Hide
          jira-bot ASF subversion and git services added a comment -

          Commit 92e619260cc89b4725c2e5e971fc3cb7bbb339cc in lucene-solr's branch refs/heads/branch_6x from Yonik Seeley
          [ https://git-wip-us.apache.org/repos/asf?p=lucene-solr.git;h=92e6192 ]

          SOLR-9764: fix CHANGES entry

          Show
          jira-bot ASF subversion and git services added a comment - Commit 92e619260cc89b4725c2e5e971fc3cb7bbb339cc in lucene-solr's branch refs/heads/branch_6x from Yonik Seeley [ https://git-wip-us.apache.org/repos/asf?p=lucene-solr.git;h=92e6192 ] SOLR-9764 : fix CHANGES entry
          Hide
          dsmiley David Smiley added a comment -

          I'm looking at this closer again. Comments/Questions:

          • The change in DocSetBase.getBits from '64' vs 'size()' seems odd to me. Wouldn't, say Math.max(64,size()) (or perhaps use a larger number like 1024) make more sense? size() is almost certainly too small; no?
          • Perhaps DocSetCollector.getDocSet should return DocSet.EMPTY? Or perhaps this should be the job of DocSetUtil.getDocSet since it already optimizes to a shared reference for the live docs. That is quite minor though; it's cheap & light-weight.
          • SolrIndexSearcher.getDocSetBits will call getDocSet which will ensure the query gets put into the filter cache. Yet it also upgrades it to a BitDocSet if it isn't and will put it in again, overriding the existing SortedIntSet (like that's what it is). Why? What if it's a match-no-docs? If this is deliberate it deserves a comment; if not then probably a minor perf bug.

          The main thing I'm investigating, however, is how might the filterCache's maxRamMB setting not over-count the shared liveDocs: either count it zero times, one times (both fine possibilities), but definitely not more than once. Without resorting to the cache knowing about live docs (ugh; pretty ugly), I think this requires a MatchAll instance like Michael had since created. The match-all (live docs) can easily be a common cache entry for range faceting on time, especially with time based shards.

          Show
          dsmiley David Smiley added a comment - I'm looking at this closer again. Comments/Questions: The change in DocSetBase.getBits from '64' vs 'size()' seems odd to me. Wouldn't, say Math.max(64,size()) (or perhaps use a larger number like 1024) make more sense? size() is almost certainly too small; no? Perhaps DocSetCollector.getDocSet should return DocSet.EMPTY ? Or perhaps this should be the job of DocSetUtil.getDocSet since it already optimizes to a shared reference for the live docs. That is quite minor though; it's cheap & light-weight. SolrIndexSearcher.getDocSetBits will call getDocSet which will ensure the query gets put into the filter cache. Yet it also upgrades it to a BitDocSet if it isn't and will put it in again, overriding the existing SortedIntSet (like that's what it is). Why? What if it's a match-no-docs? If this is deliberate it deserves a comment; if not then probably a minor perf bug. The main thing I'm investigating, however, is how might the filterCache's maxRamMB setting not over-count the shared liveDocs: either count it zero times, one times (both fine possibilities), but definitely not more than once. Without resorting to the cache knowing about live docs (ugh; pretty ugly), I think this requires a MatchAll instance like Michael had since created. The match-all (live docs) can easily be a common cache entry for range faceting on time, especially with time based shards.

            People

            • Assignee:
              yseeley@gmail.com Yonik Seeley
              Reporter:
              michael.sun Michael Sun
            • Votes:
              0 Vote for this issue
              Watchers:
              9 Start watching this issue

              Dates

              • Created:
                Updated:
                Resolved:

                Development