0

I have a geo table that contains

  • countries
  • localities (city, town, village, island, archipelago)
  • locations (venue/business + boroughs/district/area), e.g - Big Ben, or Southwark Borough.

For extra details of each place type, I have a relating tables.
'country_details' table for places of type 'country', and similarly for locations.

For a location like 'Big Ben', it has reference for the id of its locality (i.e London), and also reference to country (which can be simply by the country's iso_code)

Example:

 id |     title      |  locality_id  |  country_iso_code |
---------------------------------------------------------|
 1  | United Kingdom |     null      |     UK            |
 2  | London         |     null      |     UK            |
 3  | Big Ben        |      2        |     UK            |
 4  | XYZ District   |      2        |     UK            |

Scenario

Now, since in order to send the client information about Big Ben I'd also want to get to the name of locality (London) and the country (United Kingdom), it seems my only 2 options are:

  1. recursive CTE
  2. JOIN on the same table.

However, once we have a table of tens of thousand records, which can potentially grow into a lot more (few millions), aside for the query complexity it will also impact the performance I suppose.

Question

What is the better option to get "join" the details like "London" and "United Kingdom" ?
Are both options bad and it's better to rethink the schema design?

Tables :

CREATE TABLE places (
    id              int,
    type            smallint, -- ['country', 'locality', 'location']
    sub_type        smallint, -- nullable (city, village, etc.)

    -- names
    title           text,

    -- locality
    locality_name   text,
    locality_id     

    -- country
    country_iso_alpha2 text, -- 'GB'
    country_name       text, -- 'United Kingdom'
    admin_region       text, -- 'England', 'Texas', .. (null for Country)
    
    ...
);

CREATE TABLE country_details(
    place_id      int,
    place_type    smallint NOT NULL CHECK (item_type=1),

    iso_alpha2    text,
    iso_alpha3    text,
    ...

    PRIMARY KEY (place_id, place_type),
    FOREIGN KEY (place_id, place_type) references places (place_id, place_type) ON DELETE CASCADE
);

CREATE TABLE location_details(
    place_id      int,
    place_type    smallint NOT NULL CHECK (item_type=3),

    website            text,
    neighborhood       text,
    formatted_address  text,
    ...

    PRIMARY KEY (place_id, place_type),
    FOREIGN KEY (place_id, place_type) references places (place_id, place_type) ON DELETE CASCADE
);

2 Answers 2

1

It's a tree, so let's build an example tree with 10 leaves per level and 7 levels, so about 1.1M rows.

-- create raw data
CREATE UNLOGGED TABLE tree1 (
    id          INTEGER NOT NULL GENERATED BY DEFAULT AS IDENTITY,
    parent_id   INTEGER NULL,
    level       INTEGER NOT NULL
);

INSERT INTO tree1 (id, parent_id, level) VALUES (0,NULL,0);
INSERT INTO tree1 (parent_id,level) SELECT id,level+1 FROM tree1 CROSS JOIN generate_series(1,10) WHERE level=0;
INSERT INTO tree1 (parent_id,level) SELECT id,level+1 FROM tree1 CROSS JOIN generate_series(1,10) WHERE level=1;
INSERT INTO tree1 (parent_id,level) SELECT id,level+1 FROM tree1 CROSS JOIN generate_series(1,10) WHERE level=2;
INSERT INTO tree1 (parent_id,level) SELECT id,level+1 FROM tree1 CROSS JOIN generate_series(1,10) WHERE level=3;
INSERT INTO tree1 (parent_id,level) SELECT id,level+1 FROM tree1 CROSS JOIN generate_series(1,10) WHERE level=4;
INSERT INTO tree1 (parent_id,level) SELECT id,level+1 FROM tree1 CROSS JOIN generate_series(1,10) WHERE level=5;

-- create table with paths
CREATE UNLOGGED TABLE tree (
    id          INTEGER NOT NULL,
    parent_id   INTEGER NULL,
    path        INTEGER[] NOT NULL,
    level       INTEGER GENERATED ALWAYS AS (array_length(path,1)) STORED
);

-- populate
WITH RECURSIVE st AS (
    -- select root
    SELECT t.id, t.parent_id, ARRAY[t.id] path FROM tree1 t WHERE t.id=0
  UNION ALL
    SELECT t.id, t.parent_id, path || t.id 
    FROM tree1 t JOIN st ON (t.parent_id=st.id)
)
INSERT INTO tree (id, parent_id, path) SELECT * FROM st;

DROP TABLE tree1;

ALTER TABLE tree ADD PRIMARY KEY (id);
CREATE INDEX ON tree( parent_id );
CREATE INDEX ON tree( path );

VACUUM ANALYZE tree;

Now let's get a leaf, along with all its parents, up to the root. There are several methods.

  • Using the path

That's the way it was done before WITH RECURSIVE. It works fine:

-- get one node and parents using path
SELECT * FROM 
  (SELECT unnest(path) id FROM tree WHERE id=1000000) p 
  JOIN tree USING (id);

 Nested Loop  (cost=0.85..92.95 rows=10 width=60) (actual time=0.092..0.152 rows=7 loops=1)
   ->  ProjectSet  (cost=0.43..8.50 rows=10 width=4) (actual time=0.071..0.078 rows=7 loops=1)
         ->  Index Scan using tree_pkey on tree tree_1  (cost=0.43..8.45 rows=1 width=48) (actual time=0.064..0.067 rows=1 loops=1)
               Index Cond: (id = 1000000)
   ->  Index Scan using tree_pkey on tree  (cost=0.43..8.45 rows=1 width=60) (actual time=0.008..0.008 rows=1 loops=7)
         Index Cond: (id = (unnest(tree_1.path)))
 Planning Time: 0.342 ms
 Execution Time: 0.214 ms
  • Using WITH RECURSIVE

This is the standard option. It doesn't use the path at all, so this column can be removed unless it is used for something else.

-- get one node and parents using WITH
WITH RECURSIVE st AS (
    -- select root
    SELECT * FROM tree WHERE id=1000000
  UNION ALL
    SELECT tree.* FROM tree JOIN st ON (tree.id=st.parent_id)
)
SELECT * FROM st;

 CTE Scan on st  (cost=855.96..857.98 rows=101 width=44) (actual time=0.037..0.204 rows=7 loops=1)
   CTE st
     ->  Recursive Union  (cost=0.43..855.96 rows=101 width=60) (actual time=0.035..0.193 rows=7 loops=1)
           ->  Index Scan using tree_pkey on tree  (cost=0.43..8.45 rows=1 width=60) (actual time=0.033..0.036 rows=1 loops=1)
                 Index Cond: (id = 1000000)
           ->  Nested Loop  (cost=0.43..84.65 rows=10 width=60) (actual time=0.019..0.019 rows=1 loops=7)
                 ->  WorkTable Scan on st st_1  (cost=0.00..0.20 rows=10 width=4) (actual time=0.000..0.001 rows=1 loops=7)
                 ->  Index Scan using tree_pkey on tree tree_1  (cost=0.43..8.45 rows=1 width=60) (actual time=0.015..0.015 rows=1 loops=7)
                       Index Cond: (id = st_1.parent_id)
 Planning Time: 0.409 ms
 Execution Time: 0.269 ms

Conclusion: both options are very fast, less than 1ms. No clear winner. Not surprising since all they do is fetch a small number of rows via the indexed primary key.

  • Using JOINs

I'm not considering it because it would impose a fixed maximum depth on the tree and it returns rows in a format that is inconvenient for a tree (ie, with a ton of columns).

However, in my tree example, all leaves in this tree have the same format. The subdivision levels you're using do not.

If your depth is fixed (countries>localities>locations) and you're sure you'll never need to subdivide into counties, blocks, sub-boroughs or other stuff... then the JOIN method makes sense because the row format that was previously inconvenient now becomes convenient, since you're dealing with three different types of subdivisions, in three different tables, and they all have different columns.

In fact, with the JOIN method, you can get the whole result in one query. With the other two, once you get the id's from the path out of the tree table, you'd have to query the three subdivision tables separately, which adds more work.

This will scale well, because the most often hit rows are the low levels of the tree, which will pretty much always be cached in RAM.

1
  • Thank you for this detailed explanation!
    – BinaryVeil
    Commented Feb 5 at 21:24
1

it seems my only 2 options are:

  1. recursive CTE
  2. JOIN on the same table.

If it's a fixed number of joins and a small number, then for simplicity's sake, I'd say go with option #2 and do a few self-joins.

If there's a lot of variability in the hierarchical depth of the data, then I'd say go with option #1 and use a recursive CTE.

However, once we have a table of tens of thousand records, which can potentially grow into a lot more (few millions), aside for the query complexity it will also impact the performance I suppose.

For the self-join solution, a few million rows is small, and when indexed properly, the difference from a few hundred rows is negligible.

For the recursive CTE solution, it should still be quite performant over a few million rows, when indexed properly. But you may notice slight regression, such as from taking under a second for a few hundred rows to taking a few seconds for a few million rows.

1
  • Thank you for the answer! alas it's impossible to accept both answers. It reassured me in the design decision
    – BinaryVeil
    Commented Feb 5 at 21:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.