0

I am on the quest to implement an NMS filter for labels in a Database.

For context, here's a link to my first question, where I explain what NMS is and what I'm trying to achieve (I will edit that post from its current state to a self-answered post as soon as I finish writing this question, then I will delete this parenthesis).

In that post, I could group the labels that shared a large area.

My problem now is that the query I came out with is slow (takes like 1.6 seconds for 20 registers) and seems to me that is also redundant, but I don't know how to optimize it (or if there is a better (faster) approach for that problem).

This is the table I start from.

id top left right bottom
orange 10 15 29 60
red 12 16 30 58
grey 11 10 28 61
green 20 23 45 44
blue 22 25 44 41

And this is what I want to get.

id top left right bottom
orange 10 15 29 60
blue 22 25 44 41

The picture below shows on the left side the start table (1) and on the right the target table(2). The goal is to remove duplicates, and two labels are considered duplicates if they share a big proportion of its area (details on how to determine that are written in my previous question).

(1)what I have, (2) goal

Which label I will be selecting to "survive" is unimportant for the time being.

The query that achieves that is the following

with recursive data as ( '(a) ,(b)'
    select  l1.id,
            array [l1.id,l2.id] as ids,
            greatest(least(l1.right,l2.right) - greatest(l1.left,l2.left),0) * greatest(least(l1.bottom,l2.bottom) - greatest(l1.top,l2.top),0) as i, 
            (l1.right-l1.left)*(l1.bottom-l1.top) + (l2.right-l2.left)*(l2.bottom-l2.top) - greatest(least(l1.right,l2.right) - greatest(l1.left,l2.left),0) * greatest(least(l1.bottom,l2.bottom) - greatest(l1.top,l2.top),0) as u,
            (greatest(least(l1.right,l2.right) - greatest(l1.left,l2.left),0) * greatest(least(l1.bottom,l2.bottom) - greatest(l1.top,l2.top),0)::float)
                    /
                ((l1.right-l1.left)*(l1.bottom-l1.top)
                + (l2.right-l2.left)*(l2.bottom-l2.top)
                - greatest(least(l1.right,l2.right) - greatest(l1.left,l2.left),0) * greatest(least(l1.bottom,l2.bottom) - greatest(l1.top,l2.top),0))
            as iou
    from "IoAi".labelstry l1
    left join "IoAi".labelstry l2
        on l1.id != l2.id 
    where (greatest(least(l1.right,l2.right) - greatest(l1.left,l2.left),0) * greatest(least(l1.bottom,l2.bottom) - greatest(l1.top,l2.top),0)::float)
                    /
                ((l1.right-l1.left)*(l1.bottom-l1.top)
                + (l2.right-l2.left)*(l2.bottom-l2.top)
                - greatest(least(l1.right,l2.right) - greatest(l1.left,l2.left),0) * greatest(least(l1.bottom,l2.bottom) - greatest(l1.top,l2.top),0))
        > 0.6
),
grouped_data(id, ids) as( '(c)'
    select id, ids 
    from data
    union   
    select d.id, iou_array_merge(d.ids, gd.ids)
    from grouped_data gd
    join data d
    on gd.ids && d.ids 
), selected_data as( '(d)'
    select array_agg(id) as ids
    from (
        select distinct on(id) *
        from grouped_data
        order by id, cardinality(ids) desc
        ) s
    group by ids
)
select sd.ids as grouped, l1.* from selected_data sd '(e)'
left join "IoAi".labelstry l1
on l1.id = sd.ids[1]

'a) The only recursive table is the second one, grouped_data. Postgres syntax demands the keyword recursive to be in the first with.'
'b) "data" query obtains the "intersection over union" (IoU) score between two labels and discards those that are less than 0.6'
'c) "grouped_data" uses the result from "data" and recursiveness to join all groups that share one common element'
'd) "selected_data" filters the result from "grouped_data" to retrieve the largest groups'
'e) the last query selects the first element of each group (arbitrary criteria) and joins the label'

These are the sub-query results:

data:

id ids I U IoU
orange {orange,red} 598 746 0.8016085790884718
orange {orange,grey} 637 963 0.6614745586708204
red {red,orange} 598 746 0.8016085790884718
grey {grey,orange} 637 963 0.6614745586708204
green {green,blue} 361 528 0.6837121212121212
blue {blue,green} 361 528 0.6837121212121212

grouped_data:

id ids
orange {orange,red}
orange {orange,grey}
red {red,orange}
grey {grey,orange}
green {green,blue}
blue {blue,green}
orange {grey,orange,red}
orange {grey,orange}
red {orange,red}
red {grey,orange,red}
grey {grey,orange,red}
green {blue,green}

selected_data: | ids| |:--:| |{grey,orange,red}| |{blue,green}|

this is the final result.

grouped id top left right bottom
{grey,orange,red} grey 11 10 28 61
{blue,green} blue 22 25 44 41

Is worth noticing that I got the gray square instead of orange. Wich one I get is not important yet.

I also added the grouped column, which will be important in the future for deleting the duplicated registers.

As @Charlieface suggests in comments, I'm adding the create table statement and some registers.

CREATE TABLE labels (
    id varchar NULL,
    "left" int4 NULL,
    "top" int4 NULL,
    "right" int4 NULL,
    "bottom" int4 NULL,
    CONSTRAINT labelstry_pk PRIMARY KEY (id)
);

INSERT INTO "IoAi".labelstry (id,"left",top,"right",bottom) 
VALUES ('0a521a93-145c-46b9-9c4a-8839caf7c22b'::uuid,11,4,189,231),
       ('09f50acd-4974-4cf6-adab-9d3c86242819'::uuid,8,5,189,232),
       ('3f335f57-b262-474a-ba9e-20d342a5db91'::uuid,42,52,86,31),
       ('b18196e4-6999-4220-8f3a-749170036dde'::uuid,5,7,188,231),
       ('707e73e6-0d7a-40fd-b46f-72e2856f923d'::uuid,24,65,99,122),
       ('21536d52-81cf-47fa-88b6-6c47acc56e23'::uuid,9,5,189,231),
       ('ab7d2ed2-0344-4361-9103-0d8de31464c7'::uuid,24,69,100,122),
       ('d542dbb0-deab-41cd-a18c-35aeb40fc449'::uuid,42,51,85,30),
       ('5bf9b655-8c96-4435-8668-0e387ac21a58'::uuid,27,65,96,121),
       ('bcd7ad39-0241-48f3-9752-5e46c8fa62c7'::uuid,2,5,189,231),
       ('64930c0e-026f-4b7a-8906-2ca7de125966'::uuid,4,7,188,232),
       ('43994f28-d86b-4546-a7e8-4a8a76823c7a'::uuid,10,4,189,232),
       ('245ff938-7c74-43df-901e-b7e28877784d'::uuid,44,54,89,32),
       ('a1afcc94-ec26-4169-890f-b893e915c97c'::uuid,7,6,188,231),
       ('a84c25a1-056e-4c89-8980-5f7cc08a9679'::uuid,6,6,188,232),
       ('446ce255-6533-4ef2-9058-56a49ffe639e'::uuid,26,67,100,121),
       ('f7330f09-514e-4345-9b95-28a17aeafad3'::uuid,100,21,33,51),
       ('87f6d6f8-0b38-4ec2-8f5e-1438136c7e83'::uuid,65,33,99,51),
       ('619a1e7f-e41c-4a4b-b124-271075c3ca6d'::uuid,4,5,189,231),
       ('49ccfd1f-877c-4bc2-abdc-9d6b0144c161'::uuid,4,5,189,231);

the queryplan

Hash Left Join  (cost=34212.77..34219.30 rows=200 width=64)
Hash Cond: ((array_agg(s.id))[1] = l1.id)
CTE data
    ->  Nested Loop  (cost=0.00..51.78 rows=114 width=64)
        Join Filter: ((l1_1.id <> l2.id) AND ((((GREATEST((LEAST(l1_1."right", l2."right") - GREATEST(l1_1."left", l2."left")), 0))::double precision * (GREATEST((LEAST(l1_1.bottom, l2.bottom) - GREATEST(l1_1.top, l2.top)), 0))::double precision) / (((((l1_1."right" - l1_1."left") * (l1_1.bottom - l1_1.top)) + ((l2."right" - l2."left") * (l2.bottom - l2.top))) - (GREATEST((LEAST(l1_1."right", l2."right") - GREATEST(l1_1."left", l2."left")), 0) * GREATEST((LEAST(l1_1.bottom, l2.bottom) - GREATEST(l1_1.top, l2.top)), 0))))::double precision) > '0.6'::double precision))
        ->  Seq Scan on labelstry l1_1  (cost=0.00..1.19 rows=19 width=32)
        ->  Materialize  (cost=0.00..1.28 rows=19 width=32)
                ->  Seq Scan on labelstry l2  (cost=0.00..1.19 rows=19 width=32)
CTE grouped_data
    ->  Recursive Union  (cost=0.00..32892.36 rows=13114 width=48)
        ->  CTE Scan on data  (cost=0.00..2.28 rows=114 width=48)
        ->  Nested Loop  (cost=0.00..3262.78 rows=1300 width=48)
                Join Filter: (gd.ids && d.ids)
                ->  CTE Scan on data d  (cost=0.00..2.28 rows=114 width=48)
                ->  WorkTable Scan on grouped_data gd  (cost=0.00..22.80 rows=1140 width=32)
->  GroupAggregate  (cost=1267.20..1271.20 rows=200 width=64)
        Group Key: s.ids
        ->  Sort  (cost=1267.20..1267.70 rows=200 width=48)
            Sort Key: s.ids
            ->  Subquery Scan on s  (cost=1191.99..1259.56 rows=200 width=48)
                    ->  Unique  (cost=1191.99..1257.56 rows=200 width=52)
                        ->  Sort  (cost=1191.99..1224.77 rows=13114 width=52)
                                Sort Key: grouped_data.id, (cardinality(grouped_data.ids)) DESC
                                ->  CTE Scan on grouped_data  (cost=0.00..295.07 rows=13114 width=52)
->  Hash  (cost=1.19..1.19 rows=19 width=32)
        ->  Seq Scan on labelstry l1  (cost=0.00..1.19 rows=19 width=32)
Improve this question
3
  • 2
    For optimization quetions, we need table and index definitions, as well as the current query plan.
    – Charlieface
    Commented Oct 30, 2022 at 1:45
  • Hello @Charlieface, thank you for your input. What is a "query plan"? the only index in this testing table is the id column, that is the primary key and is type uuid (I changed it to color names for this example to make it easy to match with the picture). On the other hand, I am not looking for optimizations on the database or table structure, but on the query itself, since I find it to be clumsy, redundant, and it takes too many steps to achieve its the goal.
    – J Pablo F
    Commented Oct 30, 2022 at 14:02
  • 1
    postgresql.org/docs/current/sql-explain.html It shows you how the optimizer worked out the best way to execute the query. Part of optimizing a query is normally to also look at what indexes may help the query. A sample script with the table definition CREATE TABLE and sample INSERT statements would help also.
    – Charlieface
    Commented Oct 30, 2022 at 14:44

0

Reset to default

Your Answer

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