4

I run a car sales website for a client. They are constantly adding and removing cars. When a new one comes in, they add a batch of images and the website generates a thumbnail for each. The site stores the base filename (through which I can access both thumbnail and original). Here's an example:

5e1adcf7c9c1bcf8842c24f3bacbf169.jpg
5e1adcf7c9c1bcf8842c24f3bacbf169_tn.jpg
5e1de0c86e45f84b6d01af9066581e84.jpg
5e1de0c86e45f84b6d01af9066581e84_tn.jpg
5e2497180424aa0d5a61c42162b03fef.jpg
5e2497180424aa0d5a61c42162b03fef_tn.jpg
5e2728ac5eff260f20d4890fcafb1373.jpg
5e2728ac5eff260f20d4890fcafb1373_tn.jpg

The problem comes after a product is removed. In my existing workflow, there isn't a simple way to remove old images. In a period of a few months we end up with 10,000 images, where only 10% are live.

I can search the database and generate a list of live image stubs:

5e1adcf7c9c1bcf8842c24f3bacbf169
5e2497180424aa0d5a61c42162b03fef

I want to delete the images that don't begin with these stubs.

Note that time/space performance is an issue here too. There are ~500+ stubs at any one time. I have tried grepping ls like:

ls | grep -vf <(
    sqlite3 database.sqlite3 'select replace(images, CHAR(124), CHAR(10)) from cars_car'
)

This works but it's critically slow (and you shouldn't parse ls). The query is fast so it's the grep bit that bogs it all down. I'd like better solutions. Bash isn't necessary but it's what I do most of my maintenance scripting in.

7 Answers 7

3

I would guess it will be both simpler and faster to just use GLOBIGNORE (assuming your shell is bash anyway):

   GLOBIGNORE
          A colon-separated list of patterns defining the set of filenames
          to be ignored by pathname expansion.  If a filename matched by a
          pathname expansion pattern also matches one of the  patterns  in
          GLOBIGNORE, it is removed from the list of matches.

So, you could just read the patterns you want from your file, add a * to make them globs and convert into a colon separated list:

GLOBIGNORE=$(sqlite3 database.sqlite3 'select images from cars_car;' |
             sed 's/|/*:/g; s/$/*/')

Then, you can just rm everything, and reset GLOBIGNORE (or just close the current terminal) :

rm * && GLOBIGNORE=""

Because GLOBIGNORE will now look like this:

$ echo $GLOBIGNORE 
5e1adcf7c9c1bcf8842c24f3bacbf169*:5e2497180424aa0d5a61c42162b03fef*

Any files matching those globs will not be included in the expansion of *. This has the added benefit of working with any type of file name, including those with spaces, newlines or other strange characters.

7
  • It seems the delimiter from sqlite is |, so sed 's/|/*:'?
    – muru
    Mar 22, 2015 at 12:17
  • This looks very interesting. I'll benchmark it in a minute.
    – Oli
    Mar 22, 2015 at 12:19
  • @muru ah, yes, thanks. I was using a file with a pattern per line for testing. Fixed.
    – terdon
    Mar 22, 2015 at 12:24
  • @Oli if you do, please use the updated one that fixes the bug that Muru found.
    – terdon
    Mar 22, 2015 at 12:25
  • My SQL output was a little more complicated than that. It was pipe-separated and line-separated so each record could have multiple image stubs. I've updated the example so it just pumps out a line-separated list of stubs with pipes already removed.
    – Oli
    Mar 22, 2015 at 12:56
3

While writing the question, I started playing around with grep. Part of the performance problem is that grep is running a ton of regex searches for every file. These are expensive.

We can just do full-string searches without the regex, using the -F argument.

find | grep -vFf <(
    sqlite3 database.sqlite3 'select replace(images, CHAR(124), CHAR(10)) from cars_car'
) ### | xargs rm

The output is the same, and runs in 0.045s.
The old one took 14.211s.


One of the problems with parsing ls is the problematic filenames. muru's comment below highlights a pretty decent way of using null-characters through the entire pipeline.

find -print0 | grep -vzFf <(
    sqlite3 database.sqlite3 'select replace(images, CHAR(124), CHAR(10)) from cars_car'
) ### | xargs -0 rm

The reason I'm not switching my main answer to this is that I know my files will always be clean and that I've been running this into wc -l to make sure I'm seeing the correct number of files for deletion.

4
  • So... find . -iname '*.jpg' -print0 | grep -vzFf <(sqlite3 database.sqlite3 'select images from cars_car;' | sed 's/|/\n/g') | xargs -0 rm? Since fixed-string matching doesn't automaticaly imply whole-word matching, so foo will filter out both foo.jpg and foo_tn.jpg.
    – muru
    Mar 22, 2015 at 12:05
  • +1 but you might want to mention that this fails if the file names contain spaces or newlines.
    – terdon
    Mar 22, 2015 at 12:07
  • @muru That's a nice alteration to sidestep problematic filenames, but it makes checking how many files it's selecting (with wc -l) a bit tougher.
    – Oli
    Mar 22, 2015 at 12:14
  • 2
    @Oli while we're at it... grep -zc ^?
    – muru
    Mar 22, 2015 at 12:16
1

If you are using bash as your shell, then shopt -s extglob can enable some more features in glob patterns. For example

!(5e1adcf7c9c1bcf8842c24f3bacbf169*|5e2497180424aa0d5a61c42162b03fef*)

will match all names not starting with one of the two strings.

1
  • The list is very long (500×32char strings) and dynamically pulled from a database. This would work for small exceptions but gets a bit unwieldy for my purposes.
    – Oli
    Mar 22, 2015 at 16:44
1

You could simply remove the images within the product removal script execution. This way the load will be balanced across each product removal over time. Additionally you won't have to worry about running a script to clean them up at all, and the whole application will be self-sufficient. Not to mention it would solve the space issue to this end.

I have no idea about which DBMS you're using, nor about which scripting language you're using to manipulate it or about how your database structure looks like (no idea about the images' path as well), but for example, assuming MySQL as the DBMS, PHP as the scripting language and a Products table in a 1-to-many relationship with a Images table, with the images' path pointing to a img folder placed under the root directory, it would be something like this:

<?php
    // ...
    $imgPath = $SERVER['DOCUMENT_ROOT'].'/img/';
    $result = mysqli_query($link, "SELECT Images.basename FROM Products, Images WHERE Products.productId = Images.productId AND Products.productId = $productId)
    while($row = mysqli_fetch_assoc($result)) {
        unlink($imgPath.$row['Images.basename'].'.jpg');
        unlink($imgPath.$row['Images.basename'].'_tn.jpg');
    }
    // ...
?>

If you're concerned about unlink() performances, you could always use:

<?php
    // ...
    $imgPath = $SERVER['DOCUMENT_ROOT'].'/img/';
    $result = mysqli_query($link, "SELECT Images.basename FROM Products, Images WHERE Products.productId = Images.productId AND Products.productId = $productId)
    while($row = mysqli_fetch_assoc($result)) {
        shell_exec("rm {$imgPath}{$row['Images.basename']}*");
    }
    // ...
?>

Concerns about these solution might be about the additional query you'll have to run each time, unless you're pulling from Images already before in the script and if that's a concern at all.

1
  • Traditionally speaking, this is the right answer but in my case, the update script deletes all the products and replaces them. I'd need to implement a selective deletion. Thus isn't impossible at all, but it's just a bigger job and I'm not being paid for elegant solutions.
    – Oli
    Mar 23, 2015 at 8:02
1

The long term solution I'm erring towards is something at the end of my update script (Python/Django). I have a list of Car objects —so no more database querying— which makes this even faster. It also happens at the exact time old images cease being useful.

I'm using a Python set because it's probably the fastest way of checking. Into that I'm adding all stubs of the images I want to keep, then I'm iterating through the thumbnails (easier to glob), and deleting the files that aren't in the set.

# Generate a python "set" of image stubs
import itertools
imagehashes = set(itertools.chain(*map(lambda c: c.images.split('|'), cars)))

# Check which files aren't in the set and delete
import glob, os
for imhash in map(lambda i: i[25:-7], glob.glob('/path/to/images/*_tn.jpg')):
    if imhash in imagehashes:
        continue

    os.remove('/path/to/images/%s_tn.jpg' % imhash)
    os.remove('/path/to/images/%s.jpg' % imhash)

There are a few tricks with map and itertools to save a bit of time, but it's mostly self explanatory.

1

When pure bash doesn't cut it (or gets unnecessarily awkward), it's time to switch to a proper scripting language. My tool of choice is usually Perl, but you could use Python or Ruby or, heck, even PHP for this if you'd prefer.

That said, here's a simple Perl script that reads a list of prefixes from stdin (since you didn't specify exactly how you're obtaining this list), one per line, and deletes all files in the current directory with a .jpg suffix that don't have one of these prefixes:

#!/usr/bin/perl
use strict;
use warnings;

my @prefixes = <>;
chomp @prefixes;
# if you need to do any further input mangling, do it here

my $regex = join "|", map quotemeta, @prefixes;
$regex = qr/^($regex)/;   # anchor the regex and precompile it

foreach my $filename (<*.jpg>) {
    next if $filename =~ $regex;
    unlink $filename or warn "Error deleting $filename: $!\n";
}

If you'd prefer, you can compress that down to a one-liner, e.g.:

perl -e '$re = "^(" . join("|", map { chomp; "\Q$_" } <>) . ")"; unlink grep !/$re/, <*.jpg>'

Ps. In your case, since it's easy enough to extract the prefix from the file names, you could also use a hash instead of a regex to optimize the lookup, like this:

my %hash;
undef @hash{@prefixes};   # fastest way to add keys to a hash

foreach my $filename (<*.jpg>) {
    my ($prefix) = ($filename =~ /^([0-9a-f]+)/);
    next if exists $hash{$prefix};
    unlink $filename or warn "Error deleting $filename: $!\n";
}

However, even though this method scales better asymptotically (at least in practice; in theory, the regex engine could optimize the match to scale as well as the hash method), for just 500 prefixes there's no noticeable difference whatsoever.

At least on current Perl versions, however, the regex solution gets a lot slower once the number of alternatives exceeds a certain limit. For 32-byte prefixes, my testing showed a massive jump in execution time when the number of alternatives reached 6553, but the exact threshold apparently also depends on the length of the prefixes and on what else, if anything, the regex contains. This is apparently a quirk of the Perl regex engine and its optimizer, so other regex implementations (even PCRE ones) may exhibit different behavior.

4
  • That's quite fun but for the sake of performance, I would probably dump the regex lookup (for the same reason I did in grep and use an iterative index() to do a quick substring comparison. A hashtable would be even faster but I'm not Perly enough.
    – Oli
    Mar 23, 2015 at 11:55
  • @Oli: The regex is probably faster than any explicitly iterative solution, just because any looping is done inside the regex engine, written in highly optimized C. (And yes, I suspect that is true for Python too.) A hash table would indeed work, just like a set in Python; I've added a Perl example above. For just 500 prefixes or so, though, it's unlikely to matter -- any halfway sensible solution, even an explicit loop, would be more than fast enough in practice. Mar 23, 2015 at 14:55
  • Okay did a benchmark in Python, set > re > string.startswith(). I think that's as predicted but it's quite a huge difference.
    – Oli
    Mar 23, 2015 at 16:03
  • @Oli: I also did some testing in Perl (v5.18.2), and the results are... weird. The hash and regex solutions are about equally matched (in fact, the regex seems slightly faster) up to about 6500 prefixes, but then something strange happens, with the execution time jumping from 1.8 seconds for 6552 prefixes up to almost a minute for 6553(!). (Yes, that number is suspiciously close to 2**16 / 10; not sure why that should matter, though.) Clearly, there's something funny going on inside the Perl regex engine. Mar 23, 2015 at 16:33
0

The query is fast so it's the grep bit that bogs it all down.

Another solution would be to simply invert the query, so that you can pipe the results to rm directly.

This shouldn't introduce any difference in timing at all.

4
  • The problem with that (per my comment on your other answer) is that by this point the database doesn't have the filenames of the files that we want to delete, only the ones we want to keep. Hence needing to intersect it with a list of files that exist.
    – Oli
    Mar 23, 2015 at 10:52
  • @Oli Actually per your comment I assumed you could: "in my case, the update script deletes all the products and replaces them". Do you mind explain this line? I'm probably missunderstanding it.
    – kos
    Mar 23, 2015 at 11:00
  • Sure. Three times a day we dump the database and completely regenerate it from an external data source. There is no intermediate step where I check to see if a product has been removed between two versions of the database (and by extension, query those items for their files). The records are already gone. As I said before, I could change how this works but I'd rather not start altering how a mature and critical production system works, if I can help it.
    – Oli
    Mar 23, 2015 at 11:04
  • @Oli Ok I saw the updated comment. Then I can't imagine another way to get the inverted list of files to keep other than by performing an intersection somehow, which having a quadratic cost is the expensive thing here. I see the problem.
    – kos
    Mar 23, 2015 at 11:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .