As a matter of fact, they do not use the whole tablebase, as one may check by introducing the following pieces on the board:
Black: Bc3, Bd4, Kf2, Pf3.
The thing is, some positions are considered "uninteresting" because of the inevitable and obvious outcome of the game. Some of them, like the the positions with a lone king versus a king and five pieces, are simply omited from the calculations. However, every user of a tablebase may reject certain positions as trivial, and I believe the restriction used by the website you mention has many (or at least a few) of this rejections.
They certainly reduce the size of the standard tableblases at least to a tenth of the size you mention, since not even some basic pawn and kings endgames are covered (try Kg7 for white and Kg2 plus Pg3 for black), and this goes for both sides. Moreover, provided they use a similar technology as @oleksii does, I doubt they have any problem.
@Jason Lepack on the comments to the question said that the computer needs them. I ignore that, but after reading the article on Wikipedia and what I've seen on the website you provide and a few tries, I'm pretty sure that one does not.
About the smallest size, I would consider how to decide wether a position is "trivial" or not. I guess that esentially all positions involving a lone king vs king plus any number of pieces should be eliminated. Plus, most of the endings of king vs king and pawns, even with pawns on both sides, can be "solved" on a decent time by a computer. I'd also leave out any position where the material difference is greater than 3, since this would mean a piece down or four pawns up, which cannot be drawn even with different colour bishops... Continuing this way, one may get pretty light on memory size, I guess.
And the generator provided by @MikhailTal looks pretty awesome, now that's condensed information.