Skip to content

Instantly share code, notes, and snippets.

@adamsanderson
Last active January 23, 2024 14:08
Show Gist options
  • Save adamsanderson/5573945 to your computer and use it in GitHub Desktop.
Save adamsanderson/5573945 to your computer and use it in GitHub Desktop.
Demonstration of hierarchical queries in Postgres using a materialized path. It will create a new database that you can later play around with.
source 'https://rubygems.org'
gem 'activerecord', '4.0.0.rc1'
require 'active_record'
# Run the sample hierarchy_with_postgres.sql file first
# psql < hierarchy_with_postgres.sql
#
# Normally you would use a migration, and configure this in database.yml, but
# this is just a little sample.
ActiveRecord::Base.establish_connection :adapter => 'postgresql',
:database => 'hierarchy_with_postgres',
:host => 'localhost'
class Employee < ActiveRecord::Base
def depth
path.length
end
def full_path
path + [id]
end
def parents
Employee.find(path)
end
def children
Employee.where('path && ARRAY[?]', id)
end
def move!(new_parent)
if new_parent.path.include?(id)
throw ArgumentError "Cannot move under a child record"
end
Employee.transaction do
new_path = new_parent.full_path
children.update_all [
'path = ARRAY[:new_path] || path[:depth + 1 : array_length(path,1)]',
new_path: new_path,
depth: depth
]
self.path = new_path
self.save!
end
end
def to_s
"#{name} (#{id})"
end
end
# Sample script to play around with the hierarchy:
if $0 == __FILE__
def display_tree
tree = Employee.order('path || id')
tree.each{|e| puts(" " * e.depth + e.to_s) }
end
def display_employee(id)
employee = Employee.find(id)
depth = employee.depth
parents = employee.parents.join(', ')
children = employee.children.join(', ')
puts "#{employee}"
puts "Depth: #{depth}"
puts "Parents: #{parents}"
puts "Children: #{children}"
end
def move_employee(id, new_parent_id)
employee = Employee.find(id)
parent = Employee.find(new_parent_id)
employee.move!(parent)
display_tree
end
case ARGV.length
when 0 then display_tree
when 1 then display_employee ARGV.shift
when 2 then move_employee ARGV.shift, ARGV.shift
else
puts <<-HELP
ruby #{$0}
Print Tree
ruby #{$0} id
Print Employee `id`
ruby #{$0} id new_parent_id
Move Employee `id` under `new_parent_id`
HELP
exit 1
end
end
DROP DATABASE IF EXISTS hierarchy_with_postgres;
CREATE DATABASE hierarchy_with_postgres;
-- Now use hierarchy_with_postgres
\c hierarchy_with_postgres
CREATE TABLE employees (
id integer primary key,
path integer[],
name text
);
-- id | name
-----------------------------
-- 1 | Harold
-- 2 | Arthur
-- 3 | Alice
-- 4 | Rose
-- 5 | Bob
-- 6 | Sally
-- 7 | Mortimer
-- 8 | Penny
INSERT INTO employees VALUES
(1, ARRAY[1], 'Harold'),
(2, ARRAY[1,2], 'Arthur'),
(3, ARRAY[1,2,3], 'Alice'),
(4, ARRAY[1,2,3,4], 'Rose'),
(5, ARRAY[1,2,5], 'Bob'),
(6, ARRAY[1,6], 'Sally'),
(7, ARRAY[1,6,7], 'Mortimer'),
(8, ARRAY[1,6,8], 'Penny');
-- Find the top 2 levels of the company
SELECT id, name, path, array_length(path,1) as depth
FROM employees
WHERE array_length(path,1) <= 2;
-- Find who works for Arthur
SELECT id, name, path FROM employees
WHERE path && ARRAY[2];
-- Find who Alice works under
SELECT id, name, path FROM employees
WHERE ARRAY[id] && ARRAY[1,2,3];
-- Move Alice under Mortimer
UPDATE employees
SET path = ARRAY[1,6,7] || path[3:array_length(path,1)]
WHERE path && ARRAY[3];
-- Show the Hierarchy Again
SELECT id, name, path FROM employees ORDER BY path;
--------------------------------------------------------
-- Move Alice back under Arthur's purview
UPDATE employees
SET path = ARRAY[1,2] || path[4:array_length(path,1)]
WHERE path && ARRAY[3];
-- Show the Hierarchy Again
SELECT id, name, path FROM employees ORDER BY path;
--------------------------------------------------------
-- Aggregates
--
-- How can we generate a breadcrumb?
SELECT employees.id, employees.name, array_agg(parents.name ORDER BY parents.depth) AS superiors
FROM employees
LEFT JOIN (SELECT *, array_length(path,1) as depth FROM employees) AS parents ON employees.path && ARRAY[parents.id]
GROUP BY employees.id;
-- And now in slow motion, what were those pieces?
SELECT
employees.id AS employee_id,
employees.name AS employee_name,
parents.id AS parent_id,
parents.name AS parent_name
FROM employees
LEFT JOIN (SELECT id, name FROM employees) AS parents ON employees.path && ARRAY[parents.id];
-- Ok, what about aggregating the children?
SELECT
employees.id AS employee_id,
employees.name AS employee_name,
children.id AS child_id,
children.name AS child_name
FROM employees
LEFT JOIN (
SELECT id, name, path FROM employees
) AS children ON children.path && ARRAY[employees.id];
--So what does unnest do?
SELECT id, name, path, unnest(path)
FROM employees;
-- How many people work under each employee by id?
SELECT
employees.id,
employees.name,
count
FROM (
SELECT unnest(path) AS employee_id,
count(*) as count
FROM employees
GROUP BY employee_id
) AS children INNER JOIN employees ON children.employee_id = employees.id
ORDER BY count DESC;
-- Add a salary column so we can roll something else up:
ALTER TABLE employees ADD COLUMN salary integer;
-- Populate it:
UPDATE employees
SET salary = (6 - array_length(path,1)) * 20000 + 1000 * id;
-- View it:
SELECT id, name, path, salary FROM employees ORDER BY path;
-- Unnest with our salaries:
SELECT id, name, path, salary, unnest(path)
FROM employees;
-- Now how can we roll up the salary?
SELECT
employees.id,
employees.name,
total_salary
FROM (
SELECT unnest(path) AS parent_id,
sum(salary) AS total_salary
FROM employees
GROUP BY parent_id
) AS children INNER JOIN employees ON children.parent_id = employees.id
ORDER BY id;
--
-- Now lets update this to make it more palatable for rails.
-- Although it was handy beforehand to encode the record's id at the
-- end of its path, it is fairly redundant. Let's strip it out.
UPDATE employees
SET path = path[1:array_length(path,1) - 1];
SELECT id, name, path, array_length(path,1) as depth
FROM employees
ORDER BY path;
@rosenfeld
Copy link

Just to link back to the original article, since I can't "star" the article ;)

http://monkeyandcrow.com/blog/aggregating_hierarchies_with_postgres/

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment