Module | Sequel::Plugins::RcteTree
In: | lib/sequel/plugins/rcte_tree.rb

# Overview

The rcte_tree plugin deals with tree structured data stored in the database using the adjacency list model (where child rows have a foreign key pointing to the parent rows), using recursive common table expressions to load all ancestors in a single query, all descendants in a single query, and all descendants to a given level (where level 1 is children, level 2 is children and grandchildren etc.) in a single query.

# Background

There are two types of common models for storing tree structured data in an SQL database, the adjacency list model and the nested set model. Before recursive common table expressions (or similar capabilities such as CONNECT BY for Oracle), the nested set model was the only easy way to retrieve all ancestors and descendants in a single query. However, it has significant performance corner cases.

On PostgreSQL 8.4, with a significant number of rows, the nested set model is almost 500 times slower than using a recursive common table expression with the adjacency list model to get all descendants, and almost 24,000 times slower to get all descendants to a given level.

Considering that the nested set model requires more difficult management than the adjacency list model, it‘s almost always better to use the adjacency list model if your database supports common table expressions. See explainextended.com/2009/09/24/adjacency-list-vs-nested-sets-postgresql/ for detailed analysis.

# Usage

The rcte_tree plugin adds four associations to the model: parent, children, ancestors, and descendants. Both the parent and children are fairly standard many_to_one and one_to_many associations, respectively. However, the ancestors and descendants associations are special. Both the ancestors and descendants associations will automatically set the parent and children associations, respectively, for current object and all of the ancestor or descendant objects, whenever they are loaded (either eagerly or lazily). Additionally, the descendants association can take a level argument when called eagerly, which limits the returned objects to only that many levels in the tree (see the Overview).

      Model.plugin :rcte_tree

      # Lazy loading
      model = Model.first
      model.parent
      model.children
      model.ancestors # Populates :parent association for all ancestors
      model.descendants # Populates :children association for all descendants

      # Eager loading - also populates the :parent and children associations
      # for all ancestors and descendants
      Model.filter(:id=>[1, 2]).eager(:ancestors, :descendants).all

      # Eager loading children and grand children
      Model.filter(:id=>[1, 2]).eager(:descendants=>2).all
      # Eager loading children, grand children, and great grand children
      Model.filter(:id=>[1, 2]).eager(:descendants=>3).all

# Options

You can override the options for any specific association by making sure the plugin options contain one of the following keys:

- :parent - hash of options for the parent association
- :children - hash of options for the children association
- :ancestors - hash of options for the ancestors association
- :descendants - hash of options for the descendants association

Note that you can change the name of the above associations by specifying a :name key in the appropriate hash of options above. For example:

      Model.plugin :rcte_tree, :parent=>{:name=>:mother},
       :children=>{:name=>:daughters}, :descendants=>{:name=>:offspring}

Any other keys in the main options hash are treated as options shared by all of the associations. Here‘s a few options that affect the plugin:

- :key - The foreign key in the table that points to the primary key of the parent (default: :parent_id)
- :primary_key - The primary key to use (default: the model‘s primary key)
- :key_alias - The symbol identifier to use for aliasing when eager loading (default: :x_root_x)
- :cte_name - The symbol identifier to use for the common table expression (default: :t)
- :level_alias - The symbol identifier to use when eagerly loading descendants up to a given level (default: :x_level_x)

### Methods

apply

### Public Class methods

apply(model, opts={})

Create the appropriate parent, children, ancestors, and descendants associations for the model.

[Source]

         # File lib/sequel/plugins/rcte_tree.rb, line 95
     95:       def self.apply(model, opts={})
     96:         model.plugin :tree, opts
     97:
     98:         opts = opts.dup
     99:         opts[:class] = model
    100:         opts[:methods_module] = Module.new
    101:         model.send(:include, opts[:methods_module])
    102:
    103:         key = opts[:key] ||= :parent_id
    104:         prkey = opts[:primary_key] ||= model.primary_key
    105:
    106:         parent = opts.merge(opts.fetch(:parent, {})).fetch(:name, :parent)
    107:         childrena = opts.merge(opts.fetch(:children, {})).fetch(:name, :children)
    108:
    109:         ka = opts[:key_alias] ||= :x_root_x
    110:         t = opts[:cte_name] ||= :t
    111:         opts[:reciprocal] = nil
    112:         c_all = SQL::ColumnAll.new(model.table_name)
    113:
    114:         a = opts.merge(opts.fetch(:ancestors, {}))
    115:         ancestors = a.fetch(:name, :ancestors)
    116:         a[:read_only] = true unless a.has_key?(:read_only)
    117:         a[:eager_loader_key] = key
    118:         a[:dataset] ||= proc do
    119:           base_ds = model.filter(prkey=>send(key))
    120:           recursive_ds = model.join(t, key=>prkey)
    121:           if c = a[:conditions]
    122:             (base_ds, recursive_ds) = [base_ds, recursive_ds].collect do |ds|
    123:               (c.is_a?(Array) && !Sequel.condition_specifier?(c)) ? ds.filter(*c) : ds.filter(c)
    124:             end
    125:           end
    126:           table_alias = model.dataset.schema_and_table(model.table_name)[1].to_sym
    127:           model.from(t => table_alias).
    128:            with_recursive(t, base_ds.select_all,
    129:             recursive_ds.
    130:             select(c_all))
    131:         end
    132:         aal = Array(a[:after_load])
    133:         aal << proc do |m, ancs|
    134:           unless m.associations.has_key?(parent)
    135:             parent_map = {m[prkey]=>m}
    136:             child_map = {}
    137:             child_map[m[key]] = m if m[key]
    138:             m.associations[parent] = nil
    139:             ancs.each do |obj|
    140:               obj.associations[parent] = nil
    141:               parent_map[obj[prkey]] = obj
    142:               if ok = obj[key]
    143:                 child_map[ok] = obj
    144:               end
    145:             end
    146:             parent_map.each do |parent_id, obj|
    147:               if child = child_map[parent_id]
    148:                 child.associations[parent] = obj
    149:               end
    150:             end
    151:           end
    152:         end
    153:         a[:after_load] ||= aal
    154:         a[:eager_loader] ||= proc do |eo|
    155:           id_map = eo[:key_hash][key]
    156:           parent_map = {}
    157:           children_map = {}
    158:           eo[:rows].each do |obj|
    159:             parent_map[obj[prkey]] = obj
    160:             (children_map[obj[key]] ||= []) << obj
    161:             obj.associations[ancestors] = []
    162:             obj.associations[parent] = nil
    163:           end
    164:           r = model.association_reflection(ancestors)
    165:           base_case = model.filter(prkey=>id_map.keys).
    166:            select(SQL::AliasedExpression.new(prkey, ka), c_all)
    167:           recursive_case = model.join(t, key=>prkey).
    168:            select(SQL::QualifiedIdentifier.new(t, ka), c_all)
    169:           if c = r[:conditions]
    170:             (base_case, recursive_case) = [base_case, recursive_case].collect do |ds|
    171:               (c.is_a?(Array) && !Sequel.condition_specifier?(c)) ? ds.filter(*c) : ds.filter(c)
    172:             end
    173:           end
    174:           table_alias = model.dataset.schema_and_table(model.table_name)[1].to_sym
    175:           elds = model.eager_loading_dataset(r,
    176:            model.from(t => table_alias).
    177:             with_recursive(t, base_case,
    178:              recursive_case),
    179:            r.select,
    180:            eo[:associations], eo)
    181:           elds = elds.select_append(ka) unless elds.opts[:select] == nil
    182:           elds.all do |obj|
    183:             opk = obj[prkey]
    184:             if in_pm = parent_map.has_key?(opk)
    185:               if idm_obj = parent_map[opk]
    186:                 idm_obj.values[ka] = obj.values[ka]
    187:                 obj = idm_obj
    188:               end
    189:             else
    190:               obj.associations[parent] = nil
    191:               parent_map[opk] = obj
    192:               (children_map[obj[key]] ||= []) << obj
    193:             end
    194:
    195:             if roots = id_map[obj.values.delete(ka)]
    196:               roots.each do |root|
    197:                 root.associations[ancestors] << obj
    198:               end
    199:             end
    200:           end
    201:           parent_map.each do |parent_id, obj|
    202:             if children = children_map[parent_id]
    203:               children.each do |child|
    204:                 child.associations[parent] = obj
    205:               end
    206:             end
    207:           end
    208:         end
    209:         model.one_to_many ancestors, a
    210:
    211:         d = opts.merge(opts.fetch(:descendants, {}))
    212:         descendants = d.fetch(:name, :descendants)
    213:         d[:read_only] = true unless d.has_key?(:read_only)
    214:         la = d[:level_alias] ||= :x_level_x
    215:         d[:dataset] ||= proc do
    216:           base_ds = model.filter(key=>send(prkey))
    217:           recursive_ds = model.join(t, prkey=>key)
    218:           if c = d[:conditions]
    219:             (base_ds, recursive_ds) = [base_ds, recursive_ds].collect do |ds|
    220:               (c.is_a?(Array) && !Sequel.condition_specifier?(c)) ? ds.filter(*c) : ds.filter(c)
    221:             end
    222:           end
    223:           table_alias = model.dataset.schema_and_table(model.table_name)[1].to_sym
    224:           model.from(t => table_alias).
    225:            with_recursive(t, base_ds.select_all,
    226:             recursive_ds.
    227:             select(SQL::ColumnAll.new(model.table_name)))
    228:           end
    229:         dal = Array(d[:after_load])
    230:         dal << proc do |m, descs|
    231:           unless m.associations.has_key?(childrena)
    232:             parent_map = {m[prkey]=>m}
    233:             children_map = {}
    234:             m.associations[childrena] = []
    235:             descs.each do |obj|
    236:               obj.associations[childrena] = []
    237:               if opk = obj[prkey]
    238:                 parent_map[opk] = obj
    239:               end
    240:               if ok = obj[key]
    241:                 (children_map[ok] ||= []) << obj
    242:               end
    243:             end
    244:             children_map.each do |parent_id, objs|
    245:               parent_map[parent_id].associations[childrena] = objs
    246:             end
    247:           end
    248:         end
    249:         d[:after_load] = dal
    250:         d[:eager_loader] ||= proc do |eo|
    251:           id_map = eo[:key_hash][prkey]
    252:           associations = eo[:associations]
    253:           parent_map = {}
    254:           children_map = {}
    255:           eo[:rows].each do |obj|
    256:             parent_map[obj[prkey]] = obj
    257:             obj.associations[descendants] = []
    258:             obj.associations[childrena] = []
    259:           end
    260:           r = model.association_reflection(descendants)
    261:           base_case = model.filter(key=>id_map.keys).
    262:            select(SQL::AliasedExpression.new(key, ka), c_all)
    263:           recursive_case = model.join(t, prkey=>key).
    264:            select(SQL::QualifiedIdentifier.new(t, ka), c_all)
    265:           if c = r[:conditions]
    266:             (base_case, recursive_case) = [base_case, recursive_case].collect do |ds|
    267:               (c.is_a?(Array) && !Sequel.condition_specifier?(c)) ? ds.filter(*c) : ds.filter(c)
    268:             end
    269:           end
    270:           if associations.is_a?(Integer)
    271:             level = associations
    272:             no_cache_level = level - 1
    273:             associations = {}
    274:             base_case = base_case.select_more(SQL::AliasedExpression.new(0, la))
    275:             recursive_case = recursive_case.select_more(SQL::AliasedExpression.new(SQL::QualifiedIdentifier.new(t, la) + 1, la)).filter(SQL::QualifiedIdentifier.new(t, la) < level - 1)
    276:           end
    277:           table_alias = model.dataset.schema_and_table(model.table_name)[1].to_sym
    278:           elds = model.eager_loading_dataset(r,
    279:            model.from(t => table_alias).with_recursive(t, base_case, recursive_case),
    280:            r.select,
    281:            associations, eo)
    282:           elds = elds.select_append(ka) unless elds.opts[:select] == nil
    283:           elds.all do |obj|
    284:             if level
    285:               no_cache = no_cache_level == obj.values.delete(la)
    286:             end
    287:
    288:             opk = obj[prkey]
    289:             if in_pm = parent_map.has_key?(opk)
    290:               if idm_obj = parent_map[opk]
    291:                 idm_obj.values[ka] = obj.values[ka]
    292:                 obj = idm_obj
    293:               end
    294:             else
    295:               obj.associations[childrena] = [] unless no_cache
    296:               parent_map[opk] = obj
    297:             end
    298:
    299:             if root = id_map[obj.values.delete(ka)].first
    300:               root.associations[descendants] << obj
    301:             end
    302:
    303:             (children_map[obj[key]] ||= []) << obj
    304:           end
    305:           children_map.each do |parent_id, objs|
    306:             parent_map[parent_id].associations[childrena] = objs.uniq
    307:           end
    308:         end
    309:         model.one_to_many descendants, d
    310:       end

[Validate]