[REF] models: use `parent_path` to implement parent_store

This replaces the former modified preorder tree traversal (MPTT) with the
fields `parent_left`/`parent_right`.  Each record is associated to a string
`parent_path`, that represents the path from its root node to itself.  The path
is made of the node ids suffixed with a slash:

              a                 node | id | parent_path
             / \                  a  | 42 | 42/
           ...  b                 b  | 63 | 42/63/
               / \                c  | 84 | 42/63/84/
              c   d               d  | 85 | 42/63/85/

This field provides an efficient implementation for parent_of/child_of queries:
the nodes in the subtree of record are the ones where `parent_path` starts with
the `parent_path` of record.  It is also more efficient to maintain than the
MPTT fields, and less sensitive to concurrent updates, because the value of
`parent_path` does not depend on sibling nodes.

14 files changed, 132 insertions, 220 deletions

diff --git a/addons/account/models/account.py b/addons/account/models/account.py
index a5fb776f6f7..3b1a6b7cdf7 100644
--- a/addons/account/models/account.py
+++ b/addons/account/models/account.py
@@ -310,13 +310,11 @@ class AccountAccount(models.Model):
 
 class AccountGroup(models.Model):
     _name = "account.group"
-
     _parent_store = True
     _order = 'code_prefix'
 
     parent_id = fields.Many2one('account.group', index=True, ondelete='cascade')
-    parent_left = fields.Integer('Left Parent', index=True)
-    parent_right = fields.Integer('Right Parent', index=True)
+    parent_path = fields.Char(index=True)
     name = fields.Char(required=True)
     code_prefix = fields.Char()
 
diff --git a/addons/analytic/models/analytic_account.py b/addons/analytic/models/analytic_account.py
index ad6d3b0508f..d1cb5601fd3 100644
--- a/addons/analytic/models/analytic_account.py
+++ b/addons/analytic/models/analytic_account.py
@@ -39,8 +39,7 @@ class AccountAnalyticGroup(models.Model):
     name = fields.Char(required=True)
     description = fields.Text(string='Description')
     parent_id = fields.Many2one('account.analytic.group', string="Parent", ondelete='cascade')
-    parent_left = fields.Integer('Left Parent', index=True)
-    parent_right = fields.Integer('Right Parent', index=True)
+    parent_path = fields.Char(index=True)
     children_ids = fields.One2many('account.analytic.group', 'parent_id', string="Childrens")
     complete_name = fields.Char('Complete Name', compute='_compute_complete_name', store=True)
     company_id = fields.Many2one('res.company', string='Company')
diff --git a/addons/l10n_be_intrastat/models/l10n_be_intrastat.py b/addons/l10n_be_intrastat/models/l10n_be_intrastat.py
index 2506a19e2ce..a06e068f605 100644
--- a/addons/l10n_be_intrastat/models/l10n_be_intrastat.py
+++ b/addons/l10n_be_intrastat/models/l10n_be_intrastat.py
@@ -152,8 +152,6 @@ class StockWarehouse(models.Model):
     region_id = fields.Many2one('l10n_be_intrastat.region', string='Intrastat region')
 
     def get_regionid_from_locationid(self, location):
-        location_ids = location.search([('parent_left', '<=', location.parent_left), ('parent_right', '>=', location.parent_right)])
-        warehouses = self.search([('lot_stock_id', 'in', location_ids.ids), ('region_id', '!=', False)], limit=1)
-        if warehouses:
-            return warehouses.region_id.id
-        return None
+        domain = [('lot_stock_id', 'parent_of', location.ids), ('region_id', '!=', False)]
+        warehouses = self.search(domain, limit=1)
+        return warehouses.region_id.id or None
diff --git a/addons/product/models/product.py b/addons/product/models/product.py
index e9944afe5f7..e921f616a9b 100644
--- a/addons/product/models/product.py
+++ b/addons/product/models/product.py
@@ -17,18 +17,16 @@ class ProductCategory(models.Model):
     _description = "Product Category"
     _parent_name = "parent_id"
     _parent_store = True
-    _parent_order = 'name'
     _rec_name = 'complete_name'
-    _order = 'parent_left'
+    _order = 'complete_name'
 
     name = fields.Char('Name', index=True, required=True, translate=True)
     complete_name = fields.Char(
         'Complete Name', compute='_compute_complete_name',
         store=True)
     parent_id = fields.Many2one('product.category', 'Parent Category', index=True, ondelete='cascade')
+    parent_path = fields.Char(index=True)
     child_id = fields.One2many('product.category', 'parent_id', 'Child Categories')
-    parent_left = fields.Integer('Left Parent', index=1)
-    parent_right = fields.Integer('Right Parent', index=1)
     product_count = fields.Integer(
         '# Products', compute='_compute_product_count',
         help="The number of products under this category (Does not consider the children categories)")
diff --git a/addons/product/models/product_pricelist.py b/addons/product/models/product_pricelist.py
index 7c260b98408..fe47dcbe169 100644
--- a/addons/product/models/product_pricelist.py
+++ b/addons/product/models/product_pricelist.py
@@ -151,7 +151,7 @@ class Pricelist(models.Model):
             'AND (item.pricelist_id = %s) '
             'AND (item.date_start IS NULL OR item.date_start<=%s) '
             'AND (item.date_end IS NULL OR item.date_end>=%s)'
-            'ORDER BY item.applied_on, item.min_quantity desc, categ.parent_left desc',
+            'ORDER BY item.applied_on, item.min_quantity desc, categ.complete_name desc',
             (prod_tmpl_ids, prod_ids, categ_ids, self.id, date, date))
 
         item_ids = [x[0] for x in self._cr.fetchall()]
diff --git a/addons/stock/models/product.py b/addons/stock/models/product.py
index 5e474a5ba01..89284e61147 100644
--- a/addons/stock/models/product.py
+++ b/addons/stock/models/product.py
@@ -195,26 +195,23 @@ class Product(models.Model):
         domain = company_id and ['&', ('company_id', '=', company_id)] or []
         locations = self.env['stock.location'].browse(location_ids)
         # TDE FIXME: should move the support of child_of + auto_join directly in expression
-        # The code has been modified because having one location with parent_left being
-        # 0 make the whole domain unusable
-        hierarchical_locations = locations.filtered(lambda location: location.parent_left != 0 and operator == "child_of")
-        other_locations = locations.filtered(lambda location: location not in hierarchical_locations)  # TDE: set - set ?
+        hierarchical_locations = locations if operator == 'child_of' else locations.browse()
+        other_locations = locations - hierarchical_locations
         loc_domain = []
         dest_loc_domain = []
+        # this optimizes [('location_id', 'child_of', hierarchical_locations.ids)]
+        # by avoiding the ORM to search for children locations and injecting a
+        # lot of location ids into the main query
         for location in hierarchical_locations:
             loc_domain = loc_domain and ['|'] + loc_domain or loc_domain
-            loc_domain += ['&',
-                           ('location_id.parent_left', '>=', location.parent_left),
-                           ('location_id.parent_left', '<', location.parent_right)]
+            loc_domain.append(('location_id.parent_path', '=like', location.parent_path + '%'))
             dest_loc_domain = dest_loc_domain and ['|'] + dest_loc_domain or dest_loc_domain
-            dest_loc_domain += ['&',
-                                ('location_dest_id.parent_left', '>=', location.parent_left),
-                                ('location_dest_id.parent_left', '<', location.parent_right)]
+            dest_loc_domain.append(('location_dest_id.parent_path', '=like', location.parent_path + '%'))
         if other_locations:
             loc_domain = loc_domain and ['|'] + loc_domain or loc_domain
-            loc_domain = loc_domain + [('location_id', operator, [location.id for location in other_locations])]
+            loc_domain = loc_domain + [('location_id', operator, other_locations.ids)]
             dest_loc_domain = dest_loc_domain and ['|'] + dest_loc_domain or dest_loc_domain
-            dest_loc_domain = dest_loc_domain + [('location_dest_id', operator, [location.id for location in other_locations])]
+            dest_loc_domain = dest_loc_domain + [('location_dest_id', operator, other_locations.ids)]
         return (
             domain + loc_domain,
             domain + dest_loc_domain + ['!'] + loc_domain if loc_domain else domain + dest_loc_domain,
diff --git a/addons/stock/models/stock_location.py b/addons/stock/models/stock_location.py
index 05e4bb2b60d..b144f490f14 100644
--- a/addons/stock/models/stock_location.py
+++ b/addons/stock/models/stock_location.py
@@ -14,8 +14,7 @@ class Location(models.Model):
     _description = "Inventory Locations"
     _parent_name = "location_id"
     _parent_store = True
-    _parent_order = 'name'
-    _order = 'parent_left'
+    _order = 'complete_name'
     _rec_name = 'complete_name'
 
     @api.model
@@ -55,8 +54,7 @@ class Location(models.Model):
     posx = fields.Integer('Corridor (X)', default=0, help="Optional localization details, for information purpose only")
     posy = fields.Integer('Shelves (Y)', default=0, help="Optional localization details, for information purpose only")
     posz = fields.Integer('Height (Z)', default=0, help="Optional localization details, for information purpose only")
-    parent_left = fields.Integer('Left Parent', index=True)
-    parent_right = fields.Integer('Right Parent', index=True)
+    parent_path = fields.Char(index=True)
     company_id = fields.Many2one(
         'res.company', 'Company',
         default=lambda self: self.env['res.company']._company_default_get('stock.location'), index=True,
@@ -119,9 +117,8 @@ class Location(models.Model):
     @api.returns('stock.warehouse', lambda value: value.id)
     def get_warehouse(self):
         """ Returns warehouse id of warehouse that contains location """
-        return self.env['stock.warehouse'].search([
-            ('view_location_id.parent_left', '<=', self.parent_left),
-            ('view_location_id.parent_right', '>=', self.parent_left)], limit=1)
+        domain = [('view_location_id', 'parent_of', self.ids)]
+        return self.env['stock.warehouse'].search(domain, limit=1)
 
     def should_bypass_reservation(self):
         self.ensure_one()
diff --git a/addons/website/models/website.py b/addons/website/models/website.py
index a85170aa449..47d9534dc4c 100644
--- a/addons/website/models/website.py
+++ b/addons/website/models/website.py
@@ -791,7 +791,6 @@ class Menu(models.Model):
     _description = "Website Menu"
 
     _parent_store = True
-    _parent_order = 'sequence'
     _order = "sequence, id"
 
     def _default_sequence(self):
@@ -806,8 +805,7 @@ class Menu(models.Model):
     website_id = fields.Many2one('website', 'Website')  # TODO: support multiwebsite once done for ir.ui.views
     parent_id = fields.Many2one('website.menu', 'Parent Menu', index=True, ondelete="cascade")
     child_id = fields.One2many('website.menu', 'parent_id', string='Child Menus')
-    parent_left = fields.Integer('Parent Left', index=True)
-    parent_right = fields.Integer('Parent Right', index=True)
+    parent_path = fields.Char(index=True)
     is_visible = fields.Boolean(compute='_compute_visible', string='Is Visible')
 
     @api.one
diff --git a/addons/website_forum_doc/models/forum_documentation_toc.py b/addons/website_forum_doc/models/forum_documentation_toc.py
index fc167f1ed80..c0d38fc31cd 100644
--- a/addons/website_forum_doc/models/forum_documentation_toc.py
+++ b/addons/website_forum_doc/models/forum_documentation_toc.py
@@ -8,8 +8,7 @@ class Documentation(models.Model):
     _name = 'forum.documentation.toc'
     _description = 'Documentation ToC'
     _inherit = ['website.seo.metadata']
-    _order = "parent_left"
-    _parent_order = "sequence, name"
+    _order = "sequence, name"
     _parent_store = True
 
     sequence = fields.Integer('Sequence')
@@ -17,8 +16,7 @@ class Documentation(models.Model):
     introduction = fields.Html('Introduction', translate=True)
     parent_id = fields.Many2one('forum.documentation.toc', string='Parent Table Of Content', ondelete='cascade')
     child_ids = fields.One2many('forum.documentation.toc', 'parent_id', string='Children Table Of Content')
-    parent_left = fields.Integer(string='Left Parent', index=True)
-    parent_right = fields.Integer(string='Right Parent', index=True)
+    parent_path = fields.Char(index=True)
     post_ids = fields.One2many('forum.post', 'documentation_toc_id', string='Posts')
     forum_id = fields.Many2one('forum.forum', string='Forum', required=True)
 
diff --git a/odoo/addons/base/models/ir_ui_menu.py b/odoo/addons/base/models/ir_ui_menu.py
index a807489f6f3..4c1c7221915 100644
--- a/odoo/addons/base/models/ir_ui_menu.py
+++ b/odoo/addons/base/models/ir_ui_menu.py
@@ -29,8 +29,7 @@ class IrUiMenu(models.Model):
     sequence = fields.Integer(default=10)
     child_id = fields.One2many('ir.ui.menu', 'parent_id', string='Child IDs')
     parent_id = fields.Many2one('ir.ui.menu', string='Parent Menu', index=True, ondelete="restrict")
-    parent_left = fields.Integer(index=True)
-    parent_right = fields.Integer(index=True)
+    parent_path = fields.Char(index=True)
     groups_id = fields.Many2many('res.groups', 'ir_ui_menu_group_rel',
                                  'menu_id', 'gid', string='Groups',
                                  help="If you have groups, the visibility of this menu will be based on these groups. "\
diff --git a/odoo/addons/base/models/res_partner.py b/odoo/addons/base/models/res_partner.py
index f5feedc3f21..4f81b8b6e95 100644
--- a/odoo/addons/base/models/res_partner.py
+++ b/odoo/addons/base/models/res_partner.py
@@ -67,17 +67,15 @@ class FormatAddressMixin(models.AbstractModel):
 class PartnerCategory(models.Model):
     _description = 'Partner Tags'
     _name = 'res.partner.category'
-    _order = 'parent_left, name'
+    _order = 'name'
     _parent_store = True
-    _parent_order = 'name'
 
     name = fields.Char(string='Tag Name', required=True, translate=True)
     color = fields.Integer(string='Color Index')
     parent_id = fields.Many2one('res.partner.category', string='Parent Category', index=True, ondelete='cascade')
     child_ids = fields.One2many('res.partner.category', 'parent_id', string='Child Tags')
     active = fields.Boolean(default=True, help="The active field allows you to hide the category without removing it.")
-    parent_left = fields.Integer(string='Left parent', index=True)
-    parent_right = fields.Integer(string='Right parent', index=True)
+    parent_path = fields.Char(index=True)
     partner_ids = fields.Many2many('res.partner', column1='category_id', column2='partner_id', string='Partners')
 
     @api.constrains('parent_id')
diff --git a/odoo/addons/test_new_api/models.py b/odoo/addons/test_new_api/models.py
index 70e1d1b2d2c..026159bbf00 100644
--- a/odoo/addons/test_new_api/models.py
+++ b/odoo/addons/test_new_api/models.py
@@ -13,13 +13,11 @@ class Category(models.Model):
     _order = 'name'
     _parent_store = True
     _parent_name = 'parent'
-    _parent_order = 'name'
 
     name = fields.Char(required=True)
     color = fields.Integer('Color Index')
     parent = fields.Many2one('test_new_api.category', ondelete='cascade')
-    parent_left = fields.Integer("Left Parent", index=True)
-    parent_right = fields.Integer("Right Parent", index=True)
+    parent_path = fields.Char(index=True)
     root_categ = fields.Many2one(_name, compute='_compute_root_categ')
     display_name = fields.Char(compute='_compute_display_name', inverse='_inverse_display_name')
     dummy = fields.Char(store=False)
diff --git a/odoo/models.py b/odoo/models.py
index 2a00a8297ff..3fa61eb728d 100644
--- a/odoo/models.py
+++ b/odoo/models.py
@@ -239,8 +239,7 @@ class BaseModel(MetaModel('DummyModel', (object,), {'_register': False})):
     _rec_name = None            # field to use for labeling records
     _order = 'id'               # default order for searching results
     _parent_name = 'parent_id'  # the many2one field used as parent field
-    _parent_store = False       # set to True to compute MPTT (parent_left, parent_right)
-    _parent_order = False       # order to use for siblings in MPTT
+    _parent_store = False       # set to True to compute parent_path field
     _date_name = 'date'         # field to use for default calendar view
     _fold_name = 'fold'         # field to determine folded groups in kanban views
 
@@ -2001,31 +2000,41 @@ class BaseModel(MetaModel('DummyModel', (object,), {'_register': False})):
 
     @api.model_cr
     def _parent_store_compute(self):
+        """ Compute parent_path field from scratch. """
         if not self._parent_store:
             return
 
-        _logger.info('Computing parent left and right for table %s...', self._table)
-        cr = self._cr
-        select = "SELECT id FROM %s WHERE %s=%%s ORDER BY %s" % \
-                    (self._table, self._parent_name, self._parent_order)
-        update = "UPDATE %s SET parent_left=%%s, parent_right=%%s WHERE id=%%s" % self._table
-
-        def process(root, left):
-            """ Set root.parent_left to ``left``, and return root.parent_right + 1 """
-            cr.execute(select, (root,))
-            right = left + 1
-            for (id,) in cr.fetchall():
-                right = process(id, right)
-            cr.execute(update, (left, right, root))
-            return right + 1
-
-        select0 = "SELECT id FROM %s WHERE %s IS NULL ORDER BY %s" % \
-                    (self._table, self._parent_name, self._parent_order)
-        cr.execute(select0)
-        pos = 0
-        for (id,) in cr.fetchall():
-            pos = process(id, pos)
-        self.invalidate_cache(['parent_left', 'parent_right'])
+        # Each record is associated to a string 'parent_path', that represents
+        # the path from the record's root node to the record. The path is made
+        # of the node ids suffixed with a slash (see example below). The nodes
+        # in the subtree of record are the ones where 'parent_path' starts with
+        # the 'parent_path' of record.
+        #
+        #               a                 node | id | parent_path
+        #              / \                  a  | 42 | 42/
+        #            ...  b                 b  | 63 | 42/63/
+        #                / \                c  | 84 | 42/63/84/
+        #               c   d               d  | 85 | 42/63/85/
+        #
+        # Note: the final '/' is necessary to match subtrees correctly: '42/63'
+        # is a prefix of '42/630', but '42/63/' is not a prefix of '42/630/'.
+        _logger.info('Computing parent_path for table %s...', self._table)
+        query = """
+            WITH RECURSIVE __parent_store_compute(id, parent_path) AS (
+                SELECT row.id, concat(row.id, '/')
+                FROM {table} row
+                WHERE row.{parent} IS NULL
+            UNION
+                SELECT row.id, concat(comp.parent_path, row.id, '/')
+                FROM {table} row, __parent_store_compute comp
+                WHERE row.{parent} = comp.id
+            )
+            UPDATE {table} row SET parent_path = comp.parent_path
+            FROM __parent_store_compute comp
+            WHERE row.id = comp.id
+        """.format(table=self._table, parent=self._parent_name)
+        self.env.cr.execute(query)
+        self.invalidate_cache(['parent_path'])
         return True
 
     @api.model_cr
@@ -2119,7 +2128,7 @@ class BaseModel(MetaModel('DummyModel', (object,), {'_register': False})):
                 tools.create_model_table(cr, self._table, self._description)
 
             if self._parent_store:
-                if not tools.column_exists(cr, self._table, 'parent_left'):
+                if not tools.column_exists(cr, self._table, 'parent_path'):
                     self._create_parent_columns()
 
             self._check_removed_columns(log=False)
@@ -2158,18 +2167,11 @@ class BaseModel(MetaModel('DummyModel', (object,), {'_register': False})):
 
     @api.model_cr
     def _create_parent_columns(self):
-        tools.create_column(self._cr, self._table, 'parent_left', 'INTEGER')
-        tools.create_column(self._cr, self._table, 'parent_right', 'INTEGER')
-        if 'parent_left' not in self._fields:
-            _logger.error("add a field parent_left on model %s: parent_left = fields.Integer('Left Parent', index=True)", self._name)
-        elif not self._fields['parent_left'].index:
-            _logger.error('parent_left field on model %s must be indexed! Add index=True to the field definition)', self._name)
-        if 'parent_right' not in self._fields:
-            _logger.error("add a field parent_right on model %s: parent_right = fields.Integer('Left Parent', index=True)", self._name)
-        elif not self._fields['parent_right'].index:
-            _logger.error("parent_right field on model %s must be indexed! Add index=True to the field definition)", self._name)
-        if self._fields[self._parent_name].ondelete not in ('cascade', 'restrict'):
-            _logger.error("The field %s on model %s must be set as ondelete='cascade' or 'restrict'", self._parent_name, self._name)
+        tools.create_column(self._cr, self._table, 'parent_path', 'VARCHAR')
+        if 'parent_path' not in self._fields:
+            _logger.error("add a field parent_path on model %s: parent_path = fields.Char(index=True)", self._name)
+        elif not self._fields['parent_path'].index:
+            _logger.error('parent_path field on model %s must be indexed! Add index=True to the field definition)', self._name)
 
     @api.model_cr
     def _add_sql_constraints(self):
@@ -2393,10 +2395,6 @@ class BaseModel(MetaModel('DummyModel', (object,), {'_register': False})):
         elif 'x_name' in cls._fields:
             cls._rec_name = 'x_name'
 
-        # make sure parent_order is set when necessary
-        if cls._parent_store and not cls._parent_order:
-            cls._parent_order = cls._order
-
     @api.model
     def fields_get(self, allfields=None, attributes=None):
         """ fields_get([fields][, attributes])
@@ -2977,7 +2975,7 @@ class BaseModel(MetaModel('DummyModel', (object,), {'_register': False})):
         self._check_concurrency()
         self.check_access_rights('write')
 
-        bad_names = {'id', 'parent_left', 'parent_right'}
+        bad_names = {'id', 'parent_path'}
         if self._log_access:
             bad_names.update(LOG_ACCESS_COLUMNS)
 
@@ -3056,7 +3054,7 @@ class BaseModel(MetaModel('DummyModel', (object,), {'_register': False})):
 
         cr = self._cr
 
-        # determine records that require updating parent_left, parent_right
+        # determine records that require updating parent_path
         parent_records = self._parent_store_update_prepare(vals)
 
         # determine SQL values
@@ -3145,7 +3143,7 @@ class BaseModel(MetaModel('DummyModel', (object,), {'_register': False})):
         # check Python constraints
         self._validate_fields(vals)
 
-        # update parent_left/parent_right
+        # update parent_path
         if parent_records:
             parent_records._parent_store_update(vals)
 
@@ -3178,7 +3176,7 @@ class BaseModel(MetaModel('DummyModel', (object,), {'_register': False})):
         # add missing defaults
         vals = self._add_missing_default_values(vals)
 
-        bad_names = {'id', 'parent_left', 'parent_right'}
+        bad_names = {'id', 'parent_path'}
         if self._log_access:
             bad_names.update(LOG_ACCESS_COLUMNS)
 
@@ -3250,9 +3248,6 @@ class BaseModel(MetaModel('DummyModel', (object,), {'_register': False})):
             if field.type == 'boolean' and field.store:
                 vals.setdefault(name, False)
 
-        # prepare the update of parent_left, parent_right
-        parent_store = self._parent_store_create_prepare(vals)
-
         # determine SQL values
         columns = []                    # list of (column_name, format, value)
         other_fields = []               # list of non-column fields
@@ -3293,9 +3288,8 @@ class BaseModel(MetaModel('DummyModel', (object,), {'_register': False})):
         # from now on, self is the new record
         self = self.browse(cr.fetchone()[0])
 
-        # update parent_left, parent_right
-        if parent_store:
-            self._parent_store_update(vals)
+        # update parent_path
+        self._parent_store_create(vals)
 
         with self.env.protecting(protected_fields, self):
             # mark fields to recompute; do this before setting other fields,
@@ -3332,133 +3326,76 @@ class BaseModel(MetaModel('DummyModel', (object,), {'_register': False})):
 
         return self
 
-    def _parent_store_create_prepare(self, vals):
-        """ Prepare the creation of a record, and return whether its
-            parent_left/parent_right fields must be updated after creation.
-        """
+    def _parent_store_create(self, vals):
+        """ Set the parent_path field on ``self`` after its creation. """
         if not self._parent_store:
-            return False
+            return
 
-        # temporarily put the node at the top-level rightmost position
-        query = "SELECT COALESCE(MAX(parent_right) + 1, 0) FROM {}"
-        self._cr.execute(query.format(self._table))
-        parent_left = self._cr.fetchone()[0]
-        vals.setdefault(self._parent_name, False)
-        vals['parent_left'] = parent_left
-        vals['parent_right'] = parent_left + 1
-        return True
+        parent_val = vals.get(self._parent_name)
+        if parent_val:
+            query = """
+                UPDATE {0}
+                SET parent_path=concat((SELECT parent_path FROM {0} WHERE id=%s), id, '/')
+                WHERE id IN %s
+            """
+            params = [parent_val, tuple(self.ids)]
+        else:
+            query = "UPDATE {} SET parent_path=concat(id, '/') WHERE id IN %s"
+            params = [tuple(self.ids)]
+        self._cr.execute(query.format(self._table), params)
 
     def _parent_store_update_prepare(self, vals):
-        """ Return the records in ``self`` that must update their parent_left,
-            parent_right fields, in their sibling order. This must be called
-            before updating the parent field.
+        """ Return the records in ``self`` that must update their parent_path
+            field. This must be called before updating the parent field.
         """
         if not self._parent_store or self._parent_name not in vals:
             return self.browse()
 
-        # The parent_left/right computation may take up to 5 seconds. No need to
-        # recompute the values if the parent is the same.
-        #
-        # Note: to respect parent_order, nodes must be processed in order, so
-        # the result must be ordered properly.
+        # No need to recompute the values if the parent is the same.
         parent_val = vals[self._parent_name]
         if parent_val:
             query = """ SELECT id FROM {0}
-                        WHERE id IN %s AND ({1} != %s OR {1} IS NULL)
-                        ORDER BY {2} """
+                        WHERE id IN %s AND ({1} != %s OR {1} IS NULL) """
             params = [tuple(self.ids), parent_val]
         else:
             query = """ SELECT id FROM {0}
-                        WHERE id IN %s AND {1} IS NOT NULL
-                        ORDER BY {2} """
+                        WHERE id IN %s AND {1} IS NOT NULL """
             params = [tuple(self.ids)]
-        query = query.format(self._table, self._parent_name, self._parent_order)
+        query = query.format(self._table, self._parent_name)
         self._cr.execute(query, params)
         return self.browse([row[0] for row in self._cr.fetchall()])
 
     def _parent_store_update(self, vals):
-        """ Update the parent_left/parent_right fields of ``self``. """
+        """ Update the parent_path field of ``self``. """
         cr = self.env.cr
+
+        # determine new prefix in parent_path, and check for recursion
         parent_val = vals[self._parent_name]
         if parent_val:
-            clause, params = '{}=%s'.format(self._parent_name), [parent_val]
-        else:
-            clause, params = '{} IS NULL'.format(self._parent_name), []
-
-        modified_ids = set()
-        for record in self:
-            # retrieve record's siblings data (this CANNOT be fetched
-            # outside the loop, as it needs to be refreshed after each
-            # update, in case several nodes are sequentially inserted one
-            # next to the other)
-            query = """ SELECT id, parent_left, parent_right FROM {}
-                        WHERE {} ORDER BY {} """
-            cr.execute(query.format(self._table, clause, self._parent_order), params)
-            siblings = cr.fetchall()
-
-            # determine record's position among its siblings
-            index = next(pos
-                         for pos, data in enumerate(siblings)
-                         if data[0] == record.id)
-
-            # retrieve record's current data
-            pleft0, pright0 = siblings[index][1:]
-            width = pright0 - pleft0 + 1
-
-            # determine new parent_left of current record
-            if index:
-                # record comes right after its closest left sibling
-                pleft1 = (siblings[index - 1][2] or 0) + 1
-            else:
-                # record is the first node of its parent
-                if not parent_val:
-                    pleft1 = 0          # the first node starts at 0
-                else:
-                    query = "SELECT parent_left FROM {} WHERE id=%s"
-                    cr.execute(query.format(self._table), [parent_val])
-                    pleft1 = cr.fetchone()[0] + 1
+            query = "SELECT parent_path FROM {} WHERE id=%s"
+            cr.execute(query.format(self._table), [parent_val])
+            new_prefix = cr.fetchone()[0]
 
-            if pleft0 == pleft1:
-                continue
-
-            if pleft0 < pleft1 <= pright0:
-                raise UserError(_('Recursivity Detected.'))
-
-            # We have to slide values in the interval [x,x+a+b) in order to
-            # swap the subsets in [x,x+a) and [x+a,x+a+b), respectively.
-            #
-            #             x          x+a         x+b        x+a+b
-            #             |-----------|-----------|-----------|
-            #     before: A A A A A A B B B B B B B B B B B B
-            #      after: B B B B B B B B B B B B A A A A A A
-            #
-            query1 = """
-                UPDATE {}
-                SET parent_left = parent_left + (CASE
-                        WHEN parent_left<%(x)s THEN 0
-                        WHEN parent_left<%(x)s+%(a)s THEN %(b)s
-                        WHEN parent_left<%(x)s+%(a)s+%(b)s THEN -%(a)s
-                        ELSE 0 END),
-                    parent_right = parent_right + (CASE
-                        WHEN parent_right<%(x)s THEN 0
-                        WHEN parent_right<%(x)s+%(a)s THEN %(b)s
-                        WHEN parent_right<%(x)s+%(a)s+%(b)s THEN -%(a)s
-                        ELSE 0 END)
-                WHERE (parent_left BETWEEN %(x)s AND %(x)s+%(a)s+%(b)s-1)
-                   OR (parent_right BETWEEN %(x)s AND %(x)s+%(a)s+%(b)s-1)
-                RETURNING id
-            """
-            if pleft0 < pleft1:
-                # x = pleft0, a = width, x+a+b = pleft1
-                params1 = dict(x=pleft0, a=width, b=pleft1 - pleft0 - width)
-            else:
-                # x = pleft1, x+a = pleft0, b = width
-                params1 = dict(x=pleft1, a=pleft0 - pleft1, b=width)
+            parent_ids = {int(label) for label in new_prefix.split('/')[:-1]}
+            if not parent_ids.isdisjoint(self._ids):
+                raise UserError(_("Recursivity Detected."))
 
-            cr.execute(query1.format(self._table), params1)
-            modified_ids.update(row[0] for row in cr.fetchall())
+        else:
+            new_prefix = ''
 
-        self.browse(modified_ids).modified(['parent_left', 'parent_right'])
+        # update parent_path of all records and their descendants
+        query = """
+            UPDATE {0} child
+            SET parent_path = concat(%s, substr(child.parent_path,
+                    length(node.parent_path) - length(node.id || '/') + 1))
+            FROM {0} node
+            WHERE node.id IN %s
+            AND child.parent_path LIKE concat(node.parent_path, '%%')
+            RETURNING child.id
+        """
+        cr.execute(query.format(self._table), [new_prefix, tuple(self.ids)])
+        modified_ids = {row[0] for row in cr.fetchall()}
+        self.browse(modified_ids).modified(['parent_path'])
 
     # TODO: ameliorer avec NULL
     @api.model
@@ -3746,7 +3683,7 @@ class BaseModel(MetaModel('DummyModel', (object,), {'_register': False})):
                 default['state'] = value
 
         # build a black list of fields that should not be copied
-        blacklist = set(MAGIC_COLUMNS + ['parent_left', 'parent_right'])
+        blacklist = set(MAGIC_COLUMNS + ['parent_path'])
         whitelist = set(name for name, field in self._fields.items() if not field.inherited)
 
         def blacklist_given_fields(model):
diff --git a/odoo/osv/expression.py b/odoo/osv/expression.py
index d9719740edb..9e2bb7228e2 100644
--- a/odoo/osv/expression.py
+++ b/odoo/osv/expression.py
@@ -737,18 +737,15 @@ class expression(object):
 
         def child_of_domain(left, ids, left_model, parent=None, prefix=''):
             """ Return a domain implementing the child_of operator for [(left,child_of,ids)],
-                either as a range using the parent_left/right tree lookup fields
+                either as a range using the parent_path tree lookup field
                 (when available), or as an expanded [(left,in,child_ids)] """
             if not ids:
                 return FALSE_DOMAIN
             if left_model._parent_store:
-                # TODO: Improve where joins are implemented for many with '.', replace by:
-                # doms += ['&',(prefix+'.parent_left','<',rec.parent_right),(prefix+'.parent_left','>=',rec.parent_left)]
-                doms = []
-                for rec in left_model.browse(ids):
-                    if doms:
-                        doms.insert(0, OR_OPERATOR)
-                    doms += [AND_OPERATOR, ('parent_left', '<', rec.parent_right), ('parent_left', '>=', rec.parent_left)]
+                doms = OR([
+                    [('parent_path', '=like', rec.parent_path + '%')]
+                    for rec in left_model.browse(ids)
+                ])
                 if prefix:
                     return [(left, 'in', left_model.search(doms).ids)]
                 return doms
@@ -762,17 +759,17 @@ class expression(object):
 
         def parent_of_domain(left, ids, left_model, parent=None, prefix=''):
             """ Return a domain implementing the parent_of operator for [(left,parent_of,ids)],
-                either as a range using the parent_left/right tree lookup fields
+                either as a range using the parent_path tree lookup field
                 (when available), or as an expanded [(left,in,parent_ids)] """
             if left_model._parent_store:
-                doms = []
-                for rec in left_model.browse(ids):
-                    if doms:
-                        doms.insert(0, OR_OPERATOR)
-                    doms += [AND_OPERATOR, ('parent_right', '>', rec.parent_left), ('parent_left', '<=',  rec.parent_left)]
+                parent_ids = [
+                    int(label)
+                    for rec in left_model.browse(ids)
+                    for label in rec.parent_path.split('/')[:-1]
+                ]
                 if prefix:
-                    return [(left, 'in', left_model.search(doms).ids)]
-                return doms
+                    return [(left, 'in', parent_ids)]
+                return [('id', 'in', parent_ids)]
             else:
                 parent_name = parent or left_model._parent_name
                 parent_ids = set()