Given rational numbers $a$ and $b$, what is the fastest way to determine whether there are any rational solutions to $a=x^2+by^2$?

I am interested in the case where the numerator and denominator of $a$ have about $4$ digits, and those of $b$ have about $8$ digits. I am willing to restrict attention to solutions where $x$ and $y$ also have numerators and denominators that are not too large, if that will help. I would like to solve a large number of problems of this type, perhaps tens of millions, so efficiency is important. Both $a$ and $b$ will be different for each problem. I would also be interested in heuristics for roughly how often rational solutions exist.