Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to SELECT the newest four items per category?

I have a database of items. Each item is categorized with a category ID from a category table. I am trying to create a page that lists every category, and underneath each category I want to show the 4 newest items in that category.

For Example:

Pet Supplies

img1
img2
img3
img4

Pet Food

img1
img2
img3
img4

I know that I could easily solve this problem by querying the database for each category like so:

SELECT id FROM category

Then iterating over that data and querying the database for each category to grab the newest items:

SELECT image FROM item where category_id = :category_id 
ORDER BY date_listed DESC LIMIT 4

What I'm trying to figure out is if I can just use 1 query and grab all of that data. I have 33 categories so I thought perhaps it would help reduce the number of calls to the database.

Anyone know if this is possible? Or if 33 calls isn't that big a deal and I should just do it the easy way.

like image 264
justinl Avatar asked Sep 18 '09 03:09

justinl


3 Answers

This is the greatest-n-per-group problem, and it's a very common SQL question.

Here's how I solve it with outer joins:

SELECT i1.*
FROM item i1
LEFT OUTER JOIN item i2
  ON (i1.category_id = i2.category_id AND i1.item_id < i2.item_id)
GROUP BY i1.item_id
HAVING COUNT(*) < 4
ORDER BY category_id, date_listed;

I'm assuming the primary key of the item table is item_id, and that it's a monotonically increasing pseudokey. That is, a greater value in item_id corresponds to a newer row in item.

Here's how it works: for each item, there are some number of other items that are newer. For example, there are three items newer than the fourth newest item. There are zero items newer than the very newest item. So we want to compare each item (i1) to the set of items (i2) that are newer and have the same category as i1. If the number of those newer items is less than four, i1 is one of those we include. Otherwise, don't include it.

The beauty of this solution is that it works no matter how many categories you have, and continues working if you change the categories. It also works even if the number of items in some categories is fewer than four.


Another solution that works but relies on the MySQL user-variables feature:

SELECT *
FROM (
    SELECT i.*, @r := IF(@g = category_id, @r+1, 1) AS rownum, @g := category_id
    FROM (@g:=null, @r:=0) AS _init
    CROSS JOIN item i
    ORDER BY i.category_id, i.date_listed
) AS t
WHERE t.rownum <= 3;

MySQL 8.0.3 introduced support for SQL standard window functions. Now we can solve this sort of problem the way other RDBMS do:

WITH numbered_item AS (
  SELECT *, ROW_NUMBER() OVER (PARTITION BY category_id ORDER BY item_id) AS rownum
  FROM item
)
SELECT * FROM numbered_item WHERE rownum <= 4;
like image 85
Bill Karwin Avatar answered Nov 10 '22 10:11

Bill Karwin


This solution is an adaptation from another SO solution, thank you RageZ for locating this related/similar question.

NOTE

This solution seems satisfactory for Justin's use case. Depending on your use case you may want to check Bill Karwin or David Andres' solutions in this posting. Bill's solution has my vote! See why, as I put both queries next to one another ;-)

The benefit of my solution is that it returns one record per category_id (the info from the item table is "rolled-up"). The main drawback of my solution is its lack of readability and its growing complexity as the number of desired rows grows (say to have 6 rows per category rather than 6). Also it may be slightly slower as the number of rows in the item table grows. (Regardless, all solutions will perform better with a smaller number of eligible rows in the item table, and it is therefore advisable to either periodically delete or move older items and/or to introduce a flag to help SQL filter out rows early)

First try (didn't work!!!)...

The problem with this approach was that the subquery would [rightfully but bad for us] produce very many rows, based on the cartesian products defined by the self joins...

SELECT id, CategoryName(?), tblFourImages.*
FROM category
JOIN (
    SELECT i1.category_id, i1.image as Image1, i2.image AS Image2, i3.image AS Image3, i4.image AS Image4
    FROM item AS i1
    LEFT JOIN item AS i2 ON i1.category_id = i2.category_id AND i1.date_listed > i2.date_listed
    LEFT JOIN item AS i3 ON i2.category_id = i3.category_id AND i2.date_listed > i3.date_listed
    LEFT JOIN item AS i4 ON i3.category_id = i4.category_id AND i3.date_listed > i4.date_listed
) AS tblFourImages ON tblFourImages.category_id = category.id
--WHERE  here_some_addtional l criteria if needed
ORDER BY id ASC;

Second try. (works ok!)

A WHERE clause in added for the subquery, forcing the date listed to be the latest, second latest, thrird lateest etc. for i1, i2, i3 etc. respectively (and also allowing for the null cases when there are fewer than 4 items for a given category id). Also added was unrelated filter clauses to prevent showing entries that are "sold" or entries that do not have an image (added requirements)

This logic makes the assumption that there are no duplicate date listed values (for a given category_id). Such cases would otherwise create duplicate rows. Effectively this use of the date listed is that of a monotonically incremented primary key as defined/required in Bill's solution.

SELECT id, CategoryName, tblFourImages.*
FROM category
JOIN (
    SELECT i1.category_id, i1.image as Image1, i2.image AS Image2, i3.image AS Image3, i4.image AS Image4, i4.date_listed
    FROM item AS i1
    LEFT JOIN item AS i2 ON i1.category_id = i2.category_id AND i1.date_listed > i2.date_listed AND i2.sold = FALSE AND i2.image IS NOT NULL
          AND i1.sold = FALSE AND i1.image IS NOT NULL
    LEFT JOIN item AS i3 ON i2.category_id = i3.category_id AND i2.date_listed > i3.date_listed AND i3.sold = FALSE AND i3.image IS NOT NULL
    LEFT JOIN item AS i4 ON i3.category_id = i4.category_id AND i3.date_listed > i4.date_listed AND i4.sold = FALSE AND i4.image IS NOT NULL
    WHERE NOT EXISTS (SELECT * FROM item WHERE category_id = i1.category_id AND date_listed > i1.date_listed)
      AND (i2.image IS NULL OR (NOT EXISTS (SELECT * FROM item WHERE category_id = i1.category_id AND date_listed > i2.date_listed AND date_listed <> i1.date_listed)))
      AND (i3.image IS NULL OR (NOT EXISTS (SELECT * FROM item WHERE category_id = i1.category_id AND date_listed > i3.date_listed AND date_listed <> i1.date_listed AND date_listed <> i2.date_listed)))
      AND (i4.image IS NULL OR (NOT EXISTS (SELECT * FROM item WHERE category_id = i1.category_id AND date_listed > i4.date_listed AND date_listed <> i1.date_listed AND date_listed <> i2.date_listed AND date_listed <> i3.date_listed)))
) AS tblFourImages ON tblFourImages.category_id = category.id
--WHERE  --
ORDER BY id ASC;

Now... compare the following where I introduce an item_id key and use Bill's solution to provide the list of these to the "outside" query. You can see why Bill's approach is better...

SELECT id, CategoryName, image, date_listed, item_id
FROM item I
LEFT OUTER JOIN category C ON C.id = I.category_id
WHERE I.item_id IN 
(
SELECT i1.item_id
FROM item i1
LEFT OUTER JOIN item i2
  ON (i1.category_id = i2.category_id AND i1.item_id < i2.item_id
      AND i1.sold = 'N' AND i2.sold = 'N'
      AND i1.image <> '' AND i2.image <> ''
      )
GROUP BY i1.item_id
HAVING COUNT(*) < 4
)
ORDER BY category_id, item_id DESC
like image 5
10 revs Avatar answered Nov 10 '22 08:11

10 revs


In other databases you can do this using the ROW_NUMBER function.

SELECT
    category_id, image, date_listed
FROM
(
    SELECT
        category_id, image, date_listed,
        ROW_NUMBER() OVER (PARTITION BY category_id
                           ORDER BY date_listed DESC) AS rn
    FROM item
) AS T1
WHERE rn <= 4

Unfortunately MySQL does not support the ROW_NUMBER function, but you can emulate it using variables:

SELECT
    category_id, image, date_listed
FROM
(
    SELECT
        category_id, image, date_listed,
        @rn := IF(@prev = category_id, @rn + 1, 1) AS rn,
        @prev := category_id
    FROM item
    JOIN (SELECT @prev := NULL, @rn = 0) AS vars
    ORDER BY category_id, date_listed DESC
) AS T1
WHERE rn <= 4

See it working online: sqlfiddle

It works as follows:

  • Intially @prev is set to NULL, and @rn is set to 0.
  • For each row we see, check if the category_id is the same as the previous row.
    • If yes, increment the row number.
    • Otherwise start a new category and reset the row number back to 1.
  • When the subquery completes, the final step is to filter so that only rows with row number less than or equal to 4 are kept.
like image 3
Mark Byers Avatar answered Nov 10 '22 08:11

Mark Byers