Machine learning - PCA and KNN on rgb images are too slow
One possible approach is to train a classifier that, given a table, outputs its shape; train a classifier that, given a table, outputs its texture; train a classifier that, given a table, outputs its colour; and so on for each of the feature values you care about.  Thus, given a table, you can compute a feature vector that has the value of each of these attributes.  You can then define a distance metric on these feature vectors (e.g., some kind of weighted L2 distance), which will let you measure how similar two tables are by comparing their feature vectors.

Once you've done this, there's a straightforward way to find the most similar tables.  Use the classifiers to find the feature vectors for all the tables.  Then, use k-nearest neighbors to find the k most similar images to each given image.  If the number of features is not too large, this should be efficient, as you are now doing k-NN in a low-dimensional space.  For instance, you can use k-d trees or other data structures for nearest neighbor search to speed up the search.  These data structures are a lot more efficient when the number of dimensions is small.

I expect this should be plenty efficient for your needs.  Handling 4000 table images should be no problem.

There are other possible approaches as well, but the above is the first thing I'd try.