[FIX] core: compute on batches of maximum PREFETCH_MAX records

Calling a compute method on 1M records inevitably brings a worst case in
cache prefetching: the code that determines which records to fetch has
time complexity O(N²).  We avoid this situation by calling the compute
method on maximum 1K records.  Each computed batch has a "prefetch set"
of maximum 1K records too, which avoids the worst-case scenario above.

closes odoo/odoo#58647

X-original-commit: 0b1aa660b1d94fe46dea09670b875f2d81ca36a3
Signed-off-by: Raphael Collet (rco) <rco@openerp.com>

1 files changed, 18 insertions, 12 deletions

diff --git a/odoo/models.py b/odoo/models.py
index 6c23cad4c00..f82a012f485 100644
--- a/odoo/models.py
+++ b/odoo/models.py
@@ -55,7 +55,7 @@ from .exceptions import AccessError, MissingError, ValidationError, UserError
 from .osv.query import Query
 from .tools import frozendict, lazy_classproperty, ormcache, \
                    Collector, LastOrderedSet, OrderedSet, IterableGenerator, \
-                   groupby, unique
+                   groupby
 from .tools.config import config
 from .tools.func import frame_codeinfo
 from .tools.misc import CountingStream, clean_context, DEFAULT_SERVER_DATETIME_FORMAT, DEFAULT_SERVER_DATE_FORMAT, get_lang
@@ -219,6 +219,19 @@ def origin_ids(ids):
     return ((id_ or id_.origin) for id_ in ids if (id_ or getattr(id_, "origin", None)))
 
 
+def expand_ids(id0, ids):
+    """ Return an iterator of unique ids from the concatenation of ``[id0]`` and
+        ``ids``, and of the same kind (all real or all new).
+    """
+    yield id0
+    seen = {id0}
+    kind = bool(id0)
+    for id_ in ids:
+        if id_ not in seen and bool(id_) == kind:
+            yield id_
+            seen.add(id_)
+
+
 IdType = (int, str, NewId)
 
 
@@ -5619,27 +5632,20 @@ Fields:
         """ Return the cache of ``self``, mapping field names to values. """
         return RecordCache(self)
 
-    @api.model
     def _in_cache_without(self, field, limit=PREFETCH_MAX):
         """ Return records to prefetch that have no value in cache for ``field``
             (:class:`Field` instance), including ``self``.
             Return at most ``limit`` records.
         """
-        # This method returns records that are either all real, or all new.
+        ids = expand_ids(self.id, self._prefetch_ids)
+        ids = self.env.cache.get_missing_ids(self.browse(ids), field)
+        if limit:
+            ids = itertools.islice(ids, limit)
         # Those records are aimed at being either fetched, or computed.  But the
         # method '_fetch_field' is not correct with new records: it considers
         # them as forbidden records, and clears their cache!  On the other hand,
         # compute methods are not invoked with a mix of real and new records for
         # the sake of code simplicity.
-        kind = bool(self.id)
-        recs = self.browse(unique(self._prefetch_ids))
-        ids = [self.id]
-        for record_id in self.env.cache.get_missing_ids(recs - self, field):
-            if bool(record_id) != kind:
-                continue
-            ids.append(record_id)
-            if limit and limit <= len(ids):
-                break
         return self.browse(ids)
 
     @api.model