Tiny six-sided ice crystals slowly falling through the atmosphere create the effect. As they fall, the crystals align themselves parallel to the horizon, in effect simulating a colossal mirror made of billions of individual pieces. Wind moving the crystals causes the reflected light to stretch into a column.
You saw the pillar below the Sun. But pillars also occur that are above it or the Moon. Indeed, either of these celestial objects can be below the horizon while still creating pillars. And pillars formed by earthbound lights (which sit on the horizon) are always seen above the lights.
Indeed, some Egyptologists believe that Sun pillars were the inspiration for the great obelisks created by that culture in the same way that crepuscular rays inspired them to construct the pyramids. For more about this, see “Stargazing in ancient Egypt,” by Patricia Blackwell Gary and Richard Talcott, in the June 2006 issue of Astronomy.