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 = if model.dataset.recursive_cte_requires_column_aliases?
    113:           # Work around Oracle/ruby-oci8 bug that returns integers as BigDecimals in recursive queries.
    114:           conv_bd = model.db.database_type == :oracle
    115:           col_aliases = model.dataset.columns
    116:           model_table = model.table_name
    117:           col_aliases.map{|c| SQL::QualifiedIdentifier.new(model_table, c)}
    118:         else
    119:           [SQL::ColumnAll.new(model.table_name)]
    120:         end
    121:
    122:         a = opts.merge(opts.fetch(:ancestors, {}))
    123:         ancestors = a.fetch(:name, :ancestors)
    124:         a[:read_only] = true unless a.has_key?(:read_only)
    125:         a[:eager_loader_key] = key
    126:         a[:dataset] ||= proc do
    127:           base_ds = model.filter(prkey=>send(key))
    128:           recursive_ds = model.join(t, key=>prkey)
    129:           if c = a[:conditions]
    130:             (base_ds, recursive_ds) = [base_ds, recursive_ds].collect do |ds|
    131:               (c.is_a?(Array) && !Sequel.condition_specifier?(c)) ? ds.filter(*c) : ds.filter(c)
    132:             end
    133:           end
    134:           table_alias = model.dataset.schema_and_table(model.table_name)[1].to_sym
    135:           model.from(t => table_alias).
    136:            with_recursive(t, col_aliases ? base_ds.select(*col_aliases) : base_ds.select_all,
    137:             recursive_ds.select(*c_all),
    138:             :args=>col_aliases)
    139:         end
    140:         aal = Array(a[:after_load])
    141:         aal << proc do |m, ancs|
    142:           unless m.associations.has_key?(parent)
    143:             parent_map = {m[prkey]=>m}
    144:             child_map = {}
    145:             child_map[m[key]] = m if m[key]
    146:             m.associations[parent] = nil
    147:             ancs.each do |obj|
    148:               obj.associations[parent] = nil
    149:               parent_map[obj[prkey]] = obj
    150:               if ok = obj[key]
    151:                 child_map[ok] = obj
    152:               end
    153:             end
    154:             parent_map.each do |parent_id, obj|
    155:               if child = child_map[parent_id]
    156:                 child.associations[parent] = obj
    157:               end
    158:             end
    159:           end
    160:         end
    161:         a[:after_load] ||= aal
    162:         a[:eager_loader] ||= proc do |eo|
    163:           id_map = eo[:id_map]
    164:           parent_map = {}
    165:           children_map = {}
    166:           eo[:rows].each do |obj|
    167:             parent_map[obj[prkey]] = obj
    168:             (children_map[obj[key]] ||= []) << obj
    169:             obj.associations[ancestors] = []
    170:             obj.associations[parent] = nil
    171:           end
    172:           r = model.association_reflection(ancestors)
    173:           base_case = model.filter(prkey=>id_map.keys).
    174:            select(SQL::AliasedExpression.new(prkey, ka), *c_all)
    175:           recursive_case = model.join(t, key=>prkey).
    176:            select(SQL::QualifiedIdentifier.new(t, ka), *c_all)
    177:           if c = r[:conditions]
    178:             (base_case, recursive_case) = [base_case, recursive_case].collect do |ds|
    179:               (c.is_a?(Array) && !Sequel.condition_specifier?(c)) ? ds.filter(*c) : ds.filter(c)
    180:             end
    181:           end
    182:           table_alias = model.dataset.schema_and_table(model.table_name)[1].to_sym
    183:           elds = model.eager_loading_dataset(r,
    184:            model.from(t => table_alias).
    185:             with_recursive(t, base_case,
    186:              recursive_case,
    187:              :args=>(([ka] + col_aliases) if col_aliases)),
    188:            r.select,
    189:            eo[:associations], eo)
    190:           elds = elds.select_append(ka) unless elds.opts[:select] == nil
    191:           elds.all do |obj|
    192:             opk = obj[prkey]
    193:             if in_pm = parent_map.has_key?(opk)
    194:               if idm_obj = parent_map[opk]
    195:                 idm_obj.values[ka] = obj.values[ka]
    196:                 obj = idm_obj
    197:               end
    198:             else
    199:               obj.associations[parent] = nil
    200:               parent_map[opk] = obj
    201:               (children_map[obj[key]] ||= []) << obj
    202:             end
    203:
    204:             kv = obj.values.delete(ka)
    205:             kv = kv.to_i if conv_bd && kv.is_a?(BigDecimal)
    206:             if roots = id_map[kv]
    207:               roots.each do |root|
    208:                 root.associations[ancestors] << obj
    209:               end
    210:             end
    211:           end
    212:           parent_map.each do |parent_id, obj|
    213:             if children = children_map[parent_id]
    214:               children.each do |child|
    215:                 child.associations[parent] = obj
    216:               end
    217:             end
    218:           end
    219:         end
    220:         model.one_to_many ancestors, a
    221:
    222:         d = opts.merge(opts.fetch(:descendants, {}))
    223:         descendants = d.fetch(:name, :descendants)
    224:         d[:read_only] = true unless d.has_key?(:read_only)
    225:         la = d[:level_alias] ||= :x_level_x
    226:         d[:dataset] ||= proc do
    227:           base_ds = model.filter(key=>send(prkey))
    228:           recursive_ds = model.join(t, prkey=>key)
    229:           if c = d[:conditions]
    230:             (base_ds, recursive_ds) = [base_ds, recursive_ds].collect do |ds|
    231:               (c.is_a?(Array) && !Sequel.condition_specifier?(c)) ? ds.filter(*c) : ds.filter(c)
    232:             end
    233:           end
    234:           table_alias = model.dataset.schema_and_table(model.table_name)[1].to_sym
    235:           model.from(t => table_alias).
    236:            with_recursive(t, col_aliases ? base_ds.select(*col_aliases) : base_ds.select_all,
    237:             recursive_ds.select(*c_all),
    238:             :args=>col_aliases)
    239:           end
    240:         dal = Array(d[:after_load])
    241:         dal << proc do |m, descs|
    242:           unless m.associations.has_key?(childrena)
    243:             parent_map = {m[prkey]=>m}
    244:             children_map = {}
    245:             m.associations[childrena] = []
    246:             descs.each do |obj|
    247:               obj.associations[childrena] = []
    248:               if opk = obj[prkey]
    249:                 parent_map[opk] = obj
    250:               end
    251:               if ok = obj[key]
    252:                 (children_map[ok] ||= []) << obj
    253:               end
    254:             end
    255:             children_map.each do |parent_id, objs|
    256:               parent_map[parent_id].associations[childrena] = objs
    257:             end
    258:           end
    259:         end
    260:         d[:after_load] = dal
    261:         d[:eager_loader] ||= proc do |eo|
    262:           id_map = eo[:id_map]
    263:           associations = eo[:associations]
    264:           parent_map = {}
    265:           children_map = {}
    266:           eo[:rows].each do |obj|
    267:             parent_map[obj[prkey]] = obj
    268:             obj.associations[descendants] = []
    269:             obj.associations[childrena] = []
    270:           end
    271:           r = model.association_reflection(descendants)
    272:           base_case = model.filter(key=>id_map.keys).
    273:            select(SQL::AliasedExpression.new(key, ka), *c_all)
    274:           recursive_case = model.join(t, prkey=>key).
    275:            select(SQL::QualifiedIdentifier.new(t, ka), *c_all)
    276:           if c = r[:conditions]
    277:             (base_case, recursive_case) = [base_case, recursive_case].collect do |ds|
    278:               (c.is_a?(Array) && !Sequel.condition_specifier?(c)) ? ds.filter(*c) : ds.filter(c)
    279:             end
    280:           end
    281:           if associations.is_a?(Integer)
    282:             level = associations
    283:             no_cache_level = level - 1
    284:             associations = {}
    285:             base_case = base_case.select_more(SQL::AliasedExpression.new(0, la))
    286:             recursive_case = recursive_case.select_more(SQL::AliasedExpression.new(SQL::QualifiedIdentifier.new(t, la) + 1, la)).filter(SQL::QualifiedIdentifier.new(t, la) < level - 1)
    287:           end
    288:           table_alias = model.dataset.schema_and_table(model.table_name)[1].to_sym
    289:           elds = model.eager_loading_dataset(r,
    290:            model.from(t => table_alias).with_recursive(t, base_case, recursive_case,
    291:             :args=>(([ka] + col_aliases + (level ? [la] : [])) if col_aliases)),
    292:            r.select,
    293:            associations, eo)
    294:           elds = elds.select_append(ka) unless elds.opts[:select] == nil
    295:           elds.all do |obj|
    296:             if level
    297:               no_cache = no_cache_level == obj.values.delete(la)
    298:             end
    299:
    300:             opk = obj[prkey]
    301:             if in_pm = parent_map.has_key?(opk)
    302:               if idm_obj = parent_map[opk]
    303:                 idm_obj.values[ka] = obj.values[ka]
    304:                 obj = idm_obj
    305:               end
    306:             else
    307:               obj.associations[childrena] = [] unless no_cache
    308:               parent_map[opk] = obj
    309:             end
    310:
    311:             kv = obj.values.delete(ka)
    312:             kv = kv.to_i if conv_bd && kv.is_a?(BigDecimal)
    313:             if root = id_map[kv].first
    314:               root.associations[descendants] << obj
    315:             end
    316:
    317:             (children_map[obj[key]] ||= []) << obj
    318:           end
    319:           children_map.each do |parent_id, objs|
    320:             parent_map[parent_id].associations[childrena] = objs.uniq
    321:           end
    322:         end
    323:         model.one_to_many descendants, d
    324:       end

[Validate]