title: Postgres Materialized Path - What are the benefits of using ltree?
body: <p>Materialized Path is a method for representing hierarchy in SQL. Each node contains the path itself and all its ancestors (<code>grandparent/parent/self</code>).</p>
  
  <p>The <code>django-treebeard</code> implementation of MP (<a href="https://django-treebeard.readthedocs.io/en/latest/mp_tree.html" rel="noreferrer">docs</a>):</p>
  
  <ol>
  <li><p>Each step of the path is a fixed length for consistent performance.</p></li>
  <li><p>Each node contains <code>depth</code> and <code>numchild</code> fields (fast reads at minimal cost to writes).</p></li>
  <li><p>The path field is indexed (with a standard b-tree index):</p>
  
  <blockquote>
    <p>The materialized path approach makes heavy use of LIKE in your database, with clauses like WHERE path LIKE '002003%'. If you think that LIKE is too slow, you’re right, but in this case the path field is indexed in the database, and all LIKE clauses that don’t start with a % character will use the index. This is what makes the materialized path approach so fast.</p>
  </blockquote></li>
  </ol>
  
  <p>Implementation of <code>get_ancestors</code> (<a href="https://github.com/django-treebeard/django-treebeard/blob/8042ee939cb45394909237da447f8925e3cc6aa3/treebeard/mp_tree.py#L1052" rel="noreferrer">link</a>):</p>
  
  <p>Match nodes with a path that contains a subset of the current path (<code>steplen</code> is the fixed length of a step).</p>
  
  <pre><code>paths = [
      self.path[0:pos]
      for pos in range(0, len(self.path), self.steplen)[1:]
  ]
  return get_result_class(self.__class__).objects.filter(
      path__in=paths).order_by('depth')
  </code></pre>
  
  <p>Implementation of <code>get_descendants</code> (<a href="https://github.com/django-treebeard/django-treebeard/blob/8042ee939cb45394909237da447f8925e3cc6aa3/treebeard/mp_tree.py#L958" rel="noreferrer">link</a>):</p>
  
  <p>Match nodes with a depth greater than self and a path which starts with current path.</p>
  
  <pre><code>return cls.objects.filter(
      path__startswith=parent.path,
      depth__gte=parent.depth
  ).order_by(
      'path'
  )
  </code></pre>
  
  <p>Potential downsides to this approach:</p>
  
  <ol>
  <li>A deeply nested hierarchy will result in long paths, which can hurt read performance.</li>
  <li>Moving a node requires updating the path of all descendants.</li>
  </ol>
  
  <p>Postgres includes the <code>ltree</code> extension which provides a custom <a href="https://en.wikipedia.org/wiki/GiST" rel="noreferrer">GiST</a> index (<a href="https://www.postgresql.org/docs/current/ltree.html" rel="noreferrer">docs</a>).</p>
  
  <p>I am not clear which benefits <code>ltree</code> provides over <code>django-treebeard</code>'s implementation. This <a href="http://patshaughnessy.net/2017/12/15/looking-inside-postgres-at-a-gist-index" rel="noreferrer">article</a> argues that only <code>ltree</code> can answer the <code>get_ancestors</code> question, but as demonstrated earlier, figuring out the ancestors (or descendants) of a node is trivial.</p>
  
  <p>[As an aside, if found this Django <code>ltree</code> library - <a href="https://github.com/mariocesar/django-ltree]" rel="noreferrer">https://github.com/mariocesar/django-ltree]</a>.</p>
  
  <p>Both approaches use an index (<code>django-treebeard</code> uses b-tree, <code>ltree</code> uses a custom GiST). I am interested in understanding the implementation of the <code>ltree</code> GiST and why it might be a more efficient index than a standard b-tree for this particular use case (materialized path).</p>
  
  <p><strong>Additional links</strong></p>
  
  <p><a href="https://stackoverflow.com/questions/4048151/what-are-the-options-for-storing-hierarchical-data-in-a-relational-database">What are the options for storing hierarchical data in a relational database?</a></p>
  
  <p><a href="https://news.ycombinator.com/item?id=709970" rel="noreferrer">https://news.ycombinator.com/item?id=709970</a></p>