You could expand each regex to a regex on the whole table, and then take the intersection of the corresponding NFA/DFAs. Unfortunately, I suspect this takes exp

You could expand each regex to a regex on the whole table, and then take the intersection of the corresponding NFA/DFAs. Unfortunately, I suspect this takes exponential (or worse?) time in the worst case.