Exponential growth in number of possible strategies with the increase in number of relations in a query has been identified as a major problem in the field of query optimization of relational databases. Present database systems use exhaustive search to find the best possible strategy. But as the size of a query grows, exhaustive search method itself becomes quite expensive. Other AI algorithms like A* algorithm, Simulated Annealing etc. have been suggested as a solution. However, all these algorithms fail to produce the best strategy; necessarily required for query execution. We did some modifications to the A* algorithm to produce a randomized form of the algorithm and compared it with the original A* algorithm and exhaustive search. The comparison results have shown improved A* algorithm to be almost equivalent in output quality along with a colossal decrease in search space in comparison to exhaustive search method.