5

Say, I have a table representing colored and labeled items inside numbered boxes.
Each box can not contain more than one item with a particular label, but items with the same label (and the same or a different color) may be unique in other boxes.

Oversimplifying, and using PostgreSQL, we can take the following table:

CREATE TABLE items (
    label character varying,
    color character varying,
    box_number integer
);
INSERT INTO items VALUES
  ('a','red',1),
  ('b','blue',1),
  ('c','blue',1),
  ('a','red',2),
  ('c','green',2),
  ('d','blue',2),
  ('b','red',3),
  ('d','green',3);

I want to know the label and the color of all the items inside the box number 3, but also all the box numbers where an item with the same label can be found. In other words, I'm trying to:

SELECT label, boxes
FROM (
  SELECT label, array_agg(DISTINCT box_number) AS boxes
  FROM items
  GROUP BY label
) AS sub1
WHERE 3 = ANY(boxes);

But I also need to return the color column, showing only the color of the item inside the box number 3.

For the example data, the output should be this:

label | color | boxes
------+-------+------
b     | red   | 1,3
d     | green | 2,3

Here's an SQL Fiddle for the example.

  • Not sure how the title fits the rest of your question? What's discarded? – Erwin Brandstetter Nov 16 '15 at 1:18
  • We can easily find a solution aggregating both box_numbers and colors in arrays, but what I need is to aggregate box_numbers discarding all colors in those rows where the box_number doesn't have a match with a given value (3 in this case). I was thinking about a solution that iterates only once per row, set the color to NULL if it box_number doesn't match 3, put both box_numbers and colors values in arrays so that a simple function like coalesce returns the non NULL color from the resulting array of colors. – Claudio Floreani Nov 16 '15 at 15:09
3

You can use a correlated subquery:

SELECT label, color
    , (SELECT ARRAY (SELECT box_number FROM items WHERE label = i.label)) AS boxes
FROM   items i
WHERE  box_number = 3;

Or (more modern) with LEFT JOIN LATERAL:

SELECT i.label, i.color, b.boxes
FROM   items i
LEFT   JOIN LATERAL (
   SELECT ARRAY (SELECT box_number FROM items WHERE label = i.label) AS boxes
   ) b ON true
WHERE  box_number = 3;

Using an array constructor since that is faster than array_agg() for a single column in the SELECT list.

You could also just use a self-join and aggregate:

SELECT i.label, i.color, array_agg(b.box_number) AS boxes
FROM   items i
JOIN   items b USING (label)
WHERE  i.box_number = 3
GROUP  BY i.label, i.color;

I'd expect that to be a bit slower. Test with EXPLAIN ANALYZE.

SQL Fiddle.

We certainly don't need DISTINCT here, since your data definition says:

Each box can not contain more than one item with a particular label

.. which is surely enforced with a UNIQUE constraint (or equivalent) on (label, box_number)?
This would also automatically provide the second index to make this query fast - besides the obvious index on (box_number). Details:

  • This is an excellent answer! It also turns out that with the real dataset the answer by @a_vlad doesn't always return all the box_numbers where a label is found. I was wondering: (1) in this case, is there a difference in terms of performance between the two methods? (2) (maybe this deserves a separate question:) LATERAL have to be evaluated once for every label inside box 3, do all the answers need to iterate NxN times on N labels? Please read also the comment about the question's title. Thank you – Claudio Floreani Nov 16 '15 at 14:55
  • @ClaudioFloreani: (1) Performance of the two (now three) solutions should be pretty similar. Test with EXPLAIN ANALYZE (repeat a couple of times to rule out caching effects). (2) Basically yes, but Postgres is smart about this, especially with index support. I added an alternative with a plain self-join, I don't expect it to be faster, though. Matching indexes are the most important factor for performance with big tables. – Erwin Brandstetter Nov 16 '15 at 18:14
1

try this (just working ideas, without any optimisation research):

SELECT t1.label, t1.color, array_agg(t1.box_number)
FROM items t1

WHERE t1.box_number = 3
GROUP BY t1.label, t1.color

union all
select 'LABEL' as label, 'NOT FOUND' as color, array_agg(t1.box_number)
FROM items t1 
where t1.label not in (SELECT t2.label
FROM items t2

WHERE t2.box_number = 3)

Test dataset:

BEGIN;
INSERT INTO "dbo"."items" VALUES ('aaa', '1', 'yellow');
INSERT INTO "dbo"."items" VALUES ('bbb', '3', 'green');
INSERT INTO "dbo"."items" VALUES ('ccc', '3', 'black');
INSERT INTO "dbo"."items" VALUES ('ddd', '4', 'green');
COMMIT;

result:

bbb green   {3}
ccc black   {3}
LABEL   NOT FOUND   {1,4}

UPD. after Edit and comment:

SELECT label, color, boxes
FROM (
  SELECT t1.label, (select t2.color from items t2 where t2.box_number =3 and t2.label = t1.label LIMIT 1) as color,array_agg(DISTINCT t1.box_number) AS boxes
  FROM items t1
  GROUP BY label
) AS sub1
WHERE 3=ANY(boxes);

Think, this is what You need?

  • It's a working answer and I've upvoted it. However if my understanding is correct, the color selection needs to iterate label x label times for all labels inside box 3. I'm wondering if there is a linear/faster way, maybe aggregating also colors, giving a NULL value to the colors of items of other boxes, and then using coalesce to get the color. – Claudio Floreani Nov 15 '15 at 17:12
  • It turns out that with the real dataset this solution doesn't always return all the box_numbers where a label is found because if I specify another attribute in the outer SELECT, it also have to be present in the sub SELECT and so it has to be also in the GROUP BY clause. This is still a working solution for the oversimplified example in the question, but it's quite hard (for me) to handle in the more general cases. – Claudio Floreani Nov 16 '15 at 15:38
  • I think it's will be good if You create on SQL fiddle thread with some "real" data which not included in query, sure it help to find right solution – a_vlad Nov 16 '15 at 15:47
  • It would be too complex and out of scope, given that the oversimplified data are themselves a result of other queries and joins. Your solution is a working one to this question and so it has been upvoted, however I'm trying to explain why I've found @Erwin's one more powerful and versatile and so it is the accepted one (so far). – Claudio Floreani Nov 16 '15 at 16:09
0

Ok, after pondering upon @a_vlad and @erwin-brandstetter answers, I came out with my own solution that I leave here open to discussion:

SELECT
    label,
    array_to_string(array_agg(color),',') AS color,
    array_agg(box_number) AS boxes
FROM (SELECT
        label,
        CASE WHEN box_number=3 THEN color END AS color,
        box_number
    FROM items
    ) AS sub1
GROUP BY label
HAVING 3=ANY(array_agg(box_number))

Here's the SQLFiddle : http://sqlfiddle.com/#!15/eb2ac/11/0

As I explained in the comments to the previous answers, the reason why I'm proposing this solution is that it seems much more faster (even from the tests I've done) because it needs only to iterate 2N times instead of NxN times. I'm still convinced that this answer can be further refined, maybe using array constructors instead of array_agg() as Erwin suggested, but I cannot work out how. I would be glad to hear what do you think about.

Here's what is happening on the actual database (column names have been replaced as well as other attributes that needs to be selected/joined/sorted) when I run EXPLAIN SELECT:

Solution 1 (correlated subquery):

Seq Scan on items m  (cost=0.00..1552688.65 rows=355 width=21) (actual time=22.883..5813.845 rows=355 loops=1)
"  Filter: ((box_number)::text = '3'::text)"
"  Rows Removed by Filter: 27123"
"  SubPlan 2"
"    ->  Result  (cost=4361.48..4361.49 rows=1 width=0) (actual time=16.312..16.312 rows=1 loops=355)"
"          InitPlan 1 (returns $1)"
"            ->  Seq Scan on items  (cost=0.00..4361.48 rows=2 width=4) (actual time=4.958..16.271 rows=18 loops=355)"
"                  Filter: ((label)::text = (m.label)::text)"
"                  Rows Removed by Filter: 27460"
Planning time: 0.200 ms
Execution time: 5814.197 ms

Solution 2 (using LATERAL):

Nested Loop Left Join  (cost=4361.48..1552695.75 rows=355 width=53) (actual time=31.448..5693.496 rows=355 loops=1)
"  ->  Seq Scan on items m  (cost=0.00..4361.48 rows=355 width=21) (actual time=11.945..24.483 rows=355 loops=1)"
"        Filter: ((box_number)::text = '3'::text)"
"        Rows Removed by Filter: 27123"
"  ->  Result  (cost=4361.48..4361.49 rows=1 width=0) (actual time=15.962..15.963 rows=1 loops=355)"
"        InitPlan 1 (returns $1)"
"          ->  Seq Scan on items  (cost=0.00..4361.48 rows=2 width=4) (actual time=4.837..15.920 rows=18 loops=355)"
"                Filter: ((label)::text = ($0)::text)"
"                Rows Removed by Filter: 27460"
Planning time: 0.258 ms
Execution time: 5693.929 ms

Solution 3 (using CASE):

GroupAggregate  (cost=6318.73..7231.95 rows=15417 width=25) (actual time=881.221..951.466 rows=340 loops=1)
"  Group Key: items.label"
"  Filter: ('3'::text = ANY ((array_agg(items.box_number))::text[]))"
"  Rows Removed by Filter: 15077"
"  ->  Sort  (cost=6318.73..6387.43 rows=27478 width=25) (actual time=881.066..885.931 rows=27478 loops=1)"
"        Sort Key: items.label"
"        Sort Method: quicksort  Memory: 2906kB"
"        ->  Seq Scan on items  (cost=0.00..4292.78 rows=27478 width=25) (actual time=0.012..21.602 rows=27478 loops=1)"
Planning time: 0.696 ms
Execution time: 952.184 ms

I've repeated the tests several times and they are all alike, and when adding complexity to the query the first two solutions takes so long that I need to stop them and the third always returns within seconds. Furthermore the third query is enough quick that I don't need to touch the indexes since the dataset is not supposed to grow very much.

EDIT:

After checking the self-join solution, it seems to be the faster one when used in a simply case and with only one box_number. When this has to be performed in a more complex case, for example against several box_numbers, it still takes an unacceptable lapse of time compared to the CASE solution

This are the results of the EXPLAIN ANALYZE for the same (logical) query as the other three.

HashAggregate  (cost=9637.72..9640.22 rows=200 width=25) (actual time=63.424..64.045 rows=340 loops=1)
"  Group Key: i.label, i.color"
"  ->  Hash Join  (cost=4636.26..9588.61 rows=6548 width=25) (actual time=41.224..57.156 rows=6494 loops=1)"
"        Hash Cond: ((i.label)::text = (b.label)::text)"
"        ->  Seq Scan on items i  (cost=0.00..4361.48 rows=355 width=21) (actual time=6.033..18.434 rows=355 loops=1)"
"              Filter: ((box_number)::text = '3'::text)"
"              Rows Removed by Filter: 27123"
"        ->  Hash  (cost=4292.78..4292.78 rows=27478 width=18) (actual time=35.145..35.145 rows=27478 loops=1)"
"              Buckets: 4096  Batches: 1  Memory Usage: 1363kB"
"              ->  Seq Scan on items b  (cost=0.00..4292.78 rows=27478 width=18) (actual time=0.007..19.538 rows=27478 loops=1)"
Planning time: 2.236 ms
Execution time: 64.579 ms
  • This is actually rather inefficient. May be ok for a small table using a single sequential scan, but not for anything bigger. – Erwin Brandstetter Nov 16 '15 at 18:24
  • @ErwinBrandstetter you are the expert, but the actual query performances are the ones I edited in the answer. I like the elegance of your solutions but the harsh reality is that the dirty solution is much quicker. If you are able to work out something that performs faster without looking at the actual database and manipulating the indexes or other definitions, I would be very pleased to have a cleaner solution. – Claudio Floreani Nov 16 '15 at 19:00
  • 1
    I only see sequential scans in your query plans. The basic problem: missing indexes. Your post is really another question, not an answer. Start an actual question if you need to optimize performance. You can always link to this one. Consider instructions in the tag info for [postgresql-performance]. – Erwin Brandstetter Nov 17 '15 at 4:44
  • Thank you Erwin, your answers were very exhaustive and I will continue to test them, taking in consideration your comments. Maybe I will make a composite index as you suggest to make the correlated subquery solution faster since it seems the smartes one. The actual dataset in the main table is quite small, less than 50k records, and it must be queried by a large number of different queries, so I wonder if providing indexes and composite indexes to make each of them fast is the right way to go, but as you suggest I will start another question as the development goes on. – Claudio Floreani Nov 17 '15 at 18:05
  • There is also an issue with data types. ((box_number)::text = '3'::text)" shouldn't occur for an integer column. Might prevent index utilization on top of being inefficient. That's all stuff for a new question providing the complete, actual table definition, indexes, cardinalities, queries, write patterns etc. as instructed in the tag info for [postgresql-performance]. – Erwin Brandstetter Nov 17 '15 at 20:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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