Holy smokes! I would never have thought the speed-up to be so drastic.
I reimplemented some logic using streams, and by golly, did that pay off.
#hash((#<age> . 28) (#<name> . Faye) (#<meal> . Fish) (#<drink> . Aqua))
#hash((#<age> . 27) (#<name> . John) (#<meal> . Beef) (#<drink> . Aqua))
#hash((#<age> . 27) (#<name> . Nina) (#<meal> . Stew) (#<drink> . Aqua))
cpu time: 15 real time: 41 gc time: 0
Edit: LOL, it's because it is too good to be true. My sucky code causes the evaluation of parts of the relations before it is even run... Sigh. It is cleaner with the streams, though, which isn't bad.
Just as I suspected, when amending the culprit:
#hash((#<drink> . Aqua) (#<age> . 28) (#<name> . Faye) (#<meal> . Fish))
#hash((#<drink> . Aqua) (#<age> . 27) (#<name> . John) (#<meal> . Beef))
#hash((#<drink> . Aqua) (#<age> . 27) (#<name> . Nina) (#<meal> . Stew))
cpu time: 1203 real time: 1905 gc time: 250