Archive for March 1st, 2010
A feedback on one of my previous articles comparing adjacency list and nested sets models for PostgreSQL.
In your series on adjacency lists vs nested sets, you discuss geometric types and R-Tree indexes in MySQL, but you don't discuss them when discussing the same subject with PostgreSQL, which also has geometric types and R-Tree indexing (mostly available through GiST indexes).
To make it simple I added the following line after the data insertion part of the script at Nested Sets - Postgresql:ALTER TABLE t_hierarchy ADD COLUMN sets POLYGON; UPDATE t_hierarchy SET sets = POLYGON(BOX(POINT(-1,lft), POINT(1, rgt)));
It needed to be a
POLYGONinstead of a
BOXsince there is a
@>(POLYGON,POLYGON)function but no
@>(BOX,BOX)function, and the polygon was cast from the box to create the rectangle shape required.
It outperforms the adjacency list onall descendants; outperforms it onall ancestors(not by much); performs reasonably well onall descendants up to a certain levelon items with few descendants (e. g. 31415) and badly on items with many descendants (e. g. 42).
It still completes in less than 20 seconds though, which is an improvement over 1 minute.
PostgreSQL does support R-Tree indexes indeed (through GiST interface), and they can be used to improve the efficiency of the nested sets model.
Let's create a sample table and try some of the queries that Jay proposed:
Read the rest of this entry »